Application of a New Hybrid Optimization Algorithm on Cluster Analysis

Authors: T. Niknam, M. Nayeripour, B.Bahmani Firouzi

Abstract:

Clustering techniques have received attention in many areas including engineering, medicine, biology and data mining. The purpose of clustering is to group together data points, which are close to one another. The K-means algorithm is one of the most widely used techniques for clustering. However, K-means has two shortcomings: dependency on the initial state and convergence to local optima and global solutions of large problems cannot found with reasonable amount of computation effort. In order to overcome local optima problem lots of studies done in clustering. This paper is presented an efficient hybrid evolutionary optimization algorithm based on combining Particle Swarm Optimization (PSO) and Ant Colony Optimization (ACO), called PSO-ACO, for optimally clustering N object into K clusters. The new PSO-ACO algorithm is tested on several data sets, and its performance is compared with those of ACO, PSO and K-means clustering. The simulation results show that the proposed evolutionary optimization algorithm is robust and suitable for handing data clustering.

Keywords: Ant Colony Optimization (ACO), Data clustering, Hybrid evolutionary optimization algorithm, K-means clustering, Particle Swarm Optimization (PSO).

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1075806

References:

[1] Yi-Tung Kao, Erwie Zahara and I-Wei Kao, "A hybridized approach to data clustering" Expert Systems with Applications, Volume 34, Issue 3, pp. 1754-1762, April 2008.
[2] J.F. Lu, J.B. Tang, Z.M. Tang and J.Y. Yang, "Hierarchical initialization approach for K-Means clustering", Pattern Recognition Letters, January 2008.
[3] Hong Zhou and Yonghuai Liu, "Accurate integration of multi-view range images using k-means clustering", Pattern Recognition, Volume 41, Issue 1, pp. 152-175, January 2008.
[4] Michael Laszlo and Sumitra Mukherjee , "A genetic algorithm that exchanges neighboring centers for k-means clustering", Pattern Recognition Letters, Volume 28, Issue 16, pp. 2359-2366, 1 December 2007.
[5] Amir Ahmad and Lipika Dey , "A k-mean clustering algorithm for mixed numeric and categorical data", Data & Knowledge Engineering, Volume 63, Issue 2, pp. 503-527, November 2007.
[6] Chung-Chian Hsu, Chin-Long Chen and Yu-Wei Su , "Hierarchical clustering of mixed data based on distance hierarchy", Information Sciences, Volume 177, Issue 20, 15, pp. 4474-4492, October 2007.
[7] Mohammad Fathian, Babak Amiri and Ali Maroosi , "Application of honey-bee mating optimization algorithm on clustering", Applied Mathematics and Computation, Volume 190, Issue 2, pp. 1502-1513, July 2007.
[8] Stephen J. Redmond and Conor Heneghan , "A method for initialising the K-means clustering algorithm using kd-trees", Pattern Recognition Letters, Volume 28, Issue 8, pp. 965-973, June 2007.
[9] Georgios P. Papamichail and Dimitrios P. Papamichail , "The k-means range algorithm for personalized data clustering in e-commerce", European Journal of Operational Research, Volume 177, Issue 3, pp. 1400-1408, March 2007
[10] R.J. Kuo, H.S. Wang, Tung-Lai Hu and S.H. Chou , "Application of ant K-means on clustering analysis", Computers & Mathematics with Applications, Volume 50, Issues 10-12, pp. 1709-1724, November- December 2005.
[11] P. S. Shelokar, V. K. Jayaraman and B. D. Kulkarni ",An ant colony approach for clustering ",Analytica Chimica Acta, Volume 509, Issue 2, pp. 187-195, May 2004.
[12] Michael K. Ng and Joyce C. Wong , "Clustering categorical data sets using tabu search techniques", Pattern Recognition, Volume 35, Issue 12, December 2002, pp. 2783-2790
[13] C. S. Sung and H. W. Jin, "A tabu-search-based heuristic for clustering", Pattern Recognition, Volume 33, Issue 5, pp. 849-858, May 2000.
[14] Khaled S. Al-Sultan, "A Tabu search approach to the clustering problem", Pattern Recognition, Volume 28, Issue 9, pp. 1443- 1451, September 1995.
[15] Michael Laszlo and Sumitra Mukherjee, "A genetic algorithm that exchanges neighboring centers for k-means clustering" Pattern Recognition Letters, Volume 28, Issue 16, pp. 2359-2366, December 2007
[16] J. Olamaei , T. Niknam and G. Gharehpetian, "Application of Particle Swarm Optimization for Distribution Feeder Reconfiguration Considering Distributed Generators", accepted for future publication in Applied Mathematics and Computation journal, 2008.
[17] J. Kennedy and R. Eberhart, "Particle Swarm Optimization," IEEE International Conf. on Neural Networks, Piscataway, NJ, vol. 4, pp. 1942- 1948, 1995.
[18] T. Niknam, "An Approach Based on Particle Swarm Optimization for Optimal Operation of Distribution Network Considering Distributed Generators,", 32nd Annual Conference onIEEE Industrial Electronics, IECON 2006 , pp. :633 - 637
[19] T. Niknam , A.M. Ranjbar and A.R. Shirani, "A new approach for distribution state estimation based on ant colony algorithm with regard to distributed generation" Journal of Intelligent and Fuzzy Systems, vol. 16, no. 2, pp.119-131, June 2005.
[20] T.Niknam, H. Arabian and M. Mirjafari, "Reactive power pricing in deregulated environments using novel search methods" Proceedings of 2004 International Conference on Machine Learning and Cybernetics, 2004, vol. 7, p.p. 4234 - 4239, Aug. 2004
[21] T. Niknam, A.M. Ranjbar, and A.R. Shirani, "A new approach based on ant algorithm for Volt/Var control in distribution network considering distributed generation," Iranian Journal of Science & Technology, Transaction B, vol. 29, no. B4, pp. 1-15, 2005.
[22] M. Dorigo, G.D. Caro and L.M. Gambardella, "Ants algorithms for discrete optimization", Artificial Life, vol. 5, no. 3, pp. 137-172, 1999.