一种优化初始点与自适应半径的密度聚类算法  

A Density Clustering Algorithm with Optimized Initial Points and Adaptive Radius

作　　者：王治和 曹旭琰 杜辉 WANG Zhihe;CAO Xuyan;DU Hui(School of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China)

机构地区：[1]西北师范大学计算机科学与工程学院,兰州730070

出　　处：《计算机工程》2022年第1期51-59,共9页Computer Engineering

基　　金：国家自然科学基金(61962054)。

摘　　要：传统DBSCAN算法不能正确聚类密度不均匀的数据集,聚类结果受邻域阈值和密度阈值参数的影响较大。提出一种新的优化初始点和自适应半径的密度聚类算法。利用反向最近邻和相似度矩阵发现当前全局密度最大的数据样本,分析该样本周围密度的分布情况,采用自适应的方法计算当前簇的邻域阈值,并利用DBSCAN算法进行聚类。在人工数据集和UCI数据集上进行测试的结果表明,与经典的DBSCAN、OPTICS、RNN-DBSCAN算法相比,优化初始点和自适应半径的密度聚类算法在ARI、NMI、Homogeneity、Completeness和V-measure 5个评价指标上整体取得最优值,其中在Compound、Jain等数据集上达到1.0,具有较高的聚类效率和准确度。The DBSCAN algorithm cannot accurately cluster the datasets with uneven densities,and the clustering results are greatly affected by the parameters of the neighborhood threshold and density threshold.This paper proposes a new density clustering algorithm for optimizing initial points and adaptive radius.The algorithm uses the Reverse Nearest Neighbor(RNN)and similarity matrix to find the sample point with the largest global density.Through the analysis of the density distribution around the sample,the neighborhood threshold of the current cluster is calculated using an adaptive method and then clustered using the DBSCAN algorithm.The experimental results on artificial datasets and UCI datasets show that compared with the DBSCAN,OPTICS and RNN-DBSCAN algorithms,the proposed algorithm displays the highest score in all five evaluation indexes,including ARI,NMI,Homogeneity,Completeness and V-measure,reaching 1.0 on the Compound dataset and Jain dataset.It can provide high efficiency and accuracy in clustering.

关 键 词：密度聚类 初始点优化 反向最近邻 自适应半径 相似度矩阵 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]