US6182058B1 — Bayes rule based and decision tree hybrid classif…

Claim 1

Independent Claim 103 words

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.

Claim 2

Dependent Claim 103 words

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.

Claim 3

Independent Claim 91 words

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.

Claim 4

Independent Claim 91 words

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.

Claim 5

Independent Claim 176 words

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 1 of a Bayes classifier at the root-node; (b) estimating utility D 1 of a split into a plurality of child-nodes with a Bayes classifier at the child-nodes; (c) determining if C 1 is higher than D 1 , if C 1 is higher than D 1 , making said root-node a leaf-node with a Bayes classifier; if C 1 is not higher than D 1 , 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.

Claim 6

Independent Claim 176 words

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 1 of a Bayes classifier at the root-node; (b) estimating utility D 1 of a split into a plurality of child-nodes with a Bayes classifier at the child-nodes; (c) determining if C 1 is higher than D 1 , if C 1 is higher than D 1 , making said root-node a leaf-node with a Bayes classifier; if C 1 is not higher than D 1 , 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.

Claim 7

Dependent Claim 22 words

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

Claim 8

Dependent Claim 37 words

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.

Claim 9

Dependent Claim 36 words

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

Claim 10

Dependent Claim 32 words

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.

Claim 11

Dependent Claim 50 words

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.

Claim 12

Independent Claim 229 words

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 i u(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.

Claim 13

Independent Claim 229 words

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 i u(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.

Claim 14

Independent Claim 201 words

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 1 of a Bayes classifier at the root-node; (b) means for estimating utility D 1 of a split into a plurality of child-nodes with a Bayes classifier at the child-nodes; (c) means for determining if C 1 is higher than D 1 ; (d) means for making said root-node a leaf-node with a Bayes classifier if C 1 is higher than D 1 ; (e) means for making said root node a decision-node, and partitioning the instances into a plurality of child-nodes, if C 1 is not higher than D 1 ; 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.

Claim 15

Independent Claim 201 words

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 1 of a Bayes classifier at the root-node; (b) means for estimating utility D 1 of a split into a plurality of child-nodes with a Bayes classifier at the child-nodes; (c) means for determining if C 1 is higher than D 1 ; (d) means for making said root-node a leaf-node with a Bayes classifier if C 1 is higher than D 1 ; (e) means for making said root node a decision-node, and partitioning the instances into a plurality of child-nodes, if C 1 is not higher than D 1 ; 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.

Claim 16

Dependent Claim 233 words

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 1 of a Bayes classifier at the root-node; (b) computer readable program code means for estimating utility D 1 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 1 is higher than D 1 ; (d) computer readable program code means for making said root-node a leaf-node with a Bayes classifier if C 1 is higher than D 1 ; (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 1 is not higher than D 1 ; 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.

Claim 17

Dependent Claim 233 words

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 1 of a Bayes classifier at the root-node; (b) computer readable program code means for estimating utility D 1 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 1 is higher than D 1 ; (d) computer readable program code means for making said root-node a leaf-node with a Bayes classifier if C 1 is higher than D 1 ; (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 1 is not higher than D 1 ; 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.

Claim 18

Dependent Claim 18 words

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

Claim 19

Dependent Claim 110 words

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.

Claim 20

Dependent Claim 110 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2004-01-30	2004-07-31	2005-01-30	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2008-01-30	2008-07-31	2009-01-30	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2012-01-30	2012-07-31	2013-01-30	$7700.00	Window Closed / Lapsed

Bayes rule based and decision tree hybrid classifier

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag