Method and system for extracting and visualizing graph-structured relations from unstructured text

• US 7,730,085 B2
• Filed: 11/08/2006
• Issued: 06/01/2010
• Est. Priority Date: 11/29/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hassan, Hany M., Mostafa, Hala
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Hocker; John P
• Application Number:
  US11/557,527
• Publication Number:
  US 20070124291A1
• Time in Patent Office: 1,301 Days
• Field of Search: 707 1- 10, 707/100, 707776-778
• US Class Current: 707/776
• CPC Class Codes: G06F 16/34 Browsing; Visualisation therefor

Abstract

The present invention is directed to a system, method and computer program for automatically extracting and mining relations and related entities from unstructured text. A method in accordance with an embodiment of the invention includes: extracting relations and related entities from unstructured text data, representing the extracted information into a graph, and manipulating the resulting graph to gain more insight into the information it contains. The extraction of relations and related entities is performed first by automatically inducting pattern and second by applying these induced patterns to unstructured text data. For each relation and entity, several features are extracted in order to build a graph whose nodes are entities and edges are relations.

Claims

1. A method for automatically extracting and mining relations and related entities from unstructured text, comprising:

Receiving a query specifying a main entity; and

Extracting, using a computer processing system, from unstructured text relations and related entities related to the main entity specified in the query, the extracting further comprising;

Searching and selecting in the unstructured text, documents containing the main entity;

Attaching to each word of the selected documents, at least one tag, each tag being of a different type;

extracting relations and related entities by applying patterns to the tagged documents, wherein the patterns are induced from unstructured text, the inducing comprising;

attaching to each word of an unstructured text, at least one tag of a different type;

defining at least one template, each template being based on a sequence of tags;

and Generating from each template, at least one pattern, each pattern specifying a role for each tag in the template;

Extracting from the selected documents features characterizing each entity and relation; and

building a graph based on the extracted features, whose nodes represent the entities related to the specified main entity and whose edges represent the relations between the entities, wherein building a graph based on the extracted features further comprises expanding the graph based on distances between nodes, the expanding further comprising selecting at least one expanded entity, close to the main entity, and extracting from the unstructured text, relations and related entities related to each expanded entity;

wherein extracting features characterizing each relation from the selected documents further comprises associating each relation with a relation class, a relation strength, and temporal information, and wherein building the graph further comprises indicating on the graph which of the entities are related at a given time based on the temporal information for each relation.

2. The method according to claim 1, further comprising:

manipulating the graph in order to gain more insight into information it contains.

3. The method according to claim 1, wherein attaching to each word of the selected documents, at least one tag, each tag being of a different type, further comprises:

applying syntax and semantic taggers on selected documents in order to extract named entities, lexical types, and semantics of words.

4. The method according claim 1, wherein manipulating the resulting graph in order to gain more insight into information it contains, further comprises:

receiving a graph query to obtain a specific representation of the related entities and relations according to certain criteria; and

in response to the graph query, generating an output graph representing the entities and their relations according to the criteria specified in the graph query.

5. The method according to claim 4, wherein the criteria are temporal criteria or are conditions and/or constrains related to at least one feature associated with the relations and related entities.

6. The method according to claim 1, wherein building a graph based on the extracted features, further comprises

associating each node representing an entity, with a vector based on the value of the features characterizing the relations and related entities.

7. The method according to claim 1, wherein the at least one feature characterizing an entity is derived from the context in which the entity frequently occurs in the selected documents containing the main entity.

8. The method according to claim 1, wherein the value associated with a feature characterizing an entity is based on a probability of occurrence of the feature with the associated entity.

9. The method according to claim 1, wherein building a graph based on the extracted features further comprises:

classifying relations in a predefined category according to a semantic meaning of the relation.

10. The method according to claim 1, wherein a tag is a part of speech tag, a named entity tag, a semantic tag, or a tag of any other type.

11. The method according to claim 1, wherein defining at least one template further comprises:

selecting an initial set of templates; and

filtering out unlikely templates from the initial set of templates.

12. The method according to claim 11, wherein generating from each template, at least one pattern, further comprises:

generating an initial set of patterns from the initial set of templates;

applying each pattern in the initial set of patterns to the unstructured text in order to obtain for each pattern, as many tuples as possible matching the pattern, a tuple being the result of the application of a pattern to unstructured text; and

identifying most informative patterns.

13. The method according to claim 12, wherein identifying most informative patterns further comprises:

running a Hypertext Induced Topic Selection (HITS) algorithm.

14. The method according to claim 1, wherein each pattern specifies for each tag in the template whether the tag is a first entity, a second entity, or a relation.

15. A system for automatically extracting and mining relations and related entities from unstructured text, comprising:

a computer processing system, including;

a system for receiving a query specifying a main entity; and

a system for extracting from unstructured text relations and related entities related to the main entity specified in the query, the system for extracting further comprising;

a system for searching and selecting in the unstructured text, documents containing the main entity;

a system for attaching to each word of the selected documents, at least one tag, each tag being of a different type;

a system for extracting relations and related entities by applying patterns to the tagged documents, the system for extracting relations and related entities comprising a system for inducing the patterns from unstructured text, the inducing comprising;

attaching to each word of an unstructured text, at least one tag of a different type;

defining at least one template, each template being based on a sequence of tags; and

generating from each template, at least one pattern, each pattern specifying a role for each tag in the template;

a system for extracting from the selected documents features characterizing each entity and relation; and

a system for building a graph based on the extracted features, whose nodes represent the entities related to the specified main entity and whose edges represent the relations between the entities, wherein the system for building a graph based on the extracted features further comprises a system for expanding the graph based on distances between nodes, the expanding of the graph based on distances between nodes further comprising selecting at least one expanded entity, close to the main entity, and extracting from the unstructured text, relations and related entities related to each expanded entity;

wherein the system for extracting features characterizing each relation from the selected documents further is configured to associate each relation with a relation class, a relation strength, and temporal information, and wherein the system for building the graph is configured to indicate on the graph which of the entities are related at a given time based on the temporal information for each relation.

16. A computer program stored on a computer readable medium for automatically extracting and mining relations and related entities from unstructured text, when the computer program is executed on a computer, the computer program comprising program code for:

receiving a query specifying a main entity; and

extracting from unstructured text relations and related entities related to the main entity specified in the query, the extracting further comprising;

searching and selecting in the unstructured text, documents containing the main entity;

attaching to each word of the selected documents, at least one tag, each tag being of a different type;

extracting relations and related entities by applying patterns to the tagged documents, wherein the patterns are induced from unstructured text, the inducing comprising;

attaching to each word of an unstructured text, at least one tag of a different type;

defining at least one template, each template being based on a sequence of tags; and

generating from each template, at least one pattern, each pattern specifying a role for each tag in the template;

extracting from the selected documents features characterizing each entity and relation; and

building a graph based on the extracted features, whose nodes represent the entities related to the specified main entity and whose edges represent the relations between the entities, wherein building a graph based on the extracted features further comprises expanding the graph based on distances between nodes, the expanding further comprising selecting at least one expanded entity, close to the main entity, and extracting from the unstructured text, relations and related entities related to each expanded entity;

wherein extracting features characterizing each relation from the selected documents further comprises associating each relation with a relation class, a relation strength, and temporal information, and wherein building the graph further comprises indicating on the graph which of the entities are related at a given time based on the temporal information for each relation.