US6247016B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Decision tree classifier with integrated building and pruning phases
Assignee: WSOU Investments LLC
•
Filing: 1998-11-10
•
Granted: 2001-06-12
•
Expires: 2018-11-10
Abstract
Abstract A method of data classification using a decision tree having nodes is disclosed, along with an apparatus for perming the method. Periodically or after a certain number of nodes of the tree are split, the partially built tree is pruned. During the building phase the minimum cost of subtrees rooted at leaf nodes that can still be expanded ("yet to be expanded nodes")is computed. With the computation of the minimum subtree cost at nodes, the nodes pruned are a subset of those that would have been pruned anyway during the pruning phase, and they are pruned while the tree is still being built.
Inventors
- 👤 Rajeev Rastogi
- 👤 Kyuseok Shim
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 00:35
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/28; G06F16/284; G06F16/285; G06F18/00; G06F18/20; G06F18/24; G06F18/243; G06F18/24323; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942; Y10S707/99943
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
50 words
In a method of data classification involving the generation of a decision tree by building and pruning the decision tree, the improvement comprising: determining, during the building process, which nodes of the decision tree are appropriate for pruning; and pruning, during the building process, those nodes deemed appropriate for pruning.
Claim 2
Dependent Claim
50 words
In a method of data classification involving the generation of a decision tree by building and pruning the decision tree, the improvement comprising: determining, during the building process, which nodes of the decision tree are appropriate for pruning; and pruning, during the building process, those nodes deemed appropriate for pruning.
Claim 3
Dependent Claim
83 words
A method as set forth in claim 1 , wherein said determining step includes the steps of: computing the minimum cost of subtrees of yet to be expanded nodes; computing the minimum cost of encoding the subtrees at existing internal nodes using the computed minimum cost of subtrees of yet to be expanded nodes; and immediately pruning those subtrees at the internal node for which the computed minimum cost of the subtree is greater than the cost of encoding the internal node itself.
Claim 4
Dependent Claim
39 words
A method as set forth in claim 2 , wherein said step of computing the minimum cost of subtrees of yet to be expanded nodes is based on the cost of the node in which the subtree is rooted.
Claim 5
Dependent Claim
48 words
A method as set forth in claim 2 , wherein said step of computing the minimum cost of subtrees of yet to be expanded nodes is based on cost of the node in which the subtree is rooted and the cost of any splits associated with that node.
Claim 6
Dependent Claim
63 words
A method as set forth in claim 2 , wherein said step of computing the minimum cost of subtrees of yet to be expanded nodes is based on the cost of the node in which the subtree is rooted, the cost of any splits associated with that node, and the cost of encoding the split value of any splits associated with that node.
Claim 7
Independent Claim
199 words
A method of generating a decision tree classifier from a training set of records, each record having at least one numeric attribute and a class label of a class to which the record belongs, the method comprising the steps of: presorting the records based on the numeric attribute; generating an attribute list for each attribute and a class list, each entry of the class list corresponding to a class label, the attribute list including values of the attribute and indices to the class label; building a decision tree from the pre-sorted records, attribute lists, and class list, using a breadth-first process, the decision tree having a root node, a plurality of interior nodes, and a plurality of leaf nodes, the breadth first process being such that the nodes of a same depth from the root node are formed in parallel; and periodically pruning the decision tree during the building process based on a Minimum Description Length (MDL) scheme to obtain the decision tree classifier, the MDL scheme encoding the decision tree as a model such that an encoding cost for describing the decision tree and the training set is minimized taking into account the encoding cost in the pruning.
Claim 8
Independent Claim
199 words
A method of generating a decision tree classifier from a training set of records, each record having at least one numeric attribute and a class label of a class to which the record belongs, the method comprising the steps of: presorting the records based on the numeric attribute; generating an attribute list for each attribute and a class list, each entry of the class list corresponding to a class label, the attribute list including values of the attribute and indices to the class label; building a decision tree from the pre-sorted records, attribute lists, and class list, using a breadth-first process, the decision tree having a root node, a plurality of interior nodes, and a plurality of leaf nodes, the breadth first process being such that the nodes of a same depth from the root node are formed in parallel; and periodically pruning the decision tree during the building process based on a Minimum Description Length (MDL) scheme to obtain the decision tree classifier, the MDL scheme encoding the decision tree as a model such that an encoding cost for describing the decision tree and the training set is minimized taking into account the encoding cost in the pruning.
Claim 9
Dependent Claim
84 words
A method as set forth in claim 6 , wherein said periodic pruning step includes the steps of: computing the minimum cost of subtrees of yet to be expanded nodes; computing the minimum cost of encoding the subtrees at existing internal nodes using the computed minimum cost of subtrees of yet to be expanded nodes; and immediately pruning those subtrees at the internal node for which the computed minimum cost of the subtree is greater than the cost of encoding the internal node itself.
Claim 10
Dependent Claim
39 words
A method as set forth in claim 7 , wherein said step of computing the minimum cost of subtrees of yet to be expanded nodes is based on the cost of the node in which the subtree is rooted.
Claim 11
Dependent Claim
48 words
A method as set forth in claim 7 , wherein said step of computing the minimum cost of subtrees of yet to be expanded nodes is based on cost of the node in which the subtree is rooted and the cost of any splits associated with that node.
Claim 12
Dependent Claim
63 words
A method as set forth in claim 7 , wherein said step of computing the minimum cost of subtrees of yet to be expanded nodes is based on the cost of the node in which the subtree is rooted, the cost of any splits associated with that node, and the cost of encoding the split value of any splits associated with that node.
Claim 13
Independent Claim
47 words
A method of data classification, comprising the steps of: building a decision tree based on the data to be classified; determining, during the building step, which nodes of the decision tree are appropriate for pruning; and pruning said decision tree prior to completion of the building process.
Claim 14
Independent Claim
47 words
A method of data classification, comprising the steps of: building a decision tree based on the data to be classified; determining, during the building step, which nodes of the decision tree are appropriate for pruning; and pruning said decision tree prior to completion of the building process.
Claim 15
Dependent Claim
87 words
A method as set forth in claim 11 , wherein said determining step includes the steps of: computing the minimum cost of subtrees of yet to be expanded nodes of said decision tree; computing the minimum cost of encoding the subtrees at existing internal nodes using the computed minimum cost of subtrees of yet to be expanded nodes; and immediately pruning those subtrees at the internal node for which the computed minimum cost of the subtree is greater than the cost of encoding the internal node itself.
Claim 16
Dependent Claim
39 words
A method as set forth in claim 12 , wherein said step of computing the minimum cost of subtrees of yet to be expanded nodes is based on the cost of the node in which the subtree is rooted.
Claim 17
Dependent Claim
48 words
A method as set forth in claim 12 , wherein said step of computing the minimum cost of subtrees of yet to be expanded nodes is based on cost of the node in which the subtree is rooted and the cost of any splits associated with that node.
Claim 18
Dependent Claim
63 words
A method as set forth in claim 12 , wherein said step of computing the minimum cost of subtrees of yet to be expanded nodes is based on the cost of the node in which the subtree is rooted, the cost of any splits associated with that node, and the cost of encoding the split value of any splits associated with that node.
Claim 19
Dependent Claim
83 words
A computer system for classifying data by generating a decision tree, said computer system comprising: a CPU; a user interface operatively connected to said CPU; and memory operatively connected to said CPU, said memory containing instructions for instructing said CPU to perform the following steps: building a decision tree based on the data to be classified; determining, during the building step, which nodes of the decision tree are appropriate for pruning; and pruning said decision tree prior to completion of the building process.
Claim 20
Dependent Claim
83 words
A computer system for classifying data by generating a decision tree, said computer system comprising: a CPU; a user interface operatively connected to said CPU; and memory operatively connected to said CPU, said memory containing instructions for instructing said CPU to perform the following steps: building a decision tree based on the data to be classified; determining, during the building step, which nodes of the decision tree are appropriate for pruning; and pruning said decision tree prior to completion of the building process.
Claim 21
Dependent Claim
94 words
A computer system as set forth in claim 16 , said memory further containing instructions for instructing the CPU to perform the following steps: computing the minimum cost of subtrees of yet to be expanded nodes of said decision tree; computing the minimum cost of encoding the subtrees at existing internal nodes using the computed minimum cost of subtrees of yet to be expanded nodes; and immediately pruning those subtrees at the internal node for which the computed minimum cost of the subtree is greater than the cost of encoding the internal node itself.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-06-11 | 2004-12-11 | 2005-06-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-06-11 | 2008-12-11 | 2009-06-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-06-11 | 2012-12-11 | 2013-06-12 | $7700.00 | Window Closed / Lapsed |