基于分布式并行关联规则的挖掘算法

《基于分布式并行关联规则的挖掘算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于分布式并行关联规则的挖掘算法摘要以往使用的分布式数据挖掘算法各有优缺点，提出了一种基于星型网络的分布式关联规则挖掘算法。对其基本思想、算法描述等进行了分析。【关键词】并行关联规则挖掘算法SDAM算法在因特网的推动下，分布式数据库的应用范围越来越广，如超市、银行、图书馆等领域都有所应用。随着数据量的增多，对信息安全要求的提高，数据挖掘技术备受关注，成了当前研究的重点。作为数据挖掘领域的重要组成部分，关联规则可发现不同项之间内在的联系，进而提高更优质的服务。自上世纪90年代被发现后，相关研究日益增多，特别是分布式并行挖掘方面

2、，很多算法相继被提出。其中，FDM算法得到广泛应用，但尚有缺陷点。为此，提出一种新的算法。1SDAM算法实际中，网络拓扑结构多呈现星型结构，针对roM算法的不足，对其加以改进，介绍一种基于星型网络的分布式关联规则挖掘算法SDAM算法。SDAM算法是在Aprioi算法的基础上，候选集为1项的项目长度，通过数据库扫描分析，算出局部大项集。接着将此局部大项集发送至中心结点，通过判断，检查此项集能否满足全局的大项集标准。在项目长度为k的大项集基础上，生成项目长度为k+1的大项集，然后对数据库进行二次分析、扫描，最后确定项目的全部大项

3、集。SDAM算法与FDM算法不同点是，SDAM算法只需要一个结点的局部大项集，不需要其他结点，SDAM算法的局部结点可以和中心结点进行信息交换。2SDAM算法描述设结点为j(1n),保证在结点运行算法的基础上完成局部剪枝，具体步骤是：(1)选出候选集。结点j经过(k-1)次迭代后可以生成强项集，根据计算可生成CGj(k)。(2)局部剪枝。设置项集是Xi的数据(XiECGj(k))，通过扫描数据库中的DBj，对局部支持度合计数进行计算分析。若Xi在结点i上并非局部最大值，则Xi项集不为局部大项集，应从候选集中删除。(3)交换信

4、息。将候选集项LLi(k)发送到中心结点，进行信息交换，并且接受源于中心结点的全局大数据项集。在结点运行算法的基础上完成局部剪枝。设置k次迭代结束后，k的候选数据项集大小是X。在中心结点接受的数据集内，大小为(k-1)的所有子集进行局部支持度合计数，用maxsupi(X)来表示一个结点数据库DBj中所有子集进行局部支持度合计数，即minsupi(X)=min{Y.supi且=k—1}o所有分支数据库中此类上界函数之和为X.supi的上界，可用maxsup(X)表示，即：X.supmaxsup(X)=maxsupi(X)，可用

5、其进行全局剪枝。从中可知，一旦maxsup(X)比S*D小，则数据集X难以迗到候选数据集的要求，也就不能成为一个数据集。交换合计数前，要用结点i对剩余的候选元进行剪枝。X.supi+maxsupi(X)为候选数据集X的全局支持度合计数上界值。X.supi值可以从在局部剪枝中得到，上界值能从中心结点中计算出来，用于数据集的剪枝。3分析SDAM算法3.1分析复杂度该算计算时，如果结点i的局部最大值是项集X，那么通信量的复杂性为0(n)，如果使用CD算法(一种计数分布算法)，那么需要的通讯量为0(n2)。3.2分析并行代价如果结点

6、的分区大小结果相同，存在D/n个事务，有m各项目需要挖掘，那么生成项集最多为2m个。假设在最恶劣的情况下，t是扫描每个数据库D的时间，在串行情况下，复杂度为0(2m)，2mXts为算法的扫描时间。2mXts/n为所有分区的并行运行时间。设并行代价为c，则c=t*n，式中，t表示的是并行运算时间，n为结点总数量。可知c=2mXts，在挖掘执行代价在阶的意义关联规则的并行算法上，在最坏情形下，串行求解此问题所需的运行时间同SDAM算法相同，经过比较，发现SDAM算法的并行代价最好。3.3分析并行伸缩性在平常的并行算法中，效率为E

7、p=Sp/n，式中的n表示并行结点数，Sp表示算法的加速比。并行算法的可伸缩性具体表现为：在处理机数目保持固定的情况下，Ep会随着问题规模的扩大呈现单调递增的趋势，此时，其效率为：Ep=Sp/n=1/[1+(Tr/Tc)]又因为Tr=TfXm,Tc=TsX2m,可求得Ep=1/[1+(TfXm/TsX2m)]当数据库规模发生变化时，Ep的分母会不断减少，则其值呈现出单调递增的情形，由此可见，SDAM算法的可伸缩性能很好。3.4分析加速比中心结点在每次迭代结束后，向各结点通讯的时间就是各个结点需要等待的时间，从最坏的情况下进行

8、分析，如果中心结点迭代结束后，发往各结点的时间为Tf，那么中心结点的总发送时间为mXTf。根据阿迗尔定律可知，Sp