An improved data clustering algorithm using NSGA-II

M.G.Pagale ¹ , R.S.Hanchate ²

Section:Research Paper, Product Type: Isroset-Journal
Vol.5 , Issue.7 , pp.1-7, Jul-2019

Online published on Jul 30, 2019

Copyright © M.G.Pagale, R.S.Hanchate . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

Abstract :
In Data clustering, there are various Multiobjective clustering techniques evolved which can automatically partition the data into appropriate no of clusters. For achieving multiple objective functions simultaneously Multiobjective optimization technique is used. Three objective functions such as compactness, connectedness and symmetry of the cluster are optimized simultaneously using NSGA-II. The compactness of the cluster is based on Euclidean distance, a point symmetry based distance used to measure the symmetry of the cluster and Connectedness [1] of the cluster is measured by using relative neighborhood graph concept. Sub cluster are merged appropriately to form variable no of global cluster for objective function evaluation. In this method data is partitioned using k-means clustering algorithm and three objective functions such as compactness, symmetry and connectedness of cluster is optimized by using NSGA-II algorithm. In order to get appropriate no of cluster and accurate partitioning Two-Stage genetic algorithm is applied to these three objective functions.

Key-Words / Index Term :
Euclidean distance,Genetic Algorithm,Multiobjective optimization (MOO),Relative neighborhood grap, Symmetry

References :
[1] Sriparna Sahaa, Sanghamitra Bandyopadhyayb, “A generalized automatic clustering algorithm in a multiobjective framework”,Department of Computer Science and Engineering, Indian Institute of Technology Patna, India, Applied Soft Computing 13 (2013) 89–108
[2] Deb, K., S. Agrawal, Amrit Pratap and T. Meyarivan (2000), “A fast elitist non – dominated sorting genetic algorithm for multi-objective optimization: NSGA II”. In M. S. et al. (Ed), Parallel Problem Solving From Nature – PPSN VI, Berlin, 849 –858. Springer.
[3] Hong He,Yonghong Tan,” A two-stage genetic algorithm for automatic clustering ”, International Journal of Advanced Research in Computer Science and Software Engineering, Volume 3, Issue 6, June 2013,pp-376-380
[4] S. Bandyopadhyay, S. Saha, “A point symmetry based clustering technique for automatic evolution of clusters”, IEEE Transactions on Knowledge and Data
[5] Xue, F.; Sanderson, A.C.; Graves, R. J. “Pareto-based multi-objective differential evolution”. In Proceedings of the 2003 Congress on Evolutionary Computation (CEC’2003), Canberra, Australia, 2003; Volume 2, pp. 862-869.
[6] Knowles, J. D. and D. W. Corne (1999), “The Pareto archived evolution strategy: A new baseline algorithm for Pareto multiobjective optimization”. In Congress on Evolutionary Computation (CEC 99), Volume 1, Piscataway , NJ,98 – 105. IEEE Press.
[7] H.C. Chou, M.C. Su, E. Lai, “A new cluster validity measure and its application to image compression, Pattern Analysis and Applications” 7 (July) (2004) 205–220.
[8] S. Bandyopadhyay, U. Maulik, “Nonparametric genetic clustering: comparison of validity indices”, IEEE Transactions On Systems, Man and Cybernetics, Part C 31 (1) (2001) 120–125.
[9] U. Maulik, S. Bandyopadhyay, “Performance evaluation of some clustering algorithms and validity indices”, IEEE Transactions on Pattern Analysis and Machine Intelligence 24 (12) (2002) 1650–1654.
[10] Zitzler, E. and Thiele, L.(1999). “An evolutionary algorithm for multiobjective optimization: The strength Pareto approach”. Technical report 43, Computer engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich.
[11] Zitzler, E., Laumanns, M. and Thiele, L. (2001). “SPEA 2: Improving the Strength Pareto Evolutionary algorithm”. Technical report 103, Computer engineering and Networks Laboratory (TIK), Swiss Federal Institute of Technology (ETH) Zurich.
[12] H.C. Chou, M.C. Su, E. Lai, “A new cluster validity measure and its application to image compression, Pattern Analysis and Applications” 7 (July) (2004) 205–220.
[13] W. Wang, Y. Zhang, “On fuzzy cluster validity indices”, Fuzzy Sets and Systems 158 (October (19)) (2007) 2095–2117.
[14] P.B. Helena Brás Silva, J.P. da Costa,”A partitional clustering algorithm validated by a clustering tendency index based on graph theory”, Pattern Recognition 39 (May (5)) (2006) 776–788.
[15] M. Kim, R. Ramakrishna, “New indices for cluster validity assessment”, Pattern Recognition Letters 26 (November (15)) (2005) 2353–2363.
[16] G.T. Toussaint, “The relative neighborhood graph of a finite planar set”, PatternRecognition89912(1980)261–268.