谱聚类（Spectral Clustering）的随机游走解释与图切割优化过程
题目描述
谱聚类是一种基于图论的聚类方法，它将数据点视为图中的节点，并通过图的谱（特征分解）对数据进行降维和聚类。传统谱聚类通常从图切割（如RatioCut或Ncut）的角度解释，但另一种重要视角是随机游走（Random Walk）：将聚类问题转化为“在图中随机游走时，哪些节点更容易被长时间停留”的划分问题。本题要求从随机游走的概率转移角度，推导谱聚类的目标函数，并解释其与拉普拉斯矩阵特征分解的关系。
解题过程
步骤1：构建相似图与随机游走模型
- 数据表示：给定数据集 \(X = \{x_1, x_2, ..., x_n\}\)，每个数据点作为图中的一个节点。
- 相似图构建：
- 计算节点间的相似度（如高斯核函数）：
\[ W_{ij} = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right) \]
其中 $ W $ 是邻接矩阵，$ W_{ij} $ 表示节点 $ i $ 和 $ j $ 的边权重。
- 定义度矩阵 \(D\)：对角矩阵，\(D_{ii} = \sum_j W_{ij}\) 表示节点 \(i\) 的度。
- 随机游走转移矩阵：
- 从节点 \(i\) 转移到节点 \(j\) 的概率为：
\[ P_{ij} = \frac{W_{ij}}{D_{ii}} \]
转移矩阵 $ P = D^{-1}W $ 是随机矩阵（每行和为1）。
步骤2：随机游走的平稳分布与聚类直觉
- 平稳分布：若随机游走收敛，平稳分布 \(\pi\) 满足 \(\pi P = \pi\)。对于无向图，\(\pi_i = \frac{D_{ii}}{\sum_j D_{jj}}\)。
- 聚类目标：理想聚类中，随机游走在同一簇内转移概率高，跨簇转移概率低。因此，聚类问题可转化为寻找图的划分，使得随机游走难以逃离每个簇。
步骤3：从随机游走到图切割的等价性
- 逃离概率与归一化割（Ncut）：
- 定义簇 \(A\) 的逃离概率：从 \(A\) 出发一步转移到其他簇的概率：
\[ \text{Pr}(A \to \bar{A}) = \frac{\sum_{i \in A, j \notin A} W_{ij}}{\sum_{i \in A} D_{ii}} \]
- 目标是最小化所有簇的逃离概率之和，即等价于最小化归一化割（Ncut）：
\[ \text{Ncut}(A_1, ..., A_k) = \sum_{t=1}^k \frac{\text{cut}(A_t, \bar{A}_t)}{\text{vol}(A_t)} \]
其中 $\text{cut}(A, B) = \sum_{i \in A, j \in B} W_{ij}$，$\text{vol}(A) = \sum_{i \in A} D_{ii}$。
步骤4：推导谱聚类的优化问题
- 指示向量与拉普拉斯矩阵：
- 对簇 \(A_t\)，定义指示向量 \(h_t\)：
\[ h_t(i) = \begin{cases} 1/\sqrt{\text{vol}(A_t)} & \text{if } i \in A_t \\ 0 & \text{otherwise} \end{cases} \]
- 可验证 \(h_t^T D h_t = 1\)，且 \(h_t^T L h_t = \frac{\text{cut}(A_t, \bar{A}_t)}{\text{vol}(A_t)}\)，其中 \(L = D - W\) 是未归一化拉普拉斯矩阵。
- 松弛化问题：
- 最小化Ncut的离散优化问题是NP难问题，通过松弛约束（允许 \(h_t\) 取连续值），问题转化为：
\[ \min_{H \in \mathbb{R}^{n \times k}} \text{Tr}(H^T L H) \quad \text{s.t.} \quad H^T D H = I \]
- 令 \(F = D^{1/2} H\)，问题等价于：
\[ \min_F \text{Tr}(F^T D^{-1/2} L D^{-1/2} F) \quad \text{s.t.} \quad F^T F = I \]
其中 $ L_{\text{sym}} = D^{-1/2} L D^{-1/2} $ 是归一化拉普拉斯矩阵。
步骤5：特征分解与聚类实现
- 求解特征向量：上述优化问题的解是 \(L_{\text{sym}}\) 的前 \(k\) 个最小特征值对应的特征向量组成的矩阵 \(F\)。
- 降维与聚类：
- 对 \(F\) 的行进行归一化得到新特征 \(Y = D^{-1/2} F\)。
- 对 \(Y\) 的行（即数据点在降维空间的表示）运行K-means算法，得到最终聚类。
关键点总结
- 随机游走视角将聚类问题转化为最小化逃离概率，与Ncut等价。
- 通过松弛离散约束，问题转化为归一化拉普拉斯矩阵的特征分解。
- 最终聚类在降维空间（特征向量张成的空间）中进行，避免了原始高维数据的复杂分布。
此方法特别适用于非凸分布的数据，但需注意相似度参数 \(\sigma\) 的选择对结果的影响。