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

• US 20040111438A1
• Filed: 12/04/2002
• Published: 06/10/2004
• Est. Priority Date: 12/04/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Krishnapuram, Raghuram, Chitrapura, Krishna Prasad, Joshi, Sachindra
• Granted Patent: US 7,320,000 B2
• Time in Patent Office: Days
• US Class Current: 707/200
• 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

Disclosed are 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 (such as yahoo), 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 method for automating classification of a new data item when adding the new data item to an hierarchically organized;

set of classified data items, wherein nodes of the hierarchy correspond to classes of data items, the method comprising the steps of;

for a new data item requiring classification within the set of classified data items, identifying classification attributes of the new data item by reference to a set of classification attributes for the set of classified data items;

calculating a conditional value representative of the randomness of distribution of classification attributes for data items within the set of classified data items, which value is conditional on the new data item being added to a first class at a particular level of the hierarchy, and repeating the step of calculating a conditional value for each sibling class of the first class at said particular level of the hierarchy wherein said conditional values are each conditional on adding the new data item to a different respective one of said sibling classes at said particular level of the hierarchy;

comparing the conditional values to identify the lowest conditional value; and

selecting the class having the lowest conditional value for classifying the new data item.

2. A method according to claim 1, further comprising the steps of:

responsive to a first selected class being a parent class of one or more immediate descendant classes, repeating the steps of calculating said conditional values, comparing the conditional values and selecting a class, for the set of immediate descendant classes of the first selected class, thereby to select a class at the level of the hierarchy of said immediate descendant classes.

3. A method according to claim 2, wherein the steps of calculating, comparing and selecting are repeated for all descendant levels of the hierarchy until a class is selected at a leaf node of the hierarchy, and then classifying the new data item within the selected leaf node class.

4. A method according to claim 2, wherein the classification method ends by selecting a non-leaf node of the hierarchy in response to said comparison step determining that the selected non-leaf node has a calculated conditional value within a predefined threshold of the calculated conditional value of a sibling node of the non-leaf node.

5. A method according to claim 2, wherein the classification method ends by selecting a non-leaf node of the hierarchy in response to said comparison step determining that the calculated conditional values of child nodes of the non-leaf node are within a predefined threshold of each other.

6. A method according to claim 2, further comprising the step of:

comparing the calculated conditional value for the first selected class with the calculated conditional value for a selected one of the immediate descendant classes of the first selected class, and classifying the new data item within the first selected class in response to determining that the calculated conditional value for the first selected class is lower than the calculated conditional value for the selected descendant class.

7. A method according to claim 1, further comprising a preliminary step of creating a set of classification attributes for the set of classified data items, such that each data item in the set may be classified by reference to classification attributes of the data item and classification attributes of classes of data items in the hierarchy.

8. A method according to claim 7, for classifying a document within an hierarchically organized set of classified documents, wherein the classification attributes within the set comprise class labels for a set of document classes and words extracted from within the documents of the hierarchically organized set of documents.

9. A method according to claim 8, wherein the set of classification attributes is modified to include only the subset of words selected according to a feature selection criterion.

10. A method according to claim 9, wherein the subset of words comprise the words which each appear at least a predefined number of times within the set of classified documents.

11. A method according to claim 1, further comprising the steps, prior to calculating said conditional values, of modelling the hierarchically organized set of classified data items by:

calculating a probability distribution for the classification attributes of the set of classified data items;

calculating an initial value representative of the randomness of distribution of classification attributes for data items within the set of classified data items; and

storing said initial value for subsequent comparison with calculated conditional values.

12. A method according to claim 11, wherein the step of calculating the initial value comprises the steps of calculating a value representative of the initial randomness of distribution of classification attributes for each class of data items, applying a respective weighting to the calculated randomness value for each class which weighting corresponds to the respective probability of the class, and calculating the sum of the weighted randomness values.

13. A method according to claim 12, wherein the step of calculating a conditional value for the first class comprises the steps of:

(a) calculating a conditional value representative of the randomness of distribution of classification attributes within the parent class of the first class, conditional on the new data item being added to the first class;

(b) retrieving from storage initial calculated values representative of the initial randomness value for said first class and for each class other than said parent class;

(c) applying a respective weighting to the calculated and retrieved values of steps (a) and (b), which weighting corresponds to the probability of the respective class; and

(d) calculating the sum of the weighted randomness values.

14. A method according to claim 11, further comprising the step of:

responsive to a comparison between the stored initial value and the lowest calculated conditional value determining that the difference between the compared values is higher than a defined theshold, creating a new class within the hierarchy for classifying the new data item.

15. A method according to claim 1, further comprising the step of:

requesting user confirmation of a class selection in response to said comparison step determining that a difference between the lowest calculated conditional value and another calculated conditional value for sibling classes is less than a defined threshold.

16. A method according to claim 1, wherein the hierarchy of classified data items comprises an hierarchical directory for use in retrieval of classified data items within the set.

17. A method according to claim 1, implemented on a directory server computer having communication access to data storage in which said hierarchical directory is stored, and having communication access to one or more data processing systems in which said set of classified data items is stored.

18. A method for automating classification of a new data item when adding the new data item to an hierarchical set of classified data items in which each data item of the hierarchical set is associated with a specific class of data items, the class corresponding to a specific node of the hierarchy, the method comprising the steps of:

creating a set of classification attributes for the set of classified data items, such that each data item in the set may be classified by reference to classification attributes of the data item and classification attributes of classes of data items in the hierarchy;

for a new data item requiring classification within the set of classified data items, identifying classification attributes of the new data item by reference to the set of classification attributes;

calculating a conditional value representative of the randomness of distribution of classification attributes for data items within the set of classified data items, which value is conditional on the new data item being added to a first class at a particular level of the hierarchy, and repeating the step of calculating a conditional value for each sibling class of the first class at said particular level of the hierarchy wherein said conditional values are each conditional on adding the new data item to a different respective one of said sibling classes at said particular level of the hierarchy;

comparing the conditional values to identify the lowest conditional value; and

selecting the class having the lowest conditional value for classifying the new data item.

19. A method for verifying the classification of a current data item within an hierarchical set of classified data items, wherein nodes of the hierarchy correspond to classes of data items and data items within the classes each have one or more classification attributes, and wherein the current item has been classified within a first class corresponding to a node within the hierarchical set of classified data items, the method comprising the steps of:

calculating an initial value representative of the randomness of distribution of classification attributes for the set of classified data items;

calculating a conditional value representative of the randomness of distribution of classification attributes for data items within the set of classified data items, which value is conditional on the current data item being classified within a respective one of the set of sibling classes of the first class as an alternative to the first class, wherein sibling classes comprise the set of immediate descendant classes of a common ancestor class in the hierarchy;

repeating the step of calculating a conditional value respectively for any other ones of said sibling classes, wherein said conditional values are each conditional on classifying the current data item within a different respective one of said sibling classes; and

checking whether the initial value representative of the randomness of distribution of classification attributes is a lower value than each of the conditional values.

20. 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 automated classification of a new data item within an hierarchically organized set of classified data items in which nodes of the hierarchy correspond to classes of data items, wherein the program code comprises:

program code for identifying classification attributes of a new data item which requires classification within the set of data items, by reference to a set of classification attributes for the set of classified data items;

program code for calculating a conditional value representative of the randomness of distribution of classification attributes for data items within the set of classified data items, which value is conditional on the new data item being added to a first class at a particular level of the hierarchy, and repeating the step of calculating a conditional value for each sibling class of the first class at said particular level of the hierarchy wherein said conditional values are each conditional on adding the new data item to a different respective one of said sibling classes at said particular level of the hierarchy;

program code for comparing the conditional values to identify the lowest conditional value; and

program code for selecting the class having the lowest conditional value for classifying the new data item.

21. A data processing apparatus comprising:

storage means, for storing a set of data items and information defining an hierarchical organization of the set of data items within classes, wherein nodes of the hierarchy correspond to classes of data items;

storage means for storing a set of classification attributes for the set of data items;

means for identifying classification attributes of a new data item which requires classification within the set of data items, by reference to a set of classification attributes for the set of data items;

means for calculating a conditional value representative of the randomness of distribution of classification attributes for data items within the set of data items, which value is conditional on the new data item being added to a first class at a particular level of the hierarchy, and repeating the step of calculating a conditional value for each sibling class of the first class at said particular level of the hierarchy wherein said conditional values are each conditional on adding the new data item to a different respective one of is said sibling classes at said particular level of the hierarchy;

means for comparing the conditional values to identify the lowest conditional value; and

means for selecting the class having the lowest conditional value for classifying the new data item.

22. A directory server computer comprising:

storage means for storing a set of data items and information defining an hierarchical organization of the set of data items within classes, wherein nodes of the hierarchy correspond to classes of data items;

storage means for storing a set of classification attributes for the set of data items;

means for identifying classification attributes of a new data item which requires classification within the set of data items, by reference to a set of classification attributes for the set of data items;

means, for calculating a conditional value representative of the randomness of distribution of classification attributes for data items within the set of data items, which value is conditional on the new data item being added to a first class at a particular level of the hierarchy, and repeating the step of calculating a conditional value for each sibling class of the first class at said particular level of the hierarchy wherein said conditional values are each conditional on adding the new data item to a different respective one of said sibling classes at said particular level of the hierarchy;

means for comparing the conditional values to identify the lowest conditional value; and

means for selecting the class having the lowest conditional value for classifying the new data item.

23. An automated classifier for classifying a new data item when adding the new data item to an hierarchically organized set of classified data items in which nodes of the hierarchy correspond to classes of data items, the classifier comprising:

means for identifying classification attributes of a new data item which requires classification within the set of data items, by reference to a set of classification attributes for the set of classified data items;

means for calculating a conditional value representative of the randomness of distribution of classification attributes for data items within the set of classified data items, which value is conditional on the new data item being added to a first class at a particular level of the hierarchy, and repeating the step of calculating a conditional value for each sibling class of the first class at said particular level of the hierarchy wherein said conditional values are each conditional on adding the new data item to a different respective one of said sibling classes at said particular level of the hierarchy;

means for comparing the conditional values to identify the lowest conditional value; and

means for selecting the class having the lowest conditional value for classifying the new data item.