An Optimized K-Harmonic Means Algorithm Combined with Modified Particle Swarm Optimization and Cuckoo Search Algorithm

Bouyer, Asgarali

doi:10.1515/fcds-2016-0006

Abstract

Among the data clustering algorithms, k-means (KM) algorithm is one of the most popular clustering techniques due to its simplicity and efficiency. However, k-means is sensitive to initial centers and it has the local optima problem. K-harmonic-means (KHM) clustering algorithm solves the initialization problem of k-means algorithm, but it also has local optima problem. In this paper, we develop a new algorithm for solving this problem based on an improved version of particle swarm optimization (IPSO) algorithm and KHM clustering. In the proposed algorithm, IPSO is equipped with Cuckoo Search algorithm and two new concepts used in PSO in order to improve the efficiency, fast convergence and escape from local optima. IPSO updates positions of particles based on a combination of global worst, global best with personal worst and personal best to dynamically be used in each iteration of the IPSO. The experimental result on five real-world datasets and two artificial datasets confirms that this improved version is superior to k-harmonic means and regular PSO algorithm. The results of the simulation show that the new algorithm is able to create promising solutions with fast convergence, high accuracy and correctness while markedly improving the processing time.

References

[1] Abdel-Kader, R.F. Genetically Improved PSO Algorithm for Efficient Data Clustering. in Machine Learning and Computing (ICMLC), 2010 Second International Conference on.2010, 71-75.10.1109/ICMLC.2010.19
Search in Google Scholar
[2] Abdeyazdan, M., Data clustering based on hybrid K-harmonic means and modifier imperialist competitive algorithm. Journal of Supercomputing, 68, 2, 2014, 574-598.10.1007/s11227-013-1053-1
Search in Google Scholar
[3] Anaya, A.R. and J.G. Boticario, Application of machine learning techniques to analyse student interactions and improve the collaboration process. Expert Syst. Appl., 38, 2, 2011, 1171-1181.10.1016/j.eswa.2010.05.010
Search in Google Scholar
[4] Benameur, L., J. Alami, and A. El Imrani. A New Hybrid Particle Swarm Optimization Algorithm for Handling Multiobjective Problem Using Fuzzy Clustering Technique. in Computational Intelligence, Modelling and Simulation, 2009. CSSim '09. International Conference on.2009, 48-53.10.1109/CSSim.2009.42
Search in Google Scholar
[5] Blake, C.L., D.J. Newman, and C.J. Merz, UCI Repository of machine learning databases, University of California, Irvine, Dept. of Information and Computer Sciences 1998.
Search in Google Scholar
[6] Bouyer, A., H. Ghafarzadeh, and O. Tarkhaneh, An Efficient Hybrid Algorithm using Cuckoo Search and Differential Evolution for Data Clustering. Indian Journal of Science and Technology, 8, 24, 2015.
Search in Google Scholar
[7] Changhe, L. and Y. Shengxiang. A clustering particle swarm optimizer for dynamic optimization. in Evolutionary Computation, 2009. CEC '09. IEEE Congress on.2009, 439-446.
Search in Google Scholar
[8] Chen, C.-Y. and Y. Fun. Particle swarm optimization algorithm and its application to clustering analysis. in Networking, Sensing and Control, 2004 IEEE International Conference on.2004, 789-794 Vol.2.
Search in Google Scholar
[9] Chuang, L.-Y., C.-J. Hsiao, and C.-H. Yang, Chaotic particle swarm optimization for data clustering. Expert Systems with Applications, 38, 12, 2011, 14555-14563.10.1016/j.eswa.2011.05.027
Search in Google Scholar
[10] Dalli, A., Adaptation of the F-measure to cluster based lexicon quality evaluation, in Proceedings of the EACL 2003 Workshop on Evaluation Initiatives in Natural Language Processing: are evaluation methods, metrics and resources reusable? Association for Computational Linguistics: Budapest, Hungary. 2003, 51-56.10.3115/1641396.1641404
Search in Google Scholar
[11] Danesh, M., M. Naghibzadeh, M. Totonchi, M. Danesh, B. Minaei, and H. Shirgahi, Data Clustering Based on an Efficient Hybrid of K-Harmonic Means, PSO and GA, in Transactions on Computational Collective Intelligence IV, N. Nguyen, Editor, Springer Berlin Heidelberg. 2011, 125-140.10.1007/978-3-642-21884-2_2
Search in Google Scholar
[12] Fathi, V. and G.A. Montazer, An improvement in RBF learning algorithm based on PSO for real time applications. Neurocomputing, 111, 0, 2013, 169-176.10.1016/j.neucom.2012.12.024
Search in Google Scholar
[13] Fodeh, S.J., C. Brandt, T.B. Luong, A. Haddad, M. Schultz, T. Murphy, and M. Krauthammer, Complementary ensemble clustering of biomedical data. Journal of Biomedical Informatics, 46, 3, 2013, 436-443.10.1016/j.jbi.2013.02.001400721923454721
Search in Google Scholar
[14] Ghaemi, R., N.B. Sulaiman, H. Ibrahim, and N. Mustapha, A review: accuracy optimization in clustering ensembles using genetic algorithms. Artif. Intell. Rev., 35, 4, 2011, 287-318.10.1007/s10462-010-9195-5
Search in Google Scholar
[15] Hatamlou, A., In search of optimal centroids on data clustering using a binary search algorithm. Pattern Recognition Letters, 33, 13, 2012, 1756-1760.10.1016/j.patrec.2012.06.008
Search in Google Scholar
[16] Hatamlou, A., V. Beiranvand, A. Bouyer, A. Habiboghli, and R. Mostafaeia, Application of modified PSO on clustering, in 5th Postgraduate Annual Research Seminar 2009 (PARS'09): Malaysia. 2009.
Search in Google Scholar
[17] He, Q., A review of clustering algorithms as applied in IR. Univ. Illinois at Urbana-Champaign, Tech. Rep. UIUCLIS-1999/6+ IRG, 1999.
Search in Google Scholar
[18] Hilas, C.S. and P.A. Mastorocostas, An application of supervised and unsupervised learning approaches to telecommunications fraud detection. Knowledge-Based Systems, 21, 7, 2008, 721-726.10.1016/j.knosys.2008.03.026
Search in Google Scholar
[19] Hu, G., S. Zhou, J. Guan, and X. Hu, Towards effective document clustering: A constrained K-means based approach. Information Processing & Management, 44, 4, 2008, 1397-1409.10.1016/j.ipm.2008.03.001
Search in Google Scholar
[20] Jain, A.K., Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 31, 8, 2010, 651-666.10.1016/j.patrec.2009.09.011
Search in Google Scholar
[21] Jain, A.K., M.N. Murty, and P.J. Flynn, Data clustering: a review. ACM Comput. Surv., 31, 3, 1999, 264-323.10.1145/331499.331504
Search in Google Scholar
[22] Kao, Y.-T. and E. Zahara, A hybrid genetic algorithm and particle swarm optimization for multimodal functions. Appl. Soft Comput., 8, 2, 2008, 849-857.10.1016/j.asoc.2007.07.002
Search in Google Scholar
[23] Kao, Y.-T., E. Zahara, and I.W. Kao, A hybridized approach to data clustering. Expert Systems with Applications, 34, 3, 2008, 1754-1762.10.1016/j.eswa.2007.01.028
Search in Google Scholar
[24] Karaboga, D. and C. Ozturk, A novel clustering approach: Artificial Bee Colony (ABC) algorithm. Appl. Soft Comput., 11, 1, 2011, 652-657.10.1016/j.asoc.2009.12.025
Search in Google Scholar
[25] Keller, F., Clustering. Computer University Saarlandes, Tutorial Slides.
Search in Google Scholar
[26] Kennedy, J. and R. Eberhart. Particle swarm optimization. in Neural Networks, 1995. Proceedings., IEEE International Conference on.1995, 1942-1948 vol.4.
Search in Google Scholar
[27] Kiranyaz, S., J. Pulkkinen, and M. Gabbouj, Multi-dimensional particle swarm optimization in dynamic environments. Expert Systems with Applications, 38, 3, 2011, 2212-2223.10.1016/j.eswa.2010.08.009
Search in Google Scholar
[28] Kumar, M. and N.R. Patel, Clustering data with measurement errors. Computational Statistics & Data Analysis, 51, 12, 2007, 6084-6101.10.1016/j.csda.2006.12.012
Search in Google Scholar
[29] Kumar, S. and C.S.P. Rao, Application of ant colony, genetic algorithm and data mining-based techniques for scheduling. Robotics and Computer-Integrated Manufacturing, 25, 6, 2009, 901-908.10.1016/j.rcim.2009.04.015
Search in Google Scholar
[30] Lévy, P. The Lévy Distribution. Available from: http://www.math.uah.edu/stat/special/Levy.html.
Search in Google Scholar
[31] Liu, C.-M., C.-H. Lee, and L.-C. Wang, Distributed clustering algorithms for data-gathering in wireless mobile sensor networks. Journal of Parallel and Distributed Computing, 67, 11, 2007, 1187-1200.10.1016/j.jpdc.2007.06.010
Search in Google Scholar
[32] Maimon, O.Z. and L. Rokach, Data mining and knowledge discovery handbook. Vol. 1. 2005: Springer.10.1007/b107408
Search in Google Scholar
[33] Mangat, V., Survey on Particle Swarm Optimization Based Clustering Analysis, in Swarm and Evolutionary Computation, L. Rutkowski, et al., Editor, Springer Berlin Heidelberg. 2012, 301-309.10.1007/978-3-642-29353-5_35
Search in Google Scholar
[34] Marinakis, Y., M. Marinaki, M. Doumpos, and C. Zopounidis, Ant colony and particle swarm optimization for financial classification problems. Expert Syst. Appl., 36, 7, 2009, 10604-10611.10.1016/j.eswa.2009.02.055
Search in Google Scholar
[35] Nanda, S.J. and G. Panda, Automatic clustering algorithm based on multi-objective Immunized PSO to classify actions of 3D human models. Engineering Applications of Artificial Intelligence, 26, 5–6, 2013, 1429-1441.10.1016/j.engappai.2012.11.008
Search in Google Scholar
[36] Niknam, T. and B. Amiri, An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis. Applied Soft Computing, 10, 1, 2010, 183-197.10.1016/j.asoc.2009.07.001
Search in Google Scholar
[37] Passino, K.M., Biomimicry of bacterial foraging for distributed optimization and control. Control Systems, IEEE, 22, 3, 2002, 52-67.10.1109/MCS.2002.1004010
Search in Google Scholar
[38] Rana, S., S. Jasola, and R. Kumar, A review on particle swarm optimization algorithms and their applications to data clustering. Artificial Intelligence Review, 35, 3, 2011, 211-222.10.1007/s10462-010-9191-9
Search in Google Scholar
[39] Runkler, T.A., Ant colony optimization of clustering models: Research Articles. Int. J. Intell. Syst., 20, 12, 2005, 1233-1251.10.1002/int.20111
Search in Google Scholar
[40] Saatchi, S. and C.C. Hung, Hybridization of the ant colony optimization with the k-means algorithm for clustering, in Proceedings of the 14th Scandinavian conference on Image Analysis Springer-Verlag: Joensuu, Finland. 2005, 511-520.10.1007/11499145_52
Search in Google Scholar
[41] Senthilnath, J., V. Das, S.N. Omkar, and V. Mani, Clustering Using Levy Flight Cuckoo Search, in Proceedings of Seventh International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA 2012), J.C. Bansal, et al., Editor, Springer India. 2013, 65-75.10.1007/978-81-322-1041-2_6
Search in Google Scholar
[42] Servet, M.K., M.S. Kiran, E. ÖZceylan, M. Gündüz, and T. Paksoy, Swarm intelligence approaches to estimate electricity energy demand in Turkey. Know.-Based Syst., 36, 2012, 93-103.10.1016/j.knosys.2012.06.009
Search in Google Scholar
[43] Shengxiang, Y. and L. Changhe, A Clustering Particle Swarm Optimizer for Locating and Tracking Multiple Optima in Dynamic Environments. Evolutionary Computation, IEEE Transactions on, 14, 6, 2010, 959-974.10.1109/TEVC.2010.2046667
Search in Google Scholar
[44] Sung, C. and H. Jin, A tabu-search-based heuristic for clustering. Pattern Recognition, 33, 5, 2000, 849-858.10.1016/S0031-3203(99)00090-4
Search in Google Scholar
[45] Van Der Merwe, D.W. and A.P. Engelbrecht. Data clustering using particle swarm optimization. in Evolutionary Computation, 2003. CEC '03. The 2003 Congress on.2003, 215-220 Vol.1.
Search in Google Scholar
[46] Xin-She, Y. and S. Deb. Cuckoo Search via Levy flights. in Nature & Biologically Inspired Computing, 2009. NaBIC 2009. World Congress on.2009, 210-214.
Search in Google Scholar
[47] Yan, X., Y. Zhu, W. Zou, and L. Wang, A new approach for data clustering using hybrid artificial bee colony algorithm. Neurocomput., 97, 2012, 241-250.10.1016/j.neucom.2012.04.025
Search in Google Scholar
[48] Yang, F., T. Sun, and C. Zhang, An efficient hybrid data clustering method based on K-harmonic means and Particle Swarm Optimization. Expert Syst. Appl., 36, 6, 2009, 9847-9852.10.1016/j.eswa.2009.02.003
Search in Google Scholar
[49] Yang, S., R. Wu, M. Wang, and L. Jiao, Evolutionary clustering based vector quantization and SPIHT coding for image compression. Pattern Recogn. Lett., 31, 13, 2010, 1773-1780.10.1016/j.patrec.2010.04.006
Search in Google Scholar
[50] Yang, X.-S. and S. Deb. Cuckoo search via Lévy flights. in Nature & Biologically Inspired Computing, 2009. NaBIC 2009. World Congress on. IEEE,2009, 210-214.10.1109/NABIC.2009.5393690
Search in Google Scholar
[51] Žalik, K.R., An efficient k′-means clustering algorithm. Pattern Recognition Letters, 29, 9, 2008, 1385-1391.10.1016/j.patrec.2008.02.014
Search in Google Scholar
[52] Zhang, B., M. Hsu, and U. Dayal, K-Harmonic Means -A Spatial Clustering Algorithm with Boosting, in Temporal, Spatial, and Spatio-Temporal Data Mining, J. Roddick and K. Hornsby, Editor, Springer Berlin Heidelberg. 2001, 31-45.10.1007/3-540-45244-3_4
Search in Google Scholar

An Optimized K-Harmonic Means Algorithm Combined with Modified Particle Swarm Optimization and Cuckoo Search Algorithm

Abstract

Paradigm

My account