An efficient hybrid PSO polygamous crossover based clustering algorithm
Tóm tắt
Clustering of data into cohesive groups is an open area of research with lots of applications in different domains. Many traditional and metaheuristic algorithms have been proposed in the literature, but the main inherent problem with most of these algorithms is that they can easily get trapped in local optima and can lead to premature convergence. Thus a significant balance is required between exploration and exploitation to find a near optimal solution. This paper attempts to resolve this problem by proposing a real encoded hybrid algorithm (PSOPC) using PSO for global search and polygamous approach for crossover in order to refine the exploration and exploitation strategy. Parameters like inertia weight, crossover probability and alpha values in arithmetic crossover are also tuned dynamically to refine the optimization process. The Proposed hybrid algorithm is simulated on seven real life data sets. It has also been compared with other four standard well known metaheuristic clustering algorithms i.e. Particle Swarm Optimization, Genetic Algorithm, Differential Evolution, Firefly Algorithm and Grey Wolf Optimization. The computational results demonstrate that the PSOPC outperforms other approaches in context of within cluster distance, cluster quality measures and convergence speed to find the near optimal solutions. Simulation results clearly reveal that the proposed algorithm PSOPC is able to generate compact clusters. Various external quality evaluation measurements (like Precision, Sensitivity, Accuracy and G-measure) used for quality evaluation demonstrated that the proposed algorithm is able to perform better clustering than the other compared algorithms.
Tài liệu tham khảo
Hartigan JA (1975) Clustering algorithms. Wiley, Hoboken
Abraham A, Das S, Roy S (2008) Swarm intelligence algorithms for data clustering. In: Maimon O, Rokach L (eds) Soft computing for knowledge discovery and data mining. Springer, Boston, MA, pp 279–313
Shabanzadeh P, Yusof R (2015) An efficient optimization method for solving unsupervised data classification problems. Comput Math Methods Med 2015:802754. https://doi.org/10.1155/2015/802754
Kanungo T, Mount DM, Netanyahu NS, Piatko CD, Silverman R, Wu AY (2002) An efficient k-means clustering algorithm: analysis and implementation. IEEE Trans Pattern Anal Mach Intell 2(7):881–892
Kao I-W, Kao YT, Zaharab E (2008) A hybridized approach to data clustering. Expert Syst Appl 34(3):1754–1762
Bansal JC, Sharma H, Arya KV, Nagar A (2013) Memetic search in artificial bee colony algorithm. Soft Comput 17(10):1911–1928
Prajapati A, Chhabra JK (2018) Many-objective artificial bee colony algorithm for large-scale software module clustering problem. Comput Lang Syst Struct 22(19):6341–6361
Prajapati A, Chhabra JK (2018) TA-ABC: two-archive artificial bee colony for multi-objective software module clustering problem. J Intell Syst 27(4):619–641
Kumar V, Chabbra JK, Kumar D (2017) Grey wolf algorithm based clustering technique. J Intell Syst 26(1):153–168
Prajapati A, Chhabra JK (2018) MaDHS: many objective discrete harmony search to improve existing package design. Comput Intell 35(1):98–123
Prajapati A, Chhabra JK (2017) Harmony search based remodularization for object-oriented software systems. Comput Lang Syst Struct 47(2):153–169
Blake CL, Merz CJ (1998) UCI repository of machine learning databases. University of California, Oakland
Xu R, Wunschu DC II (2009) Clustering. Wiley, Hoboken, pp 92–95
Amiri B, Hossain L, Mosavi SE (2010) Application of harmony search algorithm on clustering. In: Proceedings of the world congress on engineering and computer science 2010, vol I, WCECS 2010, October 20–22, 2010, San Francisco, USA
Shokhri SZ, Alsultan K (1991) A simulated annealing algorithm for the clustering problem. Pattern Recognit 24(10):1003–1008
Maulik U, Bandyopadhyay S (2000) Genetic algorithm based clustering technique. Pattern Recognit 33:1455–1465
Krishna K, Murty MN (1999) Genetic K-mean algorithm. IEEE Trans Syst Man Cybern B Cybern 29(3):433–439
Sung CS, Jin HW (2000) A tabu-search-based heuristic for clustering. Pattern Recognit 33(5):849–858
Cura T (2012) A particle swarm optimization approach to clustering. Expert Syst Appl 39:1582–1588
Chang DX, Zhang XD, Zheng CW (2009) A genetic algorithm with gene rearrangement for K mean clustering. Pattern Recognit 42(7):1210–1222
Shelokar PS, Jayaraman VK, Kulkarni BD (2004) An ant colony approach for clustering. Anal Chim Acta 509(2):187–195
Nehsat M, Yardi SF, Yazdani D, Sargolzaei M (2012) A new cooperative algorithm based on PSO and k-means for data clustering. J Comput Sci 8(2):188–194
Karaboga D, Basturk B (2008) On the performance of artificial bee colony (ABC) algorithm. Appl Soft Comput 8(1):687–697
Fathian M, Amiri B, Maroosi A (2007) Application of honey-bee mating optimization algorithm on clustering. Appl Math Comput 190(2):1502–1513
Kwedlo W (2011) A clustering method combining differential evolution with k mean algorithm. Pattern Recognit Lett 32(12):1613–1621
Wahid F, Ghazali R (2018) Hybrid of firefly algorithm and pattern search for solving optimization problems. Evolut Intell 12:1–10
Senthilnath J, Omkar SN (2011) Clustering using firefly algorithm: performance study. Swarm Evolut Comput 1(3):164–171
Hassanzadeh T, Meybodi MR (2012) A new hybrid approach for data clustering using firefly algorithm and k means. In: The 16th CSI international symposium on artificial intelligence and signal processing, Iran, 2012
Singh G, Deep K (2016) A new membrane algorithm using the rules of Particle Swarm Optimization incorporated within the framework of cell-like P-systems to solve Sudoku. Appl Soft Comput 45:27–39
Peng H, Luo X, Gao Z, Wang J, Pei Z (2015) A novel clustering algorithm inspired by membrane computing. Sci World J 2015:929471. https://doi.org/10.1155/2015/929471
Geem ZW, Kim JH, Loganathan GV (2001) A new heuristic optimization algorithm: harmony search. Simulation 76:1552–1557
Alia OM, Al-Betar MA, Mandava R, Khader AT (2011) Data clustering using harmony search algorithm. In: Panigrahi BK, Suganthan PN, Das S, Satapathy SC (eds) SEMCCO’11 proceedings of the second international conference on swarm, evolutionary, and memetic computing, vol 7077. Springer, Berlin, Heidelberg, pp 79–88
Holland JH (1992) Adaptation in natural and artificial systems. MIT Press, Cambridge
Goldgerg D (1989) Genetic algorithm in search, optimization and machine learning. Addison Wesley, Boston
Rathee A, Chhabra JK (2019) Reusability in multimedia software using structural and lexical dependencies. Multimed Tools Appl. https://doi.org/10.1007/s11042-019-7382-1
Eberhart R, Kennedy J (1995) A new optimizer using particle swarm optimization. In: Sixth international symposium on micro machine and human science
Deep K, Bansal JC (2009) Hybridization of particle swarm optimization with quadratic approximation. Opsearch 46(1):3–24
Prajapati A, Chhabra JK (2018) A particle swarm optimization-based heuristic for software module. Arab J Sci Eng 43:7083–7094
Paxton JR (2005) Male mating behaviour and mating systems of bees: an overview. Apidologie 36(2):145–156
Kumar R, Jyotishree (2012) Novel approach to polygamous selection in genetic algorithms. In: International conference on information systems design and intelligent applications, Vishakhapatnam
Prajapati A, Chhabra JK (2017) Improving modular structure of software system using structural and lexical dependency. Inf Sotw Technol 82:92–120
De Jong KA, Spears WM, Gordon DF (1989) Using genetic algorithms to solve NP complete problems. In: Proceedings of the third international conference on genetic algorithm, Morgan Kaufman, Los Altos
Saremi S, Mirjalil SZ, Mirjalili SM (2015) Evolutionary population dynamics and grey wolf optimizer. Neural Comput Appl 26(5):1257–1263
Buckland M, Gay F (1994) The relationship between recall and precision. J Am Soc Inf Sci 45(1):12–19
Tharwat A (2018) Classification assessment methods. Appl Comput Inf. https://doi.org/10.1016/j.aci.2018.08.003
Figueiredo D (2013) When is statistical significance not significant? Braz Polit Sci Rev 7:1–26