Entropy-based criterion in categorical clustering

ABSTRACT

Entropy-type measures for the heterogeneity of clusters have been used for a long time. This paper studies the entropy-based criterion in clustering categorical data. It first shows that the entropy-based criterion can be derived in the formal framework of probabilistic clustering models and establishes the connection between the criterion and the approach based on dissimilarity co-efficients. An iterative Monte-Carlo procedure is then presented to search for the partitions minimizing the criterion. Experiments are conducted to show the effectiveness of the proposed procedure.

REFERENCES

• 1: Daniel Barbará , Yi Li , Julia Couto, COOLCAT: an entropy-based algorithm for categorical clustering, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584888]
• 2: Baulieu, F. B. (1997). Two variant axiom systems for presence/absence based dissimilarity coefficients. Journal of Classification, 14, 159--170.
• 3: Baxter, R. A., & Oliver, J. J. (1994). MDL and MML: similarities and differences (Technical Report 207). Monash University.
• 4: Bock, H.-H. (1989). Probabilistic aspects in cluster analysis. In O. Optiz (Ed.), Conceptual and numerical analysis of data, 12--44. Berlin: Springer-verlag.
• 5: Celeux, G., & Govaert, G. (1991). Clustering criteria for discrete data and latent class models. Journal of Classification, 8, 157--176.
• 6: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 7: 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]
• 8: 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
• 9: Sudipto Guha , Rajeev Rastogi , Kyuseok Shim, ROCK: a robust clustering algorithm for categorical attributes, Information Systems, v.25 n.5, p.345-366, July 2000 [doi>10.1016/S0306-4379(00)00022-3]
• 10: Mats Gyllenberg , Timo Koski , Martin Verlaan, Classification of binary vectors by stochastic complexity, Journal of Multivariate Analysis, v.63 n.1, p.47-72, Oct. 1997 [doi>10.1006/jmva.1997.1687]
• 11: Havrda, J., & Charvat, F. (1967). Quantification method of classification processes: Concept of structural a-entropy. Kybernetika, 3, 30--35.
• 12: Zhexue Huang, Extensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values, Data Mining and Knowledge Discovery, v.2 n.3, p.283-304, September 1998 [doi>10.1023/A:1009769707641]
• 13: Jardine, N., & Sibson, R. (1971). Mathematical taxonomy. John Wiley & Sons.
• 14: Tao Li , Shenghuo Zhu , Mitsunori Ogihara, Efficient multi-way text categorization via generalized discriminant analysis, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956924]
• 15: McCallum, A. K. (1996). Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. http://www.cs.cmu.edu/mccallum/bow.
• 16: Roberts, S., Everson, R., & Rezek, I. (2000). Maximum certainty data partitioning. Pattern Recognition, 33, 833--839.
• 17: Reuven Y. Rubinstein, Simulation and the Monte Carlo Method, John Wiley & Sons, Inc., New York, NY, 1981
• 18: Symons, M. J. (1981). Clustering criteria and multivariate normal mixtures. Biometrics, 37, 35--43.
• 19: Wallace, R. S. (1989). Finding natural clusters through entropy minimization (Technical Report CMU-CS-89-183). Carnegie Mellon University.
• 20: Zhao, Y., & Karypis, G. (2001). Criterion functions for document clustering: Experiments and analysis (Technical Report). Department of Computer Science, University of Minnesota.