A novel optimization approach towards improving separability of clusters. (April 2023)

• Record Type: Journal Article
• Authors: Bagirov, Adil; Hoseini-Monjezi, Najmeh; Taheri, Sona
• Is Part Of: Computers & operations research. Volume 152(2023)
• Publication Date: 2023-04
• Subjects: Cluster analysis -- Incremental clustering -- Cluster validity indices -- Nonsmooth optimization; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.106135
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: The objective functions in optimization models of the sum-of-squares clustering problem reflect intra-cluster similarity and inter-cluster dissimilarities and in general, optimal values of these functions can be considered as appropriate measures for compactness of clusters. However, the use of the objective function alone may not lead to the finding of separable clusters. To address this shortcoming in existing models for clustering, we develop a new optimization model where the objective function is represented as a sum of two terms reflecting the compactness and separability of clusters. Based on this model we develop a two-phase incremental clustering algorithm. In the first phase, the clustering function is minimized to find compact clusters and in the second phase, a new model is applied to improve the separability of clusters. The Davies–Bouldin cluster validity index is applied as an additional measure to compare the compactness of clusters and silhouette coefficients are used to estimate the separability of clusters. The performance of the proposed algorithm is demonstrated and compared with that of four other algorithms using synthetic and real-world data sets. Numerical results clearly show that in comparison with other algorithms the new algorithm is able to find clusters with better separability and similar compactness. Highlights: New optimization model is formulated for hard partitional clustering problem. Novel incremental algorithm is developed to find compact and well-separated clusters. Performance of algorithm is tested and compared with other clustering algorithms. Davies–Bouldin cluster validity index is applied to compare compactness of clusters. Silhouette coefficients are used to estimate separability of clusters.