论文部分内容阅读
近年来,数据密集型计算越来越得到相关学者的关注。数据密集型计算环境下的数据具有海量、高速变化、分布、异构、半结构化或非结构化的特点,传统的数据挖掘算法已经不能满足其处理要求。如何从具有这些数据特点的数据中挖掘出有效的信息,成为当前数据挖掘领域所面临的一大挑战。聚类分析是当前一种常用的数据挖掘工具,是将无规则的数据点依据某一方面的相似性分成若干类,使得每个类中的所有数据点在该方面相似性最大,不同类中的数据点在该方面相似性最小的过程。常见的聚类分析算法有分割方法、层次方法、基于密度的方法、基于网格的方法和基于约束的方法等。本文分析了数据密集型计算环境下数据的特点,介绍了聚类分析的相关理论知识,重点讨论了基于划分的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、数据点个数及密度的键值对<key, value>,并由Combine阶段进行相关合并,发送到主节点执行Reduce阶段全局的k-means算法。最后在Hadoop实验环境下利用数据集DOCWORD.NYTIMES进行实验,实验结果表明:IDBDC算法在数据密集型计算环境下表现出了较高的执行效率和准确率,能够较好的适用于数据密集型计算环境下的数据分析。