摘要： Apriori算法能够挖掘事物之间的关联关系，但传统Apriori算法每计算一次候选集的支持度，都需要遍历原始事务数据库，多次扫描数据库导致其效率较低。为此，提出一种基于哈希存储与事务加权的改进算法。通过哈希存储的去重特性对事务进行去重，以减少冗余计算。将项目与项集的映射存储到哈希结构中，避免计算候选集的支持度时多次扫描事务数据库。同时开启多个线程，并行计算候选集的支持度，从而提高Apriori算法的运行效率。在开源数据集上的实验结果表明，当数据集中事务条数以及重复事务数越多时，该算法相较于传统Apriori算法的性能提升越明显，其运行时间与FP-Growth算法相近但避免了FP-Growth算法内存占用过大的问题。

关键词: 关联规则, 频繁项集, 哈希存储, 事务加权, 并行计算

Abstract: The Apriori algorithm can mine the association relationships between things,but the traditional Apriori algorithm needs to traverse the original transaction database every time the support of the candidate set is calculated,which reduces the efficiency of the algorithm.To address the problem,this paper proposes an improved algorithm based on hash storage and transaction weighting.The algorithm uses the deduplication feature of hash storage to deduplicate the transactions to reduce redundant calculations.At the same time,the mapping between the transaction set and the itemset is stored in the hash structure to avoid scanning the transaction database for multiple times during the calculation of the support of the candidate set.In addition,the support of the candidate set is calculated in parallel using multiple threads to improve the efficiency of the Apriori algorithm.Experimental results on open-source datasets show that the performance improvement of the proposed algorithm over the traditional Apriori algorithm increases with the number of transactions and repeated transactions in the dataset.Its running time is similar to that of the FP-Growth algorithm while the excessive memory consumption is avoided.

Key words: association rule, frequent itemset, hash storage, transaction weighting, parallel computing

中图分类号: 

• TP391