Bayes rule based and decision tree hybrid classifier
First Claim
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.
6 Assignments
0 Petitions
Accused Products
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 C1 of a Bayes classifier at a root-node is first estimated. Next, a utility D1 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 C1 is higher than D1. If C1 is higher than D1, the root-node is transformed into a leaf-node with a Bayes classifier. If C1 is not higher than D1, 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.
-
Citations
13 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. - View Dependent Claims (12)
-
-
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 C1 of a Bayes classifier at the root-node;
(b) estimating utility D1 of a split into a plurality of child-nodes with a Bayes classifier at the child-nodes;
(c) determining if C1 is higher than D1, if C1 is higher than D1, making said root-node a leaf-node with a Bayes classifier;
if C1 is not higher than D1, 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. - View Dependent Claims (4, 5, 6, 7, 8)
-
-
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 Xi is ordered, determining a threshold;
(c) determining the accuracy estimate u(Xi) of a split into a plurality of child-nodes based on each attribute Xi at said root-node;
(d) determining the attribute j with the highest accuracy, said j=arg maxiu(Xi), said u(Xj) being the accuracy of the attribute j;
(e) if u(Xj) is not higher than A, making said root-node a leaf-node, creating a Naive-Bayes classifier at said leaf-node, if u(Xj) is higher than A, making said root-node a decision-node based on Xi, partitioning the instances into a plurality of child-nodes according to Xj, 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 Xj 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 C1 of a Bayes classifier at the root-node;
(b) means for estimating utility D1 of a split into a plurality of child-nodes with a Bayes classifier at the child-nodes;
(c) means for determining if C1 is higher than D1;
(d) means for making said root-node a leaf-node with a Bayes classifier if C1 is higher than D1;
(e) means for making said root node a decision-node, and partitioning the instances into a plurality of child-nodes, if C1 is not higher than D1; 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 C1 of a Bayes classifier at the root-node;
(b) computer readable program code means for estimating utility D1 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 C1 is higher than D1;
(d) computer readable program code means for making said root-node a leaf-node with a Bayes classifier if C1 is higher than D1;
(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 C1 is not higher than D1; 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.
-
Specification