A general model for clustering binary data

ABSTRACT

Clustering is the problem of identifying the distribution of patterns and intrinsic correlations in large data sets by partitioning the data points into similarity classes. This paper studies the problem of clustering binary data. This is the case for market basket datasets where the transactions contain items and for document datasets where the documents contain "bag of words". The contribution of the paper is three-fold. First a general binary data clustering model is presented. The model treats the data and features equally, based on their symmetric association relations, and explicitly describes the data assignments as well as feature assignments. We characterize several variations with different optimization procedures for the general model. Second, we also establish the connections between our clustering model with other existing clustering methods. Third, we also discuss the problem for determining the number of clusters for binary clustering. Experimental results show the effectiveness of the proposed clustering model.

REFERENCES

• 1: Charu C. Aggarwal , Joel L. Wolf , Philip S. Yu , Cecilia Procopiuc , Jong Soo Park, Fast algorithms for projected clustering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.61-72, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 3: Baier, D., Gaul, W., & Schader, M. (1997). Two-mode overlapping clustering with applications to simultaneous benefit segmentation and market structuring. In R. Klar and O. Opitz (Eds.), Classification and knowledge organization, 577--566. Springer.
• 4: Baulieu, F. B. (1997). Two variant axiom systems for presence/absence based dissimilarity coefficients. Journal of Classification, 14, 159--170.
• 5: Daniel Boley , Maria Gini , Robert Gross , Eui-Hong (Sam) Han , Kyle Hastings , George Karypis , Vipin Kumar , Bamshad Mobasher , Jerome Moore, Document Categorization and Query Generation on the World Wide WebUsing WebACE, Artificial Intelligence Review, v.13 n.5-6, p.365-391, Dec. 1999 [doi>10.1023/A:1006592405320]
• 6: Castillo, W., & Trejos, J. (2002). Two-mode partitioning: Review of methods and application and tabu search. In K. Jajuga, A. Sokolowski and H.-H. Bock (Eds.), Classification, clustering and data analysis, 43--51. Springer.
• 7: Cho, H., Dhillon, I. S., Guan, Y., & Sra, S. (2004). Minimum sum-squared residue co-clustering of gene experssion data. Proceedings of the SIAM Data Mining Conference.
• 8: Desarbo, W. (1982). GENNCLUS: New models for general nonhierarchical clustering analysis. Psuchometrika, 47, 449--475.
• 9: Deuflhard, P., Huisinga, W., Fischer, A., & Schutte, C. (2000). Identification of almost invariant aggregates in reversible nearly coupled markov chain. Linear Algebra and Its Applications, 315, 39--59.
• 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: 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, Jan. 2001 [doi>10.1023/A:1007612920971]
• 12: Chris Ding , Xiaofeng He , Hongyuan Zha , Horst D. Simon, Adaptive dimension reduction for clustering high dimensional data, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.147, December 09-12, 2002
• 13: Carlotta Domeniconi , Jing Peng , Dimitrios Gunopulos, Locally Adaptive Metric Nearest-Neighbor Classification, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.9, p.1281-1285, September 2002 [doi>10.1109/TPAMI.2002.1033219]
• 14: Golub, G. H., & Loan, C. F. V. (1991). Matrix computations. The Johns Hopkins University Press.
• 15: Govaert, G. (1995). Simultaneous clustering of rows and columns. Control and Cybernetics, 24, 437--458.
• 16: Eui-Hong Han , Daniel Boley , Maria Gini , Robert Gross , Kyle Hastings , George Karypis , Vipin Kumar , Bamshad Mobasher , Jerome Moore, WebACE: a Web agent for document categorization and exploration, Proceedings of the second international conference on Autonomous agents, p.408-415, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280872]
• 17: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 18: Hastie, T., Tibshirani, R., & Friedman, J. (2001). The elements of statistical learning: Data mining, inference, prediction. Springer.
• 19: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 20: Kato, T. (1995). Perturbation theory for linear operators. Springer.
• 21: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 22: Lee, D. D., & Seung, H. S. (2000). Algorithms for non-negative matrix factorization. NIPS (pp. 556--562).
• 23: Li, T., & Ma, S. (2004). IFD:iterative feature and data clustering. Proceedings of the 2004 SIAM International conference on Data Mining (SDM 2004). SIAM.
• 24: Tao Li , Sheng Ma , Mitsunori Ogihara, Entropy-based criterion in categorical clustering, Proceedings of the twenty-first international conference on Machine learning, p.68, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015404]
• 25: Li, T., & Zhu, S. (2005). On clustering binary data. Proceedings of the 2005 SIAM International Conference On Data Mining(SDM'05) (pp. 526--530).
• 26: Maris, E., Boeck, P. D., & Mechelen, I. V. (1996). Probability matrix decomposition models. Psychometrika, 61, 7--29.
• 27: Maurizio, V. (2001). Double k-means clustering for simultaneous classification of objects and variables. In S. Borra, R. Rocci, M. Vichi and M. Schader (Eds.), Advances in classification and data analysis, 43--52. Springer.
• 28: McCallum, A. K. (1996). Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. http://www.cs.cmu.edu/~mccallum/bow.
• 29: Mickey, M. R., Mundle, P., & Engelman, L. (1988). Boolean factor analysis. In Bmdp statistical software manual, vol. 2, 789--800. University of California Press.
• 30: Paatero, P., & Tapper, U. (1994). Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Environmetrics, 5, 111--126.
• 31: Rissanen, J. (1978). Modeling by shortest data description. Automatica, 14, 465--471.
• 32: Sha, F., Saul, L. K., & Lee, D. D. (2002). Multiplicative updates for nonegative quadratic programming in support vector machines. Advances in Neural Information Processing Systems (pp. 1065--1072).
• 33: Shepard, R. N., & Arabie, P. (1979). Additive clustering: Representation of similarities as combinations of discrete overlapping properties. Psychological Review, 86, 87--123.
• 34: 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]
• 35: Soete, G., & Carroll, J. D. (1994). K-means clustering in a low-dimensional eucildean space. New Approaches in Classification and Data Analysis (pp. 212--219). Springer-Verlag.
• 36: Tishby, N., Pereira, F. C., & Bialek, W. (1999). The information bottleneck method. Proc. of the 37-th Annual Allerton Conference on Communication, Control and Computing (pp. 368--377).
• 37: Wei Xu , Yihong Gong, Document clustering by concept factorization, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009029]
• 38: Wei Xu , Xin Liu , Yihong Gong, Document clustering based on non-negative matrix factorization, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860485]
• 39: Zha, H., He, X., Ding, C., & Simon, H. (2001). Spectral relaxation for k-means clustering. Proceedings of Neural Information Processing Systems.
• 40: Zhao, Y., & Karypis, G. (2002). Evaluation of hierarchical clustering algorithms for document datasets (Technical Report). Department of Computer Science, University of Minnesota.
• 41: Shenghuo Zhu , Tao Li , Mitsunori Ogihara, CoFD: An Algorithm for Non-distance Based Clustering in High Dimensional Spaces, Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery, p.52-62, September 04-06, 2002

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering

General Terms:
Algorithms, Experimentation, Theory

Keywords:
binary data, clustering, general model, matrix approximation