Association rule mining using evolutionary computing

Abstract

In this thesis we address the Association Rule Mining (ARM) problem of the Knowledge Discovery and Data Mining (KDD) processes. ARM is computationally very expensive due to the exponential growth of the number of rules in increasingly large databases. This causes scaling problems to ARM algorithms. The association rule mining problem is even made more complex because there are several rule quality metrics, which in some cases are either non-commensurate or conflicting.

In this thesis we we propose genetic algorithms–based techniques aimed at narrowing the existing gaps in the ARM arena including algorithmic complexity and scaling. We propose a new algorithm to generate association rules using five rule quality metrics. We also propose a new approach to generating optimal association rules using two new rule quality metrics to ensure that dominated but interesting rules are not eliminated from the resulting set of rules. We deal with ARM algorithm scaling by combining query–based dimensionality reduction techniques and dynamic allocation of fitness cases in the evaluation routine of the genetic algorithm.

Our proposed approach was thoroughly tested on both real–world databases and standard databases from the UCI repository. Results from extensive experimentation show that the proposed approach was successful in significantly improving the efficiency of the algorithm without compromising the quality of solutions. This also enabled to produce rules of comparable or superior quality to existing, well-tested commonly used algorithms. The proposed approach produce rules that are easily interpretable, understandable and interesting.