Class description generation for clustering and categorization

• US 7,813,919 B2
• Filed: 12/20/2005
• Issued: 10/12/2010
• Est. Priority Date: 12/20/2005
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Goutte, Cyril
• Primary Examiner(s): Sked; Matthew J
• Application Number:
  US11/312,764
• Publication Number:
  US 20070143101A1
• Time in Patent Office: 1,757 Days
• Field of Search: None
• US Class Current: 704/9
• CPC Class Codes: G06F 16/35 Clustering; Classification

Abstract

A class is to be characterized of a probabilistic classifier or clustering system that includes probabilistic model parameters. For each of a plurality of candidate words or word combinations, divergence of the class from other classes is computed based on one or more probabilistic model parameters profiling the candidate word or word combination. One or more words or word combinations are selected for characterizing the class as those candidate words or word combinations for which the class has substantial computed divergence from the other classes.

Claims

1. A method for characterizing a class of a probabilistic classifier or clustering system that classifies or clusters documents into classes and includes probabilistic model parameters, the method comprising:

for each of a plurality of candidate words or word combinations wherein the candidate words or word combinations include natural language phrases, computing a divergence element of the class from each of a plurality of other classes of the probabilistic classifier or clustering system based on one or more probabilistic model parameters profiling the candidate word or word combination; and

selecting one or more words or word combinations including at least one natural language phrase for characterizing the class as those candidate words or word combinations for which the class has a substantial computed divergence element from at least one of the plurality of other classes of the probabilistic classifier or clustering system that is effective for distinguishing the class from at least one of the plurality of other classes; and

labeling the class based on the selected one or more words or word combinations, the labeling including constructing a semantic description of the class based on the at least one selected natural language phrase;

wherein the computing a divergence operation and the selecting operation and the labeling operation are performed by a digital processor.

2. The method as set forth in claim 1, wherein the computing of divergence elements comprises:

computing a Kulback-Leibler divergence element of the class from each of the plurality of other classes of the probabilistic classifier or clustering system.

3. The method as set forth in claim 1, wherein the candidate words or word combinations include training documents.

4. The method as set forth in claim 1, wherein the natural language phrases include noun phrases.

5. The method as set forth in claim 1, wherein the candidate words or word combinations further include sentences.

6. The method as set forth in claim 5, wherein the selecting comprises:

performing a multi-document summarization ranking of the candidate natural language phrases or sentences based on the computed divergences.

7. The method as set forth in claim 1, wherein:

the computing of a divergence element of the class from each of the other classes is repeated for each class of the probabilistic classifier or clustering system to generate a matrix of divergence elements for each candidate word or word combination, and

the selecting comprises selecting a plurality of word or word combinations for differentiating classes of the probabilistic classifier or clustering system, the selecting being based on the generated matrices of divergence elements.

8. A storage medium storing instructions which when executed by a digital processor perform a method for characterizing classes of a probabilistic classifier or clustering system including (i) computing divergences of classes from other classes respective to candidate phrases based on probabilistic model parameters of the probabilistic classifier or clustering system, and (ii) characterizing classes using candidate phrases that provide substantial computed divergence from other classes effective for distinguishing the class from other classes, wherein the divergences computing (i) includes:

computing a word-based divergence based on one or more probabilistic model parameters of the probabilistic classifier or clustering system that profile one or more words of the candidate phrase,

computing a phrase-based divergence based on one or more probabilistic model parameters of the probabilistic classifier or clustering system that profile training documents containing the candidate phrase, and

combining the word-based divergence and the phrase-based divergence to determine the divergence.

9. The storage medium as set forth in claim 8, wherein the method performed by the instructions when executed by a digital processor further includes (iii) deriving the candidate phrases by natural language processing of training documents used to train the probabilistic classifier or clustering system.

10. The storage medium as set forth in claim 8, wherein the candidate phrases include noun phrases.

11. The storage medium as set forth in claim 8, wherein the characterizing (ii) includes performing a multi-document summarization ranking of the candidate phrases based on the computed divergences.

12. A method for characterizing a class of a probabilistic classifier or clustering system that classifies or clusters documents into classes and includes probabilistic model parameters, the method comprising:

for each of a plurality of candidate words or word combinations, computing a divergence element of the class from each of a plurality of other classes of the probabilistic classifier or clustering system based on one or more probabilistic model parameters profiling the candidate word or word combination; and

selecting one or more words or word combinations for characterizing the class as those candidate words or word combinations for which the class has a substantial computed divergence element from at least one of the plurality of other classes of the probabilistic classifier or clustering system that is effective for distinguishing the class from at least one of the plurality of other classes; and

labeling the class based on the selected one or more words or word combinations;

wherein the computing a divergence operation and the selecting operation and the labeling operation are performed by a digital processor.