Language Model-Based Document Clustering Using Random Walks

Proceedings of the Human Language Technology Conference of the North American Chapter of the ACL, pages 479–486, New York, June 2006. c⃝2006 Association for Computational Linguistics Language Model-Based Document Clustering Using Random Walks G¨unes¸ Erkan Department of EECS University of Michigan Ann Arbor, MI 48109-2121 gerkan@umich.edu Abstract We propose a new document vector represen- tation specifically designed for the document clustering task. Instead of the traditional term- based vectors, a document is represented as an �-dimensional vector, where � is the number of documents in the cluster. The value at each di- mension of the vector is closely related to the generation probability based on the language model of the corresponding document. In- spired by the recent graph-based NLP methods, we reinforce the generation probabilities by it- erating random walks on the underlying graph representation. Experiments with k-means and hierarchical clustering algorithms show signif- icant improvements over the alternative � � � � � � vector representation. 1 Introduction Document clustering is one of the oldest and most studied problems of information retrieval (van Rijsbergen, 1979). Almost all document clustering approaches to date have represented documents as vectors in a bag-of-words vec- tor space model, where each dimension of a document vector corresponds to a term in the corpus (Salton and McGill, 1983). General clustering algorithms are then applied to these vectors to cluster the given corpus. There have been attempts to use bigrams or even higher-order n- grams to represent documents in text categorization, the supervised counterpart of document clustering, with little success (Caropreso et al., 2001; Tan et al., 2002). Clustering can be viewed as partitioning a set of data objects into groups such that the similarities between the objects in a same group is high while inter-group simi- larities are weaker. The fundamental assumption in this work is that the documents that are likely to have been generated from similar language models are likely to be in the same cluster. Under this assumption, we propose a new representation for document vectors specifically de- signed for clustering purposes. Given a corpus, we are interested in the generation probabilities of a document based on the language models induced by other documents in the corpus. Using these probabilities, we propose a vector representation where each dimension of a document vector corresponds to a document in the corpus instead of a term in the classical representation. In other words, our document vectors are �-dimensional, where � is the number of documents in the corpus to be clustered. For the vector � � � of docu- ment � �, the th element of � is closely related to the generation probability of � � based on the language model induced by document � . The main steps of our method are as follows:  For each ordered document pair  � �  �  in a given corpus, we compute the generation probability of � � from the language model induced by � mak- ing use of language-model approaches in informa- …

Content truncated to 500 words