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

Density-Based Distributed Clustering Method

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

Clustering is an important method for data analysis in the field of data mining.The function of clustering is to divide unlabeled data divided into several groups according to the data similarity.CSDP is a density-based clustering method.When data size is Iarge or data dimensionality is high,the efficiency of clustering is relatively low.In order to improve the efficiency of clustering algorithm,this paper proposes a density-based distributed clustering method,called MRCSDP,which uses MapReduce to cluster text data.This method introduces the definition of independent calculation unit and independent calculation block.First,data are split into several data blocks which are used to construct independent calculation unit and independent calculation block.The task for each independent calculation block is assigned.Then the distributed calculation is conducted to obtain the local density of the data blocks.The local densities are combined to obtain the global density.The center value is calculated according to the global density.Based on the global density and the center value,the candidate cluster centers of each data block can be obtained.Finally,the global cluster centers are obtained by calculating the density of all candidate cluster centers.MRCSDP can achieve better clustering performance by reducing time complexity.Experimental results show that compared to CSDP,MRCSDP can process large scale data more effectively with loadbalancing on each computing nodes.