Data mining technique with position labeling

• US 9,710,764 B1
• Filed: 03/13/2014
• Issued: 07/18/2017
• 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: Kamali, Kaivan, Fink, Daniel E., Hodjat, Babak, Shahrzad, Hormoz
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Nilsson, Eric
• Application Number:
  US14/209,933
• Time in Patent Office: 1,223 Days
• Field of Search: None
• 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, individuals in both a training system and in a production system include a label field in their rule outputs. Positions entered by an individual are maintained in a status record for the individual, including the label output by the rule which triggered entry of that position. Rules that assert exiting or partial exiting of a position also output the label from the rule which triggered the assertion, and are effective only so far as matching positions exist or remain in the individual'"'"'s status record, including a matching label. Labels present in the status record also can be referenced in conditions of a rule. During evolution, a rule'"'"'s output label is subject to crossover and/or mutation just like the conditions and output assertions.

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 database having a pool of candidate individuals, each candidate individual identifying a respective set of at least two rules including an entering rule and an exiting rule, the entering rule identifying both a label to assert in dependence upon the training data and a position entering action to assert in dependence upon the training data, and the exiting rule identifying both a label to assert in dependence upon the training data and a position exiting action to assert in dependence upon the training data, each candidate individual further having associated therewith an indication of a respective fitness estimate; and

a candidate pool processor which;

tests individuals from the candidate pool on the training data, each individual being tested undergoing a respective battery of at least one trial, each trial applying the rules of the respective individual to the training data, each rule that asserts its action in response to the training data also asserting its label in response to the training data;

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

selects individuals for discarding from the candidate pool in dependence upon predetermined criteria.

2. The system of claim 1, wherein in updating the fitness estimate associated with each of the individuals, the system, in response to activation of a first exiting rule which asserts a first exiting action and a corresponding first label, the individual having the first exiting rule having associated therewith a first status record, to the extent that the first status record has a position matching the first exiting action and the first label:

updates the first status record associated with the individual having the first exiting rule to reflect the first exiting action; and

updates the fitness estimate of the individual having the first exiting rule in dependence upon the extent that the first status record has a position matching the first exiting action and the first label.

3. The system of claim 2, wherein in updating the fitness estimate associated with each of the individuals, the system, in response to activation of a second entering rule which asserts a second entering action and a corresponding second label, updates a second status record associated with the individual having the second entering rule to reflect the second entering action in association with the second label.

4. The system of claim 3, wherein the individual having the second entering rule is the same as the individual having the first exiting rule, and wherein the second status record is the same as the first status record.

5. The system of claim 1, wherein in updating the fitness estimate associated with each of the individuals, the system, in response to activation of a second entering rule which asserts a second entering action and a corresponding second label, updates a second status record associated with the individual having the second entering rule to reflect the second entering action in association with the second label.

6. The system of claim 1, wherein the exiting rule in a first one of the individuals identifies a set of at least one condition upon which assertion of the exiting rule depends,

and wherein a first one of the conditions identifies a first label.

7. The system of claim 6, wherein the label identified for assertion by the entering rule of the first individual matches the first label.

8. The system of claim 6, wherein the first condition precludes assertion of the action of the exiting rule unless a status record of the first individual has a position associated with the first label, that satisfies the first condition.

9. The system of claim 1, wherein the candidate 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 candidate pool, at least in part by copying into each subject new individual at least one item selected by the candidate pool processor from an available group of items, the available group of items including a label identified for assertion in a rule of an individual in the set of parent individuals corresponding to the subject new individual.

10. The system of claim 1, wherein each given one of the rules identifies a set of at least one condition upon which activation of the given rule depends,

and wherein the candidate 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 candidate pool, at least in part by copying into each subject new individual at least one item selected by the candidate pool processor from an available group of items, the available group of items including a condition in a rule of an individual in the set of parent individuals corresponding to the subject new individual,

wherein the condition identifies a label.

11. The system of claim 10, wherein the available group of items further includes:

a label identified for assertion in a rule of an individual in the set of parent individuals corresponding to the subject new individual;

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

an action identified for assertion in a rule in an individual in the set of parent individuals corresponding to the subject new individual.

12. The system of claim 1, wherein in updating the fitness estimate associated with each given one of the individuals, the system activates at least one of the rules of the given individual which asserts its action.

13. The system of claim 1, wherein in updating the fitness estimate associated with each given one of the individuals, the system, for each application of the rules of the given individual to the training data, selects for activation no more than one of the rules of the given individual that assert their action.

14. The system of claim 13, wherein the rules of each of the individuals have an order from first to last,

and wherein in selecting for activation no more than one of the rules of the given individual that assert their action, the system selects the lowest order one of the rules that asserts its action.

15. The system of claim 13, wherein each of the rules in each of the individuals further identifies a strength value,

and wherein in selecting for activation no more than one of the rules of the given individual that assert their action, the system selects an asserted rule that identifies the highest strength value.

16. The system of claim 13, wherein all of the actions of all of the rules of all of the individuals in the candidate pool are restricted to a limited number of categories,

and wherein in selecting for activation no more than one of the rules of the given individual that assert their action, the system:

determines a category containing the largest number of asserted rules; and

selects an asserted rule whose action falls into that category.

17. The system of claim 1, wherein the system restricts all of the labels identified for assertion by all of the rules of all of the individuals in the candidate pool, to a limited number of different labels.

18. The system of claim 1, wherein the system restricts all of the labels identified for assertion by all of the rules of all of the individuals in the candidate pool, to no more than five different labels.

19. The computer-implemented data mining system of claim 1, further comprising a harvesting module providing for deployment selected ones of the individuals from the candidate pool.

20. The computer-implemented data mining system of claim 1, wherein the predetermined criteria comprises the selected individual'"'"'s updated fitness estimate.

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

a data processor; and

a storage subsystem coupled to the data processor and having stored therein in a non-transitory manner a candidate database having a plurality of candidate individuals, each candidate individual identifying a respective set of at least two rules including an entering rule and an exiting rule, the entering rule identifying both a label to assert in dependence upon the training data and a position entering action to assert in dependence upon the training data, and the exiting rule identifying both a label to assert in dependence upon the training data and a position exiting action to assert in dependence upon the training data, each candidate individual further having associated therewith an indication of a respective fitness estimate.

22. The system of claim 21, wherein the storage subsystem further has stored therein in a non-transitory manner a status record corresponding to each of the candidate individuals, each of the status records indicating all positions of the corresponding candidate individual resulting from prior activation of entering and exiting rules of the corresponding candidate individual, the status records also indicating a label for at least each non-zero position.

23. The system of claim 21, wherein a particular one of the rules in a particular one of the candidate individuals identifies a set of at least one condition upon which assertion of the particular rule depends,

and wherein a particular one of the conditions identifies a particular label.

24. The system of claim 23, wherein the label identified for assertion by the entering rule of the particular individual matches the particular label.

25. The system of claim 23, wherein the particular condition precludes assertion of the action of the particular rule unless a status record of the particular individual has a position associated with the particular label, that satisfies the condition.

26. A computer-implemented system, for use with an ordered sequence of input data, comprising:

a processor; and

a storage subsystem coupled to the processor and having stored therein in a non-transitory manner a pool of at least one individual, each individual identifying a respective set of at least two rules including an entering rule and an exiting rule, the entering rule identifying both a label to assert in dependence upon the input data and a position entering action to assert in dependence upon the input data, and the exiting rule identifying both a label to assert in dependence upon the input data and a position exiting action to assert in dependence upon the input data, each individual further having a status record associated therewith,

wherein the processor, for each given individual in the pool;

applies the rules of the given individual to the input data, each rule that asserts its action in response to the input data also asserting its label in response to the input data; and

in response to activation of a given rule that asserts its action;

outputs a signal toward a controlled system in dependence upon the action of the given rule, and

updates a status record associated with the given individual in dependence upon both the action of the given rule and the label of the given rule.

27. The system of claim 26, wherein the processor, in updating the status record of the given individual in response to activation of an entering rule which asserts a first entering action and a corresponding first label, updates the status record of the given individual to reflect both an increase in a position identified by the first entering action and an association of either the increase or the position or both with the first label.

28. The system of claim 27, wherein the processor, in updating the status record of the given individual in response to activation of an exiting rule which asserts a second exiting action and a corresponding second label, updates the status record of the given individual only to the extent that the status record of the given individual has a position matching the second exiting action and the second label.

29. The system of claim 28, wherein the processor, in outputting a signal toward a controlled system in response to activation of the second exiting rule, limits any exiting order in the signal, to the extent that the status record of the given individual has a position matching the second exiting action and the second label.

30. The system of claim 26, wherein the processor, in updating the status record of the given individual in response to activation of an exiting rule which asserts a second exiting action and a corresponding second label, updates the status record of the given individual only to the extent that the status record of the given individual has a position matching the second exiting action and the second label.

31. The system of claim 26, wherein a particular one of the rules of the given individual identifies a set of at least one condition upon which assertion of the particular rule depends,

and wherein a first one of the conditions identifies particular label.

32. The system of claim 31, wherein the label identified for assertion by the entering rule of the first individual matches the particular label.

33. The system of claim 31, wherein the particular condition precludes assertion of the action of the particular rule unless the status record of the given individual has a position associated with the particular label, that satisfies the particular condition.

34. The system of claim 26, wherein the processor, in applying the rules of the given individual to the input data, activates at least one of the rules of the given individual which asserts its action.

35. A method for data mining, for use with a data mining training database containing training data, comprising:

storing in a memory, a candidate database having a pool of candidate individuals, each candidate individual identifying a respective set of at least two rules including an entering rule and an exiting rule, the entering rule identifying both a label to assert in dependence upon the training data and a position entering action to assert in dependence upon the training data, and the exiting rule identifying both a label to assert in dependence upon the training data and a position exiting action to assert in dependence upon the training data, each candidate individual further having associated therewith an indication of a respective fitness estimate;

a candidate pool processor testing individuals from the candidate pool on the training data, each individual being tested undergoing a respective battery of at least one trial, each trial applying the rules of the respective individual to the training data, each rule that asserts its action in response to the training data also asserting its label in response to the training data;

the candidate pool processor updating the fitness estimate associated with each of the individuals being tested in dependence upon both the training data and the actions and labels asserted by the rules in the respective individual in the battery of trials; and

the candidate pool processor selecting individuals for discarding from the candidate pool in dependence upon predefined criteria.

36. The method for data mining of claim 35, further comprising providing by a harvesting module deployment of selected ones of the individuals from the candidate pool.

37. The method for data mining of claim 35, wherein the predetermined criteria comprises the selected individual'"'"'s updated fitness estimate.

38. A method for data mining, for use with a data mining training database containing training data, comprising:

storing in a non-transitory manner in a storage subsystem coupled to a data processor, a candidate database having a plurality of candidate individuals, each candidate individual identifying a respective set of at least two rules including an entering rule and an exiting rule, the entering rule identifying both a label to assert in dependence upon the training data and a position entering action to assert in dependence upon the training data, and the exiting rule identifying both a label to assert in dependence upon the training data and a position exiting action to assert in dependence upon the training data, each candidate individual further having associated therewith an indication of a respective fitness estimate.

39. A method for processing an ordered sequence of input data, comprising:

storing in a non-transitory manner in a storage subsystem coupled to a data processor, a pool of at least one individual, each individual identifying a respective set of at least two rules including an entering rule and an exiting rule, the entering rule identifying both a label to assert in dependence upon the input data and a position entering action to assert in dependence upon the input data, and the exiting rule identifying both a label to assert in dependence upon the input data and a position exiting action to assert in dependence upon the input data, each individual further having a status record associated therewith; and

for each given individual in the pool;

applying the rules of the given individual to the input data, each rule that asserts its action in response to the input data also asserting its label in response to the input data, and

in response to activation of a given rule that asserts its action;

outputting a signal toward a controlled system in dependence upon the action of the given rule; and

updating a status record associated with the given individual in dependence upon both the action of the given rule and the label of the given rule.

40. A computer-readable medium for implementing a data mining system and for use with a data mining training database containing training data,

the medium having stored thereon in a non-transitory manner a candidate database having a pool of candidate individuals, each candidate individual identifying a respective set of at least two rules including an entering rule and an exiting rule, the entering rule identifying both a label to assert in dependence upon the training data and a position entering action to assert in dependence upon the training data, and the exiting rule identifying both a label to assert in dependence upon the training data and a position exiting action to assert in dependence upon the training data, each candidate individual further having associated therewith an indication of a respective fitness estimate;

the medium further having stored thereon in a non-transitory manner a plurality of software code portions which define logic for implementing a candidate pool processor which;

tests individuals from the candidate pool on the training data, each individual being tested undergoing a respective battery of at least one trial, each trial applying the rules of the respective individual to the training data, each rule that asserts its action in response to the training data also asserting its label in response to the training data,

updates the fitness estimate associated with each of the individuals being tested in dependence upon both the training data and the actions and labels asserted by the rules in the respective individual in the battery of trials, and

selects individuals for discarding from the candidate pool in dependence upon predetermined criteria.

41. The computer-readable medium of claim 40, the medium further having stored thereon in a non-transitory manner a plurality of software code portions which define logic for implementing a harvesting module providing for deployment selected ones of the individuals from the candidate pool.

42. The computer-readable medium of claim 40, wherein the predetermined criteria comprises the selected individual'"'"'s updated fitness estimate.

43. A computer-readable medium for implementing a data mining system and for use with a data mining training database containing training data,

the medium having stored therein in a non-transitory manner a candidate database having a plurality of candidate individuals, each candidate individual identifying a respective set of at least two rules including an entering rule and an exiting rule, the entering rule identifying both a label to assert in dependence upon the training data and a position entering action to assert in dependence upon the training data, and the exiting rule identifying both a label to assert in dependence upon the training data and a position exiting action to assert in dependence upon the training data, each candidate individual further having associated therewith an indication of a respective fitness estimate.

44. A computer readable medium, for use with an ordered sequence of input data, the medium having stored therein in a non-transitory manner a pool of at least one individual, each individual identifying a respective set of at least two rules including an entering rule and an exiting rule, the entering rule identifying both a label to assert in dependence upon the input data and a position entering action to assert in dependence upon the input data, and the exiting rule identifying both a label to assert in dependence upon the input data and a position exiting action to assert in dependence upon the input data, each individual further having a status record associated therewith,

the medium further having stored thereon in a non-transitory manner a plurality of software code portions which define logic for, for each given individual in the pool:

applying the rules of the given individual to the input data, each rule that asserts its action in response to the input data also asserting its label in response to the input data; and

in response to activation of a given rule that asserts its action;

outputting a signal toward a controlled system in dependence upon the action of the given rule, and

updating a status record associated with the given individual in dependence upon both the action of the given rule and the label of the given rule.

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

storage means for storing a candidate database having a pool of candidate individuals, each candidate individual identifying a respective set of at least two rules including an entering rule and an exiting rule, the entering rule identifying both a label to assert in dependence upon the training data and a position entering action to assert in dependence upon the training data, and the exiting rule identifying both a label to assert in dependence upon the training data and a position exiting action to assert in dependence upon the training data, each candidate individual further having associated therewith an indication of a respective fitness estimate; and

candidate pool processor means for;

testing individuals from the candidate pool on the training data, each individual being tested undergoing a respective battery of at least one trial, each trial applying the rules of the respective individual to the training data, each rule that asserts its action in response to the training data also asserting its label in response to the training data;

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

selecting individuals for discarding from the candidate pool in dependence upon their updated fitness estimate.

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

storage means for storing in a non-transitory manner a candidate database having a plurality of candidate individuals, each candidate individual identifying a respective set of at least two rules including an entering rule and an exiting rule, the entering rule identifying both a label to assert in dependence upon the training data and a position entering action to assert in dependence upon the training data, and the exiting rule identifying both a label to assert in dependence upon the training data and a position exiting action to assert in dependence upon the training data, each candidate individual further having associated therewith an indication of a respective fitness estimate.

47. A computer-implemented data mining system, for use with an ordered sequence of input data, comprising:

storage means for storing in a non-transitory manner a pool of at least one individual, each individual identifying a respective set of at least two rules including an entering rule and an exiting rule, the entering rule identifying both a label to assert in dependence upon the input data and a position entering action to assert in dependence upon the input data, and the exiting rule identifying both a label to assert in dependence upon the input data and a position exiting action to assert in dependence upon the input data, each individual further having a status record associated therewith, and

processing means for, for each given individual in the pool;

applying the rules of the given individual to the input data, each rule that asserts its action in response to the input data also asserting its label in response to the input data; and

in response to activation of a given rule that asserts its action;

outputting a signal toward a controlled system in dependence upon the action of the given rule, and

updating a status record associated with the given individual in dependence upon both the action of the given rule and the label of the given rule.