2019年3月
第40卷第3期
计算机工程与设计
C O M P U T E R E N G I N E E R I N G A N
D D
E S I G N
Mar.2019
Vol.40 N o.3
Hadoop环境下基于并行熵的FIUT算法挖掘
晏依，徐苏
(南昌大学信息工程学院，江西南昌330031)
摘要：针对传统频繁项集挖掘算法效率低下的问题，提出基于H a d o o p平台的并行B M R-F I U T算法。通过引入F IU-T re e
((r e q u e n t it e m s u lt r a m e t r ic t r e e)结构挖掘频繁项集，避免传统算法的缺陷；改进F I U T算法的分解过程，使之适应于M ap-
R e d u c e框架下的并行计算，达到并行化的目的；利用并行熵作为集系统的负载均衡度量，使系统尽可能在各节点间合理 分发数据以平衡负载。实验结果表明，B M R-F I U T算法能够有效减少并行化过程中节点负载倾斜的问题，较现有的P F P-
G r o w t h算法具有更好的性能，适用于海量数据挖掘。
关键词：数据挖掘；频繁项集；M a p R e d u c e编程模型；F I U T算法；并行熵；负载均衡
中图法分类号！T P311文献标识号：A文章编号$1000-7024 (2019) 03-0685-06
doi:10. 16208!. is s n l000-7024. 2019. 03. 016
Mining research on FIUT algorithm based on
parallel entropy in Hadoop environment
YAN Y i，XU Su
(School (( Information Engineering，NanchangUniversity，Nanchang 330031，China)
Abstract： Focusing on the inefficient problem 〇(traditional algorithms (or mining frequent itemsets & a Balanced一MapReduce_F I U T (B M R-F I U T)based on Hadoop platform was proposed.By introducing freque tree (FIU-Tree)structure，frequent i t emsets were mined & effectively avoiding the defects of the traditional algorithm.The process of decomposition was improved with F I U T algorithm t o adapt to i t s parallel comput duce &achieving the purpose of parallelization.The parallel entropy was used as the load balance measurement so that system could in a l l reasonable to distribute data as much as possible between every nodes.Experimental results show that
B M R-F I U T algorithm can effectively reduce the problem about load inclination of any node in the process superior to the existing PFP-Growth algorithm a nd i t has better performance on mining volume Keywords：data mining；f requent items; MapReduce programmingmodel；F I U T algorithm； parallel entropy； load balance
/引言
传统的串行化频繁项集挖掘（F I M)算法主要有A p­ron 算法和 F P-G o w t h算法 ，然而随着大数据时代的到来，传统单机环境下F I M算法的性能迅速降低，分布式并行处 理成为大数据挖掘的首选方案。Hadoop框架是一个能够处 理P B级别以上数据的开源分布式系统架构，其两大核心模 块是：H D F S(hadoop distributed f i l e system)和 M a p R e­duce，利用 MapReduce 来处理 H D F S上的数据具有高容错 的优点。MapReduce编程模型已经被广泛应用于众多大数据分析领域，国内外学者也开始在传统F I M算法的基础上 衍生出许多针对大数据处理的向MapReduce模型迁移的并 行F I M算法研究[1]，其基本思想都是利用H D F S解决海量 数据存储问题，MapReduce完成并行化挖掘的任务。文 献[2]利用Hadoop框架并基于事务缩减的思想对算法进 行优化，实现了改进的A p t r算法；文献[3]提出了一 种基于布尔矩阵和M a p R e d u c e的FP-G r o w t h算法；文 献[4]在M a p R e d u c e框架的基础上，提出基于FP-Gro w t h的S O N算法的并行化实现。这些算法具有很好的 扩展性，但仍受到传统F I M算法的限制，并且在并行化算
收稿日期：2018-01-16；修订日期：2018-02-26
作者简介：晏依（1993 -)，女，江西九江人，硕士，研究方向为数据挖掘与数据仓库；徐苏（1964 -)，男，江西南昌人，硕士，教授，硕士生导师，研究方向为网络信息安全。
E-mail：512970l26@qq
•686 •计算机工程与设计2019 年
法的过程中往往发生负载不均衡的情况，降低程序执〇
为此，本文提出基于M a p R e d u c e模型的并行B M R- F I U T算法，于H a d o o p平台上实现了对F I U T算法[5]在分 布 的，分配策略，完成负载不均 的，提高 。
1 MapReduce编程模型
基于幵34〇〇卩平台的编程模型，其设计灵 感源自于WisZ 编程语言，是一种应用 模数处理的分布 计算模型，该模型 计 1象到）a p和两个函数，基本格式如下：
)狂卩：〈'#，T# &:L is t(〈'2&%#
R e d u c e:〈'2，W ist(B2)&:〈'3，b3&。
M a p R e d u c e采用分治策略，将大规模的计算任务分解 成若 务，交给由一个 管 的多个工作节处理，的计 程相互 ，然 些工作 的任务结果规约处理，最终 输出，执行过程如 图1所示。
图1MapReduce编程模型执行过程
MapReduce模型具体的工作流程如下：
(1) MapReduce首先将输入文件切分成若干个独立的 数据分片Split，分片中的数据会被 〈key，value &的键 作为 传递给M a p，每个分片分别应一个 M a p务。
并行计算框架()用户编写的MapReduce程序会被系统分发部署到 集中的若 ，其中一个 作为 程（M a s­ter)，其余节点为工作进程 （Worker)。
()主控进程负责分配系统中空闲的Worker分别处理 M a p或者Reduce任务，并监控各个W o r k e r的工作状态。
分片被分配给处理M a p任务的Worker后，根据一定 的映射规则生成一批新的〈key，value&中间键值对作为输 被缓存在内存中。
()缓存中的数据经过分区排序操作后会被溢写到本 地磁盘中，所有的溢写文件最后会被归并（Merge)成一个 磁盘文件。Master将记录各个分区在磁盘中的存储情况，并通知处理Reduce任务的Worker读取它所负责分区中的 中。
(5) Reduce任务接收来自各个M a p上输出的中间数后执行归并操作，聚集每个唯一 k e y的键 其分发到
同一个Reduce，最后通过调用Reduce函数产生输出并存储 到H D F S中。
2 FIUT算法描述
F I U T算法使用了一种更为高效的树结构FIU-T e e，通过将事务中的每个频繁项压缩到一个节点并建立相应路 径 构 程，有 的存储，该
树叶子节点的计数值便可直接获取频繁项集。F I U T算法需 要对D B。第一 ，包含所有频繁
-项集的 #第二 ，第一 的结果 ：每条事务中的 繁项，包 繁项的事务 ，
接着再 FIU-T e e的构造和挖掘。
由以上分析可以看出，F I U T算法与Aprior算法相比，它只扫描两遍D B且不产生候选项集，避免了重复扫描D B
的缺陷#也无需像FP-G o w t h算法那样需要大量递归遍历 构造条件子树，的。F I U T的
基本 如 ：
定义1通过删除事务中的非频繁项得到由'个频繁项 组成的'-itemset集合。
定义2 FIU-T e e是一个树形结构，它的数据结
构如 ：
()根为null，项集-1，2,…，厶}表示一条以h作为 根节点的 ，^作为结点的路径，每个'-item-
set 中的项目 顺序按字典序 。
()将具有相同长度的项目集作为路径插入FIU-Tree。
(3) FIU-Tree 的非叶子结点由 item-name 和 node-li 两个字段构成，item-n a m e即项目名称，node-link指向链接
的指针# 结点包 个字段，分 ：item-n a m e和count，count是指以该叶子节点结尾的路径上 包含所有项目的数量。
推论'-FIU-T e e的所有叶子节点均处于同一高度'。
F I U T算法的执行主要分为两个阶段。第一阶段，扫描
D B计算所有项的支 繁-项集#然后，再 描
，有 繁项生成'-itemets；第二阶段，重
复构建'-FIU-T e e，挖掘并释放它，其中'从M降到2,
M表示'能取到的最大值。FIU-Tree构建和挖掘的具体过 程如 ：
构造'-FIU-T r e e需要把每一个Z i-itemsets分解为
'-itemsets，（' +1%^%M)，并与原始的'-itemsets
合并生
第40卷第3期晏依，徐苏$Hadoop环境下基于并行熵的F IU T算法挖掘•687 •
成新的'-i t e m s e t s集合，再开始构建'-F I U-T r e e。
首先标记该'-F I U-T r e e树的根节点r o o t为n u ll，并把 每个'-i t e m s e t的第一个项作为r o o t的子节点#然后，依次 遍历第2至（'一 1)项，标记第m个项作为第（rn — 1)个 节点的子节点，其中2<rn<$— 1)；重复该遍历过程直 到进行到第'项，检查第'项是否作为第（'一 1)个节点 的，若第'项存在则增加该 结点的c o u n t计数，即该路径 有 的项目 的支持度，否则为该项添加一个新的 结点作为第（'一 1)个 的叶子节点，并设定c o u n t值为1，此时这颗'-F I U-T e e构造完 成；最后通过遍历该'-F I U-T e e各个叶子节点上的cou n t ，选择 小支持度的叶子路径 有项目的 •即接获取频繁'项集。
3基于MapReduce的FIUT算法的实现
由以上F I U-T e e的构造过程可以看出，F I U T算法生 成'-i t e m s e t s时需要分解所有的Zi-item sets，其中A>'，从而构造'-F I U-T e e挖掘频繁出'项集。这将使得构造
'-F I U-T e e非常耗时，并且'-F I U-T e e的构建是按'值递 减的顺序 的，这些问题将导致在构建'-F IU-
T r e e的过程中，'项集的产生依赖于Z项集，只能顺序生 成'项集，因此F I U T不 挖掘。其在并行挖掘中的不足之处，本节基于M a p R e d uc e编程模型，提 出一种M R-F I U T算法对其改进，使之能被较好地应用于
H a d o o p环境下的并行F I M挖掘。以下是对M R-F I U T算法 具体 "
M R-F I U T算法主要改进在F I U T算法的第二阶段，在这里'-ite m s e t s被直接分解为（'一 1)、（'一 2)， (2)
it e m s e ts而不是顺序分解生成'-it e m s e t s。通过这个方式，长项集和短项集的生成是相互独立的，即可以并行产生。基于H a d o o p平台的M R-F I U T算法需要经过3轮M a p R e­duce 任务迭代 ，其 中各个 M a p任务能够并行产生 '-i t e m-s e t s，解决了 F I U T算法在并行化时的问题，M R-F I U T算 法具体设计过程如图2所示。
图2 M R-F I U T算法流程
3.1 第一轮M a p R e d u c e迭代
第一个MapReduce用来生成频繁1-项集集合Flist。首 先H D F S把存储在其中的D B划分为若干数据分片Split，M a p的输入键值对为〈key = offset，value= T C &，其中 key为事务在数据库中的偏移量，T-
代表分片中的每一条 事务；然后每个M a p分别读取对应分片，该阶段m a p的任 务是负责计算每个项的支 生成局部-项集，输出键值对〈k e y] item，value ] 1 &，key为项目名称；接着，在 shuffle阶段，经过M a p操作后产生的每个唯一 k e y的中间 键值对会被分别发 应的reduce 务，re­duce 的工作是把具有相同 key 的局部 -项集进行合并操作，统计其计数进行输出，输出格式为〈key ] item，value] sup >，sup代表该项对应的支持度计数；最后选择大于最 小支持度的项目，即可获取全局频繁-项集集合Flit。
3.2 第二轮M a p R e d u c e迭代
第二个MapReduce的任务是用来移除每条事务中的非频繁项生成'-itemsets，此时需要再次扫描数据库，根据上 一步得到的频繁-项集来删减每条事务中的非频繁项。各 个M a p仍然读取Split作为输入，在第二轮m a p操作开始 前，先将第一轮MapReduce工作生成的频繁-项集存放于 本地内存中；接着执行m a p函数移除每条事务中的非频繁 项，输出形式为〈key ] '-itemset，1 >的中间键值对，其 中'-itemset由被删减后的项目个数和项目内容组成；再将 中间结果shuffle给相应的Reduce进行处理，Reduce任务 统计来自不同节点传递过来的具有相同长度的'-itemsets，进行归后输出键值对形式为〈key ='value = '-itemset< s u m>，产生的k e y代表项目个数，value为项目内容及其个(
3.3 第三轮M a p R ed u ce迭代
第三个MapReduce是M R-F I U T算法的核心。在该阶 段，每个M a p任务负责将第二个MapReduce任
务产生的 '-itemsets分解成2至（'一 1)项集，然后把在D B
中被删
•688 •计算机工程与设计2019 年
减后得到的Fitemsets与被m a p分解后得到的相同长度的 项目集合并，构建本地？FIU-Tree。该步骤中M a p将第二 个MapReduce产生的<key,value >作为输人，然后执行 M a p函数。M a p任务在该阶段主要负责3个工作：①分解 6-itemsets;②构造F F I U-Tree;③挖掘频繁项集。当集 中所有m a p任务处理完成之后，产生一组key为项目个数，value值为一颗FIU-Tr e e的键值对；Reduce通过归并各个 M a p
发送来的相同长度的FIU-Tree，构造出全局&-FIU-Tree，这颗？FIU-Tree的叶子结点记录了由该叶子结点所 在路径上所有节点组成的项目集合的支持度，因此通过检 查最终F F I U-Tree叶子结点的计数值，遍历大于最小支持 度的节点路径即可得到频繁项集。
由对第三个MapReduce任务的分析可以看出，在该过 程中可以利用多个M a p任务独立的分解;—itemsets，各个 m a p e r作业是完全并行的，有效提高了 I/O性能；并且 F I U T算法无需递归挖掘FIU-T r e e即可获得频繁项集，FIU-Tree在被挖掘后会被释放，大大降低了系统的计算和 存储开销，因此相比原始的F I U T算法，M R-F I U T算法可 以很好地被运用在海量数据的挖掘之中。
4系统负载均衡的优化
M R-F I U T算法在第二阶段的分解过程中，没有充分考 虑到每个M a p任务的分解代价，当第三个MapReduce任务 开始后，任务被分发到各节点，但是每个节点的计算量不 一样，这将导致系统产生负载倾斜的问题，而负载均衡问 题是分布式并行计算里的关键性问题[6，]。
M R-F I U T算法的第三个MapReduce任务完成—tem-sets的分解过程。将一个&项集分解成2至$—1)项集的 代价可表示为
C21C31—
—
  1 c r1) " 2' ;' ;  2
其中，（2<'<M)，所以分解'C e m s e t的时间复杂度为 0$')。可以看出-temset中项的个数和它的分解代价成 指数关系，当项集长度增大时，其分解代价也会极具增加，而分解代价的大小直接关系着节点负载倾斜的问题，因此M R-F I U T算法中第三个MapReduce的分解代价是影 响系统负载倾斜问题的关键因素，关于如何平衡各节点的 分解代价对整个系统的影响，是决定算法成功与否重要的一步。
为了平衡H a d o o p集系统中各节点的负载，保证执 行效率，本节提出B M R-F I U T算法，定义并行熵的概念用 以准确量化系统负载情况；再结合每个节点的计算量并转 化为相应的权值，优先选择候选队列中满足条件的节点进 行任务迁移，将任务合理的分配到各节点，解决对负载均 衡的 。
B M R-F I U T算法实现的特点是：在H a d o o p集环境 下，通过设计并行熵对系统负载进行量化，使各节点之间能够根据当前的负载情况自发完成项目迁移调整，精准反 映了集系统的负载情况。
4.1并行熵介绍
熵的物理意义是表示体系的混乱程度，Shannon曾在 信息论中提出了信息熵的理论解决对信息的量化度量问题，这里对其进行扩展，定义并行熵89][为系统的负载均衡度 量并运用在集环境上。并行熵能够根据各节点总任务计 算量的实时情况动态的进行调整，达到负载均衡的目的。
并行熵的基本理论思想"在集系统中，程序的运行 时间主要取决于负载最重节点上的总计算量大小，即该节 点上所有任务的负载情况；当并行熵朝着最大熵增的方向 迁移时，各个节点的负载趋向于平衡，使负载较重节点和 负载过轻节点上的计算量都尽可能达到均衡状态，从而减 少程序运行时间；当并行熵达到最大值时，意味着此时集 中各节点计算量一致，程序运行时间最小。因此在对集 系统做负载均衡策略的过程中，每一次的迁移步骤，都 尽可能的取最大熵增的迁移，就能在最大程度上缩短程序 运行时间，由此可见并行熵可以准确的度量系统的负载均 衡性能。
对Hadoop集进行负载均衡的优化过程中，项目分 影响 负载的重要 ，为 证 个 的计算量均衡，首先需要量化每个节点的负载大小。
假设4代表长度为™的项集，N,(4)代表节点z中包 含L的个数，定义4的负载权值w(4)为2"，其中2"表 示分解m项集的时间复杂度。依据负载权值的定义，节点i 上所有"项集的负载L,$»)可表示为
L i(I") = 2" X N i(I m)$)给定X$其中X代表节点i上的随机项目集，则节 点i的负载g，可被表达为
q, = #L,(.X)$)
的负载为该 负载与 负载之比，若数据集被划分至t个数据节点，相对负载G，可 被为
G i =q j#q q$)
'3=1
定义3在Hadoop集环境下事务数据库被划分在t 个数据节点时，并行熵H(D)定义为
t
H(D) =；X logG.$)并行熵的大小与系统数^分布的合理性存在直接联系。当各节点的负载q值相等时，这意味着节点之间的计算量 一致，此时H(F)达到最大值为1，程序执行时间最短，系统负载均衡；相反，H(F)越小，表明各节点之间产生 较大的计算量差距，导致较差的负载性能，当H(F)为0 时，代表计算量将全部集中在一个节点。
此在 负载均衡处，要 能
第40卷第3期晏依，徐苏$Hadoop环境下基于并行熵的F IU T算法挖掘•689 •
HCD)的值以提高程序运行效率。据此提出负载均衡策略:
①将具有最大g，值节点上的任务向最小g，值的节点进行调
。②将负载过重的W乙）的项集向负载过轻
的。
4.2基于并行熵的负载均衡策略具体设计
本用作为的负载均衡度量，决定任务
迁移。首先凡，的值对
有很大影响。当高时，务迁移v频
繁，更多处理时间#，若？，负载
严重不均，。
的负载由项目的计算量情况及各节点
上所有项目的计算量量。本的目
能的中所有的计算量平衡状态，节点
处理的任务都能在大致内，运‘
间。因此，选择节点负载g作为负载指标，每一步的迁
移工作都尽可能高的值，当爿
，负载较重的计算量，中其它节
点的计算量趋于平衡，最终完成负载均衡目标。据此，
基于负载均衡的B M R-F I U T的具体步
骤如下：
$)当第三个M a p R e d u c e工作开始将所有任务分发到 各节点后，计算此时系统的并行熵值？C D)。当？〇)))时，系统负载均衡，不需移，算法结束，否则进入步骤$)#
$)计算集系统的平均负载
$)计算各节点相对平均负载的差值：A g=g—g胃，然 后创建队列Q P存放"g& 0的节点，并按"g值降序排列；同时选取A g<0的节点按| "g|值的大小顺序降序存入队 列Q k。队列Q P和Q k中节点的排列顺序对应第$)步做 移工作时该 被选择的优先级顺序。
$)设定待迁移任务的负载阈值为Wmin，当Wmin过小时 该任务的迁移 负载均衡性能影响不大，反而占用一分内存 多 移 ，故对负载 小于COmin的任务不 。首先 队列Q p中的优先级顺序获队列首端的节点作为 移源节点，，选择 ，中负载权值最大的项目，若 移项目的负载权值
O$w)%"，则对该项目迁移；然后，根据Q m队列中的优 先顺序选择〇(乙）％l"g I的目标节点7，这步操作的原理 就是选定Q m队列中I"g I与被迁入的任务负载最接近的，在 负载不超 系统平均负载的 ，先朝着 的方向 移# 选定的项目入。
$)更新各节点的负载，返回步骤$)。
B M R-F I U T算法流程如图3所示。
图3 B M R-F I U T算法流程
5实验结果与分析
本节通过实验对M R-F I U T算法和基于负载均衡的 B M R-F I U T算法的性能进行测试和分析。实验在H a d o o p 集配置@个，采用构，包括1个N a m e N o d e，6 个D a ta N o d e。每个节点配置I n t e l c o r e i5-2450M C P U2. 50G H\40B内存，并运行在w i n7操作系 统上，安装H a d o o p!  6. 2和J D K1. 7.0_25，算法采用Java 语言实现。实验数据集选取F requen t Item set M in in g Data R e p o i o H1
0]里的T1014D100K. d a t，该数据集大小为3.84M B，包含10万条记录，有870个属性，每个事物的 平均长度为10。由验结果具有一定的不稳定性，因此每个实验的最终结果均为5 验结果的平均值，其中设的最小支为5f。
5.1算法加速比比较
加速比可以反映集系统的并行化性能，用
表示，当集中节点数目为n时砑可表示为
S p ee d U p (n)=t1/tn(6)其中，8指算法在单节点上的运行时间，8指算法在多节 点上的运行时间。为了测试本文所提出的M R-F I U T算法 的有效性，实验通过将P F P-G o w t h算法[11]与M R-F I U T 比较，在不同个的加速比如图4 示。
图4显示，随着集中数据节点个数的增加，两种算 法的加速比都有所提高。这是因为M R-F I U T算法和P F P
-

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。