An evolutionary approach for discovering changing patterns in historical data

In this paper, we propose a new data mining approach, called dAR, for discovering interesting association rules and their changes by evolutionary computation, dAR searches through huge rule spaces effectively using a genetic algorithm. It has the following characteristics: (i) it encodes a complete set of rules in one single chromosome; (ii) each allele encodes one rule and each rule is represented by some non-binary symbolic values; (iii) the evolutionary process begins with the generation of an initial set of first-order rules (i.e., rules with one condition) using a probabilistic induction technique and based on these rules, rules of higher order (two or more conditions) are obtained iteratively; (iv) it adopts a steady-state reproduction scheme in which only two chromosomes are replaced every time; (v) when identifying interesting rules, an objective interestingness measure is used; and (vi) the fitness of a chromosome is defined in terms of the probability that the attribute values of a tuple can be correctly determined using the rules it encodes. Furthermore, dAR can also be used to mine the changes in discovered rules over time. This allows the accurate prediction of the future based on the historical data in the past. The experimental results on a synthetic database have shown that dAR is very effective at mining interesting association rules and their changes over time.