基于FP-Growth关联规则的并行算法分析及其应用研究

论文摘要

随着现代科学技术的发展,计算机科学与技术的进步,数据挖掘作为一门崭新的知识发现技术学科得到了快速的发展。数据挖掘（Data Mining）就是从大量的、不完全的、有噪声的、模糊的、随机的大型数据中挖掘那些令人感兴趣的、有用的、隐含的、先前未知的和可能有用的模式或知识。由于我们在科学研究以及日常事务中积累了大量的数据资料,如果不借助有用的工具去发现其中潜在有用的信息,即使是知识的海洋,我们也将信息贫乏,很多有用的信息也不能够被我们发现。由于以往的算法如:经典算法Aprior算法需要多次扫描数据库,产生大量候选项集,而FP-Growth算法需要建立庞大FP-Tree占用大量内存,它们在效率上不高,当面临十分庞大的数据库时,其算法在效率上显然不足,也不能够适应大型数据库的数据挖掘,效率问题成为该研究与应用的关键和难点。FP-Growth算法采用分而治之的策略,把数据库中的频繁项集压缩到一棵频繁模式树（FP-tree）中,同时保留项集之间的关联信息,再将FP-tree划分为一些条件模式库分别进行挖掘。由于不用多次扫描数据库,不产生候选项集,其效率显然比Apriori算法高,但是该算法由于要建立FP-tree需要占用大量内存,所以不适用于大型数据库进行数据挖掘。Parallel Algorithm算法是指在并行机上,将一个任务分解成多个子任务（task）,分配给多个不同的处理器（process）,各个处理器之间相互协同合作,并行地执行子任务,从而达到加速求解速度或者求解应用问题规模的目的。本论文研究的是基于FP-Growth关联规则的并行算法问题,通过对当前FP-Growth和Parallel Algorithm的一些关键技术的研究,提出一种基于FP-Growth关联规则的并行算法分析及其应用研究。该算法针对以往算法的缺点和不足,在FP-Growth算法基础上,借助并行算法的思想,将数据库分块以及保留数据相关性不变的FP-tree树划分算法,同时将任务合理分配,并将它们进行合理组合,在负载平衡,多处理器调度上做了相应的研究,使任务达到合理分配组合、实现了较好的负载平衡,提高了算法速度,此算法适用于大型数据库的数据挖掘,相对以往算法,在效率上有了显著的提高。

论文目录

• 致谢
• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 研究的目的和意义
• 1.3 本文主要工作
• 1.4 论文的组织结构
• 2 数据挖掘概述
• 2.1 数据挖掘基本概念
• 2.2 数据挖掘的功能
• 2.3 数据挖掘的对象
• 2.4 数据挖掘的技术与过程
• 2.5 数据挖掘的方法
• 2.6 数据挖掘的应用
• 2.7 数据挖掘面临的挑战及发展趋势
• 3 关联规则挖掘算法与分析
• 3.1 关联规则简介
• 3.2 关联规则研究现状
• 3.2.1 关联规则国外研究现状
• 3.2.2 关联规则国内研究现状
• 3.3 关联规则定义性质与应用
• 3.3.1 关联规则基本概念
• 3.3.2 关联规则性质
• 3.3.3 关联规则应用
• 3.4 关联规则分类
• 3.5 关联规则挖掘的主要步骤
• 3.6 经典算法分析
• 3.6.1 Apriori 算法分析
• 3.6.2 FP-Growth 算法分析
• 4 并行算法分析
• 4.1 并行计算相关概念
• 4.1.1 并行计算定义
• 4.1.2 并行计算基本条件
• 4.1.3 并行计算目的
• 4.1.4 并行算法设计过程
• 4.2 MPI 基本概念
• 4.2.1 什么是MPI
• 4.2.2 MPI 的结构
• 4.2.3 MPI 的目的
• 4.2.4 MPI 程序设计简介
• 4.3 并行效率评价方法
• 4.4 并行计算典型算法
• 4.4.1 任务分配算法
• 4.4.2 负载平衡问题
• 4.4.3 多处理机调度近似算法
• 4.5 并行程序性能优化
• 5 基于FP-Tree 关联规则的并行算法分析
• 5.1 基于数据库划分的并行算法
• 5.1.1 新算法思想
• 5.1.2 新FP-tree 并行算法实现步骤
• 5.1.3 实验结果
• 5.1.4 结论
• 5.2 基于Split 的 FP-Growth 新并行算法
• 5.2.1 新算法的设计思想
• 5.2.2 新算法的特点
• 5.2.3 新算法仿真
• 5.2.4 新算法性能分析
• 5.3 基于FP-Growth 关联规则并行算法在中医心脏病治疗上应用研究
• 5.3.1 中医诊断治疗的基本原理
• 5.3.2 基本数据预处理
• 5.3.3 关联规则并行算法的实现步骤
• 5.3.4 实验结果及其分析
• 结论
• 参考文献
• 作者简历
• 学位论文数据集