Adaptive Bayes Network data mining modeling

• US 6,973,459 B1
• Filed: 10/21/2002
• Issued: 12/06/2005
• Est. Priority Date: 05/10/2002
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Yarmus, Joseph S.
• Primary Examiner(s): Wassum, Luke S
• Assistant Examiner(s): Black, Linh
• Application Number:
  US10/274,039
• Time in Patent Office: 1,142 Days
• Field of Search: 707 1-1041
• US Class Current: 707/778
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method, system, and computer program product for generating an Adaptive Bayes Network data mining model includes receiving a data table having a plurality of predictor columns and a target column, constructing a plurality of single-predictor models, ranking each single-predictor model using minimum description length and selecting a best single predictor model, performing feature selection, constructing a Naïve Bayes model, comparing a description length of the Naive Bayes model with a description length of a baseline model, replacing the baseline model with the Naïve Bayes model, if the description length of the Naive Bayes model is less than the description length of the baseline model, extending a plurality of single-predictor models in rank order, stepwise, to multi-predictor features, and testing whether each new feature should be included in or should replace a current model state using minimum description length.

Claims

1. A method of generating an Adaptive Bayes Network data mining model comprising the steps of:

receiving a data table having a plurality of predictor columns and a target column and comprising a plurality of rows of data;

constructing a plurality of single-predictor models, comprising the steps of;

computing a description length of a baseline model based on unconditional target probabilities among the plurality of rows;

determining which predictor columns are correlated to the target column based on minimum description length;

computing probabilities of at least two target values of the target column conditioned on at least two predictor values of at least one correlated predictor column; and

computing a probability of at least one correlated predictor column conditioned on the at least two target values;

ranking each predictor column by ranking each single-predictor model using minimum description length and selecting a best single predictor model;

performing feature selection based on a minimum of a specified number of predictors and as a function of a reduction in entropy attributable to the best single predictor model;

constructing a Naï

ve Bayes model using a top-ranked portion of the plurality of predictor columns;

comparing a description length of the Naive Bayes model with a description length of a baseline model;

replacing the baseline model with the Naï

ve Bayes model, if the description length of the Naive Bayes model is less than the description length of the baseline model;

extending a plurality of single-predictor models in rank order, stepwise, to multi-predictor features; and

testing whether each new feature should be included in or should replace a current model state using minimum description length.

2. The method of claim 1, wherein the step of constructing a plurality of single-predictor models further comprises the step of binning values included in the predictor columns.

3. The method of claim 2, wherein the step of ranking each predictor column by ranking each single-predictor model using minimum description length comprises the steps of:

generating histograms of the target within each predictor bin value; and

obtaining, from the histograms, smoothed probabilities of target value conditioned on predictor value estimated as a proportion of each target value within a given predictor bin value.

4. The method of claim 3, wherein the step of ranking each predictor column by ranking each single-predictor model using minimum description length comprises the step of:

computing the description length as a sum of a penalty term, Σ

log₂ (n_i+1), where n_i is a number of training row instances of an ith value of a predictor; and

a transmission cost, −

Σ

log₂(p_ij)n_ij, where p_ij is the probability of a jth target value conditioned on an ith predictor value and n_ij is a corresponding count.

5. The method of claim 4, wherein the step of extending a plurality of single-predictor models to multi predictor features comprises the steps of:

extending a portion of the plurality of single-predictor models to multi-predictor features, one predictor at a time as far as minimum description length or a maximum depth parameter permits in rank order; and

extending each model to include a portion of the plurality of multi-predictor features as far as minimum description length pruning or a maximum number of network features parameter permits.

6. The method of claim 5, further comprising the step of:

biasing against selection of predictors with many missing values by using an encoding reflecting a proportion of potential single-predictor models attributable to each predictor.

7. The method of claim 6, further comprising the step of:

applying a reduced penalty term to a product model due to bias inherent in the product model'"'"'s assumptions concerning data in the data table.

8. A system for generating an Adaptive Bayes Network data mining model comprising:

a processor operable to execute computer program instructions;

a memory operable to store computer program instructions executable by the processor; and

computer program instructions stored in the memory and executable to perform the steps of;

receiving a data table having a plurality of predictor columns and a target column and comprising a plurality of rows of data;

constructing a plurality of single-predictor models, comprising the steps of;

computing a description length of a baseline model based on unconditional target probabilities among the plurality of rows;

determining which predictor columns are correlated to the target column based on minimum description length;

computing probabilities of at least two target values of the target column conditioned on at least two predictor values of at least one correlated predictor column; and

computing a probability of at least one correlated predictor column conditioned on the at least two target values;

ranking each predictor column by ranking each single-predictor model using minimum description length and selecting a best single predictor model;

performing feature selection based on a minimum of a specified number of predictors and as a function of a reduction in entropy attributable to the best single predictor model;

constructing a Naï

ve Bayes model using a top-ranked portion of the plurality of predictor columns;

comparing a description length of the Naive Bayes model with a description length of a baseline model;

replacing the baseline model with the Naï

ve Bayes model, if the description length of the Naive Bayes model is less than the description length of the baseline model;

extending a plurality of single-predictor models in rank order, stepwise, to multi-predictor features; and

testing whether each new feature should be included in or should replace a current model state using minimum description length.

9. The system of claim 8, wherein the step of constructing a plurality of single-predictor models further comprises the step of binning values included in the predictor columns.

10. The system of claim 9, wherein the step of ranking each predictor column by ranking each single-predictor model using minimum description length comprises the steps of:

generating histograms of the target within each predictor bin value; and

obtaining, from the histograms, smoothed probabilities of target value conditioned on predictor value estimated as a proportion of each target value within a given predictor bin value.

11. The method of claim 10, wherein the step of ranking each predictor column by ranking each single-predictor model using minimum description length comprises the step of:

computing the description length as a sum of a penalty term, Σ

log₂(n_i+1), where n_i is a number of training row instances of an ith value of a predictor; and

a transmission cost, −

Σ

log₂(p_ij)n_ij, where p_ij is the probability of a jth target value conditioned on an ith predictor value and n_ij is a corresponding count.

12. The system of claim 11, wherein the step of extending a plurality of single-predictor models to multi predictor features comprises the steps of:

extending a portion of the plurality of single-predictor models to multi-predictor features, one predictor at a time as far as minimum description length or a maximum depth parameter permits in rank order; and

extending each model to include a portion of the plurality of multi-predictor features as far as minimum description length pruning or a maximum number of network features parameter permits.

13. The system of claim 12, further comprising the step of:

biasing against selection of predictors with many missing values by using an encoding reflecting a proportion of potential single-predictor models attributable to each predictor.

14. The system of claim 13, further comprising the step of:

applying a reduced penalty term to a product model due to bias inherent in the product model'"'"'s assumptions concerning data in the data table.

15. A computer program product for generating an Adaptive Bayes Network data mining model, comprising:

a computer readable medium;

computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of

receiving a data table having a plurality of predictor columns and a target column and comprising a plurality of rows of data;

constructing a plurality of single-predictor models, comprising the steps of;

computing a description length of a baseline model based on unconditional target probabilities among the plurality of rows;

determining which predictor columns are correlated to the target column based on minimum description length;

computing probabilities of at least two target values of the target column conditioned on at least two predictor values of at least one correlated predictor column; and

computing a probability of at least one correlated predictor column conditioned on the at least two target values;

ranking each predictor column by ranking each single-predictor model using minimum description length and selecting a best single predictor model;

performing feature selection based on a minimum of a specified number of predictors and as a function of a reduction in entropy attributable to the best single predictor model;

constructing a Naï

ve Bayes model using a top-ranked portion of the plurality of predictor columns;

comparing a description length of the Naive Bayes model with a description length of a baseline model;

replacing the baseline model with the Naï

ve Bayes model, if the description length of the Naive Bayes model is less than the description length of the baseline model;

extending a plurality of single-predictor models in rank order, stepwise, to multi-predictor features; and

testing whether each new feature should be included in or should replace a current model state using minimum description length.

16. The computer program product of claim 15, wherein the step of constructing a plurality of single-predictor models further comprises the step of binning values included in the predictor columns.

17. The computer program product of claim 16, wherein the step of ranking each predictor column by ranking each single-predictor model using minimum description length comprises the steps of:

generating histograms of the target within each predictor bin value; and

obtaining, from the histograms, smoothed probabilities of target value conditioned on predictor value estimated as a proportion of each target value within a given predictor bin value.

18. The computer program product of claim 17, wherein the step of ranking each predictor column by ranking each single-predictor model using minimum description length comprises the step of:

computing the description length as a sum of a penalty term, Σ

log₂(n_i+1), where n_i is a number of training row instances of an ith value of a predictor; and

a transmission cost, −

Σ

log₂(p_ij)n_ij, where p_ij is the probability of a jth target value conditioned on an ith predictor value and n_ij is a corresponding count.

19. The computer program product of claim 18, wherein the step of extending a plurality of single-predictor models to multi predictor features comprises the steps of:

extending a portion of the plurality of single-predictor models to multi-predictor features, one predictor at a time as far as minimum description length or a maximum depth parameter permits in rank order; and

extending each model to include a portion of the plurality of multi-predictor features as far as minimum description length pruning or a maximum number of network features parameter permits.

20. The computer program product of claim 19, further comprising the step of:

biasing against selection of predictors with many missing values by using an encoding reflecting a proportion of potential single-predictor models attributable to each predictor.

21. The computer program product of claim 20, further comprising the step of:

applying a reduced penalty term to a product model due to bias inherent in the product model'"'"'s assumptions concerning data in the data table.