Data mining technique with diversity promotion

• US 8,977,581 B1
• Filed: 07/02/2012
• Issued: 03/10/2015
• Est. Priority Date: 07/15/2011
• Status: Active Grant

• Current Assignee: Cognizant Technology Solutions U.S. Corporation (Cognizant Technology Solutions Corp.)
• Original Assignee: Sentient Technologies (Barbados) Limited
• Inventors: Hodjat, Babak, Shahrzad, Hormoz
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Misir, Dave
• Application Number:
  US13/540,507
• Time in Patent Office: 981 Days
• Field of Search: 706/13
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

Roughly described, a computer-implemented evolutionary data mining system includes a memory storing a candidate gene database in which each candidate individual has a respective fitness estimate; a gene pool processor which tests individuals from the candidate gene pool on training data and updates the fitness estimate associated with the individuals in dependence upon the tests; and a gene harvesting module for deploying selected individuals from the gene pool, wherein the gene pool processor includes a competition module which selects individuals for discarding in dependence upon both their testing experience level and a diversity measure of individuals in the gene pool.

Claims

1. A computer-implemented data mining system, for use with a data mining training database containing training data, comprising:

a memory storing a candidate gene database having a pool of candidate individuals, each candidate individual identifying a plurality of conditions and at least one corresponding proposed output in dependence upon the conditions, each candidate individual further having associated therewith a respective testing experience level and an indication of a respective fitness estimate,

wherein the memory further identifies layer parameters for each of a plurality of gene pool experience layers L₁-L_T in an elitist pool, T>

1, the layer parameters for each i'"'"'th one of the layers L₁-L_T-1 identifying a range of testing experience [ExpMin(L_i) . . . ExpMax(L_i)],

and wherein each ExpMin(L_i)>

ExpMax(L<sub>i−

1</sub>) for i>

1;

a gene pool processor which;

tests individuals from the candidate gene pool on the training data, each individual being tested undergoing a respective battery of at least one trial, each trial applying the conditions of the respective individual to the training data to propose an output, and

updates the fitness estimate associated with each of the individuals being tested in dependence upon both the training data and the outputs proposed by the respective individual in the battery of trials; and

a gene harvesting module providing for deployment selected ones of the individuals from the gene pool,

wherein the gene pool processor includes a competition module which selects individuals for discarding from the gene pool in dependence upon both their testing experience level and a diversity measure of individuals in the gene pool,

and wherein the diversity measure of individuals in the gene pool comprises a first value being a diversity measure of only those individuals having an experience level within a first one of the experience layers and a second value being a diversity measure of only those individuals having an experience level within a second one of the experience layers.

2. A system according to claim 1, wherein the competition module selects individuals for discarding from the gene pool further in dependence upon their updated fitness estimate.

3. A system according to claim 1, for use as a server with respect to a collection of at least one client device,

wherein the gene pool processor includes a client delegation module which delegates to the client devices the testing of individuals from the candidate gene pool,

wherein the competition module receives back individuals from the client devices after having undergone their respective testing batteries, each received individual having associated therewith an indication of the results of its respective testing battery,

and wherein the competition module updates the fitness estimate associated with the individuals received back from the client devices in dependence upon the results of their respective testing batteries before the competition module selects individuals for discarding.

4. A system according to claim 3, wherein the competition module also receives from the client devices new individuals which the gene pool processor had not delegated to the client devices for testing, each received new individual having associated therewith an indication of the results of a respective testing battery,

and wherein the competition module, in response to receipt of the new individuals, includes them in the selection of individuals for discarding in dependence upon both their updated fitness estimate and their testing experience level.

5. A system according to claim 3, further including a subject one of the clients, the subject client comprising:

a client memory storing a client gene database having a client pool of candidate individuals, each candidate individual in the client pool identifying a plurality of conditions and at least one corresponding proposed output in dependence upon the conditions, each candidate individual in the client pool further having associated therewith a client-centric testing experience level and an indication of a respective client-centric fitness estimate;

a gene pool processor which;

tests individuals from the client candidate gene pool on the training data, each individual being tested by the client undergoing a respective client-centric battery of at least one trial, each trial by the client applying the conditions of the respective individual to the training data to propose an output, and

updates the client-centric fitness estimate associated with each of the individuals being tested by the client in dependence upon both the training data and the outputs proposed by the respective individual in the client-centric battery of trials; and

a gene harvesting module which forwards selected ones of the individuals from the client gene pool to the server,

wherein the gene pool processor in the client includes a competition module which selects individuals for discarding from the client gene pool in dependence upon both their updated client-centric fitness estimate and their client-centric testing experience level.

6. A system according to claim 3, further including a subject one of the clients, the subject client comprising:

a client memory storing a client gene database having a client pool of candidate individuals, each candidate individual in the client pool identifying a plurality of conditions and at least one corresponding proposed output in dependence upon the conditions, each candidate individual in the client pool further having associated therewith an indication of a respective client-centric fitness estimate;

a gene pool processor which;

tests individuals from the client candidate gene pool on the training data, each individual being tested by the client undergoing a respective client-centric battery of at least one trial, each trial by the client applying the conditions of the respective individual to the training data to propose an output, and

updates the client-centric fitness estimate associated with each of the individuals being tested by the client in dependence upon both the training data and the outputs proposed by the respective individual in the client-centric battery of trials; and

a gene harvesting module which forwards selected ones of the individuals from the client gene pool to the server,

wherein the gene pool processor in the client includes a competition module which selects individuals for discarding from the client gene pool in dependence upon both their testing experience level and a diversity measure of individuals in the client gene pool.

7. A system according to claim 6, wherein the client gene pool processor further includes a procreation module which forms new individuals in dependence upon a respective set of at least one parent individual from the client gene pool,

and wherein the procreation module on the client forms the new individuals at least in part by copying into each subject new individual at least one member of the group consisting of:

a condition in an individual in the set of parent individuals corresponding to the subject new individual; and

an output in an individual in the set of parent individuals corresponding to the subject new individual.

8. A computer-implemented data mining system, for use with a data mining training database containing training data, comprising:

a memory storing a candidate gene database having a pool of candidate individuals, each candidate individual identifying a plurality of conditions and at least one corresponding proposed output in dependence upon the conditions, each candidate individual further having associated therewith a respective testing experience level and an indication of a respective fitness estimate,

wherein the memory further identifies layer parameters for each of a plurality of gene pool experience layers L₁-L_T in an elitist pool, T>

1, the layer parameters for each i'"'"'th one of the layers L₁-L_T-1 identifying a range of testing experience [ExpMin(L_i) . . . ExpMax(L_i)],

and wherein each ExpMin(L_i)>

ExpMax(L<sub>i−

1</sub>) for i>

1;

a gene pool processor which;

tests individuals from the candidate gene pool on the training data, each individual being tested undergoing a respective battery of at least one trial, each trial applying the conditions of the respective individual to the training data to propose an output, and

updates the fitness estimate associated with each of the individuals being tested in dependence upon both the training data and the outputs proposed by the respective individual in the battery of trials; and

a gene harvesting module providing for deployment selected ones of the individuals from the gene pool,

wherein the gene pool processor includes a competition module which selects individuals for discarding from the gene pool in dependence upon both their testing experience level and a diversity measure of individuals in the gene pool,

and wherein in the selection of individuals for discarding, for a j'"'"'th one of the layers in the elitist pool, the gene pool processor;

selects a pair of individuals in the j'"'"'th layer which the gene pool processor determines to satisfy a predetermined measure of similarity better than another pair in the j'"'"'th layer; and

discards the least fit individual in the selected pair.

9. A system according to claim 8, wherein in the selection a pair of individuals, the gene pool processor selects the pair of individuals which, of all unique pairs of individuals in the j'"'"'th layer, best satisfies the predetermined measure of similarity.

10. A system according to claim 8, wherein in the selection of a pair of individuals, the gene pool processor:

selects a sample set of at least three but fewer than all of the individuals in the j'"'"'th layer; and

selects the pair of individuals which, of all unique pairs of individuals in the sample set, best satisfies the predetermined measure of similarity.

11. A system according to claim 10, wherein the gene pool processor selects the sample set randomly.

12. A system according to claim 10, wherein the gene pool processor selects the sample set by choosing those individuals that form unique pairs which, of all unique pairs of individuals in the j'"'"'th layer, the gene pool processor determines best satisfy a rough measure of similarity, the rough measure being less computationally intensive than the predetermined measure.

13. A system according to claim 8, wherein the layer parameters for each i'"'"'th one of the layers L₁-L_T-1 further identify a first gene capacity quota QuotaL(L_i),

and wherein in the selection of individuals for discarding, for the j'"'"'th layer, before the gene pool processor performs discarding of any least fit individual, the gene pool processor makes a determination that the number of individuals in the j'"'"'th layer exceeds QuotaL(L_j).

14. A system according to claim 13, wherein the layer parameters for each i'"'"'th one of the layers L₁-L_T-1 further identify a second gene capacity quota QuotaH(L_i), QuotaH(L_i)>

QuotaL(L_i),

and wherein in the selection of individuals for discarding, for the j'"'"'th layer, before the gene pool processor performs discarding of any least fit individual, the gene pool processor makes a determination that;

either the number of individuals in the j'"'"'th layer exceeds QuotaH(L_j);

or the individuals in the j'"'"'th layer fail to satisfy a predetermined measure of sufficient diversity.

15. A system according to claim 8, wherein the layer parameters for each i'"'"'th one of the layers L₁-L_T-1 further identify a gene capacity quota QuotaH(L_i),

and wherein in the selection of individuals for discarding, for the j'"'"'th layer, before the gene pool processor performs discarding of any least fit individual, the gene pool processor makes a determination that:

either the number of individuals in the j'"'"'th layer exceeds QuotaH(L_j);

or the individuals in the j'"'"'th layer fail to satisfy a predetermined measure of sufficient diversity.

16. A system according to claim 8, wherein the layer parameters further include a minimum testing experience ExpMin(L_T) for the layer L_T,

and wherein the gene pool processor, in testing individuals from the candidate gene pool, is restricted to testing only individuals whose testing experience level is below ExpMin(L_T).

17. A system according to claim 8, wherein the memory further identifies layer parameters for a gene pool experience layer L₀, the layer parameters for experience layer L₀ including a range of testing experience [0 . . . ExpMax(L₀)],

wherein ExpMin(L₁)>

ExpMax(L₀),

and wherein the gene pool processor is restricted from discarding individuals in L₀.

18. A system according to claim 8, wherein the gene pool processor further includes a procreation module which forms new individuals in dependence upon a respective set of at least one parent individual from the gene pool,

and wherein the procreation module forms the new individuals at least in part by copying into each subject new individual at least one member of the group consisting of:

a condition in an individual in the set of parent individuals corresponding to the subject new individual; and

an output in an individual in the set of parent individuals corresponding to the subject new individual.

19. A system according to claim 18, wherein each new individual formed by the procreation module begins with an experience level of zero and a fitness estimate that is undefined.

20. A computer-implemented data mining system, for use with a data mining training database containing training data, comprising:

a memory storing a candidate gene database having a pool of candidate individuals, each candidate individual identifying a plurality of conditions and at least one corresponding proposed output in dependence upon the conditions, each candidate individual further having associated therewith a respective testing experience level and an indication of a respective fitness estimate,

wherein the memory further identifies layer parameters for each of a plurality of gene pool experience layers L₁-L_T in an elitist pool, T>

1, the layer parameters for each i'"'"'th one of at least the layers L₁-L_T-1 identifying a range of testing experience [ExpMin(L_i) . . . ExpMax(L_i)], a first gene capacity quota QuotaL(L_i), and a second gene capacity quota QuotaH(L_i),

and wherein each QuotaH(L_i)>

QuotaL(L_i), and wherein for i>

1, each ExpMin(L_i)>

ExpMax(L<sub>i−

1</sub>);

a gene pool processor which;

tests individuals from the candidate gene pool on the training data, each individual being tested undergoing a respective battery of at least one trial, each trial applying the conditions of the respective individual to the training data to propose an output, and

updates the fitness estimate associated with each of the individuals being tested in dependence upon both the training data and the outputs proposed by the respective individual in the battery of trials; and

a gene harvesting module providing for deployment selected ones of the individuals from the gene pool,

wherein the gene pool processor includes a competition module which selects individuals for discarding from the gene pool in dependence upon both their testing experience level and a diversity measure of individuals in the gene pool,

and wherein in the selection of individuals for discarding, the gene pool processor;

identifies each j'"'"'th layer in the elitist pool for which (a) the number of individuals in the j'"'"'th layer exceeds QuotaL(Lj), and either (b) the number of individuals in the j'"'"'th layer exceeds QuotaH(Lj) or (c) the individuals in the j'"'"'th layer fail to satisfy a predetermined measure of sufficient diversity;

selects a pair of individuals in each identified j'"'"'th layer which the gene pool processor determines to satisfy a predetermined measure of similarity better than another pair in the j'"'"'th layer; and

discards the least fit individual in each selected pair.

21. A system according to claim 20, wherein in the selection of a pair of individuals, the gene pool processor:

selects a sample set of at least three but fewer than all of the individuals in the j'"'"'th layer; and

selects the pair of individuals which, of all unique pairs of individuals in the sample set, best satisfies the predetermined measure of similarity.

22. A computer-implemented data mining method, for use with a data mining training database containing training data, comprising the steps of:

providing, in a memory, a candidate gene database having a pool of candidate individuals, each candidate individual identifying a plurality of conditions and at least one corresponding proposed output in dependence upon the conditions, each candidate individual further having associated therewith a respective testing experience level and an indication of a respective fitness estimate,

wherein the memory further identifies layer parameters for each of a plurality of gene pool experience layers L₁-L_T in an elitist pool, T>

1, the layer parameters for each i'"'"'th one of the layers L₁-L_T-1 identifying a range of testing experience [ExpMin(L_i) . . . ExpMax(L_i)],

and wherein each ExpMin(L_i)>

ExpMax(L<sub>i−

1</sub>) for i>

1;

a computer system testing individuals from the candidate gene pool on the training data, each individual being tested undergoing a respective battery of at least one trial, each trial applying the conditions of the respective individual to the training data to propose an output;

updating the fitness estimate associated with each of the individuals being tested in dependence upon both the training data and the outputs proposed by the respective individual in the battery of trials;

selecting individuals for discarding from the gene pool in dependence upon both their testing experience level and a diversity measure of individuals in the gene pool; and

providing for deployment selected ones of the individuals from the gene pool,

wherein the diversity measure of individuals in the gene pool comprises a first value being a diversity measure of only those individuals having an experience level within a first one of the experience layers and a second value being a diversity measure of only those individuals having an experience level within a second one of the experience layers.

23. A method according to claim 22, further comprising a step of forming new individuals in dependence upon a respective set of at least one parent individual from the gene pool, at least in part by copying into each subject new individual at least one member of the group consisting of:

a condition in an individual in the set of parent individuals corresponding to the subject new individual; and

an output in an individual in the set of parent individuals corresponding to the subject new individual.

24. A method according to claim 23, wherein each new subject individual begins with an experience level of zero and a fitness estimate that is undefined.

25. A computer-implemented data mining method, for use with a data mining training database containing training data, comprising the steps of:

providing, in a memory, a candidate gene database having a pool of candidate individuals, each candidate individual identifying a plurality of conditions and at least one corresponding proposed output in dependence upon the conditions, each candidate individual further having associated therewith a respective testing experience level and an indication of a respective fitness estimate,

wherein the memory further identifies layer parameters for each of a plurality of gene pool experience layers L₁-L_T in an elitist pool, T>

1, the layer parameters for each i'"'"'th one of the layers L₁-L_T-1 identifying a range of testing experience [ExpMin(L_i) . . . ExpMax(L_i)],

and wherein each ExpMin(L_i)>

ExpMax(L<sub>i−

1</sub>) for i>

1;

a computer system testing individuals from the candidate gene pool on the training data, each individual being tested undergoing a respective battery of at least one trial, each trial applying the conditions of the respective individual to the training data to propose an output;

updating the fitness estimate associated with each of the individuals being tested in dependence upon both the training data and the outputs proposed by the respective individual in the battery of trials;

selecting individuals for discarding from the gene pool in dependence upon both their testing experience level and a diversity measure of individuals in the gene pool; and

providing for deployment selected ones of the individuals from the gene pool,

wherein the step of selecting individuals for discarding comprises, for a j'"'"'th one of the layers in the elitist pool;

selecting a pair of individuals in the j'"'"'th layer which the computer system determines to satisfy a predetermined measure of similarity better than another pair in the j'"'"'th layer; and

discarding the least fit individual in the selected pair.

26. A method according to claim 25, wherein the step of selecting a pair of individuals comprises selecting the pair of individuals which, of all unique pairs of individuals in the j'"'"'th layer, best satisfies the predetermined measure of similarity.

27. A method according to claim 25, wherein the step of selecting a pair of individuals comprises:

selecting a sample set of at least three but fewer than all of the individuals in the j'"'"'th layer; and

selecting the pair of individuals which, of all unique pairs of individuals in the sample set, best satisfies the predetermined measure of similarity.

28. A method according to claim 27, wherein the step of selecting a sample set comprises selecting the sample set randomly.

29. A method according to claim 27, wherein the step of selecting a sample set comprises choosing those individuals that form unique pairs which, of all unique pairs of individuals in the j'"'"'th layer, the computer system determines to best satisfy a rough measure of similarity, the rough measure being less computationally intensive than the predetermined measure.

30. A method according to claim 25, wherein the layer parameters for each i'"'"'th one of the layers L₁-L_T-1 further identify a first gene capacity quota QuotaL(L_i),

and wherein the step of selecting individuals for discarding further comprises, for the j'"'"'th layer, before discarding any least fit individual, making a determination that the number of individuals in the j'"'"'th layer exceeds QuotaL(L_j).

31. A method according to claim 30, wherein the layer parameters for each i'"'"'th one of the layers L₁-L_T-1 further identify a second gene capacity quota QuotaH(L_i), QuotaH(L_i)>

QuotaL(L_i),

and wherein the step of selecting of individuals for discarding further comprises, for the j'"'"'th layer, before discarding of any least fit individual, making a determination that;

either the number of individuals in the j'"'"'th layer exceeds QuotaH(L_j);

or the individuals in the j'"'"'th layer fail to satisfy a predetermined measure of sufficient diversity.

32. A method according to claim 25, wherein the layer parameters for each i'"'"'th one of the layers L₁-L_T-1 further identify a gene capacity quota QuotaH(L_i),

and wherein the step of selecting individuals for discarding further comprises, for the j'"'"'th layer, before discarding any least fit individual, making a determination that:

either the number of individuals in the j'"'"'th layer exceeds QuotaH(L_j);

or the individuals in the j'"'"'th layer fail to satisfy a predetermined measure of sufficient diversity.

33. A method according to claim 25, for use by a server with respect to a collection of at least one client device, wherein the step of testing individuals on the training data comprises:

delegating to at least one of the client devices the testing of individuals from the candidate gene pool; and

receiving back individuals from the client devices after having undergone their respective testing batteries, each received individual having associated therewith an indication of the results of its respective testing battery,

and wherein the step of updating comprises, before any individuals are selected in the step of selecting individuals for discarding, updating the fitness estimate associated with the individuals received back from the client devices in dependence upon the results of their respective testing batteries.