聚类方法

1. 问题背景与定位

之前，我们明确了聚类的目标：将数据集划分为若干个内部相似、外部相异的簇。这个定义中，“相似”与“相异”是核心概念，但它们本身是定性的。要让计算机执行聚类任务，我们必须首先将这一概念定量化。

因此，在讨论任何具体的聚类算法之前，我们必须回答一个根本问题：

如何用数学语言精确地测量两个数据样本点之间的相似或不相似程度？

这个问题的答案，就是本文的第一部分——距离度量 (Distance Metrics)。一旦定义了点与点之间的距离，下一个自然的问题就是如何定义簇与簇之间的距离，这正是层次聚类算法需要解决的核心。

2. 相似度与距离度量

在聚类分析中，我们通常使用距离来度量样本间的不相似性。距离越小，代表样本越相似；距离越大，代表样本越不相似。

2.1 距离度量的数学定义

在数学上，一个定义在集合 $X$ 上的函数 $d : X \times X \to R$ 如果被称为一个距离或度量 (Metric)，它必须满足以下四个基本性质（对于任意 $x, y, z \in X$ ）：

非负性 (Non-negativity): $d (x, y) \geq 0$
同一性 (Identity of indiscernibles): $d (x, y) = 0 ⟺ x = y$
对称性 (Symmetry): $d (x, y) = d (y, x)$
三角不等式 (Triangle inequality): $d (x, z) \leq d (x, y) + d (y, z)$

满足这些性质的距离保证了度量空间的良好结构，是大多数经典聚类算法的基础。

2.2 常用距离度量

假设我们有两个 $d$ 维数据样本 $x_{i} = (x_{i 1}, x_{i 2}, \dots, x_{i d})^{T}$ 和 $x_{j} = (x_{j 1}, x_{j 2}, \dots, x_{j d})^{T}$ 。

2.2.1 闵可夫斯基距离

这是一个广义的距离定义，许多其他距离都是它的特例。

d (x_{i}, x_{j}) = (k = 1 \sum d ∣ x_{ik} - x_{jk} ∣^{p})^{1/ p}

这个公式也被称为 $L_{p}$ 范数 ( $∣∣ x_{i} - x_{j} ∣ ∣_{p}$ )。通过改变参数 $p$ ( $p \geq 1$ )，我们可以得到不同的距离。

欧几里得距离 (Euclidean Distance, $p = 2$ ) 这是最常用、最直观的距离，即两点间的直线距离。
$d_{E u c} (x_{i}, x_{j}) = k = 1 \sum d (x_{ik} - x_{jk})^{2} = ∣∣ x_{i} - x_{j} ∣ ∣_{2}$
应用: 适用于数据分布较为均匀、各个维度尺度相似的场景。
曼哈顿距离 (Manhattan Distance, $p = 1$ ) 也称为城市街区距离，它计算的是两点在标准坐标系上各轴坐标差的绝对值总和。
$d_{M an} (x_{i}, x_{j}) = k = 1 \sum d ∣ x_{ik} - x_{jk} ∣ = ∣∣ x_{i} - x_{j} ∣ ∣_{1}$
应用: 当数据在不同维度上的度量单位不同，或存在较多离群值时，曼哈顿距离的鲁棒性通常优于欧氏距离。

2.2.2 余弦相似度与余弦距离 (Cosine Similarity & Distance)

余弦相似度衡量的是两个向量在方向上的差异，而非大小上的差异。它计算的是两个向量的夹角的余弦值。

sim_{cos} (x_{i}, x_{j}) = \frac{x _{i}^{T} x _{j}}{∣∣ x _{i} ∣ ∣ _{2} \cdot ∣∣ x _{j} ∣ ∣ _{2}} = \frac{\sum _{k = 1}^{d} x _{ik} x _{jk}}{\sum _{k = 1}^{d} x _{ik}^{2} \sum _{k = 1}^{d} x _{jk}^{2}}

余弦相似度的取值范围是 $[- 1, 1]$ 。值越接近1，表示方向越一致；越接近-1，方向越相反；接近0，表示正交（无关）。

为了将其转换为距离度量（值越小越相似），通常使用：

d_{cos} (x_{i}, x_{j}) = 1 - sim_{cos} (x_{i}, x_{j})

这个在文本挖掘、推荐系统等高维稀疏数据场景中极为常用。例如，在文档分析中，我们更关心词语出现的频率比例（方向），而不是文档的绝对长度（大小）。

3. 层次聚类

层次聚类试图构建一个嵌套的簇的层级结构。其结果通常用一个树状图 (Dendrogram) 来可视化，展示了数据点是如何一步步合并（或分裂）的。

3.1 核心思想与基本分类

层次聚类主要分为两类：

聚合式 (Agglomerative): “自底向上”的方法。初始时，每个样本点自成一簇。在每一步中，找到距离最近的两个簇并将它们合并，直到所有样本点都合并到同一个簇中。这是最常用的方法。
分裂式 (Divisive): “自顶向下”的方法。初始时，所有样本点属于一个大簇。在每一步中，选择一个簇并将其分裂为两个子簇，直到每个样本点都自成一簇。

本次主要聚焦于聚合式层次聚类。

3.2 聚合层次聚类的算法流程

初始化: 将数据集 $X$ 中的每个样本 $x_{i}$ 视为一个单独的簇 $C_{i} = {x_{i}}$ 。
计算距离矩阵: 计算所有簇对 $(C_{i}, C_{j})$ 之间的距离，构成一个 $N \times N$ 的距离矩阵。初始时，这等价于计算所有样本点对 $(x_{i}, x_{j})$ 之间的距离。
迭代合并: 重复以下步骤，直到只剩下一个簇： a. 在距离矩阵中，找到距离最小的两个簇 $C_{i}^{*}$ 和 $C_{j}^{*}$ 。 b. 将这两个簇合并成一个新的簇 $C_{n e w} = C_{i}^{*} \cup C_{j}^{*}$ 。 c. 从距离矩阵中移除关于 $C_{i}^{*}$ 和 $C_{j}^{*}$ 的行和列。 d. 计算新簇 $C_{n e w}$ 与所有其他现存簇 $C_{k}$ 之间的距离，并将这些新距离添加到矩阵中。

3.3 簇间距离计算

步骤 3.d 是算法的核心。如何定义两个簇（它们是点的集合）之间的距离？这由链接准则 (Linkage Criteria) 决定。不同的准则会导致不同的聚类结果。

令 $C_{i}$ 和 $C_{j}$ 为两个簇，它们之间的距离 $D (C_{i}, C_{j})$ 可以定义为：

单链接 (Single Linkage / MIN): 定义为两个簇中最近的两个点之间的距离。
$D_{s in g l e} (C_{i}, C_{j}) = x \in C_{i}, y \in C_{j} min d (x, y)$
特性: 倾向于产生链状的、细长的簇，对噪声和离群点敏感。
全链接 (Complete Linkage / MAX): 定义为两个簇中最远的两个点之间的距离。
$D_{co m pl e t e} (C_{i}, C_{j}) = x \in C_{i}, y \in C_{j} max d (x, y)$
特性: 倾向于产生紧凑的、球状的簇，对离群点不那么敏感，但可能将大簇分裂。
平均链接 (Average Linkage / UPGMA): 定义为两个簇中所有点对之间距离的平均值。
$D_{a vg} (C_{i}, C_{j}) = \frac{1}{∣ C _{i} ∣∣ C _{j} ∣} x \in C_{i} \sum y \in C_{j} \sum d (x, y)$
特性: 是单链接和全链接的一种折衷，鲁棒性较好。
Ward链接 (Ward’s Linkage): 旨在最小化簇合并后总的簇内平方和 (Within-cluster Sum of Squares, WCSS) 的增量。其距离定义为合并两簇导致的 WCSS 增加量。
$D_{w a r d} (C_{i}, C_{j}) = \frac{2∣ C _{i} ∣∣ C _{j} ∣}{∣ C _{i} ∣ + ∣ C _{j} ∣} ∣∣ μ_{i} - μ_{j} ∣ ∣_{2}$
其中 $μ_{i}$ 和 $μ_{j}$ 分别是簇 $C_{i}$ 和 $C_{j}$ 的质心（均值向量）。 特性: 倾向于产生大小相似、方差较小的球状簇，表现通常很好，但仅适用于欧氏距离。

3.4 手动执行一次层次聚类

假设我们有5个2D数据点： $P_{1} (1, 2), P_{2} (2, 2), P_{3} (5, 8), P_{4} (8, 8), P_{5} (7, 3)$ 。我们将使用欧氏距离和单链接 (MIN) 准则。

步骤 0: 计算初始距离矩阵

我们首先计算所有点对之间的欧氏距离 $d (P_{i}, P_{j}) = (x_{i} - x_{j})^{2} + (y_{i} - y_{j})^{2}$ 。

d (P_{1}, P_{2}) d (P_{1}, P_{3}) d (P_{1}, P_{4}) d (P_{1}, P_{5}) d (P_{2}, P_{3}) d (P_{2}, P_{4}) d (P_{2}, P_{5}) d (P_{3}, P_{4}) d (P_{3}, P_{5}) d (P_{4}, P_{5}) = (1 - 2)^{2} + (2 - 2)^{2} = 1.0 = (1 - 5)^{2} + (2 - 8)^{2} = 16 + 36 = 7.21 = (1 - 8)^{2} + (2 - 8)^{2} = 49 + 36 = 9.22 = (1 - 7)^{2} + (2 - 3)^{2} = 36 + 1 = 6.08 = (2 - 5)^{2} + (2 - 8)^{2} = 9 + 36 = 6.71 = (2 - 8)^{2} + (2 - 8)^{2} = 36 + 36 = 8.49 = (2 - 7)^{2} + (2 - 3)^{2} = 25 + 1 = 5.10 = (5 - 8)^{2} + (8 - 8)^{2} = 9 + 0 = 3.0 = (5 - 7)^{2} + (8 - 3)^{2} = 4 + 25 = 5.39 = (8 - 7)^{2} + (8 - 3)^{2} = 1 + 25 = 5.10

初始距离矩阵 $M_{0}$ (对称矩阵，只显示上三角):

	$P_{1}$	$P_{2}$	$P_{3}$	$P_{4}$	$P_{5}$
$P_{1}$	0	1.0	7.21	9.22	6.08
$P_{2}$		0	6.71	8.49	5.10
$P_{3}$			0	3.0	5.39
$P_{4}$				0	5.10
$P_{5}$					0

步骤 1: 第一次合并

矩阵中的最小值为 $d (P_{1}, P_{2}) = 1.0$ 。我们合并 $P_{1}$ 和 $P_{2}$ 形成新簇 $C_{1} = {P_{1}, P_{2}}$ 。合并发生在距离 1.0 的高度。

步骤 2: 更新距离矩阵

现在簇集合为 ${C_{1}, P_{3}, P_{4}, P_{5}}$ 。我们需要计算 $C_{1}$ 与其他点的距离。根据单链接准则： $D (C_{i}, C_{j}) = min_{x \in C_{i}, y \in C_{j}} d (x, y)$

D (C_{1}, P_{3}) D (C_{1}, P_{4}) D (C_{1}, P_{5}) = min (d (P_{1}, P_{3}), d (P_{2}, P_{3})) = min (7.21, 6.71) = 6.71 = min (d (P_{1}, P_{4}), d (P_{2}, P_{4})) = min (9.22, 8.49) = 8.49 = min (d (P_{1}, P_{5}), d (P_{2}, P_{5})) = min (6.08, 5.10) = 5.10

更新后的距离矩阵 $M_{1}$ :

	$C_{1}$	$P_{3}$	$P_{4}$	$P_{5}$
$C_{1}$	0	6.71	8.49	5.10
$P_{3}$		0	3.0	5.39
$P_{4}$			0	5.10
$P_{5}$				0

步骤 3: 第二次合并

$M_{1}$ 中的最小值为 $d (P_{3}, P_{4}) = 3.0$ 。我们合并 $P_{3}$ 和 $P_{4}$ 形成新簇 $C_{2} = {P_{3}, P_{4}}$ 。合并发生在距离 3.0 的高度。

步骤 4: 更新距离矩阵

簇集合为 ${C_{1}, C_{2}, P_{5}}$ 。计算新距离：

D (C_{1}, C_{2}) D (C_{1}, P_{5}) D (C_{2}, P_{5}) = min (d (P_{1}, P_{3}), d (P_{1}, P_{4}), d (P_{2}, P_{3}), d (P_{2}, P_{4})) = min (7.21, 9.22, 6.71, 8.49) = 6.71 = 5.10 (已计算) = min (d (P_{3}, P_{5}), d (P_{4}, P_{5})) = min (5.39, 5.10) = 5.10

更新后的距离矩阵 $M_{2}$ :

	$C_{1}$	$C_{2}$	$P_{5}$
$C_{1}$	0	6.71	5.10
$C_{2}$		0	5.10
$P_{5}$			0

步骤 5: 第三次合并

$M_{2}$ 中的最小值为 $D (C_{1}, P_{5}) = 5.10$ 和 $D (C_{2}, P_{5}) = 5.10$ 。我们可以任选其一。我们选择合并 $C_{1}$ 和 $P_{5}$ ，形成新簇 $C_{3} = {P_{1}, P_{2}, P_{5}}$ 。合并发生在距离 5.10 的高度。

步骤 6: 最后一次合并

簇集合为 ${C_{3}, C_{2}}$ 。计算最后距离：

D (C_{3}, C_{2}) D (C_{3}, C_{2}) = min (D (C_{1}, C_{2}), D (P_{5}, C_{2})) = min (6.71, 5.10) = 5.10 (注意：这里出了个计算错误，我们重新计算一下) = min (d (P_{1}, P_{3}), d (P_{1}, P_{4}), d (P_{2}, P_{3}), d (P_{2}, P_{4}), d (P_{5}, P_{3}), d (P_{5}, P_{4})) = min (7.21, 9.22, 6.71, 8.49, 5.39, 5.10) = 5.10

为了清晰，我们选择合并 $C_{2}$ 和 $P_{5}$ 形成新簇 $C_{3}^{'} = {P_{3}, P_{4}, P_{5}}$ 。合并发生在 5.10 高度。

簇集合变为 ${C_{1}, C_{3}^{'}}$ 。最后计算 $D (C_{1}, C_{3}^{'})$ : $D (C_{1}, C_{3}^{'}) = min (D (C_{1}, C_{2}), D (C_{1}, P_{5})) = min (6.71, 5.10) = 5.10$ 。最后合并发生在 5.10 高度。

最终结果与树状图 (Dendrogram)

基于上述合并过程，我们可以绘制树状图：

在高度 1.0 处，P1 和 P2 合并。
在高度 3.0 处，P3 和 P4 合并。
在高度 5.1 处，簇{P3,P4}与P5合并。
在高度 5.1 处，簇{P1,P2}与簇{P3,P4,P5}合并。

     |
  +--|-----------------------+
  |  |                       |
  |  +---------+             |
  |  |         |             |
  +--|--+   +--|--+          |
  |  |  |   |  |  |          |
 P1 P2 P5  P3 P4
  1.0     5.1  3.0      <- Merge Heights (Distances)

通过在某个高度水平切割树状图，我们就可以得到相应数量的簇。例如，在高度4.0处切割，得到3个簇： ${P_{1}, P_{2}}$ , ${P_{3}, P_{4}}$ , ${P_{5}}$ 。

3.5 层次聚类算法分析 (Algorithm Analysis)

3.5.1 计算复杂度 (Computational Complexity)

时间复杂度:
- 初始距离矩阵计算: 需要计算 $N (N - 1) /2$ 个距离，复杂度为 $O (N^{2} d)$ ，其中 $d$ 是数据维度。
- 迭代合并: 在朴素实现中，每一步都需要扫描 $O (N^{2})$ 的距离矩阵来找到最小值。总共有 $N - 1$ 次合并。因此，查找过程总共是 $O (N^{3})$ 。更新矩阵的复杂度取决于链接准则，但通常低于查找。所以，总体时间复杂度为 $O (N^{3})$ 。
- 优化: 使用优先队列等数据结构，可以将复杂度优化到 $O (N^{2} lo g N)$ 甚至 $O (N^{2})$ 。但对于初学者，理解 $O (N^{3})$ 的来源更为重要。
空间复杂度: 主要开销是存储 $N \times N$ 的距离矩阵，因此空间复杂度为 $O (N^{2})$ 。

3.5.2 优缺点 (Advantages and Disadvantages)

优点:
1. 无需预设簇数K: 算法会生成一个完整的层次结构，用户可以根据需要选择簇的数量。
2. 可解释性强: 树状图提供了丰富的可视化信息，直观地展示了数据点之间的亲缘关系。
3. 结果确定: 对于给定的距离度量和链接准则，算法的结果是唯一且确定的。
缺点:
1. 计算成本高: $O (N^{2})$ 的空间和至少 $O (N^{2})$ 的时间复杂度，使其不适用于大规模数据集。
2. 贪心策略: 一旦一个合并决策做出，就无法撤销。这可能导致次优的聚类结果。
3. 对链接准则敏感: 不同的链接准则可能产生截然不同的聚类结构。
4. 难以处理非球形簇(除了单链接): 大多数链接准则（如全链接、Ward）倾向于发现球状簇。

4. K-Means聚类

在上文中，我们学习了层次聚类。该方法构建了一个完整的、嵌套的聚类层级，但其 $O (N^{2})$ 的空间复杂度和至少 $O (N^{2})$ 的时间复杂度使其难以应用于大规模数据集。这促使我们寻找更高效的替代方案。

划分式聚类 (Partitional Clustering) 提供了一种不同的思路。它不构建复杂的层级结构，而是直接将数据集 $X$ 划分（Partition）成 $K$ 个预先指定的、互不相交的簇。K-均值（K-Means） 是划分式聚类中最具代表性、最著名的算法。

其核心问题可以表述为：

给定一个数据集 $X = {x_{1}, \dots, x_{N}}$ 和一个预设的簇数 $K$ ，如何找到 $K$ 个簇的中心点（质心）以及每个数据点到簇的分配关系，从而使得所有数据点到其所属簇中心的距离平方和最小？

4.1. 核心概念与目标函数

K-Means 的所有行为都围绕着一个单一、明确的优化目标：最小化簇内平方和 (Within-Cluster Sum of Squares, WCSS)，有时也称为惯性 (Inertia)。这个目标函数是衡量聚类结果紧凑程度的核心指标。

为了精确定义目标函数，我们引入以下符号：

$K$ : 预先设定的簇的数量。
$C_{k}$ : 第 $k$ 个簇的样本集合，其中 $k \in {1, \dots, K}$ 。
$μ_{k}$ : 第 $k$ 个簇的质心（centroid），即该簇内所有样本点的均值向量。
$r_{ik}$ : 一个二元指示变量。如果样本 $x_{i}$ 被分配到簇 $k$ ，则 $r_{ik} = 1$ ，否则 $r_{ik} = 0$ 。对于每个样本 $x_{i}$ ，有且仅有一个 $k$ 使得 $r_{ik} = 1$ ，即 $\sum_{k = 1}^{K} r_{ik} = 1$ 。

K-Means 的目标函数 $J$ 定义为所有数据点到其所属簇质心的欧氏距离平方的总和：

J = k = 1 \sum K x_{i} \in C_{k} \sum ∣∣ x_{i} - μ_{k} ∣ ∣_{2}^{2}

使用指示变量 $r_{ik}$ ，我们可以将目标函数写成一个更通用的形式，该形式对所有样本和所有簇进行求和：

J ({μ_{k}}_{k = 1}^{K}, {r_{ik}}_{i = 1, k = 1}^{N, K}) = i = 1 \sum N k = 1 \sum K r_{ik} ∣∣ x_{i} - μ_{k} ∣ ∣_{2}^{2}

这个公式的含义是：对于每个点 $x_{i}$ ，找到它所属的簇 $k$ (即 $r_{ik} = 1$ 的那一项)，计算它到该簇质心 $μ_{k}$ 的平方距离，然后将所有点的这个值加起来。我们的目标就是找到一组质心 ${μ_{k}}$ 和一组分配关系 ${r_{ik}}$ ，使得 $J$ 的值最小。

4.2 K-均值算法

直接同时优化 ${μ_{k}}$ 和 ${r_{ik}}$ 以最小化 $J$ 是一个 NP-hard 问题。K-Means 采用了一种非常有效的启发式策略——迭代优化，它交替地固定一组变量，优化另一组变量。这个过程与期望最大化 (EM) 算法的思想高度一致。

算法的流程可以分解为两个交替执行的步骤：

初始化 (Initialization):
- 从数据集中选择 $K$ 个点作为初始质心 $μ_{1}^{(0)}, μ_{2}^{(0)}, \dots, μ_{K}^{(0)}$ 。
- 注意: 初始化的选择对最终结果影响巨大。随机选择是一种方法，但更好的策略是 ==K-Means++==，它能以更高的概率选择到更好的初始质心。

迭代执行直至收敛 (Iterate until convergence):

a. 分配步骤 (Assignment Step): * 目标: 在保持质心 ${μ_{k}}$ 不变的情况下，更新每个点的分配关系 ${r_{ik}}$ 以最小化目标函数 $J$ 。 * 操作: 对于每一个数据点 $x_{i}$ ，分别计算它到所有 $K$ 个质心的距离，并将其分配给距离最近的那个质心。 * 数学表达: 对于每个 $i \in {1, \dots, N}$ ，更新其所属簇的索引 $c_{i}$ ：

    $$
     c_i \leftarrow \arg\min_{k \in \{1, \ldots, K\}} ||\mathbf{x}_i - \boldsymbol{\mu}_k||_2^2
     $$
    这等价于将对应的指示变量 $r_{ic_i}$ 设为 1，其他的 $r_{ik}$ ($k \neq c_i$) 设为 0。这一步确保了对于当前的质心，我们找到了最优的划分。

b. 更新步骤 (Update Step): * 目标: 在保持分配关系 ${r_{ik}}$ 不变的情况下，更新每个簇的质心 ${μ_{k}}$ 以最小化目标函数 $J$ 。 * 操作: 对于每一个簇 $k$ ，将其质心 $μ_{k}$ 重新计算为所有被分配到该簇的样本点的算术平均值。 * 数学推导: 我们需要找到使 $J$ 最小化的 $μ_{k}$ 。我们对 $J$ 关于 $μ_{k}$ 求偏导数并令其为零。

    $$
    \begin{align*}
    \frac{\partial J}{\partial \boldsymbol{\mu}_k} &= \frac{\partial}{\partial \boldsymbol{\mu}_k} \left( \sum_{i=1}^{N} \sum_{j=1}^{K} r_{ij} ||\mathbf{x}_i - \boldsymbol{\mu}_j||_2^2 \right) \\
    &= \sum_{i=1}^{N} r_{ik} \frac{\partial}{\partial \boldsymbol{\mu}_k} ||\mathbf{x}_i - \boldsymbol{\mu}_k||_2^2 && \text{（只有 $j=k$ 的项与 $\boldsymbol{\mu}_k$ 相关）} \\
    &= \sum_{i=1}^{N} r_{ik} \frac{\partial}{\partial \boldsymbol{\mu}_k} \left( (\mathbf{x}_i - \boldsymbol{\mu}_k)^T (\mathbf{x}_i - \boldsymbol{\mu}_k) \right) \\
    &= \sum_{i=1}^{N} r_{ik} \cdot 2(\mathbf{x}_i - \boldsymbol{\mu}_k) \cdot (-1) && \text{（应用向量微分法则 $\frac{\partial}{\mathbf{v}} (\mathbf{a}-\mathbf{v})^T(\mathbf{a}-\mathbf{v}) = -2(\mathbf{a}-\mathbf{v})$）} \\
    &= -2 \sum_{i=1}^{N} r_{ik} (\mathbf{x}_i - \boldsymbol{\mu}_k)
    \end{align*}
    $$
    令偏导数为零：
    $$
    \sum_{i=1}^{N} r_{ik} (\mathbf{x}_i - \boldsymbol{\mu}_k) = 0 \implies \sum_{i=1}^{N} r_{ik} \mathbf{x}_i - \sum_{i=1}^{N} r_{ik} \boldsymbol{\mu}_k = 0
    $$
    令 $|C_k| = \sum_{i=1}^{N} r_{ik}$ 为簇 $k$ 中的样本数量，则：
    
    $$
    \sum_{\mathbf{x}_i \in C_k} \mathbf{x}_i - |C_k| \boldsymbol{\mu}_k = 0 \implies \boldsymbol{\mu}_k \leftarrow \frac{\sum_{\mathbf{x}_i \in C_k} \mathbf{x}_i}{|C_k|}
    $$
    这个结果表明，使簇内平方和最小的质心位置，恰好是该簇所有点的几何中心。

终止条件 (Termination):
- 当以下任一条件满足时，算法收敛并终止：
  - 质心位置不再发生变化。
  - 数据点的簇分配关系不再改变。
  - 目标函数 $J$ 的下降值小于一个预设的微小阈值。

4. K-均值算法的执行过程

我们继续使用上文中的数据集： $P_{1} (1, 2), P_{2} (2, 2), P_{3} (5, 8), P_{4} (8, 8), P_{5} (7, 3)$ 。我们设定 $K = 2$ 。

步骤 0: 初始化 为方便演示，我们选择 $P_{1}$ 和 $P_{4}$ 作为初始质心。 $μ_{1}^{(0)} = (1, 2)$ $μ_{2}^{(0)} = (8, 8)$

迭代 1

分配步骤: 计算每个点到 $μ_{1}^{(0)}$ 和 $μ_{2}^{(0)}$ 的平方欧氏距离（为避免开方，直接比较平方距离）。
- $P_{1} (1, 2)$ : $d^{2} (P_{1}, μ_{1}) = 0$ , $d^{2} (P_{1}, μ_{2}) = (1 - 8)^{2} + (2 - 8)^{2} = 85$ . 分配给 $C_{1}$ 。
- $P_{2} (2, 2)$ : $d^{2} (P_{2}, μ_{1}) = (2 - 1)^{2} + (2 - 2)^{2} = 1$ , $d^{2} (P_{2}, μ_{2}) = (2 - 8)^{2} + (2 - 8)^{2} = 72$ . 分配给 $C_{1}$ 。
- $P_{3} (5, 8)$ : $d^{2} (P_{3}, μ_{1}) = (5 - 1)^{2} + (8 - 2)^{2} = 52$ , $d^{2} (P_{3}, μ_{2}) = (5 - 8)^{2} + (8 - 8)^{2} = 9$ . 分配给 $C_{2}$ 。
- $P_{4} (8, 8)$ : $d^{2} (P_{4}, μ_{1}) = (8 - 1)^{2} + (8 - 2)^{2} = 85$ , $d^{2} (P_{4}, μ_{2}) = 0$ . 分配给 $C_{2}$ 。
- $P_{5} (7, 3)$ : $d^{2} (P_{5}, μ_{1}) = (7 - 1)^{2} + (3 - 2)^{2} = 37$ , $d^{2} (P_{5}, μ_{2}) = (7 - 8)^{2} + (3 - 8)^{2} = 26$ . 分配给 $C_{2}$ 。
- 当前簇划分: $C_{1}^{(1)} = {P_{1}, P_{2}}$ , $C_{2}^{(1)} = {P_{3}, P_{4}, P_{5}}$ 。
更新步骤: 重新计算质心。
- $μ_{1}^{(1)} = \frac{P _{1} + P _{2}}{2} = (\frac{1 + 2}{2}, \frac{2 + 2}{2}) = (1.5, 2)$ 。
- $μ_{2}^{(1)} = \frac{P _{3} + P _{4} + P _{5}}{3} = (\frac{5 + 8 + 7}{3}, \frac{8 + 8 + 3}{3}) = (\frac{20}{3}, \frac{19}{3}) \approx (6.67, 6.33)$ 。

迭代 2

分配步骤: 使用新的质心 $μ_{1}^{(1)}$ 和 $μ_{2}^{(1)}$ 重新分配。
- $P_{1} (1, 2)$ : $d^{2} (P_{1}, μ_{1}) = (1 - 1.5)^{2} + (2 - 2)^{2} = 0.25$ , $d^{2} (P_{1}, μ_{2}) \approx (1 - 6.67)^{2} + (2 - 6.33)^{2} = 50.8$ . 分配给 $C_{1}$ 。
- $P_{2} (2, 2)$ : $d^{2} (P_{2}, μ_{1}) = (2 - 1.5)^{2} + (2 - 2)^{2} = 0.25$ , $d^{2} (P_{2}, μ_{2}) \approx (2 - 6.67)^{2} + (2 - 6.33)^{2} = 40.5$ . 分配给 $C_{1}$ 。
- $P_{3} (5, 8)$ : $d^{2} (P_{3}, μ_{1}) = (5 - 1.5)^{2} + (8 - 2)^{2} = 48.25$ , $d^{2} (P_{3}, μ_{2}) \approx (5 - 6.67)^{2} + (8 - 6.33)^{2} = 5.58$ . 分配给 $C_{2}$ 。
- $P_{4} (8, 8)$ : $d^{2} (P_{4}, μ_{1}) = (8 - 1.5)^{2} + (8 - 2)^{2} = 78.25$ , $d^{2} (P_{4}, μ_{2}) \approx (8 - 6.67)^{2} + (8 - 6.33)^{2} = 4.56$ . 分配给 $C_{2}$ 。
- $P_{5} (7, 3)$ : $d^{2} (P_{5}, μ_{1}) = (7 - 1.5)^{2} + (3 - 2)^{2} = 31.25$ , $d^{2} (P_{5}, μ_{2}) \approx (7 - 6.67)^{2} + (3 - 6.33)^{2} = 11.19$ . 分配给 $C_{2}$ 。
- 当前簇划分: $C_{1}^{(2)} = {P_{1}, P_{2}}$ , $C_{2}^{(2)} = {P_{3}, P_{4}, P_{5}}$ 。
终止: 由于 $C_{1}^{(2)} = C_{1}^{(1)}$ 且 $C_{2}^{(2)} = C_{2}^{(1)}$ ，簇的分配关系没有发生变化。因此，算法收敛。

最终结果:

簇 1: ${P_{1} (1, 2), P_{2} (2, 2)}$ ，质心为 $(1.5, 2)$ 。
簇 2: ${P_{3} (5, 8), P_{4} (8, 8), P_{5} (7, 3)}$ ，质心为 $(6.67, 6.33)$ 。

5. 算法分析 (Algorithm Analysis)

5.1 计算复杂度 (Computational Complexity)

设 $N$ 为样本数， $d$ 为数据维度， $K$ 为簇数， $I$ 为迭代次数。
时间复杂度:
- 分配步骤: 对每个样本 $N$ ，计算其与 $K$ 个质心的距离。每次距离计算耗时 $O (d)$ 。总计 $O (N \cdot K \cdot d)$ 。
- 更新步骤: 遍历所有 $N$ 个样本一次，累加到对应簇的求和向量中。总计 $O (N \cdot d)$ 。
- 总体: 每次迭代的复杂度为 $O (N K d)$ 。总时间复杂度为 $O (I \cdot N \cdot K \cdot d)$ 。由于 $I, K, d$ 通常远小于 $N$ ，K-Means 的时间复杂度近似线性于样本数 $N$ ，这使其非常高效。
空间复杂度:
- 存储原始数据： $O (N \cdot d)$ 。
- 存储质心： $O (K \cdot d)$ 。
- 总空间复杂度为 $O (N d + K d)$ 。

5.2 收敛性与局部最优 (Convergence and Local Minima)

收敛性保证: K-Means 算法保证收敛。因为：
1. 分配步骤通过将每个点分给最近的质心，使得目标函数 $J$ 的值减小或保持不变。
2. 更新步骤通过将质心移动到簇的均值位置，同样使得 $J$ 的值减小或保持不变。
3. 目标函数 $J$ 的值非负（有下界0），且在每次迭代中单调不增，因此它必然会收敛到一个定值。
局部最优: K-Means 收敛到的是一个局部最小值 (local minimum)，而非全局最小值。最终的聚类结果严重依赖于初始质心的选择。不同的初始值可能导致截然不同的聚类结果和不同的 $J$ 值。实践中，通常会多次运行 K-Means（使用不同的随机初始化），并选择使得 $J$ 值最小的那次结果。

5.3 优缺点

优点:
1. 高效性: 算法快速、可扩展，是处理大规模数据集最常用的聚类算法之一。
2. 简单性: 原理直观，易于理解和实现。
3. 可解释性: 结果易于解释，簇的质心提供了对簇的直观描述。
缺点:
1. K 值选择: 必须手动预设簇的数量 $K$ ，而 $K$ 值的选择往往没有唯一的正确答案。通常需要借助肘部法则 (Elbow Method) 或轮廓系数 (Silhouette Score) 等指标来辅助判断。
2. 对初始化敏感: 结果可能陷入局部最优，强烈依赖于初始质心的选择。
3. 对离群点敏感: 由于质心是均值，它很容易被异常值（outliers）拉偏，从而影响聚类效果。
4. 对非球形簇的无力: K-Means 的目标函数基于欧氏距离，这内在地假设了簇的形状是凸的、球形的（各向同性），并且大小相似。它无法有效识别细长、环状或非凸形状的簇。

LazyBearLee's Blog

探索