Method and apparatus for populating a predefined concept hierarchy or other hierarchical set of classified data items by minimizing system entrophy

• US 7,320,000 B2
• Filed: 12/04/2002
• Issued: 01/15/2008
• Est. Priority Date: 12/04/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Krishnapuram, Raghuram, Chitrapura, Krishna Prasad, Joshi, Sachindra
• Primary Examiner(s): Rodriguez; Paul
• Assistant Examiner(s): OSBORNE, LUKE R
• Application Number:
  US10/309,612
• Publication Number:
  US 20040111438A1
• Time in Patent Office: 1,868 Days
• Field of Search: 707/6, 707/104.1, 707/200, 707/1, 707/7, 706/20, 706/59, 706/14
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A system and method for automated populating of an existing concept hierarchy of items with new items, using entropy as a measure of the correctness of a potential classification. User-defined concept hierarchies include, for example, document hierarchies such as directories for the Internet, library catalogues, patent databases and journals, and product hierarchies. These concept hierarchies can be huge and are usually maintained manually. An internet directory may have, for example, millions of Web sites, thousands of editors and hundreds of thousands of different categories. The method for populating a concept hierarchy includes calculating conditional ‘entropy’ values representing the randomness of distribution of classification attributes for the hierarchical set of classes if a new item is added to specific classes of the hierarchy and then selecting whichever class has the minimum randomness of distribution when calculated as a condition of insertion of the new data item.

Claims

1. A computer-implemented method for automating classification of a new data item when adding the new data item to an hierarchically organized hierarchy set of classified data items, wherein nodes of the hierarchy set correspond to classes of data items, said method comprising:

inputting into a computer system classes of documents comprising (i) a collection of classified documents within a hierarchy of classes and (ii) class labels associated with said collection of classified documents;

training said computer system using said collection of classified documents, wherein the training process comprises;

selecting, from an input set of said collection of classified documents, a set of tokens for use as classification attributes; and

building a dictionary comprising said classification attributes;

modeling a distribution of said classification attributes across said classes of documents by using a set of random variables and values associated with said set of random variables to represent said classification attributes in said dictionary;

calculating an initial entropy value at every node of each level of said hierarchy of classes using said set of random variables;

inputting into said computer system a new data item to be classified into one of said classes in said hierarchy of classes;

calculating entropy values for each of a plurality of possible classes into which said new data item could be classified;

comparing the calculated entropy values with said initial entropy value at every node of each level of said hierarchy of classes in order to create a plurality of conditional entropy values;

selecting a class having a lowest conditional entropy value; and

classifying said new data item in the selected class.

2. The computer-implemented method of claim 1, wherein said classification attributes comprise all words within said each document, wherein said dictionary comprises a corpus of words within an entirety of said input set of said collection of classified documents, and wherein said training process further comprises retaining, in said dictionary, said words appearing at least a minimum number of times in a selected portion of said each document.

3. The computer-implemented method of claim 1, wherein the modeling process further comprises measuring probability distributions of said random variables.

4. The computer-implemented method of claim 3, wherein the measuring process comprises:

computing a probability distribution of said classification attributes across said classes; and

computing a probability distribution of said classes.

5. The computer-implemented method of claim 1, wherein the calculating of said initial entropy value comprises:

calculating an entropy separately for said classification attributes within each class;

calculating an overall entropy for said node, wherein said overall entropy comprises a weighted sum of entropies of individual classes and said classification attributes for said each class upon applying computed probabilities for said individual classes and said classification attributes for said each class.

6. The computer-implemented method of claim 1, wherein entropy comprises a value representative of a randomness of distribution of said classification attributes.

7. The computer-implemented method of claim 1, further comprising identifying classification attributes of said new data item based on classification attributes in said dictionary.

8. The computer-implemented method of claim 1, further comprising determining whether said selected class having said lowest conditional value for classifying said new data item is a correct class by comparing said selected class with a class having a next lowest conditional value, wherein a difference between said lowest conditional value and said next lowest conditional value being greater than a user-defined threshold is indicative of said selected class being said correct class.

9. A computer program product comprising program code recorded on a machine-readable recording medium, for controlling the operation of a data processing apparatus on which the program code executes to perform a method for automating classification of a new data item when adding the new data item to an hierarchically organized hierarchy set of classified data items, wherein nodes of the hierarchy set correspond to classes of data items, said method comprising:

inputting into a computer system classes of documents comprising (i) a collection of classified documents within a hierarchy of classes and (ii) class labels associated with said collection of classified documents;

training said computer system using said collection of classified documents, wherein the training process comprises;

selecting, from an input set of said collection of classified documents, a set of tokens for use as classification attributes; and

building a dictionary comprising said classification attributes;

modeling a distribution of said classification attributes across said classes of documents by using a set of random variables and values associated with said set of random variables to represent said classification attributes in said dictionary;

calculating an initial entropy value at every node of each level of said hierarchy of classes using said set of random variables;

inputting into said computer system a new data item to be classified into one of said classes in said hierarchy of classes;

calculating entropy values for each of a plurality of possible classes into which said new data item could be classified;

comparing the calculated entropy values with said initial entropy value at every node of each level of said hierarchy of classes in order to create a plurality of conditional entropy values;

selecting a class having a lowest conditional entropy value; and

classifying said new data item in the selected class.

10. The computer program product of claim 9, wherein said classification attributes comprise all words within said each document, wherein said dictionary comprises a corpus of words within an entirety of said input set of said collection of classified documents, and wherein said training process further comprises retaining, in said dictionary, said words appearing at least a minimum number of times in a selected portion of said each document.

11. The computer program product of claim 9, wherein in said method, the modeling process further comprises measuring probability distributions of said random variables.

12. The computer program product of claim 9, wherein in said method, the measuring process comprises:

computing a probability distribution of said classification attributes across said classes; and

computing a probability distribution of said classes.

13. The computer program product of claim 9, wherein in said method, the calculating of said initial entropy value comprises:

calculating an entropy separately for said classification attributes within each class;

calculating an overall entropy for said node, wherein said overall entropy comprises a weighted sum of entropies of individual classes and said classification attributes for said each class upon applying computed probabilities for said individual classes and said classification attributes for said each class.

14. The computer program product of claim 9, wherein entropy comprises a value reptesentative of a randomness of distribution of said classification attributes.

15. The computer program product of claim 9, wherein said method further comprises identifying classification attributes of said new data item based on classification attributes in said dictionary.

16. The computer program product of claim 9, wherein said method further comprises determining whether said selected class having said lowest conditional value for classifying said new data item is a correct class by comparing said selected class with a class having a next lowest conditional value, wherein a difference between said lowest conditional value and said next lowest conditional value being greater than a user-defined threshold is indicative of said selected class being said correct class.

17. A data processing apparatus for automating classification of a new data item when adding the new data item to an hierarchically organized hierarchy set of classified data items, wherein nodes of the hierarchy set correspond to classes of data items, said data processing apparatus comprising a microprocessor adapted to:

input into a computer system classes of documents comprising (i) a collection of classified documents within a hierarchy of classes and (ii) class labels associated with said collection of classified documents;

train said computer system using said collection of classified documents, wherein the training of said computer system comprises;

selecting, from an input set of said collection of classified documents, a set of tokens for use as classification attributes; and

building a dictionary comprising said classification attributes;

model a distribution of said classification attributes across said classes of documents by using a set of random variables and values associated with said set of random variables to represent said classification attributes in said dictionary;

calculate an initial entropy value at every node of each level of said hierarchy of classes using said set of random variables;

input into said computer system a new data item to be classified into one of said classes in said hierarchy of classes;

calculate entropy values for each of a plurality of possible classes into which said new data item could be classified;

compare the calculated entropy values with said initial entropy value at every node of each level of said hierarchy of classes in order to create a plurality of conditional entropy values;

select a class having a lowest conditional entropy value; and

classify said new data item in the selected class.

18. The data processing apparatus of claim 17, wherein said classification attributes comprise all words within said each document, wherein said dictionary comprises a corpus of words within an entirety of said input set of said collection of classified documents, and wherein said training process frrther comprises retaining, in said dictionary, said words appearing at least a minimum number of times in a selected portion of said each document.

19. The data processing apparatus of claim 17, wherein the modeling of the distribution of said classification attributes across said classes of documents further comprises measuring probability distributions of said random variables.

20. The data processing apparatus of claim 19, wherein the measuring process comprises:

computing a probability distribution of said classification attributes across said classes; and

computing a probability distribution of said classes.

21. The data processing apparatus of claim 17, wherein the calculation of said initial entropy value comprises:

calculating an entropy separately for said classification attributes within each class;

calculating an overall entropy for said node, wherein said overall entropy comprises a weighted sum of entropies of individual classes and said classification attributes for said each class upon applying computed probabilities for said individual classes and said classification attributes for said each class.

22. The data processing apparatus of claim 17, wherein entropy comprises a value representative of a randomness of distribution of said classification attributes.

23. The data processing apparatus of claim 17, wherein said microprocessor is further adapted to identify classification attributes of said new data item based on classification attributes in said dictionary.