整体框图


基于密度

核心思想:用一个点的 $\epsilon$ 邻域内的邻居点数衡量该点所在空间的密度,可以发现任意形状的聚类,且对噪声数据不敏感.


DBSCAN

DBSCAN算法有两个重要的参数:Eps 和 MinPts。前者为定义密度时的邻域半径,后者定义为核心点所拥有的最小邻居数。

我们先对数据点进行分类,邻域内数据点数:$\rho(x) \ge MinPts$,我们称之为核心点。核心点邻域内的非核心点我们成为边界点,其它的就是噪声点,不在任何核心点的邻域内,看图。

数据点分类

通俗地讲,核心点对应稠密区域内部的点,边界点对应稠密区域边缘的点,而噪声点对应稀疏区域中的点。


算法实现也非常简单,我们先随机的从某个核心点出发,将它邻域内的点加入我们的seed_list,自身输出到结果列表,打上cluster标签;然后从seed_list中取出一个点,如果是非核心点,丢到结果列表即可,如果是核心点,则还要将其邻域内的点加到seed_list,循环直到seed_list清空,则分完一类;然后在从剩下未处理的核心节点挑一个,继续,直到所有核心节点都被处理完,剩下的未访问的点就是噪声点。

数据点分类


优点:

  • 不需要事先指定cluster的数目
  • 可以发现任意形状的cluster
  • 能够找出数据中的噪声点,且对噪声不敏感

缺点:

  • DBSCAN不适用于数据集密度差异很大的情形(参数难以设置)

数据点分类


OPTICS

OPTICS可以视为DBSCAN算法的一种改进算法,它并不显示地生成数据聚类,而是为聚类分析生成一个增广的簇排序。这个排序代表了各样本点基于密度的聚类结果,如以可达距离为纵轴,样本点输出次序为横轴的坐标轴,包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类1

OPTICS引入了两个额外的概念:核心距离和可达距离。


  • 一个对象$p$的核心距离是使得其成为核心对象的最小半径,如果$p$不是核心点,其可达距离没有定义。

  • 可达距离是根据核心距离来定义的。

数据点分类


其中 $X$ 是原始的点的数据集合,$P$ 作为最后输出结果的点集的有序序列,seedlist 是一个无重复元素的队列, 保存了当前已找到但是还没处理过的属于同一类别的点的集合。算法首先遍历输入的点集 $X $,找到一个核心点,如果找不到,则直接结束算法,如果找到一个点 x 为核心点, 则设置 $x$ 的核心距离以及可达距离并将其加入输出序列 $P$,将其所有邻点加入队列 seedlist。 之后从队列 seedlist 中找出可达距离最小的点 $y$,将其加入输出序列,如果 $y$ 也是核心点, 则将 $y$ 的所有邻点加入到并且更新队列 seedlist。重复以上步骤直到处理完所有的点2


处理流程3

数据点分类


上面的算法处理完后,我们得到了输出结果序列,每个节点的可达距离和核心距离。我们以可达距离为纵轴,样本点输出次序为横轴进行可视化,

数据点分类


每个团簇的深浅代表了团簇的紧密程度,我们可以在这基础上采用DBSCAN(选取最有的Eps)或层次聚类方法对数据进行聚类。

数据点分类


基于OPTICS算法扩展有很多,比如:

  • OPTICS-OF用来检测异常值(Outliar Detection);
  • DeLi-Clu算法来消除eps参数,提供比OPTICS更好的性能指标;
  • HiSC算法将其应用到Subspace Clustering;
  • HiCO应用到相关聚类(Correlation Clustering)上;
  • 基于HiSC改进的DiSH能够找到更加复杂的簇结构。

基于峰值密度和距离

这是由Alex和Alessandro于2014年发表在的Science上的一篇关于聚类的文章,整体思路非常简单,效果很不错。

文中聚类算法的核心思想在于对聚类中心的刻画上,作者认为聚类中心应该同时具有以下两个特点:

  • 本身的密度大,即它被密度均不超过它的邻居包围;
  • 与其它密度更大的数据点之间的“距离”相对更大

我们可以用一种通俗的方法来解释,就好比江湖中的帮派,各个帮派的老大相当于是聚类中心,密度大相当于小弟多,“距离”大小相当于亲疏程度,同一帮派的人之间距离小,而不同帮派的人之间距离大。作为帮派老大有什么特点呢?一方面,他拥有众多的小弟,本身密度很大;另外,他与其它更大帮派老大距离应该更大,不然就要打架了4


为了从数学的角度来描述聚类中心,我们需要定义两个指标:局部密度$\rho_i$和距离$\delta_i$。

$x_i$的局部密度$\rho_i$定义为:

其中,

$\rho_i$表示与$x_i$之间的距离小于$d_c$的数据点数。


距离$\delta_i$度量$x_i$和比其密度高的最近样本点之间的距离。如果$\rho_i$为最大值,则$\delta_i$为离$x_i$最远样本之间的距离。

数据点分类


我们根据每个点的$(\rho_i,\delta_i)$画出决策图,

数据点分类

容易发现,1 号和 10 号数据点由于同时具有较大的 $\rho$ 值和 $\delta$ 值,于是就脱颖而出了,这两个点正好是图A的两个聚类中心。26 , 27 , 28 这三个数据点在原始数据集中是“离群点”,它们的特点是:$\delta$ 值很大,但 $\rho$ 值很小。