TFI-Apriori: Using new encoding to optimize the apriori algorithm

摘要

In this paper we propose a new optimization for Apriori-based association rule mining algorithms where the frequency of items can be encoded and treated in a special manner drastically increasing the efficiency of the frequent itemset mining process. An efficient algorithm, called TFI-Apriori, is developed for mining the complete set of frequent itemsets. In the preprocessing phase of the proposed algorithm, the most frequent items from the database are selected and encoded. The TFI-Apriori algorithm then takes advantage of the encoded information to decrease the number of candidate itemsets generated in the mining process, and consequently drastically reduces execution time in candidate generation and support counting phases. Experimental results on actual datasets - databases coming from applications with very frequent items - demonstrate how the proposed algorithm is an order of magnitude faster than the classical Apriori approach without any loss in generation of the complete set of frequent itemsets. Additionally, TFI-Apriori has a smaller memory requirement than the traditional Apriori-based algorithms and embedding this new optimization approach in well-known implementations of the Apriori algorithm allows reuse of existing processing flows.