Graph-based Word Clustering using a Web Search Engine

Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 542–550, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Graph-based Word Clustering using a Web Search Engine Yutaka Matsuo National Institute of Advanced Industrial Science and Technology 1-18-13 Sotokanda, Tokyo 101-0021 y.matsuo@aist.go.jp Takeshi Sakaki University of Tokyo 7-3-1 Hongo Tokyo 113-8656 Kˆoki Uchiyama Hottolink Inc. 2-11-17 Nishi-gotanda Tokyo 141-0031 uchi@hottolink.co.jp Mitsuru Ishizuka University of Tokyo 7-3-1 Hongo Tokyo 113-8656 ishizuka@i.u-tokyo.ac.jp Abstract Word clustering is important for automatic thesaurus construction, text classification, and word sense disambiguation. Recently, several studies have reported using the web as a corpus. This paper proposes an unsupervised algorithm for word clus- tering based on a word similarity mea- sure by web counts. Each pair of words is queried to a search engine, which pro- duces a co-occurrence matrix. By calcu- lating the similarity of words, a word co- occurrence graph is obtained. A new kind of graph clustering algorithm called New- man clustering is applied for efficiently identifying word clusters. Evaluations are made on two sets of word groups derived from a web directory and WordNet. 1 Introduction The web is a good source of linguistic informa- tion for several natural language techniques such as question answering, language modeling, and multilingual lexicon acquisition. Numerous stud- ies have examined the use of the web as a corpus (Kilgarriff, 2003). Web-based models perform especially well against the sparse data problem: Statistical tech- niques perform poorly when the words are rarely used. For example, F. Keller et al. (2002) use the web to obtain frequencies for unseen bigrams in a given corpus. They count for adjective-noun, noun-noun, and verb-object bigrams by querying a search engine, and demonstrate that web fre- quencies (web counts) correlate with frequencies from a carefully edited corpus such as the British National Corpus (BNC). Aside from counting bi- grams, various tasks are attainable using web- based models: spelling correction, adjective order- ing, compound noun bracketing, countability de- tection, and so on (Lapata and Keller, 2004). For some tasks, simple unsupervised models perform better when n-gram frequencies are obtained from the web rather than from a standard large corpus; the web yields better counts than the BNC. The web is an excellent source of information on new words. Therefore, automatic thesaurus construction (Curran, 2002) offers great potential for various useful NLP applications. Several stud- ies have addressed the extraction of hypernyms and hyponyms from the web (Miura et al., 2004; Cimiano et al., 2004). P. Turney (2001) presents a method to recognize synonyms by obtaining word counts and calculating pointwise mutual informa- tion (PMI). For further development of automatic thesaurus construction, word clustering is benefi- cial, e.g. for obtaining synsets. It also contributes to word sense disambiguation (Li and Abe, 1998) and text classification (Dhillon et al., 2002) be- cause the dimensionality is reduced efficiently. This paper presents an unsupervised algorithm for word clustering based on a word similarity measure by web counts. Given a set of words, the algorithm clusters …

Content truncated to 500 words