22 谱聚类——Spectral Clustering-Toy模板网

这篇具有很好参考价值的文章主要介绍了22 谱聚类——Spectral Clustering。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

22 谱聚类——Spectral Clustering

22.1 背景介绍

我们在一般的聚类过程中，普遍理性而言会有两种思想：

将聚集在一起的点进行聚类（离得近的为同一类数据），例如可以线性分类的一组数据。
将具有联通性的一堆点进行聚类，如环形等线性不可分的数据。（这种其实在一定情况下也可以通过Kernel+K-Mean实现——进行非线性转换）

所以我们可以将聚类方法分成两大类：

compactness: K-means, GMM
connectivity: Spectral Clustering

22.2 模型介绍

Spectral Clustering实际上可以表示为一个带权重的无向图。

先给这张图做一个定义：

基本数据表示为：
${\lbrace V, E \rbrace}, \quad V = {\lbrace 1, 2, \dots, N \rbrace}, \quad W = [w_{ij}], 1 \leq i, j \leq N$
其中 $W$ 也被称为Simlarity Matrix或Affinity Matrix， $w_{ij}$ 表示为：
$w_{ij} = \begin{cases} K(x_i, x_j) = \exp{\lbrace - \frac{{\lVert x_i - x_j \rVert}_2^2}{2 \sigma^2} \rbrace} & (i, j) \in E \\ 0 & otherwise \end{cases}$
代表了节点之间的相似度
再做一个定义，用于表示一个符号：若 $\subset V, B \subset V, A \cap B = \empty$ ，则表示集合之间的相似度为
$\sum_{i \in A, j \in B} w_{ij}$

22.3 模型导出

接下来具体导出该模型的公式：

我们可以认为每个节点用于表示一个数据，而边表示数据之间的关联，而现在的目标是将数据分成 $K$ 类，且每一组数据之间的相似度最低，所以我们自然要删除一些边，将图变成由 $K$ 个连通图组成。
为了数学化表示，我们定义一个函数 $C u t (V)$ 用于表示集合 $V$ 删除边的权值之和：
$Cut(A_1, A_2, \dots, A_K) = \sum_{k=1}^K W(A_k, {\bar {A_k}})$
但如果通过 $C u t (V)$ 用于表示目标函数，未免有失偏颇。因为我们切开的每一类中的节点数都是不同的，对于他们的相似度，我们应该做一个加权平均。
一般来说我们会通过节点数求均值： $\sum_{k=1}^K \frac{W(A_k, {\bar {A_k}})}{|A_k|}$ 。但本模型是通过边表示相似度，所以我们应当用类中度数加权，将新的函数定义为 $N c u t (V)$ ：
$\begin{cases} Ncut(V) = \sum_{k=1}^K \frac{W(A_k, {\bar {A_k}})}{\sum_{i \in A_k} degree(i)} \\ degree(i) = \sum_{j=1}^N w_{ij} \end{cases}$
所以我们最后的目标就是这样一个带优化问题：
${\lbrace {\bar{A_k}} \rbrace}_{k=1}^K = arg\min_{{\lbrace {\bar{A_k}} \rbrace}_{k=1}^K} Ncut(V)$

由于这样的数学表示有些过于繁杂，我们自然会想通过矩阵将其表示，首先引入一个指示向量替代目标问题：

假定有指示向量（indicator vector），定义为：
$\begin{cases} Y = {(y_1 \ y_2 \ \dots \ y_N)}_{N \times K}^T \\ y_i \in {\lbrace 0, 1 \rbrace}^K \\ \sum_{j=1}^K y_{ij} = 1 \end{cases}$
所以大致可以表现为 $y_i = {(0 \ \dots \ 1 \ \dots \ 0)}^T$ ，用于表示第 $i$ 个样本属于第 $j$ 个类别
那么我们就可以将带优化问题表示为：
${\bar Y} = arg\min_{Y} Ncut(V)$

22.4 模型的矩阵形式

继目标问题之后，我们也要将优化问题化为矩阵形式：首先化简 $N c u t (V)$ 函数，下文中将 $d e g ree (i)$ 简化为 $d_i$ ：

$\begin{align} Ncut(V) &= \sum_{k=1}^K \frac{W(A_k, {\bar {A_k}})}{\sum_{i \in A_k} d_i} = \begin{pmatrix} \frac{W(A_1, {\bar {A_1}})}{\sum_{i \in A_1} d_i} & & \\ & \dots & \\ & & \frac{W(A_K, {\bar {A_K}})}{\sum_{i \in A_K} d_i} \end{pmatrix} \\ &= tr \left[ \underbrace{\begin{pmatrix} {W(A_1, {\bar {A_1}})} & & \\ & \dots & \\ & & {W(A_K, {\bar {A_K}})} \end{pmatrix}}_{O_{K \times K}} \underbrace{{\begin{pmatrix} {\sum_{i \in A_1} d_i} & & \\ & \dots & \\ & & {\sum_{i \in A_K} d_i} \end{pmatrix}}^{-1}}_{P_{K \times K}} \right] \\ &= tr(O \cdot P^{-1}) \end{align}$

我们将 $N c u t (V)$ 函数拆分成了两部分，我们现在已知 $W, Y$ ，我们需要通过已知条件构造出 $O, P$ 。为了构造出 $P$ ：

我们先来了解一下 $Y$ 的性质：
$\begin{align} Y^T Y &= (y_1 \ y_2 \ \dots \ y_N) \begin{pmatrix} y_1^T \\ y_2^T \\ \dots \\ y_N^T \end{pmatrix} = \sum_{i=1}^N \underbrace{y_i y_i^T}_{=diag(0, \dots, 1, \dots, 0)} \\ &= \underbrace{\begin{pmatrix} N_1 & & \\ & \dots & \\ & & N_K \end{pmatrix}}_{N = \sum_{i=1}^K N_i} = \begin{pmatrix} \sum_{i \in A_1} 1 & & \\ & \dots & \\ & & \sum_{i \in A_K} 1 \end{pmatrix} \end{align}$
我们发现，倘如能把矩阵中的 $1$ 换成 $d_i$ ，结果就是 $P$ 了，所以：
$\begin{cases} P = \begin{pmatrix} {\sum_{i \in A_1} d_i} & & \\ & \dots & \\ & & {\sum_{i \in A_K} d_i} \end{pmatrix} = Y^T D Y \\ D = \begin{pmatrix} d_1 & & \\ & \dots & \\ & & d_N \end{pmatrix} = diag( \underbrace{W \cdot 1_N}_{{(\sum_{j=1}^N w_{1j} \ \dots \ \sum_{j=1}^N w_{Nj})}^T} ) \end{cases}$

为了构造出 $O$ ：

我们先对 $O$ 进行一些数学变换，根据 $W(A_k, {\bar {A_k}}) = W(A_k, V) - W(A_k, {A_k})$ 可得：
$\begin{align} O &= \begin{pmatrix} {W(A_1, {\bar {A_1}})} & & \\ & \dots & \\ & & {W(A_K, {\bar {A_K}})} \end{pmatrix} \\ &= \begin{pmatrix} {\sum_{i \in A_1} d_i} & & \\ & \dots & \\ & & {\sum_{i \in A_K} d_i} \end{pmatrix}- \begin{pmatrix} {W(A_1, {A_1})} & & \\ & \dots & \\ & & {W(A_K, {A_K})} \end{pmatrix} \end{align}$
为了表示 $O$ ，我们发现 $left=Y^TDY$ ，这个已经求出来了。为了表示 $r i g h t$ ，我们模仿着看一下 $Y^TWY$ 是什么（我们知道 $y_i y_j^T$ 的矩阵只有在 $(i, j)$ 的位置上为 $1$ ，其他地方都是 $0$ ）：
$\begin{align} Y^TWY &= \sum_{i=1}^N \sum_{j=1}^N y_i w_{ij} y_j^T = \sum_{i=1}^N \sum_{j=1}^N y_i y_j^T w_{ij} \\ &= \begin{pmatrix} \sum_{i \in A_1} \sum_{j \in A_1} w_{ij} & \dots & \sum_{i \in A_1} \sum_{j \in A_K} w_{ij} \\ \dots & \dots & \\ \sum_{i \in A_K} \sum_{j \in A_1} w_{ij} & & \sum_{i \in A_K} \sum_{j \in A_K} w_{ij} \end{pmatrix} \end{align}$
我们发现其实 $Y^TWY \neq right$ ，但如果我们假设 $O^{'} = Y^TDY - Y^TWY$ ，我们会发现其实用 $O^{'}$ 替代 $O$ 进行计算也没有问题，因为我们只需要求trace， $O^{'}$ 的对角线与 $O$ 相同即可。用数学语言表示为：
$\cdot P^{-1}) = tr(O^{'} \cdot P^{-1})$