US5899992A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Scalable set oriented classifier
Assignee: International Business Machines Corp
•
Filing: 1997-02-14
•
Granted: 1999-05-04
•
Expires: 2017-02-14
Abstract
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.
Inventors
- 👤 Balakrishna Raghavendra Iyer
- 👤 Min Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 21:33
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/35; G06F16/31; G06F16/316; G06F16/322; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99937
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
225 words
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.
Claim 2
Independent Claim
225 words
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.
Claim 3
Dependent Claim
26 words
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.
Claim 4
Dependent Claim
25 words
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.
Claim 5
Dependent Claim
37 words
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.
Claim 6
Dependent Claim
34 words
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.
Claim 7
Dependent Claim
43 words
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.
Claim 8
Dependent Claim
20 words
The method of claim 6 wherein the step of growing the classification tree further comprises updating the leaf node list.
Claim 9
Independent Claim
272 words
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.
Claim 10
Independent Claim
272 words
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.
Claim 11
Dependent Claim
25 words
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.
Claim 12
Dependent Claim
24 words
The apparatus of claim 8 wherein the means for determining a gini index value further comprises means for collecting distribution information for each attribute.
Claim 13
Dependent Claim
36 words
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.
Claim 14
Dependent Claim
33 words
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.
Claim 15
Dependent Claim
45 words
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.
Claim 16
Dependent Claim
22 words
The apparatus of claim 13 wherein the means for growing the classification tree further comprises means for updating the leaf node list.
Claim 17
Dependent Claim
251 words
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.
Claim 18
Dependent Claim
251 words
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.
Claim 19
Dependent Claim
28 words
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.
Claim 20
Dependent Claim
27 words
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.
Claim 21
Dependent Claim
39 words
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.
Claim 22
Dependent Claim
36 words
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.
Claim 23
Dependent Claim
45 words
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.
Claim 24
Dependent Claim
22 words
The program storage device of claim 20 wherein the step of growing the classification tree further comprises updating the leaf node list.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-05-03 | 2002-11-02 | 2003-05-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-05-03 | 2006-11-02 | 2007-05-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-05-03 | 2010-11-02 | 2011-05-04 | $7700.00 | Window Closed / Lapsed |