电子学报 ›› 2018, Vol. 46 ›› Issue (3): 730-738.DOI: 10.3969/j.issn.0372-2112.2018.03.031

• 学术论文 • 上一篇    下一篇

基于z值的分布式密度峰值聚类算法

卢晶1, 段勇1, 刘海波2   

  1. 1. 沈阳工业大学信息科学与工程学院, 辽宁沈阳 110870;
    2. 河北大学计算机科学与技术学院, 河北保定 071002
  • 收稿日期:2016-10-31 修回日期:2017-05-31 出版日期:2018-03-25
    • 通讯作者:
    • 段勇
    • 作者简介:
    • 卢晶,女,1992年7月出生,辽宁盘锦人,现为沈阳工业大学信息科学与工程学院硕士研究生.主要研究方向为数据挖掘、大数据分布式计算.E-mail:fionalujing@163.com;刘海博,男,1979年2月出生,河北廊坊人,硕士.现为河北大学计算机科学与技术学院副教授.研究领域为大规模数据挖掘、个性化推荐与大规模社会网络分析.E-mail:liuhaibo@hbu.edu.cn
    • 基金资助:
    • 辽宁省自然科学基金 (No.2015020010); 辽宁省高等学校优秀科技人才支持计划 (No.LR2015045); 河北省自然科学基金青年基金 (No.F2015201140)

Distributed Density Peaks Clustering Based on z-Value

LU Jing1, DUAN Yong1, LIU Hai-bo2   

  1. 1. School of Information Science and Engineering, Shenyang University of Technology, Shenyang, Liaoning 110870, China;
    2. School of Computer Science and Technology, Hebei University, Baoding, Hebei 071002, China
  • Received:2016-10-31 Revised:2017-05-31 Online:2018-03-25 Published:2018-03-25
    • Corresponding author:
    • DUAN Yong
    • Supported by:
    • National Natural Science Foundation of Liaoning Province,  China (No.2015020010); Excellent Science andTechnology Talents Support Project of Colleges and Universities in Liaoning Province (No.LR2015045); Natural Science Foundation of Hebei Province,  China (No.F2015201140)

摘要: 密度峰值聚类算法由于在发现任意形状簇且不需指定聚类个数等方面具有一定的优势而被广泛关注.但是该算法需要计算数据集中所有点的密度和点对之间的距离,因此不适合处理大规模高维数据集.为此,本文提出了一种基于z值的分布式密度峰值聚类算法,DP-z.本方法利用空间z填充曲线将高维数据集映射到一维空间上,根据数据点的z值信息对数据集分组.为了能够得到正确的结果,需要对分组间数据进行交互,然后并行计算每个点密度和斥群值.DP-z算法在分组间数据交互时采用过滤策略,减少大量无效距离计算和数据传输开销,有效提高算法的执行效率.最后,本文在云计算平台上对DP-z算法进行了验证,实验表明在保证DP-z算法与原始密度峰值聚类算法聚类结果相同的情况下有效的提高了算法执行效率.

关键词: 聚类, 分布式计算, 云计算, z填充曲线, 密度峰值

Abstract: Density peak clustering is an effective and novel clustering algorithm, it is concerned as its superiority of finding arbitrary shape of clusters and number of clusters. However, this algorithm is required to measure the density and distance between any pair of objects. This limits the practicability of this algorithm when clustering high-volume and high-dimensional data set. In order to improve efficiency and scalability, we propose a distributed density peak clustering algorithm based on z-value, and DP-z. It utilizes z-values to map points in multidimensional space into one dimension, and then splits the data set into several partitions according to the z-values of points. In order to get the correct result, we make use of the character of points' z-values to filter the data object while exchanging data among groups, which reduces a huge amount of useless distance measurement cost and data shuffle cost. Then we compute the density and distance value in parallel. Finally, we test the DP-z algorithm based on the cloud computing platform, the experiments show that DP-z can achieve higher performance at speed without reducing the accuracy. 

Key words: clustering, distributed computing, cloud computing, z-order curve, density peaks

中图分类号: