Fully automatic cross-associations

ABSTRACT

Large, sparse binary matrices arise in numerous data mining applications, such as the analysis of market baskets, web graphs, social networks, co-citations, as well as information retrieval, collaborative filtering, sparse matrix reordering, etc. Virtually all popular methods for the analysis of such matrices---e.g., k-means clustering, METIS graph partitioning, SVD/PCA and frequent itemset mining---require the user to specify various parameters, such as the number of clusters, number of principal components, number of partitions, and "support." Choosing suitable values for such parameters is a challenging problem.Cross-association is a joint decomposition of a binary matrix into disjoint row and column groups such that the rectangular intersections of groups are homogeneous. Starting from first principles, we furnish a clear, information-theoretic criterion to choose a good cross-association as well as its parameters, namely, the number of row and column groups. We provide scalable algorithms to approach the optimal. Our algorithm is parameter-free, and requires no user intervention. In practice it scales linearly with the problem size, and is thus applicable to very large matrices. Finally, we present experiments on multiple synthetic and real-life datasets, where our method gives high-quality, intuitive results.

REFERENCES

• 1: Dan Pelleg , Andrew W. Moore, X-means: Extending K-means with Efficient Estimation of the Number of Clusters, Proceedings of the Seventeenth International Conference on Machine Learning, p.727-734, June 29-July 02, 2000
• 2: G. Hamerly and C. Elkan, "Learning the k in k-means," in Proc. 17th NIPS, 2003.
• 3: Bin Zhang , Meichun Hsu , Umeshwar Dayal, K-Harmonic Means - A Spatial Clustering Algorithm with Boosting, Proceedings of the First International Workshop on Temporal, Spatial, and Spatio-Temporal Data Mining-Revised Papers, p.31-45, September 12, 2000
• 4: 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]
• 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: 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
• 7: George Karypis , Eui-Hong (Sam) Han , Vipin Kumar, Chameleon: Hierarchical Clustering Using Dynamic Modeling, Computer, v.32 n.8, p.68-75, August 1999 [doi>10.1109/2.781637]
• 8: A. Hinneburg and D. A. Keim, "An efficient approach to clustering in large multimedia databases with noise," in Proc. 4th KDD, pp. 58--65, 1998.
• 9: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 10: Inderjit S. Dhillon , Subramanyam Mallela , Dharmendra S. Modha, Information-theoretic co-clustering, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956764]
• 11: M. M. Madiman, M. Harrison, and I. Kontoyiannis, "A minimum description length proposal for lossy data compression," in Proc. IEEE ISIT, 2004.
• 12: 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
• 13: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 14: Jiawei Han , Jian Pei , Yiwen Yin , Runying Mao, Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach, Data Mining and Knowledge Discovery, v.8 n.1, p.53-87, January 2004 [doi>10.1023/B:DAMI.0000005258.31418.83]
• 15: Alexander Tuzhilin , Gediminas Adomavicius, Handling very large numbers of association rules in the analysis of microarray data, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775104]
• 16: S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman, "Indexing by latent semantic analysis," JASI, vol. 41, pp. 391--407, 1990.
• 17: Tamara G. Kolda , Dianne P. O'Leary, A semidiscrete matrix decomposition for latent semantic indexing information retrieval, ACM Transactions on Information Systems (TOIS), v.16 n.4, p.322-346, Oct. 1998 [doi>10.1145/291128.291131]
• 18: 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]
• 19: Christos H. Papadimitriou , Hisao Tamaki , Prabhakar Raghavan , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.159-168, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275505]
• 20: George Karypis , Vipin Kumar, Multilevel algorithms for multi-constraint graph partitioning, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-13, November 07-13, 1998, San Jose, CA
• 21: A. Y. Ng, M. I. Jordan, and Y. Weiss, "On spectral clustering: Analysis and an algorithm," in Proc. NIPS, pp. 849--856, 2001.
• 22: N. Mishra, D. Ron, and R. Swaminathan, "On finding large conjunctive clusters," in Proc. 16th COLT, 2003.
• 23: P. Krishna Reddy , Masaru Kitsuregawa, An Approach to Relate the Web Communities through Bipartite Graphs, Proceedings of the Second International Conference on Web Information Systems Engineering (WISE'01) Volume 1, p.301, December 03-06, 2001
• 24: Chun Tang , Aidong Zhang, Mining multiple phenotype structures underlying gene expression profiles, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956942]
• 25: J. Rissanen, "Modeling by shortest data description," Automatica, vol. 14, pp. 465--471, 1978.
• 26: J. Rissanen, "Generalized Kraft inequality and arithmetic coding," IBM J. Res. Dev., vol. 20, no. 3, pp. 198--203, 1976.
• 27: J. Rissanen and G. G. Langdon Jr., "Arithmetic coding," IBM J. Res. Dev., vol. 23, pp. 149--162, 1979.
• 28: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]
• 29: J. Rissanen, "Universal prior for integers and estimation by minimum description length," Annals of Statistics, vol. 11, no. 2, pp. 416--431, 1983.
• 30: Duncan J. Watts, Small worlds: the dynamics of networks between order and randomness, Princeton University Press, Princeton, NJ, 1999
• 31: M. Richardson, R. Agrawal, and P. Domingos, "Trust management for the semantic web," in Proc. 2nd ISWC, pp. 351--368, 2003.
• 32: Alan L. Montgomery , Christos Faloutsos, Identifying Web Browsing Trends and Patterns, Computer, v.34 n.7, p.94-95, July 2001 [doi>10.1109/2.933515]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing

General Terms:
Algorithms, Theory

Keywords:
MDL, cross-association, information theory