AC-Close: Efficiently Mining Approximate Closed Itemsets by Core Pattern Recovery

Recent studies have proposed methods to discover approximate frequent itemsets in the presence of random noise. By relaxing the rigid requirement of exact frequent pattern mining, some interesting patterns, which would previously be fragmented by exact pattern mining methods due to the random noise or measurement error, are successfully recovered. Unfortunately, a large number of "uninteresting" candidates are explored as well during the mining process, as a result of the relaxed pattern mining methodology. This severely slows down the mining process. Even worse, it is hard for an end user to distinguish the recovered interesting patterns from these uninteresting ones. In this paper, we propose an efficient algorithm AC-Close to recover the approximate closed itemsets from "core patterns". By focusing on the so-called core patterns, integrated with a top-down mining and several effective pruning strategies, the algorithm narrows down the search space to those potentially interesting ones. Experimental results show that AC-Close substantially outperforms the previously proposed method in terms of efficiency, while delivers a similar set of interesting recovered patterns.