Clustering by fast search and find of density peaks
研究的问题
本文提出了一种新型的基于密度的聚类算法，思路新颖、方法巧妙，能够实现对任意形状分布的数据进行聚类。
研究动机
传统基于距离的聚类算法仅仅局限于球面分布的数据聚类，为了实现对非球面数据、甚至对任意分布形状的数据聚类，密度聚类算法应用而生。密度聚类的典型代表DBSCAN算法能完成上述任务，但必须设定一个密度阈值来去除低于此密度阈值的噪音点。阈值的选取非常关键，甚至决定了聚类的成败，这增大了聚类的难度。本文提出的方法解决了该问题。
先进性与贡献
- DP聚类核心思想：聚类簇中心被具有较低局部密度的邻居点包围，且与具有更高密度的任何点有相对较大的距离。这样我们仅需聚算两个量就能完成聚类：局部密度𝜌i和NN距离𝜹i。
- 用一种简单的方式衡量样本得分：𝛄i = 𝜌i * 𝜹i, i ∈ Is（需要对𝜌i和𝜹i归一化处理来消除数量级的干扰）
具体方法
- 计算样本集两两之间的距离，构成距离矩阵
- 确定截断距离dc：选取一个dc，使样本平均近邻数约为总样本数的1%～2%
- 计算局部密度𝜌i：可通过Cut-off kernel方法或者Gaussian kernel方法计算
- 计算NN距离𝜹i：样本i到任何比其局部密度𝜌i大的样本的距离的最小值
- 𝜹i = min（dij）, 𝜌j > 𝜌i
- 𝜹i = max（dij）, 𝜌i = max（𝜌）
- 做出决策图（局部密度-距离图）和得分排序图
- 决定聚类簇的个数，得到聚类中心
- 依次对剩余样本完成聚类
优缺点及思考
本文提出的方法不仅能胜任任意形状数据分布的聚类任务，可以很好地描述数据分布，而且思路新颖，方法巧妙，在算法复杂度上也比一般的K-means算法低。同时该算法只考虑点与点之间的距离，不需要将点映射到一个向量空间中。该算法将非聚类中心点的聚类过程分离成一个单独的过程，使得聚类中心的选择和非聚类点的归类分离开来，增大了聚类精度。
2018.11.1
