Top-rank-k频繁模式挖掘算法优化及其并行化研究
发布时间：2022-02-11 03:07
数据挖掘（Data Mining）是当前数据库和信息决策领域的前沿研究方向之一,top-rank-k频繁模式挖掘是数据挖掘中挖掘rank不大于k的频繁模式的方法,可以解决传统频繁模式挖掘支持度阈值设置困难的问题。但主流的top-rank-k频繁模式挖掘算法效率有待提高,且这类算法普遍基于串行设计,难于突破单机硬件资源限制,无力应对“大数据”时代的海量数据挖掘任务,因此关于top-rank-k频繁模式挖掘算法优化及其并行化研究具有重要意义。本文的主要工作如下:（1）针对当前top-rank-k频繁模式挖掘时空耗费大的问题,提出了一种基于混合搜索的top-rank-k频繁模式挖掘算法HTK（Hybrid-search-based Algorithm of Top-rank-k Frequent Patterns）,其主要思想是:定义名为RSL（Static Doubly-linked List of Top-rank-k）的静态双链表存储top-rank-k频繁模式,采用1-模式的支持度及其在事务中后缀项的基数设计了模式区分方法,把模式区分为短模式和长模式。挖掘过程中,首先利用基于贪心策略...
【文章来源】：湖南师范大学湖南省211工程院校
【文章页数】：67 页
【学位级别】：硕士
【部分图文】：
RDD有向无环图
硕士学位论文12式数据集RDD（ResilienntDistributedDatasets）之上，这使得Spark的各个组件可以无缝地进行集成，能够在同一个应用程序中完成大数据处理。Spark具有比Hadoop更为丰富的操作算子，包含转换（Transformations）和动作（Actions）两类。转换算子完成作业中间过程处理，行动算子触发SparkContext提交Job作业。转换算子采用的是惰性计算策略，只有在行动算子提交任务时才会被触发。原始的RDD经过一系列的转换就形成了一个有向无环图DAG（DirectedAcyclegraph），如图2-1所示。图2-1RDD有向无环图图2-2所示的是Spark的集群架构图，涵盖了Spark运行流程的主要内容：首先SparkContext向ClusterManager注册并申请运行Executor资源，ClusterManager分配Executor资源；然后，SparkContext构建成DAG图并分解为Task，发送给TaskScheduler；之后Executor向SparkContext申请Task，TaskScheduler将Task发放给Executor运行，同时SparkContext将应用程序代码发放给Executor；最后，Task在Executor上运行，运行完毕释放所有资源。图2-2Spark集群架构综上，Spark对比于Hadoop的优点如下：RDD4RDD3RDD1RDD2RDD7RDD5RDD6SparkContextCacheTaskTaskCacheTaskTaskDriverProgramClusterManagerWorkerNodeWorkerNodeExecutorExecutor
Top-rank-k频繁模式挖掘算法优化及其并行化研究41图4-3并行计数过程图4-4数据划分过程（4）并行挖掘top-rank-k频繁模式。采用mapPartitions操作分区执行HTK算法。此处的HTK算法略有变化，在Gen_Subsume方法中，当两个1-模式连接时，要检查支持度更大的1-模式是否是本分组内的1-模式，如果不是则不能连接。此外，各节点挖掘的结果集Stop-k需要将不属于本分组的其余1-模式删除。（5）聚合并输出结果。利用flatMap及reduceBykey聚合各节点挖掘结果，然后sortBy，silce及saveAsTextFile等算子过滤并输出top-rank-k频繁模式。T1={[a],[c],[b],[d]}T2={[b],[a],[c],[f]}T3={[e],[a],[d]}T4={[a],[b]}T5={[c],[b],[a]}T6={[c],[d]}<[a],1>,<[b],1><[c],1>,<[d],1><[a],1>,<[b],1><[c],1>,<[f],1><[a],1>,<[d],1><[a],1>,<[b],1><[b],1>,<[c],1><[a],1>,<[c],1><[d],1><[a],3><[b],2><[c],2><[d],2><[e],1><[f],1><[a],2><[b],2><[c],2><[d],1><[a],5><[b],4><[c],4><[d],3><[e],1><[f],1>textFileflatMapreduceBykeyNode1Node2T1={[a],[b],[c],[d]}T2={[a],[b],[c],[f]}T3={[a],[d],[e]}T4={[a],[b]}T5={[a],[b],[c]}T6={[c],[d]}SortCost_list<[a],log288)><[b],log18)><[c],log8)><[d],log2)><[e],0)><[f],0)>G_list<[a],log288)><[e],0)><[f],0)><[b],log18)><[c],log8)><[d],log2)>T1’={[a]}T2’={[a],[b],[c],[f]}T3’={[a],[d],[e]}T4’={[a]}T5’={[a]}T1’={[a],[b],[c],[d]}T2’={[a],[b],[c]}T3’={[a],[d]}T4’={[a],[b]}T5’={[a],[b],[c]}T6’={[c],[d]}CutdataNode1Node2No
【参考文献】：
期刊论文
[1]了解中国,从《今日中国》开始[J]. 今日中国. 2018(12)
[2]基于Spark的Top-k对比序列模式挖掘[J]. 张鹏,段磊,秦攀,左劼,唐常杰,元昌安,彭舰. 计算机研究与发展. 2017(07)
[3]FP-growth算法改进与分布式Spark研究[J]. 邓玲玲,娄渊胜,叶枫. 微型电脑应用. 2016(05)
[4]A new algorithm for fast mining frequent itemsets using N-lists[J]. DENG ZhiHong ,WANG ZhongHui & JIANG JiaJian Key Laboratory of Machine Perception(Ministry of Education),School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China. Science China（Information Sciences）. 2012(09)
[5]基于工业设计的装备制造业产品创新开发策略[J]. 虞世鸣. 机械制造. 2012(08)
本文编号：3619760
【文章来源】：湖南师范大学湖南省211工程院校
【文章页数】：67 页
【学位级别】：硕士
【部分图文】：
RDD有向无环图
硕士学位论文12式数据集RDD（ResilienntDistributedDatasets）之上，这使得Spark的各个组件可以无缝地进行集成，能够在同一个应用程序中完成大数据处理。Spark具有比Hadoop更为丰富的操作算子，包含转换（Transformations）和动作（Actions）两类。转换算子完成作业中间过程处理，行动算子触发SparkContext提交Job作业。转换算子采用的是惰性计算策略，只有在行动算子提交任务时才会被触发。原始的RDD经过一系列的转换就形成了一个有向无环图DAG（DirectedAcyclegraph），如图2-1所示。图2-1RDD有向无环图图2-2所示的是Spark的集群架构图，涵盖了Spark运行流程的主要内容：首先SparkContext向ClusterManager注册并申请运行Executor资源，ClusterManager分配Executor资源；然后，SparkContext构建成DAG图并分解为Task，发送给TaskScheduler；之后Executor向SparkContext申请Task，TaskScheduler将Task发放给Executor运行，同时SparkContext将应用程序代码发放给Executor；最后，Task在Executor上运行，运行完毕释放所有资源。图2-2Spark集群架构综上，Spark对比于Hadoop的优点如下：RDD4RDD3RDD1RDD2RDD7RDD5RDD6SparkContextCacheTaskTaskCacheTaskTaskDriverProgramClusterManagerWorkerNodeWorkerNodeExecutorExecutor
Top-rank-k频繁模式挖掘算法优化及其并行化研究41图4-3并行计数过程图4-4数据划分过程（4）并行挖掘top-rank-k频繁模式。采用mapPartitions操作分区执行HTK算法。此处的HTK算法略有变化，在Gen_Subsume方法中，当两个1-模式连接时，要检查支持度更大的1-模式是否是本分组内的1-模式，如果不是则不能连接。此外，各节点挖掘的结果集Stop-k需要将不属于本分组的其余1-模式删除。（5）聚合并输出结果。利用flatMap及reduceBykey聚合各节点挖掘结果，然后sortBy，silce及saveAsTextFile等算子过滤并输出top-rank-k频繁模式。T1={[a],[c],[b],[d]}T2={[b],[a],[c],[f]}T3={[e],[a],[d]}T4={[a],[b]}T5={[c],[b],[a]}T6={[c],[d]}<[a],1>,<[b],1><[c],1>,<[d],1><[a],1>,<[b],1><[c],1>,<[f],1><[a],1>,<[d],1><[a],1>,<[b],1><[b],1>,<[c],1><[a],1>,<[c],1><[d],1><[a],3><[b],2><[c],2><[d],2><[e],1><[f],1><[a],2><[b],2><[c],2><[d],1><[a],5><[b],4><[c],4><[d],3><[e],1><[f],1>textFileflatMapreduceBykeyNode1Node2T1={[a],[b],[c],[d]}T2={[a],[b],[c],[f]}T3={[a],[d],[e]}T4={[a],[b]}T5={[a],[b],[c]}T6={[c],[d]}SortCost_list<[a],log288)><[b],log18)><[c],log8)><[d],log2)><[e],0)><[f],0)>G_list<[a],log288)><[e],0)><[f],0)><[b],log18)><[c],log8)><[d],log2)>T1’={[a]}T2’={[a],[b],[c],[f]}T3’={[a],[d],[e]}T4’={[a]}T5’={[a]}T1’={[a],[b],[c],[d]}T2’={[a],[b],[c]}T3’={[a],[d]}T4’={[a],[b]}T5’={[a],[b],[c]}T6’={[c],[d]}CutdataNode1Node2No
【参考文献】：
期刊论文
[1]了解中国,从《今日中国》开始[J]. 今日中国. 2018(12)
[2]基于Spark的Top-k对比序列模式挖掘[J]. 张鹏,段磊,秦攀,左劼,唐常杰,元昌安,彭舰. 计算机研究与发展. 2017(07)
[3]FP-growth算法改进与分布式Spark研究[J]. 邓玲玲,娄渊胜,叶枫. 微型电脑应用. 2016(05)
[4]A new algorithm for fast mining frequent itemsets using N-lists[J]. DENG ZhiHong ,WANG ZhongHui & JIANG JiaJian Key Laboratory of Machine Perception(Ministry of Education),School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China. Science China（Information Sciences）. 2012(09)
[5]基于工业设计的装备制造业产品创新开发策略[J]. 虞世鸣. 机械制造. 2012(08)
本文编号：3619760
本文链接：https://www.wllwen.com/shoufeilunwen/xixikjs/3619760.html
