关联规则挖掘中对Apriori算法的一种改进研究

1、0引言关联规则挖掘发现大量数据中项集之间有趣的关联或相关关系。随着大量数据不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从大量商务数据库中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物和贱卖分析。关联规则的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助商家制定营销策略，设计不同的商店布局。最经典的关联规则挖掘算法是Apriori算法1-2，它是由Ag-rawal等人于1993年首先提出的，是一种最有影响的挖掘布尔关联规则频繁项集的宽

2、度优先算法。该算法使用一种称作逐层搜索的迭代方法，繁1-项集集合，该集合记为2用于寻找）项集。首先，找出频1用于寻找频繁2-项集的集合-项集，找个项集在第行，第出每个Lk需要扫描数据库一次。此算法利用了下面两个基本性质，即：一个频繁项集的任一子集必定也是频繁项集；一个非频繁项集的任一超集必定也是非频繁项集。如何由1找出4220的挖掘问题就可转化为对其布尔矩阵的分析。为了清楚的介绍，这里引用一个例子，表1是一个示例数据库；5个项，即可以用矩阵表示如表2所示。2，4，then/Ii,为项集i对应的行向量；AddVjtotheadjacentlistofViEndIfNextEnd2.2基于无向项集

3、图的优化挖掘算法本文提出的算法利用深度优先的搜索策略进行遍历无向项集图。具体过程如下：(1)从结点集，则µÄƵ·±1-项集中的一项；(3)当，则当无向项集图,，¸ö½áµã<,为边<1,-项频繁集。doForeachViofVifcount(Vi)Sdo/count(Vi)为结点Vi出现的次数L=Vi;对应的行向量与结点与结点SelectunvisitedVjfromVi.adjacentlist;Ifcount(Vi,Vj)Sdo/count(Vi,Vj)为边

4、<Vi,Vj>的出现次数L=LVjL.adjacentlist=L.adjacentlistVj.adjacentlistCallDFS(Vj)End;ProcedureDFS(Vj)BeginifVj.adjacentlistµÄƵ·±2-项集中中存在3个结点的环，且这个环的的频繁3-项集，依次类推，当图>3£¬ÇÒÕâ,>就是满足最小支持度为S的频繁的一项，接着以作为搜索起点，依次类推，找出频繁2-项集；每条边的出现次数不小于最小支持度2.1基于

5、无向项集图的频繁集挖掘优化算法无向项集图的定义及生成算法无向项集图无向项集图(undirecteditemsetsgraph，UDISG)(1)无向项集图中的结点集2.1.1的定义如下：2.1.2无向项集图的构造首先扫矩阵，把矩阵每个项集的当作结点，此矩阵的行向量之和为项集出现的次数，则可求出各个项集的支持计数。各项集的支持计数为：2：7，4：2，4221SelectVkfromVj.adjacentlist;Callisloop(L,Vk)Ifcount(L,Vk)SdoL=LVkCallDFS(Vk)OutputLdeleteVkfromVj.adjacentlistCallDFS(Vj)

6、ElseReturntoitsparentvertexViCallDFS(Vi)End;Procedureisloop(L,Vk)BeginIfVkL.adjacentlistdoReturnVkElsedeleteVkfromVj.adjacentlistCallDFS(Vj)End;根据算法2，可推出图1中包含的频繁1-项集有：，频繁2-项集有：，3=，2,，1,，5。，4，1,I1I2I3I4I5表4矩阵表示的变化的示例数据库T50010100T600T700T800011001010011101T90011100T90110010T100T200T300T400210010101001

7、100110101，1=2=5，,4。7I14722I43I24I36212242,3，4,2,2，3，5，4；频繁3-项集有：，I5图2由表4生成的无向项集2.3.2最小支持度发生变化例如，当图1中的最小支持度1=2,，。2.3基于无向项集图的更新策略当交易数据库和最小支持度发生变化后如何在数据库中2=2，3，3；频繁3-项集有：生成频繁项集，已有许多研究人员进行了分析和研究，并提出了相应的算法4-7。但事实上，对于很多应用系统的交易数据库的交易数据而言，数据库的模式往往要进行受限重构(即项目集进行增删、最小支持度发生变化)，此时，以上算法就不能直接应用，否则会丢失相关项目集关联规则的有效信

8、息。本文提出的基于无向项集图的挖掘算法中无向项集图可以被实时的构造，当有新的项目加入时，无向项集图就可以被更新，这时只要再运行一次算法2即可生成新的频繁项集。当最小支持度发生变化时，只要调整算法2的一个参数：最小支持度3算法性能分析本文使用PentiumIII1.7/256M微机(OS为Windows2003)，VC+语言，对基于无向项集图的挖掘算法与Apriori算法在时间上进行了对比实验，共10000条事务，平均每条事务包含项为10个，当最小支持度分别取0.3，0.25，0.2，0.15，0.1时，基于无向项集图的挖掘算法与Apriori算法的运行时间如图3所示。910此时由于新增了一项目

9、表3TIDT100T200T300T400T500T600T700T800T900T9104，如表3和表4所示。，变化的示例数据库IDI1，I2，I5I2，I4I2，I3I1，I2，I4I1，I3I2，I3I1，I3I1，I2，I3，I5I1，I2，I3I4，I1通过实验证明改进的挖掘算法有比较好的运行速度，相比原来的Apriori算法，同样条件下，运行速度提高了，在频集发现性能上有很大的改进。不管频集较短还是较长，数据相关性较弱还是较强，改进的挖掘算法都可以进行处理。因此，改进的挖掘算法非常行之有效，完全优于现有的Apriori算法。4结束语本文提出的从事务数据库所对应的布尔矩阵出发，直接4

10、222利用按位与运算提高了数据项集频度统计速度即高效的数字运算代替了了低速的查找比较运算。进而生成无向项集图，将有关项集的信息保存在一个无向图中，通过对无向图进行搜索来发现其中的频繁项集，而不需要产生候选项目集，并且当事务数据库和最小支持度发生变化时，本算法只需重新遍历一次无向项集图，即可得到新的频繁项集。56743frontiersC.PrecedingECML/PKDD,ACMPress,2002.HanJiawei,KamberMiceline.数据挖掘概念与技术M.北京:机械工业出版社,2001:149-179.HanJ,PeiJ,YinJ.Miningfrequentpatterns

11、withoutcandidategenerationC.ProceedingsofACMSIGMODICMD,ACMPre-ss,2000:1-12.朱玉全,孙志挥.快速更新频繁项集J.计算机研究与发展,2003,40(1):94-99.章志明,黄龙军.一种基于矩阵的动态频繁项集挖掘算法J.计算机工程与应用,2006,42(32):170-172.朱意霞,姚力军,黄水源,等.基于排序矩阵和树的关联规则挖掘算法J.计算科学,2006,33(7):196-198.参考文献:1WenLei,LiMinqiang.Anewassociationrulesminingalgori-thmsbasedon

12、directeditemsetsgraphC.China:Proceedingof9ththeInt'lConfRSFDGrc,2003:660-663.2DzeroskiS,RaedtLD.Multi-relationaldatamining:Thecurrent(上接第4211页)(1)持久性分级管理：根据应用的持久性以及网格资源节点的在线时间进行合理的管理。这要求对存储资源的持久性进行分级，以便于存储空间的分配。可考虑分为以下3级：临时存储、经常使用、长期保存。(2)负载均衡：在若干个资源节点中，按负载均衡的策略进行存储分配。可有效提高网络的效率。(3)子网优先策略：局域存储网格

13、系统可由若干个局域网组成，为网格应用分配同一子网中的存储资源可提高文件的传输效率。(4)可靠性优先策略：存储在网格中的数据必须安全可靠，确保用户随机存取和维护，因此分配存储资源时，要优先考虑网格资源的可靠性。可靠性、在不间断服务的情况下实现系统扩展和技术更新等。进一步的研究成果可促进局域存储网格系统的设计与改进。4结束语本文基于许多存储资源闲置、利用率低的特点，设计了一种通用的局域存储网格系统，该系统具有透明性、高效性、实时性，屏蔽了存储资源的分布性、异构性等特征，为用户提供了快速、方便的存储资源使用环境，同时也大大提高了存储资源的利用率。参考文献:12倪永军,谢长生.网络存储技术现状、存在的

14、问题及对策研究J.计算机工程与应用,2003,39(10):159-161.IanFoster,Kesselman.Thegrid:BlueprintforafuturecomputinginfrastructureM.SanFrancisco,USA:MorganKaufmannPub-lishers,1999.3AllcockW,ChervenakA,FosterI,etal.Thedatagrid:TowardsanarchitectureforthedistributedmanagementandanalysisoflargescientificdatasetsJ.JournalofN

15、etworkandComputerApplica-tion,2000,23(3):187-200.4刘福明,黄河,应宏.网格与存储J.重庆三峡学院学报,2006,22(3):28-33.56789李明,刘福明.基于网格环境的存储技术浅析J.重庆工学院学报,2006,20(8):101-103.刘苗,陈海鹏.基于LVMY与Soft-RAID的网格存储体系结构J.吉林大学学报(信息科学版),2006,24(5):526-529.李润洲,宋彩利.校园网格数据集成中间件体系结构研究J.西安科技大学学报,2006,26(4):532-534.杨俊.网格环境下的数据存储研究J.哈尔滨商业大学学报(自然科学版),2005,21(4):500-503.王意洁,肖侬等.数据网格及其关键技术研究J.计算机研究与发展,2002,39(8):943-946.10武秀川,胡亮,鞠九滨.数据网格的数据管理策略J.小型微型计算机系统,2004,25(1):98-文件传输服务对于存储网格来说，文件传输是一个重要的问题。为了提高传输的效率，局域存储网格系统采用第三方控制，如图3所示。为实现文件传输的安全、可靠和高效，定义了专门的网格传输协议(GridFTP)，该协