An optimized k-harmonic means algorithm combined with modified particle swarm optimization and Cuckoo Search algorithm

• Autorzy: Bouyer A.

Identyfikatory

DOI

10.1515/fcds-2016-0006

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

k-means; k-harmonic means clustering; particle swarm optimization (PSO); Lévy flight; Local Minimum

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2016
• Tom: Vol. 41, No. 2
• Strony: 99--121
• Opis fizyczny: Bibliogr. 52 poz., rys. tab.

Twórcy

autor

Bouyer A.

• Faculty of Information Technology and Communications, Azarbaijan Shahid Madani University, Tabriz, Iran

Bibliografia

• [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.
• [2] Abdeyazdan M., Data clustering based on hybrid K-harmonic means and modifier imperialist competitive algorithm. Journal of Supercomputing, 68, 2, 2014, 574-598.
• [3] Anaya A.R. and J.G. Boticario, Application of machine learning techniques to analyze student interactions and improve the collaboration process. Expert Syst. Appl., 38, 2, 2011, 1171-1181.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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] 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.
• [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.
• [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.
• [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.
• [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.
• [15] Hatamlou A., In search of optimal centroids on data clustering using a binary search algorithm. Pattern Recognition Letters, 33, 13, 2012, 1756-1760.
• [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.
• [17] He Q., A review of clustering algorithms as applied in IR. Univ. Illinois at Urbana-Champaign, Tech. Rep. UIUCLIS-1999/6+ IRG, 1999.
• [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.
• [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.
• [20] Jain A.K., Data clustering: 50 years beyond K-means. Pattern Recognition Letters, 31, 8, 2010, 651-666.
• [21] Jain A.K., M.N. Murty and P.J. Flynn, Data clustering: a review. ACM Comput. Surv., 31, 3, 1999, 264-323.
• [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.
• [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.
• [24] Karaboga D. and C. Ozturk, A novel clustering approach: Artificial Bee Colony (ABC) algorithm. Appl. Soft Comput., 11, 1, 2011, 652-657.
• [25] Keller F., Clustering. Computer University Saarlandes, Tutorial Slides.
• [26] Kennedy J. and R. Eberhart, Particle swarm optimization. in Neural Networks, 1995. Proceedings., IEEE International Conference on. 1995, 1942-1948 vol. 4.
• [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.
• [28] Kumar M. and N.R. Patel, Clustering data with measurement errors. Computational Statistics & Data Analysis, 51, 12, 2007, 6084-6101.
• [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.
• [30] Lévy P., The Lévy Distribution. Available from: http://www.math.uah.edu/stat/special/Levy.html.
• [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.
• [32] Maimon O.Z. and L. Rokach, Data mining and knowledge discovery handbook. Vol. 1. 2005: Springer.
• [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.
• [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.
• [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.
• [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.
• [37] Passino K.M., Biomimicry of bacterial foraging for distributed optimization and control. Control Systems, IEEE, 22, 3, 2002, 52-67.
• [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.
• [39] Runkler T.A., Ant colony optimization of clustering models: Research Articles. Int. J. Intell. Syst., 20, 12, 2005, 1233-1251.
• [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.
• [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.
• [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.
• [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.
• [44] Sung C. and H. Jin, A tabu-search-based heuristic for clustering. Pattern Recognition, 33, 5, 2000, 849-858.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [51] Žalik K.R., An efficient k′-means clustering algorithm. Pattern Recognition Letters, 29, 9, 2008, 1385-1391.
• [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.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.