A Dynamic Genetic Algorithm for Clustering Problems

Abstract:

Due to many of the clustering algorithms based on GAs suffer from degeneracy and are easy to fall in local optima, a novel dynamic genetic algorithm for clustering problems (DGA) is proposed. The algorithm adopted the variable length coding to represent individuals and processed the parallel crossover operation in the subpopulation with individuals of the same length, which allows the DGA algorithm clustering to explore the search space more effectively and can automatically obtain the proper number of clusters and the proper partition from a given data set; the algorithm used the dynamic crossover probability and adaptive mutation probability, which prevented the dynamic clustering algorithm from getting stuck at a local optimal solution. The clustering results in the experiments on three artificial data sets and two real-life data sets show that the DGA algorithm derives better performance and higher accuracy on clustering problems.

• Periodical: Applied Mechanics and Materials (Volumes 411-414)
• Pages: 1884-1893
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.411-414.1884
• Online since: September 2013
• Authors: Yong Chun Cao, Ya Bin Shao, Shuang Liang Tian, Zheng Qi Cai
• Keywords: Adaptive Mutation, Clustering Problems, Dynamic Crossover, Genetic Algorithm (GA)

References

[1] Anil K. Jain, Data clustering: 50years beyond k-means: Pattern Recognition Letters Vol. 31 (2010), p.651–666.

DOI: 10.1016/j.patrec.2009.09.011

[2] J. Handl, J. Knowles, D. B. Kell, Computational cluster validation in post-genomic data analysis: Bioinformatics Vol. 21 (2005), p.3201–3212.

DOI: 10.1093/bioinformatics/bti517

[3] M. Ester, H. P. Kriegel, J. Sander, Xiaowei Xu, A density-based algorithm for discovering clusters in large spatial data bases with noise: Proceedings of the 2nd international conference on knowledge discovery and data mining 1996, p.226–231.

DOI: 10.1109/icde.1998.655795

[4] Sara C. Madeira and A. L. Oliveira, Biclustering algorithms for biological data analysis: a survey: IEEE Transactions on Computational Bioinformatics Vol. 1 (2004), p.24–45.

DOI: 10.1109/tcbb.2004.2

[5] S. Dehuri, A. Ghosh, R. Mall, Genetic algorithms for multi-criterion classification and clustering in data mining: International Journal of Computing and Information Systems Vol. 4 (2006), p.143–154.

[6] Eduardo Raul Hruschka, Ricardo J.G.B. Campello and Alex. A. Freitas et al, A survey of evolutionary algorithms for clustering: IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews Vol. 39 (2009), p.133–155.

DOI: 10.1109/tsmcc.2008.2007252

[7] Dongxia Chang, Xianda Zhang, Changwen Zheng, A genetic algorithm with gene rearrangement for K-means clustering: Pattern Recognition Vol. 42 (2009), p.1210 – 1222.

DOI: 10.1016/j.patcog.2008.11.006

[8] Lianjiang Zhu, Bingxian Ma and Xuequan Zhao, Clustering validity analysis based on silhouette coefficient: Journal of Computer Applications Vol. 30 (2010), pp.139-141.

[9] N. R. Pal and J. C. Bezdek, On cluster validity for the fuzzy c-means model: IEEE Transactions on Fuzzy Systems Vol. 3 (1995), p.370–379.

DOI: 10.1109/91.413225

[10] T. James, M. Vroblefski, Q. Nottingham, A hybrid grouping genetic algorithm for the registration area planning problem: Computer Communications Vol. 30 (2007), p.2180–2190.

DOI: 10.1016/j.comcom.2007.04.018

[11] S. Bandyopdhyay and U. Maulik, An evolutionary technique based on K-means algorithm for optimal clustering in RN: Information Sciences Vol. 146 (2002), p.221–237.

DOI: 10.1016/s0020-0255(02)00208-6

[12] Information on http: /archive. ics. uci. edu/ml.