Clique based clustering for named entity recognition system

• US 8,275,608 B2
• Filed: 07/03/2008
• Issued: 09/25/2012
• Est. Priority Date: 07/03/2008
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Ah-Pine, Julien, Jacquet, Guillaume
• Primary Examiner(s): Desir, Pierre-Louis
• Assistant Examiner(s): Sharma, Neeraj
• Application Number:
  US12/167,382
• Publication Number:
  US 20100004925A1
• Time in Patent Office: 1,545 Days
• Field of Search: 704/9, 704/10, 704/245
• 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 wherein the identifying of each named entity identifies the named entity as a noun or noun phrase starting with an upper-case letter;

grouping the named entities into cliques based on mutual context similarity, each clique including a plurality of different named entities each named entity being a noun or noun phrase starting with an upper-case letter, the named entities of each clique having mutual context similarity, the grouping of the named entities into cliques being non-exclusive in that a named entity can belong to more than one clique;

clustering the cliques to generate named entity groups each named entity group consisting of one or more cliques, the clustering being performed 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;

wherein at least the identifying, the grouping, and the clustering are performed by a computer.

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 wherein each named entity identified by the named entity detector is a noun or noun phrase starting with an upper-case letter;

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 each named entity being a noun or noun phrase starting with an upper-case letter, the named entities of each clique having mutual context similarity, the cliques being nonexclusive in that a named entity can belong to more than one clique;

and a cliques clusterer configured to receive and cluster the cliques to generate named entity groups each named entity group consisting of one or more cliques, the clustering being performed on the basis of mutual similarity of the contexts of the named entities constituting the cliques;

wherein the named entity detector, the cliques identifier, and the cliques clusterer comprise a digital processing device.

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 east 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 i 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.

21. The annotation system as set forth in claim 9, wherein the named entity detector identifies named entities in using the rule that a named entity is identified as a noun or noun phrase starting with an upper-case letter which is a rector argument of an attribute syntactic relation with a noun as rected argument or which is a rected argument of a modifier syntactic relation with a noun as a rector argument.

17. A non-transitory storage medium storing instructions executable to perform a soft clustering method comprising:

(i) Grouping items into non-exclusive cliques based on mutual context similarity, each clique including a plurality of different named entities each named entity being a noun or noun phrase starting with an upper-case letter, the named entities of each clique having mutual context similarity, the grouping of the named entities into cliques being non-exclusive in that a named entity can belong to more than one clique,

and (ii) Clustering the non-exclusive cliques using a hard clustering algorithm to generate named entity groups each named entity group consisting of one or more cliques, the clustering being performed on the basis of mutual similarity of the contexts of the named entities constituting the cliques.

18. The non-transitory storage medium as set forth in claim 17, 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.

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

20. The non-transitory 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.