分布式关联规则挖掘系统实现

《分布式关联规则挖掘系统实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第8卷第24期2008年12月科学技术与工程Vol_8No．24Dec．20081671—1819(2008)24—6496—04ScienceTechnologyandEngineering⑥2008Sci．Tech．Engng．计算机技术分布式关联规则挖掘系统实现邹丽梁旭(大连交通大学软件学院，大连116052)摘要提出一种基于AprTidRec算法的分布武关联规则挖掘算法，并通过实验验证了算法运行的有效性。给出基于局部一全局通信模式的分布式关联规则挖掘方案，并在此方案基础之上进行了系统实现。关键词数据挖掘关联规则分布式支持度可信度中图法分类号TP3

2、11．132．3；文献标志码A数据挖掘(DataMining)就是从大量的、不完全定的事务数据库D，其中的每个事务都对应一个唯的、有噪声的、模糊的、随机的数据中，提取隐含在一的事务标识TID和一组项目集Itemsets(hemsets其中的、人们事先不知道的、但又是潜在有用信息，)。关联规则是如下形式的一种蕴含：Y，其和知识的过程¨J。关联规则挖掘是数据挖掘中非中Itemsets，YItemsets，且Xf3Y=。常重要的内容，关联规则通过量化的数字来描述一对关联规则属性的描述一般有两个参数：物品的出现对另一物品的出现有多大影响，它是1．1支持度一种简单

3、但很实用的规则，可以用于对物品的存储规则y的支持度定义为事务数据库中同时规划和货物的摆放及追加销售等商业决策行为进包含项目集和y的事务的百分数。行指导。1．2可信度当数据库中存储的数据的规模非常大时，采用规则l，的可信度定义为在包含项目集的分布式系统是进行关联规则挖掘的一种解决方案。事务中，同时也包含项目集y的事务的百分数。随着网络技术的发展和分布式技术的发展，数据库频繁项目集：支持度不小于用户给定的最小支存储呈现出分布式的趋势，这使得基于分布式系统持度的项目集称为频繁项目集。的关联规则挖掘算法的研究显得非常重要，而且具关联规则的挖掘问题就是在给定数据库

4、D中有广阔地应用前景。分布式算法具有高度的适应找出具有用户给定的最小支持度(minsup)和最小性、可伸缩性、低性能损耗和容易连接等特性，它可可信度(minconf)的关联规则。以作为挖掘关联规则的理想平台。挖掘关联规则的问题可以分解为两个子问题：(1)找出存在于事务数据库中的所有频繁项1相关理论目集；(2)利用频繁项目集生成关联规则：对于每个假设，={，，，⋯，，}是一组物品集，对于给频繁项目集，若r(x，l，≠(且规则y(X—Y)的可信度不小于用户给定的最小可信度，则构成关联2008年8月27日收到规则(X—Y)。第一作者简介：邹丽(1980一)，女

5、，山东龙口人，讲师，研究方向其中第二个子问题比较简单，易于实现，而第数据挖掘及数据库技术。E．mail：stu—zl@163．corn。一个子问题是关联规则挖掘研究的重点，也是解决24期邹丽，等：分布式关联规则挖掘系统实现问题的关键。Begin假设某个事务数据库D分布存储在n个局部(1)Lk=(2)foralitemsetsI1∈Lk一1dobegin场地．s(1≤≤n)，即D={D，，D，⋯，D}，称D为(3)forallitemsets∈Lk一1dobegin全局数据库，D(1≤≤n)为局部数据库。记lDl为(4)ifI1．iteml=I2．item

6、lAI1．itero22=I2．item2A⋯⋯局部数据库中的事务数，lDl为全局数据库中的事^I1．itemk一2=I2．itemk一2AI1．itemk一1<12．itemk一1：务数。对于某个项目集，，记，在D中的支持数为(5)thenLsup(i)，在D中的支持数为，．sup。若，．sup(i)≥(6)beginII×minsup则称，在场地Si为局部大频繁项目(7)Ck．itemsets=I1．item1．I1．item2⋯I1．itcmk一1．．itemk—l集，若LsupI>IDI×minsup则称，为全局大频繁项(8)Ck．tidRec=

7、I1．tidReen12．tidRee目集。(9)Ck．count=ICk．tidRecl定理：假设儿(k)是在场地S局部大的频繁k(10)end项集，(k)是全局大频繁k项集，则必有()(11)if(Ck．count≥lDI}minsup)thenn(12)Lk=Lku{Ck}儿(k)。证明参见文献[3]。(13)end上述定理说明全局大频繁项目集一定能从各(14)end个局部大频繁项目集中得到。当数据库具有很强End的分布性时，这种从各个局部大频繁项目集中得到从算法的描述中不难看出，采用AprTidRec算候选全局大频繁项目集的方法能大大缩减产生候法

8、求全局频繁k项集的候选数据集时，仅需要扫描选项目集的数目。各局部数据库一次(建立