一种基于密度的分布式聚类方法

来源：软件学报杂志2017年第11期北京时间：

作者：王岩,彭涛,韩佳育,刘露

单位：王岩，吉林大学 计算机科学与技术学院, 吉林 长春 13001211,彭涛，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001202,韩佳育，吉林大学 计算机科学与技术学院, 吉林 长春 13001203,刘露，吉林大学 计算机科学与技术学院, 吉林 长春 13001204

摘要：聚类是数据挖掘领域中的一种重要的数据分析方法.它根据数据间的相似度，将无标注数据划分为若干聚簇.CSDP是一种基于密度的聚类算法，当数据量较大或数据维数较高时，聚类的效率相对较低.为了提高聚类算法的效率，提出了一种基于密度的分布式聚类方法MRCSDP，利用MapReduce框架对实验数据进行聚类.该方法定义了独立计算单元和独立计算块的概念.首先，将数据拆分为若干数据块，构建独立计算单元和独立计算块，在集群中分配独立计算块的任务；然后进行分布式计算，得到数据块的局部密度，将局部密度合并得到全局密度，根据全局密度计算中心值，由全局密度和中心值得到每个数据块中候选聚簇中心；最后，从候选聚簇中心选举出最终的聚簇中心.MRCSDP在充分降低时间复杂度的基础上得到较好的聚类效果.实验结果表明，分布式环境下的聚类方法MRCSDP相对于CSDP更能快速、有效地处理大规模数据，并使各节点负载均衡.

关键词：聚类;分布式计算;MapReduce;独立计算单元;独立计算块

基金资助：国家自然科学基金（60903098）；吉林省发改委产业技术研究与开发专项（2015Y055）；吉林省科技厅重点科技攻关项目（20150204040GX）；吉林大学研究生创新基金（2016183）