巩树凤　　　张岩峰

(东北大学计算机科学与工程学院　沈阳　110819)(shidashufeng@163.com)



EDDPC：一种高效的分布式密度中心聚类算法

巩树凤张岩峰

(东北大学计算机科学与工程学院沈阳110819)(shidashufeng@163.com)

摘要聚类分析是数据挖掘中经常用到的一种分析数据之间关系的方法.它把数据对象集合划分成多个不同的组或簇，每个簇内的数据对象之间的相似性要高于与其他簇内的对象的相似性.密度中心聚类算法是一个最近发表在《Science》上的新型聚类算法，它通过评估每个数据对象的2个属性值(密度值ρ和斥群值δ)来进行聚类.相对于其他传统聚类算法，它的优越性体现在交互性、无迭代性、无数据分布依赖性等方面.但是密度中心聚类算法在计算每个数据对象的密度值和斥群值时，需要O(N2)复杂度的距离计算，当处理海量高维数据时，该算法的效率会受到很大的影响.为了提高该算法的效率和扩展性，提出一种高效的分布式密度中心聚类算法EDDPC (efficient distributed density peaks clustering)，它利用Voronoi分割与合理的数据复制及过滤，避免了大量无用的距离计算开销和数据传输开销.实验结果显示:与简单的MapReduce分布式实现比较，EDDPC可以达到40倍左右的性能提升.

关键词密度中心；数据聚类；Voronoi分割；MapReduce；大数据

聚类在很多应用中是一种基础的数据分析方法，例如社会网络分析、智能商务、图像模式识别、Web搜索和生物学等.当前存在很多聚类算法[1]，这其中包括基于划分的方法(如k-medoids[2]，k-means[3])、基于层次的方法(如AGNES[4])、基于密度的方法(如DBASCAN[5])、基于网格的方法(如STING[6])，还有面向……