Clique based clustering for named entity recognition system

• US 20100004925A1
• Filed: 07/03/2008
• Published: 01/07/2010
• Est. Priority Date: 07/03/2008
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Jacquet, Guillaume, Ah-Pine, Julien
• Granted Patent: US 8,275,608 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 40/169 Annotation, e.g. comment data or footnotes
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

A soft clustering method comprises (i) grouping items into non-exclusive cliques based on features associated with the items, and (ii) clustering the non-exclusive cliques using a hard clustering algorithm to generate item groups on the basis of mutual similarity of the features of the items constituting the cliques. In some named entity recognition embodiments illustrated herein as examples, named entities together with contexts are grouped into cliques based on mutual context similarity. Each clique includes a plurality of different named entities having mutual context similarity. The cliques are clustered to generate named entity groups on the basis of mutual similarity of the contexts of the named entities constituting the cliques.

Claims

1. An annotation method comprising:

identifying named entities in a corpus together with contexts;

grouping the named entities into cliques based on mutual context similarity, each clique including a plurality of different named entities having mutual context similarity, the grouping of the named entities into cliques being non-exclusive;

clustering the cliques to generate named entity groups on the basis of mutual similarity of the contexts of the named entities constituting the cliques;

assigning annotations to the named entity groups; and

annotating named entity instances in the corpus based on the named entity groups and corresponding assigned annotations.

2. The annotation method as set forth in claim 1, wherein the clustering comprises hard clustering.

3. The annotation method as set forth in claim 2, wherein the grouping into cliques does not employ a predetermined number of cliques, and the hard clustering does not employ a predetermined number of groups.

4. The annotation method as set forth in claim 2, wherein the hard clustering employs a relational analysis-based clustering algorithm.

5. The annotation method as set forth in claim 4, further comprising:

generating an initial ordering of cliques for use in the relational analysis-based clustering algorithm, the initial ordering of cliques inputting to the relational analysis-based clustering algorithm (1) cliques that are generally dissimilar from other cliques before (2) cliques that are similar to a substantial number of other cliques.

6. The annotation method as set forth in claim 1, wherein the assigning of annotations to the named entity groups comprises:

automatically assigning an annotation to at least one of the named entity groups based on the contexts of the named entities constituting said at least one of the named entity groups.

7. The annotation method as set forth in claim 1, wherein the annotating of named entity instances comprises:

annotating those named entity instances of the corpus or input object for which the named entity belongs to a single named entity group with the annotation assigned to said single named entity group.

8. The annotation method as set forth in claim 7, wherein the annotating further comprises:

annotating a named entity instance of the corpus or input object for which the named entity belongs to more than one named entity group with the annotation assigned to the named entity group whose constituent named entities have context most similar to the context of the named entity instance of the corpus or input object.

9. An annotation system comprising:

a named entity detector configured to identify named entities in a corpus together with contexts;

a cliques identifier configured to receive and group the named entities into cliques based on mutual context similarity, each clique including a plurality of different named entities having mutual context similarity; and

a cliques clusterer configured to receive and cluster the cliques to generate named entity groups on the basis of mutual similarity of the contexts of the named entities constituting the cliques.

10. The annotation system as set forth in claim 9, further comprising:

a group annotator configured to assign annotations to the named entity groups.

11. The annotation system as set forth in claim 10, further comprising:

a named entity instance annotator configured to annotate an instance of a named entity in the corpus or in an input document based on membership of the named entity in one or more named entity groups.

12. The annotation system as set forth in claim 10, wherein the group annotator automatically assigns an annotation to at least one of the named entity groups based on the contexts of the named entities constituting said at least one of the named entity groups.

13. The annotation system as set forth in claim 9, wherein the cliques identifier does not utilize a predetermined number of cliques, and the cliques clusterer does not utilize a predetermined number of groups.

14. The annotation system as set forth in claim 10, wherein the cliques clusterer utilizes a relational analysis-based hard clustering algorithm.

15. The annotation system as set forth in claim 14, wherein the cliques clusterer generates an initial ordering of cliques for use in the relational analysis-based hard clustering algorithm, the initial ordering of cliques inputting to the relational analysis-based hard clustering algorithm (1) cliques that are generally dissimilar from other cliques before (2) cliques that are similar to a substantial number of other cliques.

16. The annotation system as set forth in claim 9, wherein the cliques identifier comprises:

a similarity matrix generator configured to generate a similarity matrix having elements (i,j) indicative of pairwise similarity between named entities indexed by indices and j;

a binary adjacency matrix generator configured to convert the similarity matrix to a binary adjacency matrix having elements (i,j) indicative of whether named entities indexed by indices i and j are nearest neighbors; and

a cliques generator configured to group named entities into cliques based on nearest neighbor information provided by the binary adjacency matrix.

17. A storage medium storing instructions executable to perform a soft clustering method comprising (i) grouping items into non-exclusive cliques based on features associated with the items, and (ii) clustering the non-exclusive cliques using a hard clustering algorithm to generate item groups on the basis of mutual similarity of the features of the items constituting the cliques.

18. The storage medium as set forth in claim 17, wherein the items comprise named entities occurring in a corpus and the features associated with the items comprise contexts of occurrences of the named entities in the corpus, whereby the generated item groups comprise named entity groups.

19. The storage medium as set forth in claim 18, wherein the storage medium further stores instructions executable to annotate instances of named entities based on the named entity groups generated by the soft clustering method.

20. The storage medium as set forth in claim 17, wherein the hard clustering algorithm comprises a relational analysis-based hard clustering algorithm.

21. The storage medium as set forth in claim 17, wherein the grouping comprises (i)(a) generating a similarity matrix having elements (i,j) indicative of similarity of items indexed by indices i and j as measured by the features of the respective items, and (i)(b) grouping the items into non-exclusive cliques on the basis of similarities between items as indicated by the generated similarity matrix.