摘 要 以往使用的分布式数据挖掘算法各有优缺点，提出了一种基于星型网络的分布式关联规则挖掘算法。对其基本思想、算法描述等进行了分析。

　　【关键词】并行关联规则 挖掘算法 SDAM算法

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

　　1 SDAM算法

　　实际中，网络拓扑结构多呈现星型结构，针对FDM算法的不足，对其加以改进，介绍一种基于星型网络的分布式关联规则挖掘算法SDAM算法。SDAM算法是在Aprioi算法的基础上，候选集为1项的项目长度，通过数据库扫描分析，算出局部大项集。接着将此局部大项集发送至中心结点，通过判断，检查此项集能否满足全局的大项集标准。在项目长度为k的大项集基础上，生成项目长度为k+1的大项集，然后对数据库进行二次分析、扫描，最后确定项目的全部大项集。SDAM算法与FDM算法不同点是，SDAM算法只需要一个结点的局部大项集，不需要其他结点，SDAM算法的局部结点可以和中心结点进行信息交换。

　　2 SDAM算法描述

　　设结点为j（1 ≤j≤ n），保证在结点运行算法的基础上完成局部剪枝，具体步骤是：

　　（1）选出候选集。结点j经过（k―1）次迭代后可以生成强项集，根据计算可生成CGj（k） 。

　　（2）局部剪枝。设置项集是Xi的数据（Xi∈CGj（k）），通过扫描数据库中的DBj，对局部支持度合计数进行计算分析。若Xi在结点i上并非局部最大值，则Xi项集不为局部大项集，应从候选集中删除。

　　（3）交换信息。将候选集项LLi（k）发送到中心结点，进行信息交换，并且接受源于中心结点的全局大数据项集。

　　在结点运行算法的基础上完成局部剪枝。设置k次迭代结束后，k的候选数据项集大小是X。在中心结点接受的数据集内，大小为（k―1）的所有子集进行局部支持度合计数，用max supi（X）来表示一个结点数据库DBj中所有子集进行局部支持度合计数，即min supi（X）= min{Y.supi且= k ―1 }。所有分支数据库中此类上界函数之和为X.supi的上界，可用max sup（X）表示，即：X.sup ≤ max sup （X） = maxsupi（X），可用其进行全局剪枝。从中可知，一旦max sup（X）比δ*D小，则数据集X难以达到候选数据集的要求，也就不能成为一个数据集。交换合计数前，要用结点i对剩余的候选元进行剪枝。X.supi + max supi（X） 为候选数据集X的全局支持度合计数上界值。

　　X.supi值可以从在局部剪枝中得到，上界值能从中心结点中计算出来，用于数据集的剪枝。

　　3 分析SDAM算法

　　3.1 分析复杂度

　　该算计算时，如果结点i的局部最大值是项集X，那么通信量的复杂性为O（n），如果使用CD算法（一种计数分布算法），那么需要的通讯量为O（n2）。

　　3.2 分析并行代价

　　如果结点的分区大小结果相同，存在D/n个事务，有m各项目需要挖掘，那么生成项集最多为2m个。假设在最恶劣的情况下，t是扫描每个数据库D的时间，在串行情况下，复杂度为O（2m ），2m × ts为算法的扫描时间。2m × ts/n 为所有分区的并行运行时间。

　　设并行代价为c，则c = t * n ，式中，t 表示的是并行运算时间，n为结点总数量。可知c = 2m × ts ，在挖掘执行代价在阶的意义关联规则的并行算法上，在最坏情形下，串行求解此问题所需的运行时间同SDAM算法相同，经过比较，发现SDAM算法的并行代价最好。

　　3.3 分析并行伸缩性

　　在平常的并行算法中，效率为Ep = Sp/n，式中的n表示并行结点数，Sp表示算法的加速比。并行算法的可伸缩性具体表现为：在处理机数目保持固定的情况下，Ep会随着问题规模的扩大呈现单调递增的趋势，此时，其效率为：

　　Ep = Sp/n = 1/[1 + （Tr/Tc）]

　　又因为Tr = Tf × m，Tc = Ts × 2m，可求得

　　Ep = 1/[1 + （Tf × m/Ts × 2m）]

　　当数据库规模发生变化时，Ep的分母会不断减少，则其值呈现出单调递增的情形，由此可见，SDAM算法的可伸缩性能很好。

　　3.4 分析加速比

　　中心结点在每次迭代结束后，向各结点通讯的时间就是各个结点需要等待的时间，从最坏的情况下进行分析，如果中心结点迭代结束后，发往各结点的时间为Tf，那么中心结点的总发送时间为m × Tf 。根据阿达尔定律可知，

　　Sp<为SDAM算法的最大可能加速。

　　上式中，Sp表示的是最大加速比，p为结点数目，f表示串行执行部分的时间。

　　经计算分析，SDAM算法的加速比也十分良好。

　　4 结束语

　　分布式关联规则挖掘算法的重要性日益突出，针对以往算法的不足之处，文中提出的新算法充分利用了局部剪枝和全局剪枝技术，采用星型结构网络拓扑，与实际系统比较相符，实用性强，值得推广应用。

　　参考文献

　　[1]杨泽民。关联规则的并行优化挖掘算法[J].中北大学学报，2007，21（5）：130-131.

　　[2]黄贤英，王柯柯，范伟。基于星型网络的分布式关联规则挖掘算法研究[J].计算机科学，2007，24（12）：109-110.

　　[3]刘晶，朱清香，梅群，张蕾。一种基于单处理机的并行关联规则算法及其在数字图书馆中的应用[J].图书情报工作，2011，20（7）：137-138.

　　[4]张建军，黄登斌，蒋宏。一个快速的关联模式并行挖掘算法[J].计算机与数字工程，2011，20（12）：143-144.

　　作者单位

　　同济大学 上海市 200092