Insights from Network Structure for Text Mining

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 1616–1625, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Insights from Network Structure for Text Mining Zornitsa Kozareva and Eduard Hovy USC Information Sciences Institute 4676 Admiralty Way Marina del Rey, CA 90292-6695 {kozareva,hovy}@isi.edu Abstract Text mining and data harvesting algorithms have become popular in the computational lin- guistics community. They employ patterns that specify the kind of information to be har- vested, and usually bootstrap either the pat- tern learning or the term harvesting process (or both) in a recursive cycle, using data learned in one step to generate more seeds for the next. They therefore treat the source text corpus as a network, in which words are the nodes and relations linking them are the edges. The re- sults of computational network analysis, espe- cially from the world wide web, are thus ap- plicable. Surprisingly, these results have not yet been broadly introduced into the computa- tional linguistics community. In this paper we show how various results apply to text mining, how they explain some previously observed phenomena, and how they can be helpful for computational linguistics applications. 1 Introduction Text mining / harvesting algorithms have been ap- plied in recent years for various uses, including learning of semantic constraints for verb participants (Lin and Pantel, 2002) related pairs in various rela- tions, such as part-whole (Girju et al., 2003), cause (Pantel and Pennacchiotti, 2006), and other typical information extraction relations, large collections of entities (Soderland et al., 1999; Etzioni et al., 2005), features of objects (Pasca, 2004) and ontolo- gies (Carlson et al., 2010). They generally start with one or more seed terms and employ patterns that specify the desired information as it relates to the seed(s). Several approaches have been developed specifically for learning patterns, including guided pattern collection with manual filtering (Riloff and Shepherd, 1997) automated surface-level pattern in- duction (Agichtein and Gravano, 2000; Ravichan- dran and Hovy, 2002) probabilistic methods for tax- onomy relation learning (Snow et al., 2005) and ker- nel methods for relation learning (Zelenko et al., 2003). Generally, the harvesting procedure is recur- sive, in which data (terms or patterns) gathered in one step of a cycle are used as seeds in the following step, to gather more terms or patterns. This method treats the source text as a graph or network, consisting of terms (words) as nodes and inter-term relations as edges. Each relation type in- duces a different network1. Text mining is a process of network traversal, and faces the standard prob- lems of handling cycles, ranking search alternatives, estimating yield maxima, etc. The computational properties of large networks and large network traversal have been studied inten- sively (Sabidussi, 1966; Freeman, 1979; Watts and Strogatz, 1998) and especially, over the past years, in the context of the world wide web (Page et al., 1999; Broder et al., 2000; Kleinberg and Lawrence, 2001; Li et al., 2005; Clauset et al., 2009). Surpris- ingly, except in …

Content truncated to 500 words