Data mining method and system for generating a decision tree classifier for data records based on a minimum description length (MDL) and presorting of records

• US 5,787,274 A
• Filed: 11/29/1995
• Issued: 07/28/1998
• Est. Priority Date: 11/29/1995
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mehta, Manish, Agrawal, Rakesh, Rissanen, Jorma Johannes
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US08/564,694
• Time in Patent Office: 972 Days
• Field of Search: 395/613, 395/611, 395/600, 395/612
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and apparatus are disclosed for generating a decision tree classifier from a training set of records. The method comprises the steps of: pre-sorting the records based on each numeric record attribute, creating a decision tree breadth-first, and pruning the tree based on the MDL principle. Preferably, the pre-sorting includes generating a class list and attribute lists, and independently sorting the numeric attribute lists. The growing of the tree includes evaluating possible splitting criteria and selecting a splitting test for each leaf node, based on a splitting index, and updating the class list to reflect new leaf nodes. In a preferred embodiment, the splitting index is a gini index. The pruning preferably includes encoding the decision tree and splitting tests in an MDL-based code, and determining whether to convert a node into a leaf node, prune its child nodes, or leave the node intact, based on the code length of the node.

Claims

1. A method for 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:

pre-sorting 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 labels;

creating 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

pruning the decision tree 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, and the method taking into account the encoding cost in the pruning.

2. The method as recited in claim 1, wherein:

each entry of the class list includes a node ID corresponding to a leaf node; and

the step of generating an attribute list includes the steps of;

initializing each node ID to be the root node of the decision tree; and

sorting the attribute list for each numeric attribute, based on the attribute values.

3. The method as recited in claim 2, wherein

the step of creating includes the steps, executed for each leaf node, of:

evaluating possible splitting criteria for each attribute at the leaf node, each possible splitting criterion having a respective splitting index associated therewith, the step of evaluating being based on the splitting index associated with each splitting criterion;

determining a splitting test for the leaf node from the evaluated splitting criteria, the splitting test being a splitting criterion with a highest splitting index;

creating child nodes for the leaf node, the child nodes becoming new leaf nodes of the decision tree;

partitioning the records according to the splitting test at the leaf node; and

updating the class list to reflect the created child nodes.

4. The method as recited in claim 3, wherein:

the attributes further include categorical attributes;

each leaf node has a class histogram associated therewith; and

the step of evaluating includes the steps of;

a) for each attribute A, traversing the attribute list for A;

b) for each value v in the attribute list for A;

i) identifying from the class list a class label corresponding to the value v;

ii) updating the class histogram associated with a leaf node referenced by the identified class label; and

iii) if the attribute A is numeric, then computing a splitting index for the splitting criterion (A≦

v) for the referenced leaf node; and

c) if A is categorical, then determining a subset of the attribute A with a best split for the referenced leaf node after the attribute list for A has been traversed, the best split being a split with a highest splitting index.

5. The method as recited in claim 4, wherein

the splitting index is a gini-index, the gini-index being based on relative frequencies of records from each class contained in the training set.

6. The method as recited in claim 4, wherein:

at least an attribute A of the attributes is categorical;

the step of determining a subset includes evaluating all subsets of a set S of all values of A, if a number of elements in S is less than a threshold; and

the step of determining a subset includes, if the number of elements in S is equal to or more than the threshold, the steps of;

starting with an empty subset S'"'"' of the set S, adding an element of S to S'"'"' such that the splitting index for the split at the leaf node is maximized; and

repeating the step of adding until there is no improvement in the splitting index.

7. The method as recited in claim 3, wherein:

the step of partitioning includes the steps of;

(i) reading the records from the training set,

(ii) for each record, determining a first leaf node of the decision tree to which the record belongs, and

(iii) applying the splitting test for the first leaf node to the record; and

the step of updating the class list includes the steps of;

(i) identifying the child node of the first leaf node to which the record belongs,

(ii) updating the class histogram associated with the identified child node, and

(iii) updating the class label and node ID corresponding to the first leaf node to reflect the identified child node.

8. The method as recited in claim 7, wherein

the step of updating the class list further includes the steps of, for each value v in the attribute list of the attribute used in the splitting test of the first leaf node:

identifying from the class table a class label corresponding to V;

identifying a new class to which v belongs by applying the splitting test at the leaf node referenced by the identified class label;

updating the identified class label to reflect the new class; and

updating the node ID referenced by the identified class label to be the node ID of the child node corresponding to the new class.

9. The method as recited in claim 3, wherein the steps included in creating the decision tree are repeated until each leaf node of the decision tree contains only one class of records.

10. The method as recited in claim 1, wherein:

the pruning step includes the steps of;

encoding the decision tree in a MDL-based code;

encoding the splitting tests for the leaf nodes in the MDL-based code;

calculating a code length C(n) for each node n of the decision tree; and

determining whether to prune the child nodes of the node n, convert n into a leaf node, or leave n intact, taking into account the encoding cost; and

the encoding cost is based on C(n).

11. The method as recited in claim 10, wherein:

the step of encoding the decision tree includes;

(i) encoding each node of the decision tree using one bit, if the possible number of child nodes the node can have is zero and two;

(ii) encoding each node of the decision tree using two bits, if the possible number of child nodes the node can have is zero, one, and two; and

(iii) encoding each node of the decision tree using log(3) bits, if only the internal nodes are examined; and

the encoding cost includes;

(i) a cost for encoding an attribute value v of an attribute A, where the splitting test is of the form (A≦

v) and A is numeric; and

(ii) ln n_A where n_A is a number of times the splitting test is used in the tree and A is a categorical attribute.

12. The method as recited in claim 10, wherein:

each node n of the decision tree is encoded using one bit; and

the step of determining whether to prune includes the steps of;

pruning both children nodes of the node n; and

converting the node n into a leaf node,

if the code length C(n) when n has both child nodes is more than C(n) when n is a leaf node.

13. The method as recited in claim 10, wherein:

each node n of the decision tree is encoded using two bits; and

the step of determining whether to prune includes the steps of;

evaluating the code length C(n) when n is a leaf node, n has only a left child node, n has only a right child node, and n has both child nodes; and

selecting a pruning option that results in a shortest code length C(n).

14. The method as recited in claim 12 further comprising the steps of:

for each node n of the pruned decision tree, evaluating the code length C(n) when n has only a left child node, n has only a right child node, and n has both child nodes; and

selecting a pruning option that results in a shortest code length C(n).

15. A computer program product for use with a computer system for 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 computer program product comprising:

a recording medium;

means, recorded on the recording medium, for directing the computer system to pre-sort the records based on the numeric attribute;

means, recorded on the recording medium, for directing the computer system to generate 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 labels;

means, recorded on the recording medium, for directing the computer system to create 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 created in parallel; and

means, recorded on the recording medium for directing the computer system to prune the decision tree 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, and the method taking into account the encoding cost in the pruning.

16. The computer program product as recited in claim 15, wherein:

each entry of the class list includes a node ID corresponding to a leaf node; and

the means for directing to generate an attribute list includes;

means, recorded on the recording medium, for directing the computer system to initialize each node ID to be the root node of the decision tree; and

means, recorded on the recording medium, for directing the computer system to sort the attribute list for each numeric attribute, based on the attribute values.

17. The computer program product as recited in claim 16, wherein the means for directing to create includes:

means, recorded on the recording medium for directing the computer system to evaluate possible splitting criteria for each attribute, at each leaf node, each possible splitting criterion having a respective splitting index associated therewith, the evaluation being based on the splitting index associated with each splitting criterion;

means, recorded on the recording medium, for directing the computer system to determine a splitting test for the leaf node from the evaluated splitting criteria, the splitting test being a splitting criterion with a highest splitting index;

means, recorded on the recording medium, for directing the computer system to create child nodes for the leaf node, the child nodes becoming new leaf nodes of the decision tree;

means, recorded on the recording medium, for directing the computer system to partition the records according to the splitting test at the leaf node; and

means, recorded on the recording medium, for directing the computer system to update the class list to reflect the created child nodes.

18. The computer program product as recited in claim 17, wherein:

the attributes further include categorical attributes;

each leaf node has a class histogram associated therewith; and

the means for directing to evaluate includes;

a) means, recorded on the recording medium, for directing the computer system to traverse the attribute list for each attribute A;

b) for each value v in the attribute list for A;

i) means, recorded on the recording medium, for directing the computer system to identify from the class list a class label corresponding to the value v;

ii) means, recorded on the recording medium, for directing the computer system to update the class histogram associated with a leaf node referenced by the identified class label; and

iii) if the attribute A is numeric, then means, recorded on the recording medium, for directing the computer system to compute a splitting index for the splitting criterion (A≦

v) for the referenced leaf node; and

c) if A is categorical, then means, recorded on the recording medium, for directing the computer system to determine a subset of the attribute A with a best split for the leaf node after the attribute list for A has been traversed, the best split being a split with a highest splitting index.

19. The computer program product as recited in claim 18, wherein

the splitting index is a gini-index, the gini-index being based on relative frequencies of records from each class contained in the training set.

20. The computer program product as recited in claim 18, wherein:

at least an attribute A of the attributes is categorical;

the means for directing to determine a subset includes means, recorded on the recording medium, for directing the computer system to evaluate all subsets of a set S of all values of A, if a number of elements in S is less than a threshold; and

if a number of elements in S is equal to or more than a threshold, then the means for directing to determine a subset includes;

means, recorded on the recording medium, for directing the computer system to add, starting with an empty subset S'"'"' of the set S, an element of S to S'"'"' such that the splitting index for the split at the leaf node is maximized; and

means, recorded on the recording medium, for directing the computer system to repeat the adding until there is no improvement in the splitting index.

21. The computer program product as recited in claim 17, wherein:

the means for directing to partition includes means, recorded on the recording medium, for directing the computer system to;

(i) read the records from the training set,

(ii) for each record, determine a first leaf node of the decision tree to which the record belongs, and

(iii) apply the splitting test for the first leaf node to the record; and

the means for directing to update the class list includes means, recorded on the recording medium, for directing the computer system to;

(i) identify the child node of the first leaf node to which the record belongs,

(ii) update the histogram associated with the identified child node, and

(iii) update the class label and node ID corresponding to the first leaf node to reflect the identified child node.

22. The computer program product as recited in claim 21, wherein the means for directing to update the class list further includes, for each value v in the attribute list of the attribute used in the splitting test of the first leaf node:

means, recorded on the recording medium, for directing the computer system to identify from the class table a class label corresponding to V;

means, recorded on the recording medium, for directing the computer system to identify a new class to which v belongs by applying the splitting test at the leaf node referenced by the identified class label;

means, recorded on the recording medium, for directing the computer system to update the identified class label to reflect the new class; and

means, recorded on the recording medium, for directing the computer system to update the node ID referenced by the identified class label to be the node ID of the child node corresponding to the new class.

23. The computer program product as recited in claim 17, wherein the operation of the means for directing to create the decision tree is repeated until each leaf node of the decision tree contains only one class of records.

24. The computer program product as recited in claim 15, wherein the means for directing the system to prune includes:

means, recorded on the recording medium, for directing the computer system to encode the decision tree in a MDL-based code;

means, recorded on the recording medium, for directing the computer system to encode the splitting tests for the leaf nodes in the MDL-based code;

means, recorded on the recording medium, for directing the computer system to calculate a code length C(n) for each node n of the decision tree; and

means, recorded on the recording medium, for directing the computer system to determine whether to prune the child nodes of the node n, convert n into a leaf node, or leave n intact, taking into account the encoding cost; and

wherein the encoding cost is based on C(n).

25. The computer program product as recited in claim 24, wherein:

the means for directing the system to encode the decision tree includes;

(i) means, recorded on the recording medium, for directing the computer system to encode each node of the decision tree using one bit, if the possible number of child nodes for the node is zero and two;

(ii) means, recorded on the recording medium, for directing the computer system to encode each node of the decision tree using two bits, if the possible number of child nodes for the node is zero, one, and two; and

(iii) means, recorded on the recording medium, for directing the computer system to encode each node of the decision tree using log(3) bits, if only the internal nodes are examined; and

the encoding cost includes;

(i) a cost for encoding an attribute value v of an attribute A, where the splitting test is of the form (A≦

v) and A is numeric; and

(ii) ln n_A where n_A.sbsb.i is a number of times the splitting test is used in the tree and A is a categorical attribute.

26. The computer program product as recited in claim 24, wherein:

each node of the decision tree is encoded using one bit; and

the means for directing the system to determine whether to prune includes;

means, recorded on the recording medium, for directing the computer system to prune both child nodes of the node n; and

means, recorded on the recording medium, for directing the computer system to convert the node n into a leaf node,

if the code length C(n) when n has both child nodes is more than C(n) when n is a leaf node.

27. The computer program product as recited in claim 24, wherein:

each node of the decision tree is encoded using two bits; and

the means for directing the system to determine whether to prune includes;

means, recorded on the recording medium, for directing the computer system to evaluate the code length C(n) when n is a leaf node, n has only a left child node, n has only a right child node, and n has both child nodes; and

means, recorded on the recording medium, for directing the computer system to select a pruning option that results in a shortest code length C(n).

28. The computer program product as recited in claim 26 further comprising:

means, recorded on the recording medium, for directing the computer system to evaluate, for each node n of the pruned decision tree, the code length C(n) when n has only a left child node, n has only a right child node, and n has both child nodes; and

means, recorded on the recording medium, for directing the computer system to select a pruning option that results in a shortest code length C(n).

29. A computer-based system for 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 system comprising:

means for pre-sorting the records based on the values of the numeric attribute;

means for 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 labels;

means for creating 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

means for pruning the decision tree 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, and the method taking into account the encoding cost in the pruning.

30. The system as recited in claim 29, wherein:

each entry of the class list includes a node ID corresponding to a leaf node; and

the means for generating an attribute list includes;

means for initializing each node ID to be the root node of the decision tree; and

means for sorting the attribute list for each numeric attribute, based on the attribute values.

31. The system as recited in claim 30, wherein the means for creating includes:

means for evaluating possible splitting criteria for each attribute, at each leaf node, each possible splitting criterion having a respective splitting index associated therewith, the evaluation being based on the splitting index associated with each splitting criterion;

means for determining a splitting test for each leaf node from the evaluated splitting criteria, the splitting test being a splitting criterion with a highest splitting index;

means for creating child nodes for each leaf node, the child nodes becoming new leaf nodes of the decision tree;

means for partitioning the records according to the splitting test at each leaf node; and

means for updating the class list to reflect the created child nodes.

32. The system as recited in claim 31, wherein:

the attributes further include categorical attributes;

each leaf node has a class histogram associated therewith; and

the means for evaluating includes;

a) means for traversing, for each attribute A, the attribute list for A;

b) for each value v in the attribute list for A;

i) means for identifying from the class list a class label corresponding to the value v;

ii) means for updating the class histogram associated with a leaf node referenced by the identified class label; and

iii) if the attribute A is numeric, then means for computing a splitting index for the splitting criterion (A≦

v) for the referenced leaf node; and

c) if A is categorical, then means for determining a subset of the attribute A with a best split for the referenced leaf node after the attribute list for A has been traversed, the best split being a split with a highest splitting index.

33. The system as recited in claim 32, wherein

the splitting index is a gini-index, the gini-index being based on relative frequencies of records from each class contained in the training set.

34. The system as recited in claim 32, wherein:

at least one attribute A of the attributes is categorical;

the means for determining a subset includes means for evaluating all subsets of a set S of all values of A, if a number of elements in S is less than a threshold; and

if the number of elements in S is equal to or more than the threshold, the means for determining a subset includes;

means for adding, starting with an empty subset S'"'"' of the set S, an element of S to S'"'"' such that the splitting index for the split at the leaf node is maximized; and

means for repeating the adding until there is no improvement in the splitting index.

35. The system as recited in claim 31, wherein:

the means for partitioning includes;

(i) means for reading the records from the training set,

(ii) means for determining, for each record, a first leaf node of the decision tree to which the record belongs, and

(iii) means for applying the splitting test for the first leaf node to the record; and

the means for updating the class list includes;

(i) means for identifying the child node of the first leaf node to which the record belongs,

(ii) means for updating the class histogram associated with the identified child node, and

(iii) means for updating the class label and node ID corresponding to the first leaf node to reflect the identified child node.

36. The system as recited in claim 35, wherein

the means for updating the class list further includes:

for each value v in the attribute list of the attribute used in the splitting test, of the first leaf node;

means for identifying from the class table a class label corresponding to a value v;

means for identifying a new class to which v belongs by applying the splitting test at the leaf node referenced by the identified class label;

means for updating the identified class label to reflect the new class; and

means for updating the node ID referenced by the identified class label to be the node ID of the child node corresponding to the new class.

37. The system as recited in claim 31, wherein the operation of the means for creating the decision tree is repeated until each leaf node of the decision tree contains only one class of records.

38. The system as recited in claim 29, wherein:

the means for pruning includes;

means for encoding the decision tree in a MDL-based code;

means for encoding the splitting tests for the leaf nodes in the MDL-based code;

means for encoding a code length C(n) for each node n of the decision tree; and

means for determining whether to prune the child nodes of the node n, convert n into a leaf node, or leave n intact, taking into account the encoding cost; and

the encoding cost is based on C(n).

39. The system as recited in claim 38, wherein:

the means for encoding the decision tree includes;

(i) means for encoding each node of the decision tree using one bit, if the possible number of child nodes for the node is zero and two;

(ii) means for encoding each node of the decision tree using two bits, if the possible number of child nodes for the node is zero, one, and two; and

(iii) means for encoding each node of the decision tree using log(3) bits, if only the internal nodes are examined; and

the encoding cost includes;

(i) a cost for encoding an attribute value v of an attribute A, where the splitting test is of the form (A≦

v) and A is numeric; and

(ii) ln_A where n_A is a number of times the splitting test is used in the tree and A is a categorical attribute.

40. The system as recited in claim 38, wherein:

each node of the decision tree is encoded using one bit; and

the means for determining whether to prune includes;

means for pruning both child nodes of the node n; and

means for converting n into a leaf node,

if the code length C(n) when n has both child nodes is more than C(n) when n is a leaf node.

41. The system as recited in claim 38, wherein:

each node of the decision tree is encoded using two bits; and

the means for determining whether to prune includes;

means for evaluating the code length C(n) when n is a leaf node, n has only a left child node, n has only a right child node, and n has both child nodes; and

means for selecting a pruning option that results in a shortest code length C(n).

42. The system as recited in claim 40 further comprising:

means for evaluating, for each node n of the pruned decision tree, the code length C(n) when n has only a left child node, n has only a right child node, and n has both child nodes; and

means for selecting a pruning option that results in a shortest code length C(n).