张清华(1974-), 男, 博士, 教授, 博士生导师, CCF专业会员, 主要研究领域为粗糙集, 模糊集, 粒计算, 不确定性信息处理
周靖鹏(1999-), 男, 硕士生, 主要研究领域为粗糙集, 机器学习, 数据挖掘
代永杨(1996-), 男, 硕士生, 主要研究领域为粗糙集, 机器学习, 不确定性信息处理
王国胤(1970-), 男, 博士, 教授, 博士生导师, CCF会士, 主要研究领域为粗糙集, 粒计算, 数据挖掘
密度峰值聚类(density peaks clustering, DPC)是一种基于密度的聚类算法, 该算法可以直观地确定类簇数量, 识别任意形状的类簇, 并且自动检测、排除异常点. 然而, DPC仍存在些许不足: 一方面, DPC算法仅考虑全局分布, 在类簇密度差距较大的数据集聚类效果较差; 另一方面, DPC中点的分配策略容易导致“多米诺效应”. 为此, 基于代表点(representative points)与K近邻(K-nearest neighbors, KNN)提出了RKNN-DPC算法. 首先, 构造了K近邻密度, 再引入代表点刻画样本的全局分布, 提出了新的局部密度; 然后, 利用样本的K近邻信息, 提出一种加权的K近邻分配策略以缓解“多米诺效应”; 最后, 在人工数据集和真实数据集上与5种聚类算法进行了对比实验, 实验结果表明, 所提出的RKNN-DPC可以更准确地识别类簇中心并且获得更好的聚类结果.
Density peaks clustering (DPC) is a density-based clustering algorithm that can intuitively determine the number of clusters, identify clusters of any shape, and automatically detect and exclude abnormal points. However, DPC still has some shortcomings: The DPC algorithm only considers the global distribution, and the clustering performance is poor for datasets with large cluster density differences. In addition, the point allocation strategy of DPC is likely to cause a Domino effect. Hence, this study proposes a DPC algorithm based on representative points and K-nearest neighbors (KNN), namely, RKNN-DPC. First, the KNN density is constructed, and the representative points are introduced to describe the global distribution of samples and propose a new local density. Then, the KNN information of samples is used to propose a weighted KNN allocation strategy to relieve the Domino effect. Finally, a comparative experiment is conducted with five clustering algorithms on artificial datasets and real datasets. The experimental results show that the RKNN-DPC algorithm can more accurately identify cluster centers and obtain better clustering results.
聚类分析是一种重要的无监督学习方法[
Rodriguez等人[
然而, DPC存在一些不足: 1) 因为DPC的局部密度定义仅考虑了样本的局部分布, 所以当数据集的类簇密度差距较大时, 不能准确地表达数据样本点的密度, 从而导致选择错误的类簇中心. 2) 密度峰值聚类算法的分配策略容易导致“多米诺效应”, 即一个点分配错误, 产生连锁反应, 导致更多的点分配错误.
近年来, DPC算法的研究主要集中于改进和扩展DPC算法. 关于改进DPC算法, 有学者将K近邻思想引入DPC, 为改善DPC算法在多维数据集的聚类效果, Du等人[
针对DPC及其改进算法在确定类簇中心以及非中心点分配策略的不足, 本文提出了基于代表点和K近邻的密度峰值算法(density peaks clustering algorithm based on representative points and K-nearest neighbors, RKNN-DPC). RKNN-DPC算法的创新点包括: 1) 基于样本的K近邻信息提出了K近邻密度定义, K近邻密度更能反映点近邻分布; 提出了代表点和代表值的定义来表示一个样本在类簇的重要程度, 不仅使样本的局部密度更层次化, 还能更准确地找到类簇中心; 为了解决类簇间密度差距的问题, 结合代表值和K近邻密度构造了RKNN-DPC算法的局部密度. 2) 依据样本K近邻点的欧氏距离及所属类簇数量构造类簇权重, 确认待分配点的所属类簇; 在此基础上引入预备队列提出了改进的迭代分配策略, 针对不同的待分配点选择分配策略, 使得RKNN-DPC算法有效缓解了“多米诺效应”.
本文第1节介绍DPC聚类算法并分析其不足, 第2节详细介绍本文提出的RKNN-DPC算法, 第3节通过实验将本文RKNN-DPC与其他经典聚类算法进行了对比, 以验证RKNN-DPC的有效性, 第4节总结本文, 并指出了未来的研究方向.
DPC算法基于两个假设: 类簇中心点的密度大于周围点的密度; 类簇中心点与更高密度点之间的距离相对较大. DPC算法给每一个样本赋予局部密度和相对距离两个重要属性.
DPC算法提供了2种局部密度
定义
其中,
使用截断距离计算局部密度是找以
定义
其中,
相对距离
定义
其中,
DPC的聚类过程为: 根据定义1和定义2计算样本的局部密度
DPC算法思想简单, 可以识别任意形状的类簇, 能直观找到簇数量. 但依然存在如下不足.
1)对于类簇之间密度差距较大的数据集, DPC算法的局部密度计算方式无法找到正确的类簇中心. 本文以Jain数据集[
DPC密度差距问题
2)若前置点的类簇中心找错, DPC算法的分配策略可能会导致“多米诺效应”. 本文以Spiral数据集[
DPC的“多米诺效应”
针对第1.2节中的分析, 本文提出了基于代表点与K近邻的RKNN-DPC算法. RKNN-DPC聚类过程分为类簇中心的选择和非中心点的分配, 整体流程如
RKNN-DPC流程图
传统DPC算法是基于欧氏距离来计算局部密度和相对距离, 仅考虑欧氏距离忽略了每个类簇的分布情况. 为了更准确地估计样本局部密度本文引入K近邻和代表点思想以确认密度峰值.
定义
其中,
K近邻密度是由点的K近邻信息计算, 而传统DPC考虑的是全局分布, 局部密度取决于截断距离
定义
为了体现一个点在类簇的重要性, 本文将代表点量化为代表值, 代表值的含义为点在数据集中作为其他点的代表点的次数, 代表值越大就表明该点为K近邻点集中越密集, 该值可以表明它在类簇的密集程度. 代表值定义如下.
定义
K近邻密度反映的是点的局部信息, 其在密度差距较大的数据集并不能正确表达点的密度, 所以使用代表值来获取每一个类簇的密度峰值, 如果单独使用代表值来代替局部密度可能会出现一个类簇有相同代表值的情况, 所以本文结合代表值和K近邻信息定义新的局部密度, 定义如下.
定义
其中,
改进的局部密度由两个部分组成, 点的K近邻密度取决于它与K近邻点集的距离, 在越密集的区域, 该点的K近邻密度越大, 相反越稀疏K近邻密度越小, 这可以表明它在一个类簇的密集程度; 代表值取决于K近邻密度, DPC算法假设类簇中心点的密度大于周围点的密度, 同样本文也基于这一假设, 那么一个类簇中心的K近邻密度就应该在其K近邻范围内最大, 所以类簇中心的代表值往往是等于K, 因为代表值是基于K近邻, 所以即使在类簇差距较大的数据集, 也能从密度稀疏的类簇找到代表值为K的点, 这也是RKNN-DPC能够解决密度差距的核心.
本文RKNN-DPC算法保留了DPC算法确定类簇中心的过程, 在改进的局部密度定义的基础上, RKNN-DPC算法确定类簇中心的详细步骤如算法1.
算法
输入: 数据集
输出: 类簇中心
1. 数据归一化, 计算样本的距离矩阵.
2. 根据公式(6)计算每个样本的K近邻密度
3. 根据公式(7)和公式(8)计算每个样本的代表点
4. 根据公式(9)和公式(3)计算每个样本的局部密度
5. 通过
为了说明RKNN-DPC选取类簇中心的有效性, 本节仍以Jain数据集为例进行分析, 其中红色五角星为RKNN-DPC找到的类簇中心, 如
RKNN-DPC密度差距问题
因为DPC算法的分配策略仅考虑前置点所属的类簇, 所以容易出现“多米诺效应”. 本文考虑多个点的类簇信息, 并基于样本的K近邻信息优化分配策略. 在分配点时, 首先找到点的K近邻分别属于的类簇, 再计算该点属于每一个类簇的权重, 并将其划分到权重最高的类簇. 类簇的权重定义如下.
定义
其中, 集合
在分配的过程中, 点
基于类簇权重, 本文引入预备队列设计优化的非中心点分配策略, 分配思想为: 将离类簇中心的K近邻点分配对应类簇; 然后根据预备队列的预备值
算法
输入: 数据集
输出: 聚类结果
1. 将每个中心点
2.
3.
4. 将
5.
6. 根据公式(10)计算
7.
8.
9.
10.
11.
12.
13.
14. 根据公式(10)计算
15.
16.
17.
18.
19.
20.
21. 根据公式(10)计算
22.
预备队列存放的是不具备分配条件的点, 通过预备值
在面对复杂的数据集下, 传统DPC采用的分配策略使非中心点的所属类簇完全取决于前置点, DPC考虑的前置点可能是错误的, 从而容易导致连续性错误. 本文使用的类簇权重可以缓解这种情况, 类簇权重考虑的是待分配点的K近邻点集, 点集往往包含着DPC分配过程中的前置点, 而DPC分配时若分配错误前置点时没有纠错的措施, 而RKNN-DPC使用类簇权重在分配过程时基于欧氏距离和K近邻点集所属类簇, 即便前置点出现分配错误, 也可以通过其余的K近邻点修正. 所以本文提出的非中心点的分配策略在类簇相接较多的数据集下, 相比于DPC算法具有更好的聚类效果和泛化能力.
设样本的数量为
为了验证RKNN-DPC算法的聚类效果, 实验使用人工数据集和真实数据集来测试其性能, 并以DPC、FKNN-DPC、RDDPC、DBSCAN、K-means这5种聚类方法作为对照组来对比实验结果.
人工数据集
数据集 | 文献 | 样本量 | 属性数量 | 类簇数量 |
Spiral | [ |
312 | 2 | 3 |
Jain | [ |
373 | 2 | 2 |
Zelnik3 | [ |
266 | 2 | 3 |
Four-lines | [ |
512 | 2 | 4 |
DIM512 | [ |
1 024 | 512 | 16 |
Aggregation | [ |
788 | 2 | 7 |
Flame | [ |
240 | 2 | 2 |
D31 | [ |
3 100 | 2 | 31 |
Mouse | [ |
490 | 2 | 3 |
Xclara | [ |
3 000 | 2 | 3 |
真实数据集
数据集 | 文献 | 样本量 | 属性数量 | 类簇数量 |
Iris | [ |
150 | 4 | 3 |
Ionosphere | [ |
351 | 34 | 2 |
Wine | [ |
178 | 13 | 3 |
WDBC | [ |
569 | 30 | 2 |
Seeds | [ |
210 | 7 | 3 |
Dermatology | [ |
366 | 34 | 6 |
Parkinsons | [ |
195 | 23 | 2 |
Libras movement | [ |
360 | 91 | 15 |
Yeast | [ |
1 484 | 8 | 10 |
Banknote | [ |
1 372 | 4 | 2 |
Zoo | [ |
101 | 17 | 7 |
MFCCs | [ |
7 195 | 22 | 10 |
Vihecle | [ |
846 | 18 | 4 |
Abalone | [ |
4 177 | 8 | 3 |
Pima | [ |
768 | 8 | 2 |
Thyroid | [ |
215 | 6 | 3 |
Olivetti faces | [ |
400 | 64×64 | 40 |
COIL20 | [ |
1 440 | 32×32 | 20 |
为了消除指标之间的量纲对实验影响, 需要对数据标准化处理. 本文采用最大最小归一化, 最大最小归一化的计算公式如下:
其中
为了保证对比实验的有效性, RKNN-DPC、DPC、FKNN-DPC、RDDPC、DBSCAN、K-means这5种聚类算法的聚类结果均在测试多组参数值后取最优结果, 其中RKNN-DPC的K近邻数取[5, 51), 步长为1, 预备值取[2,
本文选择了若干个常用的人工数据集, 比较各种聚类算法的聚类性能. 这些数据集的类簇数量不同, 样本不同, 可以模拟不同的情况.
人工数据集实验结果
数据集 | 指标 | RKNN-DPC | DPC | FKNN-DPC | RDDPC | DBSCAN | K-means | avg. |
Spiral | AMI | −0.0054 | 0.8324 | |||||
ARI | −0.0058 | 0.8323 | ||||||
NMI | 0.0005 | 0.8334 | ||||||
Arg- | 2/8 | 0.06 | 5 | 5 | 0.04/2 | 3 | - | |
Jain | AMI | 0.7414 | 0.7895 | 0.9341 | 0.043 | 0.7513 | ||
ARI | 0.8224 | 0.8597 | 0.976 | 0.0021 | 0.77 | |||
NMI | 0.7421 | 0.79 | 0.9345 | 0.1824 | 0.7748 | |||
Arg- | 2/7 | 0.31 | 13 | 12 | 0.08/2 | 2 | - | |
Zelnik3 | AMI | 0.7869 | 0.826 | 0.5843 | 0.8662 | |||
ARI | 0.721 | 0.7918 | 0.4874 | 0.8333 | ||||
NMI | 0.7884 | 0.8272 | 0.5873 | 0.8671 | ||||
Arg- | 8/11 | 0.06 | 7 | 13 | 0.07/11 | 3 | - | |
Four-lines | AMI | 0.8693 | 0.6849 | 0.9257 | ||||
ARI | 0.8174 | 0.5206 | 0.8896 | |||||
NMI | 0.8693 | 0.6849 | 0.9257 | |||||
Arg- | 2/11 | 0.06 | 9 | 48 | 0.05/5 | 4 | - | |
DIM512 | AMI | |||||||
ARI | ||||||||
NMI | ||||||||
Arg- | 2/6 | 0.05 | 7 | 6 | 0.41/2 | 16 | - | |
Aggregation | AMI | 0.9923 | 0.9956 | 0.9923 | 0.9828 | 0.8307 | 0.9656 | |
ARI | 0.9956 | 0.9978 | 0.9956 | 0.9881 | 0.721 | 0.9496 | ||
NMI | 0.9924 | 0.9956 | 0.9924 | 0.9828 | 0.833 | 0.966 | ||
Arg- | 2/17 | 0.09 | 9 | 26 | 0.06/11 | 7 | - | |
Flame | AMI | 0.9633 | 0.8752 | 0.8894 | 0.3969 | 0.8541 | ||
ARI | 0.9832 | 0.8748 | 0.9494 | 0.4534 | 0.8768 | |||
NMI | 0.9634 | 0.9338 | 0.8901 | 0.3987 | 0.8643 | |||
Arg- | 2/17 | 0.12 | 6 | 5 | 0.1/9 | 2 | - | |
D31 | AMI | 0.9526 | 0.9547 | 0.9559 | 0.9233 | 0.9496 | 0.949 | |
ARI | 0.9311 | 0.9345 | 0.935 | 0.8851 | 0.9058 | 0.922 | ||
NMI | 0.9547 | 0.9568 | 0.9579 | 0.9269 | 0.952 | 0.9514 | ||
Arg- | 2/16 | 0.05 | 11 | 33 | 0.03/23 | 31 | - | |
Mouse | AMI | 0.9737 | 0.8626 | 0.9246 | 0.8021 | 0.5947 | 0.8557 | |
ARI | 0.8728 | 0.9801 | 0.9414 | 0.7591 | 0.5185 | 0.8431 | ||
NMI | 0.8632 | 0.9638 | 0.9249 | 0.8032 | 0.5963 | 0.8542 | ||
Arg- | 10/18 | 0.08 | 13 | 7 | 0.07/9 | 3 | - | |
Xclara | AMI | 0.9887 | 0.9951 | 0.9955 | 0.9736 | 0.9872 | 0.99 | |
ARI | 0.9939 | 0.998 | 0.9979 | 0.9872 | 0.9928 | 0.9949 | ||
NMI | 0.9887 | 0.9951 | 0.9955 | 0.9736 | 0.9872 | 0.99 | ||
Arg- | 2/10 | 0.05 | 18 | 9 | 0.07/28 | 3 | - |
Spiral数据集上的聚类结果
Jain数据集上的聚类结果
Zelnik3数据集上的聚类结果
Four-lines数据集上的聚类结果
DIM512数据集上的聚类结果
Aggregation数据集上的聚类结果
Flame数据集上的聚类结果
D31数据集上的聚类结果
Mouse数据集上的聚类结果
Xclara的聚类结果
首先分析Spiral、Jain、Zelnik3这3个流形数据集, 其中Jain、Zelnik3的类簇密度有差距. 从
接下来讨论Four-lines、DIM512、Aggregation、Flame数据集, 4个数据集的分布较为清晰, 所以大多聚类算法可以得到较好的聚类效果.
由
实验使用了16个UCI数据集和2个图像数据集来测试RKNN-DPC聚类算法的性能. 这些数据集在样本数、特征数和簇的数量是不同的,
真实数据集实验结果
数据集 | 指标 | RKNN-DPC | DPC | FKNN-DPC | RDDPC | DBSCAN | K-means | avg. |
Iris | AMI | 0.8579 | 0.8665 | 0.8815 | 0.728 | 0.7421 | 0.8321 | |
ARI | 0.879 | 0.8823 | 0.9008 | 0.7388 | 0.7218 | 0.8436 | ||
NMI | 0.8598 | 0.8682 | 0.883 | 0.7302 | 0.7454 | 0.834 | ||
Arg- | 10/16 | 0.18 | 20 | 5 | 0.82/2 | 3 | - | |
Ionosphere | AMI | 0.2639 | 0.3192 | 0.1299 | 0.2578 | 0.1314 | 0.2433 | |
ARI | 0.2885 | 0.3926 | 0.2108 | 0.1698 | 0.1761 | 0.2859 | ||
NMI | 0.2833 | 0.3209 | 0.1319 | 0.2609 | 0.1333 | 0.2483 | ||
Arg- | 7/19 | 0.31 | 14 | 14 | 0.87/4 | 2 | - | |
Wine | AMI | 0.8336 | 0.7232 | 0.7407 | 0.5857 | 0.8135 | 0.7572 | |
ARI | 0.8561 | 0.6989 | 0.7269 | 0.5291 | 0.8368 | 0.7523 | ||
NMI | 0.8354 | 0.7261 | 0.7434 | 0.5904 | 0.8154 | 0.7598 | ||
Arg- | 16/26 | 0.21 | 37 | 18 | 0.5/21 | 3 | - | |
WDBC | AMI | 0.4855 | 0.6411 | 0.4979 | 0.0067 | 0.6225 | 0.4892 | |
ARI | 0.5016 | 0.6929 | 0.5174 | 0.0048 | 0.7301 | 0.5388 | ||
NMI | 0.4863 | 0.6416 | 0.4986 | 0.0101 | 0.623 | 0.4903 | ||
Arg- | 7/14 | 0.16 | 6 | 10 | 1.175/2 | 2 | - | |
Seed | AMI | 0.7213 | 0.7409 | 0.7319 | 0.5862 | 0.7421 | 0.717 | |
ARI | 0.7447 | 0.7684 | 0.7664 | 0.5291 | 0.7454 | 0.724 | ||
NMI | 0.7237 | 0.7432 | 0.7342 | 0.5911 | 0.7218 | 0.7159 | ||
Arg- | 7/9 | 0.08 | 6 | 5 | 0.24/16 | 3 | - | |
Dermatology | AMI | 0.8523 | 0.8217 | 0.8632 | 0.8559 | 0.644 | 0.8197 | |
ARI | 0.8208 | 0.7281 | 0.7941 | 0.7754 | 0.4669 | 0.7448 | ||
NMI | 0.8555 | 0.8255 | 0.8592 | 0.6493 | 0.7425 | 0.7997 | ||
Arg- | 6/9 | 0.3 | 7 | 6 | 1.429/20 | 6 | - | |
Parkinsons | AMI | 0.3473 | 0.2989 | 0.2731 | 0.1525 | 0.2318 | 0.2863 | |
ARI | 0.391 | 0.3769 | 0.2686 | 0.2074 | 0.0519 | 0.2947 | ||
NMI | 0.3513 | 0.3032 | 0.2761 | 0.1597 | 0.235 | 0.2905 | ||
Arg- | 5/7 | 0.07 | 8 | 19 | 0.34/6 | 2 | - | |
Libras Movement | AMI | 0.5661 | 0.5936 | 0.5978 | 0.3977 | 0.5476 | 0.5508 | |
ARI | 0.3526 | 0.3391 | 0.3721 | 0.1134 | 0.327 | 0.315 | ||
NMI | 0.6218 | 0.6472 | 0.6503 | 0.4728 | 0.6069 | 0.6089 | ||
Arg- | 2/8 | 0.08 | 8 | 9 | 0.9/2 | 15 | - | |
Yeast | AMI | 0.2396 | 0.1997 | 0.1352 | 0.2585 | 0.0942 | 0.199 | |
ARI | 0.0987 | 0.0766 | 0.1424 | 0.0354 | 0.1524 | 0.113 | ||
NMI | 0.2517 | 0.2116 | 0.1521 | 0.2719 | 0.1008 | 0.211 | ||
Arg- | 6/14 | 0.06 | 50 | 8 | 0.14/25 | 10 | - | |
Banknote | AMI | 0.879 | 0.4497 | 0.3891 | 0.728 | 0.0178 | 0.5609 | |
ARI | 0.9227 | 0.539 | 0.3684 | 0.6343 | 0.024 | 0.573 | ||
NMI | 0.8791 | 0.45 | 0.3895 | 0.7302 | 0.0183 | 0.5615 | ||
Arg- | 2/17 | 0.11 | 20 | 15 | 0.31/5 | 2 | - | |
Zoo | AMI | 0.5811 | 0.7495 | 0.8055 | 0.1361 | 0.5669 | 0.6162 | |
ARI | 0.5103 | 0.7165 | 0.8086 | 0 | 0.4479 | 0.5652 | ||
NMI | 0.6265 | 0.762 | 0.8445 | 0.1873 | 0.5791 | 0.6454 | ||
Arg- | 4/6 | 0.9 | 13 | 6 | 0.01/5 | 7 | - | |
MFCCs | AMI | 0.6097 | 0.6001 | 0.6197 | 0.7119 | 0.6851 | 0.6603 | |
ARI | 0.7258 | 0.6459 | 0.6966 | 0.828 | 0.5792 | 0.7254 | ||
NMI | 0.6107 | 0.6012 | 0.6213 | 0.7129 | 0.6861 | 0.6614 | ||
Arg- | 2/6 | 0.51 | 11 | 9 | 0.23/35 | 10 | - | |
Vihecle | AMI | 0.1867 | 0.1923 | 0.1833 | 0.1734 | 0.0961 | 0.1713 | |
ARI | 0.1286 | 0.1335 | 0.1009 | 0.0606 | 0.075 | 0.1074 | ||
NMI | 0.1904 | 0.1955 | 0.1872 | 0.1787 | 0.0996 | 0.1751 | ||
Arg- | 10/33 | 0.33 | 5 | 6 | 0.25/4 | 4 | - | |
Abalone | AMI | 0.1798 | 0.1534 | 0.1561 | 0.0924 | 0.1254 | 0.1512 | |
ARI | 0.1596 | 0.0704 | 0.1158 | 0.0938 | 0.0669 | 0.1141 | ||
NMI | 0.1802 | 0.1549 | 0.1564 | 0.1438 | 0.1265 | 0.1608 | ||
Arg- | 10/33 | 0.08 | 9 | 8 | 0.2/2 | 3 | - | |
Pima | AMI | 0.0358 | 0.0515 | 0.0269 | 0.0175 | 0.0507 | 0.0390 | |
ARI | 0.078 | 0.0804 | 0.0795 | 0.051 | 0.1023 | 0.0834 | ||
NMI | 0.0371 | 0.0529 | 0.029 | 0.0187 | 0.0517 | 0.0403 | ||
Arg- | 12/21 | 0.12 | 47 | 2 | 0.3/13 | 2 | - | |
Thyroid | AMI | 0.4545 | 0.4538 | 0.2913 | 0.6161 | 0.5908 | 0.5102 | |
ARI | 0.7526 | 0.4257 | 0.3861 | 0.2895 | 0.6282 | 0.5414 | ||
NMI | 0.4635 | 0.462 | 0.3044 | 0.6186 | 0.5966 | 0.5173 | ||
Arg- | 2/6 | 0.3 | 22 | 5 | 0.1/8 | 3 | - | |
Olivetti faces | AMI | 0.7513 | 0.7203 | 0.7811 | 0.5819 | 0.6174 | 0.7084 | |
ARI | 0.5508 | 0.5396 | 0.5855 | 0.1431 | 0.4126 | 0.4841 | ||
NMI | 0.847 | 0.8313 | 0.866 | 0.7323 | 0.7648 | 0.8203 | ||
Arg- | 4/5 | 0.4 | 6 | 44 | 0.5/2 | 40 | - | |
COIL20 | AMI | 0.7928 | 0.8376 | 0.8656 | 0.6962 | 0.7842 | 0.8112 | |
ARI | 0.4935 | 0.4523 | 0.6576 | 0.2105 | 0.6189 | 0.5327 | ||
NMI | 0.8027 | 0.8457 | 0.8718 | 0.7133 | 0.7942 | 0.8206 | ||
Arg- | 14/20 | 0.57 | 10 | 47 | 0.3/3 | 20 | - |
从
Olivetti faces类簇中心选择
COIL20类簇中心选择
本文针对DPC和改进的DPC存在的问题, 提出了基于代表点与K近邻的密度峰值聚类算法. 聚类过程主要为: 选择类簇中心和分配非中心点. 对于类簇中心的选择, 基于K近邻思想构造K近邻密度, 提出代表点、代表值定义, 在此基础上构造改进的局部密度计算方式, 解决了类簇差距问题; 对于非中心点的分配, 构造类簇权重公式, 考虑每个点的类簇可能性, 找到其最佳的类簇权重以完成最终聚类, 缓解了“多米诺效应”; 最后本文在人工数据集和真实数据集上进行了实验, 实验证明RKNN-DPC算法可以适用于不同大小、任意形状的数据集并且优于DPC的改进算法和常见聚类算法. 此外, 下一步的研究工作是尝试将该算法的思想应用到社区划分中, 研究基于改进的DPC的社区划分方法.
http://www.jos.org.cn/1000-9825/5625.htm]]>
http://www.jos.org.cn/1000-9825/5625.htm]]>
Wang CD, Lai JH, Huang D, Zheng WS. SVStream: A support vector-based algorithm for clustering data streams. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(6): 1410–1424. [doi: 10.1109/TKDE.2011.263]
Xu DK, Tian YJ. A comprehensive survey of clustering algorithms. Annals of Data Science, 2015, 2(2): 165–193. [doi: 10.1007/s40745-015-0040-1]
代永杨, 张清华, 支学超. 融合相对密度与近邻关系的密度峰值聚类算法. 重庆邮电大学学报(自然科学版), 2021, 33(5): 791–805. [doi: 10.3979/j.issn.1673-825X.202105220174]
Dai YY, Zhang QH, Zhi XC. Density peaks clustering algorithm by combining relative density with nearest neighbor relationship. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2021, 33(5): 791–805 (in Chinese with English abstract). [doi: 10.3979/j.issn.1673-825X.202105220174]
Park HS, Jun CH. A simple and fast algorithm for K-medoids clustering. Expert Systems with Applications, 2009, 36(2): 3336–3341. [doi: 10.1016/j.eswa.2008.01.039]
Zhang T, Ramakrishnan R, Livny M. BIRCH: An efficient data clustering method for very large databases. ACM SIGMOD Record, 1996, 25(2): 103–114. [doi: 10.1145/235968.233324]
Ankerst M, Breunig MM, Kriegel HP, Sander J. OPTICS: Ordering points to identify the clustering structure. ACM Sigmod Record, 1999, 28(2): 49–60. [doi: 10.1145/304181.304187]
Rodriguez A, Laio A. Clustering by fast search and find of density peaks. Science, 2014, 344(6191): 1492–1496. [doi: 10.1126/science.1242072]
Du MJ, Ding SF, Jia HJ. Study on density peaks clustering based on k-nearest neighbors and principal component analysis. Knowledge-Based Systems, 2016, 99: 135–145. [doi: 10.1016/j.knosys.2016.02.001]
Xie JY, Gao HC, Xie WX, Liu XH, Grant PW. Robust clustering by detecting density peaks and assigning points based on fuzzy weighted
陈玉洪, 张清华, 杨洁. 基于区间阴影集的密度峰值聚类算法. 模式识别与人工智能, 2019, 32(6): 531–544. [doi: 10.16451/j.cnki.issn1003-6059.201906006]
Chen YH, Zhang QH, Yang J. Density peak clustering algorithm based on interval shadowed sets. Pattern Recognition and Artificial Intelligence, 2019, 32(6): 531–544 (in Chinese with English abstract). [doi: 10.16451/j.cnki.issn1003-6059.201906006]
Seyedi SA, Lotfi A, Moradi P, Qader NN. Dynamic graph-based label propagation for density peaks clustering. Expert Systems with Applications, 2019, 115: 314–328. [doi: 10.1016/j.eswa.2018.07.075]
Jiang D, Zang WK, Sun R, Wang ZH, Liu XY. Adaptive density peaks clustering based on K-nearest neighbor and Gini coefficient. IEEE Access, 2020, 8: 113900–113917. [doi: 10.1109/ACCESS.2020.3003057]
Hou J, Zhang AH, Qi NM. Density peak clustering based on relative density relationship. Pattern Recognition, 2020, 108: 107554. [doi: 10.1016/j.patcog.2020.107554]
Guan JY, Li S, He XX, Zhu JH, Chen JJ. Fast hierarchical clustering of local density peaks via an association degree transfer method. Neurocomputing, 2021, 455: 401–418. [doi: 10.1016/j.neucom.2021.05.071]
Tao XM, Guo WJ, Ren C, Li Q, He Q, Liu R, Zou JR
http://www.jos.org.cn/1000-9825/6462.htm]]>
http://www.jos.org.cn/1000-9825/6462.htm]]>
Shi Y, Chen ZS, Qi ZQ, Meng F, Cui LM. A novel clustering-based image segmentation via density peaks algorithm with mid-level feature. Neural Computing and Applications, 2017, 28(S1): 29–39. [doi: 10.1007/s00521-016-2300-1]
Tu B, Yang XC, Li NY, Zhou GL, He DB. Hyperspectral anomaly detection via density peak clustering. Pattern Recognition Letters, 2020, 129: 144–149.
Xu ML, Li YH, Li RX, Zou FH, Gu XW. EADP: An extended adaptive density peaks clustering for overlapping community detection in social networks. Neurocomputing, 2019, 337: 287–302. [doi: 10.1016/j.neucom.2019.01.074]
Xie XY, Liu HW, Zeng SZ, Lin LB, Li W. A novel progressively undersampling method based on the density peaks sequence for imbalanced data. Knowledge-Based Systems, 2021, 213: 106689. [doi: 10.1016/j.knosys.2020.106689]
Elaziz MA, Al-Qaness MAA, Zaid EOA, Lu SF, Lbrahim RA, Ewees AA. Automatic clustering method to segment COVID-19 CT images. PLoS One, 2021, 16(1): e0244416. [doi: 10.1371/journal.pone.0244416]
Chang H, Yeung DY. Robust path-based spectral clustering. Pattern Recognition, 2008, 41(1): 191–203. [doi: 10.1016/j.patcog.2007.04.010]
Cheng DD, Zhu QS, Huang JL, Yang LJ, Wu QW. Natural neighbor-based clustering algorithm with local representatives. Knowledge-Based Systems, 2017, 123: 238–253. [doi: 10.1016/j.knosys.2017.02.027]
Vinh NX, Epps J, Bailey J. Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. The Journal of Machine Learning Research, 2010, 11: 2837–2854.
Chen WY, Song YQ, Bai HJ, Lin CJ, Chang EY. Parallel spectral clustering in distributed systems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(3): 568–586. [doi: 10.1109/TPAMI.2010.88]
Franti P, Virmajoki O, Hautamaki V. Fast agglomerative clustering using a k-nearest neighbor graph. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(11): 1875–1881. [doi: 10.1109/TPAMI.2006.227]
Gionis A, Mannila H, Tsaparas P. Clustering aggregation. ACM Transactions on Knowledge Discovery from Data, 2007, 1(1): 4-es. [doi: 10.1145/1217299.1217303]
Fu LM, Medico E. FLAME, a novel fuzzy clustering method for the analysis of DNA microarray data. BMC Bioinformatics, 2007, 8: 3. [doi: 10.1186/1471-2105-8-3]
Veenman CJ, Reinders MJT, Backer E. A maximum variance cluster algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(9): 1273–1280. [doi: 10.1109/TPAMI.2002.1033218]
Xia CY, Hsu W, Lee ML, Ooi BC. Border: Efficient computation of boundary points. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(3): 289–303. [doi: 10.1109/TKDE.2006.38]
Jia HJ, Ding SF, Du MJ. Self-tuning
http://archive.ics.uci.edu/ml]]>