计算机应用 ›› 2018, Vol. 38 ›› Issue (6): 1601-1607.DOI: 10.11772/j.issn.1001-9081.2017122898

• 数据科学与技术 • 上一篇    下一篇

基于共享近邻相似度的密度峰聚类算法

鲍舒婷1,2, 孙丽萍1,2, 郑孝遥1,2, 郭良敏1,2   

  1. 1. 安徽师范大学 计算机与信息学院, 安徽 芜湖 241002;
    2. 网络与信息安全安徽省重点实验室(安徽师范大学), 安徽 芜湖 241002
  • 收稿日期:2017-12-12 修回日期:2018-02-02 出版日期:2018-06-10 发布日期:2018-06-13
  • 通讯作者: 孙丽萍
  • 作者简介:鲍舒婷(1994-),女,安徽合肥人,硕士研究生,主要研究方向:数据挖掘、信息安全;孙丽萍(1980-),女,安徽芜湖人,教授,博士,CCF会员,主要研究方向:数据挖掘、信息安全;郑孝遥(1981-),男,安徽芜湖人,副教授,博士研究生,CCF会员,主要研究方向:信息安全、个性化推荐;郭良敏(1980-),女,安徽肥东人,副教授,博士,CCF会员,主要研究方向:云计算、信息安全。
  • 基金资助:
    国家自然科学基金资助项目(61602009,61772034); 安徽省自然科学基金资助项目(1608085MF145,1508085QF133)。

Density peaks clustering algorithm based on shared near neighbors similarity

BAO Shuting1,2, SUN Liping1,2, ZHENG Xiaoyao1,2, GUO Liangmin1,2   

  1. 1. School of Computer and Information, Anhui Normal University, Wuhu Anhui 241002, China;
    2. Anhui Provincial Key Laboratory of Network and Information Security(Anhui Normal University), Wuhu Anhui 241002, China
  • Received:2017-12-12 Revised:2018-02-02 Online:2018-06-10 Published:2018-06-13
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (61602009, 61772034), the Natural Science Foundation of Anhui Province (1608085MF145, 1508085QF133).

摘要: 密度峰聚类是一种基于密度的高效聚类方法,但存在对全局参数dc敏感和需要人工干预决策图进行聚类中心选择的缺陷。针对上述问题,提出了一种基于共享近邻相似度的密度峰聚类算法。首先,该算法结合欧氏距离和共享近邻相似度进行样本局部密度的定义,避免了原始密度峰聚类算法中参数dc的设置;其次,优化聚类中心的选择过程,能够自适应地进行聚类中心的选择;最后,将样本分配至距其最近并拥有较高密度的样本所在的簇中。实验结果表明,在UCI数据集和模拟数据集上,该算法与原始的密度峰聚类算法相比,准确率、标准化互信息(NMI)和F-Measure指标分别平均提高约22.3%、35.7%和16.6%。该算法能有效地提高聚类的准确性和聚类结果的质量。

关键词: 密度峰聚类, k近邻, 共享近邻, 局部密度, 相似性度量

Abstract: Density peaks clustering is an efficient density-based clustering algorithm. However, it is sensitive to the global parameter dc. Furthermore, artificial intervention is needed for decision graph to select clustering centers. To solve these problems, a new density peaks clustering algorithm based on shared near neighbors similarity was proposed. Firstly, the Euclidean distance and shared near neighbors similarity were combined to define the local density of a sample, which avoided the setting of parameter dc of the original density peaks clustering algorithm. Secondly, the selection process of clustering centers was optimized to select initial clustering centers adaptively. Finally, each sample was assigned to the cluster as its nearest neighbor with higher density samples. The experimental results show that, compared with the original density peaks clustering algorithm on the UCI datasets and the artificial datasets, the average values of accuracy, Normalized Mutual Information (NMI) and F-Measure of the proposed algorithm are respectively increased by about 22.3%, 35.7% and 16.6%. The proposed algorithm can effectively improve the accuracy of clustering and the quality of clustering results.

Key words: density peaks clustering, k nearest neighbors, shared near neighbors, local density, similarity measure

中图分类号: