基于不相似性度量优化的密度峰值聚类算法
作者:
作者单位:

作者简介:

丁世飞(1963-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为人工智能与模式识别,机器学习与数据挖掘.
徐晓(1992-),女,博士生,主要研究领域为机器学习,聚类分析.
王艳茹(1991-),女,博士生,CCF学生会员,主要研究领域为机器学习,聚类分析.

通讯作者:

丁世飞,E-mail:dingsf@cumt.edu.cn

中图分类号:

基金项目:

国家自然科学基金(61672522,61379101);国家重点基础研究发展计划(973)(2013CB329502)


Optimized Density Peaks Clustering Algorithm Based on Dissimilarity Measure
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61672522, 61379101); National Program on Key Basic Research Project of China (973) (2013CB329502)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    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 dc only considers the global distribution of datasets, ignoring the local information of the data, so the change of dc will affect the results of clustering, especially on small scale datasets. Aiming at these shortcomings, this study proposes an optimized density peaks clustering algorithm based on dissimilarity measure (DDPC). DDPC introduces a mass-based dissimilarity measure to calculate the similarity matrix, and calculates the k-nearest neighbor information of the sample based on the new similarity matrix. Then local-density is redefined by the k-nearest neighbor information. Experimental results show that the optimized density peaks clustering algorithm based on dissimilarity measure is superior to the optimized FKNN-DPC and DPC-KNN clustering algorithms, and can be satisfied on datasets with uneven density and higher dimensions. As a result, the local-density measurement method is unified at the same time, which avoids the influence of dc on the clustering results in the traditional DPC algorithm.

    参考文献
    相似文献
    引证文献
引用本文

丁世飞,徐晓,王艳茹.基于不相似性度量优化的密度峰值聚类算法.软件学报,2020,31(11):3321-3333

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2018-04-19
  • 最后修改日期:2018-07-25
  • 录用日期:
  • 在线发布日期: 2020-11-07
  • 出版日期: 2020-11-06
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号