Co-clustering on manifolds

ABSTRACT

Co-clustering is based on the duality between data points (e.g. documents) and features (e.g. words), i.e. data points can be grouped based on their distribution on features, while features can be grouped based on their distribution on the data points. In the past decade, several co-clustering algorithms have been proposed and shown to be superior to traditional one-side clustering. However, existing co-clustering algorithms fail to consider the geometric structure in the data, which is essential for clustering data on manifold. To address this problem, in this paper, we propose a Dual Regularized Co-Clustering (DRCC) method based on semi-nonnegative matrix tri-factorization. We deem that not only the data points, but also the features are sampled from some manifolds, namely data manifold and feature manifold respectively. As a result, we construct two graphs, i.e. data graph and feature graph, to explore the geometric structure of data manifold and feature manifold. Then our co-clustering method is formulated as semi-nonnegative matrix tri-factorization with two graph regularizers, requiring that the cluster labels of data points are smooth with respect to the data manifold, while the cluster labels of features are smooth with respect to the feature manifold. We will show that DRCC can be solved via alternating minimization, and its convergence is theoretically guaranteed. Experiments of clustering on many benchmark data sets demonstrate that the proposed method outperforms many state of the art clustering methods.

REFERENCES

• 1: Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 2: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 3: Deng Cai , Xiaofei He , Xiaoyun Wu , Jiawei Han, Non-negative Matrix Factorization on Manifold, Proceedings of the 2008 Eighth IEEE International Conference on Data Mining, p.63-72, December 15-19, 2008 [doi>10.1109/ICDM.2008.57]
• 4: O. Chapelle, B. Scholkopf, and A. Zien, editors. Semi-Supervised Learning. MIT Press, Cambridge, MA, 2006.
• 5: F. R. K. Chung. Spectral Graph Theory. American Mathematical Society, February 1997.
• 6: 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]
• 7: Inderjit S. Dhillon , Yuqiang Guan , Brian Kulis, Kernel k-means: spectral clustering and normalized cuts, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014118]
• 8: 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]
• 9: C. H. Ding, T. Li, and M. I. Jordan. Convex and semi-nonnegative matrix factorizations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 99(1), 2008.
• 10: C. H. Q. Ding and X. He. On the equivalence of nonnegative matrix factorization and spectral clustering. In SDM, 2005.
• 11: Chris Ding , Tao Li , Wei Peng , Haesun Park, Orthogonal nonnegative matrix t-factorizations for clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150420]
• 12: X. He and P. Niyogi. Locality preserving projections. In NIPS, 2003.
• 13: D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In NIPS, pages 556--562, 2000.
• 14: Tao Li , Chris Ding, The Relationships Among Various Nonnegative Matrix Factorization Methods for Clustering, Proceedings of the Sixth International Conference on Data Mining, p.362-371, December 18-22, 2006 [doi>10.1109/ICDM.2006.160]
• 15: A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In NIPS, pages 849--856, 2001.
• 16: Mikhail Belkin , Partha Niyogi, Laplacian Eigenmaps for dimensionality reduction and data representation, Neural Computation, v.15 n.6, p.1373-1396, June 2003 [doi>10.1162/089976603321780317]
• 17: S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323--2326, December 2000.
• 18: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 19: Terence Sim , Simon Baker , Maan Bsat, The CMU Pose, Illumination, and Expression Database, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.25 n.12, p.1615-1618, December 2003 [doi>10.1109/TPAMI.2003.1251154]
• 20: N. Tishby, F. C. Pereira, and W. Bialek. The information bottleneck method. CoRR, physics/0004057, 2000.
• 21: Ulrike Luxburg, A tutorial on spectral clustering, Statistics and Computing, v.17 n.4, p.395-416, December 2007 [doi>10.1007/s11222-007-9033-z]
• 22: M. Wu and B. Scholkopf. A local learning approach for clustering. In NIPS, pages 1529--1536, 2006.
• 23: 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]
• 24: H. Zha, X. He, C. H. Q. Ding, M. Gu, and H. D. Simon. Spectral relaxation for k-means clustering. In NIPS, pages 1057--1064, 2001.
• 25: X. Zhu. Semi-supervised learning literature survey. Technical report, Computer Sciences, University of Wisconsin-Madison, 2008.

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

Keywords:
co-clustering, data manifold, feature manifold, graph regularization, semi-nonnegative matrix tri-factorization