事务约简和2项集支持度矩阵快速剪枝的Apriori改进算法

在Apriori算法的改进算法M-Apriori基础上,为了进一步减少不必要的数据库扫描,引入事务约简技术,提出一种改进的MR-Apriori算法.考虑到M-Apriori算法会产生大量候选项集,为了实现对候选项集快速剪枝,加入一个自定义的2项集支持度矩阵,提出第2种改进的MP-Apriori算法.将事务约简和2项集矩阵快速剪枝一起引入到 M-Apriori算法中,提出第3种改进的MRP-Apriori算法.最后,在mushroom数据集上进行实验.结果表明:加入事务约简的MR-Apriori算法和加入2项集矩阵快速剪枝的MP-Apriori算法,运行时间相比原M-Apriori算法都有较大缩减,而同时结合两种优化策略的MRP-Apriori算法运行时间最短,验证了这两种优化策略的有效性.

Improved Apriori Algorithm for Quickly Prune by Combining Transaction Reduction WithTwo-Item Set Support Matrix

Based on the M-Apriori algprithm, an improved version of the Apriori algorithm, a transaction reduction technique is introduced and an improved algorithm, MR-Apriori, is proposed in the paper in order to further reduce unnessary database scans; Meanwhile, considering that the M-Apriori algorithm generates large amount of candidate itemsets during the running process, so as to quickly prune the candidate itemsets, a self-defined two-item set support matrix is added and a second improved algorithm, MP-Aproiri, is proposed in the paper. Then transaction reduction, accompanied by two-item set support matrix which is used to quickly prune the candidate itemsets, are combined together and a third improved algorithm, MRP-Aproiri, is proposed in the paper. Finally, an experiment is conducted on the mushroom dataset, the result shows that the MR-Apriori algorithm which uses the transaction reduction and the MP-Apriori algorithm which uses the two-item set support matrix that can quickly prune the candidate itemsets, is much faster than the M-Apriori algorithm, and the MRP-Apriori algotirhm which combines these two optimization strategies together gets the shortest time, therefore, it proves that these two optimization strategies are efficient.