Document clustering by concept factorization

ABSTRACT

In this paper, we propose a new data clustering method called concept factorization that models each concept as a linear combination of the data points, and each data point as a linear combination of the concepts. With this model, the data clustering task is accomplished by computing the two sets of linear coefficients, and this linear coefficients computation is carried out by finding the non-negative solution that minimizes the reconstruction error of the data points. The cluster label of each data point can be easily derived from the obtained linear coefficients. This method differs from the method of clustering based on non-negative matrix factorization (NMF) \citeXu03 in that it can be applied to data containing negative values and the method can be implemented in the kernel space. Our experimental results show that the proposed data clustering method and its variations performs best among 11 algorithms and their variations that we have evaluated on both TDT2 and Reuters-21578 corpus. In addition to its good performance, the new method also has the merit in its easy and reliable derivation of the clustering results.

REFERENCES

• 1: L. Douglas Baker , Andrew Kachites McCallum, Distributional clustering of words for text classification, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.96-103, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290970]
• 2: P. K. Chan, D. F. Schlag, and J. Y. Zien. Spectral k-way ratio-cut partitioning an clustering. IEEE Trans. Computer-Aided Design, 13:1088--1096, Sep. 1994.
• 3: 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]
• 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: Chris H. Q. Ding , Xiaofeng He , Hongyuan Zha , Ming Gu , Horst D. Simon, A Min-max Cut Algorithm for Graph Partitioning and Data Clustering, Proceedings of the 2001 IEEE International Conference on Data Mining, p.107-114, November 29-December 02, 2001
• 6: 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]
• 7: D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401:788--791, 1999.
• 8: Xin Liu , Yihong Gong , Wei Xu , Shenghuo Zhu, Document clustering with cluster refinement and model selection capabilities, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564411]
• 9: K.-R. Muller, S. Mika, G. Ratsch, K. Tsuda, and B. Scholkopf. An introduction to kernel-based learning algorithms. IEEE Trans. Neural Networks, 12:181--202, 3 2001.
• 10: A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems, volume 14, 2002.
• 11: F. Sha, L. K. Saul, and D. D. Lee. Multiplicative updates for nonnegative quadratic programming in support vector machines. In Advances in Neural Information Processing Systems, volume 14, 2002.
• 12: 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]
• 13: 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]
• 14: H. Zha, C. Ding, M. Gu, X. He, and H. Simon. Spectral relaxation for k-means clustering. In Advances in Neural Information Processing Systems, volume 14, 2002.
• 15: 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]
• 16: J. Y. Zien, M. D. F. Schlag, and P. K. Chan. Multilevel spectral hypergraph partitioning with artibary vertex sizes. IEEE Trans. Computer-Aided Design, 18:1389--1399, Sep. 1999.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms

Keywords:
concept factorization, data representation, dimension reduction, document clustering