Mining Nonderivable Association Rules Using a Genetic Algorithm and a Tree-Based Pruning Technique

Association rule mining is a method for searching databases for patterns or co-occurrences in data. The fundamental step in extracting association rules is mining frequent item sets. However, the itemsets extracted were found to have redundancy in them. This study aims to tackle the redundancy present in the generated association rules and itemsets. One commonly used technique to address redundancy is extracting nonderivable itemsets. The traditional approach in mining such itemsets involved checking for upper and lower bound inequalities by making a breadth-wise search of the dataset. However, this generated many candidate itemsets, increasing the algorithm’s run time and memory consumption. Therefore, it became imperative to develop a technique that addressed these shortcomings. A new approach utilizing a genetic algorithm has been proposed to extract the necessary nonderivable itemsets. To our knowledge, such an approach has not been incorporated so far in extracting nonderivable itemsets. Here operations such as crossover and mutation are applied to generate the required itemsets and this was found to be faster and more efficient in memory in comparison to existing approaches based on distribution and discretization of data. Another problem of pressing concern is the redundancy that prevailed in the association rules that were extracted from the mined itemsets. Traditional approaches involved making repeated scans of the mined collection of association rules to prune out redundant rules. Due to this, the algorithm’s runtime increased. To handle this drawback our work proposes a novel approach based on tree-based pruning to remove redundant association rules. The left and right expansion principles provide the foundation of the tree’s construction. The Minimal Antecedent and Maximal Consequent concepts are used to eliminate redundant rules and produce the necessary set of nonderivable association rules. Based on the findings of this study, it is evident that the suggested method improves run time overall by 48.77% and memory by 35.65%. Concerning metrics such as Precision, Recall, and Accuracy an aggregate improvement of 94.92%, 90.8%, and 91.21% was observed in comparison to existing approaches.