一种新的基于并行关联规则的挖掘算法

【摘要】 在FDM算法基础上，该算法利用Hash表技术改进了2阶侯选项集的生成过程；并采用AprioriTid算法中的Tid表技术对事务数据库中的事务数进行了有效消减.实验结果表明，该算法在处理海量数据时有较高的综合效率.

【关键词】数据挖掘并行算法关联规则FDM算法

本文在FDM算法基础上，提出了一种改进的并行关联规则挖掘算法，该算法给合了DHP算法中的对候选项集的消减技术[3]；并采用AprioriTid算法中使用的Tid表结构对事务进行了有效消减.

一、FDM算法

FDM算法在CD算法的基础上，采用两种全局消减的策略，减少候选项的个数.

（1）全局削减原理

如果X是k阶候选项集，对于任意的Y X，有X.supi≤Y.supi，所以，X.supi≤max_Xi，其中max_Xi=min{{Y.supi|Y X，Y为k-1阶项集}.因此，可以估计X的全局支持数X.Sup≤ ，其中m为处理器个数.如果这个上限小于最小支持数，那么X就不可能是大项集，可以从k阶候选项集中删除X.

（2）局部削减原理

如果X是大项集，则X至少在一个处理器上是大项集，而且X的所有子集也在该处理器上是大项集.利用这个性质，第k次循环时，根据局部k-1阶大项集构造k阶候选项集.

二、FDM_DT算法

针对FDM算法的不足之处在于提出了FDM_DT算法.FDM_DT算法在FDM算法基础上，利用HASH表技术对2阶候选项进行了有效削减，并利用了ApriorTid中Tid表技术对事务进行了削减.有效解决了FDM算法的不足.

三.1FDM_DT算法过程

第一次循环：

1） Pi根据出现在Di中的项产生局部1阶候选项集 C1i，计算局部支持数，同时搜索表中每条事务包含的2阶项集，通过Hash函数映射到Hash表的某个单元，同时单元计数器加1.

2） Pi和其他处理器通信，交换1阶候选项集的局部支持数和Hash表的信息，从而得到全局1阶大项集L1.

第二次循环：

1） Pi由1阶大项集产生2阶候选项集：

C2=Apriori_gen（L1）；

1） Pi根据Hash表对C2 削减：

C2=C2-{X∈C2|X.hashsup

2） Pi扫描局部数据库Di，计算C2的局部支持数.

3） Pi和其他处理器通信，交换局部支持数，得到全局支持数，从而得到2阶大项集L2.

L2={X∈C2|X.sup

4） Pi根据2阶候选项集C2的局部支持数将其进行升序排列.

第k次循环（k>=3）：

1） Pi由k-1阶大项集产生k阶候选项集：

Ck=Apriori_gen（Lk-1）；

2） Pi对Ck中每一个k阶候选项集X，查找其在Di或 上具有最小支持数的k-1阶子集的局部支持度，记为max_Xi：

max_X=min{Y.supi|Y X，Y为k-1阶项集}；

3） Pi和其它处理器通信，交换每个k阶候选项集的max_Xi，然后对Ck 作削减：

4） 当k=3时：Pi由Di得到局部k阶Tid表：Tidik .

当k>3时：Pi由k-1阶Tid表 Tidik -1得到局部k阶Tid表：Tidik .

并计算Ck的局部支持数，根据Ck局部支持数将其进行升序排列.

5） Pi和其他处理器通信，交换局部支持数，得到全局支持数，从而得到k阶大项集Lk .

Lk={X∈Ck|X.sup

6） Pi独立地决定算法是终止还是继续.

3.2 实验比较

在通过Internet相连的4台微机组成的并行环境下，我们实现了FDM及FDM_DT算法.实验数据使用UCI的KDD Cup 1999 Data，该数据集共有400万条数据，我们将其分别存储在4台处理器上，每台处理器存储100万条数据。实验结果如图1所示：

从实验结果可以看出，本文提出的FDM_DT算法比FDM算法的效率提高了10%～25%.

参考文献

[1]陈安，陈宁，周龙骧，等.数据挖掘技术及应用[M].北京：科学出版社，2006