Page 5 - 《软件学报》2020年第11期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2020,31(11):3321−3333 [doi: 10.13328/j.cnki.jos.005813] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
基于不相似性度量优化的密度峰值聚类算法

1
1,2
丁世飞 , 徐 晓 , 王艳茹 1
1
(中国矿业大学 计算机科学与技术学院,江苏 徐州 221116)
2
(中国科学院 计算技术研究所 智能信息处理重点实验室,北京 100190)
通讯作者: 丁世飞, E-mail: dingsf@cumt.edu.cn

摘 要: 密度峰值聚类(clustering by fast search and find of density peaks,简称 DPC)是一种基于局部密度和相对距
离属性快速寻找聚类中心的有效算法.DPC通过决策图寻找密度峰值作为聚类中心,不需要提前指定类簇数,并可以
得到任意形状的簇聚类.但局部密度和相对距离的计算都只是简单依赖基于距离度量的相似度矩阵,所以在复杂数
据上 DPC 聚类结果不尽如人意,特别是当数据分布不均匀、数据维度较高时.另外,DPC 算法中局部密度的计算没
有统一的度量,根据不同的数据集需要选择不同的度量方式.第三,截断距离 d c 的度量只考虑数据的全局分布,忽略
了数据的局部信息,所以 d c 的改变会影响聚类的结果,尤其是在小样本数据集上.针对这些弊端,提出一种基于不相
似性度量优化的密度峰值聚类算法(optimized density peaks clustering algorithm based on dissimilarity measure,简称
DDPC),引入基于块的不相似性度量方法计算相似度矩阵,并基于新的相似度矩阵计算样本的 K 近邻信息,然后基于
样本的 K 近邻信息重新定义局部密度的度量方法.经典数据集的实验结果表明,基于不相似性度量优化的密度峰值
聚类算法优于 DPC 的优化算法 FKNN-DPC 和 DPC-KNN,可以在密度不均匀以及维度较高的数据集上得到满意的
结果;同时统一了局部密度的度量方式,避免了传统 DPC 算法中截断距离 d c 对聚类结果的影响.
关键词: 密度峰值聚类;局部密度;决策图;不相似性度量;密度不均匀
中图法分类号: TP301

中文引用格式: 丁世飞,徐晓,王艳茹.基于不相似性度量优化的密度峰值聚类算法.软件学报,2020,31(11):3321−3333. http://
www.jos.org.cn/1000-9825/5813.htm
英文引用格式: Ding SF, Xu X, Wang YR. Optimized density peaks clustering algorithm based on dissimilarity measure. Ruan
Jian Xue Bao/Journal of Software, 2020,31(11):3321−3333 (in Chinese). http://www.jos.org.cn/1000-9825/5813.htm

Optimized Density Peaks Clustering Algorithm Based on Dissimilarity Measure

1,2
1
DING Shi-Fei , XU Xiao , WANG Yan-Ru 1
1 (School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116, China)
2 (Key Laboratory of Intelligent Information Processing, Institute of Computing Technology, Chinese Academy of Sciences, Beijing
100190, China)
Abstract: Clustering by fast search and find of density peaks (DPC) is an efficient algorithm for finding cluster centers quickly based on
local-density and relative-distance. DPC uses the decision graph to find the density peaks as cluster centers. It does not need to specify the
number of clusters in advance and clusters with arbitrary shapes can be obtained. However, the calculation of local-density and
relative-distance depends on the similarity matrix which is based on distance metrics simply, thus, DPC is not satisfactory on complex
datasets, especially when the datasets with uneven density and higher dimensions. In addition, the measurement of the local-density is not
unified and different methods correspond to different datasets. Third, the measurement of d c only considers the global distribution of

∗ 基金项目: 国家自然科学基金(61672522, 61379101); 国家重点基础研究发展计划(973)(2013CB329502)
Foundation item: National Natural Science Foundation of China (61672522, 61379101); National Program on Key Basic Research
Project of China (973) (2013CB329502)
收稿时间: 2018-04-19; 修改时间: 2018-07-25; 采用时间: 2019-01-15