谱聚类（Spectral Clustering）的图构造、拉普拉斯矩阵选择与图切割视角分析
题目描述
谱聚类是一种基于图论的聚类算法，它不直接对数据点进行分组，而是将数据转换为图结构，利用图的谱（特征值与特征向量）对数据进行划分。
本题目要求深入分析谱聚类的三个核心环节：图的构造方法（如何从数据点构建相似图）、拉普拉斯矩阵的选择（不同拉普拉斯矩阵的性质及其对聚类的影响）、以及图切割视角的解释（如何将聚类问题转化为图划分问题）。
解题过程
1. 背景与核心思想
- 传统聚类的局限性：K-means等算法假设簇呈凸形（如球形），对非凸分布（如环状、流形）效果差。
- 谱聚类的优势：通过构建数据点的相似图，将聚类转化为图划分问题，能处理复杂形状的簇。
- 关键步骤：
- 构建相似图（顶点=数据点，边权重=相似度）。
- 计算图的拉普拉斯矩阵。
- 对拉普拉斯矩阵进行特征分解，利用特征向量映射数据。
- 对映射后的数据使用传统聚类（如K-means）得到最终划分。
2. 图构造方法（相似图的构建）
目标：将数据集 \(X = \{x_1, x_2, ..., x_n\}\) 表示为带权无向图 \(G = (V, E, W)\)，其中 \(W\) 是相似度矩阵 \(W_{ij} \geq 0\)。
常用方法如下：
-
ε-邻近图：
设定阈值 \(\epsilon > 0\)，若两点距离 \(d(x_i, x_j) < \epsilon\)，则连边，权重为1（或距离函数）。
缺点：对 \(\epsilon\) 敏感，容易产生不连通图。 -
k-近邻图：
每个点只与距离最近的 \(k\) 个点连边。- 对称k近邻：仅当 \(x_i\) 是 \(x_j\) 的k近邻且 \(x_j\) 是 \(x_i\) 的k近邻时连边（更严格）。
- 互k近邻：双方互为k近邻才连边，确保图的稀疏性和连通性。
-
全连接图：
所有点之间都连边，权重用高斯核函数计算：
\[ W_{ij} = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right) \]
优点：能捕捉全局关系；缺点：计算量大（\(O(n^2)\)）。
- 高斯相似图（最常用）：
结合全连接图与高斯核，但可通过设置阈值或仅保留k近邻边来稀疏化。
关键参数：带宽 \(\sigma\) 控制相似度衰减速度。
3. 拉普拉斯矩阵的选择
拉普拉斯矩阵 \(L\) 是图 \(G\) 的数学表示，用于刻画图的割性质。定义度矩阵 \(D\)（对角阵，\(D_{ii} = \sum_j W_{ij}\)）。常见形式：
- 非规范化拉普拉斯矩阵：
\[ L = D - W \]
性质：
-
对称半正定，特征值非负。
-
最小特征值为0，对应特征向量为全1向量。
-
适用于连通图，但对噪声敏感。
-
规范化拉普拉斯矩阵（更常用）：
- 对称规范化拉普拉斯：
\[ L_{\text{sym}} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} W D^{-1/2} \]
性质：特征值在 [0,2] 区间，特征向量正交，常用于理论分析。
- 随机游走拉普拉斯：
\[ L_{\text{rw}} = D^{-1} L = I - D^{-1} W \]
性质：与随机游走的转移矩阵相关，特征向量与 $ L_{\text{sym}} $ 可通过 $ D^{-1/2} $ 转换。
- 选择依据：
- 若数据分布均匀，用 \(L_{\text{sym}}\) 更稳定。
- 若图中顶点度差异大（某些点连接很多边），规范化能减少偏差。
4. 图切割视角分析
谱聚类的本质是最小化图割（Graph Cut）的松弛问题。
- 最小割问题：
将图 \(G\) 划分为不相交子集 \(A, B\)，割的大小定义为：
\[ \text{Cut}(A, B) = \sum_{i \in A, j \in B} W_{ij} \]
但最小割易偏向分割出单个点。
- 归一化割（Normalized Cut）：
引入子集规模（顶点度之和）的平衡约束：
\[ \text{NCut}(A, B) = \frac{\text{Cut}(A, B)}{\text{Vol}(A)} + \frac{\text{Cut}(A, B)}{\text{Vol}(B)}, \quad \text{Vol}(A) = \sum_{i \in A} D_{ii} \]
目标：最小化 \(\text{NCut}\) 使划分均匀。
- 松弛化为特征值问题：
定义指示向量 \(f \in \mathbb{R}^n\)，其中 \( f_i = \begin{cases}
\sqrt{\text{Vol}(B)/\text{Vol}(A)} & i \in A \
-\sqrt{\text{Vol}(A)/\text{Vol}(B)} & i \in B
\end{cases} \)。
可证明：
\[ \text{NCut}(A, B) = \frac{f^T L f}{f^T D f} \]
最小化 \(\text{NCut}\) 等价于求解广义特征问题：
\[ L f = \lambda D f \]
第二小特征值对应的特征向量（Fiedler向量）给出了对图的最优二分。
- 多分类扩展：
若要划分为 \(k\) 个簇，取拉普拉斯矩阵最小的 \(k\) 个特征值对应的特征向量，构成 \(n \times k\) 矩阵，每行作为数据点的新表示，再对其行向量用K-means聚类。
5. 算法步骤总结
- 输入：数据点 \(X\)，聚类数 \(k\)。
- 构建相似矩阵 \(W \in \mathbb{R}^{n \times n}\)，如高斯相似度。
- 计算度矩阵 \(D\) 和拉普拉斯矩阵 \(L\)（通常选 \(L_{\text{sym}}\)）。
- 特征分解：求 \(L\) 最小的 \(k\) 个特征值对应的特征向量 \(u_1, ..., u_k\)，形成矩阵 \(U \in \mathbb{R}^{n \times k}\)。
- 规范化：若用 \(L_{\text{sym}}\)，特征向量已正交；若用 \(L_{\text{rw}}\)，需对 \(U\) 的行归一化。
- 聚类：将 \(U\) 的每一行视为新特征向量，用K-means划分为 \(k\) 类。
- 输出：原始数据点的簇标签。
6. 关键问题与讨论
- 参数选择：相似度带宽 \(\sigma\) 和近邻数 \(k\) 影响图结构，可通过启发式方法（如局部尺度调整）优化。
- 计算复杂度：特征分解需 \(O(n^3)\)，大规模数据需使用稀疏矩阵或近似方法。
- 与K-means的联系：谱聚类可视为先对数据做非线性映射（特征向量），再进行线性划分。
- 适用场景：适合非凸分布、流形数据；对噪声和离群点较敏感。
通过以上分析，谱聚类的图构造、拉普拉斯矩阵选择与图切割视角被系统串联，揭示了其如何将数据结构转化为图论问题，并通过谱方法获得低维嵌入以实现有效聚类。