Information-theoretic co-clustering

ABSTRACT

Two-dimensional contingency or co-occurrence tables arise frequently in important applications such as text, web-log and market-basket data analysis. A basic problem in contingency table analysis is co-clustering: simultaneous clustering of the rows and columns. A novel theoretical formulation views the contingency table as an empirical joint probability distribution of two discrete random variables and poses the co-clustering problem as an optimization problem in information theory---the optimal co-clustering maximizes the mutual information between the clustered random variables subject to constraints on the number of row and column clusters. We present an innovative co-clustering algorithm that monotonically increases the preserved mutual information by intertwining both the row and column clusterings at all stages. Using the practical example of simultaneous word-document clustering, we demonstrate that our algorithm works well in practice, especially in the presence of sparsity and high-dimensionality.

REFERENCES

• 1: P. Bradley, U. Fayyad, and C. Reina. Scaling clustering algorithms to large databases. In KDD'03. AAAI Press, 1998.
• 2: Yizong Cheng , George M. Church, Biclustering of Expression Data, Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology, p.93-103, August 19-23, 2000
• 3: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 4: Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.269-274, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502550]
• 5: I. S. Dhillon, J. Fan, and Y. Guan. Efficient clustering of very large document collections. In R. Grossman, C. Kamath, P. Kegelmeyer, V. Kumar, and R. Namburu, editors, Data Mining for Scientific and Engineering Applications, pages 357-381. Kluwer Academic Publishers, 2001.
• 6: Inderjit S. Dhillon , Subramanyam Mallela , Rahul Kumar, A divisive information theoretic feature clustering algorithm for text classification, The Journal of Machine Learning Research, 3, 3/1/2003
• 7: Inderjit S. Dhillon , Dharmendra S. Modha, Concept Decompositions for Large Sparse Text Data Using Clustering, Machine Learning, v.42 n.1-2, p.143-175, January-February 2001 [doi>10.1023/A:1007612920971]
• 8: Ran El-Yaniv , Oren Souroujon, Iterative Double Clustering for Unsupervised and Semi-supervised Learning, Proceedings of the 12th European Conference on Machine Learning, p.121-132, September 05-07, 2001
• 9: R. A. Fisher. On the interpretation of x2 from the contingency tables, and the calculation of p. J. Royal Stat. Soc., 85:87-94, 1922.
• 10: Nir Friedman , Ori Mosenzon , Noam Slonim , Naftali Tishby, Multivariate Information Bottleneck, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.152-161, August 02-05, 2001
• 11: J. A. Hartigan. Direct clustering of a data matrix. Journal of the American Statistical Association, 67(337):123-129, March 1972.
• 12: Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
• 13: Thomas Hofmann , Jan Puzicha, Latent Class Models for Collaborative Filtering, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.688-693, July 31-August 06, 1999
• 14: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 15: Ken Lang. News Weeder: Learning to filter netnews. In ICML-95, pages 331-339, 1995.
• 16: A. K. McCallum. Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. www.cs.cmu.edu/ mccallum/bow, 1996.
• 17: B. Mirkin. Mathematical Classification and Clustering. Kluwer Academic Publishers, 1996.
• 18: N. Slonim, N. Friedman, and N. Tishby. Agglomerative multivariate information bottleneck. In NIPS-14, 2001.
• 19: Noam Slonim , Naftali Tishby, Document clustering using word clusters via the information bottleneck method, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.208-215, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345578]
• 20: N. Tishby, F. C. Pereira, and W. Bialek. The information bottleneck method. In Proc. of the 37-th Annual Allerton Conference on Communication, Control and Computing, pages 368-377, 1999.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

Keywords:
co-clustering, information theory, mutual information