Hadoop下负载均衡的频繁项集挖掘算法研究

朱文飞　齐建东　洪剑珂

(北京林业大学信息学院　北京 100083)



Hadoop下负载均衡的频繁项集挖掘算法研究

朱文飞齐建东洪剑珂

(北京林业大学信息学院北京 100083)

摘要频繁项集挖掘FIM(Frequent Itemsets Mining)是关联规则挖掘算法的重要组成部分。而经典Apriori和FP-Growth算法在海量数据处理时面临内存占用、计算性能等方面的瓶颈。基于Hadoop云计算平台，提出适用大数据处理的频繁项集挖掘HBFP(High Balanced parallel FP-growth)算法，设计后缀模式转换的数据分割及均衡任务分组方案，使计算节点本地拥有计算所依赖的数据，实现不同节点相互独立的并行数据挖掘方法，并保证算法全局的负载均衡特性。实验数据表明，HBFP算法能均匀地将计算量分散至不同计算节点，并行且相互独立地进行FP-Growth挖掘过程，算法效率提高了约12%，算法全局稳定性及效率取得提升。

关键词频繁项集挖掘FP-Growth算法Hadoop并行计算

0引言

关联规则挖掘是通过对大数据集数据分析发掘潜在数据关联特性的过程，主要由频繁项集挖掘和关联规则生成两个阶段组成。前者对大规模数据集进行挖掘计算，后者则根据频繁项集生成目标规则。其中，频繁项集挖掘算法是影响关联规则质量和算法效率的主要因素。关联规则挖掘中的频繁项集算法可分为搜索算法、层次算法、数据集划分算法、抽样算法等[1]。最早关注关联规则挖掘的Agrawal等人于1994年提出Apriori算法[2]。其多次扫描、建立候选集的特性导致算法具有I/O吞吐量大、内存占用量随数据集增大而骤升的先天缺陷。Han等人提出FP-Growth算法[3]规避大量候选集引发的内存占用问题，采用FP-Tree结构压缩原始数据集。通过两次数据扫描及FP-Growth的递归调用完成整个数据挖掘过程，算法执行效率及空间复杂度均有较大改进。

随着数据规模的不断膨胀，数据集大小呈指数级增长，大规模数据下的数据挖掘具有其特殊性，频繁项集挖掘中多种算法受数据规模的影响具有较大的性能差异。改进Apriori和FP-Growth的算法[4-6]围绕分治与并行化设计方案，对算法在大数据应用方面进行探索。Pruned FP[7]及FPMFI[8]通过构建条件FP树的优化剪枝策略，减少算法递归次数，提升算法效率，但算法对数据平衡分组未展开详细描述。Li等人提出了FP-Growth并行算法PFP[9]，在MapReduce框架下将数据集和计算任务分配至不同计算节点中，在云计算平台下实现大数据下频繁项集挖掘。PFP改进算法[10,12]对原始PFP算法进行优化，通过改进数据分组方式及构建局部频繁模式树提高算法效率及适用性。ABH算法[13]利用数组随机存储的效率改进FP树结构，在Hadoop平台下有效减少了候选集规模，从而改进算法效率。文献[14]中分布式FP-Growth的动态任务分配原则试图满足任务分配的公平性，但由于未考虑不同任务间计算量差异，节点计算量分配具有不同程度的波动性。

面向大数据处理的FIM算法通过在云计算框架下实现数据的特征提取与数据挖掘工作，而其中分布式计算正确性、公平性方面仍有诸多疑问亟需解决。因此本文提出的HBFP算法在Hadoop平台通过数据分割、计算量预估及任务均衡化分类策略实现计算任务在分布式环境的负载均衡，解决并行算法中计算分配的公平性问题，保证计算结果的正确性，改进海量数据中频繁项集挖掘算法的性能表现。

1相关概念及描述

设集合I={I1,I2,…,In}，数据事务集D={T1,T2,…,Tt}由多条事务Ti组成，每条事务为多个项Ii的集合，存在Ti⊆I。

定义2若存在项的集合I，满足support(I)>Thresh，其中Thresh为支持度阈值，则称该项集I为频繁项集；当集合包含k个元素，称其为频繁k项集，记为Lk。

定义3候选集Ck表示k项元素组成事务的所有集合。

定义4项Ik的条件模式基表示树结构中所有Ik元素至根节点的前缀路径组成的集合，不含节点Ik本身。

Apriori性质[2]任意频繁项集的非空子集必为频繁项集，称为向下封闭性；非频繁项集的超集必不是频繁项集。

基于FP的算法依赖于FP-Tree的压缩结构保存原始事务数据，随着数据集的不断增加，当数据量到达一定规模后，形成的FP-Tree的规模将不再扩大，本文称其为满FP树。

满FP树(Full FP-Tree)：将I={I1,I2,…,In}中项的所有组合构成的项集作为输入构建出来的FP树。

定理1满FP树中蕴含的事务总数为2n-1，满FP树中非根节点数量亦为2n-1。

(1)

由文献[3]可得FP树中包含所有输入事务的数据，则满FP树中包含事务总数为2n-1。

在满FP树中从任一非根节点出发，回溯至根节点的路径即为一条事务，从所有节点回溯至根节点的路径为该树结构中蕴含的所有事务。设满FP树中节点数量为Nnodes，则Nnodes=Nitemsets，可得满FP树中非根节点数量为 2n-1。

定理2当输入事务数据达到一定规模，FP树转变为满FP树，新的数据输入不会改变FP树规模，称满FP树具有稳定性。

2Hadoop下均衡FP-Growth算法HBFP设计

HBPF算法采用Hadoop的任务调度机制，实现节点多任务的优化调度。同时引入任务计算量预估及分配模式模型，实现不同任务的计算量均衡分配。基于短板效应的数据独立分组策略进一步保证全局算力的均衡分布。主要需解决的问题为分布式计算中如何分配数据以确保计算公平性、如何设计分布式计算模型以保证计算正确性及如何实现全局计算的负载均衡特性等，下面对算法分步骤展开描述。

步骤一数据集分布式存储，该步骤合理数据预处理是后续算法并行高效执行的基础。

步骤二频繁1项集计算，MapReduce任务通过单次数据集扫描实现所有项的并行化计数统计。

步骤三据频繁1项集对原始数据进行修剪、重排，基于“后缀模式转换”将原始数据分割为节点独立计算所依赖的子事务集合。这是节点进行独立数据挖掘并保证结果正确性的基础。

步骤四提出任务计算量的预估模型，并基于计算估值采用短板效应策略实现任务分组的均衡化分配。该步骤是实现计算任务保证计算公平性的重要步骤，最大程度保证全局负载的均衡特性。

步骤五分布式节点针对特定的项进行节点独立的FP-Growth运算，该步骤中节点使用步骤四中分配至该节点的项关联数据子事务完成本地数据计算，保证了结果正确性。

步骤六汇聚各节点不同项的频繁项集，将所获得的大量频繁项集进行排序筛选，获取关联特性最强的前N条频繁项集。

2.1数据集分布式存储

分布式计算中原始数据集被切分为多个子数据集，Hadoop平台HDFS文件系统默认以64 MB为单位分配数据至不同节点。而大量小文件的数据处理时应利用CombineFileInputFormat类进行数据预处理，合并小数据可提高分布式存储效率[15]。数据分布式存储的物理切分过程称为分块操作。

Map任务数量是计算并行化程度的直接表征，由Hadoop中InputFormat决定，而每个Map实际输入数据量由式(2)确定：

SplitSize=max(minSize,min(goalSize,blockSize))goalSize=totalSize/mapred.map.tasks

(2)

minSize由mapred-site.xml中mapred.min.split.size设置，goalSize由输入文件大小和map数量计算所得，blockSize由hdfs-site.xml中dfs.block.size设置。上述操作输出键值对作为后续程序数据输入，为并行化计算做分布式存储准备，该过程称为分片操作。

通过数据分块和分片操作，大数据集分布式存储在多个存储节点中。

2.2频繁1项集计算

频繁1项集计算可以归类为并行化计数统计，这是典型MapReduce任务。Map以数据分片作为输入，完成数据读取任务，输出结果为形式键值对，经Shuffle阶段完成相同项的聚集和分发，Reduce以形式数据作为输入，统计输出项对应的频次。该步骤额外完成对数据集所有项的统计，将其按频次降序排列并去除不满足支持度的项后，序列记为F_List。

利用2.1节中分片及Map任务数量优化配置，并行计算的效率将提高，算法空间及时间复杂度均为O(DB_Shardingsize)。其中DB_Shardingsize为单节点中分片数据量。

2.3修剪重排与数据分组

算法1后缀模式转换算法

输入：事务数据Ti，辅助记录表RecordList

输出：各项关联的子事务数据

Procedure: SegmentTask (key, value=Ti)

//修剪、重排

(2)items[] = Split(Ti)

(3)for i=0 to items.length -1 do

//事务分割

(4)if (RecordList.isEmpty == FALSE) then

(5)Output(< items [i], RecordList >)

(6)end

(7)RecordList.add(items [i])

(8)end

算法1正确性分析：频繁项集挖掘最终结果中，有序排列频繁项集若包含某项s，仅且存在两种情况：一类为s是频繁项的后缀，形如<…，s>；一类为s是频繁项非后缀，形如<…,s,…>。而对于一条原始事务记录而言，其按照后缀模式转换后与s相关的信息均包含在{s,}及{v,}这两条子事务记录中，不同子事务按照2.4节及2.5节分配至不同节点进行计算，经2.6节完成汇聚后结果一致，算法正确性得以保证。

经Hadoop的Shuffle处理后具有相同key的子事务将汇聚至同一个Reduce节点处理，从而该节点获取所有以key为后缀的子事务分组记录。事务修剪重排与数据分组建立过程包括：修剪与重排、事务分割、事务分组建立，该过程如图1所示。

图1　事务修剪重排与分组建立过程

2.4计算量预估与均衡化分组

获取数据集中每个项的频繁项所需的精确计算量较为复杂，BPFP算法[10]依据F_List中项e所在的位置进行频繁项集挖掘所需计算量Cost(e)的估值为：

Cost(e)=Log(P(e,F_List))

(3)

这种估值方式是利用所有项频次的汇总数据进行粗略估计。本文通过利用事务分组中项的位置信息进行计算量估值，从而在不增加计算的情况下，获取更精确的计算量预估信息。如由分组信息v,{,}，可确定位置信息为P(e,T)={5,4}，据式(4)进行该项的计算量Cost(e)的估值计算，其中P(e,Ti)为数据事务Ti中e的位置，n为包含e的数据事务总数，将F_List按此估值降序排列为Cost_List。

(4)

事务分组建立后，为满足计算均衡化分配，据计算量估值进行分组归类。假设计算节点数为N，则建立分组记录表gListN，表中每个分组对应一个计算节点计算所需要的分组数据。基于短板效应的事务分组机制为：先取Cost_List中前N项保存至gListN，将分组列表中各项的计算量之和作为该分组的计算估值；遍历Cost_List中其余各项，并依次加入gListN中计算估值最小的列表，更新对应分组的计算估值。该过程为基于短板效应负载均衡模型，最大程度实现了各节点分配计算任务的均衡化，其伪码描述为算法2。

算法2短板效应均衡算法

输入：按计算量估值降序排列的列表Cost_List，计算节点数N，分组记录表gList

输出：分组任务列表gList

Procedure: TaskSplit (Cost_List, N, gList)

(1)for i = 0 to N-1 do

(2)gList(i).add(Cost_List(i))

(3)gList (i).cost += Cost_List(i).cost

(4)end

(5)for i = N to F_List.length -1 do

(6)minNode = findMin(gList)

(7)minNode. add(Cost_List(i))

(8)minNode. cost +=Cost_List(i). cost

(9)end

2.5节点独立的FP-Growth运算

数据分组机制使得节点获取到与项相关的所有子事务数据。事务数据分组以作为输入，节点据此事务分组局部构建条件FP树，并递归调用FP-Growth算法[3]进行各项关联的频繁项集挖掘。

受均衡分组机制的作用，Reduce节点会收到不同项的事务分组，在Hadoop的Shuffle机制下，多个分组将依次有序输入。当新输入事务的key发生变化时，对已建立的FP树进行条件FP树挖掘，计算完成则获得其频繁项集，清空FP树，开始新项的FP树建立及频繁项集挖掘，该过程如图2所示。

图2　分类事务的频繁项集挖掘

分布式节点获取的项关联的子事务数据也就是完整事务数据建立FP树后该项对应的条件模式基，而在数据集庞大的前提下是无法进行完整FP树构建。通过“后缀模式转换”操作将事务分割，节点级建立条件FP树、进行条件FP树的挖掘，最终实现分而治之的分布式挖掘。

根据满FP树定理2，当数据量不断扩充时，节点本地FP规模将趋于稳定。设节点本地FP树建立后头节点数量为m，据满FP树定理1，则FP树中节点数量最大为2m-1。由此可得构建此FP树的空间复杂度为O(2m)，挖掘算法的时间复杂度应小于O(m×2m)。

2.6结果汇聚

分布式节点中FP-Growth的输出结果形如,Num}>，为使得最终挖掘结果意义清晰，该汇聚过程再进行一组MapReduce操作。Map以2.5的输出作为输入，输出形式为,Num}>的运算结果。Reduce中对项e进行排序操作后将项集ItemSets有序输出，为最终满足支持度阈值要求的频繁项集。

3实验分析

3.1参数设定

实验集群由九台高性能计算机组成，包含1台管理节点，8台计算节点，节点配置为Intel®CoreTMi7-3770 CPU @ 3.40 GHz型号CPU、4 GB内存、Intel®Q77主板，系统采用Ubuntu 14.04，Hadoop版本0.23，环境中参数设定及变量定义如表1所示。数据集的元数据采用http://fimi.ua.ac.be/data/的retail.data，并以此扩展事务数为105，2×105，4×105，8×105四个级别的测试数据集，记为{D1,D2,D3,D4}。各测试数据集的特征统计信息如表2所示，其中数据集D1的详细数据频次分布如图3所示。

表1　仿真实验参数设定

表2　数据集的特征统计信息

图3　数据集D1中项的频次分布情况

3.2结论分析

算法HBFP在不同数量级事务数据库下不同数量计算节点的关联规则挖掘性能表现如图4所示。横轴为分布式计算节点数量，纵轴表示计算完成的时间。随计算节点的增加算法完成时间减少的整体表现与Hadoop分布式计算框架中多节点并行计算的性能优势相吻合。当计算数据量并不庞大时，分布式框架的任务分配与启动时间相较于计算时间不可忽视，这将导致计算节点的增加并不会使得计算性能的显著提升。这是由分布式平台特性决定的，即分布式算法在大规模的数据计算中性能提升更加显著。

图4　HBFP算法在不同样本量及计算节点数量下的运算

PFP算法[9]是MapReduce下的FP-Growth分布式设计方案，并在Mahout开源项目进行实现。图5显示了在同等配置下PFP算法与本文提出的HBFP算法在不同计算节点的执行时间，横轴表示不同的计算节点，纵轴表示节点算法执行时间(单位：分钟)。PFP算法随机任务分配机制使得在不同节点任务完成时间差别较大，图中2号节点与5号节点的完成时间相差几倍；HBFP算法利用各分组的任务计算量预估信息进行任务分配,使得各节点任务执行时间基本在6分钟左右。并行任务的完成时间由各节点中的最大完成时间决定，数据显示HBFP算法的FP-Growth阶段的总体完成时间比PFP快近12%，HBFP算法中各节点执行任务时间相近，证明任务分配更加均衡。

图5　不同节点任务执行时间差异

(5)

图6中横轴表示支持度阈值(单位：%)，纵轴表示任务执行时间的标准差，对比了在三种分布式算法(PFP、BPFP[10]、HBFP)中节点任务分配均匀度情况。由于PFP算法任务分配并未计算不同任务量的差异，支持度阈值较小时计算任务量庞大，任务分配不均匀导致任务执行时间标准差较大；支持度阈值增大时，计算任务量相应减少，由任务分配不均而导致的节点执行时间差异缩小，标准差趋于减小。BPFP算法利用项的频次信息进行计算量估值的方式一定程度上缩小了计算节点间的任务量差异，但存在支持度阈值变化导致任务分配不均的情况。HBFP算法的短板效应均衡算法使得各节点的任务执行时间基本分布在平均值左右，受支持度阈值影响最小。但也需指出HBFP算法存在随着支持度阈值增大任务分配均衡性变差，这是由于计算任务数量减少可分配任务的粒度增大，从而导致均衡分组特性有所下降。

图6　不同支持度阈值下的节点任务执行时间标准差

4结语

本文对大数据规模下的频繁项集挖掘提出负载均衡的并行设计方案，进一步优化计算分布的均衡化，实现全局计算效率的提升。实验结果表明，在大规模数据下的频繁项集挖掘中HBFP算法具有良好的适用性。文中研究的汇聚节点仅为单一节点，在数据量异常庞大时会面临汇聚缓慢的性能瓶颈，未来需对此进一步扩展研究。

参考文献

[1] 朱绍文,王泉德,黄浩,等.关联规则挖掘技术及发展动向[J].计算机工程,2000,26(9):4-6.

[2] Agrawal R,Srikant R.Fast algorithms for mining association rules[C]//Proceedings of the 20th International Conference on Very Large Data Bases,Santiago:Morgan Kaufmann Publ,1994:487-499.

[3] Han J,Pei J,Yin Y,et al.Mining frequent patterns without candidate generation:A Frequent-Pattern Tree Approach[J].Data Mining & Knowledge Discovery,2004,8(1):53-87.

[4] 曾志勇,杨呈智,陶冶.负载均衡的FP—growth并行算法研究[J].计算机工程与应用,2010,46(4):125-126.

[5] 郑麟.一种直接生成频繁项集的分治Apriori算法[J].计算机应用与软件,2014,31(4):297-301,326.

[6] 谈克林,孙志挥.一种FP树的并行挖掘算法[J].计算机工程与应用,2006,42(13):155-157.

[7] 杨勇,王伟.一种基于MapReduce的并行FP-growth算法[J].重庆邮电大学学报:自然科学版,2013,25(5):651-657.

[8] 颜跃进,李舟军,陈火旺.基于FP-Tree有效挖掘最大频繁项集[J].软件学报,2005,16(2):215-222.

[9] Li H,Wang Y,Zhang D,et al.Pfp:parallel fp-growth for query recommendation[C]//Proceedings of the 2008 ACM conference on Recommender systems,New York:ACM,2008:107-114.

[10] Zhou L,Zhong Z,Chang J,et al.Balanced parallel fp-growth with mapreduce[C]//Information Computing and Telecommunications (YC-ICT),2010 IEEE Youth Conference on,Beijing:IEEE,2010:243-246.

[11] 章志刚,吉根林.一种基于FP-Growth的频繁项目集并行挖掘算法[J].计算机工程与应用,2014,50(2):103-106.

[12] Vu L,Alaghband G.Novel parallel method for association rule mining on multi-core shared memory systems[J].Parallel Computing,2014,8(3):1-18.

[13] Feng S R,Ye L B,Lin Z Y.Research on Parallel Association Rules Mining Algorithm Based on Hadoop[J].Applied Mechanics and Materials,2014,543(1):3625-3631.

[14] 王智钢,王池社,马青霞.分布式并行关联规则挖掘算法研究[J].计算机应用与软件,2013,30(10):113-115,119.

[15] 袁玉,崔超远,乌云,等.单机下Hadoop小文件处理性能分析[J].计算机工程与应用,2013,49(3):57-60.

RESEARCH ON LOAD BALANCED FREQUENT ITEMSETS MINING ALGORITHM BASED ON HADOOP

Zhu WenfeiQi JiandongHong Jianke

(SchoolofInformation,BeijingForestryUniversity,Beijing100083,China)

AbstractFrequent itemsets mining (FIM) is an important component of association rules mining algorithms. However, classical Apriori and FP-Growth algorithms face the bottleneck of memory occupation and computation performance when processing massive data. Based on Hadoop cloud computing platform, we proposed the HBFP algorithm of frequent itemsets mining applicable for big data processing, and designed the data partitioning with suffix mode conversion and the balanced tasks grouping scheme. This makes the nodes possess locally the data relyed on by the computation and realises the parallel data mining method with different nodes independent each other, and ensures the global load balancing characteristic of the algorithm. Experimental data indicated that the HBFP algorithm could distribute the calculation load to different computation node uniformly and run FP-Growth mining progress parallelly and mutual-independently. The efficiency of the algorithm raised about 12%, and the global stabilisation and efficiency of the algorithm were promoted as well.

KeywordsFrequent itemsets miningFP-GrowthHadoopParallel computing

收稿日期：2014-11-09。国家林业局重点课题(2013-05)；十二五科技支撑课题(2011BAH10B04)。朱文飞，硕士生，主研领域：数据挖掘。齐建东，副教授。洪剑珂，硕士生。

中图分类号TP311

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.05.010