Abstract
Combinatorial Particle Swarm Optimization (CPSO) is a relatively recent technique for solving combinatorial optimization problems. CPSO has been used in different applications, e.g., partitional clustering and project scheduling problems, and it has shown a very good performance. In partitional clustering problem, CPSO needs to determine the number of clusters in advance. However, in many clustering problems, the correct number of clusters is unknown, and it is usually impossible to estimate. In this paper, an improved version, called CPSOII, is proposed as a dynamic clustering algorithm, which automatically finds the best number of clusters and simultaneously categorizes data objects. CPSOII uses a renumbering procedure as a preprocessing step and several extended PSO operators to increase population diversity and remove redundant particles. Using the renumbering procedure increases the diversity of population, speed of convergence and quality of solutions. For performance evaluation, we have examined CPSOII using both artificial and real data. Experimental results show that CPSOII is very effective, robust and can solve clustering problems successfully with both known and unknown number of clusters. Comparing the obtained results from CPSOII with CPSO and other clustering techniques such as KCPSO, CGA and K-means reveals that CPSOII yields promising results. For example, it improves 9.26 % of the value of DBI criterion for Hepato data set.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Pedrycz W (2005) Knowledge-based clustering. Wiley, New York. doi:10.1002/0471708607.fmatter
Frigui H, Krishnapuram R (1999) A robust competitive clustering algorithm with applications in computer vision. IEEE Trans Pattern Anal Mach Intell 21(5):450–465
Xu R, Wunsch DC (2010) Clustering algorithms in biomedical research: a review. IEEE Rev Biomed Eng 3(1):120–154
Niknam T, Amiri B, Olamaei J, Arefi A (2009) An efficient hybrid evolutionary optimization algorithm based on PSO and SA for clustering. J Zhejiang Univ Sci 10(4):512–519. doi:10.1631/jzus.A0820196
Papadimitriou CH, Steiglitz K (1998) Combinatorial optimization: algorithms and complexity. Dover, New York
Clerc M (2006) Particle swarm optimization. Wiley-ISTE, New York
Jarboui B, Cheikh M, Siarry P, Rebai A (2007) Combinatorial particle swarm optimization (CPSO) for partitional clustering problem. Appl Math Comput 192(2):337–345. doi:10.1016/j.amc.2007.03.010
Yucheng K, Szu-Yuan, L (2009) Combining K-means and particle swarm optimization for dynamic data clustering problems. In: IEEE international conference on intelligent computing and intelligent systems (ICIS), 20–22 Nov. 2009, pp 757–761
Hruschka ER, Campello RJGB, Freitas AA, Carvalho ACPLF (2009) A survey of evolutionary algorithms for clustering. IEEE Trans Syst Man Cybern, Part C, Appl Rev 39(2):133–155
Omran M, Salman A, Engelbrecht (2005) A dynamic clustering using particle swarm optimization with application in unsupervised image classification. In: 5th world enformatika conference (ICCI 2005), Prague, Czech Republic, Citeseer, pp 199–204
Shin K, Jeong Y-S, Jeong M (2012) A two-leveled symbiotic evolutionary algorithm for clustering problems. Appl Intell 36(4):788–799. doi:10.1007/s10489-011-0295-y
Hruschka ER, Campello RJGB, de Castro LN (2006) Evolving clusters in gene-expression data. Inf Sci 176(13):1898–1927. doi:10.1016/j.ins.2005.07.015
Hruschka ER, Ebecken NF (2003) A genetic algorithm for cluster analysis. Intell Data Anal 7(1):15–25
Ma PCH, Chan KCC, Yao X, Chiu DKY (2006) An evolutionary clustering algorithm for gene expression microarray data analysis. IEEE Trans Evol Comput 10(3):296–314
Özyer T, Zhang M, Alhajj R (2011) Integrating multi-objective genetic algorithm based clustering and data partitioning for skyline computation. Appl Intell 35(1):110–122. doi:10.1007/s10489-009-0206-7
Özyer T, Alhajj R (2009) Parallel clustering of high dimensional data by integrating multi-objective genetic algorithm with divide and conquer. Appl Intell 31(3):318–331. doi:10.1007/s10489-008-0129-8
Karthi R, Arumugam S, Rameshkumar K (2008) Comparative evaluation of particle swarm optimization algorithms for data clustering using real world data sets. Int J Comput Sci Netw Secur 8(1):203–212
Bandyopadhyay S, Maulik U (2002) Genetic clustering for automatic evolution of clusters and application to image classification. Pattern Recognit 35(6):1197–1208. doi:10.1016/s0031-3203(01)00108-x
Liu Y, Wu X, Shen Y (2011) Automatic clustering using genetic algorithms. Appl Math Comput 218(4):1267–1279. doi:10.1016/j.amc.2011.06.007
Karthi R, Arumugam S, Kumar K (2009) Discrete particle swarm optimization algorithm for data clustering. In: Nature inspired cooperative strategies for optimization (NICSO), pp 75–88
Latiff NM A, Tsimenidis CC, Sharif BS, Ladha C (2008) Dynamic clustering using binary multi-objective particle swarm optimization for wireless sensor networks. In: IEEE 19th international symposium on personal, indoor and mobile radio communications (PIMRC), 15–18 Sept. 2008, pp 1–5
Paoli A, Melgani F, Pasolli E (2009) Clustering of hyperspectral images based on multiobjective particle swarm optimization. IEEE Trans Geosci Remote Sens 47(12):4175–4188
Niknam T, Amiri B (2010) An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis. Appl Soft Comput 10(1):183–197. doi:10.1016/j.asoc.2009.07.001
Supratid S, Kim H (2009) Modified fuzzy ants clustering approach. Appl Intell 31(2):122–134. doi:10.1007/s10489-008-0117-z
Falkenauer E (1998) Genetic algorithms and grouping problems. Wiley, New York
Kennedy J, Eberhart, R (1995) Particle swarm optimization. In: IEEE international conference on neural networks. Nov/Dec, 1995, pp 1942–1948
Kao YT, Zahara E, Kao IW (2008) A hybridized approach to data clustering. Expert Syst Appl 34(3):1754–1762. doi:10.1016/j.eswa.2007.01.028
Premalatha K, Natarajan A (2009) A new approach for data clustering based on PSO with local search. Comput Inf Sci 1(4):139–145
Yang S, Li Y, Hu X, Pan R (2006) Optimization study on k-value of K-means algorithm. Syst Eng-Theory Pract, Inst China Syst Eng, Beijing 26(2):97–101
Parsopoulos KE, Vrahatis MN (2010) Particle swarm optimization and intelligence: advances and applications. Information Science Reference-Imprint of IGI Publishing
Choi S, Cha S, Tappert CC (2010) A survey of binary similarity and distance measures. Int J Syst Cybern Inform 8(1):43–48
Calinski T, Harabasz J (1974) A dendrite method for cluster analysis. Commun Stat 3(1):1–27
Davies DL, Bouldin DW (1979) A cluster separation measure. IEEE Trans Pattern Anal Mach Intell 1(2):224–227
Bandyopadhyay S, Maulik U (2001) Nonparametric genetic clustering: comparison of validity indices. IEEE Trans Syst Man Cybern, Part C, Appl Rev 31(1):120–125
Bandyopadhyay S Artificial data sets for data mining, available in http://www.isical.ac.in/~sanghami/data.html
UCI Repository of Machine Learning Databases retrieved from the World Wide Web: http://www.ics.uci.edu/~mlearn/MLRepository.html
Shi C, Yuhui S (2011) Diversity control in particle swarm optimization, Paper presented at the IEEE Symposium on Swarm Intelligence (SIS), 11–15 April 2011
Norouzzadeh M, Ahmadzadeh M, Palhang M (2011) LADPSO: using fuzzy logic to conduct PSO algorithm. Appl Intell 37(2):290–304
Zhang W, Liu Y, Clerc M (2003) An adaptive PSO algorithm for reactive power optimization. In: 6th international conference on advances in power control, operation and management, Hong Kong, pp 302–307
García-Villoria A, Pastor R (2009) Introducing dynamic diversity into a discrete particle swarm optimization. Comput Oper Res 36(3):951–966. doi:10.1016/j.cor.2007.12.001
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Masoud, H., Jalili, S. & Hasheminejad, S.M.H. Dynamic clustering using combinatorial particle swarm optimization. Appl Intell 38, 289–314 (2013). https://doi.org/10.1007/s10489-012-0373-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-012-0373-9