基于Spark的并行化FP-Growth算法研究与应用

来源 :大连海事大学 | 被引量 : 2次 | 上传用户:InsideADONET
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
传统的单机数据挖掘算法由于硬件资源的限制,在分析海量数据时,挖掘效率并不能令人满意。Spark是基于内存计算的分布式计算引擎,就是为了处理海量数据而生的技术,比Hadoop的MapReduce快很多。将算法基于Spark实现并行化可以有效的提高算法对海量数据的分析效率。  FP-Growth是关联规则领域近几年提出并被广泛应用的算法。FP-Growth算法因为要用内存缓存迭代过程中的FP-Tree结构,在面对海量数据进行挖掘时,FP-Growth会遇到内存瓶颈。为了解决内存瓶颈,本文提出基于Spark将FP-Growth算法实现并行化,并命名为SpaFP(Spark-FP-Growth)算法。通过实验比较,SpaFP算法的挖掘耗时更少,运算速度更快。  因为SpaFP算法在数据分组过程中没有考虑均衡问题,可能会使某个运算节点迭代时间过长,影响整个算法的运算效率;同时传统的FP-Growth算法的项头表结构是一个数组,在迭代构建FP-Tree时匹配查找结点元素的时间复杂度高。为了提高SpaFP算法的运算效率,本文提出对SpaFP结合两方面进行优化:(1)提出一种均衡分组策略,把未分组的负载权值最大的项放在负载权值总和最小的组里面实现均衡分组;(2)提出一种新的FP-Growth的项头表结构,通过在项头表结构中加入一张哈希表达到快速访问元素的地址的目的,从而降低时间复杂度;命名为EHSpaFP(Equal-Head-SpaFP)算法。对挖掘数据规模、集群节点数量、支持度、加速比四个方面比较算法,通过用十万条和百万条数据实验,验证优化方法都有效,EHSpaFP算法具备非常高效的计算效率。  最后本文提出一种将Spark中的主题模型LDA和EHSpaFP算法相结合的文本主题深度挖掘应用,可以挖掘出大量文本中的主题知识,并且能从松散的主题词汇中挖掘出潜在的主题知识关联规则然后进行分析,也是一种海量文本信息知识发现的新思路。对一万多篇有关“一带一路”的新闻报道文本主题深度挖掘,得到海量新闻报道中隐含的主题知识关联规则以及主题知识的描述结果。
其他文献
组织文化作为提高企业竞争力的重要资源,受到了众多管理者和学者的关注,但以往研究更多关注组织文化与财务绩效的影响,而忽视组织文化与企业非财务绩效的影响,组织文化是影响员工
生鲜农产品具有供给的时令性、需求的全年性以及旺季的销售价格低于淡季等特点。为了实现生鲜农产品均衡销售,满足消费者多样性需求,推行生鲜农产品跨季销售具有十分重要的经济