跳转至

聚类算法｜K-means⚓︎

约 1070 个字 预计阅读时间 4 分钟 总阅读量 次

算法解决的问题⚓︎

K-means算法解决的是无监督聚类问题，具体来说：

  • 输入：\(n\) 个 \(m\) 维数据点 \(\{x_1, x_2, ..., x_n\}\)，以及预设的聚类数量 \(k\)
  • 目标：将这 \(n\) 个数据点划分成 \(k\) 个簇，使得同一簇内的数据点尽可能相似，不同簇之间的数据点尽可能不同
  • 优化目标：最小化簇内平方和（Within-Cluster Sum of Squares, WCSS）：
\[J = \sum_{i=1}^{k} \sum_{x \in C_i} ||x - \mu_i||^2\]

其中 \(C_i\) 是第 \(i\) 个簇，\(\mu_i\) 是第 \(i\) 个簇的中心点（质心）。

算法主要流程⚓︎

K-means算法采用迭代优化的方式，主要包含以下步骤：

1. 初始化阶段⚓︎

  • 随机选择 \(k\) 个数据点作为初始聚类中心 \(\{\mu_1^{(0)}, \mu_2^{(0)}, ..., \mu_k^{(0)}\}\)
  • 或使用K-means++等更智能的初始化方法

2. 迭代优化阶段⚓︎

重复执行以下两个步骤直到收敛：

步骤1：分配（Assignment） - 对每个数据点 \(x_i\)，计算它到各个聚类中心的距离 - 将 \(x_i\) 分配给距离最近的聚类中心：

\[c_i = \arg\min_{j} ||x_i - \mu_j||^2\]

步骤2：更新（Update） - 重新计算每个簇的质心：

\[\mu_j^{(t+1)} = \frac{1}{|C_j|} \sum_{x_i \in C_j} x_i\]

3. 收敛条件⚓︎

  • 质心不再发生变化：\(||\mu_j^{(t+1)} - \mu_j^{(t)}|| < \epsilon\)
  • 或达到最大迭代次数
  • 或目标函数J的变化小于阈值

算法复杂度分析⚓︎

时间复杂度⚓︎

  • 单次迭代：\(O(nkm)\)
  • \(n\)：数据点数量
  • \(k\)：聚类数量
  • \(m\)：特征维度
  • 总时间复杂度：\(O(nkmt)\)
  • \(t\)：迭代次数（通常为常数）

空间复杂度⚓︎

  • 数据存储：\(O(nm)\)
  • 聚类中心：\(O(km)\)
  • 总空间复杂度：\(O(nm + km)\)

算法特点与局限性⚓︎

优点⚓︎

  1. 简单高效：算法逻辑清晰，实现简单
  2. 可扩展性好：适用于大规模数据
  3. 收敛性保证：目标函数单调递减，保证收敛

缺点⚓︎

  1. 需要预设k值：聚类数量需要事先指定
  2. 对初始值敏感：不同初始化可能得到不同结果
  3. 假设簇为球形：对非凸形状的簇效果不佳
  4. 对噪声和异常值敏感：质心容易被极值影响

聚类 vs 分类的区别⚓︎

本质区别⚓︎

维度 聚类（Clustering） 分类（Classification）
学习类型 无监督学习 监督学习
数据要求 只有特征数据，无标签 需要带标签的训练数据
目标 发现数据的内在结构和模式 学习特征到标签的映射关系

具体差异⚓︎

维度 聚类（Clustering） 分类（Classification）
数据输入 \(\{x_1, x_2, ..., x_n\}\)（只有特征） \(\{(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)\}\)（特征+标签）
问题性质 探索性数据分析，寻找隐藏的数据结构 预测性任务，对新样本进行标签预测
评估方式 轮廓系数、簇内紧密度、簇间分离度等内在指标 准确率、精确率、召回率、F1分数等外在指标
应用场景 用户画像、市场细分、数据预处理、异常检测 垃圾邮件识别、图像识别、疾病诊断、情感分析
结果解释 类别含义需要人工解释和命名 类别含义在训练时已明确定义

总的来说，聚类是"让数据告诉我们有哪些类别"，而分类是"根据已知类别来预测新数据的归属"。

如何选择合适的 K 值?⚓︎

这是 K-means 的一个经典问题，因为 K 值的选择直接决定了聚类的结果。在实践中，我们通常没有一个“唯一正确”的答案，而是通过一些启发式的评估方法来辅助决策。

1. 手肘法 (Elbow Method)⚓︎

这是最常用也是最直观的方法。

  • 核心思想：通过绘制不同 K 值对应的簇内平方和 (WCSS) 曲线，寻找一个“手肘”点。WCSS 就是 K-means 的目标函数 \(J\)。
  • 操作流程：
    1. 尝试一系列的 K 值（例如，从 2 到 10）。
    2. 对于每一个 K 值，运行 K-means 算法，并计算最终的 WCSS。
    3. 将 K 值作为横坐标，WCSS 作为纵坐标，绘制折线图。

  • 如何判断：理论上，随着 K 值的增大，每个簇会变得更小更紧凑，所以 WCSS 会不断减小。我们寻找的是这样一个点：当 K 值越过它之后，WCSS 的下降速度急剧减缓，形成一个类似手臂手肘的拐点。这个拐点就被认为是性价比最高的 K 值。

  • 优点：直观、简单、易于实现。

  • 缺点：拐点有时并不明显，可能存在多个“手肘”，主观性较强。

2. 轮廓系数法 (Silhouette Score)⚓︎

这是一种更具数学依据的方法，它同时考虑了簇的内聚性 (cohesion) 和分离度 (separation)。

  • 核心思想：计算每个样本的轮廓系数，一个好的聚类结果应该是簇内紧密、簇间疏远。
  • 操作流程：
    1. 对于单个样本点 \(x_i\)：
      • 计算它与同一簇内所有其他点的平均距离，记为 \(a(i)\)（内聚性）。
      • 计算它与最近的邻簇中所有点的平均距离，记为 \(b(i)\)（分离度）。
      • 样本 \(x_i\) 的轮廓系数为：\(s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}}\)
    2. 整个数据集的轮廓系数是所有样本轮廓系数的平均值。

  • 如何判断：

    • 轮廓系数的取值范围是 [-1, 1]。
    • 值越接近 1，表示聚类效果越好。
    • 值接近 0，表示簇与簇之间有重叠。
    • 值为负，表示样本可能被分到了错误的簇。
    • 我们可以计算不同 K 值对应的平均轮廓系数，并选择使该系数最大化的 K 值。

  • 优点：度量更全面，结果比手肘法更具说服力。

  • 缺点：计算复杂度较高，为 \(O(n^2)\)。

K-means 的改进⚓︎

K-means++：针对初始化敏感问题⚓︎

这是解决“对初始值敏感”最经典、最有效的方法，也是 scikit-learn 等库中的默认初始化策略。

  • 核心思想：在选择初始聚类中心时，不再完全随机，而是让它们之间尽可能地相互远离。

  • 算法流程：

    1. 从数据集中随机选择一个点作为第一个聚类中心 \(\mu_1\)。
    2. 对于数据集中的每一个点 \(x_i\)，计算它与当前已选出的所有聚类中心的最短距离，记为 \(D(x_i)^2\)。
    3. 选择下一个聚类中心 \(\mu_{j}\)：将 \(D(x_i)^2\) 作为一个权重，进行轮盘赌选择。\(D(x_i)^2\) 越大的点，越有可能被选为下一个中心点。
    4. 重复步骤 2 和 3，直到选出 \(k\) 个聚类中心。

  • 优点：通过这种方式，初始化的中心点倾向于分散在整个数据空间，从而能得到更好的聚类结果，并加速收敛。

Mini-Batch K-means：针对大数据量和可扩展性：⚓︎

当数据量巨大（例如，无法一次性读入内存）时，标准 K-means 的每次迭代都需要遍历所有数据，效率低下。Mini-Batch K-means 就是为此而生。

  • 核心思想：在每次迭代中，不使用全部数据，而是随机抽取一小部分数据（一个 "mini-batch"）来更新质心。

  • 算法流程：

    1. 随机初始化 \(k\) 个聚类中心。
    2. 重复迭代直到收敛： a. 从数据集中随机抽取一个 mini-batch。 b. 分配：将这个 mini-batch 中的点分配给最近的质心。 c. 更新：根据这个 mini-batch 中的点，以加权平均的方式（考虑历史更新）来更新受影响的质心。

  • 优点：大大减少了计算时间，降低了内存需求。

  • 缺点：聚类结果的精度会略有下降，因为每次更新都是基于数据的局部估计。

3. 针对非球形簇和异常值：其他聚类算法⚓︎

K-means 的一个根本性假设是簇呈凸状或球形，并且对异常值敏感。当数据不满足这些假设时，我们应该考虑使用其他算法。

  • K-Medoids (PAM)：为了解决对异常值敏感的问题。它不使用簇的均值（mean）作为中心，而是使用簇中真实存在的一个点（medoid）作为中心。因为中心点必须是真实样本，它对异常值的鲁棒性更强。
  • DBSCAN：基于密度的聚类算法。它能发现任意形状的簇，并且能自动将噪声/异常点识别出来，也无需预设 K 值。
  • 谱聚类 (Spectral Clustering)：它将聚类问题转化为图分割问题。通过构建数据的相似度图，并在拉普拉斯矩阵上进行降维，最后在降维后的空间中做 K-means。它对于处理非凸形状的簇（如两个弯月）效果非常好。

DBSCAN 算法⚓︎

DBSCAN。同样是一个==非常经典且重要的无监督学习的聚类算法==。

1. 解决的问题与核心思想⚓︎

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 是一种基于密度的聚类算法。它解决的核心问题是 K-means 等算法无法处理的场景：

  1. 发现任意形状的簇 ：K-means 假设簇是球形（或凸形）的，因为它基于最小化到质心的距离。DBSCAN 则可以发现非凸的、奇形怪状的簇，例如弯月形、环形等。
  2. 自动识别噪声/异常点：K-means 会将每一个数据点都强制分配到一个簇中，这使得它对异常值非常敏感。DBSCAN 则能明确地将那些不属于任何高密度区域的点识别为噪声。
  3. 无需预设聚类数量 K：与 K-means 不同，你不需要告诉 DBSCAN 要找几个簇，它会根据数据的密度分布自动确定簇的数量。

核心思想：一个簇可以被定义为由“足够密集”的点所组成的区域。算法通过评估每个点周围的“邻居”数量来判断该点是否属于一个密集区域，并由此将密集区域连接起来形成簇。

2. DBSCAN 与 K-means 的核心区别⚓︎

如果你理解了这张表格，你就掌握了这两个算法的本质区别。

特性 K-means DBSCAN
基础思想 基于距离（到质心的距离） 基于密度（邻域内的点数）
簇的形状 假设为球形或凸形 可以是任意形状
聚类数量 k 需要预先指定 (输入) 自动发现 (输出)
噪声处理 将所有点都分配到簇中，对噪声敏感 能自动识别并标记噪声点，鲁棒性强
核心参数 聚类数 k 半径 Eps 和 最小点数 MinPts
算法结果 非确定性（依赖随机初始化） 确定性（对于边界点归属可能略有不同）
适用场景 簇结构简单、呈球形、无太多噪声 簇结构复杂、形状不规则、含噪声

3. 算法流程详解⚓︎

在了解流程之前，必须先定义 DBSCAN 的三个核心概念：

  • Eps (ε)：邻域半径。这是一个距离阈值。对于一个给定的点，所有与它距离小于或等于 Eps 的点都被认为是它的“邻居”。
  • MinPts：最小点数。这是一个数量阈值。一个点要成为“核心点”，其 Eps 邻域内必须至少包含 MinPts 个点（包括它自己）。
  • 点的类型：
    • 核心点 (Core Point)：在其 Eps 邻域内至少有 MinPts 个点的点。它们是簇的“心脏”。
    • 边界点 (Border Point)：它不是核心点，但它是某个核心点的邻居。它们是簇的“边缘”。
    • 噪声点 (Noise Point/Outlier)：既不是核心点，也不是边界点的点。它们是离群的、稀疏的点。

算法流程（可以想象成一个“病毒传播”的过程）：

  1. 初始化：将所有数据点标记为“未访问”。
  2. 遍历：从数据集中随机选择一个未访问的点 P，开始检查。
  3. 邻域检查：
  4. 标记 P 为“已访问”。
  5. 找出 P 在 Eps 半径内的所有邻居。
  6. 情况 A：P 不是核心点 (邻居数 < MinPts)
    • 暂时将 P 标记为“噪声点”。（注意：它之后可能会被其他核心点“收编”为边界点）。
    • 回到第2步，选择下一个未访问的点。
  7. 情况 B：P 是核心点 (邻居数 \(\geq\) MinPts)
    • 创建一个新簇。将 P 分配到这个新簇。
    • 将 P 的所有邻居放入一个待处理队列（"种子集合"）。
    • 扩展簇（关键步骤）： a. 从队列中取出一个点 Q。 b. 如果 Q 曾被标记为“噪声”，则将其“收编”并分配到当前簇中（Q 成为一个边界点）。 c. 如果 Q 是“未访问”的： - 标记 Q 为“已访问”，并将其分配到当前簇中。 - 找出 Q 的所有邻居。 - 如果 Q 本身也是一个核心点，则将它所有新的、未访问过的邻居也加入到待处理队列中。这个过程不断地将密度相连的区域“传染”并扩张，直到队列为空。
  8. 循环：重复第 2、3 步，直到所有点都被访问过。
  9. 完成：所有被分配到簇的点构成了聚类结果，剩下被标记为“噪声”的点就是最终的噪声点。

4. 算法复杂度分析⚓︎

假设有 \(n\) 个样本，每个样本 \(m\) 维。

  • 朴素实现 (Naive Implementation)：

    • 算法的核心是对每个点进行邻域查询。
    • 对于一个点，查询其 Eps 邻域需要计算它与所有其他 \(n-1\) 个点的距离。
    • 由于我们需要对所有 \(n\) 个点都执行这个操作，总的时间复杂度为 \(\mathbf{O(n^2)}\)。

  • 使用空间索引优化 (Optimized Implementation)：

    • \(O(n^2)\) 的复杂度在大数据集上是不可接受的。
    • 现代的 DBSCAN 实现会使用空间索引数据结构（如 k-d树 或 R树）来加速邻域查询。
    • 这些数据结构可以将一次邻域查询的平均时间复杂度从 \(O(n)\) 降低到 \(\mathbf{O(\log n)}\)。
    • 因此，对于所有 \(n\) 个点，总的时间复杂度被优化为 \(\mathbf{O(n \log n)}\)。这是面试中更标准的答案。

主要开销在于存储数据本身，即 \(\mathbf{O(nm)}\)。

如果使用了空间索引（如 k-d 树），索引本身也需要大约 \(O(n)\) 的空间来存储。

算法运行期间，需要一个队列来存储待扩展的点，最坏情况下可能需要 \(O(n)\) 的空间。

综合来看，总的空间复杂度主要是由数据和索引决定的，可以认为是 \(\mathbf{O(nm)}\) 或 \(O(nm + n)\)。

5. 超参数选择⚓︎

DBSCAN 不会自动运行，它绝对需要手动设定超参数。 就是提到的 Eps (ε) 和 MinPts。

MinPts (最小点数) 的选择⚓︎

MinPts 相对来说没有 Eps 那么敏感，通常我们可以根据经验和数据维度来设定一个初始值。

  • 含义：它定义了构成一个“密集区域”所需的最小样本数量。它在某种程度上也决定了算法对噪声的容忍度。

  • 选择原则/经验法则：

    1. 基本原则：MinPts 至少为 3。如果 MinPts=1，每个点都是一个簇；如果 MinPts=2，结果类似于基于距离的层级聚类，对噪声非常敏感。
    2. 与维度相关：一个常用的经验法则是 MinPts >= m + 1，其中 m 是数据的特征维度。另一个更宽松的建议是 MinPts >= 2 * m。

    原因：在高维空间中，数据点会变得越来越稀疏（维度灾难），因此需要更多的点才能证明一个区域是“密集”的。

    1. 实践建议：
      • 对于二维数据，MinPts 通常取 4 是一个很好的起点。
      • 对于更高维或更嘈杂的数据，可以适当增大 MinPts。
      • 通常，我们会先固定一个合理的 MinPts 值，然后专注于寻找最佳的 Eps。

Eps (邻域半径) 的选择⚓︎

Eps 是更敏感、更难设置的参数。它的选择通常需要借助数据自身的分布来确定。最经典和有效的方法是K-距离图 (k-distance plot)。

  • 含义：它定义了“邻域”的大小。如果 Eps 太小，大部分点都会因为邻居太少而被当作噪声；如果 Eps太大，多个不同的簇可能会被合并成一个大簇。
  • 使用 K-距离图来确定 Eps：
    1. 设定 k 值：首先，设定一个 k 值。这个 k 通常就等于我们前面选择的 MinPts 值。
    2. 计算 k-距离：对于数据集中的每一个点，计算它到其第 k 个最近邻的距离。我们将这个距离称为该点的“k-距离”。
    3. 绘制图形：将所有点的 k-距离从大到小排序（或者从小到大，效果一样），然后绘制一张图：
      • Y 轴：排序后的 k-距离值。
      • X 轴：数据点的索引（从 1 到 n）。
    4. 寻找拐点 (Elbow/Knee)：
      • 在这张图上，我们寻找一个“拐点”或“膝盖点”。这个点是曲线斜率发生急剧变化的位置。
      • 拐点前的点：曲线比较平缓，代表那些处于密集区域（核心点）的点，它们的 k-近邻距离都很小。
      • 拐点后的点：曲线急剧上升，代表那些处于稀疏区域（噪声点）的点，它们的 k-近邻距离非常大。
      • 拐点本身：这个点对应的 k-距离值，就是一个非常理想的 Eps 候选值。它代表了一个能有效区分核心点和噪声点的距离阈值。

下图是一个典型的 K-距离图示例 (k = 4)：

  k-distance |
             |
             |                      /
             |                     /
             |                    /
     Eps ->  | . . . . . . . . . + <-- 拐点 (Elbow/Knee)
             | _______________ /
             |/
             +------------------------------------->
                  Points sorted by distance

在实践中，为 DBSCAN 选择超参数的推荐工作流程是：

  1. 确定 MinPts：根据数据维度 m 和对噪声的预期，选择一个合适的 MinPts 值（例如 MinPts = 2 * m）。
  2. 绘制 K-距离图：使用上一步确定的 MinPts 值作为 k，计算并绘制 K-距离图。
  3. 确定 Eps：从 K-距离图中找到拐点，并将该点对应的距离值作为 Eps。
  4. 运行并评估：使用找到的 (Eps, MinPts) 运行 DBSCAN，并根据可视化结果或领域知识评估聚类效果。如果不理想，可以微调 MinPts 并重复此过程。