Data mining technique with experience-layered gene pool

• US 8,909,570 B1
• Filed: 07/15/2011
• Issued: 12/09/2014
• Est. Priority Date: 11/07/2008
• Status: Active Grant

• Current Assignee: Cognizant Technology Solutions U.S. Corporation (Cognizant Technology Solutions Corp.)
• Original Assignee: Genetic Finance (Barbados) Limited
• Inventors: Hodjat, Babak, Shahrzad, Hormoz, Hornby, Greg S.
• Primary Examiner(s): Hill, Stanley K
• Application Number:
  US13/184,307
• Time in Patent Office: 1,243 Days
• Field of Search: None
• US Class Current: 706/13
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06N 20/00 Machine learning
• 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 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 updated fitness estimate and their testing experience level. Preferably the gene database has an elitist pool containing multiple experience layers, and the competition module causes individuals to compete only with other individuals in their same experience layer.

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 an indication of a respective fitness estimate, and an indication of a respective testing experience level;

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 and thereby increasing the individual'"'"'s testing experience level, 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 updated fitness estimate and their testing experience level, including a first instance of considering a subject individual for discarding in dependence upon both its fitness estimate and its testing experience level, and a second instance of considering the subject individual for discarding in dependence upon both its fitness estimate and its testing experience level, and wherein the second instance occurs after the subject individual has more testing experience than at the first instance.

2. A system according to claim 1, wherein each trial of a given individual by the gene pool processor improves accuracy of the fitness estimate associated with the given individual.

3. A system according to claim 1,

wherein at the second instance the fitness estimate of the subject individual is more accurate than at the first instance.

4. A system according to claim 1, 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 each new individual formed by the procreation module begins with an experience level of zero.

5. A system according to claim 4, 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;

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

a rule in individual in the set of parent individuals corresponding to the subject new individual.

6. A system according to claim 1, wherein the training in the data mining training database comprises a plurality of data samples, each sample identifying both a plurality of indicators and a corresponding output,

and wherein each trial which the gene pool processor performs on a given individual includes applying the given individual'"'"'s conditions to the indicators identified by a given one of the data samples and determining the resulting output proposed by the given individual,

and wherein the gene pool processor develops the updated fitness estimate for the given individual in dependence upon a comparison of the output proposed by the given individual in dependence upon the indicators of the given data sample, with the output identified by the given data sample.

7. A system according to claim 1, wherein each battery of trials comprises a plurality of trials.

8. A system according to claim 1, 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<sub>T−

1</sub> including a gene capacity Quota(L_i) and a range of testing experience [ExpMin(L_i) . . . ExpMax(L_i)], the layer parameters for experience layer L_T including a gene capacity Quota(L_T) and a minimum testing experience level ExpMin(L_T),

wherein each ExpMin(L_i)>

ExpMax(L<sub>i−

1</sub>) for i>

1,

and wherein in the selection of individuals for discarding, for each j'"'"'th one of the layers in the elitist pool, the competition module discards all individuals in the elitist pool which are not among the Quota(L_j) fittest individuals whose testing experience level is in the range [ExpMin(L_j) . . . ExpMax(L_j)].

9. A system according to claim 8, wherein the individual capacities Quota(L_i) for all layers in the elitist pool are fixed.

10. A system according to claim 8, 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).

11. 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 [ExpMin(L₀) . . . ExpMax(L₀)],

wherein ExpMin(L₁)>

ExpMax(L₀),

and wherein the competition module is restricted from discarding individuals in L₀.

12. A system according to claim 11, wherein ExpMin(L_i)=ExpMax(L_i−

1)+1 for 1<

i<

=T,

and wherein ExpMin(L₀)=0.

13. A system according to claim 8, wherein:

at least as soon as the top layer L_T of the elitist pool contains Quota(L_T) individuals, the competition module establishes an elitist pool minimum fitness level; and

after the elitist pool minimum fitness level has been established, in the selection of individuals for discarding, the competition module further discards all individuals in the elitist pool which are being considered by the competition module for a first time and whose fitness estimate fails to satisfy the elitist pool minimum fitness level.

14. A system according to claim 13, wherein the elitist pool minimum fitness level is distinct from the fitness estimate of the least fit individual in layer L₁.

15. A system according to claim 13, wherein the elitist pool minimum fitness level varies as a predetermined function of the fitness level of the least fit individual in the elitist pool top layer L_T.

16. A system according to claim 13, wherein the elitist pool minimum fitness level is set as equal to the fitness level of the least fit individual in the elitist pool top layer L_T.

17. 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.

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

19. 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 in dependence upon their updated fitness estimates.

20. A system according to claim 19, 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.

21. A system according to claim 19, 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 module which receives individuals to be tested and inserts them into the client pool;

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.

22. A system according to claim 21, wherein the memory in the client further identifies layer parameters for each of a plurality of client gene pool experience layers CL₁-CL_CT in a client elitist pool, CT>

1, the layer parameters for each i'"'"'th one of the layers CL₁-CL<sub>CT−

1</sub> including a gene capacity Quota(CL_i) and a range of testing experience [ExpMin(CL_i) . . . ExpMax(CL_i)], the layer parameters for experience layer CL_CT including a gene capacity Quota(CL_CT) and a minimum testing experience level ExpMin(CL_CT),

wherein the memory further identifies layer parameters for a gene pool experience layer CL₀, the layer parameters for experience layer CL₀ including a range of testing experience [0 . . . ExpMax(CL₀)],

wherein each ExpMin(CL_i)=ExpMax(CL<sub>i−

1</sub>)+1 for i>

0,

and wherein for each j'"'"'th one of the layers in the client elitist pool, in the selection by the competition module in the client of individuals for discarding, the competition module in the client discards all individuals in the client elitist pool which are not among the Quota(CL_j) fittest individuals whose testing experience level is in the range [ExpMin(CL_j) . . . ExpMax(CL_j)].

23. A system according to claim 22, wherein:

at least as soon as the top layer CL_CT of the elitist pool in the client contains Quota(CL_CT) individuals, the competition module in the client establishes a client-centric pool minimum fitness level; and

after the client-centric pool minimum fitness level has been established, in the selection by the competition module in the client of individuals for discarding, the competition module in the client further discards all individuals in the client-centric elitist pool which are being considered by the competition module in the client for a first time and whose fitness estimate fails to satisfy the client-centric elitist pool minimum fitness level.

24. A system according to claim 22, 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 leas 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.

25. A system according to claim 24, wherein each new individual formed by the procreation module on the client begins with a client-centric experience level of zero and a client-centric fitness estimate that is undefined.

26. A system according to claim 1, wherein the training database contains a plurality of samples, each sample indicating historical market data for a security at a plurality of times in a trading day, including the price of the security at the plurality of times,

wherein each individual indicates a plurality of conditions resolvable in dependence upon the data in a given one of the samples, the outputs identified by the individuals including security trading instructions,

and wherein for each trial of a given one of the individuals being tested, the gene pool processor hypothetically performs all the trading instructions made by the given individual on a respective given one of the samples throughout the trading day of the given sample, the fitness estimate associated with the given individual being updated in dependence upon the given individual'"'"'s profit or loss for the trading day of the given sample.

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

providing a computer system having a memory having a candidate gene database identifying 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 an indication of a respective fitness estimate, each candidate individual further having associated therewith an indication of a respective testing experience level;

providing in the memory data identifying 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<sub>T−

1</sub> including a gene capacity Quota(L_i) and a range of testing experience [ExpMin(L_i) . . . ExpMax(L_i)], the layer parameters for experience layer L_T including a gene capacity Quota(L_T) and a minimum testing experience level ExpMin(L_T), each ExpMin(L_i)>

ExpMax(L<sub>i−

1</sub>) for i>

1;

testing on the training data each individual in a testing subset of at least one of the candidate individuals, each individual in the testing subset undergoing a respective battery of at least one trial, each trial applying the conditions of the respective individual to the training data to propose a result;

calculating a fitness of each of the candidate individuals in the testing subset in dependence upon the training data and the results proposed by the individual in the step of testing;

for each j'"'"'th one of the layers in the elitist pool, the computer system discarding all individuals in the elitist pool which are not among the Quota(L_j) fittest individuals whose testing experience level is in the range [ExpMin(L_j) . . . ExpMax(L_j)]; and

providing for deployment selected ones of the remaining individuals from the plurality of candidate individuals.

28. A method according to claim 27, wherein in the step of testing, the battery of trials which each individual in the testing subset undergoes includes more than one trial.

29. A method according to claim 27, wherein the testing subset excludes all individuals in the candidate gene database whose testing experience level is greater than or equal to ExpMin(L_T).

30. A method according to claim 27, 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 [ExpMin(L₀) . . . ExpMax(L₀)],

wherein ExpMin(L₁)>

ExpMax(L₀),

wherein the gene pool experience layer L₀ is not in the elitist pool,

and wherein the computer system retains without discarding all individuals whose testing experience level is in the range [ExpMin(L₀) . . . ExpMax(L₀)].

31. A method according to claim 30, wherein ExpMin(L_i)=ExpMax(L_i−

1)+1 for 1<

i<

=T,

and wherein ExpMin(L₀)=0.

32. A method according to claim 27, further comprising the steps of:

at least as soon as the top layer L_T of the elitist pool contains Quota(L_T) individuals, establishing an elitist pool minimum fitness level; and

after the elitist pool minimum fitness level has been established, discarding all individuals whose fitness estimate fails to satisfy the elitist pool minimum fitness level upon first consideration for the elitist pool.

33. A method according to claim 32, wherein the step of establishing an elitist pool minimum fitness level comprises the step of varying the elitist pool minimum fitness level as a predetermined function of the fitness level of the least fit individual in the elitist pool top layer L_T.

34. A method according to claim 32, wherein the step of establishing an elitist pool minimum fitness level comprises the step of setting the elitist pool minimum fitness level equal to the fitness level of the least fit individual in the elitist pool top layer L_T.

35. A method according to claim 27, further comprising a procreation step of forming 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.

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

37. A method according to claim 27, wherein the computer system comprises a server and a collection of at least one client device including a subject client device,

wherein the step of testing comprises the server delegating the testing to the client devices, including the subject client device,

further comprising the step of the server receiving back individuals from the client devices, including the subject client device, each received individual having associated therewith an indication of a respective client-centric fitness,

wherein the step of calculating a fitness comprises the steps of:

the subject client device calculating a client-centric fitness value for a subject one of the individuals the testing of which was delegated to the subject client device, and associating the client-centric fitness value with the subject individual; and

the server updating a server-centric fitness value for individuals received back from the client devices, including the subject individual received back from the subject client device, before the step of discarding all individuals in the elitist pool which are not among the Quota(L_j) fittest individuals whose testing experience level is in the range [ExpMin(L_j) . . . ExpMax(L_j)].

38. A method according to claim 37, further comprising the step of the server receiving from the client devices new individuals which the server had not delegated to the client devices for testing, each received new individual having associated therewith an indication of a respective client-centric fitness value,

and wherein at least some of the new individuals are included in the step of discarding all individuals in the elitist pool which are not among the Quota(L_j) fittest individuals whose testing experience level is in the range [ExpMin(L_j) . . . ExpMax(L_j)].

39. A method according to claim 37, wherein the step of the subject client device calculating a client-centric fitness value for the subject individual and associating the client-centric fitness value with the particular individual, comprises the steps of the subject client device:

storing in a client memory 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;

receiving individuals including the subject individual to be tested and inserting them into the client pool;

testing individuals including the subject individual 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;

updating 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;

selecting 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, the subject individual being retained; and

forwarding selected ones of the individuals including the subject individual from the client gene pool to the server.

40. A method according to claim 39, further comprising the steps of:

providing in the memory of the subject client identification of layer parameters for each of a plurality of client gene pool experience layers CL₁-CL_CT in a client elitist pool, CT>

1, the layer parameters for each i'"'"'th one of the layers CL₁-CL<sub>CT−

1</sub> including a gene capacity Quota(CL_i) and a range of testing experience [ExpMin(CL_i) . . . ExpMax(CL_i)], the layer parameters for experience layer CL_CT including a gene capacity Quota(CL_CT) and a minimum testing experience level ExpMin(CL_CT);

providing in the memory of the subject client identification of layer parameters for a gene pool experience layer CL₀, the layer parameters for experience layer CL₀ including a range of testing experience [0 . . . ExpMax(CL₀)],

wherein each ExpMin(CL_i)=ExpMax(CL<sub>i−

1</sub>)+1 for i>

0,

and wherein the step of the subject client device selecting individuals for discarding comprises the step of for each j'"'"'th one of the layers in the client elitist pool, the subject client device discarding all individuals in the client elitist pool which are not among the Quota(CL_j) fittest individuals whose testing experience level is in the range [ExpMin(CL_j) . . . ExpMax(CL_j)].

41. A method according to claim 39, further comprising the steps of:

at least as soon as the top layer CL_CT of the elitist pool in the subject client contains Quota(CLc_CT) individuals, establishing a client-centric elitist pool minimum fitness level; and

after the client-centric elitist pool minimum fitness level has been established, the subject client device discarding all individuals in the client-centric elitist pool which are being considered by the subject client device for a first time and whose fitness estimate fails to satisfy the client-centric elitist pool minimum fitness level.

42. A method according to claim 39, further comprising a client procreation step of the subject client device forming new individuals at least in part by copying into each given 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 given new individual; and

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

43. A method according to claim 42, wherein each new individual formed in the client procreation step begins with a client-centric experience level of zero and a client-centric fitness estimate that is undefined.

44. A method according to claim 27, wherein the training database contains a plurality of samples, each sample indicating historical market data for a security at a plurality of times in a trading day, including the price of the security at the plurality of times,

wherein each individual indicates a plurality of conditions resolvable in dependence upon the data in a given one of the samples, the outputs identified by the individuals including security trading instructions,

wherein the step of testing comprises the step of for each trial of a given one of the individuals being tested, hypothetically performing all the trading instructions made by the given individual on a respective given one of the samples throughout the trading day of the given sample,

and wherein the step of calculating a fitness comprises the step of updating the fitness estimate associated with the given individual in dependence upon the given individual'"'"'s profit or loss for the trading day of the given sample.