COOLCAT: an entropy-based algorithm for categorical clustering

ABSTRACT

In this paper we explore the connection between clustering categorical data and entropy: clusters of similar poi lower entropy than those of dissimilar ones. We use this connection to design an incremental heuristic algorithm, COOLCAT, which is capable of efficiently clustering large data sets of records with categorical attributes, and data streams. In contrast with other categorical clustering algorithms published in the past, COOLCAT's clustering results are very stable for different sample sizes and parameter settings. Also, the criteria for clustering is a very intuitive one, since it is deeply rooted on the well-known notion of entropy. Most importantly, COOLCAT is well equipped to deal with clustering of data streams(continuously arriving streams of data point) since it is an incremental algorithm capable of clustering new points without having to look at every point that has been clustered so far. We demonstrate the efficiency and scalability of COOLCAT by a series of experiments on real and synthetic data sets.

REFERENCES

• 1: M.S. Aldenderfer and R.K. Blashfield. Cluster Analysis Sage Publications,(Sage University Paper series on Quantitative Applications in the Social Sciences, No. 44), 1984.
• 2: Daniel Barbará, Requirements for clustering data streams, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002 [doi>10.1145/507515.507519]
• 3: Daniel Barbará , Ping Chen, Using the fractal dimension to cluster datasets, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.260-264, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347145]
• 4: R.B. Calinski and J. Harabasz.A dendrite method for cluster analysis. Communications in Statistics pages 1--27,1974.
• 5: Peter Cheeseman , John Stutz, Bayesian classification (AutoClass): theory and results, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 6: Chun-Hung Cheng , Ada Waichee Fu , Yi Zhang, Entropy-based subspace clustering for mining numerical data, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.84-93, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312199]
• 7: H.Chernoff A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations. Annals of Mathematical Statistics pages 493--509, 1952.
• 8: DataGen. Data Generator: Perfect data for an imperfect world. http://www.datasetgenerator.com/.
• 9: R. C. Dubes and A.K. Jain. Validity studies in clustering methodologies.Pattern Recognition pages 235--254, 1979.
• 10: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 11: M. Ester, H.P. Kriegel, and X. Wu. A density-based algorithm for discovering clusters in large spatial database with noise. In Proceedings of the International Conference on Knowledge Discovery and Data Mining, Portland, Oregon August 1996.
• 12: Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, CACTUS—clustering categorical data using summaries, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.73-83, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312201]
• 13: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 14: David Gibson , Jon M. Kleinberg , Prabhakar Raghavan, Clustering Categorical Data: An Approach Based on Dynamical Systems, Proceedings of the 24rd International Conference on Very Large Data Bases, p.311-322, August 24-27, 1998
• 15: A. Gluck and J. Corter. Information, uncertainty, and the utility of categories. In Proceedings of the Seventh Annual Conference of the Cognitive Science Society 1985.
• 16: Erhan Gokcay , Jose C. Principe, Information Theoretic Clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.2, p.158-171, February 2002 [doi>10.1109/34.982897]
• 17: 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
• 18: ROCK: A Robust Clustering Algorithm for Categorical Attributes, Proceedings of the 15th International Conference on Data Engineering, p.512, March 23-26, 1999
• 19: E.H. Han, G. Karypis, V.Kumar,and B. Mobasher. Clustering based on association rule hypergraphs. In Proceedings of the SIGMOD Workshop on Research Issues on Data Mining and Knowledge Discovery June 1997.
• 20: S. Hettich(librarian). UCI KDD Archive. http://kdd.ics.uci.edu/.
• 21: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 22: G.J McLachlan and K.E.Basford.Mixture Models Marcel Dekker,New York,1988.
• 23: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 24: J.C. Pincipe, D. Xu, and J. Fisher. Information theoretic learning. In S. Haykin, editor, Unsupervised Adaptive Filtering John Wiley & Sons, 2000.
• 25: A. Renyi. On Measures of Entropy and Information. In Proc. of the Fourth Berkeley Symp. Math., Statistics, and Probability 1960.
• 26: J. Rissanen. A universal prior for integers and estimation by minimum description length. The Annals of Statistics 1983.
• 27: Jorma Rissanen, Stochastic Complexity in Statistical Inquiry Theory, World Scientific Publishing Co., Inc., River Edge, NJ, 1989
• 28: C. E. Shannon. A mathematical theory of communication. Bell System Techical Journal pages 379--423, 1948.
• 29: C. S. Wallace and D. M. Boulton. An information measure for classification.The Computer Journal 11(2), 1968.
• 30: C. S. Wallace and D. L. Dowe. Intrinsic classification by MML, the Snob program. In Proceedings of the 7th Australian Joint Conference on Artificial Intelligence 1994.
• 31: 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:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

Keywords:
clustering, data streams, entropy