原文：Clustering by fast search and find of density peaks
作者：Alex Rodriguez and Alessandro Laio
来源：Science 344.6191(2014), 1492-1496.
转载：简书不支持公式渲染，便于阅读可参考 原博文。
摘要
聚类分析的目的在于根据元素的相似性将元素分类。而该论文基于这样一种观点的提出新的方法，即聚类中心的密度高于其邻居，而密度高的点相对较远。这个想法构成了聚类过程的基础，其中簇的数量直观地产生，异常值被自动地发现并从分析中排除，并且聚类被识别，而不管它们的形状和嵌入它们的空间的维度如何。
正文
不同的聚类策略
基于距离的方法
在 K-means 和 K-medoids，聚类是以距离聚类中心很小的距离为特征的数据集合。
然而，因为数据点总是被分配到最近的中心，所以该类算法只能发现球形的簇，而在发现任意形状的簇时会遇到困难。
提示：
K-均值 (K-Means)的方法仅当簇中均值有定义时才有意义，而当涉及具有标称属性的数据时，K-均值的方法失效。而这里可采用K-众数 (K-Modes)的变体，即采用基于频率的方法来更新簇的众数，对具有标称属性的数据进行聚类。当然，还有K-Prototype、
K-Means++等优化版本的算法。
基于密度的方法
通过基于数据点局部密度的方法很容易检测具有任意形状的簇。其主要思想是：在某领域 (对象或数据点的数目) 内，给定密度阈值，将密度低于该阈值的数据点视为噪声丢弃，并将其分配给不连续的高密度领域的其他簇。这样的方法可用来过滤噪声或离群点，发现任意形状的簇。
DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 是一个基于密度的聚类算法，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的领域划分为簇。在噪声的空间数据库中可发现任意形状的聚类。
然而，从上述当中可知，除了要选择合适的阈值，且它缺少均值漂移的聚类方法。虽然这种方法允许发现非球形簇，但仅适用于由一组坐标定义的数据。
本文改进的方法
首先，该算法提出假设：类簇中心被具有较低局部密度的 邻居点 包围，且与具有较高密度的 任何点 有相对较大的距离。对于每一个数据点 i，要计算 两个量：点的局部密度 和该点到具有更高局部密度的点的距离
。而这两个值都取决于数据点间的距离
(欧几里得距离，也称
欧式距离)。数据点的局部密度定义为：
其中 为 0-1 函数，如果 x < 0，那么
；否则
，
是一个
截断距离。基本上， 等于与点 i 的距离小于
的点的个数。算法只对不同点
的相对大小敏感，这意味着对于大数据集，分析结果在
的选择方面具有很好
鲁棒性。
-
是通过计算点之间的
最小距离来测量的，即数据点 i 与距离它最近的、密度更高的点 j 的距离最小值式：提示：在图 1-1.(A) 中可知，数据点是按照密度降序排列。
- 若数据点 i 是密度最大的点，
如图 1-1 所示，其展示了算法的核心思想。图 1-1.(A) 展示了二维空间中的 28 个点，且 A 中数据点是按照密度降序排列。图 1-1.(B) 中以 作为横坐标，
作为纵坐标，画二维图，并称其为决策图。可以发现点 1 和点 10 的
和
最大，故将其作为类簇中心。
点 9 和点 10 的
相似，但
所以，正如预期的那样，只有具有高
类簇中心。因为点 26、27、28 是孤立的，所以有相对较高的异常点。
类簇中心找到后，剩余的每个点被归属到它的有更高密度的最近邻所属类簇。类簇分配只需 一步即可完成，不像其它算法要对目标函数进行 迭代优化。
在聚类分析中，定量的衡量分配的可信度是很重要的。在该算法中，首先为每个类簇定义一个 边界区域 (即分配到该类簇的点集合，且与其它类簇的点的距离小于 )，然后为每个类簇的找到其边界区域中密度最高的点
，并以来表示该点的密度。若类簇中局部密度值比
大的点被看作是类簇的核心部分 (即分配到该类簇的可靠性较高)，其他点 (类簇中局部密度值比
小的点) 被看作是类簇的
光晕部分 (亦可被看作是噪声)。
(A) 为绘制点分布的概率分布。(B和C) 分分别为4000和1000样本点的点分布。且每个点以其颜色表示所属类簇，黑色点属于光晕类簇 (噪声点)。(D和E) 为 (B和C) 相应的决策图，其中心由相应簇来着色。(F) 作为样本维度的函数，分配给不正确聚类的点的分数。误差线表示平均值的标准误差。
从图 1-2.(F) 中可以看到，错分点的比例即使在只有 1000 个点的小样本中仍保持在 1% 以下，说明算法有很好的鲁棒性。
从图 1-3 中可以看到，该算法对于各种数据级都能达到很好的聚类效果 (图中为引用文献中的测试用例结果)。
思考
- 摘要部分提到的，异常点能
自动地被分析出来，但从它的 Matlab 源码可知，还是需要人为判断异常点 (与问题三结合思考)？ - 文中提到的截断距离
，该设定多少才算较合理？
- 文中判断簇中心的两个参数量
参考资料
[1] Huang Z. Clustering large data sets with mixed numeric and categorical values [C]. 1997: 21-34.
[2] Huang Z. Extensions to the k-means algorithm for clustering large data sets with categorical values [J]. Data mining and knowledge discovery, 1998, 2(3): 283-304.
[3] San O M, Huynh V N, Nakamori Y. A clustering algorithm for mixed numeric and categorical data [J]. Journal of Systems Science and Complexity, 2003, 16(4): 562-571.
