15. 机器学习——聚类

机器学习面试题汇总与解析——聚类

本章讲解知识点

• 1. 什么是聚类
• 2. K-means 聚类算法
• 3. 均值偏移聚类算法
• 4. DBSCAN 聚类算法
• 5. 高斯混合模型（GMM）的期望最大化（EM）聚类
• 6. 层次聚类算法

---

• 本专栏适合于Python已经入门的学生或人士，有一定的编程基础。

• 本专栏适合于算法工程师、机器学习、图像处理求职的学生或人士。

• 本专栏针对面试题答案进行了优化，尽量做到好记、言简意赅。这才是一份面试题总结的正确打开方式。这样才方便背诵

• 如专栏内容有错漏，欢迎在评论区指出或私聊我更改，一起学习，共同进步。

• 相信大家都有着高尚的灵魂，请尊重我的知识产权，未经允许严禁各类机构和个人转载、传阅本专栏的内容。

  
  

• 关于机器学习算法书籍，我强烈推荐一本《百面机器学习算法工程师带你面试》，这个就很类似面经，还有讲解，写得比较好。

• 关于深度学习算法书籍，我强烈推荐一本《解析神经网络——深度学习实践手册》，简称 CNN book，通俗易懂。

• B站机器学习视频：https://space.bilibili.com/10781175/channel/detail?cid=133301

---

1. 什么是聚类

聚类算法是一种无监督学习算法，用于将数据集中的样本划分为若干个组或簇，使得同一组内的样本具有较高的相似度，而不同组之间的样本具有较大的差异。聚类算法在数据分析、模式识别、图像处理等领域具有广泛的应用。

根据样本之间的距离或者说是相似性（亲疏性），把越相似、差异越小的样本聚成一类（簇），最后形成多个簇，使同一个簇内部的样本相似度高，不同簇之间差异性高。

以下是几种常见的聚类算法：

• K-means 聚类算法：K-means 是一种基于距离的聚类算法。它通过迭代的方式将数据集中的样本划分为 K 个簇，每个簇的中心点代表该簇的特征。算法的核心思想是最小化每个样本与所属簇中心点的距离的平方和。

• 层次聚类算法：层次聚类算法将样本逐步合并或分裂，形成一个层次化的聚类结构。该算法可以分为凝聚式聚类和分裂式聚类两种类型。凝聚式聚类从每个样本作为一个独立簇开始，逐步合并相似的簇，直到形成最终的聚类结构。分裂式聚类从一个包含所有样本的簇开始，逐步将簇分裂成更小的子簇，直到满足停止条件。

• DBSCAN 聚类算法：DBSCAN 是一种基于密度的聚类算法。它将样本划分为核心对象、边界对象和噪声对象，并通过样本之间的密度连接来形成簇。DBSCAN 不需要预先指定簇的数量，能够发现任意形状的簇，并对噪声数据具有鲁棒性。

• 密度聚类算法：除了 DBSCAN，还有其他一些基于密度的聚类算法，如 OPTICS 和 MeanShift。这些算法通过测量样本之间的密度来划分簇，能够处理噪声和发现不规则形状的簇。

• 谱聚类算法：谱聚类是一种基于图论的聚类算法。它通过构建数据样本之间的相似度矩阵，并对其进行特征分解，从而将样本划分为不同的簇。谱聚类在处理图结构数据和发现不规则形状的簇方面具有优势。

2. K-means 聚类算法

2.1 K-means 聚类算法三要素

• K 值：要得到的簇的个数

• 质心：每个簇的均值向量，即向量各维取平均即可

• 距离量度：常用欧几里得距离和余弦相似度（先标准化）

欧氏距离（Euclidean Distance）：

公式： $d(x,y)=\sqrt{{\sum }_{i=1}^n(x_i-y_i{)}^2}d(x,\; y)\; =\; \backslash sqrt\{\backslash sum\_\{i=1\}^\{n\}(x\_i\; -\; y\_i)^2\}$

余弦相似度（Cosine Similarity）：

公式： $\text{similarity}(x,y)=\frac{{\sum }_{i=1}^n{x}_i\cdot y_i}{\sqrt{{\sum }_{i=1}^n{x}_i^2}\cdot \sqrt{{\sum }_{i=1}^n{y}_i^2}}\backslash text\{similarity\}(x,\; y)\; =\; \backslash frac\{\backslash sum\_\{i=1\}^\{n\}\; x\_i\; \backslash cdot\; y\_i\}\{\backslash sqrt\{\backslash sum\_\{i=1\}^\{n\}\; x\_i^2\}\; \backslash cdot\; \backslash sqrt\{\backslash sum\_\{i=1\}^\{n\}\; y\_i^2\}\}$

2.2 K-means 基本流程

• 初始化：随机选择 k 个初始聚类中心（centroid）。

• 聚类分配：对于每个样本点，计算其与 k 个聚类中心的距离，将样本点分配到距离最近的聚类中心所对应的簇。

• 更新聚类中心：对于每个簇，计算该簇内样本点的均值，并将均值作为新的聚类中心。

• 重复步骤 2 和步骤 3，直到满足终止条件，例如达到最大迭代次数或聚类中心的变化小于设定阈值。

• 输出最终的聚类结果，每个样本点属于哪个簇。

K-means 的优化目标是最小化样本点与其所属聚类中心之间的平方误差和（SSE）。用下面一组图就可以形象的描述：

上图 a 表达了初始的数据集，假设 k=2。在图 b 中，我们随机选择了两个 k 类所对应的类别质心，即图中的红色质心和蓝色质心，然后分别求样本中所有点到这两个质心的距离，并标记每个样本的类别为和该样本距离最小的质心的类别，如图 c 所示，经过计算样本和红色质心和蓝色质心的距离，我们得到了所有样本点的第一轮迭代后的类别。此时我们对我们当前标记为红色和蓝色的点分别求其新的质心，如图 d 所示，新的红色质心和蓝色质心的位置已经发生了变动。图 e 和图 f 重复了我们在图 c 和图 d 的过程，即将所有点的类别标记为距离最近的质心的类别并求新的质心。最终我们得到的两个类别如图 f。

2.3 K-means 公式推导

K-means 算法使用的是欧式距离来度量样本点之间的相似性，其公式如下：

1.距离计算：对于给定的样本点 $xx$ 和聚类中心 $\mu \mu$，欧式距离的计算公式为：

$d(x,\mu )=\sqrt{{\sum }_{i=1}^n(x_i-{\mu }_i{)}^2}d(x,\; \mu )\; =\; \backslash sqrt\{\backslash sum\_\{i=1\}^\{n\}(x\_i\; -\; \mu \_i)^2\}$

其中， $xx$ 和 $\mu \mu$ 分别表示样本点和聚类中心的特征向量， $nn$ 表示特征的维度。

2.聚类中心更新：在 K-means 算法的迭代过程中，更新聚类中心的公式为计算簇内样本点的均值，即：

${\mu }_k=\frac{1}{\mathrm{\mid }{C}_k\mathrm{\mid }}{\sum }_{x\in C_k}x\mu \_k\; =\; \backslash frac\{1\}\{|C\_k|\}\; \backslash sum\_\{x\; \backslash in\; C\_k\}\; x$

其中， ${\mu }_k\mu \_k$ 表示第 $kk$ 个聚类中心， $C_{k}C\_k$ 表示属于第 $kk$ 个簇的样本点集合， $\mathrm{\mid }{C}_k\mathrm{\mid }|C\_k|$ 表示簇内样本点的数量。

3.K-means 算法的目标是最小化所有样本点与其所属聚类中心之间的平方误差和（SSE），公式如下：

$SSE={\sum }_{k=1}^K{\sum }_{x\in C_k}d(x,{\mu }_k{)}^{2}SSE\; =\; \backslash sum\_\{k=1\}^\{K\}\; \backslash sum\_\{x\; \backslash in\; C\_k\}\; d(x,\; \mu \_k)^2$

其中， $KK$ 表示聚类的簇数， $xx$ 表示样本点， ${\mu }_k\mu \_k$ 表示第 $kk$ 个聚类中心， $C_{k}C\_k$ 表示第 $kk$ 个簇。

通过迭代更新聚类中心和重新分配样本点，K-means 算法寻找使 SSE 最小化的最优聚类结果。

动态描述了以下过程：

2.4 K-means 的优缺点

优点：

• 简单而直观：K-means 算法的原理和实现相对简单，易于理解和实现。
• 可扩展性好：K-means 算法在处理大规模数据集时具有较高的可扩展性，计算速度相对较快。
• 结果可解释性强：K-means 算法得到的聚类结果较为直观，每个样本点都被分配到最近的聚类中心。

缺点：

• 对初始聚类中心敏感：K-means 算法的聚类结果可能会受到初始聚类中心的影响，不同的初始中心可能会导致不同的结果。
• 受离群点影响较大：K-means 算法对离群点敏感，离群点可能会导致聚类结果不准确。
• 需要事先指定簇数K：K-means 算法在运行之前需要指定簇的数量 K，但在实际应用中，选择合适的 K 值并不容易。
• 只适用于凸形簇：K-means 算法假设簇为凸形状，对于非凸形状的簇效果较差。

2.5 K-means 的簇怎么选

kmeans算法其实挺简单，但是聚类个数k应该如何的选择？目前常用有肘部法则和轮廓系数法等。肘部法则通过寻找损失值下降平稳的拐点来确定 k 值，而轮廓系统则是通过寻找轮廓系数的最大值来进行计算

肘部法则 SSE（误差平方和）：

$SSE={\sum }_{k=1}^K{\sum }_{c\in C_k}\mathrm{\mid }p-{\mu }_i{\mathrm{\mid }}^{2}SSE\; =\; \backslash sum\_\{k=1\}^\{K\}\; \backslash sum\_\{c\; \backslash in\; C\_k\}\; |p\; -\; \mu \_i|^2$

k 值与 SSE 的走势关系如下图所示：

很明显，我们选择 K=3（拐点） 最合适，再大精度也没有增加多少。

轮廓系数：

$S_i=\frac{b_i-a_i}{max(a_i,b_i)}S\_i\; =\; \backslash frac\{b\_i-a\_i\}\{max(a\_i,b\_i)\}$

$a_{i}a\_i$ 是样本 i 在同类别内到其它点的平均距离， $b_{i}b\_i$ 是样本 i 到最近不同类别中样本的平均距离

由上图可以看出当 K=3 值轮廓系数达到最大值，此时的聚类效果最好，因此 K 应该选择 3。

3. 均值偏移聚类算法

均值偏移（Mean shift）聚类算法是一种基于滑动窗口（sliding-window）的算法，它试图找到密集的数据点。而且，它还是一种基于中心的算法，它的目标是定位每一组群/类的中心点，通过更新中心点的候选点来实现滑动窗口中的点的平均值。这些候选窗口在后期处理阶段被过滤，以消除几乎重复的部分，形成最后一组中心点及其对应的组。请看下面的图表。

1. 为了解释这一变化，我们将考虑二维空间中的一组点（就像上面的例子）。我们从一个以点 C（随机选择）为中心的圆形滑窗开始，以半径 r 为内核。均值偏移是一种爬山算法（hill climbing algorithm），它需要在每个步骤中反复地将这个内核移动到一个更高的密度区域，直到收敛。

2. 在每一次迭代中，滑动窗口会移向密度较高的区域，将中心点移动到窗口内的点的平均值（因此得名）。滑动窗口中的密度与它内部的点的数量成比例。自然地，通过移向窗口中点的平均值，它将逐渐向更高的点密度方向移动。

3. 我们继续根据均值移动滑动窗口，直到没有方向移动可以容纳内核中的更多点。看看上面的图表;我们一直在移动这个圆，直到我们不再增加密度（也就是窗口中的点数）。

4. 步骤 1 到 3 的过程是用许多滑动窗口完成的，直到所有的点都位于一个窗口内。当多个滑动窗口重叠的时候，包含最多点的窗口会被保留。然后，数据点根据它们所在的滑动窗口聚类。

下面展示了从端到端所有滑动窗口的整个过程的演示。每个黑点代表一个滑动窗口的质心，每个灰色点都是一个数据点。

与 K-Means 聚类相比，均值偏移不需要选择聚类的数量，因为它会自动地发现这一点。这是一个巨大的优势。聚类中心收敛于最大密度点的事实也是非常可取的，因为它非常直观地理解并适合于一种自然数据驱动。缺点是选择窗口大小/半径 r 是非常关键的，所以不能疏忽。

4. DBSCAN 聚类算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法，类似于均值转移聚类算法，但它有几个显著的优点。

1. DBSCAN 以一个从未访问过的任意起始数据点开始。这个点的邻域是用距离 ε（所有在ε距离的点都是邻点）来提取的。

2. 如果在这个邻域中有足够数量的点（根据 minPoints），那么聚类过程就开始了，并且当前的数据点成为新聚类中的第一个点。否则，该点将被标记为噪声（稍后这个噪声点可能会成为聚类的一部分）。在这两种情况下，这一点都被标记为“访问（visited）”。

3. 对于新聚类中的第一个点，其 ε 距离附近的点也会成为同一聚类的一部分。这一过程使在 ε 邻近的所有点都属于同一个聚类，然后重复所有刚刚添加到聚类组的新点。

4. 步骤 2 和步骤 3 的过程将重复，直到聚类中的所有点都被确定，就是说在聚类附近的所有点都已被访问和标记。

5. 一旦我们完成了当前的聚类，就会检索并处理一个新的未访问点，这将导致进一步的聚类或噪声的发现。这个过程不断地重复，直到所有的点被标记为访问。因为在所有的点都被访问过之后，每一个点都被标记为属于一个聚类或者是噪音。

DBSCAN 比其他聚类算法有一些优势。首先，它不需要一个预设定的聚类数量。它还将异常值识别为噪声，而不像均值偏移聚类算法，即使数据点非常不同，它也会将它们放入一个聚类中。此外，它还能很好地找到任意大小和任意形状的聚类。

DBSCAN 的主要缺点是，当聚类具有不同的密度时，它的性能不像其他聚类算法那样好。这是因为当密度变化时，距离阈值 ε 和识别邻近点的 minPoints 的设置会随着聚类的不同而变化。这种缺点也会出现在非常高维的数据中，因为距离阈值 ε 变得难以估计。

5. 高斯混合模型（GMM）的期望最大化（EM）聚类

K-Means 的一个主要缺点是它对聚类中心的平均值的使用很简单幼稚。我们可以通过看下面的图片来了解为什么这不是最好的方法。在左边看起来很明显的是，有两个圆形的聚类，不同的半径以相同的平均值为中心。K-Means 无法处理，因为聚类的均值非常接近。在聚类不是循环的情况下，K-Means 也会失败，这也是使用均值作为聚类中心的结果。

高斯混合模型（GMMs）比 K-Means 更具灵活性。使用高斯混合模型，我们可以假设数据点是高斯分布的;比起说它们是循环的，这是一个不那么严格的假设。这样，我们就有两个参数来描述聚类的形状：平均值和标准差！以二维的例子为例，这意味着聚类可以采用任何形式的椭圆形状（因为在 x 和 y 方向上都有标准差）。因此，每个高斯分布可归属于一个单独的聚类。

为了找到每个聚类的高斯分布的参数（例如平均值和标准差）我们将使用一种叫做期望最大化（EM）的优化算法。看看下面的图表，就可以看到高斯混合模型是被拟合到聚类上的。然后，我们可以继续进行期望的过程——使用高斯混合模型实现最大化聚类。

1. 我们首先选择聚类的数量（如 K-Means 所做的那样），然后随机初始化每个聚类的高斯分布参数。通过快速查看数据，可以尝试为初始参数提供良好的猜测。注意，在上面的图表中可以看到，这并不是 100% 的必要，因为高斯开始时的表现非常不好，但是很快就被优化了。

2. 给定每个聚类的高斯分布，计算每个数据点属于特定聚类的概率。一个点离高斯中心越近，它就越有可能属于那个聚类。这应该是很直观的，因为有一个高斯分布，我们假设大部分的数据都离聚类中心很近。

3. 基于这些概率，我们为高斯分布计算一组新的参数，这样我们就