基于频繁项集挖掘的2FP-Forest算法及其并行化处理研究
发布时间：2021-09-06 10:16
伴随着数据的几何式增长,大数据时代如约而至。大数据时代最重要的任务是收集数据和整理数据,数据挖掘是重要的一步,也是最基本的一步。其中在海量数据中挖掘频繁项集是数据挖掘中最基本的一项工作,深受广大国内外研究者们的重视与研究。目前,频繁项集挖掘算法的改进,基本都是基于经典的Apriori算法与FP-Growth算法进行的改进。FP-Growth算法存在如下缺点:扫描第一遍数据集只统计1-项集的支持度,而对数据集的扫描消耗时间较多;FP-Tree只是简单的将具有相同前缀进行合并,没有考虑路径上的项集是否可能构成频繁项集,没有控制FP-Tree的深度、宽度和结点个数,在数据量增大时内存消耗过多;条件FP-Tree的规模较大,使得递归挖掘的深度增加。因此,本文提出了基于频繁项集挖掘2FP-Forest算法并定义了2FP-Tree和2FP-Forest数据结构。2FP-Forest算法在遍历第一遍数据集时,统计所有1-项集和2-项集的支持度,并进行剪枝。本文在2FP-Forest中,充分利用2-项集的剪枝作用,在构建过程中进行充分的剪枝和合并结点等操作,使得2FP-Forest中不存在非潜在候选3...
【文章来源】：长春工业大学吉林省
【文章页数】：54 页
【学位级别】：硕士
【部分图文】：
基本剪枝策略1示例
枝策略是基本剪枝策略 1 的基础上的扩充，它也是基于 Apriori 性节点{1，2}，按词典序子集枚举树的定义，它的侯选扩展项集为展下一级节点时，必须计算项集{1，2，3}和{1，2，4}的支持度，行扩展时，已经得到项集{1，3}为非频繁项集，由 Apriori 性质可知频繁项集，因此重复计算项集{1，2，3}的支持度没有任何意义。限定节点 N 的侯选扩展集CX(N)来自于 N 的父节点P 的频繁扩展对已知非频繁项集合重复进行频度计算，可以有效的提高频繁项集同样，对于采用深度优先策略算法挖掘较长的频繁项集时，可以较空间，效果更好。图 2.2 是基本剪枝策略 2 的例子，我们可以看到行下一级扩展时，它的候选扩展集为{4}，避免了重复计算项集{繁项集挖掘算法riori 算法
遍数据库之后，利用得到的频繁 1-项集对事务记录重排序的事务构建 FP-Tree。构建 FP-Tree 时，首重排序的事务插入到树中。如果在树中存在要插入果添加项不存在树中，则在树中重新开一个分支。程如下：事务 ID 事务中的元素 过滤和重排序001 r,z,h,j,p z,r002 z,y,x,w,v,u,t,s z,x,y,003 z z004 r,x,n,o,s x,s,005 y,r,x,z,q,t,p z,x,y,006 y,z,x,e,q,s,t,m z,x,y,表 2-3 过滤事务与原事务元素比较
【参考文献】：
期刊论文
[1]基于Spark的并行FP-Growth算法优化与实现[J]. 陆可,桂伟,江雨燕,杜萍萍. 计算机应用与软件. 2017(09)
[2]一种基于Spark框架的并行FP-Growth挖掘算法[J]. 张稳,罗可. 计算机工程与科学. 2017(08)
[3]转换时间数据流的加权FP-Tree挖掘算法[J]. 宋军,陈潇君. 江苏大学学报(自然科学版). 2017(03)
[4]基于Hadoop的FP-Growth关联规则并行改进算法[J]. 厍向阳,张玲. 计算机应用研究. 2018(01)
[5]基于排序树的频繁项集挖掘算法[J]. 王红梅,党源源,胡明,刘大有. 吉林大学学报(工学版). 2016(04)
[6]基于MapReduce和矩阵的频繁项集挖掘算法[J]. 周国军,龚榆桐. 微电子学与计算机. 2016(05)
[7]基于MapReduce的并行关联规则增量更新算法[J]. 程广,王晓峰. 计算机工程. 2016(02)
[8]NB-MAFIA:基于N-List的最长频繁项集挖掘算法[J]. 沈戈晖,刘沛东,邓志鸿. 北京大学学报(自然科学版). 2016(02)
[9]MapReduce编程模型下的约束频繁模式挖掘算法[J]. 闫晓妩,张继福,荀亚玲,赵旭俊. 小型微型计算机系统. 2015(10)
[10]压缩FP-Tree的改进搜索算法[J]. 吴倩,罗健旭. 计算机工程与设计. 2015(07)
硕士论文
[1]基于Hadoop的改进的并行Fp-Growth算法[D]. 周诗慧.山东大学 2013
本文编号：3387273
【文章来源】：长春工业大学吉林省
【文章页数】：54 页
【学位级别】：硕士
【部分图文】：
基本剪枝策略1示例
枝策略是基本剪枝策略 1 的基础上的扩充，它也是基于 Apriori 性节点{1，2}，按词典序子集枚举树的定义，它的侯选扩展项集为展下一级节点时，必须计算项集{1，2，3}和{1，2，4}的支持度，行扩展时，已经得到项集{1，3}为非频繁项集，由 Apriori 性质可知频繁项集，因此重复计算项集{1，2，3}的支持度没有任何意义。限定节点 N 的侯选扩展集CX(N)来自于 N 的父节点P 的频繁扩展对已知非频繁项集合重复进行频度计算，可以有效的提高频繁项集同样，对于采用深度优先策略算法挖掘较长的频繁项集时，可以较空间，效果更好。图 2.2 是基本剪枝策略 2 的例子，我们可以看到行下一级扩展时，它的候选扩展集为{4}，避免了重复计算项集{繁项集挖掘算法riori 算法
遍数据库之后，利用得到的频繁 1-项集对事务记录重排序的事务构建 FP-Tree。构建 FP-Tree 时，首重排序的事务插入到树中。如果在树中存在要插入果添加项不存在树中，则在树中重新开一个分支。程如下：事务 ID 事务中的元素 过滤和重排序001 r,z,h,j,p z,r002 z,y,x,w,v,u,t,s z,x,y,003 z z004 r,x,n,o,s x,s,005 y,r,x,z,q,t,p z,x,y,006 y,z,x,e,q,s,t,m z,x,y,表 2-3 过滤事务与原事务元素比较
【参考文献】：
期刊论文
[1]基于Spark的并行FP-Growth算法优化与实现[J]. 陆可,桂伟,江雨燕,杜萍萍. 计算机应用与软件. 2017(09)
[2]一种基于Spark框架的并行FP-Growth挖掘算法[J]. 张稳,罗可. 计算机工程与科学. 2017(08)
[3]转换时间数据流的加权FP-Tree挖掘算法[J]. 宋军,陈潇君. 江苏大学学报(自然科学版). 2017(03)
[4]基于Hadoop的FP-Growth关联规则并行改进算法[J]. 厍向阳,张玲. 计算机应用研究. 2018(01)
[5]基于排序树的频繁项集挖掘算法[J]. 王红梅,党源源,胡明,刘大有. 吉林大学学报(工学版). 2016(04)
[6]基于MapReduce和矩阵的频繁项集挖掘算法[J]. 周国军,龚榆桐. 微电子学与计算机. 2016(05)
[7]基于MapReduce的并行关联规则增量更新算法[J]. 程广,王晓峰. 计算机工程. 2016(02)
[8]NB-MAFIA:基于N-List的最长频繁项集挖掘算法[J]. 沈戈晖,刘沛东,邓志鸿. 北京大学学报(自然科学版). 2016(02)
[9]MapReduce编程模型下的约束频繁模式挖掘算法[J]. 闫晓妩,张继福,荀亚玲,赵旭俊. 小型微型计算机系统. 2015(10)
[10]压缩FP-Tree的改进搜索算法[J]. 吴倩,罗健旭. 计算机工程与设计. 2015(07)
硕士论文
[1]基于Hadoop的改进的并行Fp-Growth算法[D]. 周诗慧.山东大学 2013
本文编号：3387273
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3387273.html
