US6138115A — Method and system for generating a decision-tree …

Claim 1

Independent Claim 139 words

A method for generating a decision-tree classifier in parallel in a system having a plurality of processors, from a training set of records, each record having: (i) at least one attribute, each attribute having a value, (ii) a class label of the class to which the record belongs, and (iii) a record ID, the method comprising the steps of: partitioning the records among the processors of the system; generating in parallel by each processor an attribute list for each attribute of the records, each entry in the attribute lists having the attribute value, class label, and record ID of the record from which the attribute value is obtained; and creating a decision tree cooperatively by the processors, the decision tree being formed by repeatedly partitioning the records using the attribute lists, the resulting decision tree becoming the decision-tree classifier.

Claim 2

Independent Claim 139 words

A method for generating a decision-tree classifier in parallel in a system having a plurality of processors, from a training set of records, each record having: (i) at least one attribute, each attribute having a value, (ii) a class label of the class to which the record belongs, and (iii) a record ID, the method comprising the steps of: partitioning the records among the processors of the system; generating in parallel by each processor an attribute list for each attribute of the records, each entry in the attribute lists having the attribute value, class label, and record ID of the record from which the attribute value is obtained; and creating a decision tree cooperatively by the processors, the decision tree being formed by repeatedly partitioning the records using the attribute lists, the resulting decision tree becoming the decision-tree classifier.

Claim 3

Dependent Claim 47 words

The method as recited in claim 1, wherein: the attributes include numeric attributes; and the step of generating an attribute list includes the steps of: sorting the attribute lists for the numeric attributes based on the attribute values; and distributing the sorted attribute lists among the processors.

Claim 4

Dependent Claim 13 words

The method as recited in claim 1, wherein the attributes include categorical attributes.

Claim 5

Dependent Claim 156 words

The method as recited in claim 1, wherein: the decision tree includes a root node, a plurality of interior nodes, and a plurality of leaf nodes, all of the records initially belonging to the root node; and the step of creating a decision tree includes the steps, executed by each processor for each node being examined until each leaf node of the decision tree contains only one class of records, of: a) determining a split test to best separate the records at the examined node by record classes, using the attribute lists of the processor; b) sharing the split test with the other processors to determine a best overall split test for the examined node; and c) splitting the records of the examined node that are assigned to the processor, according to the best overall split test for the examined node, to create child nodes for the examined node, the child nodes becoming new leaf nodes.

Claim 6

Dependent Claim 29 words

The method as recited in claim 4, wherein the step of determining a split test is based on a splitting index corresponding to a criterion for splitting the records.

Claim 7

Dependent Claim 29 words

The method as recited in claim 5, wherein the splitting index includes a gini-index based on relative frequencies of records from each record class present in the training set.

Claim 8

Dependent Claim 173 words

The method as recited in claim 5, wherein: each processor includes, for each leaf node, a plurality of histograms for each attribute of the records at the leaf node, the histograms representing the class distribution of the records at the leaf node; and the step of determining a split test includes the steps of: a) for each attribute A, traversing the attribute list for A at the examined node; b) for each value v of A in the attribute list for A: i) updating the class histograms for A, at the examined node, with the class label corresponding to v and the value v, and ii) if the attribute A is numeric, then computing the splitting index corresponding to splitting criterion (A<=v) for the examined node; and c) if the attribute A is categorical, then: i) a first processor collecting all the class histograms for A from all the processors, and ii) the first processor determining a subset of the attribute A that results in the highest splitting index for the examined node.

Claim 9

Dependent Claim 66 words

The method as recited in claim 7, wherein the histograms for each numeric attribute include a C below histogram and a C above histogram, the C below histogram corresponding to the class distribution of the records preceding those assigned to the processor, and the Caboos histogram corresponding to the class distribution of the records following a first record assigned to the processor, including the first record.

Claim 10

Dependent Claim 121 words

The method as recited in claim 7, wherein the step of determining a subset of the attribute A includes the steps of: if a number of elements in a set S of all values of A is less than a predetermined threshold, then evaluating all subsets of the set S to find one with the highest splitting index; and if the number of elements in S is equal to or more than the predetermined threshold, then: a) adding an element of S to an initially empty subset S' of S such that the splitting index for the splitting criterion at the examined node is maximized; and b) repeating the step of adding until there is no improvement in the splitting index.

Claim 11

Dependent Claim 107 words

The method as recited in claim 4, wherein the step of splitting the records includes the steps of: partitioning the attribute list for an attribute B used in the split test into new attribute lists corresponding, respectively, to the child nodes of the examined node; building a hash table with the record IDs from the entries of the attribute list for B as the entries are partitioned among the new attribute lists; sharing the hash table for attribute B with other processors; and partitioning the remaining attribute lists of the examined node among the newly created child nodes according to the hash tables shared by the processors.

Claim 12

Dependent Claim 54 words

The method as recited in claim 10, wherein the step of partitioning the attribute list includes the steps of: traversing the attribute list for attribute B; applying the split test to each entry of the attribute list for B; and entering the entry into a respective new attribute list according to the split test.

Claim 13

Dependent Claim 53 words

The method as recited in claim 10, wherein the step of creating a decision tree further comprises the steps of: updating the histograms for each newly created child node with the distribution of records at the child node; and sharing the updated histograms with other processors so that all the histograms remain updated.

Claim 14

Dependent Claim 21 words

The method recited in claim 4 further comprising the step of pruning the decision-tree classifier to obtain a more compact classifier.

Claim 15

Dependent Claim 123 words

The method as recited in claim 13, wherein: the step of pruning is based on a Minimum Description Length (MDL) principle that encodes the decision tree as a model such that an encoding cost for describing the decision tree and the training set is minimized; the step of pruning includes the steps of: encoding the decision tree in an MDL-based code; encoding the split 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 node n, convert n into a leaf node, or leave n intact, depending on the encoding cost; and the encoding cost is based on the code length C(n).

Claim 16

Dependent Claim 134 words

The method as recited in claim 14, wherein: a) the step of encoding the decision tree includes: (i) encoding each node of the decision tree using one bit, if the node has two or no child nodes; (ii) encoding each node of the decision tree using two bits, if the node has one, two, or no child nodes; and (iii) encoding each internal node of the decision tree using tog(3) bits; and b) the encoding cost includes: (i) a cost for encoding an attribute value v of an attribute A, where a split test is of the form (A≦v) and A is numeric; and (ii) a cost related to In(n A ) where n A is a number of times the split test is used in the tree and A is a categorical attribute.

Claim 17

Dependent Claim 76 words

The method as recited in claim 14, wherein: each node n of the decision tree is encoded using one bit; and if the code length C(n) in the case n has both child nodes is more than C(n) in the case n is a leaf node, the n the step of determining whether to prune includes the steps of: pruning both child nodes of the node n; and converting the node n into a leaf node.

Claim 18

Dependent Claim 60 words

The method as recited in claim 16 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).

Claim 19

Dependent Claim 76 words

The method as recited in claim 14, 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).

Claim 20

Dependent Claim 142 words

A database system for generating a decision-tree classifier in parallel from a training set of records, the system having a plurality of processors, each record having: (i) at least one attribute, each attribute having a value, (ii) a class label of the class to which the record belongs, and (iii) a record ID, the system comprising: means for partitioning the records among the processors of the system; means for generating in parallel by each processor an attribute list for each attribute of the records, each entry in the attribute lists having the attribute value, class label, and record ID of the record from which the attribute value is obtained; and means for creating a decision tree cooperatively by the processors, the decision tree being formed by repeatedly partitioning the records using the attribute lists, the resulting decision tree becoming the decision-tree classifier.

Claim 21

Dependent Claim 142 words

A database system for generating a decision-tree classifier in parallel from a training set of records, the system having a plurality of processors, each record having: (i) at least one attribute, each attribute having a value, (ii) a class label of the class to which the record belongs, and (iii) a record ID, the system comprising: means for partitioning the records among the processors of the system; means for generating in parallel by each processor an attribute list for each attribute of the records, each entry in the attribute lists having the attribute value, class label, and record ID of the record from which the attribute value is obtained; and means for creating a decision tree cooperatively by the processors, the decision tree being formed by repeatedly partitioning the records using the attribute lists, the resulting decision tree becoming the decision-tree classifier.

Claim 22

Dependent Claim 48 words

The system as recited in claim 19, wherein: the attributes include numeric attributes; and the means for generating an attribute list includes: means for sorting the attribute lists for the numeric attributes based on the attribute values; and means for distributing the sorted attribute lists among the processors.

Claim 23

Dependent Claim 13 words

The system as recited in claim 19, wherein the attributes include categorical attributes.

Claim 24

Dependent Claim 159 words

The system as recited in claim 19, wherein: the decision tree includes a root node, a plurality of interior nodes, and a plurality of leaf nodes, all of the records initially belonging to the root node; and the means for creating a decision tree includes, for each processor and for each node being examined until each leaf node of the decision tree contains only one class of records: a) means for determining a split test to best separate the records at the examined node by record classes, using the attribute lists of the processor; b) means for sharing the split test with the other processors to determine a best overall split test for the examined node; and c) means for splitting the records of the examined node that are assigned to the processor, according to the best overall split test for the examined node, to create child nodes for the examined node, the child nodes becoming new leaf nodes.

Claim 25

Dependent Claim 29 words

The system as recited in claim 22, wherein the means for determining a split test is based on a splitting index corresponding to a criterion for splitting the records.

Claim 26

Dependent Claim 29 words

The system as recited in claim 23, wherein the splitting index includes a gini-index based on relative frequencies of records from each record class present in the training set.

Claim 27

Dependent Claim 175 words

The system as recited in claim 23, wherein: each processor includes, for each leaf node, a plurality of histograms for each attribute of the records at the leaf node, the histograms representing the class distribution of the records at the leaf node; and the means for determining a split test includes: a) for each attribute A, means for traversing the attribute list for A at the examined node; b) for each value v of A in the attribute list for A: i) means for updating the class histograms for A, at the examined node, with the class label corresponding to v and the value v; and ii) if the attribute A is numeric, then means for computing the splitting index corresponding to splitting criterion (A<=v) for the examined node; and c) if the attribute A is categorical, then: i) means for collecting all the class histograms for A from all the processors; and ii) means for determining a subset of the attribute A that results is in the highest splitting index for the examined node.

Claim 28

Dependent Claim 67 words

The system as recited in claim 25, wherein the histograms for each numeric attribute include a C below histogram and a C above histogram, the C below histogram corresponding to the class distribution of the records preceding those assigned to the processor, and the C above histogram corresponding to the class distribution of the records following a first record assigned to the processor, including the first record.

Claim 29

Dependent Claim 122 words

The system as recited in claim 25, wherein the means for determining a subset of the attribute A includes: if a number of elements in a set S of all values of A is less than a predetermined threshold, then means for evaluating all subsets of the set S to find one with the highest splitting index; and if the number of elements in S is equal to or more than the predetermined threshold, then: a) means for adding an element of S to an initially empty subset S' of S such that the splitting index for the splitting criterion at the examined node is maximized; and b) means for repeating the adding until there is no improvement in the splitting index.

Claim 30

Dependent Claim 112 words

The system as recited in claim 22, wherein the means for splitting the records includes: means for partitioning the attribute list for an attribute B used in the split test into new attribute lists corresponding, respectively, to the child nodes of the examined node; means for building a hash table with the record IDs from the entries of the attribute list for B as the entries are partitioned among the new attribute lists; means for sharing the hash table for attribute B with other processors; and means for partitioning the remaining attribute lists of the examined node among the newly created child nodes according to the hash tables shared by the processors.

Claim 31

Dependent Claim 57 words

The system as recited in claim 28, wherein the means for partitioning the attribute list includes: means for traversing the attribute list for attribute B; means for applying the split test to each entry of the attribute list for B; and means for entering the entry into a respective new attribute list according to the split test.

Claim 32

Dependent Claim 54 words

The system as recited in claim 28, wherein the means for creating a decision tree further comprises: means for updating the histograms for each newly created child node with the distribution of records at the child node; and means for sharing the updated histograms with other processors so that all the histograms remain updated.

Claim 33

Dependent Claim 20 words

The system recited in claim 22 further comprising means for pruning the decision-tree classifier to obtain a more compact classifier.

Claim 34

Dependent Claim 128 words

The system as recited in claim 31, wherein: the means for pruning is based on a Minimum Description Length (MDL) principle that encodes the decision tree as a model such that an encoding cost for describing the decision tree and the training set is minimized; the means for pruning includes: means for encoding the decision tree in an MDL-based code; means for encoding the split tests for the leaf nodes in the MDL-based code; means for calculating a code length C(n) for each node n of the decision tree; and means for determining whether to prune the child nodes of node n, convert n into a leaf node, or leave n intact, depending on the encoding cost; and the encoding cost is based on the code length C(n).

Claim 35

Dependent Claim 139 words

The system as recited in claim 32, wherein: a) the means for encoding the decision tree includes: (i) means for encoding each node of the decision tree using one bit, if the node has two or no child nodes; (ii) means for encoding each node of the decision tree using two bits, if the node has one, two, or no child nodes; and (iii) means for encoding each internal node of the decision tree using log(3) bits; and b) the encoding cost includes: (i) a cost for encoding an attribute value of an attribute A, where a split test is of the form (A≦v) and A is numeric; and (ii) a cost related to In(n A ) where n A is a number of times the split test is used in the tree and A is a categorical attribute.

Claim 36

Dependent Claim 76 words

The system as recited in claim 32, wherein: each node n of the decision tree is encoded using one bit; and if the code length C(n) in the case n has both child nodes is more than C(n) in the case n is a leaf node, then the means for determining whether to prune includes: means for pruning both child nodes of the node n; and means for converting the node n into a leaf node.

Claim 37

Dependent Claim 61 words

The system as recited in claim 34 further comprising: for each node n of the pruned decision tree, means for 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 means for selecting a pruning option that results in a shortest code length C(n).

Claim 38

Dependent Claim 77 words

The system as recited in claim 32, wherein: each node n 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).

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2003-10-24	2004-04-24	2004-10-24	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2007-10-24	2008-04-24	2008-10-24	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2011-10-24	2012-04-24	2012-10-24	$7700.00	Window Closed / Lapsed

Method and system for generating a decision-tree classifier in parallel in a multi-processor system

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag