Data Clustering Using Multi-objective Differential Evolution Algorithms

• Autorzy: Suresh K. , Kundu D. , Ghosh S. , Das S.
• Języki publikacji: EN

Abstrakty

EN

The article considers the task of fuzzy clustering in a multi-objective optimization (MO) framework. It compares the relative performance of four recently developedmulti-objective variants of Differential Evolution (DE) on over the fuzzy clustering problem, where two conflicting fuzzy validity indices are simultaneously optimized. The resultant Pareto optimal set of solutions from each algorithm consists of a number of non-dominated solutions, from which the user can choose the most promising ones according to the problem specifications. A real-coded representation for the candidates is used for DE. A comparative study of four DE variants with two most well-known MO clustering techniques, namely the NSGA II (Non Dominated Sorting GA) and MOCK (Multi-Objective Clustering with an unknown number of clusters K) is also undertaken. Experimental results reported for six artificial and four real life datasets (including a microarray dataset of budding yeast) of varying range of complexities indicates that DE can serve as a promising algorithm for devising MO clustering techniques.

Słowa kluczowe

EN

differential evolution; multi-objective optimization; fuzzy clustering; micro-array data clustering

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 97, nr 4
• Strony: 381--403
• Opis fizyczny: . Bibliogr. 36 poz., tab., wykr.

Twórcy

autor

Suresh K.

autor

Kundu D.

autor

Ghosh S.

autor

Das S.

• Machine Intelligence Research Labs (MIR Labs), Scientific Network for Innovation and Research Excellence, USA.,

Bibliografia

• [1] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multi objective genetic algorithm: NSGA-II", IEEE Transactions on Evolutionary Computation, vol. 6, no. 2, 2002.
• [2] J. D. Knowles and D.W. Corne, "Approximating the nondominated front using the Pareto archived evolution strategy", Evolutionary Computation, vol. 8, no. 2, pp. 149-172, 2000.
• [3] R. Storn, K. V. Price, and J. Lampinen, Differential Evolution - A Practical Approach to Global Optimization, Springer, Berlin, 2005.
• [4] K. Deb, Multi-Objective Optimization using Evolutionary Algorithms, John Wiley & Sons, 2001.
• [5] C. A. Coello Coello, G. B. Lamont, and D. A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems, Springer, 2007.
• [6] A. Abraham, L. C. Jain and R. Goldberg (Eds.), Evolutionary Multiobjective Optimization: Theoretical Advances and Applications, Springer Verlag, London, 2005.
• [7] H. A. Abbass and R. Sarker, "The Pareto differential evolution algorithm", International Journal on Artificial Intelligence Tools, 11(4):531-552, 2002.
• [8] F. Xue, A. C. Sanderson, and R. J. Graves, "Pareto-basedmulti-objective differential evolution", in Proceedings of the 2003 Congress on Evolutionary Computation (CEC'2003), volume 2, pages 862-869, Canberra, Australia, 2003, IEEE Press.
• [9] T. Robic and B. Filipic, "DEMO: Differential Evolution for Multiobjective Optimization", In C. A. Coello Coello, A. H. Aguirre, and E. Zitzler, editors, Evolutionary Multi-Criterion Optimization, Third International Conference, EMO 2005, pages 520-533, Guanajuato, Mexico, 2005, Springer. Lecture Notes in Computer Science Vol. 3410, 2005.
• [10] A.W. Iorio and X. Li, "Solving rotated multi-objective optimization problems using differential evolution", in AI 2004: Advances in Artificial Intelligence, Proceedings, pages 861-872, Springer- Verlag, Lecture Notes in Artificial Intelligence Vol. 3339, 2004.
• [11] X. Xie and G. Beni, "Validity measure for fuzzy clustering", IEEE Trans. Pattern Anal. Machine Learning, Vol. 3, pp. 841-846, (1991).
• [12] J. C. Bezdek, "Cluster validity with fuzzy sets", Journal of Cybernetics, (3) 58-72, (1974).
• [13] R. Tibshirani, G.Walther, and T. Hastie, "Estimating the number of clusters in a dataset via the Gap statistic," J. Royal Statist. Soc.: SeriesB (Statistical Methodology), vol. 63, no. 2, pp. 411-423, 2001.
• [14] J. Handl and J. Knowles, "An evolutionary approach to multiobjective clustering", IEEE Transactions on Evolutionary Computation, 11(1):56-76, 2007.
• [15] S. Bandyopadhyay, U. Maulik, and A. Mukhopadhyay,Multiobjective genetic clustering for pixel classification in remote sensing imagery, IEEE Transactions Geoscience and Remote Sensing, 2006.
• [16] S. Chu et al. "The transcriptional program of sporulation in budding yeast", Science, 282, 699-705, 1998.
• [17] Kalyanmoy Deb, Samir Agrawal, Amrit Pratab, and T. Meyarivan, "A Fast Elitist Non-Dominated Sorting Genetic AlgorithmforMulti-ObjectiveOptimization: NSGA-II", inM. Schoenauer,K. Deb, G. Rudolph, X. Yao, E. Lutton, J. Julian Merelo, and H.-P. Schwefel, editors, Proceedings of the Parallel Problem Solving from Nature VI Conference, pages 849-858, Paris, France, 2000. Springer. Lecture Notes in Computer Science No. 1917.
• [18] E. Zitzler and L. Thiele, "Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach", IEEE Transactions on Evolutionary Computation, 3(4):257-271, November 1999.
• [19] E. Zitzler and L. Thiele, "Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach", IEEE Transactions on Evolutionary Computation, 3(4):257-271, November 1999.
• [20] H. A. Abbass, "The self-adaptive Pareto differential evolution algorithm", In Congress on Evolutionary Computation (CEC'2002), volume 1, pages 831-836, Piscataway, New Jersey, IEEE Service Center, 2002.
• [21] I. Das, "On characterizing the "knee' of the Pareto curve based on normal-boundary intersection," Structural Optim., vol. 18, no. 2-3, pp. 107-115, 1999.
• [22] J. Branke, K. Deb, H. Dierolf, and M. Osswald, "Finding knees in multi-objective optimization," in Proc. 8th Int. Conf. Parallel Problem Solving From Nature, pp. 722-731, 2004.
• [23] K. Deb, "Multi-objective evolutionary algorithms: Introducing bias among Pareto-optimal solutions," in Advances in Evolutionary Computing: Theory and Applications. London, U.K.: Springer-Verlag, pp. 263-292, 2003.
• [24] C. A. Mattson, A. A. Mullur, and A. Messac, "Smart Pareto filter: Obtaining a minimal representation of multiobjective design space," Eng. Optim., vol. 36, no. 6, pp. 721-740, 2004.
• [25] R. Tibshirani, G.Walther, and T. Hastie, "Estimating the number of clusters in a dataset via the Gap statistic," J. Royal Statist. Soc.: SeriesB (Statistical Methodology), vol. 63, no. 2, pp. 411-423, 2001.
• [26] W. M. Rand, "Objective criteria for the evaluation of clustering methods", Journal of the American Statistical Association, 66, 846-850, 1971.
• [27] P. J. Rousseeuw, "Silhouettes: A graphical aid to the interpretation and validation of cluster analysis," J.Comput. Appl. Math., vol. 20, no. 1, pp. 53-65, 1987.
• [28] L. Hubert and P. Arabie, "Comparing partitions", Journal of Classification, 193-218, 1985.
• [29] S. Theodoridis and K. Koutroumbas, Pattern Recognition, Second Edition, Elsevier Academic Press, 2003.
• [30] The Gene Ontology Consortium (2000): "Gene ontology: tool for the unification of biology", Nat. Genet., 25, 25-29.
• [31] D. A. Keim and H.-P. Kriegel, "Visualization techniques for mining large databases: a comparison", IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.923-938, December 1996.
• [32] M.B. Eisen, P. T. Spellman, P. O. Brown, and D. Botstein, "Cluster analysis and display of genome-wide expression patterns", Proc. Natl Acad. Sci. USA, 95, 14863-14868, 1998.
• [33] F. Al-Shahrour, R. Dłaz-Uriarte, and J. Dopazo, "FatiGO: a web tool for finding significant associations of Gene Ontology terms with groups of genes", Bioinformatics, 20, 578-580, 2004.
• [34] http:/www.ics.uci.edu/~mlearn/MLrepository.html
• [35] http:/cmgm.stanford.edu/pbrown/sporulation
• [36] http://dbkgroup.org/handl/mock/