机器学习笔记——聚类算法（Kmeans、GMM-使用EM优化）

本笔记介绍机器学习中常见的聚类算法（Kmeans、GMM-使用EM优化）。

文章目录

• 聚类
• • K-Means
  • • 工作原理
    • 特点
  • K-Medoids
  • • 工作原理
    • 特点
  • Mini-Batch K-Means
  • • 工作原理
    • 特点
  • K-Means++（重要）
  • • 工作原理
    • 特点
  • 总结
  • K的选值
  • • 1. 肘部法则（Elbow Method）
    • 2. 平均轮廓系数（Silhouette Score）
    • 3. Gap Statistic（间隙统计量）
    • 4. Davies-Bouldin 指数
    • 5. 信息准则（如 BIC/AIC）
    • 总结
  • 高斯混合模型（GMM, Gaussian Mixture Model）
  • • 公式
    • 优势
  • EM算法（Expectation-Maximization Algorithm）
  • • 使用EM训练GMM（进行参数估计）
    • • EM算法的步骤
    • EM算法的特点
    • GMM 和 EM 的关系
  • GMM 与 K-Means 的比较
  • 其他聚类算法
  • • 层次聚类（Hierarchical Clustering）
    • • 1. 凝聚式层次聚类（Agglomerative Hierarchical Clustering）
      • 2. 分裂式层次聚类（Divisive Hierarchical Clustering）
      • 优缺点
    • DBSCAN（Density-Based Spatial Clustering of Applications with Noise）
    • • 核心概念
      • 参数
      • 工作流程
      • 特点
      • 优缺点
      • 参数选择
• 历史文章

聚类

K-Means

K-Means 是一种经典的聚类算法，用于将数据集划分为 K 个簇，每个簇由其质心（簇中心）表示。算法的目标是最小化簇内样本点到质心的平方距离之和，从而使得同一个簇内的样本更加相似。

工作原理

1. 选择初始质心：随机选择 K 个点作为初始质心。
2. 分配样本到最近的质心：将每个样本分配给距离最近的质心，形成 K 个簇。
3. 更新质心：重新计算每个簇的质心，即簇内所有样本的平均值。
4. 重复步骤 2 和 3，直到质心不再变化或达到最大迭代次数。

特点

• 优点：简单易实现，计算速度快，适合大规模数据集。
• 缺点：对初始质心敏感，容易陷入局部最优；K-Means 基于欧氏距离，通常只能处理球形或凸形簇。

K-Medoids

K-Medoids（也称为 PAM，Partitioning Around Medoids）是一种基于原型的聚类算法，与 K-Means 类似，但它选择数据点本身作为质心（称为 Medoid），而不是质心的平均值。

工作原理

1. 选择初始 Medoid：随机选择 K 个数据点作为初始 Medoid。
2. 分配样本到最近的 Medoid：将每个样本分配给距离最近的 Medoid，形成 K 个簇。
3. 更新 Medoid：在每个簇内选择一个新的数据点，使得该点到簇内所有其他点的距离之和最小。
4. 重复步骤 2 和 3，直到 Medoid 不再变化或达到最大迭代次数。

更新 Medoid如何做：

1. 计算每个点的总距离：对于簇内的每个数据点 $x_i$，计算该点到簇内所有其他点的距离之和；
2. 选择距离最小的点：找到使得距离之和最小的那个点作为新的 Medoid。

计算量很大

特点

• 优点：对异常值不敏感（因为选择实际数据点作为 Medoid），适合非球形簇。
• 缺点：计算复杂度高，不适合大规模数据集。

Mini-Batch K-Means

Mini-Batch K-Means 是 K-Means 的一种扩展，旨在提高计算效率和速度。它通过在每次迭代中使用小批量的随机样本来更新质心，而不是使用整个数据集。

工作原理

1. 选择初始质心：随机选择 K 个点作为初始质心。
2. 抽取小批量数据：从数据集中随机抽取一个小批量的数据点。
3. 分配样本到最近的质心：将小批量数据中的每个样本分配给距离最近的质心。
4. 更新质心：根据小批量数据更新质心，而不是全量数据。
5. 重复步骤 2 到 4，直到质心收敛或达到最大迭代次数。

特点

• 优点：计算速度快，内存占用少，适合大规模数据集和在线学习场景。
• 缺点：相较于 K-Means 可能会损失一些精度，质心的更新不如全量数据集的更新精确。

K-Means++（重要）

K-Means++ 是 K-Means 的改进版本，旨在通过改进初始质心的选择来提高聚类效果和算法的稳定性。它能有效减少 K-Means 对初始质心的敏感性问题。

工作原理

1. 选择第一个质心：从数据集中随机选择一个样本点作为第一个质心。
2. 选择下一个质心：选择距离现有质心最远的点作为下一个质心，选择概率与当前最小距离成正比。
3. 重复步骤 2，直到选择出 K 个质心。
4. 按照 K-Means 算法的步骤进行聚类。

特点

• 优点：初始质心选择更好，聚类效果更加稳定，收敛速度更快。
• 缺点：相比 K-Means 增加了一定的计算开销。

总结

• K-Means：随机选择 K 个点作为初始质心。简单高效，适合大多数常见场景，但对初始质心敏感。
• K-Medoids：随机选择 K 个数据点作为初始 Medoid。适合处理含有异常值或非球形分布的聚类问题，但计算复杂度较高。
• Mini-Batch K-Means：随机选择 K 个点作为初始质心，与标准 K-Means 相同。适合大规模数据和在线学习，速度快，但精度较 K-Means 略有下降。
• K-Means++：质心不是一次选出来的，从数据集中随机选择一个样本点作为第一个质心，之后距离现有质心最远的点作为下一个质心。改进了初始质心的选择，收敛速度更快，效果更稳定。

K的选值

在 K-means 聚类算法中，选择合适的 K 值（即簇的数量）是一个重要的步骤。以下是几种常用的选择 K 值的方法：

1. 肘部法则（Elbow Method）

肘部法则是 K-means 中最常用的方法之一，用于通过观察误差下降的速率来选择最佳的 K 值。

• 计算不同 K 值下的 SSE（Sum of Squared Error） 或 簇内误差平方和。SSE 是每个数据点到其所属簇中心的距离平方的总和，反映了簇内的紧密度。
• 将 SSE 对应不同 K 值绘制成曲线，曲线会随着 K 的增加而逐渐下降。
• 曲线会出现一个“肘部”拐点，从此点开始，SSE 的减少幅度明显减小。这个拐点对应的 K 值通常被认为是最佳值，因为此时增加簇的数量已经无法显著降低误差。

优点：

• 简单直观，容易实施。

局限：

• 肘部位置有时不明显，可能会出现多个可能的拐点或不显著的拐点。

2. 平均轮廓系数（Silhouette Score）

轮廓系数是一种度量聚类质量的方法，通过评估数据点在簇内的紧密度和簇间的分离度，来选择最佳的 K 值。

• 对于每个 K 值，计算每个数据点的轮廓系数。轮廓系数的值范围为 [-1, 1]，值越接近 1，说明聚类效果越好。
• 计算每个数据点的轮廓系数后，取其平均值，得到该 K 值下的平均轮廓系数。
• 选择具有最高平均轮廓系数的 K 值，此时簇内紧密度和簇间分离度达到最佳平衡。

优点：

• 不仅考虑簇内紧密度，还考虑簇间分离度，对聚类效果的评价更全面。

局限：

• 计算轮廓系数比肘部法则复杂，需要更多的计算资源，尤其在大数据集上。

3. Gap Statistic（间隙统计量）

间隙统计量方法通过将实际聚类结果与随机分布数据的聚类结果进行对比，选择最佳的 K 值。

• 首先对原始数据进行 K-means 聚类，计算簇内误差平方和。
• 然后生成与原始数据相同维度的随机数据集，重复相同的聚类过程，并计算随机数据的簇内误差平方和。
• 计算原始数据的簇内误差和随机数据的差值，即 Gap 值。
• Gap 值越大，说明聚类结构越显著。选择使 Gap 值最大或首次达到局部最大值的 K 值。

优点：

• 可以有效评估聚类结构是否显著，适用于各种数据分布。

局限：

• 计算量较大，尤其在数据集较大时，需要多次生成随机数据集并重复聚类。

4. Davies-Bouldin 指数

Davies-Bouldin 指数用于评估簇内的紧密度和簇间的分离度，选择较小的 Davies-Bouldin 指数的 K 值。

• 对于每个 K 值，计算所有簇的平均距离（紧密度）以及簇之间的距离（分离度）。
• Davies-Bouldin 指数越小，表示簇内紧密、簇间分离，聚类效果越好。
• 选择 Davies-Bouldin 指数最小的 K 值。

优点：

• 简单有效，适合较小的数据集。

局限：

• 对数据分布敏感，某些分布下可能不适用。

5. 信息准则（如 BIC/AIC）

在一些统计方法中，可以使用信息准则来选择 K 值，尤其是结合高斯混合模型（GMM）时。

• 计算不同 K 值下的 AIC（Akaike 信息准则）或 BIC（贝叶斯信息准则）。
• AIC 和 BIC 的值越小，模型的解释性越强。
• 选择最小 AIC 或 BIC 值对应的 K 值。

优点：

• 适用于高斯分布假设下的聚类模型（如 GMM）。

局限：

• 适用于较小的高斯混合数据，不适用于所有 K-means 场景。

总结

• 肘部法则：最常用，适合快速估计 K 值。
• 轮廓系数：对聚类质量评估更全面，适合复杂数据集。
• Gap Statistic：适合验证聚类是否显著。
• Davies-Bouldin 指数：通过簇内紧密度和簇间分离度选择 K。
• AIC/BIC：适合与高斯混合模型（GMM）结合使用。

每种方法有其优缺点，可以根据具体的应用场景和数据特点选择合适的 K 值选择方法。

高斯混合模型（GMM, Gaussian Mixture Model）

用于聚类和概率密度估计的模型，它假设数据由多个高斯分布加权组合混合而成。GMM 能够比 K-Means 更灵活地表示数据，它允许每个簇具有不同的大小、形状和方向。

公式

$$p(x)=\sum _{k=1}^K{\pi }_k\cdot \mathcal{N}(x\mid {\mu }_k,{\Sigma }_k)$$
其中：

• $K$：簇的数量，即高斯分布的数量。
• ${\pi }_k$：第 $k$ 个高斯分布的混合系数，表示该簇占总数据的比例，且 ${\sum }_{k=1}^K{\pi }_k=1$。
• $\mathcal{N}(x\mid {\mu }_k,{\Sigma }_k)$：第 $k$ 个高斯分布，具有均值 ${\mu }_k$ 和协方差矩阵 ${\Sigma }_k$。

该模型假设数据点 $x$ 是从 $K$ 个高斯分布的加权和中采样得到的，其中每个高斯分布的权重由 ${\pi }_k$ 决定。

优势

• 能够表示数据集中的复杂分布，包括不同形状和大小的簇。
• 每个簇由高斯分布表示，而非简单的球形聚类。
• 适合处理数据具有重叠或不规则形状的聚类问题。

EM算法（Expectation-Maximization Algorithm）

EM算法是一种迭代优化算法，GMM 的参数估计通常使用期望最大化（EM）算法。它被广泛用于训练像 GMM 这样的概率模型。EM 算法包含两个主要步骤：期望步骤（E 步）和最大化步骤（M 步）。

使用EM训练GMM（进行参数估计）

EM算法的步骤

1. 初始化：

• 随机初始化每个高斯分布的均值 ${\mu }_k$、协方差 ${\Sigma }_k$ 和混合系数 ${\pi }_k$。
• 初始化可以通过随机选取数据点或使用 K-Means 聚类结果来设置初始值。

随机初始化模型参数（如 GMM 中的混合系数、均值和协方差矩阵）。

2. E 步（Expectation Step）：

• 计算每个数据点属于每个高斯分布(簇)的后验概率(责任度)，表示数据点由每个分量生成的概率。

• 计算公式：
  $$r_{ik}=\frac{{\pi }_k\cdot \mathcal{N}(x_i\mid {\mu }_k,{\Sigma }_k)}{{\sum }_{j=1}^K{\pi }_j\cdot \mathcal{N}(x_i\mid {\mu }_j,{\Sigma }_j)}$$

  其中 $r_{ik}$ 表示数据点 $x_i$ 属于簇 $k$ 的概率。

“责任度”是期望隐变量的条件概率，不是直接计算“期望”。

隐变量是模型中不可观测的变量（隐藏的结构或类别）。
在 EM 算法中，隐变量通常是表示每个数据点由哪个潜在类别或簇生成的。

3. M 步（Maximization Step）：

利用 E 步计算得到的隐变量期望值（责任度） $r_{ik}$ 来更新参数 ${\pi }_k$、${\mu }_k$ 和 ${\Sigma }_k$。最大化当前参数的似然函数，更新模型的参数。这一步的目标是优化模型参数，使得当前模型对数据的拟合更好。

(1). 更新混合系数 ${\pi }_k$

混合系数 ${\pi }_k$ 表示簇 $k$ 所占的比例，可以通过责任值的总和归一化来计算：

$${\pi }_k=\frac{{\sum }_{i=1}^N{r}_{ik}}{N}$$

其中：

• $N$ 是数据点的总数。
• ${\sum }_{i=1}^N{r}_{ik}$ 表示簇 $k$ 对所有数据点的责任度总和，即簇 $k$ 中有效的数据点数量。

(2). 更新均值 ${\mu }_k$

簇 $k$ 的均值 ${\mu }_k$ 更新为所有数据点 $x_i$ 的加权平均值，权重为责任度 $r_{ik}$：

$${\mu }_k=\frac{{\sum }_{i=1}^N{r}_{ik}\cdot x_i}{{\sum }_{i=1}^N{r}_{ik}}$$

这里：

• $r_{ik}\cdot x_i$ 表示数据点 $x_i$ 对均值 ${\mu }_k$ 的贡献，按责任度加权。
• 分母 ${\sum }_{i=1}^N{r}_{ik}$ 是簇 $k$ 中有效的数据点数量，确保均值为责任加权的结果。

(3). 更新协方差矩阵 ${\Sigma }_k$

协方差矩阵 ${\Sigma }_k$ 表示簇 $k$ 的数据分布形状和大小。协方差矩阵更新为所有数据点的加权方差，其中权重为责任度 $r_{ik}$：

$${\Sigma }_k=\frac{{\sum }_{i=1}^N{r}_{ik}\cdot (x_i-{\mu }_k)(x_i-{\mu }_k{)}^T}{{\sum }_{i=1}^N{r}_{ik}}$$

这里：

• $(x_i-{\mu }_k)(x_i-{\mu }_k{)}^T$ 表示数据点 $x_i$ 与均值 ${\mu }_k$ 的偏差。
• $r_{ik}\cdot (x_i-{\mu }_k)(x_i-{\mu }_k{)}^T$ 是数据点 $x_i$ 对协方差的贡献，按责任度加权。
• 分母 ${\sum }_{i=1}^N{r}_{ik}$ 是簇 $k$ 的有效数据点数量。

5. 重复 E 步和 M 步，直到参数收敛或达到最大迭代次数。

EM算法的特点

• 适用性广：可用于解决许多存在隐变量或缺失数据的优化问题，如 GMM 训练、因子分析、HMM 等。
• 收敛性：EM 算法每次迭代都会使似然函数单调增加，但可能收敛到局部最优解。
• 对初始值敏感：不同的初始值可能导致不同的收敛结果。

GMM 和 EM 的关系

• GMM 是模型，EM 是优化算法：GMM 是一种模型，用于表示数据的概率分布，而 EM 是一种优化算法，用于最大化 GMM 的似然函数。
• EM 训练 GMM：通过 EM 算法，GMM 能够在给定数据的情况下找到最优参数，包括每个高斯分布的均值、协方差和混合系数。

GMM 与 K-Means 的比较

其他聚类算法

层次聚类（Hierarchical Clustering）

层次聚类是一种构建层次结构的聚类算法，可以生成一棵聚类树（又称为树状图，dendrogram），并在不同层次的分组中展现数据的聚类结构。层次聚类可以分为两类方法：凝聚式（自底向上）和分裂式（自顶向下）。

1. 凝聚式层次聚类（Agglomerative Hierarchical Clustering）

在凝聚式层次聚类中，每个数据点从一开始被当作一个单独的簇，不断将相近的簇合并，直到达到预定的簇数量或合并距离超出阈值。

过程：

• 初始化：每个数据点作为一个簇。
• 迭代：计算所有簇之间的距离，将距离最小的两个簇合并为一个簇。
• 重复上述步骤，直到只剩下一个簇或达到设定的停止条件。

常用的距离度量方法：

• 单链接：计算两个簇之间最近的点的距离。
• 全链接：计算两个簇之间最远的点的距离。
• 平均链接：计算两个簇之间所有点对距离的平均值。
• 中心链接：计算两个簇中心点之间的距离。

2. 分裂式层次聚类（Divisive Hierarchical Clustering）

分裂式层次聚类从一个包含所有数据点的大簇开始，然后逐步将每个簇分裂为较小的簇，直到每个簇包含单个数据点或达到停止条件。

过程：

• 初始化：将所有数据点放入一个簇。
• 迭代：选择一个簇，将其分裂为两个子簇（通常基于聚类算法如 K-means）。
• 重复上述步骤，直到满足终止条件。

优缺点

• 优点：层次聚类不需要预设簇的数量，并且生成的树状图可以帮助我们理解数据的层次结构。
• 缺点：计算复杂度高，尤其是对大数据集，时间和空间开销较大；不同的距离度量方法会影响聚类结果。

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）

DBSCAN 是一种基于密度的聚类算法，它将数据点分为高密度区域的簇和低密度区域的噪声点。DBSCAN 可以发现任意形状的簇，并且能够自动检测噪声点。它适合用于空间分布不均匀的聚类任务。

核心概念

1. 核心点（Core Point）：在给定半径 $ϵ$ 内包含至少 MinPts 个邻居的点。
2. 边界点（Border Point）：在 $ϵ$ 半径内邻居数小于 MinPts 的点，但至少和一个核心点邻接。
3. 噪声点（Noise Point）：既不是核心点也不是边界点的点，通常被视为孤立点或噪声。

参数

• $ϵ$（半径）：用于确定邻域的半径。
• MinPts：在 $ϵ$ 邻域内点的最小数量，用于定义核心点。

工作流程

1. 选择一个未访问的数据点：
   • 如果该点是核心点，从该点开始扩展一个新簇，将它和其密度可达的点全部加入该簇。
   • 如果该点是边界点，则标记为边界点，并与已有簇的核心点连接。
   • 如果是噪声点，则将其标记为噪声，放弃该点。
2. 扩展簇：
   • 对于每个核心点，通过密度连接的方式，将所有密度可达的点加入同一簇。
3. 迭代：
   • 重复上述步骤，直到所有点都被访问过。

特点

• 密度可达：如果一个点能够通过一系列的核心点连接到另一个点，则称这两个点密度可达。
• 噪声检测：DBSCAN 能够有效检测出数据中的噪声点。
• 簇的任意形状：DBSCAN 适合发现任意形状的簇，特别是非球形的簇结构。

优缺点

• 优点：
  • 不需要预设簇的数量。
  • 能处理不同密度的簇，适合任意形状的聚类。
  • 能有效检测噪声点。
• 缺点：
  • 参数 $ϵ$ 和 MinPts 的选择较敏感。
  • 不适合检测簇密度差异较大的数据集。
  • 对高维数据表现较差，因为在高维空间很难定义合理的密度。

参数选择

DBSCAN 中的参数选择对结果有较大影响，常用方法如下：

• 通过 K-距离图（K-distance graph）选择 $ϵ$：计算每个点到其 K 个最近邻的距离，然后对这些距离排序。当图中有明显拐点时，拐点的距离即为 $ϵ$ 的值。
• MinPts 的选择：通常取 2 倍于数据的维度大小，例如在二维数据中可以取 MinPts = 4。

历史文章

本系列其他相关笔记参考如下：
机器学习笔记——损失函数、代价函数和KL散度
机器学习笔记——特征工程、正则化、强化学习
机器学习笔记——30种常见机器学习算法简要汇总
机器学习笔记——感知机、多层感知机(MLP)、支持向量机(SVM)
机器学习笔记——KNN（K-Nearest Neighbors，K 近邻算法）
机器学习笔记——朴素贝叶斯算法
机器学习笔记——决策树
机器学习笔记——集成学习、Bagging（随机森林）、Boosting（AdaBoost、GBDT、XGBoost、LightGBM）、Stacking
机器学习笔记——Boosting中常用算法（GBDT、XGBoost、LightGBM）迭代路径