Orthogonal nonnegative matrix t-factorizations for clustering

ABSTRACT

Currently, most research on nonnegative matrix factorization (NMF)focus on 2-factor $X=FG^T$ factorization. We provide a systematicanalysis of 3-factor $X=FSG^T$ NMF. While it unconstrained 3-factor NMF is equivalent to it unconstrained 2-factor NMF, itconstrained 3-factor NMF brings new features to it constrained 2-factor NMF. We study the orthogonality constraint because it leadsto rigorous clustering interpretation. We provide new rules for updating $F,S, G$ and prove the convergenceof these algorithms. Experiments on 5 datasets and a real world casestudy are performed to show the capability of bi-orthogonal 3-factorNMF on simultaneously clustering rows and columns of the input datamatrix. We provide a new approach of evaluating the quality ofclustering on words using class aggregate distribution andmulti-peak distribution. We also provide an overview of various NMF extensions andexamine their relationships.

REFERENCES

• 1: Michael W. Berry , Susan T. Dumais , Gavin W. O'Brien, Using linear algebra for intelligent information retrieval, SIAM Review, v.37 n.4, p.573-595, Dec. 1995 [doi>10.1137/1037127]
• 2: Daniel Boley, Principal Direction Divisive Partitioning, Data Mining and Knowledge Discovery, v.2 n.4, p.325-344, December 1998 [doi>10.1023/A:1009740529316]
• 3: J.-P. Brunet, P. Tamayo, T. R. Golub, and J. P. Mesirov. Metagenes and molecular pattern discovery using matrix factorization. Proc. Nat'l Academy of Sciences USA, 102(12):4164--4169, 2004.
• 4: M. Chessell. Specification: Common base event, 2003. http://www-128.ibm.com/developerworks/webservices/library/ws-cbe/.
• 5: M. Cooper and J. Foote. Summarizing video using non-negative similarity matrix factorization. In Proc. IEEE Workshop on Multimedia Signal Processing, pages 25--28, 2002.
• 6: 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]
• 7: 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]
• 8: Chris Ding , Xiaofeng He, K-means clustering via principal component analysis, Proceedings of the twenty-first international conference on Machine learning, p.29, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015408]
• 9: C. Ding, X. He, and H. D. Simon. On the equivalence of nonnegative matrix factorization and spectral clustering. Proc. SIAM Data Mining Conf, 2005.
• 10: Chris Ding , Xiaofeng He , Hongyuan Zha , Horst D. Simon, Unsupervised Learning: Self-aggregation in Scaled Principal Component Space, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.112-124, August 19-23, 2002
• 11: C. Ding, T. Li, and M. Jordan. Convex and semi-nonnegative matrix factorizations for clustering and low-dimension representation. Technical Report LBNL-60428, Lawrence Berkeley National Laboratory, University of California, Berkeley, 2006.
• 12: C. Ding, T. Li, and W. Peng. Nonnegative matrix factorization and probabilistic latent semantic indexing: Equivalence, chi-square statistic, and a hybrid method. In AAAI, 2006.
• 13: 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]
• 14: T. Hofmann. Probabilistic latent semantic analysis. In UAI, pages 289--296, 1999.
• 15: Patrik O. Hoyer, Non-negative Matrix Factorization with Sparseness Constraints, The Journal of Machine Learning Research, 5, p.1457-1469, 12/1/2004
• 16: Patrik O. Hoyer, Non-negative Matrix Factorization with Sparseness Constraints, The Journal of Machine Learning Research, 5, p.1457-1469, 12/1/2004
• 17: George Karypis , Eui-Hong (Sam) Han, Fast supervised dimensionality reduction algorithm with applications to document categorization & retrieval, Proceedings of the ninth international conference on Information and knowledge management, p.12-19, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354772]
• 18: D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401:788--791, 1999.
• 19: D. D. Lee and H. S. Seung. Algorithms for non-negatvie matrix factorization. In NIPS 13, 2001.
• 20: S. Z. Li, X. Hou, H. Zhang, and Q. Cheng. Learning spatially localized, parts-based representation. In Proceedings of IEEE Computer Vision and Pattern Recognition, pages 207--212, 2001.
• 21: Tao Li, A general model for clustering binary data, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081894]
• 22: Tao Li , Feng Liang , Sheng Ma , Wei Peng, An integrated framework on mining logs files for computing system management, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081972]
• 23: Tao Li , Sheng Ma , Mitsunori Ogihara, Document clustering via adaptive subspace iteration, 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.1009031]
• 24: Bo Long , Zhongfei (Mark) Zhang , Philip S. Yu, Co-clustering by block value decomposition, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081949]
• 25: A. K. McCallum. Bow: A toolkit for statistical language modeling, text retrieval, classification and clustering. http://www.cs.cmu.edu/ mccallum/bow, 1996.
• 26: G. W. Milligan and M. C. Cooper. A study of the comparability of external criteria for hierarchical cluster analysis. Multivar Behav Res, 21:846--850, 1986.
• 27: P. Paatero and U. Tapper. Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Environmetrics, 5:111--126, 1994.
• 28: H. Park and P. Howland. Generalizing discriminant analysis using the generalized singular value decomposition. IEEE. Trans. on Pattern Analysis and Machine Intelligence, 26:995--1006, 2004.
• 29: W. M. Rand. Objective criteria for the evaluation of clustering methods. J Am Stat Assoc, 66:846--850, 1971.
• 30: F. Sha, L. K. Saul, and D. D. Lee. Multiplicative updates for nonnegative quadratic programming in support vector machines. In NIPS 15, pages 1041--1048. 2003.
• 31: J. Stearley, Towards informatic analysis of syslogs, Proceedings of the 2004 IEEE International Conference on Cluster Computing, p.309-318, September 20-23, 2004
• 32: 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]
• 33: D. Zeimpekis and E. Gallopoulos. Clsi: A flexible approximation scheme from clustered term-document matrices. Proc. SIAM Data Mining Conf, pages 631--635, 2005.
• 34: H. Zha, C. Ding, M. Gu, X. He, and H. D. Simon. Spectral relaxation for K-means clustering. NIPS 14, pages 1057--1064, 2002.
• 35: Hongyuan Zha , Xiaofeng He , Chris Ding , Horst Simon , Ming Gu, Bipartite graph partitioning and data clustering, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502591]
• 36: Ying Zhao , George Karypis, Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering, Machine Learning, v.55 n.3, p.311-331, June 2004 [doi>10.1023/B:MACH.0000027785.44527.d6]

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
clustering, multi-peak distribution, nonnegative matrix factorization (NMF), orthogonal factorization, tri-factorization