聚类（下）

在聚类（上）中我们了解了一下聚类算法的基本原理，同时也了解了最常用的聚类算法K-Means以及相关的优化算法，对于K-Means来说，我们可以称之为原型聚类算法，本节再让我们来了解一下密度聚类和层次聚类算法。

密度聚类

密度聚类算法假设聚类结构能通过样本分布的紧密程度确定，一般情况下，密度聚类算法从样本密度的角度来考察样本的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。

密度聚类算法的主要特点：

1. 对噪声数据不敏感
2. 发现任意形状的簇
3. 一次扫描
4. 需要密度参数来作为算法停止的条件
5. 计算量大、复杂度高

DBSCAN的概念

DBSCAN是密度聚类中具有代表性的一个算法，它基于一组“邻域”参数$(\epsilon,MinPts)$(ϵ,MinPts)来刻画样本分布的紧密程度，给定数据集$D=\{x_1,x_2,...,x_m\}$D={x1​,x2​,...,xm​}，相对于基于划分的聚类算法和层次聚类算法，DBSCAN算法将簇定义为密度相连的样本的最大集合，能够将密度足够高的区域划分为簇，不需要给定簇的数量，并可以在有噪声的空间数据集中发现任意形状的簇。定义下面这几个概念：

• MinPts：$\epsilon-$ϵ−邻域内样本个数的最小值；

• $\epsilon-$ϵ−邻域：对$x_j\in D$xj​∈D，其$\epsilon-$ϵ−邻域包含样本集D中与$x_j$xj​的距离不大于$\epsilon$ϵ的样本，即$N_{\epsilon}(x_j)=\{x_i\in D|dist(x_i,x_j)\leqslant\epsilon\}$Nϵ​(xj​)={xi​∈D∣dist(xi​,xj​)⩽ϵ}，这个样本的子集个数记为$N_{\epsilon}(x_j)$Nϵ​(xj​)；

• 核心对象：若$x_j$xj​的$\epsilon-$ϵ−邻域至少包含MinPts个样本，即：$|N_\varepsilon (x_j)|\geq MinPts$∣Nε​(xj​)∣≥MinPts，则$x_j$xj​是一个核心对象；

• 密度直达：若$x_j$xj​位于$x_i$xi​的$\epsilon-$ϵ−邻域中，且$x_i$xi​是核心对象，则称$x_j$xj​由$x_i$xi​密度直达；

• 密度可达：对$x_i$xi​与$x_j$xj​，若存在样本序列$p_1,p_2,...,p_n$p1​,p2​,...,pn​，其中$p_1=x_i，p_n=x_j$p1​=xi​，pn​=xj​且$p_{i+1}$pi+1​由$p_i$pi​密度直达，则称$x_j$xj​由$x_i$xi​密度可达；

• 密度相连：对$x_i$xi​与$x_j$xj​，若存在$x_k$xk​，使得$x_i$xi​与$x_j$xj​均由$x_k$xk​密度可达，则称$x_i$xi​与$x_j$xj​密度相连。

从下图可以很容易看出理解上述定义，图中MinPts=5（图中每个圆内至少有5个样本），红色的点都是核心对象，因为其$\epsilon-$ϵ−邻域至少有5个样本。黑色的样本是非核心对象。所有核心对象密度直达的样本在以红色核心对象为中心的超球体内，如果不在超球体内，则不能密度直达。图中用绿色箭头连起来的核心对象组成了密度可达的样本序列。在这些密度可达的样本序列的$\epsilon-$ϵ−邻域内所有的样本相互都是密度相连的。

DBSCAN的算法思想

DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。

这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的s s里；如果有多个核心对象，则簇里的任意一个核心对象的ss中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的ss里所有的样本的集合组成的一个DBSCAN聚类簇。

那么怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。

基本上这就是DBSCAN算法的主要内容了，是不是很简单？但是我们还是有三个问题没有考虑。

第一个是一些异常样本点或者说少量游离于簇外的样本点，这些点不在任何一个核心对象周围，在DBSCAN中，我们一般将这些样本点标记为噪音点。

第二个是距离的度量问题，即如何计算某样本和核心对象样本的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧式距离。这和KNN分类算法的最近邻思想完全相同。对应少量的样本，寻找最近邻可以直接去计算所有样本的距离，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻。

第三种问题比较特殊，某些样本可能到两个核心对象的距离都小于\epsilon​，但是这两个核心对象由于不是密度直达，又不属于同一个聚类簇，那么如果界定这个样本的类别呢？一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为它的类别。也就是说DBSCAN的算法不是完全稳定的算法。

DBSCAN的算法流程

在进行DBSCAN算法之前首先我们要确定该算法需要的两个参数：

（1）$\epsilon$ϵ:在一个点周围邻近区域的半径
（2）minPts:邻近区域内至少包含点的个数

根据以上两个参数，结合$\epsilon-$ϵ−邻域的特征，可以把样本中的点分成三类：

核点（core point）：满足$|N_\varepsilon (x_j)|\geq MinPts$∣Nε​(xj​)∣≥MinPts，则为核样本点（核心对象）。
边缘点（border point）：$|N_\varepsilon (x_j)|< MinPts$∣Nε​(xj​)∣<MinPts，但是该点可由一些核点获得（密度直达或者密度可达）。
离群点（Outlier）：既不是核点也不是边缘点，则是不属于这一类的点。
（3）任意选择一个点（既没有指定到一个类也没有特定为离群点），计算它的$|N_\varepsilon (x_j)|$∣Nε​(xj​)∣判断是否为核点。如果是，在该点周围建立一个类，否则，设定为外围点。
（4）遍历其他点，直到建立一个类。把密度直达的点加入到类中，接着把密度可达的点也加进来。如果标记为离群点的点被加进来，修改状态为边缘点。
（5）重复步骤3和4，直到所有的点满足在类中（核点或边缘点）或者为离群点。

层次聚类

层次聚类试图在不同层次对数据集进行划分，从而形成树形的聚类结构，对于数据集的划分我们即可以采用“自底向上”的策略，也可以采用“自顶向下”的策略。层次聚类的展示图如下：

AGNES算法

AGNES是一种采用自底向上聚合策略的层次聚类算法。它先将数据集中的每个样本看作是一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直到达到预设的聚类簇个数。这里的关键就在于如何计算聚类簇之间的距离。

给定簇$C_i$Ci​与$C_j$Cj​，我们可以通过下面的式子来计算距离：

最小距离：

$d_{min}(C_i,C_j)=\underset{x\in C_i,z\in C_j}{min}dist(x,z)$dmin​(Ci​,Cj​)=x∈Ci​,z∈Cj​min​dist(x,z)

最大距离：

$d_{max}(C_i,C_j)=\underset{x\in C_i,z\in C_j}{max}dist(x,z)$dmax​(Ci​,Cj​)=x∈Ci​,z∈Cj​max​dist(x,z)

平均距离：

$d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum_{x\in C_i}\sum_{z\in C_j}dist(x,z)$davg​(Ci​,Cj​)=∣Ci​∣∣Cj​∣1​x∈Ci​∑​z∈Cj​∑​dist(x,z)

根据上面的公式，显然我们可以看出，最小距离由两个簇的最近样本决定，最大距离由两个簇的最远样本决定，而平均距离则由两个簇的所有样本共同决定。

AGNES算法的原理如下：

输入：包含n个对象的数据库，设定需要的簇的个数k。
输出：满足终止条件的若干个簇。
(1) 将每个对象当成一个初始簇；
(2)计算任意两个簇的距离，并找到最近的两个簇；
(3)合并两个簇，生成新的簇的集合；
(4)当不满足终止条件的时候重复执行（2）（3）；
(5) 终止条件（得到k个簇）得到满足，输出聚类结果。