作者：韩信子 @ShowMeAI
教程地址：http://www.showmeai.tech/tutorials/34
本文地址：http://www.showmeai.tech/article-detail/197
申明：版权所有，转载请分割平台与作者并注明出处

引言

聚类（Clustering）是最常见的无监督学习算法，它指的是依照某个特定规范（如间隔）把一个数据集宰割成不同的类或簇，使得同一个簇内的数据对象的相似性尽可能大，同时不在同一个簇中的数据对象的差异性也尽可能地大。也即聚类后同一类的数据尽可能汇集到一起，不同类数据尽量拆散。

聚类算法在很多场景下都有利用，例如新闻主动分组，用户分群，图像宰割等等。很多时候，无监督的聚类算法，失去的聚类后果还能够作为特色在后续监督学习中利用，晋升整体成果。本篇内容 ShowMeAI 带大家一起来学习一下聚类算法。

（本篇聚类算法局部内容波及到机器学习基础知识，没有先序常识储备的宝宝能够查看 ShowMeAI 的文章 图解机器学习 | 机器学习基础知识。

1. 聚类问题

1）聚类问题与外围概念

俗话说人以类聚物以群分，聚类算法做的事件，就是对无标签的数据，基于数据分布进行分群分组，使得类似的数据尽量落在同一个簇内。

咱们先 比照辨别一下聚类和分类：

• 聚类是一种无监督学习，而分类是一种有监督的学习。
• 聚类只须要人工指定类似度的规范和类别数就能够，而分类须要从训练集学习分类的办法。

2）聚类算法用处

聚类算法利用十分宽泛。在面对未知的世界时，先分类，再一一钻研，是人类摸索未知世界的一个根本办法。聚类算法能够利用于探索性数据挖掘、统计分析、生物信息学、数据压缩、计算机图像识别、医学影像剖析等，在商业畛域能够用来做市场钻研、商品归类，在社会科学畛域能够用来做立功区域分析等等。

下图中有一些样本点，咱们依据物理间隔的远近，把所有的点分成 3 类。你只须要通知算法这些信息，算法就能够依照你的要求实现聚类：

• 分类数量为 3；
• 分类规范是物理间隔；
• 分好的类别离用红、绿、蓝示意。

实际上，除了物理间隔，现实生活中任何你能想到、计算机能够通过运算和逻辑进行判断的规定，都能够作为分类规范。

上面咱们用图像压缩作为例子来解释一下。最右边是一张彩色照片，大小约 1Mb，通过压缩能够把它变成几十到几百 Kb，这就是压缩软件的实现过程。那么压缩软件的实现原理是什么呢？其中一种就是聚类算法。

从原始图片到压缩存储的过程如下图所示：

聚类算法同样能够用于图像宰割。图像中每一个像素点是一个 3 维向量，对应 [R, G, B] 像素值。给定聚类中类别个数 K，算法用 K 个不同的色彩来示意原来的图像，每个像素点用 K 个色彩中一个示意。具体如下：

对于文档、新闻、商品而言，很多时候咱们会应用嵌套的归类办法，这是一种层次化聚类：

3）支流聚类算法

咱们先对聚类算法做个理解，支流的聚类算法能够分成两类：划分聚类 （Partitioning Clustering）和 档次聚 类（Hierarchical Clustering）。他们的次要区别如图中所示：

划分聚类算法会给出一系列扁平构造的簇（离开的几个类），它们之间没有任何显式的构造来表明彼此的关联性。

• 常见算法有 K-Means/K-Medoids、Gaussian Mixture Model（高斯混合模型）、Spectral Clustering（谱聚类）、Centroid-based Clustering 等。

档次聚类会输入一个具备层次结构的簇汇合，因而可能比划分聚类输入的无构造簇汇合提供更丰盛的信息。档次聚类能够认为是是嵌套的划分聚类。

• 常见算法有 Single-linkage、Complete-linkage、Connectivity-based Clustering 等。

这两类算法在聚类过程中用到的具体算法不一样，后文咱们会重点开展讲一下 K -Means 算法、Single-linkage 算法和 Complete-linkage 算法。

2.K-Means 聚类算法

K-Means 算法是聚类算法中一个十分根底的算法，同时利用又十分宽泛，上面 ShowMeAI 给大家开展解说算法原理。

1）K-Means 算法外围概念

咱们提到了聚类算法要把 n 个数据点依照散布分成 k 类（很多算法的 k 是人为提前设定的）。咱们心愿通过聚类算法失去 k 个中心点，以及每个数据点属于哪个中心点的划分。

• 中心点能够通过迭代算法来找到，满足条件：所有的数据点到聚类核心的间隔之和是最小的。
• 中心点确定后，每个数据点属于离它最近的中心点。

在进入「如何寻找中心点」这个外围问题之前，咱们先解决几个小问题：

Q1：数据点到中心点的间隔如何计算？

• 咱们个别抉择几何间隔，就是 L2 间隔的平方。

Q2：中心点是否惟一，或者说，是不是存在全局最优解？

• 对于多个中心点的状况，全局最优是一个相当难的问题。实践上存在一个全局最优解，然而不肯定能找到。既然全局最优解不好找，那咱们退而求其次，看能不能找到部分最优解。

Q3：聚类后果如何示意？

• 采纳空间宰割的形式：将空间宰割成多个多边形，每个多边形对应一个 cluster 核心。

2）K-Means 算法步骤

K-Means 采纳 EM 算法迭代确定中心点。流程分两步：

• ① 更新中心点：初始化的时候以随机取点作为起始点；迭代过程中，取同一类的所有数据点的重心（或质心）作为新中心点。
• ② 调配数据点：把所有的数据点调配到离它最近的中心点。

反复下面的两个步骤，始终到中心点不再扭转为止。过程如图所示：

• 左侧 Assignments：一开始随机选取三个点，作为三个类的核心，基于其它点和这三个中心点的间隔调配簇；每一类从新计算和调配核心。
• 右侧 Refitted Means：依据新的中心点，重新分配所有的数据点（原来属于绿色中心点的 1 个点，此次迭代后变成属于红色中心点了）。

下图的示例展现了 K -Means 动静迭代收敛的过程：

• 图（a）上有一群散落的点，咱们设定簇数 K =2。

• 图（b）为随机找 2 个点作为核心初始化后，第一次分类的后果。

  • 能够看到，红蓝分界线在这群点的地方穿过。这显然有问题，不过没关系，算法持续往下走。对红蓝两类别离计算它们的核心。
• 图（c）能够看到，一个落在左下方这一团里，另一个落在右上方那一团里。以新的中心点进行第二次分类。
• 图（d）的分界线就根本是曾经能够把两团离开了。
• 图（f）、（g）显示后续反复计算你「中心点 - 分类数据点」的过程曾经收敛，数据点调配根本不动了，聚类实现。

下方的动图能更清晰地展现这个过程：

3.K-Means 毛病与改良

1）K-Means 算法毛病

K-Means 算法简略易用，它有什么毛病呢？咱们将 K -Means 算法的一些毛病总结如下：

• 毛病 1 ：中心点是所有同一类数据点的质心，所以聚类中心点可能不属于数据集的样本点。
• 毛病 2 ：计算间隔时咱们用的是 L2 间隔的平方。对离群点很敏感，噪声（Noisy Data）和离群点（Outlier）会把中心点拉偏，甚至扭转分割线的地位。

2）K-Medoids 算法

针对 K -Means 算法的毛病改良失去了 K -Medoids 算法：

（1）限度聚类中心点必须来自数据点。

• 求中心点的计算方法，由原来的间接计算重心，变成计算完重心后，在重心左近找一个数据点作为新的中心点。
• K-Medoids 重拟合步骤比间接求均匀的 K -Means 要简单一些。

（2）为防止平方计算对离群点的敏感，把平方变成绝对值。

总结来说，K-Medoids 算法的迭代过程与 K -Means 是统一的，不同点如下所示：

• 起始点不是随机点，而是任意抉择数据集中的点。
• 间隔应用 L1 间隔，而不是 L2 间隔。
• 新的中心点，也不是同类所有点的重心，而是同一类别所有数据点中，离其它点最近的点。
• 复杂度方面，相比于 K -Means 的 \(O(n)\)，K-Medoids 更新中心点的复杂度 \(O(n^2)\) 要更高一些。

下图是 K -Means 和 K -Medoids 两个算法的一个零碎比照：

4. 档次聚类算法

相比于 K -Means 这类划分聚类，咱们有另外一类层次化聚类算法。

1）档次聚类 vs 划分聚类

划分聚类失去的是划分清晰的几个类，而档次聚类最初失去的是一个树状层次化构造。

从层次化聚类转换为划分聚类很简略，在层次化聚类的某一层进行切割，就失去 1 个划分聚类。如下图所示：

2）Single-Linkage 算法

接下来咱们介绍一个档次聚类中的 Single-Linkage 算法。这个算法是结构一棵二叉树，用叶节点代表数据，而二叉树的每一个外部节点代表一个聚类。如图所示：

这是一个从下而上的聚类。这棵树是先有叶子，顺着叶子逐步长树枝，树枝越长越大始终到树根。

如果叶子很多，这个成长过程须要合并的类就会很多。图中有 11 个数据点，一共产生了 10 次合并。

3）Complete-Linkage 算法

与 Single-Linkage 算法类似，Complete-Linkage 的迭代思路是一样的，不同的是在合并类时，Single-Linkage 是用两个类中距离最小的两个点作为类之间的间隔，而 Complete-Linkage 恰恰相反，用间隔最远的两个数据点之间的间隔作为这两个类之间的间隔。

这两种计算方法各有利弊。总的来说，档次聚类的计算复杂度是 \(O(n^3)\) 级别，算是很高的了。能够用优先队列的数据结构对算法减速，减速后能减低到 \(O(n^{2} \log{n} )\) 的级别。

5.DB-SCAN 算法

1）DB-SCAN 算法

在后面的内容中咱们介绍了划分聚类和档次聚类的算法，接下来咱们学习另外一个聚类算法：DB-SCAN 算法。

DB-SCAN 是一个基于密度的聚类。如下图中这样不规则状态的点，如果用 K -Means，成果不会很好。而通过 DB-SCAN 就能够很好地把在同一密度区域的点聚在一类中。

2）DB-SCAN 算法的要害概念

外围对象（Core Object），也就是密度达到肯定水平的点。

• 若 \(x_j\) 的 \(\in -\) 邻域至多蕴含 MinPts 个样本，即 \(|N_\in (x_j)|≥MinPts\)，则 \(x_j\) 是一个外围对象。

密度中转（directly density-reachable），密度可达（density-reachable）：外围对象之间能够是密度中转或者密度可达。

• 若 \(x_i\) 位于 \(x_j\) 的 \(\in -\) 邻域中，且 \(x_j\) 是外围对象，则称 \(x_j\) 由 \(x_j\) 密度中转。
• 对 \(x_i\) 与 \(x_j\)，若存在样本序列 \(p_1,p_2, \dots, p_n\)，其中 \(p_1=x_i\)，\(p_n=x_j\) 且 \(p_i+1\) 由 \(p_i\) 密度中转，则称 \(x_j\) 由 \(x_i\) 密度可达。

密度相连（density-connected）：所有密度可达的外围点就形成密度相连。

• 对 \(x_i\) 与 \(x_j\)，若存在 \(x_k\) 使得 \(x_i\) 与 \(x_j\)，均由 \(x_k\) 密度可达，则称 \(x_i\) 与 \(x_j\) 密度相连。

咱们通过下图深刻了解一下方才提到的几个基本概念。

先假如要求的最小点密度 MinPts 是 3。

• 在一个半径范畴内，\(x_1\) 这个点四周的点数是 5，超过了阈值 3，所以 \(x_1\) 是一个外围对象。同样，\(x_2\)、\(x_3\) 和 \(x_4\) 也是外围对象。
• \(x_1\) 与 \(x_2\) 处于一个邻域，所以二者是密度中转的关系，而 \(x_3\) 与 \(x_2\) 也是密度中转的关系，通过 \(x_2\)，\(x_1\) 与 \(x_3\) 是密度可达的关系。
• \(x_3\) 与 \(x_4\) 通过多个外围对象实现密度相连。

3）DB-SCAN 算法伪代码

这个过程用直白的语言形容就是：

• 对于一个数据集，先规定起码点密度 MinPts 和半径范畴。
• 先找出外围对象：如果在半径范畴内点密度大于 MinPts，则这个点是外围对象。把所有的外围对象放到一个汇合中。
• 从这个外围对象汇合中，随机找一个外围对象，判断其它的数据点与它是否密度中转，如果是，则纳入聚类簇中。
• 持续判断其它点与聚类簇中的点是否密度中转，直到把所有的点都查看结束，这时候纳入聚类簇中的所有点是一个密度聚类。

更多无监督学习的算法模型总结能够查看 ShowMeAI 的文章 AI 常识技能速查 | 机器学习 - 无监督学习。

视频教程

能够点击 B 站 查看视频的【双语字幕】版本

https://www.bilibili.com/vide…

【双语字幕 + 材料下载】MIT 6.036 | 机器学习导论(2020·完整版)

https://www.bilibili.com/video/BV1y44y187wN?p=13

ShowMeAI 相干文章举荐

• 1. 机器学习基础知识
• 2. 模型评估办法与准则
• 3.KNN 算法及其利用
• 4. 逻辑回归算法详解
• 5. 奢侈贝叶斯算法详解
• 6. 决策树模型详解
• 7. 随机森林分类模型详解
• 8. 回归树模型详解
• 9.GBDT 模型详解
• 10.XGBoost 模型最全解析
• 11.LightGBM 模型详解
• 12. 反对向量机模型详解
• 13. 聚类算法详解
• 14.PCA 降维算法详解

ShowMeAI 系列教程举荐

• 图解 Python 编程：从入门到精通系列教程
• 图解数据分析：从入门到精通系列教程
• 图解 AI 数学根底：从入门到精通系列教程
• 图解大数据技术：从入门到精通系列教程
• 图解机器学习算法：从入门到精通系列教程