文档介绍：分 类 号： 单位代码：10183
研究生学号：2015534064 密 级：公 开
吉 林 大 学
硕士学位论文
（专业学位）
一种基于密度的分布式聚类算法
A Density-based Distributed Clustering Method
作 者 姓 名：王岩
类 别：工程硕士
领域（方向）：计算机技术
指 导 教 师：彭涛 教授
培 养 单 位：计算机科学与技术学院
2018 年 4 月
摘 要
一种基于密度的分布式聚类算法
随着网络信息量的不断增长，人们对获取特定领域信息的需求越来越高。聚类作
为一种数据分析的重要方法，旨在根据对象间的相近程度将无标注的数据划分为若干
聚簇。与分类不同，聚类是一种无监督学****不需要任何有标注的训练数据。研究者
已经提出了很多聚类算法，比如，基于距离的聚类（K-Means）、基于密度的聚类
（DENCLUE）和基于网格的聚类（CLIQUE）等等。在现实生活中，聚类在很多领
域也有着广泛的应用，例如，自然语言处理、多文档自动文摘、搜索引擎等。
聚类是数据挖掘领域一种重要的数据分析方法，它根据数据间的相似度将无标
注数据划分为若干聚簇。CSDP 是一种基于密度的聚类算法，当数据量较大或数据维
数较高时，聚类的效率相对较低。为了提高聚类算法的效率，本文提出了一种基于密
度的分布式聚类方法 MRCSDP。
为了将本文提出的聚类算法描述清楚，本文首先给出了聚类的概念与意义，给
出 CSDP 的算法详细内容，并且分析了 CSDP 聚类方法的优缺点。在之后给出了
MapReduce 的计算框架的结构，该分布式计算框架主要包含两个阶段一个是 Map 阶
段，一个是 Reduce 阶段，本文同时给出了一些关于分布式计算生态系统 Hadoop 的
内容，主要涉及 HDFS 和 YARN 两种组件。
在描述算法的章节中，本文定义了独立计算单元和独立计算块的概念，然后给
出了 MRCSDP 的具体算法细节。为构建独立计算单元和独立计算块，在集群中进行
独立计算块的任务的均匀分配，首先需要将数据拆分为若干均等的数据块。然后进行
分布式计算得到数据块的局部密度，将局部密度合并得到全局密度，根据全局密度计
算中心值，由全局密度和中心值计算得到每个数据块中候选聚簇中心。最后从候选聚
簇中心中选举出全局的聚簇中心。MRCSDP 在充分降低时间复杂度的基础上得到较
好的聚类效果。为验证算法的正确性和相对于其他分布式算法该算法的优缺点，本文
I
进行了五组实验。第一组实验主要比对不同参数对聚类准确度的影响，第二组，第三
组实验进行 MRCSDP 与原有算法对比，主要对比准确率和运行效率，第四组和第五
组实验进行 MRCSDP 与当前已有的分布式聚类算法的比较。实验结果表明，分布式
环境下的聚类方法 MRCSDP 相对于 CSDP 更能快速有效地处理大规模数据，并使各
计算节点负载均衡，而且在某些领域相对于其他分布式聚类算法该算法有一定的优
势。
关键词:
聚类，分布式计算，MapReduce，独立计算单元，独立计算块