基于MapReduce的分布式快速聚类算法研究

摘要

随着信息技术的高速发展，数据规模呈现指数级增长态势，传统聚类算法面临巨大的挑战。一是海量数据内的噪声杂、冗余度高、价值密度低，聚类算法的准确率不高；二是串行聚类算法面对海量数据时，搜索邻域代价巨大，执行效率无法适应实际需求。针对上述问题，本文充分分析数据特点，基于MapReduce大数据处理框架，设计了分布式快速聚类算法，实现了高效、高精度的并行数据聚类。
　　针对海量数据中冗余度高，无价值数据繁多的问题，本文提出一种基于 MapReduce的分布式数据约减算法。通过一种新的抽样算法计算数据点的矩形域和抽样域，并在抽样域中确定样本数据，然后对样本数据进行扩展抽样来达到约减原始数据集的目的，最后提出一种代表性验证策略来检验样本集，从而解决海量数据聚类产生巨大I/O开销和网络开销的问题。
　　针对搜索最近邻代价消耗大，聚类执行效率低的问题，本文利用Map任务对样本数据集进行相等大小的数据划分，Reduce任务对数据子集进行局部密度聚类，因此针对单节点提出基于扩展区域查询的密度聚类算法。首先通过基于固定网格的扩展区域查询方法，确定数据点最近邻和反最近邻的邻域关系，建立每个数据点的影响空间域，然后提出异常点判定函数，使算法能够准确地识别噪声点和边界点。
　　Reduce聚类任务结束后输出局部聚类结果，为得到面向整个数据集的全局聚类结果，本文提出一种基于簇间距离的局部类簇合并算法，通过簇间距离的计算确定局部类簇间的分布关系，得到可以两两合并的局部类簇对，然后根据连通子图发现方法合并局部类簇对，最后输出全局聚类结果。
　　实验结果表明，本文提出的算法有效地将海量数据进行约减，保证了样本数据与原始数据分布的一致性，在信息量无损失的前提下降低了数据冗余，并且该算法能够快速处理任意形状的类簇，大幅度提高了算法的执行效率和聚类质量。

目录

第1章 绪 论

1.1 课题研究背景及意义

1.2 国内外研究现状

1.3 主要研究内容

1.4 论文的组织结构

第2章 相关理论及技术

2.1 MapReduce

2.2 Hadoop

2.3 聚类分析

2.4 本章小结

第3章 基于MapReduce的分布式数据约减算法设计

3.1 概念定义

3.2 算法思想

3.3 实验结果及分析

3.4 本章小结

第4章 基于扩展区域查询的密度聚类算法设计

4.1 概念定义

4.2 算法思想

4.3 实验结果及分析

4.4 本章小结

第5章 基于簇间距离的局部类簇合并算法设计

5.1 算法思想

5.2 算法流程设计

5.3 实验结果及分析

5.4 本章小结

结论

参考文献

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

声明

致谢