Clustering by fast search and find of density peaks-论文精读报告

Clustering by fast search and find of density peaks

论文精度报告

作者：纪元

本文遵循CC-BY-NC-SA协议

(署名-非商业性-相同方式共享)

核心思想

簇心具有两个特征：

• 离其他高密度点 最远
• 周边密度值 最大

现有劣势

当前算法主要为K均值聚类和DBSCAN

• K均值聚类：只能解决球状问题，需要提前定义簇的总数，需要迭代划分。
• DBSCAN：需要提前定义阈值，计算量相对较大，且只对坐标上数据有效。

相对优势

能解决非球状分布问题，不需要将数据做成表(原文为"向量空间")，在划分时不需要迭代优化。

算法参数

$\delta$δ：表示该点距最近的高密度点（目标点密度大于该点本身密度）距离

$\rho$ρ：表示该点周边密度。计算方法为：统计该点周围，与其距离小于$d_c$dc​的点的数目。

$d_c$dc​：根据经验法则，使平均相邻点数为总点数的1%-2%即可

算法流程

• 计算所有点的$\rho、\delta$ρ、δ值
• 确定簇心-双高即认定为簇心
• 具体划分-将非簇心点划分至离其最近的簇心处，一步划分，不需要迭代。
• 噪声排除-将簇内距其他簇点小于$d_c$dc​点定义为边缘点，寻找周边密度值最大的边缘点，小于该密度值的都认定为噪声，大于该密度值的保留于簇内。

图像解读

• 表示参数的图定义为决策图（decision graph）
• 簇心由于参数值双高，集中在图的右上角
• 噪声的$\delta$δ高，$\rho$ρ低，集中在图的左下角

其他应用

该算法在人脸识别、高维数据集、特殊数据集（密度不统一，形状非球形）上均有良好的效果。

特别的，在人脸识别方面，因为数据集总数量较小，采用了较小的$d_c$dc​。有较多未分配但从结果上看错误率低：

B:将$\gamma_i$γi​降序排列并拟合，可以发现导数值在簇心和非簇心处（绿虚线）有较大改变，可以作为判断簇心的依据。
C:可以看出，
几乎没有不同个体被划分至同簇（红线）
个体数量越多，划分的簇越多（绿线）
个体数量越多，被识别的个体也越多（黑线）
个体数量越多，每个簇内的元素个数（除以10）越多（紫线）
D:灰色为噪声，带白圈的是簇心，相同颜色为被分出的元素。