一种改进的Apriori 算法

《一种改进的Apriori 算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第9卷%第1期软件导刊Vol.9No.12010年1月SoftwareGuideJan.2010一种改进的Apriori算法李晓林，王建华，廖作文（武汉工程大学计算机科学与工程学院，湖北武汉430073）摘要：关联规则挖掘是数据挖掘研究领域中的一个重要任务，旨在挖掘事务数据库中有趣的关联。Apriori算法是关联规则挖掘中的经典算法。然而Apriori算法存在着产生候选项目集效率低和频繁扫描数据等缺点。提出了一种新的Apriori的改进算法，该算法在生成k（k＞1）项频繁集时，不需要重新扫描数据库，只是在生成1项频集时，

2、才需要扫描事务数据库，有效地减少了对事务数据库的读操作，在时间复杂度上较经典的Apriori算法有更加优越的性能。关键词：关联规则；频繁项集；Apriori算法中图分类号：TP312文献标识码：A文章编号：1672-7800（2010）01－0055－02标识符TID表示某公司销售数据库中顾客的编号字段，项0引言ID为顾客购买的商品编号字段。9个顾客编号为｛T1，T2，T3，T4，T5，T6，T7，T8，T9｝；交易的记录中9个顾客购买了5种商在许多情况下，Apriori性质大幅度压缩了候选项集的大品，分别为I1，I2，

3、I3，I4，I5；具体的每一个顾客购买的商品分别小，并产生很好的性能。然而，它有两种开销可能是十分巨大为｛｛I1，I2，I5｝，｛I2，I4｝，｛I2，I3｝，｛I1，I2，I4｝，｛I1，I3｝，｛I2，I3｝，的：①数据库扫描的次数过多，寻找每个k频繁项集（k＝1，2，｛I1，I3｝，｛I1，I2，I3，I5｝，｛I1，I2，I3｝｝；具体如表1所示：…，k）都需要扫描数据库一次，共需要扫描k次。因此当数据库表1事务表或者k太大时，算法的耗时将太大甚至无法完成。②算法的剪TID购买商品枝步，VC∈Ck，判断c的k个（

4、k－1）子集是否都在Lk－1中，若找到T1{I1，I2，I5}一个（k－1）子集不在Lk－1中就淘汰C。因为这个过程会多次扫T2{I2，I4}T3{I2，I3}描Lk－1，特别是当生成的Ck很大时，算法的效率并不理想。T4{I1，I2，I4}T5{I1，I3}1改进的Apriori算法T6{I2，I3}T7{I1，I3}本文根据对事务进行压缩，对Apriori算法进行了改进。在T8{I1，I2，I3，I5}T9{I1，I2，I3}候选频繁项目集Ck的产生过程中，删除其中不必要的扫描事现要找出满足最小支持度的项集，即频繁集

5、。假设务，压缩事务数据库，提高扫描的效率，节省系统的开销。min＿sup＝2／9＝22％，即最小支持频度为2。（1）首先，扫描事务数据库，同时记录包含该项的事务标识1项频集的候选集为C1＝｛｛I1｝，｛I2｝，｛I3｝，｛I4｝，｛I5｝｝，扫TID，产生1项候选集C1（每个候选集的结构为：项集item－set，描事务数据库，同时记录包含该项的事务标识TID。得到结果支持计数Count，事务标识符列表Tid－list）；然后，从C1中删除如表2所示：不满足最小支持度的项集，则C1中的项集集合即是1项频繁表21项频繁集及相

6、关事务集的集合L1。item-setCountTid-list是否加入L1中（2）Lk－1与Lk－1连接，生成Ck；其中Ck事务标识符列表等于{I1}6T1，T4，T5，T7，T8，T9√生成它的两个Lk－1的事务标识符列表的交集。对Ck的计数不{I2}7T1，T2，T3，T4，T6，T8，T9√需要扫描事务数据库，只需计算Ck中事务标识符列表中的中的计数不满足最小支持度，则将该项{I3}6T3，T5，T6，T7，T8，T9√TID个数即可。如果Ck集删除，这样可以有效减少K项集项Ck的数量，提高效率。{I4}2T2，T

7、4√下文是一个改进Apriori算法的实例分析：{I5}2T1，T8√作者简介：李晓林（1962－），男，湖北安陆人，武汉工程大学计算机科学与工程学院副教授,现任武汉工程大学网络信息中心主任，研究方向为计算机网络技术应用、计算机图形处理、数据库系统、软件工程应用；王建华（1984－），男，山东兖州人，武汉工程大学计算机科学与工程学院硕士研究生，研究方向为计算机网络技术应用。·56·软件导刊2010年由于最小支持频度为2，因此L1＝C1＝｛｛I1｝，｛I2｝，｛I3｝，｛I4｝，｛I5｝｝；（为方便起见，并没有把count

8、，Tid－list加入到L2实验结果分析中，这些都可以从上表中得出）。使用VC＋＋6.0分别实现了经典Apriori算法和改进的Apri-由1项频集求2项频集ori算法，并在CPU为2.93G，内存为512M的机器上利用Mi-L1与L1连接结果如表3所示：crosoftSQLServer2000中的Transacti