Design of Single and Multiobjective Metaheuristic Algorithms for Effective Data Clustering

Abstract

Clustering is an important data analysis technique to find similar data objects in a given dataset. It is unsupervised learning and has proven its capability in diverse research fields such as medical diagnosis, market segmentation, image segmentation, customer behaviour analysis, outlier detection, and feature selection. Clustering aims to determine the set of identical data objects and put these data objects into a single cluster. The data objects within the clusters have more similar characteristics than other clusters. The research community presents several clustering techniques- partitional, hierarchal, model-based, grid-based, density-based, etc. But, the popular one is partitional clustering. This thesis work focuses on partitional clustering. In partitional clustering, a dataset divides into k number of partitions known as clusters. A distance function is utilized for allocating the data objects to clusters based on minimum distance. However, the number of clusters (k) should be known in advance. The performances of partitional clustering algorithms depend on the selection of initial cluster centroids. Several traditional algorithms, like K-Means, K-Mediods, K-Harmonic Mean etc., are successfully implemented for solving partitional clustering problems. But, these algorithms have several drawbacks, such as being sensitive to initial cluster selection, local optima, convergence rate and predefined method for updating cluster centroids. Several researchers explore metaheuristic algorithms capabilities to overcome the issues of traditional clustering algorithms. These are GA, PSO, ACO, ABC, TS, SA etc., and provide state-of-the-art clustering results for partitional clustering problems. However, some issues are also associated with metaheuristic algorithms, such as an imbalance in local search and global search mechanisms, population diversity, sometimes stuck in local optima, and population generation. This thesis work considers the aforementioned problems of metaheuristic algorithms and proposes new algorithms to handle the partitional clustering problems efficiently. This thesis presents two new partitional clustering algorithms, improved water wave optimization (IWWO) and improved bat (IBAT) algorithm for clustering problems. The WWO algorithm is improved using the global best direction and decay operator concept. IBAT is an improved variant of the bat algorithm. It is seen that several shortcomings are associated with the bat algorithm, such as population initialization, local optima and convergence rate. These issues of the bat algorithm are successfully resolved in the IBAT algorithm using an enhanced cooperative coevolution strategy, an elitist strategy and a neighbourhood-search scheme. The performance is evaluated using well-known benchmark clustering datasets and compared with several existing clustering algorithms. A set of performance parameters also validate the results of IWWO and IBAT algorithms. Both algorithms successfully overcome the issues related to WWO and BAT algorithms. During the experiment, it is seen that a single objective function is considered for solving the clustering problems. Still, sometimes, it generates a biased solution due to a single objective function for handling clustering problems. The biasing issue can be addressed effectively using more than one objective function. This thesis also presents a multiobjective clustering algorithm for handling the biasing issue. In multiobjective clustering, two objective functions are considered that conflict with each other. In this thesis, Euclidean distance and connectedness are objective functions for multiobjective clustering. Further, these functions are integrated into the vibrating particle system algorithm, MOVPS. The simulation results of MOVPS are compared with several multiobjective and single-objective clustering algorithms. The proposed MOVPS achieves far better clustering results than single and multiobjective clustering algorithms.