Rare-PEARs: A new multi objective evolutionary algorithm to mine rare and non-redundant quantitative association rules

摘要

Since finding quantitative association rules (QARs) is an NP-hard problem, evolutionary methods are suitable solutions for discovery QARs. Nevertheless, most of the previous evolutionary methods to discover association rules only consider frequent dependency among items in datasets. They do not pay specific attention to interestingness and non-redundancy as two critical objectives. In this paper, the proposed algorithm (Rare-PEARs) gives a chance to each rule with different length and appearance (antecedent and consequent parts of rules) to be created. Therefore, various interesting, rare or interesting and rare rules can be found. Some of these rules might be uninteresting (those that contain frequent item sets). However, we try to avoid them by Rare-PEARs. To accomplish this goal, our method decomposes the process of association rule mining into N − 1 sub-problems (N is the number of attributes, and each sub-problem is handled by an independent sub-process during Rare-PEARs execution). Each sub-process starts individually with a different initial population. It then explores the search space of its corresponding sub-problem to find rules with semi-optimal intervals for each of the attributes. This process is done by a new definition of Non-Dominated concept. Rare-PEARs uses this definition to find semi-optimal intervals for attributes during the execution of each sub-process. Finally, Rare-PEARs collects QARs from sub-processes and determines the ultimate Non-Dominated rules based on the interestingness and reliability measures. Rare-PEARs tries to maximize three objectives: interestingness, accuracy and reliability while providing vast coverage on the input dataset. We compared Rare-PEARs with ten algorithms (multi-objective, mono-objective and classical algorithms of association rule mining) over several real-world datasets. The results demonstrate high efficiency of Rare-PEARs.