没有合适的资源?快使用搜索试试~ 我知道了~
采用N-list结构的混合并行频繁项集挖掘算法.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 32 浏览量
2022-11-01
20:15:07
上传
评论
收藏 681KB DOCX 举报
温馨提示
试读
33页
采用N-list结构的混合并行频繁项集挖掘算法.docx
资源推荐
资源详情
资源评论
随着信息技术的快速发展,大数据在互联网、社交网络以及物联网等领域
得到了广泛的应用。大数据的出现对工业、医疗以及政府机构在内的许多社会
主体具有重要意义
[1]
。如何快速并准确地从这些海量数据中挖掘出有价值的信
息和知识已经成为当今社会迫切需要解决的问题之一
[2]
。
数据挖掘又称为知识发现(knowledge discover in database,KDD),其目的
在于发现大量数据中有价值的信息。常见的数据挖掘任务有分类、聚类、关联
规则等。其中关联规则分析是其重要的研究方向之一。通过对关联规则挖掘算
法的研究能够在海量数据中找出有价值的规则,这些规则对企业管理上的决策
具有巨大帮助
[3]
。传统的关联规则挖掘算法主要分为三类:(1)产生-测试方
法,此类算法先通过迭代产生候选项集并分别计数,然后根据最小支持度阈值统
计得到频繁项集,典型算法是 Agrawal 等人提出的 Apriori 算法
[4]
;(2)模式增
长方法,此类算法在挖掘过程中不会产生候选项集,而是将所有的频繁项压缩成
一种树结构,通过对树的直接遍历挖掘频繁项集,典型算法有 FP-Growth
[5]
、LP-
tree
[6]
等算法;(3)垂直格式方法,此类算法主要是将水平数据集转换成垂直格
式,通过交运算来得到频繁项集,典型算法为 Eclat 算法
[7]
。大数据环境下,随着
数据量的不断增加,运行时间和内存使用量成为传统关联规则挖掘算法的重要
瓶颈,单纯通过提升计算机硬件水平已经不能满足人们对大数据分析与处理的
需求。此时并行化的计算思想变得尤为重要,通过改进传统的关联规则挖掘算
法,并与分布式计算模型相结合成为当前研究的主要方向。
近年来,Google 开发的 MapReduce 并行编程模型由于其操作简单、自动
容错、负载均衡、扩展性强等优点深受广大学者和企业的青睐
[8]
。同时 Hadoop
作为一种广泛使用的 MapReduce 开源框架,不仅实现了对 MapReduce 的动态
调用,而且在很大程度上促进了 MapReduce 的应用开发。目前许多基于 Map-
Reduce 计算模型的关联规则挖掘算法已成功应用到大数据的分析与处理领域
中。文献[9,10,11]采用 Apriori 算法多次迭代的思想,在每次迭代过程中启用一
个 MapReduce 任务,实现了 Apriori 算法在大数据领域的应用。然而此类算法
在挖掘频繁项集时不仅需要多次扫描事务数据集而且会生成大量候选项集,极
大 降 低 了 并 行 算 法 的 挖 掘 效 率 。 鉴 于 并 行 Apriori 算 法 的 固 有 缺 陷 , 文 献
[12,13,14,15,16]通过将 MapReduce 计算模型与 FP-Growth 算法相结合提出
了并行的 FP-Growth 算法。与并行 Apriori 算法不同,此类算法在挖掘过程中不
产生大量的候选项集,并且只需要扫描两次事务数据集,在每个计算节点上构建
局部 FP-Tree 树,通过对局部 FP-Tree 树的遍历得到局部频繁项集,然后将其合
并得到全局频繁项集。在挖掘频繁项集的过程中,各节点之间计算独立,既不需
要相互等待也不需要交换数据,极大提高了并行频繁项集挖掘算法的效率。然
而并行 FP-Growth 算法在挖掘过程中需要消耗大量的计算资源来递归构建频
繁项的 FP-Tree 树,且大数据环境下各节点所构造的局部 FP-Tree 树的规模十
分巨大,对于这些 FP-Tree 树的存储需要消耗大量的内存。考虑到并行 Apriori
算法与并行 FP-Growth 算法的不足,文献[17,18,19]提出了并行 Eclat 算法,此类
算法虽然计算简单,在一定程度上克服了从海量事务数据集中挖掘频繁项集时
存在计算能力不足的问题,但并行的 Eclat 算法需要将水平数据集转化为垂直
数据集作为输入数据 ,然后采用类 Apriori 方法迭代挖掘频繁项集,这在大数据
环境下是无法实现的。
为了充分利用不同算法各自的优点,减少并行计算中单个节点的内存需求
量 与 节 点 之 间 的 通 信 量 ,Liao 等 人
[20]
提 出 了 一 种 将 dist-Eclat
[17]
与 传 统 FP-
Growth
[5]
算法相结合的混合算法——MRPrePost 算法。该算法主要分为三个阶
段:首先通过调用一次 MapReduce 任务得到频繁 1 项集 F-list;然后构造 F-list
所对应的 PPC-Tree 树,并对 PPC-Tree 树进行先序和后序遍历产生频繁项的
N-list;最后对 F-list 进行分组,并分布在多个计算节点上进行频繁项集的挖掘。
相较于其他单一的并行频繁项集挖掘算法,该算法既能对原始数据集进行无损
压缩,又可以快速计算项集的支持度。此外,该算法将对树的挖掘过程转化成与
垂直格式交运算类似的 N-list 合并过程,并且该过程不需要将 PPC-Tree 树保存
在内存中,极大减少了算法的计算时间和内存使用量。然而该算法仍存在几个
明显不足:(1)在 F-list 分组阶段,该算法未能充分考虑到集群负载均衡对算
法性能的影响,容易造成数据划分中计算节点负载不均衡的问题;(2)在合并两
个频繁项集的 N-list 结构时不仅要逐一比较两者中的每一项,而且需要将初步
获得的 N-list 结构中(先序,后序)序列相同的 PP-code 合并,极大地降低了 N-list
的合并效率;(3)在并行挖掘频繁项集阶段,该算法是通过合并任意两个 k-项集
的 N-list 结构来生成(k+1)-项集,会产生大量的冗余搜索。针对上述问题,本
文提出了一种基于 N-list 结构的混合并行频繁项集挖掘算法(hybrid parallel
frequent itemset mining algorithm based on N-list,HP-FIMBN) 。首 先,该 算
法充分考虑到集群负载对并行算法挖掘效率的影响,设计负载估计函数(load
estimation function,LE)用于计算出频繁 1 项集中每项的负载量,并提出基于贪
心策略的分组方法(grouping method based on greedy strategy,GM-GS),将
F-list 中的每一项根据其负载量进行均匀分组,既解决了数据划分中计算节点负
载不均衡的问题,又降低了集群中各节点上子 PPC-Tree 树的规模。其次,提出
预先放弃策略(early abandon strategy,EAS),该策略不仅能避免两个 N-list
结构在合并过程中的无效计算,而且不需要遍历初始 N-list 结构就能得到最终
的 N-list,极大地提高了 N-list 结构的合并效率。最后,该算法采用集合枚举树
[21]
作 为 搜 索 空 间 , 并 提 出 超 集 等 价 剪 枝 策 略 ( superset equivalent
strategy,SES),来避免挖掘过程中的冗余搜索,生成最终的挖掘结果。实验结
果表明,该算法在大数据环境下进行频繁项集挖掘具有较好的效果。
1 相关概念介绍
定义 1(PPC-Tree 树
[22,23]
) PPC-Tree 树是一种树形数据结构,树中的每
个节点均由以下五部分组成:
item-name:节点名称
count:节点计数
pre-order:先序编码
post-order:后序编码
children-list:子节点列表
定 义 2(PP-code 编 码
[22,23]
) PP-code 编 码 又被 称为 先序后 序 编码 ,由
pre-order、post-order 和 count 三部分组成。对于 PPC-Tree 树中的任意节点
N,称为该节点的 PP-code 编码。
性 质 1 ( 祖 先 孩 子 关 系
[22,23]
) 给 定 PPC-Tree 树 中 任 意 两 节 点 N1 和
N2(N1≠N2)的 PP-code,若满足以下关系:
N1.pre-order<N2.pre-order
(1)
N1.post-order>N2.post-order
(2)
则称 N1 节点是 N2 节点的祖先节点, N2 为 N1 的孩子节点。
定义 3(频繁 1 项集的 N-list
[22,23]
) 在 PPC-Tree 树中,代表相同项的所有
PP-code 编码按照先序遍历升序连接生成的序列,被称为频繁 1 项集的 N-list。
定义 4(“ ≺”关系
[22,23]
) 给定频繁 1 项集中的任意两项 i1 和 i2,若 i1 的支
持度大于 i2 的支持度,则表示为 i2≺i1。
定义 5(k-项集 N-list
[22,23]
) 给定任意两个具有相同前缀的频繁(k-1)-项集
XA 和 XB,其对应的 N-list 结构分别表示为:
N−list(XA)={(x11,y11,z11),(x12,y12,z12),⋯,(x1m,y1m,z1m)}
N−list(XB)={(x21,y21,z21),(x22,y22,z22),⋯,(x2n,y2n,z2n)}
则 k-项集 XAB 的 N-list 定义如下:
( 1 ) 对 于 任 意 (x1p,y1p,z1p) ∈ N-list(XA)(1≤p≤m), 若 满 足 条 件
x1p<x2q,y1p>y2q,则将 (x1p,y1p,z2q)加入到 XAB 的 N-list 中,得到初始的 N-
list。
(2)遍历 XAB 的 N-list,将 pre-order 和 post-order 相同的 PP-code 进行
合并,得到最终的 N-list。
性 质 2 ( 频 繁 项 集 的 支 持 度
[22,23]
) 给 定 项 集 X, 其 N-list 为
(x1,y1,z1),(x2,y2,z2),⋯,(xm,ym,zm),则项 X 的支持度为 z1+z2+⋯+zm。
2 HP-FIMBN 算法
HP-FIMBN 算法主要包括获取频繁 1 项集、频繁 1 项集分组和并行挖掘频
繁项集 3 个阶段。(1)在获取频繁 1 项集阶段,启用一次 MapReduce 任务,采
用类似 World Count 方法并行获取频繁 1 项集 F-list。(2)在频繁 1 项集分组
阶段,为了避免数据划分中出现计算节点负载不均衡的问题,提出 GM-GS 分组
方法,该方法先通过负载估计函数 LE 计算出频繁 1 项集中每一项的负载量,然
后根据贪心思想将 F-list 进行均匀分组,生成分组列表 G-list。(3)在并行挖掘
频繁项集阶段,主要包括并行挖掘频繁项集的 Map 阶段和 Reduce 阶段。在 Map
阶段主要是根据前两个阶段生成的 F-list 列表和 G-list 列表构造出映射路径。
在 Reduce 阶段首先调用 insert_tree 函数在各个计算节点上生成子 PPC-Tree
树。然后通过遍历本地 PPC-Tree 树,在各个节点上生成局部 2-项集的 N-list 结
构。在此过程中为了加快完成 N-list 结构的合并任务,提出预先放弃策略 EAS,
来减少合并过程中的无效计算。最后在挖掘频繁 k-项集(k>2)的过程中采用集
合枚举树作为搜索空间,并提出 SES 策略,来避免挖掘过程中的重复搜索,生成
最终的挖掘结果。
2.1 获取 频 繁 1 项 集
对于数据集 DB,其频繁 1 项集的生成过程主要包括 Split、Map、Combine
和 Reduce 四个阶段。(1)在 Split 阶段:使用 Hadoop 默认的文件块策略,将
原始数据集划分成大小相同的文件块 Block,并保存在分布式文件系统(hadoop
distributed file system,HDFS)中。(2)在 Map 阶段:每个 Mapper 节点调
用 Map()函数对输入文件块 Block 进行一次映射,以键值对 <key=item,value=1>
的 形 式 统 计 出 相 应 节 点 中 各 项 出 现 的 次 数 ; 同 时 为 了 降 低 集 群 通 信 , 经 过
Mapper 节点处理后的数据不会立刻发送给 Reduce 节点,而是先进行本地结合。
(3)在 Combine 阶段:将本地 key 值相同的键值对进行初步合并,然后再以
新的键值对作为下一阶段的输入数据传送到 Reduce 任务中。(4)在 Reduce
阶段:需要将输入的键值对进行再次合并,得到每个数据项 key 在整个数据集
中的支持度,最后根据最小支持度阈值 Min_Sup 筛选出频繁 1 项集 F-list。
为了更清楚地说明频繁 1 项集的获取步骤,本文给出事例,假设事务数据集
DB 如表 1 所示 (Min_Sup=2),表 2 是针对 DB 运行频繁 1 项集获取步骤之后得
到的 F-list。
表 1 事务数据集 DB
Table 1 Transaction database - DB
ID
Items
1
a,c,g,f
2
e,b,h
3
e,c,b,i
4
b,c,e
5
b,f,a,c,e
6
b,c,f,a
新窗口打开| 下载 CSV
剩余32页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3660
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功