[1]张健,刘韶涛.事务约简和2项集支持度矩阵快速剪枝的Apriori改进算法[J].华侨大学学报(自然科学版),2017,38(5):727-731.[doi:10.11830/ISSN.1000-5013.201510043]
　ZHANG Jian,LIU Shaotao.Improved Apriori Algorithm for Quickly Prune by Combining Transaction Reduction WithTwo-Item Set Support Matrix[J].Journal of Huaqiao University(Natural Science),2017,38(5):727-731.[doi:10.11830/ISSN.1000-5013.201510043]
点击复制

事务约简和2项集支持度矩阵快速剪枝的Apriori改进算法()
分享到：

《华侨大学学报（自然科学版）》[ISSN:1000-5013/CN:35-1079/N]

卷:
第38卷
期数:
2017年第5期
页码:
727-731
栏目:
出版日期:
2017-09-20

文章信息/Info

Title:
Improved Apriori Algorithm for Quickly Prune by Combining Transaction Reduction WithTwo-Item Set Support Matrix
文章编号:
1000-5013(2017)05-0727-05
作者:
张健;  刘韶涛
华侨大学 计算机科学与技术学院, 福建 厦门 361021
Author(s):
ZHANG Jian;  LIU Shaotao
College of Computer Science and Technology, Huaqiao University, Xiamen 361021, China
关键词:
关联规则;  Apriori算法;  频繁项集;  支持度矩阵
Keywords:
association rule;  Apriori algorithm;  frequent itemset;  support matrix
分类号:
TP311
DOI:
10.11830/ISSN.1000-5013.201510043
文献标志码:
A
摘要:
在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算法运行时间最短,验证了这两种优化策略的有效性.
Abstract:
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.

参考文献/References:

[1] AGRAWAL R,SRIKANT R.Fast algorithms for mining association rules[C]//Proc 20th Int Conf Very Large Data Bases.Santiago:VLDB,1994:487-499.
[2] PARK J S, CHEN M S, YU P S.An effective hash-based algorithm for mining association rules[J].ACM,1995:175-186.
[3] SAVASERE A,OMIECINSKI E R,NAVATHE S B.An efficient algorithm for mining association rules in large databases[C]// International Conference on Very Large Data Bases.[S.l.]:Morgan Kaufmann Publishers Inc,1995:432-444.
[4] TOIVONEN H.Sampling large databases for association rules[C]//Proceedings of the 22nd VLDB Conference.Mumbai:[s.n.],1996:134-145.
[5] BRIN S,MOTWANI R,ULLMAN J D,et al.Dynamic itemset counting and implication rules for market basket data[J].ACM SIGMOD Record,1997,26(2):255-264.
[6] 陈江平,傅仲良,徐志红.一种Apriori的改进算法[J].武汉大学学报(信息科学版),2003,28(1):94-99.
[7] 黄建明,赵文静,王星星.基于十字链表的Apriori改进算法[J].计算机工程,2009,35(2):37-38,40.
[8] 刘维晓,陈俊丽,屈世富,等.一种改进的Apriori算法[J].计算机工程与应用,2011,47(11):149-159.
[9] AL-MAOLEGI M,ARKOK B.An improved apriori algorithm for association rules[J].International Journal on Natural Language Computing,2014,3(1):21-29.
[10] SINGH J,RAM H,SODHI D J S.Improving efficiency of apriori algorithm using transaction reduction[J].International Journal of Scientific and Research Publications,2013,3(1):1-4.
[11] 纪怀猛.基于频繁2项集支持矩阵的Apriori改进算法[J].计算机工程,2013,39(11):183-186.
[12] 胡吉明,鲜学丰.挖掘关联规则中Apriori算法的研究与改进[J].计算机技术与发展,2006,16(4):99-101.

相似文献/References:

[1]朱龙.利润约束的关联规则挖掘算法[J].华侨大学学报(自然科学版),2015,36(5):522.[doi:10.11830/ISSN.1000-5013.2015.05.0522]
　ZHU Long.Association Rules Mining Algorithm for Profit Constraint[J].Journal of Huaqiao University(Natural Science),2015,36(5):522.[doi:10.11830/ISSN.1000-5013.2015.05.0522]
[2]唐琳瑶,祁神军,叶云珊,等.“2-4”模型及关联规则下塔吊坍塌事故致因分析[J].华侨大学学报(自然科学版),2022,43(3):323.[doi:10.11830/ISSN.1000-5013.202012052]
　TANG Linyao,QI Shenjun,YE Yunshan,et al.Cause Analysis of Tower Crane Collapse Accident Using “2-4” Model and Association Rules[J].Journal of Huaqiao University(Natural Science),2022,43(5):323.[doi:10.11830/ISSN.1000-5013.202012052]

备注/Memo

备注/Memo:
收稿日期: 2015-10-21
通信作者: 刘韶涛(1969-),男,副教授,主要从事软件体系结构与软件复用的研究.E-mail:shaotaol@hqu.edu.cn.
基金项目: 福建省科技计划重大项目(2011H6016)
更新日期/Last Update: 2017-09-20