---

基于密度

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

---

DBSCAN

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

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

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

---

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

---

优点：

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

缺点：

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

---

OPTICS

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

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

---

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

$$cd(x) = \begin{cases} UNDEFINED & \text{若$|N_{\epsilon}(x)|<\mathcal{M}$} \\ d(x,N_{\epsilon}^{\mathcal{M}}(x)) & \text{若$|N_{\epsilon}(x)|\ge \mathcal{M}$} \end{cases}$$

---

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

$$rd(y,x) = \begin{cases} UNDEFINED & \text{若$|N_{\epsilon}(x)|<\mathcal{M}$} \\ max\{ cd(x),d(x,y) \} & \text{若$|N_{\epsilon}(x)|\ge \mathcal{M}$} \end{cases}$$

---

---

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

---

处理流程³：

---

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

---

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

---

基于OPTICS算法扩展有很多，比如：

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

---

基于峰值密度和距离

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

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

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

---

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

---

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

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

$$\rho_i = \sum_j \chi(d_{ij} - d_c)$$

其中，

$$\begin{equation} \chi(x)=\begin{cases} 1,& \text{if \(x<0\)};\\ 0,& otherwise. \end{cases} \end{equation}$$

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

---

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

$$\begin{equation} \delta_i=\begin{cases} \underset{j:\rho_j>\rho_i}{\min}(d_{ij}), & \text{if \(\exists j,\rho_j>\rho_i\)};\\ \underset{j}{\max}(d_{ij}), & otherwise. \end{cases} \end{equation}$$

---

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

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

---

---

---