分布式环境下的闭频繁项集挖掘算法研究

摘要

随着大数据时代的到来人们拥有的数据越来越多，如何管理和运用这些数据成为人们迫切需要解决的问题。大数据的特点之一就是数据容量大，甚至大到无法在一个数据中心进行存储，因此分布式技术成为处理大数据的最优方案之一。针对不同的应用场景人们提出了不同的分布式解决方案，如网格，集群，云计算等。分布式存储系统解决了大数据的存放问题，使人们可以更安全，更高效的管理数据，但是仅仅拥有数据还是不够的，更重要的是从海量的数据里挖掘出对人们有用的信息。 数据挖掘研究的内容就是从数据里搜索出对人们有用的知识，数据挖掘也成为知识发现。数据挖掘早期的研究着重于单机环境下的数据处理，但是随着数据的分布存储和数据数量的指数增长传统的数据挖掘算法以不能适用于当前的环境，因此许多学者针对不同的分布式环境和数据挖掘里的不同分支研究了新的能高效运行于分布式环境的数据挖掘算法。 闭频繁项集挖掘是数据挖掘领域里的重要分支，也是许多挖掘算法里的必不可少的内容。但是闭频繁项集挖掘过程复杂包含了大量的计算，如何利用分布式巨大的数据处理能力来挖掘闭频繁项集成为人们研究的热点。本文利用几种新的数据结构研究了在分布式环境下的闭频繁项集挖掘算法，提高了分布式环境下闭频繁项集挖掘的效率。 频繁模式树最初用于挖掘频繁项集，能够很好的保存项集之间的映射关系，本文第三章通过将频繁模式树进行垂直划分提出了一种改进的频繁模式树结构，称为垂直频繁模式树，并研究了基于该结构的分布式闭频繁项集挖掘算法DVFP。DVFP同时采用数据并行和任务并行的策略进行分布式的挖掘。第三章还提出了一种新的序列化方法来对VFP树进行编码，大大减少了处理节点间的通信开销。 增量式的挖掘可以灵活的处理一些动态变化的数据集，本文的第四章提出了一种增量式闭频繁项集挖掘的算法，该算法是基于一种改进的投影前缀树结构来搜索闭频繁项集。使用投影技术表示冗余节点，减少了存储空间同时在需要时又可以迅速找到相关节点，不丢失有用信息。使用投影前缀树结构还可以避免子集检测，大大减少运行时间。 混合异构计算可以充分利用CPU与GPU的处理计算能力，实现高速的并行计算。本文第五章提出了一种利用改进的垂直型数据结构在异构平台上分布式并行挖掘闭频繁项集的算法。垂直型数据格式是闭频繁项集挖掘算法里的一种重要的数据类型，这种数据结构加快了候选项集的筛选速度，通过项之间的“与”和“或”操作就能快速的找出闭频繁项集。但是垂直型的数据结构会浪费大量的存储空间，在处理大数据和稀疏型数据时这种空间的浪费会使某些基于垂直型数据结构的算法无法运行。针对垂直型数据结构的缺点，本文第五章利用分层策略提出了一种改进的垂直型数据结构，改进后的数据结构可以有效的压缩存储空间，提高内存使用率。在改进的垂直型数据结构基础上提出了一种新的闭频繁项集挖掘算法，该算法不仅能处理密集型数据，而且在稀疏型数据上也具有很高的效率。在处理大数据时，利用该算法在图形处理器上进行闭频繁项集的挖掘可以达到较高的加速比。

目录

摘要

第一章 前言

1．1 论文的研究背景与选题依据

1．2 论文的主要内容与创新

1．3 论文的组织

第二章 相关概念及模型简介

2．1 闭频繁项集挖掘

2．2 分布式计算与分布式数据挖掘

2．3 基于OpenCL的GPU通用计算

第三章 基于垂直FP树的分布式闭频繁项集挖掘算法

3．1 事务数据库的划分与垂直FP树的构造

3．2 基于VFP树的分布式闭频繁项集挖掘

3．3 实验结果与分析

3．4 本章结论

第四章 基于投影前缀树的闭频繁项集增量挖掘算法

4．1 投影前缀树结构及其构造

4．2 闭频繁项集挖掘

4．3 实验分析

4．4 总结

第五章 基于GPU和分层垂直型数据格式的闭频繁项集挖掘算法

5．1．多层垂直数据格式

5．2 GPU闭频繁项集挖掘算法

5．3．实验与分析

5．4 本章总结

第六章 全文总结

6．1 论文研究工作总结

6．2 进一步的研究工作

参考文献

致谢

攻读学位期间发表的学术论文

攻读学位期间参加的工作

声明