基于Hadoop的DG-Apriori算法

杜佼玲，张向利

（桂林电子科技大学信息与通信学院，广西桂林 541004）

基于Hadoop的DG-Apriori算法

杜佼玲，张向利

（桂林电子科技大学信息与通信学院，广西桂林 541004）

针对Apriori算法需要多次扫描数据库、产生庞大的候选项集和计算时间过长等问题，提出一种基于Hadoop平台的DG-Apriori算法。该算法改进了频繁项集的连接方式，只需用频繁（k-1）-项集与频繁1-项集连接即可生成频繁k-项集，极大地减少了连接次数，避免了产生庞大的候选项集，并且将改进后的Apriori算法以并行处理方式移植到Hadoop平台，并行地计算频繁项集，减少了计算时间。实验结果表明，DG-Apriori算法大大提高了Apriori算法的性能。

Apriori算法；数据库；Hadoop；频繁项集

关联规则挖掘是数据挖掘领域的一个重要研究方向，其旨在挖掘事务数据库中项集之间有价值的关系。其中Apriori算法是最经典且最有影响力的挖掘关联规则算法之一，已广泛应用于商业、医疗、农业病虫害分析、网络安全、高校管理、移动通信以及气象分析等领域。针对Apriori算法中存在的多次扫描数据库和产生庞大候选项集等缺点，近年来已有很多学者对Apriori算法进行了改进，通过将事务数据库转化为矩阵表示以简化其运算，其核心思想是使用“与运算”检索事务矩阵生成频繁项集，从而提高计算效率，节省时间。罗丹等［1］用新增的2个数组记录矩阵行与列中“1”的个数，减少了扫描矩阵次数，并且去除了大量冗余非频繁项集，有效地压缩了矩阵；纪怀猛［2］分析了频繁（k＋1）-项集的生成方法，将支持矩阵与频繁2-项集矩阵结合实现快速剪枝，从而大大减少了验证频繁k-项集的计算量；苗苗苗等［3］压缩了事务矩阵，减少了算法运算量；Yu Honglie等［4］采用布尔矩阵代替事务数据库，对向量做“与运算”，并采用具有随机存储特性的数组，可直接产生k-频繁项集。一些学者采用十字链表的数据结构对Apriori算法进行了改进。黄建明等［5］将事务数据库转化为十字链表进行存储，并证明了对性能的改进；刘玉文［6］采用循环十字链表压缩事务，节省了内存空间；段仰广等［7］通过优化生成候选集的方法，减少了扫描事务数据库的次数；胡斌［8］提出了一种采用双向十字链表结构的频繁项挖掘算法，加快了频繁项的筛选过程。

但基于矩阵的Apriori算法需要多次检索并重构矩阵，且在每一项的插入和矩阵的调整方面消耗了大量时间，因此，在某些条件下并非理想选择。而十字链表结构复杂，其生成也需要耗费大量时间。为此，针对已有的串行关联规则Apriori算法诸多不足，提出一种基于Hadoop平台的DG-Apriori算法。

1 Hadoop平台

Hadoop是一个分布式系统的基础框架，源于A-pache Lucene项目的Nutch（搜索引擎子项目），它主要应用于大数据分布式处理，是用户可轻易搭建以及使用的分布式计算平台［9］。Hadoop框架主要包含分布式文件系统HDFS［10］和并行计算框架MapReduce［11］两大模块。其中，HDFS为大规模数据提供了分布式存储，它由一个主控节点NameNode和一组从节点DataNode组成，对于上层的应用程序它是透明的，具备完全透明的数据存储和访问支撑功能。MapReduce负责分布式地处理存储在HDFS中的数据。MapReduce由Map（映射）和Reduce（化简）2个过程组成，这2个过程均以Key／Value的形式输入、输出，其类型由程序员根据具体需要设定。在Map过程中，处理一批输入的键值对（k1，v1），按照相同的Key值生成一个键值对（k2，v2）列表。Map将这个键值对列表缓存，定期写入本地磁盘。在Reduce过程中，Reduce的输入为所有Mapper的输出，它先按照输入的Key值对数据进行排序，并将Key值相同的Value合并。然后通过调用Reduce函数，与指定键相关联的值进行迭代处理，生成一个键值对列表（k3，v3）。事实上，在Map和Reduce中间还有一个Combine过程，这个过程是将Map输出的键值对列表进行简单的合并，将相同Key值对应的Value进行合并，若不设定Combine，Combiner默认使用Reduce的类。Combiner的主要作用是为了合并与减少Mapper的输出，以减少网络带宽和Reduce节点的负载。

2 Apriori算法

2.1 算法思想

Agrawal等［12］于1993年提出Apriori算法，是一种挖掘单维、单层、布尔关联规则的算法，其核心思想是采用逐层搜索递推的方法。该算法的基本思想是：首先扫描事务数据库D，计算出所有1-项候选集C1的支持度，并与最小支持度min＿sup比较，产生不小于min＿sup的频繁1-项集L1；然后通过L1执行自连接（L1∞L1）和剪枝操作，生成2-项候选集C2，并根据min＿sup产生频繁2-项集L2；再由L2产生L3，如此迭代，直到Lk＝∅，算法结束［13］。

连接操作：连接频繁（k-1）-项集Lk-1生成k-项候选集Ck，可连接的条件是Lk-1中的2个元素当且仅当前（k-2）项元素相同时［14］，即设Lk＝｛l1，l2，…，ln｝，1≤i＜j≤n，当（li［1］＝lj［1］）∩（li［2］＝lj［2］）∩…∩（li［k-1］≠lj［k-1］）时，有li∞lj＝｛li［1］，li［2］，…，li［k-1］，lj［k-1］｝∈ck。

剪枝操作：Ck是Lk的超集，由Apriori性质可知，任何非频繁（k-1）-项集不属于频繁k-项集，因此，若一个k-候选集中出现其（k-1）项子集不属于Lk-1，则将该k-候选项删除。记ck∈Ck，若ck-1∉Lk-1，则ck∉Lk，则在k-项候选集Ck中删除此ck项元素。

2.2 Apriori算法分析

1）在连接操作中，利用Lk-1自连接 （Lk-1∞Lk-1）生成Ck时，需要判断是否满足连接条件，而该判断会进行多次比较，若Lk-1中有n项，则该连接操作的时间复杂度为O（（k-1）×n2）。此外，该判断过程可能产生庞大的候选集，如L1的项集个数为100，将生成4950个C2，若L1的项集个数再增加，则C2的项集个数将更大。

2）在剪枝操作中，记∀ck∈Ck，判断ck所有的（k-1）组合项是否都属于Lk-1，此过程也需要多次扫描数据库。

3）由Ck（k＝1，2，…，n）生成Lk时，需要计算ck的支持度，并与最小支持度min＿sup比较，在此过程中也要扫描n次数据库。

通过分析不难发现，Apriori算法存在可能产生庞大的候选项集、需要多次扫描数据库和进行大量支持度计算等降低算法性能的问题。因此，为了提高Apriori算法的性能，提出一种DG-Aprior算法。

3 DG-Aprior算法

3.1 相关定理及推论

定理1任何频繁项集的所有非空子集也是频繁项集，非频繁项集的超集是非频繁项集［15］。

推论1若频繁k-项集Lk还能产生频繁（k＋1）-项集Lk＋1，则Lk中项集的个数必大于k。

推论2当k≥2时，对于∀ck∈Ck，有ck∈（Lk-1∞Lk-1），则ck∈（Lk-1∞L1）。

证明（使用反证法） 假设当k≥2时，对于∀ck∈Ck，有ck∈（Lk-1∞Lk-1），且ck∈（Lk-1∞L1）。因为∃m∈ck，则有m∈Lk-1，又因为ck∉（Lk-1∞L1），那么m∉L1。这明显与当k＝2时，m∈L1相矛盾。故对于∀ck∈Ck，有ck∈（Lk-1∞Lk-1），那么ck∈（Lk-1∞L1）。

3.2 DG-Apriori算法步骤

DG-Apriori算法流程如图1所示。算法步骤为：

1）利用Hadoop Mapreduce框架中的InputFormat类对存储在HDFS上的原事务数据库D进行水平划分，将其分成多个大小相当、格式为〈Tid，Itemset〉的数据分块InputSplit，每个InputSplit都由一个Map节点独立计算。其中，Tid表示事务数，Itemset表示与之对应的项集。

2）主程序扫描每个数据分块〈Tid，Itemset〉，Map阶段计算出各自分块的所有1-项候选集C1，其格式为〈Item，1〉，然后Reduce阶段对所有mapper函数的结果合并（相同Item值计数相加，即为其I-tem的支持度），产生不小于min＿sup的频繁1-项集L1，并缓存在HDFS中供每个Map节点共享读取与使用。

3）重复步骤2），根据推论2，产生2-候选项集C2，使用Combine函数将所有mapper函数的结果合并，与min＿sup比较，得到局部频繁2-项集L2，再由Reduce函数将每个Map节点上的局部频繁2-项集L2合并，得到全局频繁2-项集L2。

4）重复步骤2）、3），生成全局频繁k-项集Lk，根据推论1条件，判断Lk元素个数是否大于k，若大于k继续执行步骤4），否则算法结束，得到最终的全局频繁k-项集Lk。

图1 DG＿Apriori算法流程Fig.1 The flow chart of DG＿Apriori algorithm

4 实验与分析

为了验证DG-Apriori算法性能，实验对Apriori算法与DG-Apriori算法进行比较。测试环境是1台PC机：Win7x64系统，8GB DDR3内存，500GB硬盘，Intel Core-i5处理器。利用虚拟机VMware Workstation搭建Hadoop集群，1台主节点Name-Node和3台从节点DataNode。每台虚拟机系统采用Ubuntu Linux10.04，Hadoop版本选取1.1.2，测试事务数据来自频繁项集挖掘数据集存储库里的经典mushroom、retail和T10I4D100K三个数据集（http：／／fimi.ua.ac.be／data／）。

1）实验1。使用mushroom数据集，其事务数Tid为8124条，项集Item为119项，比较Apriori算法与DG-Apriori算法在不同最小支持度下的运行时间，其结果如图2所示。从图2可看出，当事务数与项集数均不大时，DG-Apriori算法运行时间是Apriori算法的1／2～1／3，随着最小支持度的增加，2种算法的运行时间都在递减，可见DG-Apriori算法性能明显优于Apriori算法。

2）实验2。使用retail数据集，其事务数Tid为88 162条，项集Item为16 469项。比较Apriori算法与DG-Apriori算法在不同最小支持度下的运行时间，其结果如图3所示。从图2可看出，当事务数与项集数相差不大时，DG-Apriori算法运行时间几乎是Apriori算法的1／3，随着最小支持度的增加，2种算法的运行时间都在递减，但Apriori算法递减相对缓慢，且随着最小支持度的增加，当最小支持度大于20%，运行时间几乎不变，而DG-Apriori算法几乎呈指数状递减，可见DG-Apriori算法性能明显优于Apriori算法。

图3 retail数据集的DG-Apriori与Apriori的运行时间Fig.3 The running time of DG-Apriori and Apriori algorithm in retail data set

3）实验3。使用T10I4D100K数据集，其事务数Tid为100 000条，项集Item为1000项。比较Apriori算法与DG-Apriori算法在不同最小支持度下的运行时间，其结果如图4所示。从图4可看出，当事务数远远大于项集数时，DG-Apriori算法运行时间是Apriori算法的1／4～1／6。随着最小支持度的增加，2种算法的运行时间都在递减，虽然DG-Apriori算法递减相对缓慢些，但一直都保持着低运算时间状态，亦可说明DG-Apriori算法性能明显优于Apriori算法。

图4 T10I4D100K数据集的DG-Apriori与Apriori的运行时间Fig.4 The running time of DG-Apriori and Apriori algorithm in T10I4D100Kdata set

5 结束语

针对串行关联规则Apriori算法的不足，提出了一种基于Hadoop平台的改进的DG-Apriori算法。该算法改进了频繁项集的连接方式，只需用频繁（k-1）-项集与频繁1-项集连接即可生成频繁k-项集，大大减少了连接次数，从而极大地减少了数据库的扫描次数，避免了产生庞大的候选项集，并且将改进后的Apriori算法移植到Hadoop平台上优化，以并行方式计算频繁项集。实验结果表明，DG-Apriori算法减少了算法的运算时间，加快了频繁项集的生成过程，提高了算法的效率。下一步工作：1）用不同的计算机搭建Hadoop集群，并增加其节点数，在不同节点数下对比DG-Apriori算法与Apriori算法的运行时间；2）采用更大规模的事务数据库进行对比测试。

［1］ 罗丹，李陶深.一种基于压缩矩阵的Apriori算法改进研究［J］.计算机科学，2013，40（12）：75-80.

［2］ 纪怀猛.基于频繁2项集支持矩阵的Apriori改进算法［J］.计算机工程，2013，39（11）：183-186.

［3］ 苗苗苗，王玉英.基于矩阵压缩的Apriori算法改进的研究［J］.计算机工程与应用，2013，49（1）：159-162.

［4］ YU Honglie，WEN Jun，WANG Hongmei，et al.An improved apriori algorithm based on the boolean matrix and Hadoop［J］.Procedia Engineering，2011，15：1827-1831.

［5］ 黄建明，赵文静，王星星.基于十字链表的Apriori改进算法［J］.计算机工程，2009，35（2）：37-38.

［6］ 刘玉文.基于十字链表的Apriori算法的研究与改进［J］.计算机应用与软件，2012，29（5）：267-269.

［7］ 段仰广，韦玉科.基于循环十字链表的频繁模式挖掘算法［J］.计算机技术与发展，2009，19（10）：73-76.

［8］ 胡斌，张天，胡勇.基于双向十字链表的频繁项集挖掘［J］.科学技术与工程，2014，14（12）：68-72.

［9］ 赵龙.基于Hadoop的海量搜索日志分析平台的设计和实现［D］.大连：大连理工大学，2013：5-6.

［10］ GARCIA H，LUDU A.The Google file system［C］／／ACM Sigops Operating Systems Review，2003：29-43.

［11］ DEAN J，GHEMAWAT S.MapReduce：simplelified data processing on large clusters［J］.Communication of the ACM，2008，51（1）：107-113.

［12］ AGRAWAL R，IMIELINSKI T，SWAMI A，et al.Mining association rules between sets of items in large database［J］.Acm Sigmod Record，1993，22（2）：207-216.

［13］ 何云峰.Apriori改进算法综述［J］.微型机与应用，2013，32（6）：1-3.

［14］ 黄进，尹治本.关联规则挖掘的Apriori算法的改进［J］.电子科技大学学报，2003，32（1）：76-79.

［15］ 栗晓聪，滕少华.频繁项集挖掘的Apriori改进算法研究［J］.江西师范大学学报（自然科学版），2011，35（5）：498-502.

编辑：翁史振

DG-Apriori algorithm based on Hadoop

DU Jiaoling，ZHANG Xiangli
（School of Information and Communication Engineering，Guilin University of Electronic Technology，Guilin 541004，China）

Aiming at the problem that the Apriori algorithm needs to scan the database repeatedly and generates large candidate item sets and has long computation time，a DG-Apriori algorithm based on Hadoop is proposed，The algorithm improves connection of frequent item sets，the generation ofk-frequent item sets is only needed to join 1-frequent item sets with（k-1）-frequent item sets，the connection number is greatly reduced and the huge candidate item sets are avoided.And the improved Apriori algorithm is used for Hadoop platform to compute parallel frequent item sets and reduce the computation time.Experimental results show that DG-Apriori algorithm can effectively improve the performance of Apriori algorithm.

Apriori algorithm；database；Hadoop；frequent item sets

TP301.6

：A

：1673-808X（2016）05-0387-04

2016-03-10

国家自然科学基金（61363031，61461010）；广西高校云计算与复杂系统重点实验室研究课题（14101）；桂林电子科技大学研究生教育创新计划（GDYCSZ201450）

张向利（1968-），女，陕西渭南人，教授，博士，研究方向为物联网技术、网络化监控系统。E-mail：xlzhang＠guet.edu.cn

杜佼玲，张向利.基于Hadoop的DG-Apriori算法［J］.桂林电子科技大学学报，2016，36（5）：387-390.