基于分布式并行关联规则的挖掘系统的管理

《基于分布式并行关联规则的挖掘系统的管理》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于分布式并行关联规则的挖掘系统的管理　在因特X的推动下，分布式数据库的应用范围越来越广，如超市、银行、图书馆等领域都有所应用。随着数据量的增多，对信息安全要求的提高，数据挖掘技术备受关注，成了当前研究的重点。作为数据挖掘领域的重要组成部分，关联规则可发现不同项之间内在的联系，进而提高更优质的服务。自上世纪90年代被发现后，相关研究日益增多，特别是分布式并行挖掘方面，很多算法相继被提出。其中，FDM算法得到广泛应用，但尚有缺陷点。为此，提出一种新的算法。　　1SDAM算法　　实际中，X络拓扑结构多呈现星型结构，针对FDM算法的不足，对其加以改进，介绍一种基于星型

2、X络的分布式关联规则挖掘算法SDAM算法。SDAM算法是在Aprioi算法的基础上，候选集为1项的项目长度，通过数据库扫描分析，算出局部大项集。接着将此局部大项集发送至中心结点，通过判断，检查此项集能否满足全局的大项集标准。在项目长度为k的大项集基础上，生成项目长度为k+1的大项集，然后对数据库进行二次分析、扫描，最后确定项目的全部大项集。SDAM算法与FDM算法不同点是，SDAM算法只需要一个结点的局部大项集，不需要其他结点，SDAM算法的局部结点可以和中心结点进行信息交换。　　2SDAM算法描述　　设结点为j（1≤j≤n），保证在结点运行算法的基

3、础上完成局部剪枝，具体步骤是：　　（1）选出候选集。结点j经过（k1）次迭代后可以生成强项集，根据计算可生成CGj（k）。　　（2）局部剪枝。设置项集是Xi的数据（Xi∈CGj（k）），通过扫描数据库中的DBj，对局部支持度合计数进行计算分析。若Xi在结点i上并非局部最大值，则Xi项集不为局部大项集，应从候选集中删除。　　（3）交换信息。将候选集项LLi（k）发送到中心结点，进行信息交换，并且接受源于中心结点的全局大数据项集。　　在结点运行算法的基础上完成局部剪枝。设置k次迭代结束后，k的候选数据项集大小是X。在中心结点接受的数据集内，大小为（k1）的

4、所有子集进行局部支持度合计数，用maxsupi（X）来表示一个结点数据库DBj中所有子集进行局部支持度合计数，即minsupi（X）=min{Y.supi且=k1}。所有分支数据库中此类上界函数之和为X.supi的上界，可用maxsup（X）表示，即：X.sup≤maxsup（X）=maxsupi（X），可用其进行全局剪枝。从中可知，一旦maxsup（X）比δ*D小，则数据集X难以达到候选数据集的要求，也就不能成为一个数据集。交换合计数前，要用结点i对剩余的候选元进行剪枝。X.supi+maxsupi（X）为候选数据集X的全局支持度合计数上界值

5、。　　X.supi值可以从在局部剪枝中得到，上界值能从中心结点中计算出来，用于数据集的剪枝。　　3分析SDAM算法　　3.1分析复杂度　　该算计算时，如果结点i的局部最大值是项集X，那么通信量的复杂性为O（n），如果使用CD算法（一种计数分布算法），那么需要的通讯量为O（n2）。　　3.2分析并行代价　　如果结点的分区大小结果相同，存在D/n个事务，有m各项目需要挖掘，那么生成项集最多为2m个。假设在最恶劣的情况下，t是扫描每个数据库D的时间，在串行情况下，复杂度为O（2m），2mts为算法的扫描时间。2mts/n为所有分区的并行运行时间。　　设并行代价为c，则

6、c=t*n，式中，t表示的是并行运算时间，n为结点总数量。可知c=2mts，在挖掘执行代价在阶的意义关联规则的并行算法上，在最坏情形下，串行求解此问题所需的运行时间同SDAM算法相同，经过比较，发现SDAM算法的并行代价最好。　　3.3分析并行伸缩性　　在平常的并行算法中，效率为Ep=Sp/n，式中的n表示并行结点数，Sp表示算法的加速比。并行算法的可伸缩性具体表现为：在处理机数目保持固定的情况下，Ep会随着问题规模的扩大呈现单调递增的趋势，此时，其效率为：　　Ep=Sp/n=1/[1+（Tr/Tc）]　　又因为Tr=Tfm，Tc=Ts2m，可求得　　Ep=1/

7、[1+（Tfm/Ts2m）]　　当数据库规模发生变化时，Ep的分母会不断减少，则其值呈现出单调递增的情形，由此可见，SDAM算法的可伸缩性能很好。　　3.4分析加速比　　中心结点在每次迭代结束后，向各结点通讯的时间就是各个结点需要等待的时间，从最坏的情况下进行分析，如果中心结点迭代结束后，发往各结点的时间为Tf，那么中心结点的总发送时间为mTf。根据阿达尔定律可知，　　Sp<为SDAM算法的最大可能加速。　　上式中，Sp表示的是最大加速比，p为结点数目，f表示串行执行部分的时间。　　经计算分析，SDAM算法的加速比也十分良好。　　4结束语　　分布式关联规则

8、挖掘算法的重要性日益突出