INFORMATION MINING USING DOMAIN SPECIFIC CONCEPTUAL STRUCTURES

[0001] The present invention relates generally to the field of information analytics tools and methods in data mining and, more particularly, to eliciting and capturing domain knowledge as part of the data mining process.

[0002] Using text and information mining to find insights in volumes of data is non-trivial. Often endless “googling” (referring to use of the well-known search engine for searching the web) is done to search various kinds of information which might lead to insights. However, such googling is labor-intensive and time-consuming. Furthermore, to make sense of the search results may require significant manual processing. Even so, the results may not be valuable.

[0003] Better methodologies and tools are needed to help identify insights in the information.

[0004] In one embodiment of the present invention, a method, for use with 1) a first set of documents related to a first topic of interest and 2) a second set of documents related to a second topic of interest, comprises the steps of: using a first taxonomy to categorize the first set of documents into a set of categories; categorizing the second set of documents according to the set of categories of the first set of documents; and examining a category to identify a document of interest, the document of interest being a representative document within the category.

[0005] In another embodiment of the present invention, a method, for use with a set of documents related to a first topic of interest, comprises: creating a first set of categories of the set of documents according to an automatically generated taxonomy; creating a second set of categories of the set of documents according to at least one of unstructured data, structured data, and annotations derived from text in the set of documents; constructing a contingency table having the first set of categories along a first axis and the second set of categories along a second axis; and identifying a relationship between at least two different categories using the contingency table.

[0006] In yet another embodiment of the present invention, a method comprises: extracting a set of documents related to a specified topic from a data warehouse; generating a taxonomy for the set of documents that provides a first partition of the set of documents according to the taxonomy; using domain-specific knowledge to re-partition the set of documents to provide a second partition of the set of documents; and creating a refined taxonomy for the set of documents according to the second partition so that the refined taxonomy incorporates the domain-specific knowledge.

[0007] In still another embodiment of the present invention, a computer program product, for use with 1) a first set of documents related to a first topic of interest and 2) a second set of documents related to a second topic of interest, comprises a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to: categorize the first set of documents into a set of categories using a first taxonomy; categorize the second set of documents according to the set of categories of the first set of documents; and examine a category to identify a document of interest, wherein the document of interest typifies the category by most nearly matching a mathematical definition of the category.

[0008] In a further embodiment of the present invention, a computer program product comprises a computer useable medium including a computer readable program, wherein the computer readable program when executed on a computer causes the computer to: extract a set of documents related to a specified topic from a data warehouse; generate a taxonomy for the set of documents that provides a first partition of the set of documents according to the taxonomy; use domain-specific knowledge to re-partition the set of documents to provide a second partition of the set of documents; and create a refined taxonomy for the set of documents according to the second partition so that the refined taxonomy incorporates the domain-specific knowledge.

[0009] These and other features, aspects, and advantages of the present invention will become better understood with reference to the following drawings, description, and claims.

[0015] The following detailed description is of the best currently contemplated modes of carrying out the invention. The description is not to be taken in a limiting sense, but is made merely for the purpose of illustrating the general principles of the invention, since the scope of the invention is best defined by the appended claims.

[0016] Broadly, embodiments of the present invention provide systems and methods of information mining using domain specific conceptual structures. Embodiments of the present invention provide analytics tools, and methodologies involving those tools, for assisting in finding insights in information by eliciting and capturing domain knowledge as part of the mining process. Embodiments may be used, for example, by businesses for patent portfolio analysis, competitor analysis and white space identification, finding potential licensee markets, identification of experts, and finding potential partnering opportunities.

[0017] By enabling the use of user domain-specific knowledge to filter information and efficiently and effectively narrow search results, embodiments of the present invention differ from prior art search techniques that do not have a capability to employ such domain-specific knowledge. For example, one embodiment of the present invention goes beyond typical prior art keyword search to find deeper level relationships between collections of documents and to discover important emerging trends and correlations that would otherwise remain hidden. The present invention's incorporation of domain knowledge to capture critical concepts at each stage and to make these domain concepts the focus of the analysis work product stands in contrast to the absence of such in prior art standard text mining techniques.

[0018] FIG. 1 illustrates information retrieval system 100 in accordance with one embodiment of the present invention. To address the major issues in the information mining process, information retrieval system 100 may utilize a set of analytics tools to allow the use of domain knowledge in the location of information. The analytics tool set may contain a knowledge base data warehouse 102 and a set of analytics tools 104, for identifying information about a specific topic of interest to a user of system 100 (e.g., a topic such as expertise for a group of people) as shown in FIG. 1. The data warehouse 102 may be implemented using computer-readable storage devices 103. Computer-readable storage devices 103 may communicate with a computer system 106 via a network, electronic, or other communication path 108. Computer system 106 may provide an interface for a human user to access data warehouse 102 and may be used to implement and provide a human user interface for analytics tools 104. Data warehouse 102 may contain documents that include, for example, people information as well as other kinds of information that are helpful in analysis. For the example topic of expertise for a group of people, the information could include structured fields on people's titles and ranks. The analytics tools 104 may provide functions including, for example, exploring the data warehouse 102 and analyzing various relationships among documents and people. As indicated in FIG. 1, analytics tools 104 may include capabilities for providing an end user with, for example, taxonomies, name entity extraction, statistical analyses, contingency analyses, and network graph analysis and visualization.

[0019] Referring now to FIG. 2, a method 200 of one embodiment of the present invention may comprise an investigate phase 201 of processes, a comprehend phase 202 of processes, and an examine phase 203 of processes.

[0020] The investigate phase 201 may use a search tool, e.g., from the set of analytics tools 104, to extract a set of documents containing information related to a given topic in a specific domain of interest from a data warehouse, e.g., data warehouse 102. Exploration of the data warehouse using the search tool may use structured features, annotations, and unstructured text indexes in combination to select the relevant information for the topic of interest.

[0021] Then an analytics tool—e.g., from the set of analytics tools 104 and described in more detail below—may convert each document in the extracted document set with a numeric vector that corresponds to the document's dictionary term occurrences (e.g., using the document's word, feature, and structured information content) where the dictionary may be generated based on the frequency of words, phrases, annotations and structured features within each document in the extracted document set, compared to the corpus as a whole. The dictionary may be refined by a user of system 100, if desired.

[0022] These numeric vectors can then be systematically compared in various ways to determine the similarity of any two documents in the extracted document set to each other. Furthermore, other documents outside the initial extracted document set may be compared with the initial extracted document set via the derived dimensions of the initial extracted document set to determine similarity of the other documents to the initial extracted document set as a whole, or to individual documents within the initial extracted document set.

[0023] The comprehend phase 202 may use a document classification technology (also called a “taxonomy generation technology”)—e.g., from the set of analytics tools 104 and described in more detail below—to generate naturally occurring categories from the documents of the extracted document set and to classify a set of selected documents from the extracted document set into appropriate categories. Such a taxonomy generation technology may use the numeric vector space and the feature space created for the selected document set. Furthermore, the taxonomy generation technology may use an interactive clustering of the feature space that can help a domain expert (e.g., a user of system 100) refine the categorization if desired.

[0024] The examine phase 203 may use a contingency table analysis—e.g., from the set of analytics tools 104 and described in more detail below—that compares two taxonomies, or compares a taxonomy against a feature or structured information, such as comparing one taxonomy against a feature over time, or comparing the taxonomy against, e.g., people's titles and ranks (i.e., structured information). The contingency table analysis tool may also enable a detailed category-by-category comparison between two different document sets or two different domain specific conceptual frameworks. Furthermore, a trending tool—e.g., from the set of analytics tools 104 and described in more detail below—that overlays temporal document information on top of document categories may be used to examine the recentness of various aspects of the document information.

[0025] Referring now to FIG. 3, a method 300 of one embodiment of the present invention may begin with a process 301 of taking a given topic of interest and extracting a set of documents P₀ related to the given topic of interest from the data warehouse 102. For example, computer system 106 may be used to extract a set of documents P₀ relevant to the topic of interest from a knowledge base (in data warehouse 102) on the given topic using both search operations and query operations, for example, on text, structured fields, and annotations. The topic of interest-related documents P₀ may be extracted from the data warehouse 102 using an analytics tool from the set of analytics tools 104. The analytics tool may automatically convert the extracted documents P₀ into a numeric vector through words, phrase, and bag of words analysis. For example, computer system 106 through the set of analytics tools 104 may use a method such as that described by U.S. Pat. No. 6,424,971. Such a numeric vector, together with structured information from the documents P₀ may then be used for subsequent analysis. It may also be possible that a user of system 100 would only know about one set of initial extracted documents for one or several specific topics so that, as far as the user were concerned, process 301 could be skipped (having been already effectively completed for that user).

[0026] Continuing with method 300 at process 302, computer system 106 may be used to automatically generate a taxonomy, T₁, for the extracted document set P₀ using words, bag of words, phrases analysis, and structured and unstructured features.

[0027] FIG. 4 shows an example of a generated taxonomy 400 for a document set P₀, which illustrates the following example. In the example, given a document repository of web pages of companies that includes structured (e.g., dates and URL (uniform resource locater)) and unstructured fields (e.g., web page text), it may be desired to create an analysis of what topics are being discussed and in relation to what companies. To do so, method 300 may (e.g., at process 301) extract a set of relevant documents P₀ from the knowledge base (contained, e.g., in data warehouse 102) on a given topic using a query of some kind. For instance, a user of system 100 may be interested in discovering public perception of hybrid electric vehicles. Process 301 may extract the documents P₀ related to hybrid electric vehicles from the data warehouse 102. Then (e.g., at process 302) the set of analytics tools 104 may automatically convert the extracted documents P₀ into a numeric vector through words, phrase, and bag of words analysis, using a method such as that described in U.S. Pat. No. 6,424,971, referenced above. Such a numeric vector, together with structured information may then be used for subsequent analysis. As above, it may also be possible that end users of system 100 only know about one set of extracted documents on specific topics, which can be taken as the document set P₀ so that, as far as such end users were concerned, processes 301 and 302 could be skipped (having been already effectively completed for those users). Using the set of analytics tools 104, users of system 100 can also find the “nearest neighbor”-documents, i.e., the documents P₁ most nearly related to P₀. Then a combined set of all the documents from both P₀ and P₁, denoted P₀+P₁, may need to be examined next.

[0028] For example, a taxonomy based on the extracted document set P₀ can be generated using a method such as that described in U.S. Pat. No. 6,424,971, referenced above. Computer system 106 may be used to automatically classify the document set P₀ using automatic taxonomy generation techniques that treat the documents as words, generating a feature space for the document set P₀ and using clustering technologies such as K-means and other clustering methods to cluster the documents, as disclosed, for example, by Rasmussen, E., “Clustering Algorithms”, in Frakes, W. B. and Baeza-Yates, R., editors, Information Retrieval, Data Structures and Algorithms, pages 419-442, Prentice Hall, Englewood Cliffs, N.J. (1992). Once the clusters are generated, additional refinements can be made by merging, deleting, or adding classes. The taxonomy may also be used to partition the document set P₀, i.e., to divide the document set P₀ up into non-overlapping classes.

[0029] FIG. 4 shows an example of a generated taxonomy 400 for the document set of web pages of companies example given above. Column 401 provides a list of categories (also referred to as “class names” or classifications); column 402 provides, for example, the number of documents of P₀ in each category and the percentage the category represents out of the total number of documents of the set P₀; and column 403 presents temporal trending information in a graphical format that may show, for example, the relative volume of documents published in each category as a function of time over some pre-determined time-span.

[0030] At process 303, method 300 may continue by using specific user domain knowledge to locate domain specific concepts, filter out noise and refine the taxonomy T₁. In the example illustrated, such user domain knowledge may comprise, for example, some specialized knowledge about hybrid electric vehicles, whether technical, marketing, or regulatory in nature.

[0031] At process 304, method 300 may continue by classifying the documents of T₁ (which may be either the original set or the refined set, e.g., the document set P₀ or the document set P₀+P₁) by structured fields, annotations, or other taxonomies. In other words a second classification or categorization—additional to that of taxonomy T₁—may be made of the documents of T₁. For example, to link topics with manufacturers, i.e., companies in the illustrative example, a user of system 100 may use analytics tools 104 to build a second taxonomy T₂ based either on structured fields of the documents of T₁ or on annotations. If the classification is based on a structured field then process 304 may use the URL of the web page to determine the domain name where the web page was originally stored. Another way to make a second classification may be to extract company names using a name-annotation step over the document set of T₁ to extract names out of the documents. In either case the result may be a new taxonomy T₂ based on companies. The second taxonomy T₂ can then be compared to the original taxonomy T₁ (shown in FIG. 4) by creating a contingency table, such as contingency table 500 shown in FIG. 5.

[0032] Method 300 may continue at process 305 by using contingency analysis to generate a contingency table C₀ that compares the refined taxonomy T₁ and the second classification based on process 304. The contingency table C₀— such as contingency table 500 illustrated in FIG. 5—may display a first set of categories (e.g., the companies or automakers of the example) across one axis (e.g., horizontal axis 501 so that each column of the table 500 corresponds to an automaker) and the second set of categories or classifications along the other axis (e.g., vertical axis 502 so that each row of the table 500 corresponds to one of the classifications listed in the “Class” column of table 500). The cells (e.g., cell 503) may indicate the number of documents that occur at the intersection of the first and second classifications, e.g., automaker vs. class of the “Class” column. Each cell—such as cell 503—may have an expected value which can be calculated based on the size 507 of the second category—such as category 504, “fuel economy” for cell 503, and having size 507 equal to 691 in the example—and the total number of documents for the cell, which may also depend on the first (e.g., “automaker”) category for the cell—such as category 505 for cell 503, having the particular value of “honda” in the illustrated example.

[0033] For example, an expected value percentage for each cell may be calculated as (percent of the class's documents out of the total number for the class)×(percent of the documents in the class out of the total number of documents in all classes). If the expected value is exceeded by the actual value in the cell, then the cell may be shaded. For example, cell 503 is illustrated with a moderate shading that matches moderate affinity shading 508. The degree of shading may indicate the degree of significance of the cell's value, which may be calculated, for example, using a statistical test, such as the well-known chi-squared test (see Press, et al., “Numerical Recipes in C, second edition”, New York, Cambridge University Press, (1992), pages 620-623). Shading of each cell may indicate a significant relationship between the class (second category) corresponding to the cell and the first—or horizontal axis—category corresponding to the cell, and the degree of shading may indicate the degree of significance of the relationship. For example, the moderate affinity shading of cell 503 may indicate a moderate degree (as compared to “very high” 509, “low” 510, and “no” 511 degrees of affinity illustrated in FIG. 5) of significance between class 504 (e.g., “fuel economy”) and category 505 (e.g., “honda”) of cell 503. Each cell may also contain a checkbox, which may be checked—as shown for cell 503—for any desired special purpose, such as to draw specific attention to the particular cell.

[0034] Method 300 may continue at process 306 by finding significant relationships using contingency tables C₀. For example, looking at typical examples within each category along axis 501 (first category) of contingency table C₀ 500, process 306 may produce the following observations:

[0035] 1. Honda and Toyota are the most frequently discussed, with GM following.

[0036] 2. VW was the least frequently discussed.

[0037] 3. Discussion seems to center around sales of Honda and Toyota models.

[0038] 4. Honda discussions are highly associated with the topic of fuel economy.

[0039] 5. New models and future plans were the frequent topics when GM was discussed.

[0040] 6. Web content that discussed HEV's and SUV's frequently mentioned Ford.

[0041] Method 300 may continue at process 307 by overlaying trending information on top of document taxonomy T₁, and contingency tables C₀. For example, FIG. 4 shows trending information 403 overlaid on a taxonomy T₁. Trending information—such as trending information 403—may be added to each cell of a contingency table C₀. For example, each cell (e.g., cell 503) of contingency table 500 may contain trending information in graphical form, which may be similar in description to that given above for trending information 403. In the illustrative example given, the trend lines in each cell of contingency table 500 may be based on the structured information relating to the date of each web page from the document set P₀. The structured information relating to the date of each web page may then be converted into a trend graph showing how the contents of each cell tracks over time. Such trend graphs may help reveal recent categories, e.g., a category with a majority of documents published subsequent to some pre-determined date—such as within the past month.

[0042] Method 300 may continue at process 308 by identifying recent and most related categories (for example, first categories most related to second categories) using, for example, contingency table 500. “Recent” may defined as desired—for example, as more recent than 5 years, more recent than 1 year, more recent than 3 months, or the like. Similarly, “most related” may be defined as deemed appropriate, using the distance of nearest neighbor methodologies, for example, cosine distance in the feature space, as a measure of most closely related; or, for example, using a statistical correlation or likelihood value from the contingency table C₀ (e.g., contingency table 500) as a different measure of “most related”.

[0043] In addition to identifying categories of interest (e.g., recent or most related), method 300 may also identify a document of interest in a particular category. For example, a document of interest might be one that typifies the category in the sense of being an “average” document. Such an average may be defined, for example, as a centroid of the category using the distance of a nearest neighbor methodology, e.g., cosine distance in the feature space. There may not actually be a “typical” or “average” document that matches the centroid, so the document of interest may be identified, for example, as the document closest to the centroid in the feature space. As an alternative example, the documents of interest may be identified as any documents within a pre-specified distance of the centroid in the feature space. Such a criterion may provide a mathematical definition of the category, and the document of interest may be said to be the document that most nearly matches the mathematical definition of the category. In the same sense, a document of interest may be said to be a document that fits the category model well, or that is a “typical” document within the category, i.e., representative of documents within the category.

[0044] At process 309, method 300 may repeat processes 304-308 by using different structured fields, features, or other information to compare the document sets in various ways. In other words, by iterating processes 304-308, multiple comparisons between all the different categories and between different types of categories (e.g., first categories and second categories) may be obtained.

[0045] The invention can take the form of an entirely hardware embodiment, an entirely software embodiment or an embodiment containing both hardware and software elements. In a preferred embodiment, the invention is implemented in software, which includes but is not limited to firmware, resident software, microcode, etc.

[0046] Furthermore, the invention can take the form of a computer program product accessible from a computer-usable or computer-readable medium providing program code for use by or in connection with a computer or any instruction execution system. For the purposes of this description, a computer-usable or computer readable medium can be any apparatus that can contain, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.

[0047] The medium can be an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system (or apparatus or device) or a propagation medium. Examples of a computer-readable medium include a semiconductor or solid state memory, magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk and an optical disk. Current examples of optical disks include compact disk-read only memory (CD-ROM), compact disk-read/write (CD-R/W) and DVD.

[0048] A data processing system suitable for storing and/or executing program code will include at least one processor coupled directly or indirectly to memory elements through a system bus. The memory elements can include local memory employed during actual execution of the program code, bulk storage, and cache memories which provide temporary storage of at least some program code in order to reduce the number of times code must be retrieved from bulk storage during execution.

[0049] Input/output or I/O devices (including but not limited to keyboards, displays, pointing devices, etc.) can be coupled to the system either directly or through intervening I/O controllers. Network adapters may also be coupled to the system to enable the data processing system to become coupled to other data processing systems or remote printers or storage devices through intervening private or public networks. Modems, cable modem and Ethernet cards are just a few of the currently available types of network adapters.

[0050] It should be understood, of course, that the foregoing relates to exemplary embodiments of the invention and that modifications may be made without departing from the spirit and scope of the invention as set forth in the following claims.