Computerized modeling method and a computer program product employing a hybrid Bayesian decision tree for classification

• US 20050246307A1
• Filed: 03/25/2005
• Published: 11/03/2005
• Est. Priority Date: 03/26/2004
• Status: Abandoned Application

• Current Assignee: Inferx Corporation
• Original Assignee: Datamat Systems Research, Inc. (Inferx Corporation)
• Inventors: Bala, Jerzy
• Application Number:
  US11/090,364
• Publication Number:
  US 20050246307A1
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

In a computerized hybrid modeling method and a computer program product for implementing the method, two classification techniques are integrated: expert elicited Bayesian networks and decision trees induced from data. Bayesian networks are a compact representation for probabilistic models and inference. They have been used successfully for many applications involving classification. The tree-based classifiers, on the other hand, have proven their ability to perform well in real world data under uncertainty. For classification purposes, the inference algorithms to compute the exact posterior probability of a target node, given observed evidence in a Bayesian network, are usually computationally intensive or impossible in a mixed model. In those cases, either the approximate results are computed using stochastic simulation methods or the model is approximated using discretization or Gaussian mixture before applying an exact inference algorithm. For a tree-based classifier, however, once the tree is constructed, the classification process is trivial. The hybrid approach synergistically combines the strengths of the two techniques. Such an approach trades off the accuracy and computation. Significant computational savings can be achieved with a minimum classification accuracy drop.

Claims

1. A computerized method for classifying data comprising the steps of:

entering an expert-generated, trainable Bayesian network into a computer;

building a decision tree in said computer for classifying incoming data incorporating said Bayesian network, dependent on a classification target for said incoming data; and

classifying said data in said computer according to said decision tree incorporating said Bayesian network.

2. A method as claimed in claim 1 wherein said decision tree comprises a plurality of leaves, and wherein the step of building said decision tree comprises:

building said decision tree in said computer with at least one of said leaves representing a strong rule in said Bayesian network wherein data has a first probability of falling into a class represented by said strong rule, and with at least one other leaf representing a weak rule of said Bayesian network having a probability substantially lower than the probability for said strong rule;

using said decision tree to make a classification decision in said computer for said incoming data if said incoming data falls on said strong leaf; and

if said incoming data does not fall on said strong leaf, using said Bayesian network in said computer to compute a posterior probability for said data falling into a class.

3. A method as claimed in claim 2 comprising employing a probability of less than or equal to 1% for designating said at least one weak leaf.

4. A method as claimed in claim 1 comprising training said decision tree in said computer incorporating said Bayesian network based on simulated data using forward sampling.

5. A method as claimed in claim 1 comprising using a dynamic Bayesian network in said computer as said Bayesian network to build said decision tree.

6. A method as claimed in claim 5 comprising building a plurality of decision trees in said computer respectively representing dynamic states for data points from different states in said dynamic Bayesian network and correlating said dynamic states.

7. A method as claimed in claim 5 comprising building an incrementally updatable tree in said computer and interfacing said updated tree with said dynamic Bayesian network.

8. A computer program product for classifying data comprising a data carrying medium having machine-readable data stored thereon for causing a computer in which said medium is loaded to:

enter an expert-generated, trainable Bayesian net;

build a decision tree for classifying incoming data incorporating said Bayesian network, dependent on a classification target for said incoming data; and

classify said data according to said decision tree incorporating said Bayesian network.

9. A computer program product as claimed in claim 8 wherein said decision tree comprises a plurality of leaves, and wherein said computer program product causes said computer to:

build said decision tree with at least one of said leaves representing a strong rule in said Bayesian network wherein data has a first probability of falling into a class represented by said strong rule, and at least one leaf representing a weak rule of said Bayesian network having a probability substantially lower than the probability for said strong rule;

use said decision tree to make a classification decision for said incoming data if said incoming data falls on said strong leaf; and

if said incoming data does not fall on said strong leaf, use said Bayesian network to compute a posterior probability for said data falling into a class.

10. A computer program product as claimed in claim 9 employing a probability of less than or equal to 1% for designating said at least one weak leaf.

11. A computer program product as claimed in claim 8 allowing training said decision tree incorporating said Bayesian network in said computer based on simulated data using forward sampling.

12. A computer program product as claimed in claim 8 employing a dynamic Bayesian network as said Bayesian network used to build said decision tree.

13. A computer program product as claimed in claim 12 causing said computer to form a plurality of decision trees respectively representing dynamic states for data points from different states in said dynamic Bayesian network and correlating said dynamic states.

14. A computer program product as claimed in claim 12 causing said computer to build an incrementally updatable tree and to interface said updated tree with said dynamic Bayesian network.