Method and apparatus to model the variables of a data set

• US 6,480,832 B2
• Filed: 01/14/1999
• Issued: 11/12/2002
• Est. Priority Date: 03/13/1998
• Status: Expired due to Term

• Current Assignee: NCR Corporation
• Original Assignee: NCR Corporation
• Inventors: Nakisa, Ramin C.
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/231,498
• Publication Number:
  US 20020062296A1
• Time in Patent Office: 1,398 Days
• Field of Search: 706/13, 706/16, 706/45, 706/46, 706/59
• US Class Current: 706/13
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

The present invention relates to modeling the variables of a data set by means of a robabilistic network including data nodes and causal links. The term ‘probabilistic networks’ includes Bayesian networks, belief networks, causal networks and knowledge maps. The variables of an input data set are registered and a population of genomes is generated each of which individually models the input data set. Each genome has a chromosome to represent the data nodes in a probabilistic network and a chromosome to represent the causal links between the data nodes. A crossover operation is performed between the chromosome data of parent genomes in the population to generate offspring genomes. The offspring genomes are then added to the genome population. A scoring operation is performed on genomes in the said population to derive scores representing the correspondence between the genomes and the input data. Genomes are selected from the population according to their scores and the crossover, scoring, addition and selecting operations for a plurality of generations of the genomes. Finally a genome is selected from the last generation according to the best score. A mutation operation may be performed on the genomes. The mutation may consist of the addition or deletion of a data node and the addition or deletion of a causal link.

Claims

1. A method of modeling the variables in an input data set by means of a probabilistic network including data nodes and causal links, said input data set containing statistical data relating to at least a portion of a population group, the variables being personal to customers of a business enterprise, the method comprising the steps of:

registering the input data set;

generating a population of genomes each individually modeling the input data set by means of chromosome data to represent the data nodes in a probabilistic network and the causal links between the data nodes;

performing a crossover operation between the chromosome data of parent genomes in the population to generate offspring genomes;

performing an addition operation to add the offspring genomes to the population;

performing a scoring operation on genomes in the population to derives scores representing the correspondence between the genomes and the input data set;

performing a selecting operation to select genomes from the population according to the scores;

repeating the crossover, scoring, addition and selecting operations for a plurality of generations of the genomes;

selecting, as an output model, a genome from the last generation; and

forming predictions relating to future behavior of said population group.

2. A method according to claim 1, further comprising the step of randomly mutating the genomes.

3. A method according to claim 2, wherein the step of randomly mutating the genomes comprises adding a data node.

4. A method according to claim 2, wherein the step of randomly mutating the genomes comprises deleting a data node.

5. A method according to claim 2, wherein the step of randomly mutating the genomes comprises adding a causal link.

6. A method according to claim 2, wherein the step of randomly mutating the genomes comprises deleting a causal link.

7. A method according to claim 1, wherein the chromosome data of each genome includes a node chromosome in the form of a linear array of node data and a causal link chromosome in the form of a matrix of causal links.

8. A method according to claim 7, wherein the crossover operation provides the offspring genomes with independently inherited node and causal link chromosomes.

9. A method according to claim 1, further comprising the step of culling genomes which fail to meet predetermined structural constraints.

10. A method according to claim 9, wherein the predetermined structural constraints comprise the exclusion of preselected causal links.

11. A method according to claim 9, wherein the predetermined structural constraints comprise the exclusion of genomes that do not represent directed acyclic graphs.

12. Apparatus for modeling the variables in an input data set by means of a probabilistic network including data nodes and causal links, said input data set containing statistical data relating to a population group, the variables being personal to customers of a business enterprise, the apparatus comprising:

data register means for registering the input data set;

generating means for generating a population of genomes each individually modeling the input data set by means of chromosome data to represent the data nodes in a probabilistic network and the causal links between the data nodes;

crossover means for performing a crossover operation between the chromosome data of parent genomes in the population to generate offspring genomes;

adding means for performing an addition operation to add the offspring genomes to the population;

scoring means for performing a scoring operation on genomes in the population to derive scores representing the correspondence between the genomes and the input data set;

selecting means for performing a selecting operation to select genomes from the population according to the scores;

control means for controlling the crossover, scoring, addition and selecting means to repeat their operations for a plurality of generations of the genomes;

output means for selecting, as an output model, a genome from the last generation; and

means for forming predictions relating to future behavior of said population group.

13. Apparatus according to claim 12, further comprising mutating means for randomly mutating the genomes.

14. Apparatus according to claim 13, wherein the mutating means is adapted for performing random mutation which comprises adding a data node.

15. Apparatus according to claim 13, wherein the mutating means is adapted for performing random mutation which comprises deleting a data node.

16. Apparatus according to claim 13, wherein the mutating means is adapted for performing random mutation which comprises adding a causal link.

17. Apparatus according to claim 13, wherein the mutating means is adapted for performing random mutation which comprises deleting a causal link.

18. Apparatus according to claim 12, wherein the generating means is adapted for generating genomes each of which includes a node chromosome in the form of a linear array of node data and a causal link chromosome in the form of a matrix of causal links.

19. Apparatus according to claim 18, wherein the crossover means is adapted for providing the offspring genomes with independently inherited node and causal link chromosomes.

20. Apparatus according to claims 12, further comprising culling means for culling genomes which fail to meet predetermined structural constraints.

21. Apparatus according to claim 20, wherein the predetermined structural constraints comprise the exclusion of preselected causal links.

22. Apparatus according to claim 20, wherein the predetermined structural constraints comprise the exclusion of genomes that do not represent directed acyclic graphs.

23. A method of data mining employing modeling the variables in an input data set to enable the reduction of the knowledge about relationships between the variables by means of a probabilistic network including data nodes and causal links, said input data set containing statistical data relating to at least a portion of a population group, the method comprising the steps of:

registering the input data set for a plurality of customers of an enterprise;

generating a population of genomes each individually modeling the input data set by means of chromosome data to represent the data nodes in a probabilistic network and the causal links between the data nodes;

performing a crossover operation between the chromosome data of parent genomes in the population to generate offspring genomes;

performing an addition operation to add the offspring genomes to the population;

performing a scoring operation on genomes in the population to derive scores representing the correspondence between the genomes and the input data set;

performing a selecting operation to select genomes from the population according to the scores;

repeating the crossover, scoring, addition and selecting operations for a plurality of generations of the genomes;

selecting, as an output model, a genome from the last generation; and

forming predictions relating to future behavior of said population group to mine data from the input data set.

24. The method of claim 23 wherein the variables comprise the age, sex, address, occupation and income data for the plurality of customers.

25. The method of claim 24 wherein the enterprise is a bank and the variables further comprise information on whether the customers use telephone banking or internet bank, which branch of the bank holds an account for a particular customer and whether the customers use the bank to purchase insurance coverage.

26. Apparatus for data mining employing modeling the variables in an input data set to enable the reduction of the knowledge about relationships between the variables by means of a probabilistic network including data nodes and causal links, said input data set containing statistical data relating to a population group, the apparatus comprising:

data register means for registering the input data set for a plurality of customers of an enterprise;

generating means for generating a population of genomes each individually modeling the input data set by means of chromosome data to represent the data nodes in a probabilistic network and the causal links between the data nodes;

crossover means for performing a crossover operation between the chromosome data of parent genomes in the population to generate offspring genomes;

adding means for performing an addition operation to add the offspring genomes to the population;

scoring means for performing a scoring operation on genomes in the population to derive scores representing the correspondence between the genomes and the input data set;

selecting means for performing a selecting operation to select genomes from the population according to the scores;

control means for controlling the crossover, scoring, addition and selecting means to repeat their operations for a plurality of generations of the genomes;

output means for selecting, as an output model, a genome from the last generation; and

means for forming predictions relating to fixture behavior of said population group to mine data from the input data set.

27. The apparatus of claim 26 wherein the data register means comprises a random access memory to receive and store data supplied to an input bus through an input port connected to an input device.

28. The apparatus of claim 26 wherein the generating means comprises a central processing unit controlled by an operating system to operate on the input data set to generate a different character string of binary numbers for each genome.