谱聚类（Spectral Clustering）的图拉普拉斯矩阵视角与聚类过程
谱聚类是一种基于图论的聚类方法，特别适合处理非凸分布或复杂形状的数据集。其核心思想是将数据点视为图的节点，利用图的拉普拉斯矩阵（Laplacian Matrix）的特征向量对数据进行低维嵌入，再使用传统聚类算法（如K-means）进行划分。下面逐步讲解其原理与实现步骤。
1. 问题描述
目标：给定数据集 \(X = \{x_1, x_2, ..., x_n\}\)，将其划分为 \(k\) 个簇。
挑战：传统聚类算法（如K-means）假设簇是凸形的，但实际数据可能分布复杂（如同心圆状）。谱聚类通过图拉普拉斯矩阵的谱（特征值）性质，将数据映射到低维空间，使复杂结构变得线性可分。
2. 构建相似度图
将每个数据点视为图的节点，边表示点之间的相似度。常用方法：
- 全连接图：所有节点两两相连，边权重由高斯核函数计算：
\[ w_{ij} = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right) \]
其中 \(\sigma\) 控制相似度衰减速度。
- k近邻图：仅保留每个节点的k个最近邻的边。
- ε-邻域图：仅连接距离小于ε的节点。
相似度矩阵 \(W\)：\(n \times n\) 的对称矩阵，元素 \(w_{ij}\) 表示节点 \(i\) 和 \(j\) 的边权重。
3. 计算图拉普拉斯矩阵
拉普拉斯矩阵是谱聚类的核心，常见形式：
- 未归一化拉普拉斯矩阵：
\[ L = D - W \]
其中 \(D\) 是度矩阵（对角矩阵），\(D_{ii} = \sum_j w_{ij}\) 表示节点 \(i\) 的度。
- 归一化拉普拉斯矩阵（更常用）：
- 对称归一化：
\[ L_{\text{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2} \]
- 随机游走归一化：
\[ L_{\text{rw}} = D^{-1} L = I - D^{-1} W \]
关键性质：
- 拉普拉斯矩阵的特征值非负，最小特征值为0，对应特征向量为全1向量。
- 特征值的数量等于图中连通分量的数量，最小非零特征值对应的特征向量能揭示簇结构。
4. 特征分解与低维嵌入
对拉普拉斯矩阵进行特征分解：
- 计算 \(L\)（或 \(L_{\text{sym}}\)、\(L_{\text{rw}}\)）的前 \(k\) 个最小特征值对应的特征向量。
- 将这些特征向量按列排列，形成矩阵 \(U \in \mathbb{R}^{n \times k}\)：
\[ U = [u_1, u_2, ..., u_k] \]
其中 \(u_i\) 是第 \(i\) 小的特征值对应的特征向量。
3. 矩阵 \(U\) 的每一行对应原始数据点在低维空间（谱空间）的嵌入表示。
为什么有效？
拉普拉斯矩阵的特征向量能将数据点映射到一种“松弛的切割空间”，使得原本复杂的簇边界在低维空间中变得线性可分。
5. 聚类低维嵌入
将矩阵 \(U\) 的每一行视为一个 \(k\) 维向量，使用K-means算法对这些向量进行聚类：
- 输入：\(n\) 个低维向量（对应原始 \(n\) 个数据点）。
- 输出：\(k\) 个簇标签。
示例：若 \(k=2\)，则提取前2个特征向量，数据点被映射到二维平面，K-means直接划分平面上的点。
6. 算法步骤总结
- 输入：数据点集 \(X\)，簇数 \(k\)，相似度参数（如高斯核的 \(\sigma\)）。
- 构建相似度矩阵 \(W\)。
- 计算度矩阵 \(D\) 和拉普拉斯矩阵 \(L\)。
- 计算 \(L\) 的前 \(k\) 个最小特征值对应的特征向量。
- 形成特征向量矩阵 \(U\)，每一行是一个数据点的低维表示。
- 对 \(U\) 的行向量运行K-means，得到簇划分。
- 输出：每个数据点的簇标签。
7. 关键点说明
- 参数选择：高斯核的 \(\sigma\) 影响相似度度量，通常通过启发式方法（如最近邻距离的中位数）选择。
- 归一化的作用：归一化拉普拉斯矩阵能避免度大的节点主导聚类结果，提升对噪声的鲁棒性。
- 复杂度：特征分解是计算瓶颈（\(O(n^3)\)），适合中小规模数据集。
通过以上步骤，谱聚类将非线性可分问题转化为线性可分问题，成为处理复杂结构数据的强大工具。