Improved Self-Adaptive ACS Algorithm to Determine the Optimal Number of Clusters

Ayad Mohammed Jabbar, Ku Ruhana Ku-Mahamud, Rafid Sagban

Abstract


A fundamental problem in data clustering is how to determine the correct number of clusters. The k-adaptive medoid set ant colony optimization (ACO) clustering (METACOC-K) algorithm is superior in solving clustering problems. However, METACOC-K does not guarantee in finding the best number of clusters. It assumed the number of clusters based on an adaptive parameter strategy that lacks feedback learning. This has restrained the algorithm in producing compact clusters and the optimal number of clusters. In this paper, a self-adaptive ACO clustering (S-ACOC) algorithm is proposed to produce the optimal number of clusters by incorporating a self-adaptive parameter strategy. The S-ACOC algorithm is a centroid-based algorithm that automatically adjusts the number of clusters during the algorithm run. The selection of the number of clusters is based on a construction graph that reflects the influence of a pheromone in algorithm learning. Experiments were conducted on real-world datasets to evaluate the performance of the proposed algorithm. The external evaluation metrics (purity, F-measure, and entropy) were used to compare the results of the proposed algorithm with other swarm clustering algorithms, including a genetic algorithm (GA), particle swarm optimization (PSO), and METACOC-K. Results showed that S-ACOC provides higher purity (50%) and lower entropy (40%) than GA, PSO, and METACOC-K. Experiments were also performed on several predefined clusters, and results demonstrate that the S-ACOC algorithm is superior to GA, PSO, and METACOC-K. Based on the superior performance, S-ACOC can be used to solve clustering problems in various application domains. 


Keywords


Data clustering; parameter selection; optimization-based clustering; ant colony optimization.

Full Text:

PDF

References


T. Herawan, R. Ghazali, and M. M. Deris, “A New Algorithm for Incremental Web Page Clustering Based on k-Means and Ant Colony Optimization,†Adv. Intell. Syst. Comput., vol. 287, pp. 347–357, 2014, doi: 10.1007/978-3-319-07692-8.

A. M. Jabbar, K. R. Ku-Mahamud, and R. Sagban, “An improved ACS algorithm for data clustering,†Indones. J. Electr. Eng. Comput. Sci., vol. 17, no. 3, pp. 1506–1515, 2019, doi: 10.11591/ijeecs.v17.i3.pp1506-1515.

K. Aparna, “Evolutionary computing based hybrid bisecting clustering algorithm for multidimensional data,†SÄdhanÄ, vol. 0123456789, 2019, doi: 10.1007/s12046-018-1011-y.

R. Ünlü and P. Xanthopoulos, “Estimating the number of clusters in a dataset via consensus clustering,†Expert Syst. Appl., vol. 125, pp. 33–39, 2019, doi: 10.1016/j.eswa.2019.01.074.

A. Mutoh, M. Wada, and K. Amano, “Comprehensive cluster validity Index based on structural simplicity,†pp. 1–2, 2019.

O. Arbelaitz, I. Gurrutxaga, J. Muguerza, J. M. Pérez, and I. Perona, “An extensive comparative study of cluster validity indices,†Pattern Recognit., vol. 46, no. 1, pp. 243–256, 2013.

R. Xu, J. Xu, and D. C. Wunsch, “A Comparison Study of Validity Indices on Swarm-Intelligence-Based Clustering,†IEEE Trans. Syst. Man. Cybern., vol. 42, no. 4, pp. 1243–1256, 2012.

S. Zhou and Z. Xu, “A novel internal validity index based on the cluster centre and the nearest neighbour cluster,†Appl. Soft Comput. J., vol. 71, pp. 78–88, 2018, doi: 10.1016/j.asoc.2018.06.033.

C. W. Wang and J. I. G. Hwang, “Automatic clustering using particle swarm optimization with various validity indices,†2012 5th Int. Conf. Biomed. Eng. Informatics, BMEI 2012, no. Bmei, pp. 1557–1561, 2012, doi: 10.1109/BMEI.2012.6513143.

X. Gao and S. Wu, “CUBOS: An Internal Cluster Validity Index for Categorical Data,†Teh. Vjesn. - Tech. Gaz., vol. 26, no. 2, pp. 486–494, 2019, doi: 10.17559/tv-20190109015453.

M. Ren, P. Liu, Z. Wang, and J. Yi, “ A Self-Adaptive Fuzzy c -Means Algorithm for Determining the Optimal Number of Clusters ,†Comput. Intell. Neurosci., vol. 2016, no. 1, pp. 1–12, 2016, doi: 10.1155/2016/2647389.

R. J. K. F. E. Zulvia, “Automatic clustering using an improved artificial bee colony optimization for customer segmentation,†Knowl. Inf. Syst., no. 43, 2018, doi: 10.1007/s10115-018-1162-5.

R. J. Kuo and F. E. Zulvia, “Automatic Clustering Using an Improved Particle Swarm Optimization,†J. Ind. Intell. Inf., vol. 1, no. 1, pp. 46–51, 2013.

A. Abubaker, A. Baharum, and M. Alrefaei, “Automatic clustering using multi-objective particle swarm and simulated annealing,†PLoS One, vol. 10, no. 7, 2015, doi: 10.1371/journal.pone.0130995.

S. Supratid and P. Julrode, “Differential Evolution for Fuzzy Clustering Using Self-Adaptive Trade-Off Between Exploitation and Exploration,†Res. J. Appl. Sci., pp. 452–460, 2014.

S. Kapoor, I. Zeya, C. Singhal, and S. J. Nanda, “A Grey Wolf Optimizer Based Automatic Clustering Algorithm for Satellite Image Segmentation,†Procedia Comput. Sci., vol. 115, pp. 415–422, 2017, doi: 10.1016/j.procs.2017.09.100.

A. M. Jabbar, K. R. Ku-Mahamud, and R. Sagban, “Ant-based sorting and ACO-based clustering approaches: A review,†in IEEE Symposium on Computer Applications & Industrial Electronics (ISCAIE), Apr. 2018, pp. 217–223.

A. M. Jabbar, K. R. Ku-Mahamud, and R. Sagban, “Balancing Exploration and Exploitation in ACS Algorithms for Data Clustering,†vol. 97, no. 16, pp. 4320–4333, 2019.

M. López-Ibáñez and T. Stützle, “An experimental analysis of design choices of multi-objective ant colony optimization algorithms,†Swarm Intell., vol. 6, no. 3, pp. 207–232, 2012, doi: 10.1007/s11721-012-0070-7.

H. N. K. AL-Behadili, K. R. Ku-Mahamud, and R. Sagban, “Hybrid ant colony optimization and genetic algorithm for rule induction,†J. Comput. Sci., vol. 16, no. 7, pp. 1019–1028, 2020, doi: 10.3844/JCSSP.2020.1019.1028.

H. N. K. Al-Behadili, R. Sagban, and K. R. Ku-Mahamud, “Adaptive parameter control strategy for ant-miner classification algorithm,†Indones. J. Electr. Eng. Informatics, vol. 8, no. 1, pp. 149–162, 2020, doi: 10.11591/ijeei.v8i1.1423.

H. N. K. Al-Behadili, K. R. Ku-Mahamud, and R. Sagban, “Rule pruning techniques in the ant-miner classification algorithm and its variants: A review,†in IEEE Symposium on Computer Applications and Industrial Electronics(ISCAIE), 2018, pp. 47–56, doi: 10.1109/ISCAIE.2018.8405448.

H. N. K. Al-behadili, K. R. Ku-mahamud, and R. Sagban, “Annealing strategy for an enhance rule pruning technique in ACO-based rule classification,†Indones. J. Electr. Eng. Comput. Sci., vol. 16, no. 3, pp. 1499–1507, 2019, doi: 10.11591/ijeecs.v16.i3.pp1499-1507.

H. N. K. Al-Behadili, K. R. Ku-Mahamud, and R. Sagban, “Ant colony optimization algorithm for rule-based classification: Issues and potential solutions,†J. Theor. Appl. Inf. Technol., vol. 96, no. 21, pp. 7139–7150, 2018.

H. N. K. Al-Behadili, K. R. Ku-Mahamud, and R. Sagban, “Hybrid Ant Colony Optimization and Iterated Local Search for Rules-Based Classification,†J. Theor. Appl. Inf. Technol., vol. 98, no. 04, pp. 657–671, 2020.

T. İnkaya, S. Kayalıgil, and N. E. Özdemirel, “Ant Colony Optimization based clustering methodology,†Appl. Soft Comput., pp. 301–311, 2015.

A. M. Jabbar, K. R. Ku-Mahamud, and R. Sagban, “Modified ACS Centroid Memory for Data Clustering,†J. Comput. Sci., vol. 15, no. 10, pp. 1439–1449, 2019, doi: 10.3844/jcssp.2019.1439.1449.

J. Wahid and H. F. A. Al-Mazini, “Classification of Cervical Cancer Using Ant-Miner for Medical Expertise Knowledge Management,†Knowl. Manag. Int. Conf., no. November, 2018.

H. D. Menéndez, F. E. B. Otero, and D. Camacho, “Medoid-based clustering using ant colony optimization,†Swarm Intell., vol. 10, no. 2, pp. 123–145, 2016.

T. Stützle et al., “Parameter adaptation in ant colony optimization,†in Autonomous Search, vol. 9783642214, 2012, pp. 191–215.

M. Maur, M. López-Ibáñez, and T. Stützle, “Pre-scheduled and adaptive parameter variation in MAX-MIN ant system,†2010 IEEE World Congr. Comput. Intell. WCCI 2010 - 2010 IEEE Congr. Evol. Comput. CEC 2010, no. August, 2010, doi: 10.1109/CEC.2010.5586332.

A. E. Eiben and S. K. Smit, “Parameter tuning for configuring and analyzing evolutionary algorithms,†Swarm and Evolutionary Computation, vol. 1, no. 1. pp. 19–31, 2011.

Y. Kao and K. Cheng, “An ACO-Based Clustering Algorithm,†ANTS Int. Work. Ant Colony Optim. Swarm Intell., vol. 4150/2006, pp. 340–347, 2006.

K. Velusamy and R. Manavalan, “Performance Analysis of Unsupervised Classification based on Optimization,†Int. J. Comput. Appl., vol. 42, no. 19, pp. 22–27, 2012, doi: 10.5120/5801-8090.

K. M. Salama, A. M. Abdelbar, and A. a. Freitas, “Multiple pheromone types and other extensions to the Ant-Miner classification rule discovery algorithm,†Swarm Intell., vol. 5, no. 3–4, pp. 149–182, Jun. 2011, doi: 10.1007/s11721-011-0057-9.

R. Forsati, A. Keikha, and M. Shamsfard, “An improved bee colony optimization algorithm with an application to document clustering,†Neurocomputing, vol. 159, no. 1, pp. 9–26, 2015, doi: 10.1016/j.neucom.2015.02.048.

B. Desgraupes, “Clustering Indices,†CRAN Packag., no. April, pp. 1–10, 2013, [Online]. Available: cran.r-project.org/web/packages/clusterCrit.

J. Chavarria-Molina, J. J. Fallas-Monge, and J. Trejos-Zelaya, “Clustering via Ant Colonies: Parameter Analysis and Improvement of the Algorithm,†2019, [Online]. Available: http://arxiv.org/abs/1912.01105.

S. Zhu and L. Xu, “Many-objective fuzzy centroids clustering algorithm for categorical data,†Expert Syst. Appl., vol. 96, pp. 230–248, 2018, doi: 10.1016/j.eswa.2017.12.013.

M. H. Chehreghani, H. Abolhassani, and M. H. Chehreghani, “Improving density-based methods for hierarchical clustering of web pages,†Data Knowl. Eng., vol. 67, no. 1, pp. 30–50, 2008.

M. Haghir, H. Abolhassani, and M. Haghir, “Improving density-based methods for hierarchical clustering of web pages,†Data Knowl. Eng., vol. 67, pp. 30–50, 2008.

K. Bache and M. Lichman, “UCI Machine Learning Repository,†Univ. Calif. Irvine Sch. Inf., vol. 20, no. 8, 2013, doi: University of California, Irvine, School of Information and Computer Sciences.

M. Kudo and J. Sklansky, “Comparison of algorithms that select features for pattern classifiers,†Pattern Recognit., vol. 33, no. 1, pp. 25–41, 2000, doi: 10.1016/S0031-3203(99)00041-2.

T. Niknam and B. Amiri, “An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis,†Appl. Soft Comput. J., vol. 10, no. 1, pp. 183–197, 2010.




DOI: http://dx.doi.org/10.18517/ijaseit.11.3.11723

Refbacks

  • There are currently no refbacks.


Published by INSIGHT - Indonesian Society for Knowledge and Human Development