Marti A. Hearst
School of Information Management & Systems
University of California, Berkeley
102 South Hall
Berkeley, CA 94720-4600
The possibilities for data mining from large text collections are virtually untapped. Text expresses a vast, rich range of information, but encodes this information in a form that is difficult to decipher automatically. Perhaps for this reason, there has been little work in text data mining to date, and most people who have talked about it have either conflated it with information access or have not made use of text directly to discover heretofore unknown information.
In this paper I will first define data mining, information access, and corpus-based computational linguistics, and then discuss the relationship of these to text data mining. The intent behind these contrasts is to draw attention to exciting new kinds of problems for computational linguists. I describe examples of what I consider to be real text data mining efforts and briefly outline our recent ideas about how to pursue exploratory data analysis over text.
The nascent field of text data mining (TDM) has the peculiar distinction of having a name and a fair amount of hype but as yet almost no practitioners. I suspect this has happened because people assume TDM is a natural extension of the slightly less nascent field of data mining (DM), also known as knowledge discovery in databases [Fayyad and Uthurusamy1999], and information archeology [Brachman et al.1993]. Additionally, there are some disagreements about what actually constitutes data mining. It turns out that ``mining'' is not a very good metaphor for what people in the field actually do. Mining implies extracting precious nuggets of ore from otherwise worthless rock. If data mining really followed this metaphor, it would mean that people were discovering new factoids within their inventory databases. However, in practice this is not really the case. Instead, data mining applications tend to be (semi)automated discovery of trends and patterns across very large datasets, usually for the purposes of decision making [Fayyad and Uthurusamy1999,Fayyad1997]. Part of what I wish to argue here is that in the case of text, it can be interesting to take the mining-for-nuggets metaphor seriously.
It is important to differentiate between text data mining and information access (or information retrieval, as it is more widely known).
The goal of information access is to help users find documents that satisfy their information needs [Baeza-Yates and Ribeiro-Neto1999]. The standard procedure is akin to looking for needles in a needlestack - the problem isn't so much that the desired information is not known, but rather that the desired information coexists with many other valid pieces of information. Just because a user is currently interested in NAFTA and not Furbies does not mean that all descriptions of Furbies are worthless. The problem is one of homing in on what is currently of interest to the user.
As noted above, the goal of data mining is to discover or derive new information from data, finding patterns across datasets, and/or separating signal from noise. The fact that an information retrieval system can return a document that contains the information a user requested does not imply that a new discovery has been made: the information had to have already been known to the author of the text; otherwise the author could not have written it down.
I have observed that many people, when asked about text data mining, assume it should have something to do with ``making things easier to find on the web''. For example, the description of the KDD-97 panel on Data Mining and the Web stated:
... Two challenges are predominant for data mining on the Web. The first goal is to help users in finding useful information on the Web and in discovering knowledge about a domain that is represented by a collection of Web-documents. The second goal is to analyse the transactions run in a Web-based system, be it to optimize the system or to find information about the clients using the system.1
This search-centric view misses the point that we might actually want to treat the information in the web as a large knowledge base from which we can extract new, never-before encountered information [Craven et al.1998].
On the other hand, the results of certain types of text processing can yield tools that indirectly aid in the information access process. Examples include text clustering to create thematic overviews of text collections [Cutting et al.1992,Chalmers and Chitson1992,Rennison1994,Wise et al.1995,Lin et al.1991,Chen et al.1998], automatically generating term associations to aid in query expansion [Peat and Willett1991,Voorhees1994,Xu and Croft1996], and using co-citation analysis to find general topics within a collection or identify central web pages [White and McCain1989,Larson1996,Kleinberg1998].
Aside from providing tools to aid in the standard information access process, I think text data mining can contribute along another dimension. In future I hope to see information access systems supplemented with tools for exploratory data analysis. Our efforts in this direction are embodied in the LINDI project, described in Section 5 below.
If we extrapolate from data mining (as practiced) on numerical data to data mining from text collections, we discover that there already exists a field engaged in text data mining: corpus-based computational linguistics! Empirical computational linguistics computes statistics over large text collections in order to discover useful patterns. These patterns are used to inform algorithms for various subproblems within natural language processing, such as part-of-speech tagging, word sense disambiguation, and bilingual dictionary creation [Armstrong1994].
It is certainly of interest to a computational linguist that the words ``prices, prescription, and patent'' are highly likely to co-occur with the medical sense of ``drug'' while ``abuse, paraphernalia, and illicit'' are likely to co-occur with the illegal drug sense of this word [Church and Liberman1991]. However, the kinds of patterns found and used in computational linguistics are not likely to be what the general business community hopes for when they use the term text data mining.
Within the computational linguistics framework, efforts in automatic augmentation of existing lexical structures seem to fit the data-mining-as-ore-extraction metaphor. Examples include automatic augmentation of WordNet relations [Fellbaum1998] by identifying lexico-syntactic patterns that unambiguously indicate those relations [Hearst1998], and automatic acquisition of subcategorization data from large text corpora [Manning1993]. However, these serve the specific needs of computational linguistics and are not applicable to a broader audience.
Some researchers have claimed that text categorization should be considered text data mining. Although analogies can be found in the data mining literature (e.g., referring to classification of astronomical phenomena as data mining [Fayyad and Uthurusamy1999]), I believe when applied to text categorization this is a misnomer. Text categorization is a boiling down of the specific content of a document into one (or more) of a set of pre-defined labels. This does not lead to discovery of new information; presumably the person who wrote the document knew what it was about. Rather, it produces a compact summary of something that is already known.
However, there are two recent areas of inquiry that make use of text categorization and do seem to fit within the conceptual framework of discovery of trends and patterns within textual data for more general purpose usage.
One body of work uses text category labels (associated with Reuters newswire) to find ``unexpected patterns'' among text articles [Feldman and Dagan1995,Dagan et al.1996,Feldman et al.1997]. The main approach is to compare distributions of category assignments within subsets of the document collection. For instance, distributions of commodities in country C1 are compared against those of country C2 to see if interesting or unexpected trends can be found. Extending this idea, one country's export trends might be compared against those of a set of countries that are seen as an economic unit (such as the G-7).
Another effort is that of the DARPA Topic Detection and Tracking initiative [Allan et al.1998]. While several of the tasks within this initiative are standard text analysis problems (such as categorization and segmentation), there is an interesting task called On-line New Event Detection, whose input is a stream of news stories in chronological order, and whose output is a yes/no decision for each story, made at the time the story arrives, indicating whether the story is the first reference to a newly occurring event. In other words, the system must detect the first instance of what will become a series of reports on some important topic. Although this can be viewed as a standard classification task (where the class is a binary assignment to the new-event class) it is more in the spirit of data mining, in that the focus is on discovery of the beginning of a new theme or trend.
The reason I consider this examples - using multiple occurrences of text categories to detect trends or patterns - to be ``real'' data mining is that they use text metadata to tell us something about the world, outside of the text collection itself. (However, since these applications use metadata associated with text documents, rather than the text directly, it is unclear if it should be considered text data mining or standard data mining.) The computational linguistics applications tell us about how to improve language analysis, but they do not discover more widely usable information.
The various contrasts made above are summarized in Table 1.
Another way to view text data mining is as a process of exploratory data analysis [Tukey1977,Hoaglin et al.1983] that leads to the discovery of heretofore unknown information, or to answers to questions for which the answer is not currently known.
Of course, it can be argued that the standard practice of reading textbooks, journal articles and other documents helps researchers in the discovery of new information, since this is an integral part of the research process. However, the idea here is to use text for discovery in a more direct manner. Two examples are described below.
For more than a decade, Don Swanson has eloquently argued why it is plausible to expect new information to be derivable from text collections: experts can only read a small subset of what is published in their fields and are often unaware of developments in related fields. Thus it should be possible to find useful linkages between information in related literatures, if the authors of those literatures rarely refer to one another's work. Swanson has shown how chains of causal implication within the medical literature can lead to hypotheses for causes of rare diseases, some of which have received supporting experimental evidence [Swanson1987,Swanson1991,Swanson and Smalheiser1994,Swanson and Smalheiser1997].
For example, when investigating causes of migraine headaches, he extracted various pieces of evidence from titles of articles in the biomedical literature. Some of these clues can be paraphrased as follows:
These clues suggest that magnesium deficiency may play a role in some kinds of migraine headache; a hypothesis which did not exist in the literature at the time Swanson found these links. The hypothesis has to be tested via non-textual means, but the important point is that a new, potentially plausible medical hypothesis was derived from a combination of text fragments and the explorer's medical expertise. (According to swanson91, subsequent study found support for the magnesium-migraine hypothesis [Ramadan et al.1989].)
This approach has been only partially automated. There is, of course, a potential for combinatorial explosion of potentially valid links. beeferman98 has developed a flexible interface and analysis tool for exploring certain kinds of chains of links among lexical relations within WordNet.2 However, sophisticated new algorithms are needed for helping in the pruning process, since a good pruning algorithm will want to take into account various kinds of semantic constraints. This may be an interesting area of investigation for computational linguists.
Switching to an entirely different domain, consider a recent effort to determine the effects of publicly financed research on industrial advances [Narin et al.1997]. After years of preliminary studies and building special purpose tools, the authors found that the technology industry relies more heavily than ever on government-sponsored research results. The authors explored relationships among patent text and the published research literature, using a procedure which was reported as follows in broad97:
The CHI Research team examined the science references on the front pages of American patents in two recent periods - 1987 and 1988, as well as 1993 and 1994 - looking at all the 397,660 patents issued. It found 242,000 identifiable science references and zeroed in on those published in the preceding 11 years, which turned out to be 80 percent of them. Searches of computer databases allowed the linking of 109,000 of these references to known journals and authors' addresses. After eliminating redundant citations to the same paper, as well as articles with no known American author, the study had a core collection of 45,000 papers. Armies of aides then fanned out to libraries to look up the papers and examine their closing lines, which often say who financed the research. That detective work revealed an extensive reliance on publicly financed science.
... Further narrowing its focus, the study set aside patents given to schools and governments and zeroed in on those awarded to industry. For 2,841 patents issued in 1993 and 1994, it examined the peak year of literature references, 1988, and found 5,217 citations to science papers.
Of these, it found that 73.3 percent had been written at public institutions - universities, government labs and other public agencies, both in the United States and abroad.
Thus a heterogeneous mix of operations was required to conduct a complex analyses over large text collections. These operations included:
Because all the data was not available online, much of the work had to be done by hand, and special purpose tools were required to perform the operations.
The objectives of the LINDI project3 are to investigate how researchers can use large text collections in the discovery of new important information, and to build software systems to help support this process. The main tools for discovering new information are of two types: support for issuing sequences of queries and related operations across text collections, and tightly coupled statistical and visualization tools for the examination of associations among concepts that co-occur within the retrieved documents. Both sets of tools make use of attributes associated specifically with text collections and their metadata. Thus the broadening, narrowing, and linking of relations seen in the patent example should be tightly integrated with analysis and interpretation tools as needed in the biomedical example.
Following amant96, the interaction paradigm is that of a mixed-initiative balance of control between user and system. The interaction is a cycle in which the system suggests hypotheses and strategies for investigating these hypotheses, and the user either uses or ignores these suggestions and decides on the next move.
We are interested in an important problem in molecular biology, that of automating the discovery of the function of newly sequenced genes [Walker et al.1998]. Human genome researchers perform experiments in which they analyze co-expression of tens of thousands of novel and known genes simultaneously.4 Given this huge collection of genetic information, the goal is to determine which of the novel genes are medically interesting, meaning that they are co-expressed with already understood genes which are known to be involved in disease. Our strategy is to explore the biomedical literature, trying to formulate plausible hypotheses about which genes are of interest.
Most information access systems require the user to execute and keep track of tactical moves, often distracting from the thought-intensive aspects of the problem [Bates1990]. The LINDI interface provides a facility for users to build and so reuse sequences of query operations via a drag-and-drop interface. These allow the user to repeat the same sequence of actions for different queries. In the gene example, this allows the user to specify a sequence of operations to apply to one co-expressed gene, and then iterate this sequence over a list of other co-expressed genes that can be dragged onto the template. (The Visage interface [Derthick et al.1997] implements this kind of functionality within its information-centric framework.) These include the following operations (see Figure 1):
This system will allow maintenance of several different types of history including history of commands issued, history of strategies employed, and history of hypotheses tested. For the history view, we plan to use a ``spreadsheet'' layout [Hendry and Harper1997] as well as a variation on a ``slide sorter'' view which Visage uses for presentation creation but not for history retention [Roth et al.1997].
Since gene function discovery is a new area, there is not yet a known set of exploration strategies. So initially the system must help an expert user generate and record good exploration strategies. The user interface provides a mechanism for recording and modifying sequences of actions. These include facilities that refer to metadata structure, allowing, for example, query terms to be expanded by terms one level above or below them in a subject hierarchy. Once a successful set of strategies has been devised, they can be re-used by other researchers and (with luck) by an automated version of the system. The intent is to build up enough strategies that the system will begin to be used as an assistant or advisor [Amant1996], ranking hypotheses according to projected importance and plausibility.
Thus the emphasis of this system is to help automate the tedious parts of the text manipulation process and to integrate underlying computationally-driven text analysis with human-guided decision making within exploratory data analysis over text.
|Figure: 1 A hypothetical sequence of operations for the exploration of gene function within a biomedical text collection, where the functions of genes A, B, and C are known, and commonalities are sought to hypothesize the function of the unknown gene. The mapping operation imposes a rank ordering on the selected keywords. The final operation is a selection of only those documents that contain at least one of the top-ranked keywords and that contain mentions of all three known genes.|
For almost a decade the computational linguistics community has viewed large text collections as a resource to be tapped in order to produce better text analysis algorithms. In this paper, I have attempted to suggest a new emphasis: the use of large online text collections to discover new facts and trends about the world itself. I suggest that to make progress we do not need fully artificial intelligent text analysis; rather, a mixture of computationally-driven and user-guided analysis may open the door to exciting new results.
Acknowledgements. Hao Chen, Ketan Mayer-Patel, and Vijayshankar Raman contributed to the design and did all the implementation of the first LINDI prototype.
This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer
Based Learning Unit, University of Leeds.