Text Data Mining

Issues, Techniques, and the Relation to Information Access

Marti A. Hearst

UC Berkeley

http://www.sims.berkeley.edu/~hearst

Outline

• Background of Text DM
  • Relation to IR, Web DM
  • The new empirical Computational Linguistics
  • Special and important properties of text
• Techniques and Tasks
  • Finding Nuggets
  • Finding Patterns
  • Text Visualization
• Opportunities and Conclusions

Background

• How TDM Differs from IR

• Web != Text

• Why Text is Tough/Easy

• Recent Trends in NLP/CL

Text DM != IR

• Data Mining:

  • Patterns, Nuggets, Exploratory Analysis

• Information Retrieval:

  • Finding and ranking documents that match users’ information need
    • ad hoc query
    • filtering/standing query
  • Maybe Nuggets, but this not standard
    • find article that answers question, info extraction
  • Rarely Patterns, Exploratory Analysis

Information Access(Information Retrieval more broadly construed)

• Problem:

  • Huge amounts of online textual information

• Goal:

  • Build systems to help people discover, create use, re-use, and understand information

• Approach:

  • Leverage off of users’ smarts
  • Combine stats, text analysis, user interfaces

Web != Text

• Not all Text is on the Web

• Web is Text + Structure

  • A spectrum: book chapters to link indexes
  • Information is embedded in the world
    e.g., events, announcements, home pages
    
  • Citation links and usage patterns
  • New opportunities for conTEXTualization

Ore-Filled Text Collections

• Newspaper/Newswire

• Medical Articles

  • Patterns associated with symptoms, drugs

• Patent Law

  • Recent Study Justifying Scientific Funding
  • Hypotheses for New Inventions

• “Corporate Memory”

Why Text is Tough

• Abstract concepts difficult to represent
  (AI-Complete)
  
• “Countless” combinations of subtle, abstract relationships among concepts
• Many ways to represent similar concepts
  space ship, flying saucer, UFO, figment of imagination
  
• Concepts are difficult to visualize
• High dimensionality
  Tens or hundreds of thousands of features
  

Why Text is Tough

• I saw Pathfinder on Mars with a telescope.
• Pathfinder photographed Mars.
• The Pathfinder photograph mars our perception of a lifeless planet.
• The Pathfinder photograph from Ford has arrived.
• The Pathfinder forded the river without marring its paint job.

Why Text is Easy

• Highly redundant in bulk

• Just about any simple algorithm can get “good” results for coarse tasks

  • Pull out “important” phrases
  • Find “meaningfully” related words
  • Create summary from document
  • Major problem: Evaluation
    • Need to define goal or purpose

Recent Trends in NLP (CL)

• Previously: AI, full understanding

• Current: Corpus-based, Statistical

  • ACL proceedings: from 3 corpus-based papers in 1991 to at least half in 1996
  • Stat NLP was tried long ago (Z. Harris)

• Simple Often Wins

  • Echoes results in IR

• Interesting direction:

  • Statistics + Linguistics (Klavans & Resnik 96)

Stupid Text Tricks

• Coarse IR, Clustering
  • Don’t need dimension reduction (except stopwords)
  • Don’t need morphological analysis
  • Don’t need word sense disambiguation
• Partial parsing:
  • Simple, greedy transformation rules
  • Cascading finite state machines
• Categorization
  • Assume independence

There’s One in Every Crowd (Zipf’s Law)

• Zipf’s curves for English and Latin from The Psycho-biology of Language, 1935

Text Analysis (CL) Tasks

• Word Sense Disambiguation

• Automatic Lexicon Augmentation

• Discourse Analysis

• Parsing

  • Phrase Identification
  • Phrase Attachments
  • Predicate/Argument Structure
  • Scope of Conjunctions
  • ...

Transformation Rules

• Others at this workshop have noted that often simple hill-climbing rules win

• Something similar is being seen with certain parsing problems

• Brill’s transformation rules are simpler and as good as or better than complex probabilistic models for several parsing problems

Transformation Rules Example

I [saw V] [Pathfinder N1] [with P] [a telescope N2]

• Have training set, assume v-attach

• Rules of form:

  • if P=p and V-attach, switch to N-attach
  • if N2=“telescope” and V-attach, switch to N-attach

• Most retained rules based on P

• Generalize from individual words using automatically-generated word classes

Observation

Research that exploits patterns in text does so mainly in the service of computational linguistics or information access, rather than for learning about and exploring text collections.

Text Data Mining Tasks

• Nuggets:

  • Question Answering
  • Information Extraction (DB filling)
  • Thesaurus Generation

• Overviews:

  • Summarizing (docs or collections)
  • Categorization (documents)
  • Clustering (collections)

Text “Data Cleaning”

Pre-process text as follows:

• Tokenization

• Morphological Analysis (Stemming)

  inflectional, derivational, or crude IR methods
  

• Part-of-Speech Tagging

  I/Pro see/VP Pathfinder/PN on/P Mars/PN ...
  

• Phrase Boundary Identification

  [Subj I] [VP saw] [DO Pathfinder] [PP on Mars] [PP with a telescope].
  

Question AnsweringMurax, Kupiec, SIGIR ‘93

• Goal: Use Encyclopedia to answer Trivial Pursuit questions
• Method:
  • Heuristics about question type: who when where
  • Match up noun phrases within and across documents
  • Compare to standard vector space IR
• Example: “What famed English site is found on Salisbury Plain?”

Information Extraction

• Appropriate when
  • only a fraction of text contains relevant information
  • a relatively simple, pre-defined rigid target representation
• Hobbs et al: Fastus
  • cascaded finite state transducers
• Riloff et al: AutoSlog
  • lexico-syntactic patterns

Information Extraction Example

Salvadoran President-elect Alfredo Cristiania condemned the terrorist killing of Attorney General Roberto Garcia Alvarado and accused the Farabundo Marti Natinal Liberation Front (FMLN) of the crime. … Garcia Alvarado, 56, was killed when a bomb placed by urban guerillas on his vehicle exploded as it came to a halt at an intersection in downtown San Salvador. … According to the police and Garcia Alvarado’s driver, who escaped unscathed, the attorney general was traveling with two bodyguards. One of them was injured.

Incident: Date 19 Apr 89

Incident: Location El Salvador: San Salvador

Incident: Type Bombing

Perpetrator: Individual ID “urban guerillas”

Perpetrator: Organization ID “FMLN”

Human Target: Name “Roberto Garcia Alvarado”

… ...

Information Extraction: Learning Lexico-Syntactic PatternsAutoslog-TS, Riloff, AAAI ‘96

• Start with known relevant articles

• Extract noun phrases

• Create huge set of patterns of form:

  • <subj> passive-verb <victim> was murdered
  • active-verb <dobj> bombed <target>

• Compute relevance rate:

  • Pr(relevant text|text has patterni) = rel - freqi / total - freqi

• Rank patterns in order of importance

  • relevance rate * log2(freqi), rr > 0.5

• Human judge reviewed top patterns

• Apply all patterns to each text

Summarizing

• High-level summary or survey of all main points.

• How to summarize a collection?

• Example: sentence extraction from a single document (Kupiec et al.)

  • Start with training set, allows evaluation
  • Create heuristics
  • Classification function estimates the probability a given sentence is included in the abstract
  • 42% average precision

Summarizing (Heuristic) FeaturesKupiec et al.

• Sentence Length Cut-off

• Key fixed-phrases

  • this letter, in conclusion, etc.

• Position

  • of paragraph in document (first & last 10)
  • of sentence within paragraph (first, last, median)

• Thematic Words

• Uppercase Words

Summary of Summary PaperKupiec, Pedersen, and Chen, SIGIR 94

• To summarize is to reduce in complexity, and hence in length, while retaining some of the essential qualities of the original.

• This paper focuses on document extracts, a particular kind of computed document summary.

• Document extracts consisting of roughly 20% of the original can be as informative as the full text of a document, which suggests that even shorter extracts may be useful indictive summaries.

• The trends in our results are in agreement with those of Edmunson who used a subjectively weighted combination of features as opposed to training the feature weights using a corpus.

• We have developed a trainable summarizer program that is grounded in a solid statistical framework.

Text Categorization

• Assignment of one or more labels from a pre-defined set to a document

• Example Category sets:

  • MeSH medical hierarchy
  • Library of Congress subject headings
  • ACM keyword hierarchy

• Content vs. External Meta-Data

• Automation:

  • Feature reduction
  • Jaime Carbonell’s talk

What Categories Do

• Summarize a document according to pre-defined main topics

• Compress the many ways of representing a concept into one

• Identify which subset of attributes are salient for a collection

How to Use Text Categories

• Under-investigated

• Mapping query words to controlled vocabulary

• Organizing retrieval results

  • problems:
    • too many categories/document (show example)
    • too many documents/category
    • the right categories aren’t there
  • solutions:
    • Dynacat (Pratt), CataCone (Hearst&Karadi)
    • Clustering of Categories (to be done)

Scatter/Gather ClusteringCutting, Pedersen,Karger, Tukey 92,93

Text Clustering in Browsing & Search

Cluster sets of documents into general “themes”, like a table of contents

Display the contents of the clusters by showing topical terms and typical titles

User chooses subsets of the clusters and re-clusters the documents within

Resulting new groups have different “themes”

New use: Organize Retrieval ResultsHearst et al 95, Hearst & Pedersen 96

S/G Example: query on “star”

Encyclopedia text

14 sports

8 symbols 47 film, tv

68 film, tv (p) 7 music

97 astrophysics

67 astronomy(p) 12 steller phenomena

10 flora/fauna 49 galaxies, stars

29 constellations

7 miscelleneous

Clustering and re-clustering is entirely automated

An Example TDM SystemDagan, Feldman, and Hirsh, SDAIR ‘96(But not really mining over TEXT)

• Data:
  • Reuter’s newswire (22,000 articles, late 1980s)
  • Categories: commodities, time, countries, people, and topic
• Goals:
  • distributions of categories across time (trends)
  • distributions of categories between collections
  • category co-occurrence (e.g., topic|country)
• Interactive Interface:
  • lists, pie charts, 2D line plots

Visualization of Text Characteristics

• Eick: SeeSoft (Software Usage Patterns)

• Torveen: ReadWear/Editwear (Usage Patterns)

• BellCore: Superbook (Term Hit Patterns)

• Hearst: TileBars (Term Hit Patterns)

Text Visualization

• Clusters/Unsupervised Overviews

  • Chalmers: BEAD, Networks of Words
  • Lin,Chen: Kohonen Feature Maps
  • NSA: Local Clusters
  • Pacific Northwest: ThemeScapes
  • Rennison: Galaxy of News

Text Visualization

• Show Docs via Query Term Intersection

  • Korfhage: VIBE
  • Spoerri: InfoCrystal
  • Lyberworld

• Show Web Hyperlink Connectivity

Text Visualization (Summary)

• Huge 2D maps may be inappropriate focus for information retrieval
  • can’t see what documents are about
  • documents forced into one position in semantic space
  • space difficult to browse for IR purposes
• Perhaps more suited for pattern discovery
  • problem: often only one view on the space

Needed from Systems

• Support for linking chains of associations

• Support for combined structured and unstructured data

• Support for combining disparate collections

Needed from Viz/CL

• New ways to visualize content

• Summaries over collections

• Definitions for and evaluations of summaries, phrase extractions

• Full language understanding!

How to Deal with the Web

• Source selection first

• Query on appropriate collections

• Organize the results

• Exploratory Analysis tools can help at all stages

Summary and Future

• Text is tricky to process, but rich and abundant (now)

• Many CL tools available to begin working with

• New kinds of problems, e.g.:

  • What is the latest in database visualization?
  • How is this field related to that field?
  • What drugs have been tested for this symptom?
  • How does this Web site reflect my interests?