A novel grammar-based genetic programming approach to clustering

ABSTRACT

Most of the classical methods for clustering analysis require the user setting of number of clusters. To surmount this problem, in this paper a grammar-based Genetic Programming approach to automatic data clustering is presented. An innovative clustering process is conceived strictly linked to a novel cluster representation which provides intelligible information on patterns. The efficacy of the implemented partitioning system is estimated on a medical domain by exploiting expressly defined evaluation indices. Furthermore, a comparison with other clustering tools is performed.

REFERENCES

• 1: Charu C. Aggarwal , Philip S. Yu, Finding generalized projected clusters in high dimensional spaces, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.70-81, May 15-18, 2000, Dallas, Texas, United States
• 2: Babu, G. P. and Marty, M. N. Clustering with evolutionary strategies. Pattern Recognition, 27, 2 (1994), 321--329.
• 3: Dempster, A. P., Laird, N. M., and Rubin, D. B. Maximum Likelihood from Incomplete Data via the EM algorithm. Journal of the Royal Statistical Society, Series B., 39, 1 (1977), 1--38.
• 4: Fraley, C. and Raftery, A. How many clusters? Which clustering method? Answers via model-based cluster analysis. The Computer Journal, 41, 8 (1998), 578--588.
• 5: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, CURE: an efficient clustering algorithm for large databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.73-84, June 01-04, 1998, Seattle, Washington, United States
• 6: Hall, L. O., Ozyurt, B., and Bezdek, J. C. Clustering with a genetically optimized approach. IEEE Trans. on Evolutionary Computation, 3, 2 (1999), 103--112.
• 7: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 8: David J. Hand , Padhraic Smyth , Heikki Mannila, Principles of data mining, MIT Press, Cambridge, MA, 2001
• 9: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 10: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 11: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 12: Lee, C. Y. and Antonsson, E. K. Dynamic partitional clustering using evolutionary strategies. In Proc. of the 3rd Asia-Pacific Conference on Simulated Evolution and Learning. IEEE Press, Nagoya, Japan, 2000.
• 13: Man Leung Wong , Kwong Sak Leung, Data Mining Using Grammar-Based Genetic Programming and Applications, Kluwer Academic Publishers, Norwell, MA, 2000
• 14: Murphy, P. M. and Aha, D. W. UCI Repository of machine learning databases. University of California, Dept. of Information and Computer Science. Available at www.ics.uci.edu/~mlearn/MLRepository.html
• 15: Sarafis, I., Zalzala, A. M. S., and Trinder, P. W. A genetic rule-based data clustering toolkit. In Proc. of the IEEE Congress on Evolutionary Computation, 2002, 1238--1243.
• 16: Weka3.4: Data mining software in Java. Available at www.cs.waikato.ac.nz/~ml/weka/
• 17: Yip, A. M. A scale dependent data clustering model by direct maximization of homogeneity and separation. In Proc. Mathematical challenges in scientific data mining IPAM. 14-18 January 2002.
• 18: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Experimentation

Keywords:
data clustering, genetic programming