Scalable set oriented classifier

• US 5,899,992 A
• Filed: 02/14/1997
• Issued: 05/04/1999
• Est. Priority Date: 02/14/1997
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wang, Min, Iyer, Balakrishna Raghavendra
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/800,357
• Time in Patent Office: 809 Days
• Field of Search: 707/1, 707/5, 707/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method, apparatus, and article of manufacture for a computer implemented scaleable set-oriented classifier. The scalable set-oriented classifier stores set-oriented data as a table in a relational database. The table is comprised of rows having attributes. The scalable set-oriented classifier classifies the rows by building a classification tree. The scalable set-oriented classifier determines a gini index value for each split value of each attribute for each node that can be partitioned in the classification tree. The scalable set-oriented classifier selects an attribute and a split value for each node that can be partitioned based on the determined gini index value corresponding to the split value. Then, the scalable set-oriented classifier grows the classification tree by another level based on the selected attribute and split value for each node. The scalable set-oriented classifier repeats this process until each row of the table has been classified in the classification tree.

Claims

1. A method for classifying set-oriented data in a computer by generating a classification tree, the computer being coupled to a data storage device for storing the set-oriented data, the method comprising the steps of:

storing the set-oriented data as a table in a relational database in the data storage device coupled to the computer, the table being comprised of rows having attributes and node identifiers, wherein each node identifier indicates a node in the classification tree to which a row belongs;

iteratively performing a sequence of steps in the computer until all of the rows have been classified, the sequence of steps comprising;

determining a gini index value for each split value of each attribute for each node that can be partitioned in the classification tree;

selecting an attribute and a split value for each node that can be partitioned based on the determined gini index value corresponding to the split value of the attribute; and

growing the classification tree by a new level based on the selected attribute and split value for each node that can be partitioned, further comprising;

using the node identifier associated with a row to locate a node in the classification tree;

identifying the selected split value for that node;

applying the split value to the row; and

updating the node identifier according to the result of the split test.

2. The method of claim 1 wherein the step of determining a gini index value further comprises the step of creating an attribute table for each attribute.

3. The method of claim 1 wherein the step of determining a gini index value further comprises the step of collecting distribution information for each attribute.

4. The method of claim 3 wherein each row has an associated class and wherein the step of collecting distribution information for each attribute further comprises the step of obtaining classification information for each class of each attribute.

5. The method of claim 1 wherein the step of selecting an attribute and a split value further comprises the step of selecting the split value of the attribute with a lowest gini index value.

6. The method of claim 1 further comprising providing a leaf node list in a memory coupled to the computer, the leaf node list having one or more entries, each entry associating a node of the classification tree with a row in the table.

7. The method of claim 6 wherein the step of growing the classification tree further comprises updating the leaf node list.

8. An apparatus for classifying set-oriented data, comprising:

a computer coupled to a data storage device for storing the set-oriented data;

means, performed by the computer, for storing the set-oriented data as a table in a relational database in the data storage device coupled to the computer, the table being comprised of rows having attributes and node identifiers, wherein each node identifier indicates a node in the classification tree to which a row belongs; and

means, performed by the computer, for performing a sequence of steps in the computer until all of the rows of the table have been classified in a classification tree, further comprising;

means, performed by the computer, for determining a gini index value for each split value of each attribute for each node that can be partitioned in the classification tree;

means, performed by the computer, for selecting an attribute and a split value for the attribute for each node that can be partitioned based on the determined gini index value corresponding to the split value of the attribute; and

means, performed by the computer, for growing the classification tree by a new level based on the selected attribute and split value for each node that can be partitioned, further comprising;

means, performed by the computer, for using the node identifier associated with a row to locate a node in the classification tree;

means, performed by the computer, for identifying the selected split value for that node;

means, performed by the computer, for applying the split value to the row; and

means, performed by the computer, for updating the node identifier according to the result of the split test.

9. The apparatus of claim 8 wherein the means for determining a gini index value further comprises means for creating an attribute table for each attribute.

10. The apparatus of claim 8 wherein the means for determining a gini index value further comprises means for collecting distribution information for each attribute.

11. The apparatus of claim 10 wherein each row has an associated class and wherein the means for collecting distribution information for each attribute further comprises means for obtaining classification information for each class of each attribute.

12. The apparatus of claim 8 wherein the means for selecting an attribute and a split value further comprises means for selecting the split value of the attribute with a lowest gini index value.

13. The apparatus of claim 8 further comprising means for providing a leaf node list in a memory coupled to the computer, the leaf node list having one or more entries, each entry associating a node of the classification tree with a row in the table.

14. The apparatus of claim 13 wherein the means for growing the classification tree further comprises means for updating the leaf node list.

15. A program storage device, readable by a computer, tangibly embodying one or more programs of instructions executable by the computer to perform method steps of a classification method for classifying set-oriented data by generating a classification tree, the computer the computer being coupled to a data storage device for storing the set-oriented data, the method comprising the steps of:

storing the set-oriented data as a table in a relational database in the data storage device coupled to the computer, the table being comprised of rows having attributes and node identifiers, wherein each node identifier indicates a node in the classification tree to which a row belongs; and

iteratively performing a sequence of steps in the computer until all of the rows have been classified, the sequence of steps comprising;

determining a gini index value for each split value of each attribute for each node that can be partitioned in the classification tree;

selecting an attribute and a split value for each node that can be partitioned based on the determined gini index value corresponding to the split value of the attribute; and

growing the classification tree by a new level based on the selected attribute and split value for each node that can be partitioned, further comprising;

using the node identifier associated with a row to locate a node in the classification tree;

identifying the selected split value for that node;

applying the split value to the row; and

updating the node identifier according to the result of the split test.

16. The program storage device of claim 15 wherein the step of determining a gini index value further comprises the step of creating an attribute table for each attribute.

17. The program storage device of claim 15 wherein the step of determining a gini index value further comprises the step of collecting distribution information for each attribute.

18. The program storage device of claim 17 wherein each row has an associated class and wherein the step of collecting distribution information for each attribute further comprises the step of obtaining classification information for each class of each attribute.

19. The program storage device of claim 15 wherein the step of selecting an attribute and a split value further comprises the step of selecting the split value of the attribute with a lowest gini index value.

20. The program storage device of claim 15 further comprising providing a leaf node list in a memory coupled to the computer, the leaf node list having one or more entries, each entry associating a node of the classification tree with a row in the table.

21. The program storage device of claim 20 wherein the step of growing the classification tree further comprises updating the leaf node list.