论文 | 通过快速查找和发现密度峰值进行聚类

原文:Clustering by fast search and find of density peaks
作者:Alex Rodriguez and Alessandro Laio
来源:Science 344.6191(2014), 1492-1496.

摘要

聚类分析的目的在于根据元素的相似性将元素分类。而该论文基于这样一种观点的提出新的方法,即聚类中心的密度高于其邻居,而密度高的点相对较远。这个想法构成了聚类过程的基础,其中簇的数量直观地产生,异常值被自动地发现并从分析中排除,并且聚类被识别,而不管它们的形状和嵌入它们的空间的维度如何。

正文

不同的聚类策略

基于距离的方法

K-meansK-medoids,聚类是以距离聚类中心很小的距离为特征的数据集合。

然而,因为数据点总是被分配到最近的中心,所以该类算法只能发现球形的簇,而在发现任意形状的簇时会遇到困难。

提示:K-均值 (K-Means) 的方法仅当簇中均值有定义时才有意义,而当涉及具有标称属性的数据时,K-均值的方法失效。而这里可采用 K-众数 (K-Modes) 的变体,即采用 基于频率 的方法来更新簇的众数,对具有标称属性的数据进行聚类。当然,还有 K-Prototype $^{[1,2]}$、K-Means++ $^{[3]}$ 等优化版本的算法。

基于密度的方法

通过基于数据点局部密度的方法很容易检测具有任意形状的簇。其主要思想是:在某领域 (对象或数据点的数目) 内,给定密度阈值,将密度低于该阈值的数据点视为噪声丢弃,并将其分配给不连续的高密度领域的其他簇。这样的方法可用来过滤噪声或离群点,发现任意形状的簇。

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 是一个基于密度的聚类算法,它将簇定义为密度相连的点的最大集合,能够把具有足够高密度的领域划分为簇。在噪声的空间数据库中可发现任意形状的聚类。

然而,从上述当中可知,除了要选择合适的阈值,且它缺少均值漂移的聚类方法。虽然这种方法允许发现非球形簇,但仅适用于由一组坐标定义的数据。

本文改进的方法

首先,该算法提出假设:类簇中心被具有较低局部密度的 邻居点 包围,且与具有较高密度的 任何点 有相对较大的距离。对于每一个数据点 i,要计算 两个量:点的局部密度 $\rho_i$ 和该点到具有更高局部密度的点的距离 $\delta_i$。而这两个值都取决于数据点间的距离 ${d}_{ij}$ (欧几里得距离,也称 欧式距离)。数据点的局部密度定义为:

其中 $\chi(x)$ 为 0-1 函数,如果 x < 0,那么 $\chi(x) = 1$;否则 $\chi(x) = 0$,$d_{c}$ 是一个 截断距离。基本上,$\rho_i$ 等于与点 i 的距离小于 $d_{c}$ 的点的个数。算法只对不同点 $\rho_i$ 的相对大小敏感,这意味着对于大数据集,分析结果在 $d_{c}$ 的选择方面具有很好 鲁棒性

  • $\delta_i$ 是通过计算点之间的 最小距离 来测量的,即数据点 i 与距离它最近的、密度更高的点 j 的距离最小值式:

    提示:在图 1-1.(A) 中可知,数据点是按照密度降序排列。

  • 若数据点 i 是密度最大的点,$\delta_i$ 为所有节点中到数据点 i 的最大距离:

如图 1-1 所示,其展示了算法的核心思想。图 1-1.(A) 展示了二维空间中的 28 个点,且 A 中数据点是按照密度降序排列。图 1-1.(B) 中以 $\rho_i$ 作为横坐标,$\delta_i$ 作为纵坐标,画二维图,并称其为决策图。可以发现点 1 和点 10 的 $\rho_i$ 和 $\delta_i$ 最大,故将其作为类簇中心。

点 9 和点 10 的 $\rho_i$ 相似,但 $\delta_i$ 值却有很大差别:点 9 属于点 1 的类簇,且有其它几个更高 $\rho_i$ 的点距其很近,然而点 10 拥有更高密度的最近邻属于其它的类簇。

所以,正如预期的那样,只有具有高 $\delta_i$ 和相对较高 $\rho_i$ 的的点才是 类簇中心。因为点 26、27、28 是孤立的,所以有相对较高的 $\delta_i$ 值和低 $\rho_i$ 值,它们可以被看作是由单个点做成的类簇,也就是 异常点

图1-1算法在二维空间的展示

图 1-1 算法在二维空间的展示

类簇中心找到后,剩余的每个点被归属到它的有更高密度的最近邻所属类簇。类簇分配只需 一步即可完成,不像其它算法要对目标函数进行 迭代优化

在聚类分析中,定量的衡量分配的可信度是很重要的。在该算法中,首先为每个类簇定义一个 边界区域 (即分配到该类簇的点集合,且与其它类簇的点的距离小于 $d_c$),然后为每个类簇的找到其边界区域中密度最高的点 $\rho_b$,并以来表示该点的密度。若类簇中局部密度值比 $\rho_b$ 大的点被看作是类簇的核心部分 (即分配到该类簇的可靠性较高),其他点 (类簇中局部密度值比 $\rho_b$ 小的点) 被看作是类簇的 光晕部分 (亦可被看作是噪声)。

图1-2合成点分布的结果

图 1-2 合成点分布的结果

(A) 为绘制点分布的概率分布。(B和C) 分分别为 4000 和 1000 样本点的点分布。且每个点以其颜色表示所属类簇,黑色点属于光晕类簇 (噪声点)。(D和E) 为 (B和C) 相应的决策图,其中心由相应簇来着色。(F) 作为样本维度的函数,分配给不正确聚类的点的分数。误差线表示平均值的标准误差。

从图 1-2.(F) 中可以看到,错分点的比例即使在只有 1000 个点的小样本中仍保持在 1% 以下,说明算法有很好的鲁棒性。

从图 1-3 中可以看到,该算法对于各种数据级都能达到很好的聚类效果 (图中为引用文献中的测试用例结果)。

图1-3引用文献中的测试用例结果

图 1-3 引用文献中的测试用例结果

思考

  1. 摘要部分提到的,异常点能 自动地 被分析出来,但从它的 Matlab 源码可知,还是需要人为判断异常点 (与问题三结合思考)?
  2. 文中提到的截断距离 $d_c$,该设定多少才算较合理?
  3. 文中判断簇中心的两个参数量 $\delta_i$ 和 $\rho_i$,即同时具有相对较高的距离和局部密度可选为簇中心,那么如何定义相对较高的具体值?

参考

[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.