Text mining apparatus and associated methods

A method for extracting key terms and associated key terms for use in text mining is provided. The method includes receiving unstructured text documents, such as emails over a customer service system. Term candidates are extracted based on identifying consecutive word strings satisfying a context independency threshold. Term candidates are weighted using mutual information to generate a list of weighted terms. The weighted terms are then recounted. Terms are associated based on Chi-square values. Associated terms can then be used for information retrieval. A user interface can be personalized with individual user profiles.

BACKGROUND OF THE INVENTION

The present invention relates to text mining. In particular, the present invention relates to extracting key terms and associated key terms for data mining purposes.

Customers often send companies emails that ask questions, suggest new features or improvements, explain how a product is being used, report problems, praise or criticize customer service, and the like. Similarly, Internet message boards, webblogs, focus groups, newsgroups, and the like also generate text, which discuss similar product and customer service subjects.

The information contained in these emails and other text sources can be very useful. The information, for example, can permit companies to measure consumer satisfaction, predict market trends, detect problems with products, classify documents for research, and the like.

However, some large companies may receive thousands of emails per day on many subjects. The volume of information available from Internet and other sources is also very large. Therefore, it can be difficult to retrieve useful information from the voluminous amount of data received.

Text mining is a variation of a field called “data mining,” which tries to find interesting patterns from large databases. A typical example in data mining is using consumer purchasing patterns to predict which products to place close together on shelves, or to offer coupons for, and so on. For example, a customer buying a flashlight is likely to also buy batteries.

Text mining is an extension of data mining. The difference between regular data mining and text mining is that, in data mining, patterns are analyzed from structured databases of facts; in text mining, patterns and/or associations in unstructured text are analyzed to extract useful information. Also, databases are designed for programs to process automatically; text is written for people to read. Presently, there are limitations in how well computer programs can be designed to “read” and understand text as people do. There are also limitations and costs associated with people reading large volumes of text in order to extract useful information.

Different forms of text mining utilizing a computer can include keyword searches and various relevance ranking algorithms. While these methods can be effective, a user must usually spend significant amounts of time to effectively identify and sort relevant documents. Thus, text mining can be time-consuming, tedious, and expensive.

As a result, an improved system and method that addresses one, some, or all of the issues associated with present text mining would have significant utility.

SUMMARY OF THE INVENTION

A method for extracting associated key phrases or terms for use in text mining is provided. The method includes generating term candidates using a suffix array and values for evaluating context independence of the term candidates. Term candidates are weighted to generate a key term list based on weighted mutual information. The terms are then recounted to generate terms with weighting and more accurate count values. The method can further include automatic synonym detection. During text mining, information associated with terms is extracted from text documents via a user interface that can be personalized.

DETAILED DESCRIPTION OF ILLUSTRATIVE EMBODIMENTS

The present invention relates to extracting key terms to provide an efficient and accurate tool for text mining. In one aspect, key terms are extracted with weighting and frequency (i.e. count) values. In another aspect, the key terms can then be used for performing text mining to extract useful information from text documents. In still another aspect, synonymous terms can be automatically generated for each extracted key term. In another aspect, the present inventions include a user interface that can be personalized with individualized profiles. Before addressing the present invention in further detail, a suitable environment for use with the present invention will be described.

The invention may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The invention may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices. Tasks performed by the programs and modules are described below and with the aid of figures. Those skilled in the art can implement the description and figures as processor executable instructions, which can be written on any form of a computer readable medium.

A user may enter commands and information into the computer110through input devices such as a keyboard162, a microphone163, and a pointing device161, such as a mouse, trackball or touch pad. Other input devices (not shown) may include a joystick, game pad, satellite dish, scanner, or the like. For natural user interface applications, a user may further communicate with the computer using speech, handwriting, gaze (eye movement), and other gestures. To facilitate a natural user interface, a computer may include microphones, writing pads, cameras, motion sensors, and other devices for capturing user gestures. These and other input devices are often connected to the processing unit120through a user input interface160that is coupled to the system bus, but may be connected by other interface and bus structures, such as a parallel port, game port or a universal serial bus (USB). A monitor191or other type of display device is also connected to the system bus121via an interface, such as a video interface190. In addition to the monitor, computers may also include other peripheral output devices such as speakers197and printer196, which may be connected through an output peripheral interface190.

FIG. 2is flow diagram showing two broad aspects or steps of the present invention embodied as text mining method200.FIGS. 3 and 5are block diagrams illustrating modules for performing each of these text mining aspects. Step202includes extracting key terms from received text as indicated at203. The extracted key terms are used later in an information retrieval phase. The information retrieval phase includes receiving a query such as from a user over a user interface. Step204includes retrieving information or content associated with the key terms. Text mining method200is recursive in that any number of queries can be received as indicated at207.

FIG. 3is a block diagram illustrating system300for performing key term extraction in accordance with the present inventions.FIG. 4illustrates a method corresponding toFIG. 3, and is discussed concurrently. At step402, unstructured text or documents302are received by key term extraction module304. Unstructured documents302can include emails, text from Internet newsgroups, message boards, and chatsrooms, webblogs, transcripts of focus group, customer surveys, and the like. Unstructured documents302can be selectively obtained and can include information that a company considers useful, for example, to improve customer satisfaction as discussed above.

At step404, pre-processor306performs pre-processing or “data cleaning” on text of unstructured documents302. For example, pre-processor306can remove email headers, and other symbols or words that are considered meaningless. In some embodiments, pre-processor306comprises boundary detection module308, which accesses special symbol list or table310including, for example, symbols such as “,”, “.”, “&”, “#”, “!”, “?” that are used to detect boundaries between sentences and other phrases, such as phrases separated by commas. Boundary detection module308detects sentence boundaries and replaces them with a symbol or token recognized as a sentence boundary. Sentence boundaries are useful because it can be assumed that terms do not cross sentence boundaries. Pre-processor306generates sentence list312that can be stored in a temporary file for further processing.

At step406, term candidate extraction module314receives sentence list312. It is noted that a “term” includes at least two consecutive word strings. Term candidate extraction module314comprises consecutive word string search module316. Using suffix array318, consecutive word string search module316performs indexing of consecutive word strings or N-gram sequences using indexing methods, such as suffix array indexing. In some embodiments, other means of extracting consecutive word strings can be used, such as a “suffix tree” method. Generally, only N-gram sequences having a frequency, count, or co-occurrence of at least 2 are extracted. Also, it can be advantageous to use LCP array320in conjunction with suffix array318to identify and extract consecutive word strings having the desired frequency or count.

A suffix array is a simple data structure that enables lookup of any substring of a string and identification of repeated substrings. It is more compact than a suffix tree and is amenable to storage in secondary memory. A suffix array can be thought of as a sorted list of the suffixes of a given string. It is noted that a suffix is a substring that extends to the end of the given string. The sorted list is presented as an array of integers that identify the suffixes in order. The suffix array for the 11-letter string “ABRACADABRA”, with an endmark # that collates low, is given below, together with the corresponding suffixes. Together, the suffix array and string enable binary search for any substring, e.g. “CAD”. A useful auxiliary data structure is an LCP array, an array of lengths of the longest common prefix between each substring and its predecessor in the suffix array. The second column below gives the LCP array for the corresponding example.

EXAMPLE

Suffix Array

EXAMPLE

Corresponding LCP Array

Term candidate extraction module314further comprises context independency calculator322that calculates entropy values of context words surrounding terms. Typically, context independency calculator322performs stop word removal by removing words such as “of”, “the”, “and”, “have”, “not”, “etc.”, “are” and the like. Generally, stop words cannot be at the beginning or end of a term. The left context of a term T (and right context) is defined as the entropy of surrounding words immediately left (or right) of the consecutive word string. The larger the entropy for a consecutive word string, the more context-independent it is, and hence, the greater likelihood that it is a term. Context independency calculator322can rank consecutive word strings based on context independency values. In some embodiments, term candidates are selected based on a selected context independency threshold. In other embodiments, the top ranking k consecutive word strings (i.e. those having the highest context independency values) are generated by term candidate extraction module314as term candidate list324.

At step408, weighting module326receives term candidate list324and calculates a weighting value for each term candidate. In most embodiments, weighting module326accesses or receives resources336, which comprise boundary stop words338, stop terms340, and notable terms342, to perform weighting or to eliminate some term candidates from term candidate list324. For example, some term candidates can be filtered out using boundary stop words338and/or stop terms340so that the number of term candidates to be weighted is reduced. As noted above, consecutive word strings occurring only once are filtered, and thus, are not considered term candidates324. However, notable terms342are terms that may occur only once but can still be extracted as key terms.

In most embodiments, weighting module326comprises mutual information calculator328, which calculates the mutual information of patterns A and B. The mutual information of patterns A and B, or MI(A,B) is defined as the log-likelihood ratio of the joint probability of patterns A and B over the probability of A and B, which can be expressed as follows:

MI⁡(A,B)=log⁢⁢(P⁡(A,B)P⁡(A)⁢P⁡(B)).
Assuming that a consecutive word string of any length can be expressed as “AB” where “A” and “B” are each a pattern of one or more word strings making up consecutive word string “AB”. Pattern “A” can also be viewed as the left portion of consecutive word string “AB” while pattern “B” can be viewed as the right portion or side of “AB”.

Therefore, the weighted mutual information WMI or “weighting” of A and B is given by the following:

WMI⁡(A,B)=f⁡(A,B)N⁢log⁢⁢N·f⁡(A,B)f⁡(A)⁢f⁡(B)
where f(A,B) is the number of documents sentences (i.e. content) where both A and B occur, f(A) is the number of documents where A occurs, f(B) is the number of documents where B occurs, and N is the number of documents such as unstructured documents302received at input. However, in other embodiments, content can comprise individual sentences such as from sentence list312rather than documents302.

Weighting module326uses mutual information values generated by mutual information calculator328to identify terms meeting a selected WMI threshold. It is noted, however, that other measures of mutual information can be used such as the “significance estimation function”. Weighting module326generates weighted term list330, which comprises key terms and their respective weights.

At step410, recounting module332generates a list of terms with weights and accurate counts334by segmenting the corpus using weighted terms from list330as a dictionary or lexicon. In most embodiments, recounting module332accesses or receives resources344comprising clusters346and synonyms348. Construction of synonyms348and/or clusters346are generally separate procedures, which output synonyms and/or clusters to be used in recounting (as well as mining associated terms described in greater detail below). Synonyms348can be constructed manually or partially automatic. For example, a separate synonym construction module can generate all morphological forms of terms and/or their constituent word strings. The word “book” can be expanded to all its morphological forms: “books”, “booked”, “booking”, etc. to assist in generating synonyms348.

For illustration, a synonym called “Windows Family” can be constructed and include synonymous terms such as “Windows XP” and “Windows NT”. During processing of actual documents, if “Windows XP” and “Windows NT” occur 2 and 3 times, respectively, the synonym “Windows Family” occurs 5 times because it can be viewed as a single term. Clusters like synonyms (such as “Windows Family”) can also be considered single terms during recounting.

It is noted that term recounting generally results in more accurate frequency counts as described in the example below.

EXAMPLE

Assume the following input:Terms: Windows and Windows XPText: “Windows XP is the latest version of the Windows desktop.”Term count at output:Before re-count: Windows XP(1), Windows (2)After recounting: Windows XP(1), Windows (1)
Thus, before re-counting, the count for “Windows” is incorrectly identified at 2. After recount, the count is correctly identified at 1. It is noted that accurate key term counts are important for accurate information retrieval.

FIGS. 5 and 6are illustrative of a system and method for performing information retrieval in accordance with the present inventions. At step602, query502is received by text mining system500. Query502can be in the form of a phrase of one or more word strings, a sentence, a question, etc. that is received over a user interface. In many embodiments, text mining system500comprises pre-processing module504, which can be similar in function to pre-processor306illustrated inFIG. 3. For example, pre-processing module504can segment query502into individual words, and/or remove grammatical features such as commas and/or stop words such as “of” and “and”.

At step606, parser506parse query502into terms. In some embodiments, parser506accesses or receives term dictionary507comprising terms such as weighted terms334described with respect toFIG. 3in order to parse query502into query terms508. Text mining can then be performed for query terms508to retrieve relevant content from text documents302illustrated inFIG. 3.

At step608, Chi-square calculation module510receives query term(s)508. Chi-square calculation module510comprises χ2calculator512, which calculates χ2values between the query term(s)508and the weighted terms334extracted from the text documents302. Chi-square calculation module510first obtains or receives term count information334from the text documents (see table below) in order to calculate χ2values

TABLEyyTotalxf(x, y)f(x,y)f(x)xf(x, y)f(x, y)f(x)totalf(y)f(y)N
where f(x,y) is the number of documents where both terms x and y appear; f(x,y) is the number of documents where x appears but y does not appear; f(x) is the number of documents where x appears; f(x,y) is the number of documents where x does not appear and y appears; f(x,y) is the number of documents where neither x nor y appears; f(x) is the number where x does not appear; f(y) is the number where y appears; f(y) is the number where y does not appear; and N is the number of documents.

Also, it is noted that the following equations are important:
f(x)=f(x,y)+f(x,y)
N=f(x)+f(x)=f(y)+f(y).

Weighted terms334can be sorted in a descending order based on χ2values, which can be calculated based on the following expression:

χ2=(f⁡(x,y)-f⁡(x)·f⁡(y)N)2f⁡(x)·f⁡(y)/N+(f⁡(x,y_)-f⁡(x)·f⁡(y_)N)2f⁡(x)·f⁡(y_)/N+(f⁡(x_,y)-f⁡(x_)·f⁡(y)N)2f⁡(x_)·f⁡(y)/N+(f⁡(x_,y_)-f⁡(x_)·f⁡(y_)N)2f⁡(x_)·f⁡(y_)/N.
The top scoring terms can be identified or generated by Chi-square calculation module510based on χ2values exceeding or meeting a selected threshold. Chi-square calculation module510generates terms associated with the query term(s) or associated terms514for information retrieval.

At step610, information retrieval system receives associated terms514. Information retrieval system516can access or receive resources344comprising clusters346and synonyms348also illustrated inFIG. 3. For example, during information retrieval, each synonymous term of a synonym such as “Windows family” can be mined and/or matched in the text corpus or content518for information retrieval. Information retrieval system516retrieves content associated with query term(s)508and/or associated terms514and outputs associated terms and content as indicated at520.

FIGS. 7a-7billustrate screen shots of a graphical user interface in accordance with the present inventions.

In utilizing the present inventions, the user can access user resources, which can be used for personalized analyses. The user's profile can be viewed as a description of these resources. All user profiles (from one or more users) can be maintained in a central server protected by user authentication functionality. The profiles can be updated and/or shared with other users as desired.

FIG. 7Aillustrates a configuration of resource synonyms.FIG. 7Billustrates category view and key term finder of a specific text mining system. The top-left portion ofFIG. 7Bis the category view. The input texts or documents are classified into pre-defined categories and the number after each category label (e.g. community, verbatim, etc.) is the count of files under the category. The bottom-left portion ofFIG. 7Bis the key term view. The circled phase “having problems” is a key term and the phrase “active directory” is one of the associated terms of “having problems”. The right portion is displaying the selected messages, e.g. email messages. In the display, the term “having problems” and associated term “active directory” are illustrated.