摘要 | 第4-5页 |
ABSTRACT | 第5-6页 |
1 绪论 | 第10-18页 |
1.1 研究背景和研究动机 | 第10页 |
1.2 研究现状 | 第10-14页 |
1.2.1 树模式挖掘算法 | 第10-13页 |
1.2.2 分布式模式挖掘算法 | 第13-14页 |
1.3 主要工作和创新点 | 第14-15页 |
1.4 本文的组织结构 | 第15-18页 |
2 相关概念和算法 | 第18-26页 |
2.1 基本概念 | 第18-24页 |
2.1.1 树的定义和表示 | 第18-19页 |
2.1.2 树模式的类型 | 第19-21页 |
2.1.3 树的标准型 | 第21页 |
2.1.4 模式支持度 | 第21-24页 |
2.1.4.1 事务型 | 第22-23页 |
2.1.4.2 单树型 | 第23-24页 |
2.1.5 树模式挖掘问题的定义 | 第24页 |
2.2 分布式计算框架 | 第24-25页 |
2.3 本章小结 | 第25-26页 |
3 基于MapReduce的事务型树模式挖掘 | 第26-48页 |
3.1 问题的引出 | 第26页 |
3.2 一个高效的串行挖掘算法:SLEUTH | 第26-28页 |
3.3 基于MapReduce的挖掘算法:TETPM | 第28-39页 |
3.3.1 基本框架 | 第29-31页 |
3.3.1.1 准备阶段 | 第29-30页 |
3.3.1.2 迭代阶段 | 第30-31页 |
3.3.2 负载均衡策略 | 第31-33页 |
3.3.3 TETPM算法的实现 | 第33-36页 |
3.3.3.1 TETPM算法在Hadoop上的实现 | 第33-34页 |
3.3.3.2 TETPM算法在Spark上的实现 | 第34-36页 |
3.3.4 算法复杂度分析 | 第36-38页 |
3.3.4.1 TETPM-P算法 | 第36-37页 |
3.3.4.2 TETPM-E算法 | 第37-38页 |
3.3.5 TETPM-P和TETPM-E的比较 | 第38-39页 |
3.4 实验分析 | 第39-46页 |
3.4.1 实验环境和数据集 | 第39-41页 |
3.4.1.1 实验环境 | 第39页 |
3.4.1.2 实验数据集 | 第39-41页 |
3.4.2 实验结果分析 | 第41-46页 |
3.4.2.1 单机算法的局限性 | 第41-42页 |
3.4.2.2 不同阈值下算法性能对比 | 第42-44页 |
3.4.2.3 Hadoop和Spark上算法运行对比 | 第44-45页 |
3.4.2.4 并行度对TETPM算法的影响 | 第45-46页 |
3.5 本章小结 | 第46-48页 |
4 基于MapReduce的单树型模式挖掘 | 第48-70页 |
4.1 整体框架 | 第48-56页 |
4.1.1 枚举候选模式阶段 | 第48-49页 |
4.1.2 本地挖掘阶段 | 第49-53页 |
4.1.2.1 扩展外部子孙节点策略 | 第49-50页 |
4.1.2.2 通过路径匹配算法计算实例路径 | 第50-53页 |
4.1.3 全局统计阶段 | 第53-54页 |
4.1.4 EtpmLtd算法 | 第54-56页 |
4.2 EtpmLtd算法的优化 | 第56-59页 |
4.2.1 通过本地支持度筛选模式 | 第56-57页 |
4.2.2 通过支持度约束减少通讯 | 第57-58页 |
4.2.3 EtpmLtd+算法 | 第58-59页 |
4.3 算法复杂度分析 | 第59-63页 |
4.3.1 EtpmLtd算法 | 第61-62页 |
4.3.2 EtpmLtd+算法 | 第62-63页 |
4.4 实验分析 | 第63-69页 |
4.4.1 实验环境和数据集 | 第63-64页 |
4.4.1.1 实验环境 | 第63-64页 |
4.4.1.2 实验数据集 | 第64页 |
4.4.2 实验结果分析 | 第64-69页 |
4.4.2.1 不同阈值下算法性能对比 | 第65-68页 |
4.4.2.2 并行度对算法的影响 | 第68页 |
4.4.2.3 数据集规模对算法的影响 | 第68-69页 |
4.5 本章小结 | 第69-70页 |
5 总结与展望 | 第70-74页 |
5.1 本文的主要贡献 | 第70-71页 |
5.2 工作展望 | 第71-74页 |
参考文献 | 第74-80页 |
致谢 | 第80-82页 |
硕士期间研究成果 | 第82-83页 |