关键词: 频繁项集, 2-项集剪枝, 散列表, 首项分组, 索引表

Abstract: Apriori algorithm is a classic algorithm in frequent itemsets mining. In view of the shortcomings of pruning operations and multiply scanning data set in Apriori, a Hash-based Frequent itemsets Grouping algorithm, named HFG was put forward. In this paper, 2-length itemsets pruning property was proved, frequent 2-length itemsets were stored based on Hash list, the time complexity of Apriori algorithm in pruning operation was dropped from O(k×|Lk|) to O(1); the concept of sub-itemset of first term was defined, dataset was divided into subsets with Ii as first item and stored by grouping index list. Therefore, only the sub data set with Ii as the first item was scanned to find the frequent itemsets, and the time cost of scanning dataset was reduced. The experimental results show that the HFG algorithm is much more efficient than Apriori algorithm in time performance because of the cumulative benefits of pruning operations and skipping the invalid itemsets and records in HFG algorithm.

Key words: frequent itemset, 2-length itemset pruning, Hash list, first term grouping, index list