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. 为了解释这一变