Industrial Applications of Genetic Algorithms:Data Mining Using Genetic Algorithms

Previous | Table of Contents | Next

Fitness function

If a string of four items is coded as just described, the fitness for such a string can be determined based on the frequency with which the set of four items appear within the transactions contained in the database under investigation. In addition, if a fractional number of the items in the item list appear within a transaction, the fitness value will also reflect that fraction. For example, if the item list for which a fitness value is to be determined is as follows:

and if the database, for the purpose of this discussion, contains only two transactions, as follows:

transaction 1: | 34 22 55 01 68 99 02 07 42 24
transaction 2: | 76 01 86 99 02 07 42 24

then transaction 1 contains all four items (01, 22, 68, and 07) and transaction 2 contains only two of the four items (01 and 07). If I(ti) represents the fraction of items that are contained within a single transaction ti, then I(t1) would equal 1.0 and I(t2) would equal 0.5 (2/4). If all the I(ti)s are summed over all transactions, and this sum is divided by the total number of transaction, N, then a relationship (referred to as the base fitness) between the item set and the frequency with which the items appear within the database can be obtained. Thus, the base fitness value for the item combination of 01, 22, 68, and 07 for the example database of two transactions would be:

This yields a base fitness function that can be represented as follows:

Assume:

N | = total number of transactions in the database file (sdg.db)
ti | = transaction number
I(ti) | = fraction of items that are contained in ti
M | = sum of all I(ti) over all transactions

then M is:

and the fitness, referred to as F1, for a given string of items is:

Furthermore, in an effort to avoid possible premature convergence, and to promote competition between strings throughout a simulation, a scaled fitness, F2, was implemented and tested. F2 is expressed as,

where F2 is the scaled fitness, F1 is the raw fitness, and a and b are determined based on the maximum and average raw fitness values. In the case of the data mining problem, the maximum possible fitness (if every transaction in the database contained all four items of interest) was 1.0 and the average raw fitness was found to be around 0.4.

In a third alternative, the fitness function was based on the following additional assumptions: Since the goal is to determine the four items that are most often purchased together, the fitness function should yield a higher value if more of the items in the item set are contained together within the database transactions. For example, if one item set yielded a base fitness value of 0.25 (implying that, on average, one of the four items in the item set were contained in each of the database transactions) and a second item set yielded a base fitness value of 0.75 (implying that, on average, three of the four items in the item set were contained in each of the database transactions), it may be desirable to give more than a simple linear emphasis to the second item set value since it is closer to the goal of four. Thus, a third fitness, referred to as F3, is expressed as

where x was chosen to be 3.

While this type of fitness expression gives more emphasis to item sets that are closer to the four item goal, it must be realized that a single occurrence of four items purchased together within a large database will not yield a higher fitness than three of the items purchased together many times. Since we are seeking trends within a large set of database transactions, it was felt to be more important to recognize major trends (such as three items purchased together many times) which might lead to a trend of four items purchased together.

The results of simulations run with each of the fitness expressions just described (F1, F2, and F3) are discussed in the section, “Fitness Function Simulation Results.” Those results show that fitness function F3 provided very good performance, better than both F1 and F2.

Reproduction, Crossover, and Mutation Operators

The reproduction, crossover, and mutation operators that were implemented to support the eight-digit decimal coding are discussed next.

Reproduction Operator

A basic roulette wheel reproduction operator was implemented for this data mining application. In this type of reproduction, each string in the population is given a roulette wheel slot sized in proportion to its fitness. Then, by “spinning” the wheel N times (the population size), N new offspring are created for the next generation. By having a weighted, or “biased” roulette wheel, it is more probable that higher fit strings receive more copies in subsequent generations.

Previous | Table of Contents | Next

Copyright © CRC Press LLC