常用聚类算法综述

皮大大

发布于 2024-06-21 13:56:02

1120

发布于 2024-06-21 13:56:02

文章被收录于专栏：机器学习/数据可视化

本篇文章分享一些日常工作中最常用的聚类算法做介绍，全文较长，全文较长，欢迎点赞收藏。

来源：https://zhuanlan.zhihu.com/p/78382376，作者：Slumbers（美团）

聚类的概念

对于有标签的数据，我们进行有监督学习，常见的分类任务就是监督学习；而对于无标签的数据，我们希望发现无标签的数据中的潜在信息，这就是无监督学习。

聚类，就是无监督学习的一种，它的概念是：将相似的对象归到同一个簇中，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。即聚类后同一类的数据尽可能聚集到一起，不同数据尽量分离。

聚类算法的分类

聚类算法有很多种分法，体系也很大，这里举例几种分法：

基于划分的聚类：聚类目标是使得类内的点足够近，类间的点足够远，常见的如k-means及其衍生算法
基于密度的聚类：当邻近区域的密度超过某个阈值，则继续聚类，如DBSCAN; OPTICS
层次聚类：这个下面会具体介绍到，包括合并的层次聚类，分裂的层次聚类，实际上可以看作是二叉树的生成和分裂过程。下面会介绍实际应用中常用的HDBSCAN
基于图的聚类：通过建图来进行聚类，这是聚类算法中的大头，很多较新的聚类算法都有图聚类的思想。这篇文章会介绍以Chinese Whisper，谱聚类两大具有代表性的图聚类算法
基于GCN（图神经网络）的聚类：实际上这个本质上也是基于图的聚类，然而基于GCN的聚类算法会有深度学习中的训练的概念，而传统的聚类算法则是通过人工设定阈值来决定的，所以这里也分开列了一类，这篇文章会介绍《Learning to Cluster Faces on Affinity Graph》、CDP两篇论文的思想。

其实还有很多分类，但这里不再列举了，有兴趣的同学可以参考sklearn文档中关于聚类的划分：

https://scikit-learn.org/stable/modules/clustering.html#clustering

K-Means聚类

这个可以说是最基础的聚类算法了，它的输入需要簇的个数k，这个k是用户指定的，也就是说需要提前确定类别，其算法流程是：

随机确定$k$个初始点$u_1, u_2...u_k$作为聚类质心

重复以下过程直到收敛：

对于每一个样例，找到离它最近的质心作为label：

对于每一个类j, 更新其质心：

算法优点

主要是速度快

缺点

必须提前知道"k"，也就是有多少个簇
容易陷入局部最优
数据必须符合“数据之间的相似度可以使用欧式距离衡量”，这个是什么意思呢，看下图，这种数据的分布，样本点的距离不能简单地用欧式距离来衡量，否则分类效果会非常差。这里的距离衡量应该是“测地距离”，也就是样本沿着曲面到达另一个样本点的距离。如果在这种数据空间想要使用kmeans，必须先进行空间的转化。

k-means有一些改进算法，多是针对k-means会受异常点的影响这一点来改进的，比如K-Means++, K-Medians...

基于密度的算法-DBSCAN

基于密度的算法，要求聚类空间的一定区域所包含的对象的数目不小于某一给定阈值，先了解一些基本概念：

（1）Eps邻域：给定对象半径Eps内的邻域称为该对象的Eps邻域;

（2）核心对象（core point）：如果对象的Eps邻域至少包含最小数目MinPts的对象，则称该对象为核心对象;

（3）直接密度可达(directly density-reachable)：若某点p在点的q的Eps领域内，且q是一个核心对象，则p-q直接密度可达

（4）密度可达(density-reachable)：如果存在一个对象链 p1, …,pi,.., pn，如果对于任意pi, pi-1都是直接密度可达的，则称pi到pi-1密度可达，实际上是直接密度可达的传播链

（5）密度相连(density-connected)：如果从某个核心对象p出发，点q和点k都是密度可达的，则称点q和k是密度相连的。

（6）边界点（edge point）：边界点不是核心对象，但落在某个核心对象的邻域内;

（7）噪音点（outlier point）：既不是核心点，也不是边界点的任何点;

看看上图，红色点是所谓的核心对象，以它为圆心，Eps为半径去画圆，在圆内样本点数目大于MinPts的就是核心对象；被包含在核心对象的范围内，但是自身不是核心对象的点是样本点；即不被包含在核心对象内，自身也不是核心对象的点为噪音点，将被抛弃。

DBSCAN的核心思想是从某个核心点出发，不断向密度可达的区域扩张，从而得到一个包含核心点和边界点的最大化区域，区域中任意两点密度相连。现在我们来看看DBSCAN的一个算法流程，会更容易理解：

输入：给定点在领域内成为核心对象的最小领域点数(MinPts), 领域半径: Eps

输出：簇集合

伪代码如下：

首先将数据集D中所有的对象标记为未处理状态：
对数据集D中的每个对象p：
if p已经归入了某个簇:
    continue
else:
检查对象p的Eps领域 NEps(p)
if NEps(p)包含的对象数小于MinPts:
标记对象p为边界点或者噪声点；
else:
标记对象p为核心点，并建立新簇C，将p领域内的所有点加入C
for (NEPs(p)中所有尚未处理的对象q):
检查对象q的领域NEps(q), 若NEps(q)包含至少MInPts个对象，则将NEps(q)中未归入
任何一个簇的对象加入C

优点

不需要指定簇的数目（不需要 k）
可以发现任意形状的聚类簇
对噪声不敏感

从上面的图形中可以看出来：kmeans和DBSCAN的对比可以看出DBSCAN对这种数据分布的拟合更好

缺点

需要设置半径Eps和MinPts, 空间聚类密度不均匀时难以设置参数，所以有一个问题就是，在数据集A上挑好的参数很可能到数据集B上就不能用了。
随着数据量的增大，计算量显著增大，反正大规模数据集用DBSCAN很可能会崩的。

层次密度聚类 HDBSCAN

这是一个对DBSCAN的改进算法，结合了密度聚类和层次聚类。它的优化点主要如下：

使用相互可达距离替换欧氏距离，该距离可以使得密度低的点离密度高的区域更远，减少dbscan对Eps阈值的依赖性
使用最小生成树构建层次聚类模型，引入层次聚类思想
对最小生成树的最小子树做了限制，减少计算量，同时保证生成的类簇不要过小
使用“簇稳定性”的度量方式自动划分类簇，不需要自行设定阈值这里面有一些专业术语可能一看起来不太能明白，我们来逐一解释。

可达距离

可达距离是对DBSCAN中核心距离的一个改进版，也是DBSCAN的改进算法OPTICS的主要核心思想，也就是通过改变距离的度量方式减少dbscan对阈值Eps的敏感性；该距离可以让稀疏的点离密度高的区域更远。了解可达距离之前，我们先看看核心距离：

核心距离：对于给定的样本点，使得该点成为核心点的最小Eps为该点的核心距离。

假设样本点为p, 找到以p为圆心，刚好满足minPts的最外层的点q，则p和q的距离为核心距离；看下图，加入我们的MinPts设为3，那么找到以红色点P为圆心，MinPts正好为3的半径即为核心距离

可达距离：对于样本点p周围的点q1,q2...,1n,如果这些点到点p的距离大于p的核心距离，则可达距离为该点到p的实际距离；如小于，则可达距离为点x的核心距离。我们继续看上图，点1,2，3的可达距离均为核心距离，而在核心距离之外的点4，5，它们到点P的距离仍然是欧式距离。

那么为什么要用可达距离替换欧氏距离呢？

看看下图中，蓝色核心点和绿色核心点原本的距离应该是两点的欧氏距离，但是因为蓝色核心点在绿色核心点的核心距离内，所以此时它们的可达距离为绿色核心点的半径>两点的欧氏距离，相当于把蓝色核心点和绿色核心点区分开了；

红色核心点到蓝色核心点的距离一样，它们的可达距离要大于蓝色核心点和红色核心点的实际距离，这样以蓝色核心点为代表的高密度区域与红色核心点、绿色核心点的低密度区域就被推开了；而绿色核心点和红色核心点的距离则依旧是它们的欧氏距离。

层次聚类

要理解HDBSCAN，首先要搞清楚层次聚类到底是什么。层次聚类有自上而下的方式和自下而上的方式。在这里我们只介绍自下而上的方式，也就是HDBSCAN算法中用到的方式。

假设：假设有n个待聚类的样本
初始化：将每个样本都视为一个簇；
计算相似度：计算各个聚类之间的相似度；
分类：寻找最近的两个聚类，将他们归为一类；
循环：重复步骤二，步骤三；直到所有样本归为一类。

其实就是一个不断归一化最后归成一类的过程。实际上层次不同的层次聚类算法考虑的主要是相似度的衡量方式和终止聚类的条件的不同。相似度的衡量方式决定了哪些样本将被聚到一起，而中止聚类的条件决定了选择哪一层级的类别作为最终的聚类输出。

而HDBSCAN是以可达距离作为领接边权重，对所有节点构建最小生成树，之后进行层次聚类。

簇压缩

我们将HDBSCAN的样本点进行层次聚类，构造成上面的生成树图之后，HDBSCAN会进行一个压缩树的过程。它的原理是，对于我们生成的最小生成树，从上往下遍历，在一个簇被划分为两个子簇的过程中，如果子簇的样本点数量小于设定的最小值（也就是前面可达距离的概念中设置的MinPts，那么这个小于MinPts的子簇将会不会被保留，子簇中的样本将作为-1类被删除。