云平台下关联规则算法并行化研究与实现

戴伟敏

(阳光学院信息工程学院)

0 引言

关联规则的挖掘可以发现大量数据中项集之间有趣的关联或相关联系，其核心是通过统计数据项获得频繁项集，用于发现交易数据库中不同项目集之间的关系[1].传统的关联规则主要有Apriori算法、FP-Growth算法、抽样算法等，它们可实现可靠准确的处理小规模数据，但随着社会互联网技术、计算机技术和数据库技术的迅速发展，数据呈爆炸式上升，传统的关联规则算法在面对大数据时候，无论在运算能力还是并行化效率方面都难以满足人们的要求.云计算平台Hadoop[2-3]是一个开源的、可以更容易开发和并行处理大规模数据的分布式计算平台，主要用于海量数据的存储和分布式计算，其对海量数据的存储能力和并行计算能力提供了有利条件，为解决海量数据挖掘问题提供了一种新的解决方案.Hadoop平台是以HDFS和MapReduce为核心，HDFS是分布式文件系统，MapReduce是一种简单的编程模式，采用分布式的并行方式处理海量数据，无需考虑数据的划分、分配以及调度等问题，同时还能处理集群中节点失效，具有适用性强、资源消耗小、方便连接和可扩展性好等优点.

该文基于FP-Growth算法结合MapReduce编程模型进行改进，使其能高效运行于Hadoop平台，以解决Apriori算法在单机环境下运行效率低下的问题.

1 算法描述

1.1 关联规则描述

关联规则挖掘是数据挖掘研究的一个重要分支.根据韩家炜等观点，关联规则定义为：假设I= {I1,I2,…,Im}是项的集合.给定一个事务数据库D，其中每个事务t是I的非空集合，即每一个交易都与一个唯一的标识符TID对应.关联规则在D中的支持度定义为：

支持度support (A=>B)=P：表示D中同时包含A和B的百分比，即概率.

关联规则在D中的置信度定义为：

置信度confidence(A=>B)=( support/support(A)：表示D中已经包含A的情况下，包含B的百分比，即条件概率.

对于给定的一个事务数据库D，关联规则挖掘问题是根据事务设定好的最小支持度和最小置信度来发现强关联规则的过程.即对给定的支持度阈值min_sup、置信度阈值min_con，找到所有满足下列条件的关联规则：支持度>=min_sup 和置信度>=min_con，因而，对关联规则挖掘需经过以下两个步骤：

(1)频繁项集产生：从事务数据库D中发现满足最小支持度阈值的所有项集.

(2)规则的产生：从上一步发现的频繁项集中提取出所有高于置信度的规则，这些规则称作强规则.

1.2 传统的Apriori算法

Apriori算法是挖掘产生布尔关联规则所需的频繁项集的基本算法，也是最著名的关联规则挖掘算法之一.Apriori算法是采用逐层搜索的迭代方法，利用K-1项集来探索K项集，在挖掘过程中采用了2条重要性质：

性质1：若项目集I是事务数据库D中的频繁项目集，则其所有的非空子集在D中一定是频繁项集.

性质2：若项目集I是非频繁项集，则其所有超集都是非频繁项目集.

Apriori算法主要挖掘频繁项集过程如下：

(1)连接步：频繁K项集的集合是由所有的频繁K-1项集的集合Lk-1与自身连接产生候选K项集的集合Ck.

(2)剪枝步：扫描事务数据库D，确定Ck中每个候选的计数，再判断是否小于最小支持度min_sup，如果是，则将其从Ck中删除，否则，认为该候选集合是频繁的.

1.3 MapReduce简介

MapReduce[6-7]是面向大数据并行处理的计算模型、框架和平台，采用分布式的并行计算的简单编程模式， 在运行一个mapreduce计算任务时候，任务过程被分为两个阶段：map阶段和reduce阶段，每个阶段都是用键值对(key/value)作为输入(input)和输出(output).因此程序员只需编写map()函数和reduce()函数.MapReduce执行过程如图1所示.

图 1 MapReduce执行过程

1.4 D_Apriori算法并行化设计

1.4.1 D_Apriori算法的压缩布尔矩阵表示

Apriori算法在进行关联规则挖掘中，需要多趟扫描数据库，并在迭代过程中产生大量的候选项集，耗费大量的I/O时间，当数据量稍大时，Apriori算法的执行效率很低.因而本文提出一种基于矩阵[8]的关联规则算法D_Apriori，再结合MapReduce对该算法进行并行化改进.

改进后的D_Apriori算法在挖掘频繁项集时只需扫描一次事务数据库D，能将事务数据库转换为矩阵，矩阵中每一行的向量表示事务数据库D中的一个事务，每列对应事务中的项，矩阵中每个元素用“0”或“1”表示，下次就可以直接利用矩阵中的信息进行挖掘，不需要扫描数据事务库.矩阵中每一行表示一个事务，每一行中“1”的个数表示事务的长度，在事务矩阵中增加一列记录各事务的长度，可将不满足升序要求的行删除，降低矩阵的行维度，矩阵中的每列中“1”个数为项目在事务数据库中的支持度计数，通过给定的最小支持度，保留频繁的项目即频繁1项集，将非频繁的项目所对应的列删除，降低矩阵的列维度.

D_Apriori算法中计算支持度和删除非频繁项目所在的列算法描述如下：

输入：事务数据库D，最小支持度min_sup

输出：事务数据库D中频繁项目集的集合L

For(q=1;q

{

for(p=0;p

{ /*每项的支持度计数*/

sum=sum+M[p][q];

}

If sum<|D|.min_sup

Remove the q colume; /*删除非频繁项目所在的列*/

}

D_Apriori算法中删除长度小于k+1的事务所在的行的算法描述如下：

For(k=1;|Lk|p>=k+1;k++)

{

For(p=0;p

{

If M[p][0]

Remove the p row;/*删除长度小于k+1的事务所在的行*/

}

For each X Lk do

L1中项目标识号大于X中的最大标识号的项目与X进行连接，得到C

For each k-subset sc of C

If sc Lk {delete C;}

Else Ck+1=Ck+1 {C}

For each X C k+1 do

列向量间进行与运算计算得到支持度计数X.count

{ if X.count |D|.min_sup

Lk+1={X Ck+1|X.count}

}

|Lk+1|=0;

For each X Lk+1 do

|Lk+1|=|Lk+1|+1;/*统计Lk+1中项目集的个数*/

L= Lk

}

1.4.2 D_Apriori算法的并行化设计

并行化的主要思想，将要处理的数据集均匀地划分成n块，每个节点采用D_Apriori算法发现各自的数据块的局部频繁项集，再合并各局部频繁项集，就得到全局频繁项集.

D_Apriori算法并行化改进过程如下：

(1)将事务数据库D转化为事务矩阵；

(2)将事务矩阵划分成n块，将n个数据块分配给m个节点；

(3)每个节点使用串行的D_Apriori算法扫描数据块，得到各个数据块上所有频繁项集的集合，再合并各局部频繁项集，就得到全局候选项集；

(4)将事务矩阵划分成n’个数据块，并分配到m’个节点，同时将全局候选项目集发送到各个节点中；

(5)各个节点扫描所分配到的数据，并在数据块上计算候选项集的支持度计数.用分区函数将m’个节点输出的结果分配到m”个节点上；

(6)m”个节点将相同项目集的支持度进行计数累加，并将得到的各个项目集的支持度与最小支持度s进行比较，得到局部频繁项集的集合，最后将m”个节点的结果合并，从而得到所有频繁项集的集合.

D_Apriori算法并行化后只需要扫描一次事务数据库，利用MapReduce将数据分配到各个节点上并行计算，实现了将原本由单机处理的计算任务分配到多个节点上并行处理，简化了生成候选项的连接步骤，同时在计算的过程中对事务进行压缩，提高了运算速度，改善了算法的性能，D_Apriori算法未并行化前，时间复杂度为O(m1k.n)，假设每个节点可以处理w个计算任务，则并行化改进后的D_Apriori算法的时间复杂度为O(m1k.n/w).

2 仿真实验及分析

2.1 Hadoop平台实验环境搭建

实验环境采用9个Hadoop集群节点进行实验，采用主从式架构，其中一台作为NameNode主节点和JobTracker主节点，其余的8台作为DataNode从节点和TaskTracker从节点，操作系统采用Ubuntu12.04，JDK版本为1.7，Hadoop版本采用Hadoop-1.2.1.

2.2 实验结果与分析

该实验采用的数据源为来自某超算中心某大型超市购物的数据，大小约为3GB，Map节点数分别为2、3、4、5、6、7、8个节点的Hadoop集群模式，为了进一步比较串行并行算法的优势，选取结点数为4的实验数据作为并行算法的代表，其中CS1含有较小的数据量，所耗的资源相对小，并行化的效果不明显，因而该实验采用CS2～CS5作为并行算法的实验数据，数据见表1.

表1 并行D_Apriori算法实验数据

(1)串行并行算法的比较分析

实验过程中分别记录下单机模式和集群模式下运行大小不同数据集所需要的时间(单位为秒)，见表2.

表2 单机模式和集群模式数据集运行时间

为了分析该并行算法的可行性，只对CS2～CS5数据集的运行时间进行对比，其对比结果如图2所示。

图2 串行Apriori算法与并行D_Apriori算法的运行时间对比

(2)加速比分析

加速比是用于衡量本次实验中并行算法的并行效率的标准，根据加速比公式，得到并行Apriori算法的加速比，并将结果记录于表3.

表3 并行D_Apriori算法的加速比

其加速比的比较图如图3所示.

图3 并行D_Apriori算法的加速比比较图

从以上分析可以看出，在处理小规模数据集时，串行算法的处理时间小于并行算法的处理时间，但随着数据集规模的增大，任务所需的资源的比例也随之增大，并行算法的加速比性能越来越好，体现出了并行算法的优势，并行化的D_Apriori算法更适合应用于大规模数据的处理.

3 结束语

在数据挖掘中关联规则是重要的数据挖掘算法，是通过多次扫描数据库来产生频繁项集，但面对海量数据时，需要花费大量的时间和空间，因而利用Hadoop平台实现Apriori算法的并行化，从而解决海量数据问题，实验表时，并行化后的D_Apriori算法具有良好的加速比，适用于对海量数据的处理，下一步将会继续研究将其他数据挖掘算法也移值到Hadoop平台上实现算法并行化，增强云挖掘系统的能力.

参 考 文 献

[1] 晏杰,元文娟.基于Apriori&FP-Growth算法的研究[J].计算机系统应用,2013,22(5):122-125.

[2] 潘婷.基于物联网服务平台的海量传感信息Hadoop处理方法和系统设计[D].南京邮电大学,2013.

[3] 何建佳,叶春明,王祥兵,等.面向云计算的数据挖掘系统架构研究[J].计算机应用研究,2011,28(4):1372-1374.

[4] Han Jiawei,Pei Jian,Yin Yiwen.Mining Frequent Patterns Without Candidate Genneration[C]//Proceedings of ACM SIGMOD International Conference on Management of Date.New York,USA:ACM Press,2000.1-12.

[5] Agrawal R and Srikant R.Fsat algorithms for mining association rules in large databases[C].In Proceedings of 20th International Conference on Very Large Data Bases,1994.478-499.

[6] 董西成.Hadoop技术内幕-深入解析MapReduce架构设计与实现原理[M]..北京:机械工业出版社,2013.

[7] 林长方,吴扬扬,黄仲开,等.基于MapReduce的Apriori算法并行化[J].江南大学学报:自然科学版,2014,13(4):411-415.

[8] 戴新喜,白似雪.一种高效的基于布尔矩阵的Apriori改进算法[J].广西师范大学学报:自然科学版,2007,25(4):176-179.