基于分布式系统的关联规则挖掘算法

□霍桂利

( 山西建筑职业技术学院，山西 太原 030006)

一、数据挖掘与数据库

数据库或数据仓库可能存储相当大数量的数据，在现在的大型数据库中，保存了大量的数据，数据库自然成为数据挖掘的数据基础。数据挖掘的发展方向是和数据仓库相结合。在这样的数据环境下进行关联规则的挖掘可能需要充足的处理器资源，分布式系统是一个可能的解决方案。同时许多大型数据库本来就是分布式的。数以万计的交易数据很可能存在不同的地点，这种事实使得研究数据库中挖掘关联规则的高效分布式算法显得非常重要，同时带动并行算法的研究。因为分布式算法具有高度的适应性、可伸缩性、低性能损耗和容易连接等特性，它将可以作为挖掘关联规则的理想平台。由于有大量事务数据库的存在，这些数据库中存储海量的数据，很容易想到将一个集中的数据库进行分割，从而利用分布式系统带来的高度的可伸缩性，达到提高效率的目的。D.W.Cheung揭示了分散数据集与集中数据集之间的一些有趣关系，并提出了一个快速的基于分布式系统的关联规则挖掘算法FDM，该算法通过生成数量较少的候选数据集，大大减少了在挖掘关联规则时需要处理的数据量。

以事务数据库作为讨论对象，而相应的方法可以很容易地扩展到关系数据库中，该数据库存储了大量的交易数据，每一个交易都有一个唯一的交易码(TID}和一组属性数据。此外，可以认为该数据库是“水平”分片的(例如，对交易进行分组)，并且被分配在靠消息传递进行通信的分布式系统中。基于以上假设来考察对关联的分布式挖掘，挖掘关联规则的主要代价为对数据库中大数据集的计算。而对这些大数据集进行分布式计算会遇到一些新的问题。你可以在一个地方很容易地进行计算，但是一个局部的大数据集对于全局来说不一定是大数据集。因为对其他地点广播全部数据的代价是非常昂贵的，一种可行的做法是像其他地点广播数据集的聚合数据，而不考虑局部数据量的大小。但是，一个大数据库可能包括非常多数量的数据集的组合，这样需要传输的信息量也是惊人的。

二、挖掘关联规则的算法

通过观察可以发现，在局部大数据集与全局大数据集之间，存在着一些有价值的关联。只有最大限度地利用这些关联，就可以减少信息的传输量，对需要局部处理的数据进行过滤。如前所述，目前已经存在两种挖掘关联规则的并行算法—PDM和计数分布(CD)算法，它们都是基于各自独立的并行系统的，然而，它们也可以用在分布式环境中。FDM相对于以上提出的两种算法，有着独特的特性：(1)候选数据集的生成算法思想与Apriori算法类似。但是，在每个大数据量的重复数据集中生成小数据量的候选数据集的过程中，发现了一些关于局部的大数据集和全局的大数据集的有价值的关系。这样，就可以利用这些关系减少信息传送量。(2)在候选数据集被选出以后，在每一个单独的地点，都可以利用两种剪枝技术—局部剪枝和全局剪枝对候选数据集进行裁剪。(3)为了决定一个候选集的数据量的大小，利用一个时间复杂度为O(n)的算法来进行聚合数信息交换，n代表整个网络的节点数。比起对Apriori算法进行直接的改编，其效率要高得多，因为后者的时间复杂度为O(n2)。注意到在FDM算法中可以采用几种不同的局部剪枝和全部剪枝算法，着重研究了三个FDM的版本：FDM-LP,FDM-LUP,FDM-LPP,它们都具有相似的结构但具有不同的剪枝算法。FDM-LP算法只讨论了局部剪枝；FDM-LUP算法讨论了局部剪枝和上界剪枝；FDM-PP算法讨论了局部剪枝和逐点剪枝。

在分布式环境中考察有关大数据集的某些特殊属性是非常重要的，因为这些属性可能被利用来显著减少在挖掘关联规则时的网络信息传输量。在大数据集与分布式数据库中的地点之间又一个重要的关系：每一个全局的大数据集必定在某一个地点是局部大数据集。如果一个数据集X在地点Si既是全局大数据集又是局部大数据集，可以称X在地点Si是全局大的，一个地点所有的全局大的数据集将作为该地点的候选数据集的源数据集。可以观察到关于局部大数据集和全局大的数据集的两个特征：第一，如果一个数据集X在地点Si是局部大的，那么它的所有子集在地点Si也是局部大的。第二，如果一个数据集X在地点Si是全局大的，那么它的所有子集在地点Si也是全局大的。注意到在集中的环境中也有类似的关系，以下给出的是利用在分布式环境中有效生成候选集的技术得出的重要结果。

如果一个数据集X是全局大的，那么存在一个地点Si，X以及它的所有子集在地点Si是全局大的。

证明：如果X在任何地点都不是局部大的，即X.supi

用GLi表示在地点Si的全局大数据集，GLi(k)表示在地点Si的全局大的k-数据集，根据引理3.1 ，如果X∈L(k),那么存在一个地点S(1≤i≤n)i，使得X的所有大小为k-1的子集在地点Si是全局大的，也就是说，它们属于GLi(k-1)。

三、挖掘关联规则算法的有效性

假设某个系统中有三个分布地点将一个数据库系统DB分为DB1，DB2，DB3。并假设大的1-数据集(经过一层迭代计算所得)L(1)={A，B，C，D，E，F，G，H}，其中，A、B是C在地点S1是局部大的，B、C和D在地点S2是局部大的，E、F、G和H在地点S3是局部大的，所以，GL1(1)={A，B，C}，GL2(1)={B，C，D}，GL3(1)={E，F，G，H}，根据定理3.2，在地点S1的大小为2的候选数据集为CG1(2)，CG1(2)= Apriori—gen(GL1(2))={AB，BC，AC}。类似地，CG2(2)={BC,CD,BD}, CG3(2)={EF，EG，EH，FG，FH，GH}，因此，大的2-数据集的候选数据集CG2= CG1(2)∪CG2(2)∪CG3(2)，共有11个候选元。但是，如果对L(1)直接进行Apriori—gen变换，那么候选数据集CA(2)= Apriori—gen(L1)将包含28个元素。这说明利用定理3.2对减少候选数据集中的数据量是很有效的。

在地点Si的局部剪枝中，只用到了在DBi中得到的局部支持合计数对候选集进行剪枝，事实上，在其他地点得到的局部剪枝支持合计数也同样可以被用来剪枝。利用一种全局的剪枝技术来实施这样的剪枝，这种技术的要点如下：在每一次迭代结束时，可以得到候选数据集X的所有局部剪枝支持合计数。在一个候选数据集被确认为是全局大的以后，这些局部剪枝支持合计数都可以在以后的迭代中对候选数据集进行一些全局剪枝。

通常可以在分布式环境中选择生成一个比直接应用Apriori算法生成的数据集数据量小得多的候选数据集。当候选数据集CG(k)生成成功后，为了得到全局大的数据集，就必须在所有地点之间交换支持合计数的信息，注意到CG(k)中的某些候选数据集在进行合计数交换之前就可利用局部的剪枝技术进行剪枝。总的思想是：在每一个地点Si，如果一个数据集X∈CGi(k)在地点Si并不是局部大的，也就没有必要来算出它的全局大的支持合计数来决定它是否是全局大的。这个结论是基于如下原因：如果X是小的(也就是说不是全局大的)，或者它可能在别的地点是局部大的，那么，只有X为局部大的那些地点才有必要计算X的全局支持合计数。所以，为了计算所有的大的k-数据集，在每一个地点Si，候选数据集就可以只限定在数据集X∈CGi(k)，并且在地点Si是局部大的。为了简略起见，LLi(k)用来表示那些在CGi(k)中的候选集并且在地点Si是局部大的。根据以上的讨论，在每一层迭代(共有k次迭代)的过程中，可以按照以下步骤计算出在地点Si全局大的k-数据集：

(1)候选集的生成：根据在地点Si经过k-1次迭代生成的全局大的数据集的基础上，利用公式CGi(k)=Ariori—gen(GLi(k))生成CGi(k)。(2)本地剪枝：对于每一个数据集X∈CGi(k)，扫描每一个局部数据库DBi以计算本地支持合计数X.supi。如果X在地点Si不是局部大的，那么将其从候选数据集LLi(k)中删除。(3)支持合计数交换：将LLi(k)中的候选元向其他地点广播，以收集支持合计数。计算全局的支持合计数，并得出在地点Si所有全局大的k-数据集。(4)广播挖掘结果：将计算所得的全局大的k-数据集向其它地点广播。

在地点Si的局部剪枝中，只用到了在DBi中得到的局部支持合计数对候选集进行剪枝。事实上，在其他地点得到的局部支持合计数也同样可以被用来剪枝。利用一种全局的剪枝技术来实施这样的剪枝，这种技术的要点如下：在每一次迭代结束时，可以得到候选数据集X的所有局部支持合计数和全局支持合计数。在一个候选数据集被确认为是全局大的以后，这些局部支持合计数和全局支持合计数都可以向所有地点进行广播，利用这一信息，就可以在以后的迭代中对候选数据集进行一些全局剪枝。

因为X.supi在局部剪枝后就可以获得，所以，该上界可以在地点Si被计算出用以对候选数据集进行剪枝。在CD算法中，每一个候选数据集的局部支持合计数被从一个地点向所有其他的地点进行广播。如果一个候选数据集X在地点Si是局部大的话，那么Si需要o(n)数量级的信息来得到X的支持合计数，通常来说，在所有地点都是局部大的候选数据集是非常少的。所以，FDM算法通常只需少于o(n2)数量级的信息就可以算出每一个候选元，为了确保FDM在任何情况下只需要o(n)数量级的信息就可以算出每一个候选元，对于每一个候选数据集，该技术用到了一个指派函数，假设该函数为作用于X上的函数，将X映射为一个轮询地址，对应于X的一个轮询地址与X为局部大的那些地点是毫无关系的，对于每一个候选数据集X，它的轮询地址是用来计算是否X为全局大的。为了达到这个目的，对应于X的轮询地址必须向所有其他地点广播X的轮询请求，收集局部支持合计数，计算全局支持合计数。因为对应于每一个候选数据集X，有且仅有一个轮询地址，所以X需要的合计数交换信息数就可以被减少到o(n)数量级。

四、结果的解释和评价

进行数据挖掘时，首先要从大量数据中取出一个问题相关的样板数据子集，而不是使用全部数据。通过对数据的取样，选择与知识发现任务相关的数据集，从而减少数据处理量，同时又不降低知识发现的精确度。数据预处理主要是接受并理解用户的发现要求，确定发现任务，抽取与发现任务相关的知识源，根据背景知识中的约束性规则对数据进行合法性检查，生成供挖掘核心使用的目标数据。在经过预处理的数据基础上利用人工神经网络、遗传算法、决策树、规则推理等方法，高效地进行关联规则、序列模式、分类、聚类等各项分析。

数据挖掘的目的在于根据最终用户的决策目的对提取的信息进行分析。从上述过程中将会得出一系列的分析结果、模式和模型。分析结果一般都是形式化的，这时需要通过可视化等技术手段，用图表、图形曲线等为用户提供清晰、直观的结果描述。在大多数情况下，对目标问题的描述是多侧面的，这时就要综合它们的规律性，进行进一步的抽象与过滤，提供合理的决策支持信息。

参考文献：

[1]史忠植，潘谦红，李威，李云峰.分布式环境下的数据库知识发现[Z].第六届全国机器学习研讨会会议论文,1998,(6).

[2]王清毅,张波,蔡庆生.前数据挖掘算法的评价[J].小型微型计算机系统,2000 ，(3) .

[3]胡侃,夏绍玮.基于大型数据仓库的数据采掘研究综述[J].软件学报，1998， (1).

[4]陆建海，刘海峰.数据库中广义模糊关联规则的挖掘[J].工程数学学报,2000，(1).

[5]马洪文，王万学，李振江.广义模糊关联规则的挖掘[J].黑龙江商学院学报，2000，(2).