A Multi-Objective Particle Swarm Optimization Approach  for Optimizing K-Means Clustering Centroids

Aina Latifa Riyana Putri; Joko Riyono; Christina Eni Pujiastuti; Supriyadi

doi:10.29207/resti.v9i3.6533

Aina Latifa Riyana Putri Telkom University
Joko Riyono Universitas Trisakti
Christina Eni Pujiastuti Universitas Trisakti
Supriyadi Universitas Trisakti

DOI: https://doi.org/10.29207/resti.v9i3.6533

Keywords: centroid, k-means, multiobjective particle swarm optimization, the sum of square within, the sum of square between

Abstract

The K-Means algorithm is a popular unsupervised learning method used for data clustering. However, its performance heavily depends on centroid initialization and the distribution shape of the data, making it less effective for datasets with complex or non-linear cluster structures. This study evaluates the performance of the standard K-Means algorithm and proposes a Multiobjective Particle Swarm Optimization K-Means (MOPSO+K-Means) approach to improve clustering accuracy. The evaluation was conducted on five benchmark datasets: Atom, Chainlink, EngyTime, Target, and TwoDiamonds. Experimental results show that K-Means is effective only on datasets with clearly separated clusters, such as EngyTime and TwoDiamonds, achieving accuracies of 95.6% and 100%, respectively. In contrast, MOPSO+K-Means achieved a substantial accuracy improvement on the complex Target dataset, increasing from 0.26% to 59.2%. The TwoDiamonds dataset achieved the most desirable trade-off: it had the lowest SSW (1323.32), relatively high SSB (2863.34), and lowest standard deviation values, indicating compact clusters, good separation, and high consistency across runs. These findings highlight the potential of swarm-based optimization to achieve consistent and accurate clustering results on datasets with varying structural complexity.

Downloads

Download data is not yet available.

References

To overcome this limitation, future work could explore the extension of MOPSO to simultaneously optimize both the number of clusters and the centroid positions. This could be framed as a multi-objective optimization problem—balancing cluster compactness, separation, and model complexity—or as a constrained optimization task where k is bounded within a reasonable range. Such an approach would enhance the applicability of the method in real-world scenarios, allowing it to autonomously discover both the optimal clustering structure and its corresponding parameters without relying on prior knowledge.

Conclusions

Based on the analysis and evaluation of five benchmark datasets, it can be concluded that the performance of the K-Means algorithm is highly dependent on the shape and structural characteristics of the clusters in the data. On datasets with simple and linearly separable structures, such as TwoDiamonds and EngyTime, K-Means performs very well, achieving high accuracy—up to 100%. However, on datasets with non-linear or complex structures, such as Atom, ChainLink, and Target, the algorithm fails to properly separate clusters, resulting in low accuracy and poor alignment with the ground truth.

To address these limitations, the MOPSO+K-Means approach was introduced as an alternative solution. Based on the experimental results, this algorithm shows significant performance improvement on datasets with complex structures—most notably on the Target dataset, where the accuracy increased from 26% (K-Means) to 59.2% (MOPSO+K-Means). In addition, the obtained SSW and SSB values, along with relatively low standard deviations, indicate that MOPSO-K-Means can produce stable and consistent clustering solutions.

Overall, MOPSO+K-Means has proven to be more flexible and reliable in handling various types of cluster structures, making it a more suitable choice for clustering tasks involving non-convex or non-linearly separable data distributions. Such characteristics are often found in real-world applications, including biomedical data analysis where patient subgroups may form irregular patterns, sensor grouping in IoT environments with overlapping signal zones, and document clustering tasks where semantic relationships are not linearly separable. These application domains can benefit from algorithms that offer both structural flexibility and solution stability, as demonstrated by MOPSO+K-Means in this study.

Acknowledgements

This work was supported by Telkom University.

References

T. M. Ghazal et al., “Performances of K-Means Clustering Algorithm with Different Distance Metrics,” Intelligent Automation & Soft Computing, vol. 30, no. 2, pp. 735–742, Aug. 2021, doi: 10.32604/IASC.2021.019067.

M. Ahmed, R. Seraj, and S. M. S. Islam, “The k-means Algorithm: A Comprehensive Survey and Performance Evaluation,” Electronics 2020, Vol. 9, Page 1295, vol. 9, no. 8, p. 1295, Aug. 2020, doi: 10.3390/ELECTRONICS9081295.

A. Abdulhafedh, “Incorporating K-means, Hierarchical Clustering and PCA in Customer Segmentation,” Journal of City and Development, vol. 3, no. 1, 2021.

P. Patel, B. Sivaiah, and R. Patel, “Approaches for finding Optimal Number of Clusters using K-Means and Agglomerative Hierarchical Clustering Techniques,” in 2022 International Conference on Intelligent Controller and Computing for Smart Power, ICICCSP 2022, 2022. doi: 10.1109/ICICCSP53532.2022.9862439.

A. Vouros, S. Langdell, M. Croucher, and E. Vasilaki, “An empirical comparison between stochastic and deterministic centroid initialisation for K-means variations,” Mach Learn, vol. 110, no. 8, pp. 1975–2003, Aug. 2021, doi: 10.1007/S10994-021-06021-7/FIGURES/8.

A. Qtaish, M. Braik, D. Albashish, M. T. Alshammari, A. Alreshidi, and E. J. Alreshidi, “Optimization of K-means clustering method using hybrid capuchin search algorithm,” Journal of Supercomputing, vol. 80, no. 2, 2024, doi: 10.1007/s11227-023-05540-5.

Z. Zhang, Q. Feng, J. Huang, Y. Guo, J. Xu, and J. Wang, “A local search algorithm for k-means with outliers,” Neurocomputing, vol. 450, pp. 230–241, Aug. 2021, doi: 10.1016/J.NEUCOM.2021.04.028.

A. A. Wani, “Comprehensive analysis of clustering algorithms: exploring limitations and innovative solutions,” PeerJ Comput Sci, vol. 10, pp. 1–45, Aug. 2024, doi: 10.7717/PEERJ-CS.2286/FIG-14.

R. Gustriansyah, N. Suhandi, and F. Antony, “Clustering optimization in RFM analysis Based on k-Means,” IJEECS, vol. 18, no. 1, pp. 470–477, Apr. 2020, doi: 10.11591/ijeecs.v18.i1.pp470-477.

R. Richard, H. Cao, and M. Wachowicz, “An Automated Clustering Process for Helping Practitioners to Identify Similar EV Charging Patterns across Multiple Temporal Granularities,” International Conference on Smart Cities and Green ICT Systems, pp. 67–77, 2021, doi: 10.5220/0010485000670077.

M. T. Guerreiro et al., “Anomaly Detection in Automotive Industry Using Clustering Methods—A Case Study,” Applied Sciences 2021, Vol. 11, Page 9868, vol. 11, no. 21, p. 9868, Oct. 2021, doi: 10.3390/APP11219868.

M. Jain, V. Saihjpal, N. Singh, and S. B. Singh, “An Overview of Variants and Advancements of PSO Algorithm,” MDPI Applied Sciences, 2022, doi: 10.3390/app12178392.

M. C. Thrun and A. Ultsch, “Clustering benchmark datasets exploiting the fundamental clustering problems,” Data Brief, vol. 30, p. 105501, Jun. 2020, doi: 10.1016/J.DIB.2020.105501.

A. Ultsch, “Strategies for an Artificial Life System to cluster high dimensional Data,” 2004, Accessed: Apr. 14, 2025. [Online]. Available: https://www.researchgate.net/publication/228932819

A. Ultsch, G. Guimaraes, D. Korus, and H. Li, “Knowledge Extraction from Artificial Neural Networks and Applications,” Parallele Datenverarbeitung mit dem Transputer, pp. 148–162, 1994, doi: 10.1007/978-3-642-78901-4_11.

P. Mangiameli, S. K. Chen, and D. West, “A comparison of SOM neural network and hierarchical clustering methods,” Eur J Oper Res, vol. 93, no. 2, pp. 402–417, Sep. 1996, doi: 10.1016/0377-2217(96)00038-0.

S. P. Chatzis and D. I. Kosmopoulos, “A variational Bayesian methodology for hidden Markov models utilizing Student’s-t mixtures,” Pattern Recognit, vol. 44, no. 2, pp. 295–306, Feb. 2011, doi: 10.1016/J.PATCOG.2010.09.001.

J. Poelmans, M. M. Van Hulle, S. Viaene, P. Elzinga, and G. Dedene, “Text mining with emergent self organizing maps and multi-dimensional scaling: A comparative study on domestic violence,” Appl Soft Comput, vol. 11, no. 4, pp. 3870–3876, Jun. 2011, doi: 10.1016/J.ASOC.2011.02.026.

A. Ultsch, “U *-Matrix : a Tool to visualize Clusters in high dimensional Data,” 2004.

A. Ultsch, “Density Estimation and Visualization for Data Containing Clusters of Unknown Structure,” Studies in Classification, Data Analysis, and Knowledge Organization, pp. 232–239, 2005, doi: 10.1007/3-540-28084-7_25.

B. Khusul Khotimah, F. Irhamni, and T. Sundarwati, “A GENETIC ALGORITHM FOR OPTIMIZED INITIAL CENTERS K-MEANS CLUSTERING IN SMEs,” J Theor Appl Inf Technol, vol. 15, no. 1, 2016, Accessed: Jun. 13, 2025. [Online]. Available: www.jatit.org

H. He, B. Sun, Y. Yang, and S. Liu, “An improved K-Means clustering based on differential evolution,” J Phys Conf Ser, vol. 2595, no. 1, p. 012010, Sep. 2023, doi: 10.1088/1742-6596/2595/1/012010.

A. Hassanat, K. Almohammadi, E. Alkafaween, E. Abunawas, A. Hammouri, and V. B. S. Prasath, “Choosing Mutation and Crossover Ratios for Genetic Algorithms—A Review with a New Dynamic Approach,” Information 2019, Vol. 10, Page 390, vol. 10, no. 12, p. 390, Dec. 2019, doi: 10.3390/INFO10120390.

M. Jain, V. Saihjpal, N. Singh, and S. B. Singh, “An Overview of Variants and Advancements of PSO Algorithm,” Applied Sciences 2022, Vol. 12, Page 8392, vol. 12, no. 17, p. 8392, Aug. 2022, doi: 10.3390/APP12178392.