METHOD AND SYSTEM FOR EXTRACTING AND VISUALIZING GRAPH-STRUCTURED RELATIONS FROM UNSTRUCTURED TEXT

• US 20070124291A1
• Filed: 11/08/2006
• Published: 05/31/2007
• Est. Priority Date: 11/29/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mostafa, Hala, Hassan, Hany
• Granted Patent: US 7,730,085 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 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;

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.

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 extracting from the selected documents, features characterizing each relation, further comprises:

associating each relation with at least one of;

a relation class;

a relation strength; and

a temporal information;

and wherein generating an output graph further comprises;

visualizing on the graph the at least one of;

the relation class;

the relation strength; and

the temporal information.

10. 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.

11. The method according to claim 1, 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.

12. The method according to claim 1, comprising:

inducing patterns from unstructured text, the inducing further 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.

13. 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.

14. The method according to claim 12, 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.

15. The method according to claim 14, 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.

16. The method according to claim 15, wherein identifying most informative patterns further comprises:

running a Hypertext Induced Topic Selection (HITS) algorithm.

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

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

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;

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.

19. 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;

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.