文档介绍：基于MapReduce的自适应密度聚类算法研究 AMapReduce based adaptive density clustering algorithm 专业:计算机科学与技术作者姓名:杨亚军指导教师:张坤龙副教授天津大学计算机科学与技术学院二零一三年十二月独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果,除了文中特别加以标注和致谢之处外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得天津大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名: 签字日期: 年月日我是爱天大的!! 学位论文版权使用授权书本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。特授权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检索,并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。(保密的学位论文在解密后适用本授权说明) 学位论文作者签名: 导师签名: 签字日期: 年月日签字日期: 年月日摘要随着数据的爆炸式增长,单机聚类算法无论是存储能力还是处理能力都无法满足海量数据的聚类,必须寻求并行化的解决方案。Google提出的分布式编程模型MapReduce给并行聚类带来了新的希望,因此,论文提出了一种基于 MapReduce的自适应密度聚类算法。论文首先针对DBSCAN无法处理变化密度的聚类和参数敏感的问题进行了改进,提出了一种自适应的密度聚类算法ADC。算法将一个点到其第k个最邻近邻居的距离定义为密度,使用密度变化率来识别簇边界,当且仅当一个点的最邻近邻居中至少有k个点的密度与该点的密度变化率小于用户给定的阈值,该点才为核点,并且阈值在运行时自动动态调整。其次,论文在ADC的基础上,提出了一种基于MapReduce的聚类算法MR-ADC,算法包括五个步骤:1)对数据进行归一化;2)将归一化后的数据均匀的划分为若干个块;3)在划分后的每一个块上分别应用改进的ADC算法进行聚类,并且将靠近划分边界的点写入 HDFS;4)对划分边界的点进行分析,将局部簇合并为全局簇;5)根据局部簇与全局簇的映射关系,对局部聚类结果进行全局簇标号。论文在一个包含4个节点的Hadoop集群上对算法进行了实验分析,包括聚类的效果和算法的时间开销。实验结果表明,ADC算法可以处理任意大小、形状和密度的聚类,并且由于自适应,参数的设置更加容易,MR-ADC算法可以取得和单线程一样的效果,并且运行时间远远小于单线程算法,适合处理海量数据聚类。关键词:MapReduce自适应变化密度k最邻近邻居基于密度的聚类 ABSTRACT With the explosive growth of data, singlethreadclustering algorithm can not meet the massive data clustering in both processing power and storage capacity, so seekingparallel solutionis necessary. Google’s MapReduce programming model for distributed computing has brought new hope to parallel clustering. Therefore, our paper presents anadaptive density clustering algorithm based on MapReduce. Firstly, we propose an adaptive density based clustering algorithm which is called ADC, in order to e the ing that DBSCAN can’t find clusters of varied densities and is sensitive to parameters. Our algorithm defines one point’s density as the distance from itselfto its k-th nearest neighbor. Ituses the change rate of density to find the boundaries between clusters with different densiti