Industrial Applications of Genetic Algorithms:Data Mining Using Genetic Algorithms

Previous | Table of Contents | Next

Approximate Function Evaluation Simulation

The approximate function evaluation simulation was run with the fitness function, crossover operator, mutation operator, genetic algorithm parameters, and database configuration as noted in the simulation test matrix.

The approximate function evaluation simulation used the same database configuration as that in the full function simulation; however, only one tenth (500) of the database transactions were sampled to generate the fitness for a given item combination. The total running time for this simulation was 5.1 minutes.

As can be seen from Figure 9.19, the item combination of interest entered the population around generation 7 and the simulation converged on the solution around generation 14. Comparing this to the corresponding simulation run with the full function evaluation, we can see that the approximate function evaluation simulation performed equally as well as the full function evaluation simulation in terms of convergence to the solution. In terms of execution speed, the approximate function evaluation simulation performed 8.53 times better than the full function evaluation simulation.

Figure 9.19 Simulation 18 results.

Performance Simulation Summary

The approximate function evaluation simulation, for the data set examined in this test, converged on the solution in the same number of generations as the full function evaluation simulation. In terms of execution speed, however, the approximate function evaluation simulation performed 8.53 times better than the full function evaluation simulation. Thus, it appears that if the data set is fairly large, an approximate function evaluation method can find a solution much more efficiently than when a full function evaluation method is used.

SUMMARY

This chapter presented the results of a genetic algorithm implementation for a data mining application. The goal of this genetic algorithm implementation was to be able to determine, from a synthetically generated database, the four items that most often appeared together in a transaction. Through experimentation with a variety of fitness functions, crossover operators, mutation operators, and genetic algorithm parameters, the simulation results just presented provide evidence that this goal was achieved.

The development of the data mining genetic algorithm involved, first, the determination of a base-10 coding scheme to represent four potentially related items numbers. Then, in an effort to better understand the operation of the genetic algorithm and to identify the best fitness and genetic operators, multiple fitness functions (F1, F2, and F3), crossover operators (ASPX and UXSCO), and mutation operators (random and window) were developed and targeted for investigation through simulation. In addition to fitness and genetic operators, genetic algorithm parameters and performance were also targeted for investigation.

Also, a synthetic data generation tool was developed to enable production of data sets containing embedded relationships between specified item numbers. This capability greatly facilitated verification and analysis of the genetic algorithm implementation and simulations.

After determining the areas that were to be investigated, a simulation test matrix was created to define the tests and environments that were to be run. The execution of the defined tests led to the determination of a specific fitness function and set of genetic operators that provided the best results. The final fitness function and set of genetic operators that exhibited the best overall performance and determination of correct solutions included the following (each of which have been previously described):

Fitness function: | F3
Reproduction Operator: | Roulette Wheel
Crossover Operator: | Aligned Single-Point Crossover (ASPX)
Mutation Operator: | Random

Genetic Algorithm Parameters2 |
Population Size: | 70 (200)
Crossover Probability: | 0.9
Mutation Probability: | 0.001 (0.010)

> 2These genetic algorithm parameters provided the best “overall” performance. A higher population size (200) and mutation probability (0.010) did provide better performance in specific test scenarios.

From the results achieved in this project, it is apparent that the use of genetic algorithms in data mining applications shows considerable promise and potential for further research and application. The genetic algorithm displayed its ability to quickly and efficiently locate and converge on correct solutions in a minimal number of generations. Future research might involve the implementation and analysis of this genetic algorithm approach in a “real” database environment. In addition, this project has further emphasized the fact that genetic algorithms are useful across a wide range of applications.

REFERENCES

  1 Dilly, R. (1996, February). Data mining - An introduction. The Queens University of Belfast web site http://www-pcc.qub.ac.uk/tec/courses/datamining/ohp/dm-OHP-final_1.html.
  2 Hedberg, S. R. (Winter 1995). Parallelism speeds data mining. IEEE Parallel & Distributed Technology.
  3 Author unknown (1997). Data mining - An IBM overview. IBM web site http://www.almaden.ibm.com/cs.
  4 Elmasri. R., & Navathe, S. (1994). Fundamentals of database systems. Benjamin Cummings Publishers.
  5 Fayyad, U., Piatetsky-Shapiro, G., Smyth, P., & Uthurusamy, R. (1996). Advances in knowledge discovery and data mining. AAAI Press. The MIT Press.
  6 Chung-Sheng Li, Yu, P. S., & Castelli, V. (1996, 26 February through 1 March). HierarchyScan: A hierarchical similarity search algorithm for databases of long sequences. Twelfth International Conference on Data Engineering. New Orleans, LA, USA.
  7 Goldberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison Wesley.
  8 Potter, W., Pitts, R., Gillis, P., Young, J., & Caramadre, J. (1992). IDA-NET: An intelligent decision aid for battlefield communications network configuration. New York: IEEE.

Previous | Table of Contents | Next

Copyright © CRC Press LLC