Classification using probability estimate re-sampling

• US 20060167655A1
• Filed: 02/20/2004
• Published: 07/27/2006
• Est. Priority Date: 02/28/2003
• Status: Active Grant

• Current Assignee: Pegasystems Incorporated
• Original Assignee: Chordiant Software Europe Limited
• Inventors: Keijzer, Maarten Anton, Barrow, David
• Granted Patent: US 7,194,380 B2
• Time in Patent Office: Days
• US Class Current: 702/181
• CPC Class Codes: G06F 18/10 Pre-processing; Data cleansing
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 40/08 Insurance

Abstract

Embodiments of a computer-implemented method of calculating estimates of a joint posterior probability of class membership given combinations of attribute values of a pair of attributes are disclosed. The calculating is performed on the basis of data representing a training set of a plurality of instances defined by attribute values for a plurality of attributes together with a class membership outcome. Embodiments of the method comprise calculating first and second estimates of a posterior probability of class membership given attribute values of a first and second attribute of the pair, respectively, and binning the first and second estimates into a respective plurality of first and second probability range bins. Instances of the training set are mapped to combinations of one of each of the first and second pluralities of probability range bins, and on the basis of the mapping, calculating estimates of a joint posterior probability of class membership.

Claims

1. A computer-implemented method of calculating estimates of a joint posterior probability of class membership given combinations of attribute values of a pair of attributes, the calculating being performed on the basis of data representing a training set of a plurality of instances defined by attribute values for a plurality of attributes together with a class membership outcome, the method comprising:

a) calculating first estimates of a posterior probability of class membership given attribute values of a first attribute of the pair;

b) calculating second estimates of a posterior probability of class membership given attribute values of a second attribute of the pair;

c) binning the first estimates into a plurality of first probability range bins;

d) binning the second estimates into a plurality of second probability range bins;

e) creating a mapping of instances of the training set mapped to combinations of one of each of the first and second pluralities of probability range bins; and

f) on the basis of said mapping, calculating estimates of a joint posterior probability of class membership given membership in the combinations of first and second probability range bins.

3. A computer-implemented method of generating a model for use in classifying data representing a new instance, the model being generated on the basis of data representing a training set of a plurality of instances defined by attribute values for a plurality of attributes together with a class membership outcome, the method comprising:

a) defining a tree structure comprising one leaf node for each attribute of the plurality of attributes and one or more root/branch nodes;

b) recursively calculating estimates of a joint posterior probability of class membership given attribute values for each attribute of the plurality of attributes by;

for root/branch nodes of the tree, calculating estimates of a joint posterior probability of class membership given combinations of attribute values of attributes corresponding to the branch/leaf nodes joined by said root/branch node by performing the method of claim 1.

4. A method according to claim 3 wherein, when calculating estimates of a joint posterior probability of class membership for a root/branch node of the tree, estimates of joint posterior probabilities of class membership previously calculated in respect of one or more of the branch/leaf nodes joined by said root/branch node are binned into a plurality of probability range bins and memberships of the probability range bins are treated as attribute values.

5. A method according to claim 3, wherein the tree structure defined is a binary tree, a ternary tree, or a mixed binary/ternary tree structure.

6. A computer-implemented method of generating an aggregated model for use in classifying data representing a new instance, the model being generated on the basis of data representing a training set of a plurality of instances defined by attribute values for a plurality of attributes together with a class membership outcome, the method comprising:

a) selecting a plurality of subsets of instances of the training set;

b) on the basis of each of the subsets, performing the method of claim 3 to generate a corresponding plurality of models; and

c) combining the plurality of models to produce an aggregated model.

7. A method according to claim 1, wherein the number of bins in the pluralities of probability range bins is determined in dependence on the number of instances in the plurality of instances.

8. A method according to claim 7, wherein number of bins is in the order of the cube root of the number of instances in the plurality of instances.

9. A method according to claim 1, wherein the probability range bins are distributed on the basis of the population of plurality of instances.

10. A method according to claim 9, wherein the probability range bins are distributed using a cumulative binomial distribution function generated on the basis of the population of plurality of instances.

13. A method according to claim 1 additionally comprising a computer-implemented method of generating a model for use in classifying data representing a new instance, the model being generated on the basis of data representing a training set of a plurality of instances defined by attribute values for a plurality of attributes together with a class membership outcome, the method comprising:

selecting a first pair of attributes of the plurality of attributes;

wherein steps (a)-(f) are performed in respect of attributes of the first pair

to create a first mapping of instances of the training set;

and to calculate estimates of a first joint posterior probability of class membership; and

generating the model on the basis of the estimates of the first joint posterior probability of class membership and on the basis of the first mapping.

14. A method according to claim 13 comprising, prior to generating the model:

i) selecting a second pair of attributes of the plurality of attributes different to the first pair of attributes;

ii) performing steps b) to g) in respect of the second pair of attributes to calculate estimates of a second joint posterior probability of class membership and to create a second mapping;

wherein the model is generated on the basis of the estimates of the second joint posterior probability of class membership and on the basis of the second mapping.

15. A method according to claim 13, comprising, prior to generating the model:

i) selecting a third attribute of the plurality of attributes different to the first pair of attributes;

ii) calculating third estimates of a posterior probability of class membership given attribute values of a third attribute;

iii) binning the third estimates into a plurality of third probability range bins;

iv) binning the estimates of the first joint posterior probability of class membership into a plurality of fourth probability range bins;

v) creating a second mapping of instances of the training set mapped to combinations of one of each of the third and fourth pluralities of probability range bins;

vi) calculating estimates of a second joint posterior probability of class membership given each of the probability range bin combinations; and

wherein the model is generated on the basis of the estimates of the second joint posterior probability of class membership and on the basis of the second mapping.

2. A computer-implemented method of calculating estimates of a joint posterior probability of class membership given combinations of attribute values of a triplet of attributes, the calculating being performed on the basis of data representing a training set of a plurality of instances defined by attribute values for a plurality of attributes together with a class membership outcome, the method comprising:

a) calculating first estimates of a posterior probability of class membership given attribute values of a first attribute of the triplet;

b) calculating second estimates of a posterior probability of class membership given attribute values of a second attribute of the triplet;

c) calculating third estimates of a posterior probability of class membership given attribute values of a third attribute of the triplet;

d) binning the first estimates into a plurality of first probability range bins;

e) binning the second estimates into a plurality of second probability range bins;

f) binning the third estimates into a plurality of third probability range bins;

g) creating a mapping of instances of the training set mapped to combinations of one of each of the first, second and third pluralities of probability range bins; and

h) on the basis of said mapping, calculating estimates of a joint posterior probability of class membership given membership in the combinations of first, second and third probability range bins.

11. A computer readable storage medium having stored thereon instructions and data which, when executed by a computer, cause the computer to calculate estimates of a joint posterior probability of class membership given combinations of attribute values of a pair of attributes, the calculating being performed on the basis of data representing a training set of a plurality of instances defined by attribute values for a plurality of attributes together with a class membership outcome, and the calculating comprising:

a) calculating first estimates of a posterior probability of class membership given attribute values of a first attribute of the pair;

b) calculating second estimates of a posterior probability of class membership given attribute values of a second attribute of the pair;

c) binning the first estimates into a plurality of first probability range bins;

d) binning the second estimates into a plurality of second probability range bins;

e) creating a mapping of instances of the training set mapped to combinations of one of each of the first and second pluralities of probability range bins; and

f) on the basis of said mapping, calculating estimates of a joint posterior probability of class membership given membership in the combinations of first and second probability range bins.

12. A computer arranged to calculate estimates of a joint posterior probability of class membership given combinations of attribute values of a pair of attributes, the calculating being performed on the basis of data representing a training set of a plurality of instances defined by attribute values for a plurality of attributes together with a class membership outcome, and the calculating comprising:

a) calculating first estimates of a posterior probability of class membership given attribute values of a first attribute of the pair;

b) calculating second estimates of a posterior probability of class membership given attribute values of a second attribute of the pair;

c) binning the first estimates into a plurality of first probability range bins;

d) binning the second estimates into a plurality of second probability range bins;

e) creating a mapping of instances of the training set mapped to combinations of one of each of the first and second pluralities of probability range bins; and

f) on the basis of said mapping, calculating estimates of a joint posterior probability of class membership given membership in the combinations of first and second probability range bins.

16. A computer-implemented method of generating a model for use in classifying data representing a new instance, the model being generated on the basis of data representing a training set of a plurality of instances, each comprising attribute values for at least a first and a second attribute together with a class membership outcome, the method comprising:

a) calculating values of first estimates of a posterior probability of class membership given attribute values of the first attribute;

b) calculating values of second estimates of a posterior probability of class membership given attribute values of the second attribute;

c) mapping data corresponding to instances of the training set to data corresponding to the combined values of the first and second estimates; and

d) calculating values of estimates of a joint posterior probability of class membership given the data corresponding to the combined values of the first and second estimates.

17. A computer-implemented method of generating a model in accordance with claim 16, the method more specifically comprising:

a) selecting a first and second attribute of the plurality of attributes;

b) calculating values of first estimates of a posterior probability of class membership given attribute values of the first attribute on the basis of the training set;

c) calculating values of second estimates of a posterior probability of class membership given attribute values of the second attribute on the basis of the training set;

d) mapping instances of the training set to data corresponding to combined values of the first and second estimates; and

e) calculating values of estimates of a joint posterior probability of class membership given the data corresponding to combined values of the first and second estimates; and

f) generating the model on the basis of the calculated values of estimates of joint posterior -probability of class membership.