Document clustering with prior knowledge

ABSTRACT

Document clustering is an important tool for text analysis and is used in many different applications. We propose to incorporate prior knowledge of cluster membership for document cluster analysis and develop a novel semi-supervised document clustering model. The method models a set of documents with weighted graph in which each document is represented as a vertex, and each edge connecting a pair of vertices is weighted with the similarity value of the two corresponding documents. The prior knowledge indicates pairs of documents that known to belong to the same cluster. Then, the prior knowledge is transformed into a set of constraints. The document clustering task is accomplished by finding the best cuts of the graph under the constraints. We apply the model to the Normalized Cut method to demonstrate the idea and concept. Our experimental evaluations show that the proposed document clustering model reveals remarkable performance improvements with very limited training samples, and hence is a very effective semi-supervised classification tool.

REFERENCES

• 1: Sugato Basu , Arindam Banerjee , Raymond J. Mooney, Semi-supervised Clustering by Seeding, Proceedings of the Nineteenth International Conference on Machine Learning, p.27-34, July 08-12, 2002
• 2: Kristin P. Bennett , Ayhan Demiriz, Semi-supervised support vector machines, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.368-374, July 1999
• 3: 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]
• 4: P. K. Chan, D. F. Schlag, and J. Y. Zien. Spectral k-way ratio-cut partitioning an clustering. IEEE Transaction Computer-Aided Design, 13:1088--1096, September 1994.
• 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: D. Eichmann, M. Ruiz, and P. Srinivasan. Cluster-Based adaptive and batch filtering. In Proceedings of the 7th Text Retrieval Conference. NIST, 2000
• 7: G. H. Golub and C. F. Van Loan. Matrix Computations. John Hopkins Press, 1999
• 8: J. Hartigan and M. Wong. A k-means clustering algorithm. Applied Statistics, 28:100--108, 1979
• 9: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 10: Thorsten Joachims, Transductive Inference for Text Classification using Support Vector Machines, Proceedings of the Sixteenth International Conference on Machine Learning, p.200-209, June 27-30, 1999
• 11: T. Joachim. Transductive Learning via Spectral Graph Partitioning. Proceedings of the International Conference on Machine Learning, pp.290--297, 2003.
• 12: R. S. Michalski and R. E. Stepp. Learning from observation: Conceptual clustering. Machine Learning, an Artificial Intelligence Approach, pages 331--363. Tioga Publishing Co., Palo Alto, CA, 1983.
• 13: T. Mitchell. The role of unlabeled data in supervised learning. Proceedings of the Sixth International Colloquium on Cognitive Science, 1999.
• 14: J.L.Neto, A.D.Santos, C.A.A. Kaestner, and A.A. Freitas. Document Clustering and Text Summarization. 4th International Conference on Practical Applications of Knowledge Discovery and Data Ming, London, 2000.
• 15: Kamal Nigam , Rayid Ghani, Analyzing the effectiveness and applicability of co-training, Proceedings of the ninth international conference on Information and knowledge management, p.86-93, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354805]
• 16: Stefan Siersdorfer , Sergej Sizov, Restrictive clustering and metaclustering for self-organizing document collections, 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.1009032]
• 17: 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]
• 18: F. Wilcoxon. Individual comparisons by ranking methods. Biometrics, 1, 80--93.
• 19: Kiri Wagstaff , Claire Cardie , Seth Rogers , Stefan Schrödl, Constrained K-means Clustering with Background Knowledge, Proceedings of the Eighteenth International Conference on Machine Learning, p.577-584, June 28-July 01, 2001
• 20: Kiri Wagstaff , Claire Cardie, Clustering with Instance-level Constraints, Proceedings of the Seventeenth International Conference on Machine Learning, p.1103-1110, June 29-July 02, 2000
• 21: Yiming Yang , Xin Liu, A re-examination of text categorization methods, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.42-49, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312647]
• 22: S. X. Yu and J. Shi Grouping with Bias. Neural Information Processing Systems, 2001.
• 23: Stella X. Yu , Jianbo Shi, Segmentation Given Partial Grouping Constraints, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.2, p.173-183, January 2004 [doi>10.1109/TPAMI.2004.1262179]
• 24: Hua-Jun Zeng , Qi-Cai He , Zheng Chen , Wei-Ying Ma , Jinwen Ma, Learning to cluster web search results, 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.1009030]
• 25: H. Zha, C. Ding, M. Gu and H. Simon. Spectral relaxation for k-means clustering. Proceedings of Advances in Neural Information Processing Systems, vol 14, 2002.
• 26: http://svmlight.joachims.org/
• 27: X. Zhu, Z. Ghahramani, J. Lafferty. Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions. The Twentieth International Conference on Machine Learning, 2003.

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Theory

Keywords:
clustering with prior knowledge, semi-supervised learning, spectral clustering