Regularized clustering for documents

ABSTRACT

In recent years, document clustering has been receiving more and more attentions as an important and fundamental technique for unsupervised document organization, automatictopic extraction, and fast information retrieval or filtering. In this paper, we propose a novel method for clustering documents using regularization. Unlike traditional globally regularized clustering methods, our method first construct a local regularized linear label predictor for each document vector, and then combine all those local regularizers with a global smoothness regularizer. So we call our algorithm Clustering with Local and Global Regularization (CLGR). We will show that the cluster memberships of the documents can be achieved by eigenvalue decomposition of a sparse symmetric matrix, which can be efficiently solved by iterative methods. Finally our experimental evaluations on several datasets are presented to show the superiorities of CLGR over traditional document clustering methods.

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: 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]
• 3: M. Belkin and P. Niyogi. Towards a Theoretical Foundation for Laplacian-Based Manifold Methods. In Proceedings of the 18th Conference on Learning Theory (COLT). 2005.
• 4: Mikhail Belkin , Partha Niyogi , Vikas Sindhwani, Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples, The Journal of Machine Learning Research, 7, p.2399-2434, 12/1/2006
• 5: 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]
• 6: Léon Bottou , Vladimir Vapnik, Local learning algorithms, Neural Computation, v.4 n.6, p.888-900, Nov. 1992 [doi>10.1162/neco.1992.4.6.888]
• 7: P. K. Chan, D. F. Schlag and J. Y. Zien. Spectral K-way Ratio-Cut Partitioning and Clustering. IEEE Trans. Computer-Aided Design, 13:1088--1096, Sep. 1994.
• 8: Douglass R. Cutting , David R. Karger , Jan O. Pedersen , John W. Tukey, Scatter/Gather: a cluster-based approach to browsing large document collections, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-329, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133214]
• 9: 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]
• 10: C. Ding, X. He, and H. Simon. On the equivalence of nonnegative matrix factorization and spectral clustering. In Proceedings of the SIAM Data Mining Conference, 2005.
• 11: 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
• 12: 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]
• 13: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 14: 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]
• 15: 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]
• 16: 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]
• 17: 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]
• 18: M. Hein, J. Y. Audibert, and U. von Luxburg. From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians. In Proceedings of the 18th Conference on Learning Theory (COLT), 470--485. 2005.
• 19: J. He, M. Lan, C. -L. Tan, S. -Y. Sung, and H. -B. Low. Initialization of Cluster Refinement Algorithms: A Review and Comparative Study. In Proceedings of International Joint Conference on Neural Networks, 2004.
• 20: A. Y. Ng, M. I. Jordan, Y. Weiss. On Spectral Clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems 14. 2002.
• 21: B. SchÄolkopf and A. Smola. Learning with Kernels. The MIT Press. Cambridge, Massachusetts. 2002.
• 22: 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]
• 23: Alexander Strehl , Joydeep Ghosh, Cluster ensembles --- a knowledge reuse framework for combining multiple partitions, The Journal of Machine Learning Research, 3, p.583-617, 3/1/2003
• 24: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 25: Wu, M. and SchÄolkopf, B. A Local Learning Approach for Clustering. In Advances in Neural Information Processing Systems 18. 2006.
• 26: Stella X. Yu , Jianbo Shi, Multiclass Spectral Clustering, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.313, October 13-16, 2003
• 27: 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]
• 28: H. Zha, X. He, C. Ding, M. Gu and H. Simon. Spectral Relaxation for K-means Clustering. In NIPS 14. 2001.
• 29: Tong Zhang , Frank J. Oles, Text Categorization Based on Regularized Linear Classification Methods, Information Retrieval, v.4 n.1, p.5-31, April 2001 [doi>10.1023/A:1011441423217]
• 30: L. Zelnik-Manor and P. Perona. Self-Tuning Spectral Clustering. In NIPS 17. 2005.
• 31: D. Zhou, O. Bousquet, T. N. Lal, J. Weston and B. Scholkopf. Learning with Local and Global Consistency. NIPS 17, 2005.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Algorithms

Keywords:
document clustering, regularization