10 Cluster Methods

聚类的基本概念 ¶

相似度或距离 (page 3) ¶

在聚类任务中，核心概念是相似度（similarity） 或 距离（distance）。数据样本集通常表示为一个矩阵 \(X\)，其中包含 \(n\) 个样本，每个样本由 \(m\) 个属性（特征）组成，即 \(X = [x_{ij}]_{m \times n}\)。相似度的选择直接影响聚类的结果，因此它是聚类的根本问题。

闵可夫斯基距离 (Minkowski distance) (page 4-5) ¶

闵可夫斯基距离是一种常用的距离度量，定义如下：给定 \(m\) 维实数向量空间 \(\mathbb{R}^m\) 中的两个样本 \(x_i = (x_{1i}, x_{2i}, \dots, x_{mi})^T\) 和 \(x_j = (x_{1j}, x_{2j}, \dots, x_{mj})^T\)，它们之间的闵可夫斯基距离 \(d_{ij}\) 定义为：

注： 闵可夫斯基距离越大，相似度越小；距离越小，相似度越大。

根据参数 \(p\) 的不同取值，闵可夫斯基距离可以演变为几种常见的距离：

• 当 \(p = 2\) 时，称为欧氏距离 (Euclidean distance)：

  \[ d_{ij} = \left( \sum_{k=1}^m (x_{ki} - x_{kj})^2 \right)^{\frac{1}{2}} \]

  这是最常用的距离度量，几何意义是两点在多维空间中的直线距离。

• 当 \(p = 1\) 时，称为曼哈顿距离 (Manhattan distance) 或城市街区距离：

  \[ d_{ij} = \sum_{k=1}^m |x_{ki} - x_{kj}| \]

  它表示两点在坐标轴方向上的距离之和，如同在城市网格中行走。

• 当 \(p = \infty\) 时，称为切比雪夫距离 (Chebyshev distance)：

  \[ d_{ij} = \max_k |x_{ki} - x_{kj}| \]

  它表示两点在各个维度上的最大距离，常用于国际象棋中王（King）的移动。

马哈拉诺比斯距离 (Mahalanobis distance) (page 6) ¶

马哈拉诺比斯距离，简称马氏距离，是另一种常用的相似度度量。它考虑了各个分量（特征）之间的相关性，并且与各个分量的尺度无关。给定样本集合 \(X = [x_{ij}]_{m \times n}\)，其协方差矩阵记作 \(S\)。样本 \(x_i\) 与样本 \(x_j\) 之间的马哈拉诺比斯距离 \(d_{ij}\) 定义为：

注： 与闵可夫斯基距离类似，马哈拉诺比斯距离越大相似度越小，距离越小相似度越大。

相关系数 (correlation coefficient) (page 7) ¶

样本之间的相似度也可以用相关系数 (correlation coefficient) 来表示。样本 \(x_i\) 与样本 \(x_j\) 之间的相关系数 \(r_{ij}\) 定义为：

其中，\(\bar{x}_i = \frac{1}{m} \sum_{k=1}^m x_{ki}\) 是样本 \(x_i\) 各属性的均值，\(\bar{x}_j = \frac{1}{m} \sum_{k=1}^m x_{kj}\) 是样本 \(x_j\) 各属性的均值。

注： 相关系数的绝对值越接近于 1，表示样本越相似（正相关或负相关）；越接近于 0，表示样本越不相似（无线性相关）。

夹角余弦 (cosine similarity) (page 8) ¶

样本之间的相似度也可以用夹角余弦 (cosine similarity) 来表示。样本 \(x_i\) 与样本 \(x_j\) 之间的夹角余弦 \(s_{ij}\) 定义为：

注： 夹角余弦越接近于 1，表示样本越相似（夹角越小）；越接近于 0，表示样本越不相似（夹角接近 90 度）。它衡量的是两个向量在方向上的接近程度，而不关心它们的长度。

类或簇 (Class or Cluster) (page 10-18) ¶

通过聚类得到的类或簇，本质上是样本的子集。

用 \(G\) 表示类或簇，用 \(x_i, x_j\) 表示类中的样本，用 \(n_G\) 表示 \(G\) 中样本的个数，用 \(d_{ij}\) 表示样本 \(x_i\) 与样本 \(x_j\) 之间的距离。

类的特征可以通过不同角度来刻画，常用的特征有：类的中心、类的直径、类的样本散布矩阵和样本协方差矩阵。

1. 类的均值 \(\bar{x}_G\) ( 类的中心 ) (page 16)：

   \[ \bar{x}_G = \frac{1}{n_G} \sum_{i=1}^{n_G} x_i \]

   其中 \(n_G\) 是类 \(G\) 的样本个数。

2. 类的直径 (diameter) \(D_G\) (page 17)：

   类的直径 \(D_G\) 是类中任意两个样本之间的最大距离，即：

   \[ D_G = \max_{x_i, x_j \in G} d_{ij} \]

3. 类的样本散布矩阵 (scatter matrix) \(A_G\) 与样本协方差矩阵 (covariance matrix) \(S_G\) (page 18)：

   类的样本散布矩阵 \(A_G\) 为：

   \[ A_G = \sum_{i=1}^{n_G} (x_i - \bar{x}_G)(x_i - \bar{x}_G)^T \]

   样本协方差矩阵 \(S_G\) 为：

   \[ S_G = \frac{1}{m-1} A_G = \frac{1}{m-1} \sum_{i=1}^{n_G} (x_i - \bar{x}_G)(x_i - \bar{x}_G)^T \]

   其中 \(m\) 为样本的维数（样本属性的个数）。

类与类之间的距离 (page 19-23) ¶

在层次聚类等算法中，需要定义类与类之间的距离，也称为连接 (linkage)。设类 \(G_p\) 包含 \(n_p\) 个样本，类 \(G_q\) 包含 \(n_q\) 个样本，分别用 \(\bar{x}_p\) 和 \(\bar{x}_q\) 表示 \(G_p\) 和 \(G_q\) 的均值（即类的中心）。

1. 最短距离或单连接 (single linkage) (page 20)：

   定义类 \(G_p\) 的样本与 \(G_q\) 的样本之间的最短距离为两类之间的距离：

   \[ D_{pq} = \min \{ d_{ij} | x_i \in G_p, x_j \in G_q \} \]

   这种连接方式倾向于形成“链状”簇，对噪声敏感。

2. 最长距离或完全连接 (complete linkage) (page 21)：

   定义类 \(G_p\) 的样本与 \(G_q\) 的样本之间的最长距离为两类之间的距离：

   \[ D_{pq} = \max \{ d_{ij} | x_i \in G_p, x_j \in G_q \} \]

   这种连接方式倾向于形成“紧密”的簇，对噪声不那么敏感。

3. 中心距离 (centroid distance) (page 22)：

   定义类 \(G_p\) 与 \(G_q\) 的中心 \(\bar{x}_p\) 与 \(\bar{x}_q\) 之间的距离为两类之间的距离：

   \[ D_{pq} = d_{\bar{x}_p \bar{x}_q} \]

4. 平均距离 (average distance) (page 23)：

   定义类 \(G_p\) 与 \(G_q\) 任意两个样本之间距离的平均值为两类之间的距离：

   \[ D_{pq} = \frac{1}{n_p n_q} \sum_{x_i \in G_p} \sum_{x_j \in G_q} d_{ij} \]

层次聚类 (page 24) ¶

层次聚类基本概念 (page 25) ¶

层次聚类假设类别之间存在层次结构，旨在将样本聚到层次化的类中。

聚合聚类的具体过程 (page 26-27) ¶

聚合聚类的具体过程如下：

1. 开始时，将每个样本各自分到一个类，即每个样本是一个独立的簇。
2. 之后，按照一定的规则（例如类间距离最小），将相距最近的两个类进行合并，建立一个新的类。
3. 重复此操作，每次减少一个类，直到满足停止条件（例如所有样本聚为一类，或达到预设的簇数量）。
4. 最终得到层次化的类别结构（通常以树状图 dendrogram ¹ 表示）。

分裂聚类的具体过程类似，只是方向相反：

1. 开始时，将所有样本分到一个类。
2. 之后，将已有类中相距最远的样本分裂到两个新的类中。
3. 重复此操作直到满足停止条件。
4. 得到层次化的类别。

聚合聚类需要预先确定以下三要素 (page 28) ¶

1. 距离或相似度：选择合适的度量来计算样本之间或簇之间的距离。常见的选择包括：
   • 闵可夫斯基距离（欧氏距离、曼哈顿距离、切比雪夫距离）
   • 马哈拉诺比斯距离
   • 相关系数
   • 夹角余弦
2. 合并规则：确定如何计算两个簇之间的距离，以决定哪个簇应该被合并。常见的合并规则（即前面提到的“类与类之间的距离”）包括：
   • 类间最短距离（单连接）
   • 类间最长距离（完全连接）
   • 中心距离
   • 平均距离
3. 停止条件：确定何时停止聚类过程。常见的停止条件包括：
   • 类的个数达到阈值（极端情况是类的个数为 1，即所有样本聚为一类）。
   • 类的直径超过阈值。

聚合聚类算法 (page 29) ¶

输入： \(n\) 个样本组成的样本集合及样本之间的距离。 输出： 对样本集合的一个层次化聚类。

步骤：

1. 计算 \(n\) 个样本两两之间的欧氏距离 \(\{d_{ij}\}\)，记作矩阵 \(D = [d_{ij}]_{n \times n}\)。
2. 构造 \(n\) 个类，每个类只包含一个样本。
3. 合并类间距离最小的两个类（其中类间距离的计算通常使用预设的合并规则，例如最短距离），构建一个新类。
4. 计算新类与当前各类的距离。若类的个数为 1，终止计算；否则回到步 (3)。

聚合聚类示例 (page 30-34) ¶

给定 5 个样本的集合，样本之间的欧氏距离由如下矩阵 \(D\) 表示：

其中 \(d_{ij}\) 表示第 \(i\) 个样本与第 \(j\) 个样本之间的欧氏距离。显然 \(D\) 为对称矩阵。我们将应用聚合层次聚类法对这 5 个样本进行聚类，采用最短距离（单连接）作为合并规则。

步骤：

1. 初始化： 首先用 5 个样本构建 5 个类，\(G_i = \{x_i\}\)，其中 \(i = 1, 2, \dots, 5\)。这样，样本之间的距离就变成了类之间的距离，所以 5 个类之间的距离矩阵亦为 \(D\)。

2. 第一次合并： 由矩阵 \(D\) 可以看出，最小的非对角线元素是 \(D_{35} = D_{53} = 1\)。因此，将 \(G_3\) 和 \(G_5\) 合并为一个新类，记作 \(G_6 = \{x_3, x_5\}\)。

3. 第二次合并： 计算新类 \(G_6\) 与其他现有类 \(G_1, G_2, G_4\) 之间的最短距离。

   • \(D_{61} = \min(d_{31}, d_{51}) = \min(2, 3) = 2\)
   • \(D_{62} = \min(d_{32}, d_{52}) = \min(5, 6) = 5\)
   • \(D_{64} = \min(d_{34}, d_{54}) = \min(8, 5) = 5\)

   同时，其余两类之间的距离为： - \(D_{12} = 7\) - \(D_{14} = 9\) - \(D_{24} = 4\)

   显然，当前所有类间距离中最小的是 \(D_{61} = 2\)。所以将 \(G_1\) 与 \(G_6\) 合并成一个新类，记作 \(G_7 = \{x_1, x_3, x_5\}\)。

4. 第三次合并： 计算新类 \(G_7\) 与其他现有类 \(G_2, G_4\) 之间的最短距离。

   • \(D_{72} = \min(d_{12}, d_{32}, d_{52}) = \min(7, 5, 6) = 5\)
   • \(D_{74} = \min(d_{14}, d_{34}, d_{54}) = \min(9, 8, 5) = 5\)

   同时，其余类之间的距离为： - \(D_{24} = 4\)

   显然，当前所有类间距离中最小的是 \(D_{24} = 4\)。所以将 \(G_2\) 与 \(G_4\) 合并成一个新类，记作 \(G_8 = \{x_2, x_4\}\)。

5. 第四次合并： 将 \(G_7\) 与 \(G_8\) 合并成一个新类，记作 \(G_9 = \{x_1, x_2, x_3, x_4, x_5\}\)。此时，所有样本都聚成 1 类，聚类终止。

K- 均值聚类 (page 35) ¶

K- 均值聚类基本概念 (page 36) ¶

K- 均值 (K-means) 聚类是基于样本集合划分的聚类算法。它将样本集合划分为 \(k\) 个子集，构成 \(k\) 个类，目标是使每个样本到其所属类的中心的距离最小。

模型 (page 37-38) ¶

• 给定： \(n\) 个样本的集合 \(X = \{x_1, x_2, \dots, x_n\}\)。
• 特征： 每个样本 \(x_i\) 由一个 \(m\) 维特征向量表示。
• 目标： K- 均值聚类的目标是将 \(n\) 个样本分到 \(k\) 个不同的类或簇中，这里假设 \(k < n\)。
• 划分： \(k\) 个类 \(G_1, G_2, \dots, G_k\) 形成对样本集合 \(X\) 的划分，满足：
  • \(G_l \cap G_j = \emptyset\) (for \(l \ne j\))，即不同类之间没有交集。
  • \(\bigcup_{l=1}^k G_l = X\)，即所有类构成了完整的样本集合。
• 聚类函数： 用 \(C\) 表示划分，一个划分对应着一个聚类结果。K- 均值聚类的模型是一个从样本到类的函数 \(l = C(i)\)，其中样本用一个整数 \(i \in \{1, 2, \dots, n\}\) 表示，类用一个整数 \(l \in \{1, 2, \dots, k\}\) 表示。

策略 (page 39-43) ¶

K- 均值聚类归结为样本集合 \(X\) 的划分，或者从样本到类的函数的选择问题。K- 均值聚类的策略是通过损失函数的最小化选取最优的划分或函数 \(C^*\)。

首先，采用欧氏距离平方 (squared Euclidean distance) 作为样本之间的距离度量：

然后，定义样本与其所属类的中心之间的距离的总和为损失函数（也称为能量 \(W(C)\)），表示相同类中的样本相似的程度：

其中，\(\bar{x}_l = (\bar{x}_{1l}, \bar{x}_{2l}, \dots, \bar{x}_{ml})^T\) 是第 \(l\) 个类的均值或中心。\(\sum_{C(i)=l}\) 表示对所有被分配到类 \(l\) 的样本进行求和。

算法 (page 44-47) ¶

K- 均值聚类的算法是一个迭代的过程：

1. 初始化： 首先选择 \(k\) 个类的中心（通常随机选择 \(k\) 个样本点作为初始中心）。
2. 指派： 将每个样本逐个指派到与其最近的中心所在的类中，得到一个聚类结果。这一步可以表述为：对于给定的中心值 \((m_1, m_2, \dots, m_k)\)，求一个划分 \(C\)，使得目标函数极小化： $$ \min_C \sum_{l=1}^k \sum_{C(i)=l} |x_i - m_l|^2 $$ 也就是说，在类中心确定的情况下，将每个样本分到一个类中，使样本和其所属类的中心之间的距离总和最小。求解结果是，将每个样本指派到与其最近的中心 \(m_l\) 的类 \(G_l\) 中。
3. 更新： 然后更新每个类的样本的均值，作为类的新的中心。这一步可以表述为：对于给定的划分 \(C\)，再求各个类的中心 \((m_1, m_2, \dots, m_k)\)，使得目标函数极小化： $$ \min_{m_1, \dots, m_k} \sum_{l=1}^k \sum_{C(i)=l} |x_i - m_l|^2 $$ 也就是说，在划分确定的情况下，使样本和其所属类的中心之间的距离总和最小。求解结果是，对于每个包含 \(n_l\) 个样本的类 \(G_l\)，更新其均值 \(m_l\): $$ m_l = \frac{1}{n_l} \sum_{C(i)=l} x_i, \quad l = 1, \dots, k $$
4. 重复： 重复以上步骤（指派和更新），直到划分不再改变，或者达到预设的最大迭代次数，得到最终的聚类结果。

K- 均值聚类示例 (page 48-50) ¶

给定含有 5 个样本的集合 \(X\)：

试用 K- 均值聚类算法将样本聚到 2 个类中（即 \(k=2\)）。

步骤：

1. 初始化： 选择两个样本点作为类的中心。假设选择 \(m_1^{(0)} = x_1 = (0, 2)^T\), \(m_2^{(0)} = x_2 = (0, 0)^T\)。

2. 第一次迭代 - 样本指派： 以 \(m_1^{(0)}, m_2^{(0)}\) 为类 \(G_1^{(0)}, G_2^{(0)}\) 的中心，计算所有样本到这两个中心的欧氏距离平方：

   • \(x_1=(0,2)^T\):
     • \(d(x_1, m_1^{(0)}) = \|(0,2)^T - (0,2)^T\|^2 = 0\)
     • \(d(x_1, m_2^{(0)}) = \|(0,2)^T - (0,0)^T\|^2 = 0^2 + 2^2 = 4\)
     • \(x_1\) 离 \(m_1^{(0)}\) 最近，所以 \(x_1 \in G_1^{(0)}\)。
   • \(x_2=(0,0)^T\):
     • \(d(x_2, m_1^{(0)}) = \|(0,0)^T - (0,2)^T\|^2 = 0^2 + (-2)^2 = 4\)
     • \(d(x_2, m_2^{(0)}) = \|(0,0)^T - (0,0)^T\|^2 = 0\)
     • \(x_2\) 离 \(m_2^{(0)}\) 最近，所以 \(x_2 \in G_2^{(0)}\)。
   • \(x_3=(1,0)^T\):
     • \(d(x_3, m_1^{(0)}) = \|(1,0)^T - (0,2)^T\|^2 = (1-0)^2 + (0-2)^2 = 1^2 + (-2)^2 = 1+4=5\)
     • \(d(x_3, m_2^{(0)}) = \|(1,0)^T - (0,0)^T\|^2 = (1-0)^2 + (0-0)^2 = 1^2 + 0^2 = 1\)
     • \(x_3\) 离 \(m_2^{(0)}\) 最近，所以 \(x_3 \in G_2^{(0)}\)。
   • \(x_4=(5,0)^T\):
     • \(d(x_4, m_1^{(0)}) = \|(5,0)^T - (0,2)^T\|^2 = (5-0)^2 + (0-2)^2 = 5^2 + (-2)^2 = 25+4=29\)
     • \(d(x_4, m_2^{(0)}) = \|(5,0)^T - (0,0)^T\|^2 = (5-0)^2 + (0-0)^2 = 5^2 + 0^2 = 25\)
     • \(x_4\) 离 \(m_2^{(0)}\) 最近，所以 \(x_4 \in G_2^{(0)}\)。
   • \(x_5=(5,2)^T\):
     • \(d(x_5, m_1^{(0)}) = \|(5,2)^T - (0,2)^T\|^2 = (5-0)^2 + (2-2)^2 = 5^2 + 0^2 = 25\)
     • \(d(x_5, m_2^{(0)}) = \|(5,2)^T - (0,0)^T\|^2 = (5-0)^2 + (2-0)^2 = 5^2 + 2^2 = 25+4=29\)
     • \(x_5\) 离 \(m_1^{(0)}\) 最近，所以 \(x_5 \in G_1^{(0)}\)。

   第一次迭代聚类结果 \(C^{(0)}\)： \(G_1^{(0)} = \{x_1, x_5\}\), \(G_2^{(0)} = \{x_2, x_3, x_4\}\)。

3. 第一次迭代 - 中心更新：

   • \(m_1^{(1)} = \frac{1}{2}(x_1 + x_5) = \frac{1}{2}((0,2)^T + (5,2)^T) = \frac{1}{2}(5,4)^T = (2.5, 2.0)^T\)
   • \(m_2^{(1)} = \frac{1}{3}(x_2 + x_3 + x_4) = \frac{1}{3}((0,0)^T + (1,0)^T + (5,0)^T) = \frac{1}{3}(6,0)^T = (2.0, 0.0)^T\)

4. 第二次迭代 - 样本指派： 以 \(m_1^{(1)}, m_2^{(1)}\) 为类 \(G_1^{(1)}, G_2^{(1)}\) 的中心，计算所有样本到这两个中心的欧氏距离平方：

   • \(x_1=(0,2)^T\):
     • \(d(x_1, m_1^{(1)}) = \|(0,2)^T - (2.5,2.0)^T\|^2 = (-2.5)^2 + 0^2 = 6.25\)
     • \(d(x_1, m_2^{(1)}) = \|(0,2)^T - (2.0,0.0)^T\|^2 = (-2.0)^2 + 2^2 = 4+4=8\)
     • \(x_1\) 离 \(m_1^{(1)}\) 最近，所以 \(x_1 \in G_1^{(1)}\)。
   • \(x_2=(0,0)^T\):
     • \(d(x_2, m_1^{(1)}) = \|(0,0)^T - (2.5,2.0)^T\|^2 = (-2.5)^2 + (-2.0)^2 = 6.25+4=10.25\)
     • \(d(x_2, m_2^{(1)}) = \|(0,0)^T - (2.0,0.0)^T\|^2 = (-2.0)^2 + 0^2 = 4\)
     • \(x_2\) 离 \(m_2^{(1)}\) 最近，所以 \(x_2 \in G_2^{(1)}\)。
   • \(x_3=(1,0)^T\):
     • \(d(x_3, m_1^{(1)}) = \|(1,0)^T - (2.5,2.0)^T\|^2 = (-1.5)^2 + (-2.0)^2 = 2.25+4=6.25\)
     • \(d(x_3, m_2^{(1)}) = \|(1,0)^T - (2.0,0.0)^T\|^2 = (-1.0)^2 + 0^2 = 1\)
     • \(x_3\) 离 \(m_2^{(1)}\) 最近，所以 \(x_3 \in G_2^{(1)}\)。
   • \(x_4=(5,0)^T\):
     • \(d(x_4, m_1^{(1)}) = \|(5,0)^T - (2.5,2.0)^T\|^2 = (2.5)^2 + (-2.0)^2 = 6.25+4=10.25\)
     • \(d(x_4, m_2^{(1)}) = \|(5,0)^T - (2.0,0.0)^T\|^2 = (3.0)^2 + 0^2 = 9\)
     • \(x_4\) 离 \(m_2^{(1)}\) 最近，所以 \(x_4 \in G_2^{(1)}\)。
   • \(x_5=(5,2)^T\):
     • \(d(x_5, m_1^{(1)}) = \|(5,2)^T - (2.5,2.0)^T\|^2 = (2.5)^2 + 0^2 = 6.25\)
     • \(d(x_5, m_2^{(1)}) = \|(5,2)^T - (2.0,0.0)^T\|^2 = (3.0)^2 + 2^2 = 9+4=13\)
     • \(x_5\) 离 \(m_1^{(1)}\) 最近，所以 \(x_5 \in G_1^{(1)}\)。

   第二次迭代聚类结果 \(C^{(1)}\)： \(G_1^{(1)} = \{x_1, x_5\}\), \(G_2^{(1)} = \{x_2, x_3, x_4\}\)。

   由于得到的新的类没有改变（\(C^{(1)}\) 与 \(C^{(0)}\) 相同），聚类停止。

   最终聚类结果： \(G_1^* = \{x_1, x_5\}\), \(G_2^* = \{x_2, x_3, x_4\}\)。

K- 均值聚类算法特点 (page 51) ¶

• 基于划分的聚类方法： 将数据集划分为 \(k\) 个不重叠的簇。
• 类别数 \(k\) 事先指定： 聚类前需要确定希望得到的簇的数量。
• 距离度量： 通常以欧氏距离平方表示样本之间的距离，以中心或样本的均值表示类别。
• 目标函数： 以样本和其所属类的中心之间的距离的总和为最优化的目标函数。
• 结果特点： 得到的类别是平坦的、非层次化的。
• 迭代算法： 通过迭代指派和更新中心来逐步优化。
• 无法保证全局最优： K- 均值属于启发式算法，可能会收敛到局部最优解，而不是全局最优解，其结果依赖于初始中心的选择。

K- 均值聚类算法收敛性 (page 52) ¶

K- 均值聚类属于启发式方法，不能保证收敛到全局最优，初始中心的选择会直接影响聚类结果。尽管如此，类中心在聚类的过程中会发生移动，但往往不会移动太大，因为在每一步，样本都被分到与其最近的中心的类中，这个局部优化步骤限制了中心的剧烈变动。

K- 均值聚类算法：初始类的选择 (page 53) ¶

• 选择不同的初始中心，可能会得到不同的聚类结果。这是 K- 均值算法的一个关键挑战。
• 一种常见的初始中心选择方法是：可以使用层次聚类对样本进行聚类，得到 \(k\) 个类时停止。然后从每个类中选取一个与中心距离最近的点作为 K- 均值算法的初始中心。
• 其他更高级的初始化策略包括 K-means++，旨在选择彼此之间距离较远的初始中心点。

K- 均值聚类算法：k 的选择 (page 54) ¶

• K- 均值聚类中的类别数 \(k\) 值需要预先指定，而在实际应用中，最优的 \(k\) 值是不知道的。
• 一种常用的方法是尝试用不同的 \(k\) 值进行聚类，检验得到聚类结果的质量，从而推测最优的 \(k\) 值。
• 聚类结果的质量可以用类的平均直径来衡量：一般地，类别数 \(k\) 变小时，平均直径会增加。类别数变大超过某个值以后，平均直径会不再发生显著变化，而这个值正是最优的 \(k\) 值。这种方法被称为 “肘部法则” (Elbow Method) ，可以通过绘制平均直径随 \(k\) 值变化的曲线来观察“肘部”点。
• 实验时，可以采用二分查找等方法，快速找到最优的 \(k\) 值。

谱聚类 (Spectral Clustering) (page 55) ¶

引言 (page 56-58) ¶

回忆 K-means 聚类： K-means 算法简单高效，但其假设每个簇可以用一个中心点来表示，并且特别适合于单个簇符合高斯分布（或凸形）的情形。对于一些非凸、复杂的簇形状，K-means 往往表现不佳，例如环形结构的数据，K-means 可能会将其错误地分为多个簇，因为它在中心附近没有样本点。

对于其它分布情形： 谱聚类允许我们解决这些非凸、非球形或非线性可分的数据簇的聚类问题。

图论基本概念 (page 59-70) ¶

谱聚类算法的核心思想是将数据点视为图的顶点，数据点之间的相似度视为边的权重。因此，理解图论的基本概念是学习谱聚类的基础。

• 图 \(G\) (Graph) (page 59)：

  • 由顶点集 \(V\) 和边集 \(E\) 所构成，记为 \(G(V, E)\)。
  • 根据边是否有向，可以分为无向图或者有向图。在谱聚类中，通常使用无向图。

• 图 \(G\) 的邻接矩阵 \(W\) (Adjacency Matrix) (page 59)：

  • 是一个方阵，其行数和列数等于图中顶点的个数 \(n\)。
  • 矩阵元素 \(W_{ij}\) 表示顶点 \(i\) 和顶点 \(j\) 之间边的权重。
  • 对于未加权图，如果顶点 \(i\) 和顶点 \(j\) 之间有边相连，则 \(W_{ij}=1\)；如果没有边相连，则 \(W_{ij}=0\)。在谱聚类中，通常是加权图， \(W_{ij}\) 为相似度值。
  • 对于无向图，邻接矩阵是对称的，即 \(W_{ij} = W_{ji}\)。

• 顶点的度 (Degree of a Vertex) (page 60, 65)：

  • 对于未加权图，一个顶点的度等于与该顶点相连接的边的条数。
  • 对于加权图，一个顶点的度 \(d_i\) 等于所有与该顶点相连接的边的权重之和： $$ d_i = \sum_{j \in V} W_{ij} $$ 如果顶点 \(x_j\) 不与 \(x_i\) 相连接，则 \(W_{ij}=0\)。

• 度矩阵 \(D\) (Degree Matrix) (page 60)：

  • 是一个对角矩阵。将邻接矩阵 \(W\) 各行元素累加至对应的对角元素，即对角线元素 \(D_{ii} = d_i = \sum_j W_{ij}\)，非对角线元素为 \(0\)。

• 拉普拉斯矩阵 \(L\) (Laplacian Matrix) (page 61, 66)：

  • 是描述图的一种矩阵，通常定义为度矩阵减去邻接矩阵： $$ L = D - W $$
  • 其中，\(D\) 是一个对角矩阵，主对角元素表示顶点的度；\(W\) 为亲和度矩阵（即邻接矩阵），其元素 \(W_{ij}\) 表示顶点 \(x_i\) 与 \(x_j\) 之间的亲和程度（即相似度）。

• 基于数据集的图构造 (Graph Construction from Dataset) (page 62-64)：

  • 在谱聚类中，将每一个数据点视为图的一个顶点。
  • 顶点之间可以有边相连，每条边上加上一些权重，用来反映点对亲和性（即相似性）。
  • 亲和性函数： 常用高斯函数计算点对亲和性： $$ W_{ij} = \exp\left(-\frac{|x_i - x_j|^2}{2\sigma^2}\right) $$ 其中，\(\|x_i - x_j\|^2\) 是欧氏距离平方，\(\sigma^2\) 是一个尺度参数，控制相似度衰减的速度。
  • 图的连接方式 (Connectivity Types) (page 64)：
    • 全连接图： 所有数据点之间都有边相连。
    • 局部连接图： 只连接相近的数据点，通常基于 \(k\) - 近邻或 \(\epsilon\) - 半径。
      • \(k\) - 近邻 (\(k\) -NN)： 对每个数据点 \(x_i\)，首先在所有样本中找出不包含 \(x_i\) 的 \(k\) 个最邻近的样本点，然后 \(x_i\) 与每个邻近样本点之间均有一条边相连。为了保证 \(W\) 矩阵的对称性，可以令 \(W_{ij} = W_{ji} = (W_{ij}^T + W_{ji})/2\) ( 对于非对称的 \(k\) -NN 图 )。
      • \(\epsilon\) - 半径 (\(\epsilon\) -ball)： 连接所有距离小于 \(\epsilon\) 的数据点。
  • 相似度矩阵： 构造完成后，可以得到一个点对相似度矩阵 \(W\)。

• 子图概念 (Subgraph Concepts) (page 67)：

  • 子图 \(A \subset V\) 的势 \(|A|\)： 等于其所包含的顶点个数。
  • 子图 \(A \subset V\) 的体积 \(\text{vol}(A)\)： 等于其中所有顶点的度之和，即 \(\text{vol}(A) = \sum_{i \in A} d_i\)。

• 子图 \(A\) 的补图 \(\bar{A}\) (Complement of Subgraph A) (page 68)：

  • \(V\) 中去掉 \(A\) 的顶点所构成的子图 \(\bar{A}\)，即 \(\bar{A} = V - A\)。

• 边割 (Edge Cut) (page 68)：

  • 指边的一个子集，去掉该子集中的边后，图就变成两个或多个连通子图。

• 图切割 (Graph Cut) (page 69)：

  • 设 \(A_1, A_2, \dots, A_k\) 为顶点集合 \(V\) 的非空连通子集，如果 \(A_i \cap A_j = \emptyset\) (for \(i \ne j\))，且 \(A_1 \cup A_2 \cup \dots \cup A_k = V\)，则称 \(A_1, A_2, \dots, A_k\) 为图 \(G\) 的一个分割。

• 子图相似度 \(W(A, B)\) (Subgraph Similarity) (page 70)：

  • 子图 \(A\) 与子图 \(B\) 的相似度定义为连接两个子图所有边的权重之和： $$ W(A, B) = \sum_{i \in A, j \in B} W_{ij} $$
  • 注： 如果两个顶点不相连，则权重为零。

• 子图之间的切割 \(\text{cut}(A, B)\) (Cut between Subgraphs) (page 70)：

  • 子图 \(A\) 与子图 \(B\) 的切割定义为： $$ \text{cut}(A, B) = W(A, B) = \sum_{i \in A, j \in B} W_{ij} $$ 这表示切断两个簇所需的边的权重总和。

图切割 (page 71-74) ¶

聚类从图切割的角度来看，就是要找到一种合理的分割图的方法，使得分割后能形成若干个子图，连接不同子图的边的权重尽可能小，而子图内部的边权重尽可能大。

最小二分切割 (Minimum Bipartition Cut) (page 71-72) ¶

在所有的图切割中，找一个最小代价的切割，将图分为两个不连通的子图。也就是说，切开之后，两个子图之间的相似性要最小。最优化问题如下：

问题： 在实践中，上述目标函数通常会将一个点（比如野点 / 异常值）从其余各点中分离出来。从聚类的角度看，这并不是我们所期望的，因为这只会创建一个非常小的孤立簇。

归一化最小二分切割 (Normalized Minimum Bipartition Cut) (page 73-74) ¶

出现上述问题的原因在于对子图的规模没有加以限制。一个基本的假设是希望两个子图的规模不要相差太大。一个基本的做法是采用子图的势或者体积来对切割进行归一化，即定义如下目标函数：

• 采用子图的势（RatioCut）：

  \[ \text{RatioCut}(A, \bar{A}) := \frac{1}{2} \left( \frac{\text{cut}(A, \bar{A})}{|A|} + \frac{\text{cut}(A, \bar{A})}{|\bar{A}|} \right) \]

  RatioCut 旨在平衡簇的大小，避免切割出过小的簇。

• 采用子图的体积（Ncut）：

  \[ \text{Ncut}(A, \bar{A}) := \frac{1}{2} \left( \frac{\text{cut}(A, \bar{A})}{\text{vol}(A)} + \frac{\text{cut}(A, \bar{A})}{\text{vol}(\bar{A})} \right) \]

  Ncut（Normalized Cut）是谱聚类中最常用的切割准则之一，它考虑了簇内部的连接强度。

K- 切割 (K-Cut) (\(k > 2\)) (page 74) ¶

考虑将图分成 \(k\) 个子图：\(A_1, A_2, \dots, A_k\)。一种直观的方法是将图切割问题理解为多个二分切割问题的综合。

• 未归一化切割目标函数： $$ \text{cut}(A_1, A_2, \dots, A_k) := \frac{1}{2} \sum_{i=1}^k W(A_i, \bar{A}i) = \frac{1}{2} \sum_i) $$}^k \text{cut}(A_i, \bar{A

• 比例切割目标函数 (RatioCut)： $$ \text{RatioCut}(A_1, A_2, \dots, A_k) := \frac{1}{2} \sum_{i=1}^k \frac{W(A_i, \bar{A}i)}{|A_i|} = \sum $$}^k \frac{\text{cut}(A_i, \bar{A}_i)}{|A_i|

• 归一化切割目标函数 (Ncut)： $$ \text{Ncut}(A_1, A_2, \dots, A_k) := \frac{1}{2} \sum_{i=1}^k \frac{W(A_i, \bar{A}i)}{\text{vol}(A_i)} = \sum $$}^k \frac{\text{cut}(A_i, \bar{A}_i)}{\text{vol}(A_i)

拉普拉斯矩阵的性质 (page 75-80) ¶

拉普拉斯矩阵的性质与图的连通性和特征值密切相关，这些性质是谱聚类算法理论基础。

基本性质 (page 75) ¶

• L 的行和为零： 由于 \(L = D - W\)，且 \(D\) 的对角元素是 \(W\) 各行元素之和（即 \(d_i = \sum_j W_{ij}\)），因此 \(L\) 的任意行的元素和为 \(d_i - \sum_j W_{ij} = 0\)。

• L 是半正定矩阵 (Positive Semi-definite Matrix)： 对于任意向量 \(f = [f_1, f_2, \dots, f_n]^T \in \mathbb{R}^n\)，有： $$ \begin{align} f^T Lf &= f^T Df - f^T Wf \ &= \sum_{i=1}^n d_i f_i^2 - \sum_{i,j=1}^n f_i f_j W_{ij} \ &= \frac{1}{2} \left( \sum_{i=1}^n d_i f_i^2 - 2 \sum_{i,j=1}^n f_i f_j W_{ij} + \sum_{j=1}^n d_j f_j^2 \right) \ &= \frac{1}{2} \sum_{i,j=1}^n W_{ij} (f_i - f_j)^2 \ &\ge 0 \end{align} $$ 因为 \(W_{ij} \ge 0\) 且 \((f_i - f_j)^2 \ge 0\)，所以 \(f^T Lf \ge 0\)，这证明了拉普拉斯矩阵是半正定矩阵。半正定矩阵的所有特征值都是非负的。

• L 有 \(n\) 个非负的特征值： 由于拉普拉斯矩阵是半正定矩阵，其所有特征值都大于等于零。

零特征值与图的连通性 (page 75, 77-79) ¶

这是一个重要的定理：

证明：

• 若图 \(G\) 是连通的（即 \(k=1\)）：

  • \(L\) 矩阵有一个特征值为 \(0\)。
  • 其对应的特征向量为一个元素全为 \(1\) 的向量（例如 \(e = [1, 1, \dots, 1]^T\)）。
  • 证明：由于 \(L = D - W\)，且 \(D\) 的每一行和 \(W\) 的每一行之和相等（都等于该顶点的度），因此 \(L \cdot \mathbf{1} = (D - W) \mathbf{1} = D\mathbf{1} - W\mathbf{1} = d - d = \mathbf{0}\)，其中 \(d\) 是一个列向量，其元素为各个顶点的度。所以 \(L \mathbf{1} = \mathbf{0}\)，这意味着 \(\mathbf{1}\) 是特征值 \(0\) 的特征向量。
  • 进一步，由 \(f^T Lf = \frac{1}{2} \sum_{i,j=1}^n W_{ij} (f_i - f_j)^2 = 0\) 可推出 \(W_{ij} (f_i - f_j)^2 = 0\) 对任意 \(i, j\) 成立。如果 \(W_{ij} > 0\)（即 \(i\) 和 \(j\) 有边相连），则 \(f_i - f_j = 0\)，即 \(f_i = f_j\)。
  • 因为图 \(G\) 是连通的，任意两个顶点之间都存在一条路径。这意味着通过路径上的连续连接，所有顶点的 \(f_i\) 值都必须相等。因此，对于连通图，特征值 \(0\) 对应的特征向量只能是所有分量相等的向量（例如 \(\mathbf{1}\) 向量的任意常数倍）。这说明特征值 \(0\) 的重数为 \(1\)。

• 若图 \(G\) 不连通（即 \(k > 1\)）：

  • 不失一般性，假定样本点均按连通子图逐个排序。这样，由于连通子图之间不存在边相连，所以图 \(G\) 的拉普拉斯矩阵具有分块对角结构： $$ L = \begin{pmatrix} L_1 & & \ & L_2 & \ & & \ddots \ & & & L_k \end{pmatrix} $$ 其中 \(L_i\) 是第 \(i\) 个连通子图的拉普拉斯矩阵。
  • 每一个 \(L_i\) 均为一个连通子图的拉普拉斯矩阵，因此每个 \(L_i\) 都有一个特征值为 \(0\)，且对应的特征向量是分量全为 \(1\) 的向量。
  • 我们可以构造 \(k\) 个线性无关的特征向量，它们对应于特征值 \(0\)。例如，对于第 \(s\) 个连通分量 \(A_s\)，我们可以构造一个指示向量 \(e_{A_s}\)，其在 \(A_s\) 对应的位置为 \(1\)，在其他位置为 \(0\)。那么 \(L e_{A_s} = \mathbf{0}\)。
  • 这些指示向量是线性无关的，因此特征值 \(0\) 的重数就是 \(k\)。

这个定理告诉我们一个重要的结论：如果图 \(G\) 具有 \(k\) 个连通子图，若每个连通子图为一个聚类，那么采用其拉普拉斯矩阵的零特征值对应的特征向量可以将这些子图分离开来。 这是因为这些特征值对应的特征向量具有分块非零等值的结构，因此可以自然地将数据点分开。

实际应用中的考虑 (page 80) ¶

但是，实际应用中，数据簇之间并非是完全分离的（即图可能仍然是连通的，但连通性很弱）。在此情形下，自然地，可以考察拉普拉斯矩阵最小的几个特征值对应的特征向量，并由这些特征向量组成新的特征空间。

谱聚类 (page 81) ¶

谱聚类技术路线 (page 82-83) ¶

谱聚类算法的核心技术路线是：

1. 构造图：基于数据点之间的相似性，构建一个加权无向图，形成亲和度矩阵 \(W\)。这是至关重要的一步，因为拉普拉斯矩阵的构造本质上取决于对数据图的描述。
2. 构建拉普拉斯矩阵：根据亲和度矩阵 \(W\) 和度矩阵 \(D\) 构造拉普拉斯矩阵 \(L = D - W\)。
3. 特征值分解：对拉普拉斯矩阵进行特征值分解，求出其最小的几个特征值及其对应的特征向量。
4. 降维与聚类：将这些特征向量的每一行视为一个新的数据点，形成一个低维特征空间。然后在这个新的特征空间上，使用传统的聚类算法（例如 K-means）完成最终的聚类。

归一化图拉普拉斯 (Normalized Graph Laplacian) (page 84-86) ¶

为了解决非平衡切割问题（例如 RatioCut 和 Ncut），通常会使用归一化的拉普拉斯矩阵。有两种常见的归一化图拉普拉斯矩阵：

1. 对称归一化拉普拉斯 (Symmetric Normalized Laplacian)： $$ L_{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2} $$

2. 随机游走归一化拉普拉斯 (Random Walk Normalized Laplacian)： $$ L_{rw} = D^{-1} L = I - D^{-1} W $$

谱聚类算法流程 (page 87-92) ¶

根据不同的图拉普拉斯构造方法，可以得到不同的谱聚类算法形式。但是，这些算法的核心步骤都是相同的：

1. 构建亲和度矩阵 \(W\)： 利用点对之间的相似性。
2. 构建拉普拉斯矩阵 \(L\) ( 或其归一化形式 )： 根据 \(W\) 和 \(D\) 计算。
3. 特征值分解： 求解拉普拉斯矩阵最小的 \(k\) 个特征值对应的特征向量（通常舍弃零特征所对应的分量全相等的特征向量，因为它们对应的是整个图的连通信息而非簇的划分信息）。
4. 降维与 K-means 聚类： 由这些特征向量构成样本点的新特征，采用 K-means 等传统聚类方法完成最后的聚类。

三个经典谱聚类算法概述：

1. Un-normalized (classical) Spectral Clustering ( 非归一化谱聚类 ) - Algorithm 1 (page 88)

   • 输入： 相似度矩阵 \(W\)，簇的数量 \(k\)。
   • 步骤：
     1. 计算非归一化拉普拉斯矩阵 \(L = D - W\)。
     2. 计算 \(L\) 的前 \(k\) 个特征向量 \(u_1, u_2, \dots, u_k\)（对应最小的 \(k\) 个特征值）。
     3. 构建矩阵 \(U \in \mathbb{R}^{n \times k}\)，其列为 \(u_1, u_2, \dots, u_k\)。
     4. 对于 \(i=1, 2, \dots, n\)，令 \(y_i \in \mathbb{R}^k\) 为矩阵 \(U\) 的第 \(i\) 行。
     5. 使用 K-means 算法对点集 \(\{y_i\}_{i=1,\dots,n}\) 在 \(\mathbb{R}^k\) 空间中进行聚类，得到簇 \(A_1, A_2, \dots, A_k\)。
     6. 输出 \(A_1, A_2, \dots, A_k\)。

2. Normalized Spectral Clustering (Shi 算法 ) - Algorithm 2 (page 89)

   • Shi 和 Malik 在 2000 年提出，基于 Ncut 准则的近似解法。
   • 输入： 相似度矩阵 \(W\)，簇的数量 \(k\)。
   • 步骤：
     1. 计算非归一化拉普拉斯矩阵 \(L = D - W\)。
     2. 计算广义特征值问题 \(Lu = \lambda Du\) 的前 \(k\) 个广义特征向量 \(u_1, u_2, \dots, u_k\)（对应最小的 \(k\) 个特征值）。
     3. 构建矩阵 \(U \in \mathbb{R}^{n \times k}\)，其列为 \(u_1, u_2, \dots, u_k\)。
     4. 对于 \(i=1, 2, \dots, n\)，令 \(y_i \in \mathbb{R}^k\) 为矩阵 \(U\) 的第 \(i\) 行。
     5. 使用 K-means 算法对点集 \(\{y_i\}_{i=1,\dots,n}\) 在 \(\mathbb{R}^k\) 空间中进行聚类，得到簇 \(A_1, A_2, \dots, A_k\)。
     6. 输出 \(A_1, A_2, \dots, A_k\)。

3. Normalized Spectral Clustering (Ng 算法 ) - Algorithm 3 (page 90)

   • Ng, Jordan 和 Weiss 在 2002 年提出，基于 \(L_{sym}\) 的方法。
   • 输入： 相似度矩阵 \(W\)，簇的数量 \(k\)。
   • 步骤：
     1. 计算对称归一化拉普拉斯矩阵 \(L_{sym} = D^{-1/2} L D^{-1/2}\)。
     2. 计算 \(L_{sym}\) 的前 \(k\) 个特征向量 \(u_1, u_2, \dots, u_k\)（对应最小的 \(k\) 个特征值）。
     3. 构建矩阵 \(U \in \mathbb{R}^{n \times k}\)，其列为 \(u_1, u_2, \dots, u_k\)。
     4. 将 \(U\) 的每一行进行归一化，使其范数为 \(1\)，得到矩阵 \(T \in \mathbb{R}^{n \times k}\)，即 \(t_{ij} = u_{ij} / (\sum_{m=1}^k u_{im}^2)^{1/2}\)。
     5. 对于 \(i=1, 2, \dots, n\)，令 \(y_i \in \mathbb{R}^k\) 为矩阵 \(T\) 的第 \(i\) 行。
     6. 使用 K-means 算法对点集 \(\{y_i\}_{i=1,\dots,n}\) 在 \(\mathbb{R}^k\) 空间中进行聚类，得到簇 \(A_1, A_2, \dots, A_k\)。
     7. 输出 \(A_1, A_2, \dots, A_k\)。

算法细节与挑战 (page 93) ¶

1. 核心问题是图构造：
   • 局部连接 (k- 近邻或 \(\epsilon\) - 半径 ) 取多大？ 这个参数的选择对结果有很大影响。
   • 点对权值如何计算？ 高斯核函数中的 \(\sigma\) 参数的选择也很关键。
2. 特征值分解问题： 对于超大型矩阵，计算特征值和特征向量仍然不稳定，可能会引起结果很差。这在处理大规模数据集时是一个挑战。
3. K-means 聚类问题： 最后采用 K-means 聚类问题，也可能会影响聚类结果，因为 K-means 本身可能收敛到局部最优，且对初始值敏感。
4. 聚类数目的选择： 当然，聚类数目的多少 (\(k\)) 仍然是一个 open problem（开放问题），需要根据具体应用和数据特性进行选择或评估。

如果这对你有用的话，请给我点个star吧 ===>