聚类¶

度量相似度¶

闵可夫斯基距离¶

在聚类分析中，样本间的相似度通常用空间中的距离来表示，常用闵可夫斯基距离

定义 14.1 给定样本集合 $X$，其中 $X$ 是 $m$ 维实数向量空间 $\mathbb{R}^m$ 中的点集。对于样本 $x_i, x_j \in X$，其中 $x_i = (x_{1i}, x_{2i}, \ldots, x_{mi})^T$，$x_j = (x_{1j}, x_{2j}, \ldots, x_{mj})^T$，闵可夫斯基距离 ($d_{ij}$) 定义为：

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

这里 $p \ge 1$。

闵可夫斯基距离的特例：

欧氏距离 (Euclidean distance)：当 $p=2$ 时，闵可夫斯基距离即为欧氏距离。 $$ d_{ij} = \left( \sum_{k=1}^{m} |x_{ki} - x_{kj}|^2 \right)^{\frac{1}{2}} $$
曼哈顿距离 (Manhattan distance)：当 $p=1$ 时，闵可夫斯基距离即为曼哈顿距离。 $$ d_{ij} = \sum_{k=1}^{m} |x_{ki} - x_{kj}| $$
切比雪夫距离 (Chebyshev distance)：当 $p = \infty$ 时，即为切比雪夫距离。它取各个坐标数值差的绝对值的最大值。 $$ d_{ij} = \max_{k} |x_{ki} - x_{kj}| $$

夹角余弦¶

样本之间的相似度也可以用夹角余弦来表示。

定义 14.4 样本 $x_i$ 与样本 $x_j$ 之间的夹角余弦定义为：

\[ s_{ij} = \frac{\sum_{k=1}^{m} x_{ki}x_{kj}}{\left[ \sum_{k=1}^{m} x_{ki}^2 \sum_{k=1}^{m} x_{kj}^2 \right]^{\frac{1}{2}}} \]

余弦相似度衡量的是向量之间的方向差异。值越接近1，表示两个向量越相似；值越接近-1，表示两个向量越不相似（方向相反）；值接近0则表示相关性较低。

余弦相似度经常被用在自然语意当中，例如在文本分析中，长文档和短文档如果讨论的是相同的主题，它们依然可以被认为是相似的。

但是余弦相似度也有忽略绝对值、数据稀疏等一些问题

类/簇¶

通过聚类得到的类或簇，本质是样本的子集。我们一般假定一个聚类方法中，一个样本只能属于一个类，或者类的交集为空集，该方法称为硬聚类方法。

定义 14.5 (基于距离阈值的簇) 设 $T$ 为给定的正数，若集合 $G$ 中任意两个样本 $x_i, x_j$，有： $$ d_{ij} \le T $$

则称 $G$ 为一个类或簇。

类的特征¶

类的特征可以从不同角度来刻画，常用的特征有以下三种：

(1) 类的均值 $\bar{x}_G$ (又称为类的中心) $$ \bar{x}G = \frac{1}{n_G} \sum x_i $$ 式中 }^{n_G$n_G$ 是类 $G$ 的样本个数。

(2) 类的直径 (Diameter) $D_G$ 类的直径 $D_G$ 是类中任意两个样本之间的最大距离，即： $$ D_G = \max\limits_{x_i, x_j \in G} d_{ij} $$

(3) 类的样本散布矩阵 (Scatter Matrix) $A_G$ 与样本协方差矩阵 (Covariance Matrix) $S_G$

类的样本散布矩阵 $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$ 为样本的维数 (样本属性的个数)。

类与类之间的距离¶

下面考虑类 $G_p$ 与类 $G_q$ 之间的距离 $D(p,q)$，也称为连接 (linkage)。类与类之间的距离也有多种定义。

设类 $G_p$ 包含 $n_p$ 个样本，类 $G_q$ 包含 $n_q$ 个样本。分别用 $\bar{x}_p$ 和 $\bar{x}_q$ 表示 $G_p$ 和 $G_q$ 的均值，即类的中心。

最短距离或单连接 (Single Linkage)：
- 定义：类 $G_p$ 的样本与 $G_q$ 的样本之间的最短距离为两类之间的距离。
- 公式：$$ D_{pq} = \min {d_{ij} | x_i \in G_p, x_j \in G_q} $$
最长距离或全连接 (Complete Linkage)：
- 定义：类 $G_p$ 的样本与 $G_q$ 的样本之间的最长距离为两类之间的距离。
- 公式：$$ D_{pq} = \max {d_{ij} | x_i \in G_p, x_j \in G_q} $$
中心距离 (Centroid Linkage)：
- 定义：类 $G_p$ 与类 $G_q$ 的中心 $\bar{x}_p$ 与 $\bar{x}_q$ 之间的距离为两类之间的距离。
- 公式：$$ D_{pq} = d_{\bar{x}_p \bar{x}_q} $$ (注：$d_{\bar{x}_p \bar{x}_q}$ 表示两个类中心点之间的距离，其具体计算方式取决于所选用的样本间距离度量，如欧氏距离等。)
平均距离 (Average Linkage)：
- 定义：类 $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} $$

层次聚类¶

层次聚类是一种假设数据点之间存在层级结构的聚类方法，旨在将样本组织到一颗树状的簇结构中（通常称为谱系图）

层次聚类有聚合型（每个样本作为独立的簇开始）和分裂型（从包含所有样本的单个簇开始）

层次聚类有以下关键的关键要素

样本间距离/相似度度量：用于量化两个独立样本之间的远近或相似程度（如欧氏距离、余弦相似度等）。
簇间连接标准 (Linkage Criteria)：用于定义两个簇之间的距离，常见的有单连接（最短距离）、全连接（最长距离）等
停止条件：决定聚类过程何时结束，例如达到指定的簇数量或簇的某个特性（如直径）超过阈值。

聚合层次聚类算法的典型时间复杂度为 $O(n^3m)$，其中 $n$ 是样本数量，$m$ 是样本的维度。特定优化或条件下可能有所不同。

K均值聚类¶

策略概述¶

k-均值聚类是一种广泛使用的划分聚类算法，其目标是将数据集划分为 $k$ 个簇 (cluster)，使得每个数据点都属于其均值（质心）最近的簇。

k-均值聚类有以下关键要素

距离度量：通常使用样本间的欧氏距离的平方来衡量相似性，其中，$x_i, x_j$ 是 $m$ 维样本点。

\[ d(x_i, x_j) = \sum_{s=1}^{m} (x_{si} - x_{sj})^2 = \|x_i - x_j\|^2 \]
损失函数 (Loss Function)： k-均值聚类的目标是最小化所有样本点到其所属簇的质心（均值）的距离平方和。这个损失函数 $W(C)$ 定义为： $$ W(C) = \sum_{l=1}^{k} \sum_{x_i \in C_l} |x_i - \bar{x}_l|^2 $$
优化问题：k-均值聚类旨在求解最小化W的最优化问题，找到最优的簇划分 $C^*$： $$ C^* = \arg \min_{C} W(C) = \arg \min_{C} \sum_{l=1}^{k} \sum_{x_i \in C_l} |x_i - \bar{x}_l|^2 $$

由于将 $n$ 个样本划分到 $k$ 个簇是一个组合优化问题。所有可能划分的数目是巨大的。实际上，精确求解 k-均值聚类的最优化问题是 NP-hard 问题——意味着对于大规模数据集，在合理时间内找到全局最优解通常是不可行的。

迭代算法¶

计算k均值聚类，我们通常采用迭代算法，通过不断更新聚类质心来减少损失函数，具体算法如下

初始化 (Initialization)：
- 随机选择 $k$ 个样本点作为初始的聚类质心 $m^{(0)} = (m_1^{(0)}, m_2^{(0)}, \ldots, m_k^{(0)})$。
簇分配 (Assignment Step / E-step like)：
- 计算数据集中每个样本 $x_i$ 到这 $k$ 个聚类质心的距离（通常是欧氏距离）。
- 将每个样本 $x_i$ 指派到与其距离最近的质心所代表的簇中。
更新质心 (Update Step / M-step like)：
- 重新计算该簇中所有样本点的均值，并将此均值作为该簇新的质心 $m_l^{(t+1)}$。
收敛判断 (Convergence Check)：
- 如果满足以下任一停止条件：
  - 质心 $m^{(t+1)}$ 与 $m^{(t)}$ 的变化非常小（小于某个阈值）。
  - 簇的分配结果 $C^{(t)}$ 不再发生改变。
  - 达到预设的最大迭代次数。

若算法迭代 $I$ 次收敛，则总复杂度为 $O(Imnk)$。在实际应用中， $I$ 通常是一个较小的常数。

算法特性¶

总体特点：算法的目标是最小化所有样本与其各自类别中心之间距离的总和。最终产生的类别是扁平结构，并非层次化的。
收敛性：作为一种启发式方法，k-均值聚类算法不保证能收敛到全局最优解。
初始类的选择：

选择不同的初始类中心会导致不同的聚类结果。

一种选择初始中心的方法是，可以先采用层次聚类方法对样本进行聚类，当聚类到 k 个类别时停止。之后，从每个类别中选择一个距离该类中心最近的点作为初始的类中心。
类别数 k 的选择：

在 k-均值聚类中，类别数量 k 是一个需要用户预先设定的参数。

然而，在实际应用场景中，最合适的 k 值往往是未知的。

聚类结果的质量可以通过衡量类别的平均直径来评估。通常情况下，当类别数量减少时，平均直径会随之增加；而当类别数量增加到超过某个特定值后，平均直径将不再发生显著变化，这个特定的类别数量就可以被认为是当前数据下的最优 k 值。在实验过程中，可以运用二分查找等方法来更快速地找到这个最优的 k 值。

谱聚类¶

核心思想¶

K-Means 等传统算法，只适合凸形状的点聚类。对于非凸的形状效果不佳（如圆环为一簇）

谱聚类是一种强大的现代聚类算法，它基于图论原理，能够识别任意形状的数据簇，这是它相较于最核心的优势。

谱聚类本质上是一种降维技术，将数据映射到更易于聚类的低维空间。

其基本思想是，将每个数据点视为图上的一个节点，点与点之间的相似度视为连接节点的边的权重。

聚类的目标就是找到一种切割图的方式，使得簇内（子图内）的连接权重尽可能高，而簇间（子图间）的连接权重尽可能低。

高斯相似度 (RBF核)¶

为了将数据点转化为一个带权重的图，我们需要一个函数来度量任意两点之间的“相似度”

高斯相似度函数（也称径向基函数核，RBF Kernel） 是最常用和有效的选择，定义如下：

\[ W_{ij} = \exp\left(-\gamma \|x_i - x_j\|^2\right) \]

其中$\gamma$是超参。

通过这个函数，我们就得到了一个 相似度矩阵 $W$（邻接矩阵），其中 $W_{ij}$ 存储了点 $i$ 和点 $j$ 的相似度。

拉普拉斯矩阵¶

拉普拉斯矩阵 $L$ 的定义为：

\[ L = D - W \]

$W$: 就是我们刚通过高斯相似度计算出的邻接矩阵。
$D$: 是一个度矩阵 (Degree Matrix)。它是一个对角矩阵，其对角线上的元素 $D_{ii}$ 是与节点 $i$ 相关的所有边的权重之和，即 $D_{ii} = \sum_{j} W_{ij}$。简单来说，它衡量了每个节点在图中的“重要性”或“连接度”。

对于任意向量$x$，拉普拉斯方程有

\[ \begin{aligned} (Lx)_i &= \left(\sum_{j } W_{ij}\right) x_i - \sum_{j} W_{ij}x_j = \sum_{j } W_{ij}(x_i - x_j) \\ x^T L x &= \sum_{i,j} x_i L_{ij} x_j = \sum_{i,j} W_{ij}(x_i - x_j)^2 \end{aligned} \]

可以注意到，根据以上转换，有以下性质：

拉普拉斯矩阵的最小特征值总是 0，其对应的特征向量是所有元素为 1 的向量。
如果一个图天然地由 $k$ 个完全独立的子图构成，那么它的拉普拉斯矩阵恰好有 $k$ 个为 0 的特征值。

最优切分¶

我们令$x$为二分切分向量，当节点$i$为A类时，则为1,；为B类则为-1；

此时最小化切分代价，即最小化$x^TLx$，也即最小化$ \sum_{i,j} W_{ij}(x_i - x_j)^2$

我们允许$x$拓展到实数域上，并约束它非全为1、且为单位向量。

由瑞利-里兹定理，在与第一个特征向量（即全1向量，由拉普拉斯方程性质）正交的情况下$\frac{x^TLx}{x^Tx}$的最小解，就是第二小的特征值（Fiedler Value）对应的特征向量（Fiedler Vector）中。

因此，最优分割即该特征向量蕴含的符号，对应于每个节点的二分类。

以此类推，最小的 $k$个特征向量，各自都有一定的二分类能力（0特征除外）

可以依据此，将节点投影到$k$维度当中，随后再进行$k$聚类（此时点的分布适合$k$聚类）

谱聚类完整算法流程¶

结合以上构件，谱聚类的完整流程如下：

构建相似度图: 输入数据集，计算每对数据点之间的相似度，构建相似度矩阵 $W$。
计算拉普拉斯矩阵: 根据 $W$ 计算度矩阵 $D$，然后计算拉普拉斯矩阵 $L = D - W$。（实践中常用的是标准化的拉普拉斯矩阵，如 $L_{sym} = D^{-1/2}LD^{-1/2}$，效果更佳）。
计算特征向量: 对拉普拉斯矩阵 $L$ 进行特征分解，求出其最小的 $k$ 个特征值（包括0特征值）和对应的特征向量。（$k$ 是你希望得到的簇的数量）。
构建新特征空间: 将这 $k$ 个特征向量按列组合，形成一个 $n × k$ 的新矩阵（$n$ 是数据点数量）。这个矩阵的每一行，就是原始数据点在一个新的 $k$ 维空间中的坐标表示。
最终聚类: 在这个新的 $k$ 维低维空间中，此时，使用简单的 K-Means 算法对这个 $n × k$ 矩阵的行向量进行聚类，即可得到最终结果。

需要注意的是，对于大规模数据集，构建相似度矩阵（$O(n^2)$）和进行特征分解（$O(n^3)$）的计算成本非常高。

聚类¶