数据密集型计算环境下聚类算法的研究

摘要

近年来，数据密集型计算越来越得到相关学者的关注。数据密集型计算环境下的数据具有海量、高速变化、分布、异构、半结构化或非结构化的特点，传统的数据挖掘算法已经不能满足其处理要求。如何从具有这些数据特点的数据中挖掘出有效的信息，成为当前数据挖掘领域所面临的一大挑战。
　　聚类分析是当前一种常用的数据挖掘工具，是将无规则的数据点依据某一方面的相似性分成若干类，使得每个类中的所有数据点在该方面相似性最大，不同类中的数据点在该方面相似性最小的过程。常见的聚类分析算法有分割方法、层次方法、基于密度的方法、基于网格的方法和基于约束的方法等。本文分析了数据密集型计算环境下数据的特点，介绍了聚类分析的相关理论知识，重点讨论了基于划分的k-means算法和基于密度的DBSCAN算法；介绍了开源项目Hadoop以及相关子项目，特别是对Hadoop分布式文件系统（Hadoop Distributed File System）和MapReduce编程模型进行了深入的分析和研究。
　　本文基于MapReduce编程模型，讨论了k-means算法及DBSCAN算法在数据密集型计算环境下的实现。针对k-means算法对局部数据集的鲁棒性较差、准确率低，而在主节点对全局数据集具有较好的伸缩性及准确率；局部分节点容易产生较多的噪声点和异常点，而DBSCAN算法可有效的识别噪声点及异常点等特点，取长补短，优化两种聚类算法，提出一种改进的基于MapReduce的聚类算法IDBDC；局部聚类采用DBSCAN算法的优化，全局聚类采用k-means算法的优化，使其适用于数据密集型计算环境下的数据分析挖掘。在MapReduce模型上的实现部分，划分为三个阶段，即Map阶段、Combine阶段和Reduce阶段。分节点上的Map阶段执行DBSCAN算法，生成含有簇及噪声点ID、数据点个数及密度的键值对，并由Combine阶段进行相关合并，发送到主节点执行Reduce阶段全局的k-means算法。最后在Hadoop实验环境下利用数据集DOCWORD.NYTIMES进行实验，实验结果表明：IDBDC算法在数据密集型计算环境下表现出了较高的执行效率和准确率，能够较好的适用于数据密集型计算环境下的数据分析。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪 论

1.1 课题的研究背景

1.2 课题主要研究内容

1.3 论文组织结构

1.4 本章小结

第2章 数据密集型计算及相关领域理论研究

2.1 数据密集型计算

2.2 聚类分析算法

2.3 Hadoop项目及子项目

2.4 本章小结

第3章 k-means和DBSCAN在DIC环境下研究与实现

3.1 k-means算法及DBSCAN算法

3.2 k-means算法在MapReduce上的实现

3.3 DBSCAN算法在MapReduce上的实现

3.4 本章小结

第4章 改进的聚类算法及其在DIC环境下的实现

4.1 DBDC简介

4.2 算法IDBDC的提出

4.3 算法IDBDC在MapReduce上的实现

4.4 算法复杂度分析

4.5 本章小结

第5章 实验与结果分析

5.1 实验环境及数据

5.2 Hadoop环境配置

5.3 实验结果分析

5.4 本章小结

第6章 总结与展望

6.1 总结

6.2 展望

参考文献

致谢

攻读硕士期间公开发表论文及科研情况