导　　师： 陈国良;冯禹洪

授予学位： 硕士

作　　者： (）;

机构地区： 深圳大学

摘　　要： 许多数据挖掘算法都是基于加权图的,如聚类分析、协同过滤等,然而在应用这些算法之前,必须先构造出加权图。从给定数据集中提取出加权图包括确定顶点、特征提取和计算边的权值,当提取的特征可以被表示为一组独立的属性时,则可以使用Jaccard相似系数来计算两个顶点集合间的边权值。然而计算任意两个集合交集计算的高计算复杂度、I/O,以及需要消耗大量的存储资源使得大规模图边权值计算具有挑战性。基于MapReduce和FP-tree的图边权值计算已经证明了其从大规模数据集中提取出加权图的显著性能。然而,经过进一步分析发现,现有的算法可以进一步优化。体现在1.原算法对数据库进行了多次扫描。2.FP-tree结构存在非必要的信息,这些都延长了算法的执行时间。3.应用不适当的Mappers/Reducers-to-cores映射策略可能会耗尽集群资源从而导致作业执行失败。4.计算节点负载不均,经过分析发现,并行FP-tree算法的分组策略是影响挖掘计算负载的关键因素,现有的基于FP-tree的图边权值计算算法采用基于相同项频度的分组策略,在算法执行过程中出现数据倾斜、计算负载不均的问题。本文针对现有基于FP-tree的大规模加权图边权值计算在MapReduce多核集群环境下存在计算负载不均、流程设计有待优化等问题,提出了相应的优化方案:1.重新设计了基于FP-tree的图边权值计算的算法设计流程,仅包含两个MapReduce作业,减少了一次数据库的扫描;2.提出了特定于边权值计算的精简FP-tree结构,减少了建树时间;2.分析讨论并用实验评估两种Reducers与核之间的映射策略:one-Reducer-one-core和one-Reducer-multiple-cores;4.提出基于贪心均衡负载的分组策略实现了集群计算节点间的负载均衡。本文算法评估阶段,使用真实的社交网络生成的大规模应用数据集,评估现有的和优化后的基于FP-tree的图

关 键 词： 加权图提取 边权值计算 多核 集合交集计算 负载均衡

领　　域： []