Discovering Relations Between Named Entities from a Large Raw Corpus Using Tree Similarity-Based Clustering

R. Dale et al. (Eds.): IJCNLP 2005, LNAI 3651, pp. 378 – 389, 2005. © Springer-Verlag Berlin Heidelberg 2005 Discovering Relations Between Named Entities from a Large Raw Corpus Using Tree Similarity-Based Clustering Min Zhang1, Jian Su1, Danmei Wang1,2, Guodong Zhou1, and Chew Lim Tan2 1 Institute for Infocomm Research, 21 Heng Mui Keng Terrace, Singapore 119613 {mzhang, sujian, stuwang, zhougd}@i2r.a-star.edu.sg 2 Department of Computer Science, National University of Singapore, Singapore, 117543 tancl@comp.nus.edu.sg Abstract. We propose a tree-similarity-based unsupervised learning method to extract relations between Named Entities from a large raw corpus. Our method regards relation extraction as a clustering problem on shallow parse trees. First, we modify previous tree kernels on relation extraction to estimate the similarity between parse trees more efficiently. Then, the similarity between parse trees is used in a hierarchical clustering algorithm to group entity pairs into different clusters. Finally, each cluster is labeled by an indicative word and unreliable clusters are pruned out. Evaluation on the New York Times (1995) corpus shows that our method outperforms the only previous work by 5 in F-measure. It also shows that our method performs well on both high-frequent and less- frequent entity pairs. To the best of our knowledge, this is the first work to use a tree similarity metric in relation clustering. 1 Introduction The relation extraction task identifies various semantic relations such as location, affiliation, revival and so on between entities from text. For example, the sentence “George Bush is the president of the United States.” conveys the semantic relation “President”, between the entities “George Bush” (PERSON) and “the United States” (GPE1). The task of relation extraction was first introduced as part of the Template Element task in MUC6 and formulated as the Template Relation task in MUC7 [1]. Most work at MUC [1] was rule-based, which tried to use syntactic and semantic patterns to capture the corresponding relations by means of manually written linguis- tic rules. The major drawback of this method is the poor adaptability and the poor robustness in handling large-scale or new domain data due to two reasons. First, rules have to be rewritten for different tasks or when porting to different domains. Second, generating rules manually is quite labor- and time-consuming. 1 GPE is an acronym introduced by the ACE (2004) program to represent a Geo-Political Entity --- an entity with land and a government. Discovering Relations Between Named Entities from a Large Raw Corpus 379 Since then, various supervised learning approaches [2,3,4,5] have been explored ex- tensively in relation extraction. These approaches automatically learn relation patterns or models from a large annotated corpus. To decrease the corpus annotation require- ment, some researchers turned to weakly supervised learning approaches [6,7], which rely on a small set of initial seeds instead of a large annotated corpus. However, there is no systematic way in selecting initial seeds and deciding an “optimal” number of them. Alternatively, Hasegawa et al. [8] proposed a cosine similarity-based unsupervised learning approach for extracting relations from a large raw …

Content truncated to 500 words