其中 $ W_{ij} $ 表示节点 $ i $ 和 $ j $ 的边权重，$ \sigma $ 为尺度参数。  

 其中 $ \text{Cut}(A, B) = \sum_{i \in A, j \in B} W_{ij} $ 是子集间边权重和，$ \text{Vol}(A) = \sum_{i \in A} d_i $ 是子集内度之和（$ d_i = \sum_j W_{ij} $ 为节点度）。

 其中 $ H \in \mathbb{R}^{n \times k} $ 的每一列指示子集划分（具体形式与归一化方式相关）。

 取前 $ k $ 个最小非零特征值对应的特征向量，构成特征向量矩阵 $ V \in \mathbb{R}^{n \times k} $。

谱聚类（Spectral Clustering）的图切割视角与特征向量求解过程 题目描述 谱聚类是一种基于图论的聚类方法，其核心思想是将数据集视为图中的节点，通过图切割准则（如最小化割边权重）将图划分成多个子图。与K-means等基于欧氏距离的方法不同，谱聚类能处理非凸分布的数据。本题要求从图切割的视角出发，解释谱聚类的目标函数构建、拉普拉斯矩阵的作用，以及如何通过特征向量求解实现聚类。 解题过程 构建相似度图 给定数据集 \( X = \{x_ 1, x_ 2, ..., x_ n\} \)，首先计算任意两点间的相似度（如高斯核函数）： \[ W_ {ij} = \exp\left(-\frac{\|x_ i - x_ j\|^2}{2\sigma^2}\right) \] 其中 \( W_ {ij} \) 表示节点 \( i \) 和 \( j \) 的边权重，\( \sigma \) 为尺度参数。 得到邻接矩阵 \( W \in \mathbb{R}^{n \times n} \)，表示图的连接关系。 定义图切割目标 目标是将图划分为 \( k \) 个子集 \( A_ 1, A_ 2, ..., A_ k \)，最小化割边权重之和。常用准则为归一化割（Normalized Cut）： \[ \text{NCut}(A_ 1, ..., A_ k) = \sum_ {i=1}^k \frac{\text{Cut}(A_ i, \bar{A} i)}{\text{Vol}(A_ i)} \] 其中 \( \text{Cut}(A, B) = \sum {i \in A, j \in B} W_ {ij} \) 是子集间边权重和，\( \text{Vol}(A) = \sum_ {i \in A} d_ i \) 是子集内度之和（\( d_ i = \sum_ j W_ {ij} \) 为节点度）。 引入拉普拉斯矩阵 定义度矩阵 \( D = \text{diag}(d_ 1, ..., d_ n) \)，拉普拉斯矩阵 \( L = D - W \)。 归一化割问题可转化为： \[ \min_ {A_ 1,...,A_ k} \text{Tr}(H^T L H) \quad \text{s.t.} \quad H^T D H = I \] 其中 \( H \in \mathbb{R}^{n \times k} \) 的每一列指示子集划分（具体形式与归一化方式相关）。 松弛化与特征值问题 离散划分问题是NP难问题，通过放宽 \( H \) 的离散约束，转化为连续优化问题。 求解广义特征值问题： \[ L \mathbf{v} = \lambda D \mathbf{v} \] 取前 \( k \) 个最小非零特征值对应的特征向量，构成特征向量矩阵 \( V \in \mathbb{R}^{n \times k} \)。 聚类特征向量 将特征向量矩阵 \( V \) 的行视为原始数据在低维空间的嵌入，对其应用K-means聚类（行向量对应原数据点）。 最终聚类结果由K-means对特征向量的划分决定。 关键点说明 拉普拉斯矩阵的特征向量能捕捉图的连通性结构，最小特征值对应图的划分信息。 归一化割避免了偏向分割小群体，提升聚类平衡性。 谱聚类本质是降维后聚类，适用于复杂结构数据，但对相似度矩阵构建和参数（如 \( \sigma \)）敏感。