uniform机器学习极简入门6—聚类算法2(DBSCAN和层次

前面我们已经分别介绍了Kmeans和GMM聚类模型，下面我们再介绍两个很实用的聚类算法。

DBSCAN密度聚类

KMeans聚类的形状一般对数据的本身特性要求较高（球状），但是在很多实际场景中未能很好满足该特性。如果类别的形状比较特殊，例如下图，我们从肉眼可以很容易看出类别的分布，如果从紧密程度角度出发，似乎可以把数据分出来，DBSCAN正是这样一种算法。

DATA

• DBSCAN

DBSCAN是一种基于密度聚类的算法，它基于一组邻域参数(min_dist, min_points)来刻画
下面我们给几个概念说明下这组参数

已知数据集合D={x1, x2, ..., xn}

1. min_dist邻域
   对xj样本，它的min_dist邻域表示数据集合中与xj的距离不大于min_dist的样本，即
   
2. 核心对象
   如果xj样本的邻域集合包含的样本个数至少有min_points个，那么可以认为xj样本是一个核心对象
   

我们的目标就是希望在样本集合里通过上述两个参数描述找到合适的聚类类别。

算法描述如下：

1. 初始化核心对象集合 O={}
2. for i=1, 2, ..., n do
3. 计算样本xi的邻域N(xi)，如果邻域数量大于min_points，则样本xi加入到核心对象集合O，否则不加入。
4. end for
5. 初始化聚类簇数k=0
6. 初始化未访问的样本集合 F=D
7. while O部位空集合 do
8. 记录当前未访问集合 Fold = F
9. 从核心对象集合中随机选择一个对象o，O=O\o, F=F\o,设置初始化队列Q={o}
10. while Q<>{} do
11. 取出队列Q中的首个样本q
12. 如果q也是一个核心对象，令T = N(q)和F的交集，将T的数据集合加入到Q队列，同时从F中去除掉T的元素。
13. end while
14. k=k+1 ，生成类簇Ck=Fold\F
15. end while

DBSCAN聚类主要还是围绕核心对象进行的，如果核心对象的邻域内包含别的核心对象，根据密度的传递性，那么该对象和邻域也是另一个核心对象的邻域。

大家肯定会想到，那如果不是核心对象的样本岂不是在这里就不会被最终分为类别了？对的，基于密度聚类有个好处就是，不会强制给每个样本都分配一个类别，对于DBSCAN来说，这些样本相当于是一个离群点。在sklearn算法中，这些离群点会以label=-1的形式给出。在实际实用中，DBSCAN这种特性可以让我们剔除掉不合适的样本，但是有个问题，就是(min_dist, min_points)参数调节问题。这里需要根据我们的特征向量来决定。

本节刚开始我们给了一个样例，如果利用DBSCAN，我们可以非常轻松分开（注意min_dist的设置）

DBSCAN Result

层次聚类

层次聚类顾名思义，就是根据样本特性逐层“自底向上”或者“自顶向下”来聚类。

• “自底向上”：先假设每个样本都是类别，然后每一次寻找距离最小的两个类簇，把他们聚合成一个类别，然后依次下去，直至达到我们需要的类别数。
• “自顶向下”： 先假设所有的样本只属于一个类别，然后根据某个评价指标把样本分为两个簇（例如之前kmeans例提到的二分法），找到类簇内距离较大的类别，继续拆分，直至我们需要的类别数。

这里涉及到如何定义两个类别的距离，一般常用的方法有

层次聚类算法过程如下图所示

层次聚类

本节详细描述可以参考周志华老师的《机器学习》(西瓜书)