Bayes rule based and decision tree hybrid classifier

• US 6,182,058 B1
• Filed: 02/28/1997
• Issued: 01/30/2001
• Est. Priority Date: 02/28/1997
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Silicon Graphics Incorporated (Graphics Properties Holdings, Inc.)
• Inventors: Kohavi, Ron
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): STARKS, WILBERT L
• Application Number:
  US08/810,217
• Time in Patent Office: 1,432 Days
• Field of Search: 382/225, 382/227, 382/236, 706/25, 704/250
• US Class Current: 706/45
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers

Abstract

The present invention provides a hybrid classifier, called the NB-Tree classifier, for classifying a set of records. According to the present invention, the NB-Tree classifier includes a Decision-Tree structure having zero or more decision-nodes and one or more leaf-nodes. At each decision-node, a test is performed based on one or more attributes. At each leaf-node, a classifier based on Bayes Rule classifies the records. Furthermore, the present invention provides a method for inducing the NB-Tree classifier from a set of labeled instances. To induce the NB-Tree classifier, a utility C₁ of a Bayes classifier at a root-node is first estimated. Next, a utility D₁ of a split into a plurality of child-nodes with a Bayes classifier at the child-nodes is estimated. The utility of a split is the weighted sum of the utility of the child-nodes, where the weight given to a child-node is proportional to the number of instances that go down that child-node. Next, it is determined if C₁ is higher than D₁. If C₁ is higher than D₁, the root-node is transformed into a leaf-node with a Bayes classifier. If C₁ is not higher than D₁, the root-node is transformed into a decision-node, and the instances are partitioned into a plurality of child-nodes. The method then recursively performs the previous steps for each child-node as if it is a root-node. The present invention approximates whether a generalization accuracy for a Naive-Bayes classifier at each leaf-node is higher than a single Naive-Bayes classifier at the decision-node. According to one embodiment of the present invention, to avoid splits with little value, a split is defined to be significant if the relative (not absolute) reduction in error is greater than 5% and there are at least 30 instances in the node.

Claims

1. A hybrid classifier comprising a computer program residing in a computer readable medium for classifying a set of instances, each instance having a plurality of attributes, comprising:

a decision tree structure having zero or more decision-nodes and one or more leaf-nodes, wherein at each of said decision-nodes, a test is performed based on one or more attributes; and

a classifier based on Bayes Rule at each of said leaf-nodes, each leaf-node being connected to a decision-node of the decision tree, said classifier classifying said instances at each leaf-node according to Bayes Rule;

wherein said hybrid classifier outputs a label for each classified instance.

12. The hybrid classifier of claim 1, wherein said decision tree structure includes at least one decision node.

2. A method for executing a hybrid classifier residing in a computer readable medium, said hybrid classifier having at least one decision-node and at least one leaf-node to classify a set of instances, each having a plurality of attributes, the method comprising the steps of:

performing a test, based on one or more of said attributes, at each of said decision-nodes;

classifying said instances according to Bayes Rule, at each leaf-node, by processing of a Bayes Rule classifier residing in said computer readable medium; and

outputting a label for each classified instance.

3. A method of inducing a hybrid classifier from a set of labeled instances, each instance having a plurality of attributes, the method comprising the steps of:

(a) estimating utility C₁ of a Bayes classifier at the root-node;

(b) estimating utility D₁ of a split into a plurality of child-nodes with a Bayes classifier at the child-nodes;

(c) determining if C₁ is higher than D₁,

if C₁ is higher than D₁, making said root-node a leaf-node with a Bayes classifier;

if C₁ is not higher than D₁, making said root node a decision-node, and partitioning the instances into a plurality of child-nodes; and

(d) recursively performing steps (a) through (c) for each child-node as if it is a root-node to obtain said hybrid classifier;

wherein said induced hybrid classifier has a root-node, zero or more decision-nodes, zero or more child-nodes and one or more leaf-nodes, said root-node being either a decision-node or a leaf-node; and

(e) storing said induced hybrid classifier in a computer readable medium.

4. The method of inducing according to claim 3, wherein said Bayes classifier is Naive-Bayes built after all attributes have been discretized.

5. The method of inducing according to claim 3, wherein said utility estimate of a split in step (b) is based on an accuracy estimation selected from the group consisting of at least holdout, cross-validation and bootstrap.

6. The method of inducing according to claim 3, wherein estimating the utility D₁ of a split based on one or more attributes further comprises the step of determining a threshold split for ordered attributes.

7. The method of inducing according to claim 3, wherein said partitioning the instances into a plurality of child further comprises the step of performing a multiway split, i.e., a non-binary split.

8. The method of inducing according to claim 3, wherein the utility of a split into a plurality of child-nodes is the weighted sum of the utility of the child-nodes, where the weight given to each child-node is proportional to the number of instances that go down to that node.

9. A method of inducing a hybrid classifier from a set of labeled instances, each instance having a plurality of attributes, the method comprising the steps of:

(a) estimating the Naive-Bayes accuracy A for the root-node;

(b) if X_i is ordered, determining a threshold;

(c) determining the accuracy estimate u(X_i) of a split into a plurality of child-nodes based on each attribute X_i at said root-node;

(d) determining the attribute j with the highest accuracy, said j=arg max_iu(X_i), said u(X_j) being the accuracy of the attribute j;

(e) if u(X_j) is not higher than A, making said root-node a leaf-node, creating a Naive-Bayes classifier at said leaf-node,

if u(X_j) is higher than A, making said root-node a decision-node based on X_i, partitioning the instances into a plurality of child-nodes according to X_j, said partitioning includes a multiway split when Xj is discrete or has been discretized; and

(f) recursively performing steps (a) through (e) for each child-node X_j as if it is a root-node thereby inducing a hybrid classifier;

wherein said induced hybrid classifier has a root-node, zero or more decision-nodes, zero or more child-nodes and one or more leaf-nodes, said root-node being either a decision-node or a leaf-node; and

(g) storing said induced hybrid classifier in a computer readable medium.

10. A system for inducing a hybrid classifier from a set of labeled instances, each instance having a plurality of attributes, said hybrid classifier having a root-node, one or more decision-nodes, one or more child-nodes and one or more leaf-nodes, said root-node being either a decision-node or a leaf-node in appropriate circumstances, comprising:

at least one processor coupled to a storage means, the one at least processor includes;

(a) means for estimating utility C₁ of a Bayes classifier at the root-node;

(b) means for estimating utility D₁ of a split into a plurality of child-nodes with a Bayes classifier at the child-nodes;

(c) means for determining if C₁ is higher than D₁;

(d) means for making said root-node a leaf-node with a Bayes classifier if C₁ is higher than D₁;

(e) means for making said root node a decision-node, and partitioning the instances into a plurality of child-nodes, if C₁ is not higher than D₁; and

(f) means for recursively initiating operation of each of means (a) through (e) for each child-node as if it is a root-node thereby inducing said hybrid classifier which can be stored in said storage means.

11. A computer program product comprising:

a computer readable medium having computer readable program code means embodied in said medium for causing inducement of a hybrid classifier from a set of labeled instances, each instance having a plurality of attributes, said hybrid classifier having a root-node, one or more decision-nodes, one or more child-nodes and one or more leaf-nodes, said root-node being either a decision-node or a leaf-node in appropriate circumstances, said computer program product including;

(a) computer readable program code means for estimating utility C₁ of a Bayes classifier at the root-node;

(b) computer readable program code means for estimating utility D₁ of a split into a plurality of child-nodes with a Bayes classifier at the child-nodes;

(c) computer readable program code means for determining if C₁ is higher than D₁;

(d) computer readable program code means for making said root-node a leaf-node with a Bayes classifier if C₁ is higher than D₁;

(e) computer readable program code means for making said root node a decision-node, and partitioning the instances into a plurality of child-nodes according to the tests if C₁ is not higher than D₁; and

(f) computer readable program code means for recursively initiating operation of each of computer readable program code means (a) through (e) for each child-node as if it is a root-node thereby inducing said hybrid classifier.

13. A hybrid classifier that classifies a set of instances, each instance having a plurality of attributes, the hybrid classifier comprising:

a decision tree structure having zero or more decision-nodes and one or more leaf-nodes, wherein at each of said decision-nodes, a test is performed based on one or more attributes; and

a classifier based on Bayes Rule at each of said leaf-nodes, each leaf-node being connected to a decision-node of the decision tree, said classifier classifying said instances at each leaf-node according to Bayes Rule;

wherein said hybrid classifier outputs a label for each classified instance, and wherein said hybrid classifier comprises at least one of software, firmware, and hardware.