An efficient incremental mining algorithm-QSD

摘要

The generation of frequent itemsets is an essential and time-consuming step in mining association rules. Most of the studies adopt the Apriori-based approach, which has great effort in generating candidate itemsets and needs multiple database accesses. Recent studies indicate that FP-tree approach has been utilized to avoid the generation of candidate itemsets and scan transaction database only twice, but they work with more complicated data structure. Besides, it needs to adjust the structure of FP-tree when it applied to incremental mining application. It is necessary to adjust the position of an item upward or downward in the structure of FP-tree when a new transaction increases or decreases the accumulation of the item. The process of the adjustment of the structure of FP-tree is the bottlenecks of the FP-tree in incremental mining application. Therefore, algorithms for efficient mining of frequent patterns are in urgent demand. This paper aims to improve both time and space efficiency in mining frequent itemsets and incremental mining application. We propose a novel QSD (Quick Simple Decomposition) algorithm using simple decompose principle which derived from minimal heap tree, we can discover the frequent itemsets quickly under one database scan. Meanwhile, QSD algorithm doesn't need to scan database and reconstruct data structure again when database is updated or minimum support is varied. It can be applied to on-line incremental mining applications without any modification. Comprehensive experiments have been conducted to assess the performance of the proposed algorithm. The experimental results show that the QSD algorithm outperforms previous algorithms.