AFOPT: An Efficient Implementation of Pattern Growth Approach.

TLDR

Pattern‑growth algorithms for frequent itemset mining vary in item search order, database representation, construction strategy, and traversal, and adaptive methods have been proposed to select effective strategies. The paper aims to present implementation techniques for an adaptive pattern‑growth algorithm, AFOPT, and evaluate its performance on frequent itemset mining datasets. AFOPT is an adaptive pattern‑growth algorithm whose implementation techniques are extended to mine closed and maximal frequent itemsets and evaluated through comprehensive experiments. Experiments show that AFOPT achieves good performance and efficiency on all tested datasets.

Abstract

In this paper, we revisit the frequent itemset mining (FIM) problem and focus on studying the pattern growth approach. Existing pattern growth algorithms differ in several dimensions: (1) item search order; (2) conditional database representation; (3) conditional database construction strategy; and (4) tree traversal strategy. They adopted different strategies on these dimensions. Several adaptive algorithms were proposed to try to find good strategies for general situations. In this paper, we described the implementation techniques of an adaptive pattern growth algorithm, called AFOPT, which demonstrated good performance on all tested datasets. We also extended the algorithm to mine closed and maximal frequent itemsets. Comprehensive experiments were conducted to demonstrate the efficiency of the proposed algorithms.