Concept Discovery from Text

Concept Discovery from Text Dekang Lin and Patrick Pantel Department of Computing Science University of Alberta Edmonton, Alberta, Canada, T6G 2E8 {lindek,ppantel}@cs.ualberta.ca Abstract Broad-coverage lexical resources such as WordNet are extremely useful. However, they often include many rare senses while missing domain-specific senses. We present a clustering algorithm called CBC (Cluster- ing By Committee) that automatically discovers concepts from text. It initially discovers a set of tight clusters called committees that are well scattered in the similarity space. The centroid of the members of a committee is used as the feature vector of the cluster. We proceed by assigning elements to their most similar cluster. Evaluating cluster quality has always been a difficult task. We present a new evaluation methodology that is based on the editing distance between output clusters and classes extracted from WordNet (the answer key). Our experiments show that CBC outperforms several well-known clustering algorithms in cluster quality. 1 Introduction Broad-coverage lexical resources such as WordNet are extremely useful in applications such as Word Sense Disambiguation (Leacock, Chodorow, Miller 1998) and Question- Answering (Pasca and Harabagiu 2001). However, they often include many rare senses while missing domain-specific senses. For example, in WordNet, the words dog, computer and company all have a sense that is a hyponym of person. Such rare senses make it difficult for a coreference resolution system to use WordNet to enforce the constraint that personal pronouns (e.g. he or she) must refer to a person. On the other hand, WordNet misses the user-interface- object sense of the word dialog (as often used in software manuals). One way to deal with these problems is to use a clustering algorithm to automatically induce semantic classes (Lin and Pantel 2001). Many clustering algorithms represent a cluster by the centroid of all of its members (e.g., K- means) (McQueen 1967) or by a representative element (e.g., K-medoids) (Kaufmann and Rousseeuw 1987). When averaging over all elements in a cluster, the centroid of a cluster may be unduly influenced by elements that only marginally belong to the cluster or by elements that also belong to other clusters. For example, when clustering words, we can use the contexts of the words as features and group together the words that tend to appear in similar contexts. For instance, U.S. state names can be clustered this way because they tend to appear in the following contexts: (List A) ___ appellate court campaign in ___ ___ capital governor of ___ ___ driver's license illegal in ___ ___ outlaws sth. primary in ___ ___'s sales tax senator for ___ If we create a centroid of all the state names, the centroid will also contain features such as: (List B) ___'s airport archbishop of ___ ___'s business district fly to ___ ___'s mayor mayor of ___ ___'s subway outskirts of ___ because some of the state names (like New York and Washington) are also names of cities. Using a single representative from a cluster may be problematic too because each individual element has its own …

Content truncated to 500 words