SYSTEM AND METHOD FOR ENTITY EXTRACTION FROM SEMI-STRUCTURED TEXT DOCUMENTS

• US 20170300565A1
• Filed: 04/14/2016
• Published: 10/19/2017
• Est. Priority Date: 04/14/2016
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Calapodescu, Ioan, Guerin, Nicolas, Jacques, Fanchon
• Granted Patent: US 10,489,439 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

A method for extracting entities from a text document includes, for at least a section of a text document, providing a first set of entities extracted from the at least a section, clustering at least a subset of the extracted entities in the first set into clusters, based on locations of the entities in the document. Complete ones of the clusters of entities are identified. Patterns for extracting new entities are learned based on the complete clusters. New entities are extracted from incomplete clusters based on the learned patterns.

Claims

1. A method for extracting entities from a text document comprising:

for at least a section of a text document,

providing a first set of entities extracted from the at least a section;

clustering at least a subset of the extracted entities in the first set into clusters, based on locations of the entities in the document;

identifying complete clusters of entities from the clusters;

learning patterns for extracting new entities based on the complete clusters; and

extracting new entities from incomplete clusters based on the learned patterns,

wherein at least one of the providing of the first set of entities, identifying complete clusters, learning patterns and extracting new entities is performed with a processor device.

2. The method of claim 1, wherein the text document is a resume.

3. The method of claim 1, further comprising segmenting the document into sections and performing the extracting of entities, identifying complete clusters, learning patterns and extracting new entities for one of the sections.

4. The method of claim 1, when the extraction of the first set of entities comprises at least one of a rule-based extraction method and a probabilistic extraction method.

5. The method of claim 1, wherein the extraction of the first set of entities includes accessing a lexicon of entities to identify text sequences in the section which each match a respective entity in the lexicon.

6. The method of claim 1, wherein the extracted entities are each labeled with an entity class from a plurality of entity classes.

7. The method of claim 1, wherein the clustering includes ordering the extracted entities based on their locations in the document, initializing a cluster with a first of the ordered entities, adding a next entity to the first cluster if the distance to a representative location in the cluster is less than a threshold distance, and recomputing the cluster representative location, otherwise if the distance is greater than the threshold, initializing a next cluster.

8. The method of claim 1, wherein the identifying complete clusters of entities from the clusters includes identifying clusters which include at least a threshold set of entities.

9. The method of claim 8, wherein the threshold set is determined by identifying correlations between entities of different types occurring in a set of documents or document sections.

10. The method of claim 1, wherein the learning patterns comprises training a CRF model based on the complete clusters and the extracting new entities based on the learned patterns comprises predicting new entities in incomplete clusters based on the trained CRF model.

11. The method of claim 1, wherein the learning patterns comprises, for each of the clusters in the set of complete clusters, for a window of text which includes the cluster, chunking the text using a set of rules to generate a sequence of chunks and extracting features of the chunks in the sequence, the features being used to learn the patterns.

12. The method of claim 1, further comprising, after extracting new entities based on the learned patterns, identifying new complete clusters which include the new entities and repeating the learning of patterns and extracting the new entities with the new complete clusters.

13. The method of claim 1, further comprising, after extracting new entities based on the learned patterns, if incomplete clusters remain, applying at least one of:

a) a back-off model trained on information extracted from other documents, and

b) pseudo-relevance feedback,

to identify additional new entities.

14. The method of claim 13, wherein the back-off model is a CRF model.

15. The method of claim 1, further comprising outputting the extracted new entities or information based thereon.

16. A computer program product comprising a non-transitory storage medium storing instructions, which when executed on a computer, causes the computer to perform the method of claim 1.

17. A system comprising memory which stores instructions for performing the method of claim 1 and a processor in communication with the memory for executing the instructions.

18. A system for extracting entities from text documents comprising:

a first entity extraction component for providing a first set of entities extracted from at least a section of a text document;

a second entity extraction component for extraction of new entities from the at least the section of the text document, the second entity extraction component comprising;

a clustering component for clustering at least a subset of the extracted entities in the first set into clusters, based on locations of the entities in the document,

a cluster completeness component for identifying complete clusters of entities from the clusters, and

a pattern recognition component for learning patterns for extracting new entities based on the complete clusters and extracting new entities from incomplete clusters based on the learned patterns; and

a processor for implementing at least the second entity extraction component.

19. The system of claim 18, further comprising at least one of:

a segmentation component for segmenting the document into sections;

a chunking component which for each of the clusters in the set of complete clusters, for a window of text which includes the cluster, chunks the text using a set of rules to generate a sequence of chunks and extracting features of the chunks in the sequence, the features being used to learn the patterns; and

an output component which outputs the extracted new entities or information based thereon.

20. A method for extracting entities from a resume comprising:

segmenting the resume into sections;

extracting a first set of entities and respective entity class labels from the section with at least one of grammar rules, a probabilistic model, and a lexicon;

clustering at least a subset of the extracted entities in the first set into clusters, based on locations of the entities in the resume;

identifying complete clusters of entities from the clusters;

learning patterns for extracting new entities based on the labels of the entities in the complete clusters;

extracting new entities from incomplete clusters based on the learned patterns; and

;

outputting information based on the extracted new entities in the resume,

wherein at least one of the segmenting, extracting the first set of entities, clustering, identifying complete clusters, learning patterns, and extracting new entities is performed with a processor device.