基于PC集群的并行FP-Growth算法的研究与实现

论文摘要

FP-Growth算法是当前挖掘频繁项集算法中应用最广，并且不需要产生候选项集的频繁项集挖掘算法。它通过对源数据库的两次扫描，将全部数据项信息压缩到一个称为FP-tree的数据结构中，将数据库频繁模式的挖掘问题转化成挖掘FP-tree的问题。然而，在处理海量数据时，生成的FP-tree数据结构极为复杂，生成频繁集并挖掘频繁项集生成强关联规则过程，对内存和处理器要求极高。并行算法可以将计算任务合理地分配集群中的各个计算节点，因此对并行FP-Growth算法的研究在频繁项集挖掘中具有十分重要的现实意义。本文深入研究了并行计算理论、高性能计算集群和FP-Growth算法，对并行计算机的体系结构、并行算法的设计方法、高性能计算集群的创建技术和FP-Growth算法各个步骤有良好的理解。为了实现FP-Growth算法的并行化，本文对并行FP-Growth的一些典型算法进行了分析，发现它们主要是基于硬件同构并行计算平台，对算法中计算节点负载均衡在硬件异构并行计算平台并未加于考虑，因此，这些算法在硬件异构并行计算平台中的性能不佳。为了实现PC集群下的并行FP-Growth算法，本文设计和实现了一个高性能计算集群，提出并实现了一种在硬件异构计算平台上的并行FP-Growth算法。实验结果表明，使用本文所提出的算法后，在仅有三个计算节点的集群环境中加速比可达到2.3以上。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 背景与研究意义
• 1.2 国内外研究现状
• 1.3 论文的主要工作
• 1.4 章节安排
• 第二章 并行计算理论
• 2.1 并行计算机
• 2.1.1 并行计算机的发展概况
• 2.1.2 并行计算机的指令流与数据流
• 2.1.3 并行计算机的存储方式
• 2.1.4 并行计算机的分类
• 2.2 并行编程模型
• 2.2.1 并行编程基本思想
• 2.2.2 并行编程模型
• 2.2.3 MPI 简介
• 2.3 并行编程
• 2.3.1 并行计算机上问题的一般求解过程
• 2.3.2 并行算法设计
• 2.3.3 MPI 程序执行的一般流程
• 2.3.4 并行算法的性能度量
• 2.4 本章小结
• 第三章 高性能计算集群的研究与实现
• 3.1 集群系统概述
• 3.1.1 集群概念和基本体系结构
• 3.1.2 集群系统的分类
• 3.2 高性能计算集群
• 3.2.1 典型高性能计算集群体系结构
• 3.2.2 高性能计算集群的硬件组成
• 3.2.3 高性能计算集群的软件组成
• 3.3 基于 Linux 的高性能计算集群的设计与实现
• 3.3.1 硬件拓扑结构设计
• 3.3.2 软件逻辑结构设计
• 3.3.3 MPICH 安装与介绍
• 3.3.4 MPI 编程基础
• 3.4 本章小结
• 第四章 基于 PC 集群的并行 FP-Growth 算法的研究与实现
• 4.1 数据挖掘概述
• 4.2 关联规则及频繁项集挖掘算法
• 4.2.1 关联规则相关概念
• 4.2.2 关联规则挖掘的类型
• 4.2.3 FP-Growth 算法的详细描述
• 4.3 基于 PC 集群的并行 FP-Growth 算法的设计与实现
• 4.3.1 并行 FP-Growth 算法的设计
• 4.3.2 计算节点间的性能均衡
• 4.3.3 算法的具体实现
• 4.4 算法的性能评估与分析
• 4.5 本章小结
• 第五章 总结与展望
• 5.1 工作总结
• 5.2 未来工作展望
• 致谢
• 参考文献