1 Background

本章节主要是描述的一种聚类算法，谱聚类(Spectral Clustering)。对机器学习有点了解的同学对聚类算法肯定是很熟悉的，那么谱聚类和之前普通的聚类算法有什么不一样呢？或者说它有什么优势呢？

1.1 聚合型聚类(Compactness)

常见的聚类方法有两种思路，一种就是聚合型聚类(Compactness)。典型的算法有K-means 和Gaussian Mixture Model 这种。GMM 我们在前面的章节中有详细的描述，GMM Clustering 的思想可以这样来表述。我们首先看到GMM 的概率图模型，如下所示：

GMM 从几何角度来看，就是也就是多个高斯分布来取加权平均值。我们想将样本分成多少类，那么$Z$ 就有多少种可能，假设我们需要将其分成N 类。那么Z 是一个离散变量，$Z\in 1,2,3,\cdot \cdot \cdot ,N$，当$Z$ 取每次取不同的值时都对应着一个不同的高斯分布，公式化表达为：$P(x|z)\sim N(\mu ,\sigma 2)$。那么对于一个样本，我们可以计算出它属于每一个类别的不同的概率，从中选取概率最大的即可。GMM 举例如下图所示：
GMM 相关的具体知识，包括GMM 的定义和EM 算法进行求解等，请阅读小编之前写的“白板推导高斯混合模型”。很明显，我们看到GMM 的边界轮廓都是圆的，学术的讲就是“凸”(Convex)的。这样的考虑忽略了数据之间的结构关系，主要考虑的是特征之间的相似度，而且是一种中心的距离方式。而这时候我们需要引出另一种聚类算法的思路了，连通性(Connectivity)。

1.2 连通性聚类(Connectivity)

连通性聚类(Connectivity) 算法的典型代表就是谱聚类(Spectral Clustering)。比如，下面的数据分布，很显然用Spectral Clustering 的方法来聚类成如下的形式更加的合理。如下图所示。很显然这是一个non-convex 的聚类方式，更加注重的是数据分布之间的连通性，并且利用图结构考虑到了数据内部的结构性特点，目标是使不同的类别数据点分的越开越好，至于为什么？请接着往下看SpectralClustering 的模型描述。

1.3 小结

聚合型聚类(Compactness) 和连通性聚类(Connectivity) 方法各有千秋。对于“凸”型形状，聚合型聚类(Compactness) 更好一些，主要考虑的是特征之间的相似度。在复杂情况下，结合Kernel 的做法可以简化计算，这个在“核技巧”那章有详细的说明。而连通性聚类(Connectivity) 方法，主要考虑的是数据的结构上的特点，适合随意的形状。

2 Spectral Clustering 的模型表示

2.1 Spectral Clustering 参数说明

Spectral Clustering 的模型表示实现手段上是使用基于无向带权图的思想。我们将所有的数据样本都分别当成无向图中的一个节点，我们假设概率图模型为：
G={V,E}G=\{V, E\} G={V,E}
V={1,2,3,⋯,N}:V=\{1,2,3, \cdots, N\}:V={1,2,3,⋯,N}: 无向图中每一个节点代表一个数据样本，图中有 $N$ 个节点，代表有 $N$ 个 样本。 X=[x1,x2,⋯,xN]T=[x1Tx2T⋮xNT]N×p:X=\left[x_{1}, x_{2}, \cdots, x_{N}\right]^{T}=\left[\begin{array}{c}x_{1}^{T} \\ x_{2}^{T} \\ \vdots \\ x_{N}^{T}\end{array}\right]_{N \times p}:X=[x1​,x2​,⋯,xN​]T=⎣⎢⎢⎢⎡​x1T​x2T​⋮xNT​​⎦⎥⎥⎥⎤​N×p​: 代表有 $N$ 个样本，每个样本都是 $p$ 维的。而 $V$ 中的 $i$ 就
对应着 xi,x_{i},xi​, 表示第 $i$ 个样本。
E:[wij]n×n:E:\left[w_{i j}\right]_{n \times n}:E:[wij​]n×n​: 这个被称为相似度矩阵，也就是用来表示样本与样本之间的权重。只有点与点之间 存在边，才有权重，否则为 0。比如如下图所示的一个概率图结构：

其中：
wij={k(xi,xj)=exp⁡{−∥xi−xj∥1222σ2}(i,j)∈E0(i,j)≠Ew_{i j}=\left\{\begin{array}{ll} k\left(x_{i}, x_{j}\right)=\exp \left\{-\frac{\left\|x_{i}-x_{j}\right\|_{12}^{2}}{2 \sigma^{2}}\right\} & (i, j) \in E \\ 0 & (i, j) \neq E \end{array}\right. wij​={k(xi​,xj​)=exp{−2σ2∥xi​−xj​∥122​​}0​(i,j)∈E(i,j)​=E​
其实在概率图中体现就是，有连接的地方就有权重，没有连接的地方就没有权重。所以，这样就可以反映数据的条件独立性和结构特点，只有某些点之间才有联系，而不是像 GMM 那样，默认所有点之 间都有联系。

2.2 Spectral Clustering 优化目标

定义： A⊂V,B⊂V,A∩B=∅,W(A,B)=∑i∈A∑j∈BwijA \subset V, B \subset V, A \cap B=\varnothing, W(A, B)=\sum_{i \in A} \sum_{j \in B} w_{i j}A⊂V,B⊂V,A∩B=∅,W(A,B)=∑i∈A​∑j∈B​wij​ 。这个公式描述的是将节点分成两份，每个节点都只能属于其中一类，他们之间的距离定义为，一个集合中的每一个节点，分别到另 一个集合中的所有节点的相似度的和。 如果，想将节点分解成 $k$ 类，那么公式化描述如下所示：
cut⁡(V)=cut⁡(A1,A2,⋯,Ak){V=⋃i=1kAiAi∩Aj=∅,∀i,j∈{1,2,⋯,k}\begin{array}{l} \operatorname{cut}(V)=\operatorname{cut}\left(A_{1}, A_{2}, \cdots, A_{k}\right) \\ \\ \left\{\begin{array}{l} V=\bigcup_{i=1}^{k} A_{i} \\ \\ A_{i} \cap A_{j}=\varnothing, \forall i, j \in\{1,2, \cdots, k\} \end{array}\right. \end{array} cut(V)=cut(A1​,A2​,⋯,Ak​)⎩⎨⎧​V=⋃i=1k​Ai​Ai​∩Aj​=∅,∀i,j∈{1,2,⋯,k}​​
并且令：
cut⁡(V)=∑i=1kW(Ai,Aˉi)=∑i=1k∑p∈Ai∑q∉Aiwpq\operatorname{cut}(V)=\sum_{i=1}^{k} W\left(A_{i}, \bar{A}_{i}\right)=\sum_{i=1}^{k} \sum_{p \in A_{i}} \sum_{q \notin A_{i}} w_{p q} cut(V)=i=1∑k​W(Ai​,Aˉi​)=i=1∑k​p∈Ai​∑​q∈/​Ai​∑​wpq​
其中，Aˉi\bar{A}_{i}Aˉi​表示出了 AiA_{i}Ai​ 以外的所有子集构成的集合。那么这个公式的意思就是，每个集合中的所有点，分别到其他集合中的所有点的相似度的和。那么我们的目标函数，首先可以定义为最小化这个cut 函数。因为该值与聚类的目标一致，即每个子图内部的连接很强，而子图之间的连接很弱，换一种语言来表述就是同一个子图内的样本相似，不同子图之间的样本不相似。即为：
min⁡{Ai}i=1kcut⁡(V)\min _{\left\{A_{i}\right\}_{i=1}^{k} \operatorname{cut}(V)} {Ai​}i=1k​cut(V)min​
其实，也就是要将 V 划分 $k$ 类，使得 cut 函数值最小，实际上就是一个组合优化问题。

2.3 Spectral Clustering 优化目标改进

但是，我们观察上述的式子，实际上是有不妥的地方的。比如，图四中，有一类为2 个节点，另
一类为4 个节点。但直接通过最小化这个值实现聚类还有问题，它没有考虑子图规模对代价函数的影响，使得这个指标最小的切分方案不一定就是最优切割。因此需要对代价函数进行归一化。
第一种最简单的思路，既然我们需要考虑子图的规模，就是除以集合中点的个数，即为：
cut⁡(V)=∑i=1kW(Ai,Aˉi)∣Ak∣\operatorname{cut}(V)=\frac{\sum_{i=1}^{k} W\left(A_{i}, \bar{A}_{i}\right)}{\left|A_{k}\right|} cut(V)=∣Ak​∣∑i=1k​W(Ai​,Aˉi​)​
但是，这样做仍然不妥，因为这样即使考虑了集合中点的个数。子图的复杂度还需要考虑子图中节点的连接情况，而不是仅仅考虑子图的个数即可。考虑子图中的连接也侧面包含了子图的节点个数所带来的复杂度。为了量化连接情况，这里引入一个概念为“度”：这是离散数学中的定义，有向图中分“出度”和“入度”，其实很简单“出度”就是这个节点指向了几个节点，“入度”就是有几个节点指向这个节点。无向图中我们只用度的概念。
而在带权无向图中，一个节点的度即为与这个节点连接的所有的边的权重和。利用度作为归一化因子就比较全面的考虑了子图的复杂度了。
degree⁡(Ak)=∑i∈Akdi,di=∑j=1Nwij\operatorname{degree}\left(\mathrm{A}_{\mathrm{k}}\right)=\sum_{i \in A_{k}} d_{i}, \quad d_{i}=\sum_{j=1}^{N} w_{i j} degree(Ak​)=i∈Ak​∑​di​,di​=j=1∑N​wij​
那么就得到了，最终的优化目惊为：
min⁡{Ai}i=1kNcut⁡(V)=∑i=1kW(Ai,Aˉi)∑i∈Akdi,di=∑j=1Nwij\min _{\left\{A_{i}\right\}_{i=1}^{k}} \operatorname{Ncut}(V)=\frac{\sum_{i=1}^{k} W\left(A_{i}, \bar{A}_{i}\right)}{\sum_{i \in A_{k}} d_{i}}, \quad d_{i}=\sum_{j=1}^{N} w_{i j} {Ai​}i=1k​min​Ncut(V)=∑i∈Ak​​di​∑i=1k​W(Ai​,Aˉi​)​,di​=j=1∑N​wij​

2.4 小结

本小节我们定义了谱聚类的目标函数，该函数值反映的聚类的目标为，同一个子图内的样本相似，不同子图之间的样本不相似。因为需要考虑子图的复杂度，我们对目标函数进行了优化。考虑子图中的连接情况，用“度”的概念来定义子图的复杂度。从而通过引入“度”来表示对子图复杂度的影响，来优化目标函数。

3 目标函数的矩阵表达形式

通过上一小节，我们得到了算法的目标函数为：
{A^k}k=1K=arg⁡min⁡{Ai}i=1k∑i=1kW(Ai,Aˉi)∑i∈Ak∑j=1Nwij\left\{\hat{A}_{k}\right\}_{k=1}^{K}=\arg \min _{\left\{A_{i}\right\}_{i=1}^{k}} \frac{\sum_{i=1}^{k} W\left(A_{i}, \bar{A}_{i}\right)}{\sum_{i \in A_{k}} \sum_{j=1}^{N} w_{i j}} {A^k​}k=1K​=arg{Ai​}i=1k​min​∑i∈Ak​​∑j=1N​wij​∑i=1k​W(Ai​,Aˉi​)​
因为求解的过程中，连加符号并不方便进行各种运算操作。所以，我们要把目标函数转换为矩阵形式，从而方便计算。首先，这个{A^k}k=1K\left\{\hat{A}_{k}\right\}_{k=1}^{K}{A^k​}k=1K​，表示的是将所有的点进行划分后的结果。看着就不好进行运算，所以第一步想办法把这个变成矩阵化表示。

3.1 指示向量(Indicator vector)

令：
{yi∈{0,1}k∑j=1kyij=1\left\{\begin{array}{l} y_{i} \in\{0,1\}^{k} \\ \sum_{j=1}^{k} y_{i j}=1 \end{array}\right. {yi​∈{0,1}k∑j=1k​yij​=1​
这个公式想要表达的意思为， yiy_{i}yi​ 是一个 $k$ 维向量，每一个维度的值要么是 $0,$ 要么是 1∘yij=11_{\circ} y_{i j}=11∘​yij​=1 表示第
$i$ 个样本属于第 $j$ 个类别，而每个样本只能属于一个类别，所ル ∑j=1kyij=1,1≤i≤N,1≤j≤K\sum_{j=1}^{k} y_{i j}=1,1 \leq i \leq N, 1 \leq j \leq K∑j=1k​yij​=1,1≤i≤N,1≤j≤K 那么使用 Indicator vector 后，目标函数为：
Y=(y1,y2,⋯,yN)N×KTY^=arg⁡min⁡Y∑k=1KW(Ak,Aˉk)∑i∈Ak∑j=1Nwij\begin{array}{c} Y=\left(y_{1}, y_{2}, \cdots, y_{N}\right)_{N \times K}^{T} \\ \hat{Y}=\arg \min _{Y} \sum_{k=1}^{K} \frac{W\left(A_{k}, \bar{A}_{k}\right)}{\sum_{i \in A_{k}} \sum_{j=1}^{N} w_{i j}} \end{array} Y=(y1​,y2​,⋯,yN​)N×KT​Y^=argminY​∑k=1K​∑i∈Ak​​∑j=1N​wij​W(Ak​,Aˉk​)​​
利用指示函数将 {A^k}k=1K\left\{\hat{A}_{k}\right\}_{k=1}^{K}{A^k​}k=1K​ 变成矩阵以后，下一步目标就是将后面那一坨改写成矩阵形式。

3.2 对角矩阵

在使用只是向量后，我们成功的将目标函数化简成了：
Y=(y1,y2,⋯,yN)N×KTY^=arg⁡min⁡Y∑k=1KW(Ak,Aˉk)∑i∈Akdi,di=∑j=1Nwij\begin{array}{l} Y=\left(y_{1}, y_{2}, \cdots, y_{N}\right)_{N \times K}^{T} \\ \\ \hat{Y}=\arg \min _{Y} \sum_{k=1}^{K} \frac{W\left(A_{k}, \bar{A}_{k}\right)}{\sum_{i \in A_{k}} d_{i}}, \quad d_{i}=\sum_{j=1}^{N} w_{i j} \end{array} Y=(y1​,y2​,⋯,yN​)N×KT​Y^=argminY​∑k=1K​∑i∈Ak​​di​W(Ak​,Aˉk​)​,di​=∑j=1N​wij​​
我们的下一步目标就是想想如何将 ∑k=1KW(Ak,Aˉk)∑i∈Akdi\sum_{k=1}^{K} \frac{W\left(A_{k}, \bar{A}_{k}\right)}{\sum_{i \in A_{k}} d_{i}}∑k=1K​∑i∈Ak​​di​W(Ak​,Aˉk​)​表达成矩阵形式。细心的同学发现，这实际上就是一个实数。而求和符号可以被我们写做对角矩阵的trace；所以有：

首先来看看如何表示 P 矩阵。 ∑i∈Akdi\sum_{i \in A_{k}} d_{i}∑i∈Ak​​di​ 代表的是，第 $k$ 类集合中，所有的节点的度的和。而无向图中的度就是一个节点与其他 所有节点所连接的边的权重之和。而 W =[wij]n×n=\left[w_{i j}\right]_{n \times n}=[wij​]n×n​ 矩阵中 wijw_{i j}wij​ 代表第 $i$ 个节点与第 $j$ 个节点的权值 所以 W 矩阵，第 i 衍的所有值的利正纤就是第 $i$ 个节点与其他所有节点違接的边前权科之利。 所以，计算方法就是将 W 矩阵，每一行的所有值都相加。度的对角矩阵可以描述为：
D=diag⁡[W[11⋮1]N×1]=[d1d2⋱dN]D=\operatorname{diag}\left[W\left[\begin{array}{c} 1 \\ 1 \\ \vdots \\ 1 \end{array}\right]_{N \times 1}\right]=\left[\begin{array}{cccc} d_{1} & & & \\ & d_{2} & & \\ & & \ddots & \\ & & & d_{N} \end{array}\right] D=diag⎣⎢⎢⎢⎡​W⎣⎢⎢⎢⎡​11⋮1​⎦⎥⎥⎥⎤​N×1​⎦⎥⎥⎥⎤​=⎣⎢⎢⎡​d1​​d2​​⋱​dN​​⎦⎥⎥⎤​
那么，下一步目标就是将这些度分别按划分的类别进行求和，也就是比如 A1={1,2,5},A_{1}=\{1,2,5\},A1​={1,2,5}, 那么就 要把第 1,2,5 三个节点的度加在一起。那么，应该如何去实现呢?
$Y$ 矩阵是 $N\times K$ 维的，行代表节点标号，列代表属于的类别。那么， yij=1y_{i j}=1yij​=1 表示第 $i$ 个样本属 于第 j 个类别。那么，我们从 $Y$ 中取出第 $i$ 行向量 $(1\times K)$ 来, 那么通过这一行向量，根据第几列的 值等于 1，我们可以看出这个样本属于第几类。假设这个行向量第 j 列等于 0; 那么 yiTyiy_{i}^{T} y_{i}yiT​yi​ 结果为：
yiTyi=[00⋯yij=1⋯0][0⋯yij=1⋯0]=[0⋯0⋯0⋮⋱⋮⋱⋮0⋯yjj=1⋯0⋮⋱⋮⋱⋮0⋯0⋯0]y_{i}^{T} y_{i}=\left[\begin{array}{c} 0 \\ 0 \\ \cdots \\ y_{i j}=1 \\ \cdots \\ 0 \end{array}\right]\left[\begin{array}{ccccc} 0 & \cdots & y_{i j}=1 & \cdots & 0 \end{array}\right]=\left[\begin{array}{ccccc} 0 & \cdots & 0 & \cdots & 0 \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ 0 & \cdots & y_{j j}=1 & \cdots & 0 \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & \cdots & 0 \end{array}\right] yiT​yi​=⎣⎢⎢⎢⎢⎢⎢⎡​00⋯yij​=1⋯0​⎦⎥⎥⎥⎥⎥⎥⎤​[0​⋯​yij​=1​⋯​0​]=⎣⎢⎢⎢⎢⎢⎢⎡​0⋮0⋮0​⋯⋱⋯⋱⋯​0⋮yjj​=1⋮0​⋯⋱⋯⋱⋯​0⋮0⋮0​⎦⎥⎥⎥⎥⎥⎥⎤​
那么，很显然 yiTDyiy_{i}^{T} D y_{i}yiT​Dyi​ 求得的是一个 $K\times K$ 的矩阵，而这个矩阵中只有一个元素不为零，其他的 元素都为零。如果 yiy_{i}yi​ 样本属于第 $k$ 类, 那么这个元素的位置为第 $k$ 行, 第 $k$ 列，元素的值为 did_{i }di​。 通过这样的运算，我们成功的实现了，如果第 $i$ 个样本属于第 $k$ 类，就将这个样本的度 di,d_{i},di​, 放在了 $K\times K$的矩阵第$k$ 行，第$k$ 列的位置。而且这个矩阵一定是对角矩阵。
有 N 个样本就算有 N 个这样的矩阵，把这 N 个矩阵加起来就实现了将所有的 did_{i}di​ 按所属的类别求和的工作。也就是：
∑i=1NyiTDyi=YTDY\sum_{i=1}^{N} y_{i}^{T} D y_{i}=Y^{T} D Y i=1∑N​yiT​Dyi​=YTDY
所以，我们就得到了用 Y 和 W 对 P 矩阵的进行表达的形式为：
P=YTdiag⁡(W⋅1N)YP=Y^{T} \operatorname{diag}\left(W \cdot 1_{N}\right) Y P=YTdiag(W⋅1N​)Y
其中，1 N_{N}N​ 元素全为 1 的 $N\times 1$ 维向量。

3.3 拉普拉斯矩阵(Lapalacian Matrix)

成功将$P$ 表示以后，下一步目标则是想办法表示$O$ 矩阵。
[W(A1,Aˉ1)0⋯00W(A2,Aˉ2)⋯0⋮⋮⋱⋮00⋯W(AK,AˉK)]K×K\left[\begin{array}{cccc} W\left(A_{1}, \bar{A}_{1}\right) & 0 & \cdots & 0 \\ 0 & W\left(A_{2}, \bar{A}_{2}\right) & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & W\left(A_{K}, \bar{A}_{K}\right) \end{array}\right]_{K \times K} ⎣⎢⎢⎢⎡​W(A1​,Aˉ1​)0⋮0​0W(A2​,Aˉ2​)⋮0​⋯⋯⋱⋯​00⋮W(AK​,AˉK​)​⎦⎥⎥⎥⎤​K×K​
而 Aˉi\bar{A}_{i}Aˉi​ 代表的是，整个样本集中去除 AiA_{i}Ai​ 中的样本后的所有样本。那么，可以做下列变换：
W(Ak,Aˉk)=W(Ak,V)−W(Ak,Ak)W\left(A_{k}, \bar{A}_{k}\right)=W\left(A_{k}, V\right)-W\left(A_{k}, A_{k}\right) W(Ak​,Aˉk​)=W(Ak​,V)−W(Ak​,Ak​)
根据 W(・) 函数的定义，W(A,B) 函数表示的是 A 中所有点分别到 B 中所有点的相似度的和，即 为：
W(Ai,Aj)=∑p∈Ai,q∉AjwpqW\left(A_{i}, A_{j}\right)=\sum_{p \in A_{i}, q \notin A_{j}} w_{p q} W(Ai​,Aj​)=p∈Ai​,q∈/​Aj​∑​wpq​
所以, W(Ak,V)=∑i∈Akdi,W(Ak,Ak)=∑i∈Ak∑j∉Akwij∘W\left(A_{k}, V\right)=\sum_{i \in A_{k}} d_{i}, W\left(A_{k}, A_{k}\right)=\sum_{i \in A_{k}} \sum_{j \notin A_{k}} w_{i j \circ}W(Ak​,V)=∑i∈Ak​​di​,W(Ak​,Ak​)=∑i∈Ak​​∑j∈/​Ak​​wij∘​ 而 W(Ak,V)=∑i∈Akdi=YTdiag⁡(WW\left(A_{k}, V\right)=\sum_{i \in A_{k}} d_{i}=Y^{T} \operatorname{diag}(WW(Ak​,V)=∑i∈Ak​​di​=YTdiag(W
1N)Y\left.1_{N}\right) Y1N​)Y 是已知的，下一步只要想办法表达 W(Ak,Ak)=∑i∈Ak∑j∉AkwijW\left(A_{k}, A_{k}\right)=\sum_{i \in A_{k}} \sum_{j \notin A_{k}} w_{i j}W(Ak​,Ak​)=∑i∈Ak​​∑j∈/​Ak​​wij​ 即阿。我们的目标是求解同一个类别中，任意两个不同的样本之间的相似度。这其实和上一个求$P$ 的问题非常的类似，那么首先来看看 YTWYY^{T} W YYTWY 会等于什么，因为 Y=(y1,y2,⋯,yN)N×KT,Y=\left(y_{1}, y_{2}, \cdots, y_{N}\right)_{N \times K}^{T},Y=(y1​,y2​,⋯,yN​)N×KT​, 所以
YTWY=[y1y2⋯yN][w11w12⋯w1Nw21w22⋯w2N⋮⋮⋱⋮wN1wN2⋯wNN][y1Ty2T⋮yNNT]=[∑i=1Nyiwi1⋯∑i=1NyiwiN]=∑j=1N∑i=1NyiwijyjT\begin{aligned} Y^{T} W Y=\left[\begin{array}{llll} y_{1} & y_{2} & \cdots & y_{N} \end{array}\right]\left[\begin{array}{cccc} w_{11} & w_{12} & \cdots & w_{1 N} \\ w_{21} & w_{22} & \cdots & w_{2 N} \\ \vdots & \vdots & \ddots & \vdots \\ w_{N 1} & w_{N 2} & \cdots & w_{N N} \end{array}\right]\left[\begin{array}{c} y_{1}^{T} \\ y_{2}^{T} \\ \vdots \\ y_{N_{N}}^{T} \end{array}\right] \\ &=\left[\begin{array}{ccc} \sum_{i=1}^{N} y_{i} w_{i 1} & \cdots & \sum_{i=1}^{N} y_{i} w_{i N} \end{array}\right] \\ &=\sum_{j=1}^{N} \sum_{i=1}^{N} y_{i} w_{i j} y_{j}^{T} \end{aligned} YTWY=[y1​​y2​​⋯​yN​​]⎣⎢⎢⎢⎡​w11​w21​⋮wN1​​w12​w22​⋮wN2​​⋯⋯⋱⋯​w1N​w2N​⋮wNN​​⎦⎥⎥⎥⎤​⎣⎢⎢⎢⎡​y1T​y2T​⋮yNN​T​​⎦⎥⎥⎥⎤​​=[∑i=1N​yi​wi1​​⋯​∑i=1N​yi​wiN​​]=j=1∑N​i=1∑N​yi​wij​yjT​​
有因为 wijw_{i j}wij​ 是一个一维实数，所以. YTWY=∑j=1N∑i=1NyiwijyjT=∑j=1N∑i=1NyiyjTwijY^{T} W Y=\sum_{j=1}^{N} \sum_{i=1}^{N} y_{i} w_{i j} y_{j}^{T}=\sum_{j=1}^{N} \sum_{i=1}^{N} y_{i} y_{j}^{T} w_{i j}YTWY=∑j=1N​∑i=1N​yi​wij​yjT​=∑j=1N​∑i=1N​yi​yjT​wij​ 。那么，我们考虑一下 yiyjTy_{i} y_{j}^{T}yi​yjT​ 等于什么。 yiy_{i}yi​ 表示的是一个样本属于第几类, 那么 yi∈Ap,yi∈Aq,y_{i} \in A_{p}, y_{i} \in A_{q},yi​∈Ap​,yi​∈Aq​, 则 yiyjTy_{i} y_{j}^{T}yi​yjT​ 得到的矩阵中第 i 行，第 j 列的元 为 1，其余的全部为 0。所以：
YTWY=∑j=1N∑i=1NyiwijyjT=[∑i∈A1∑j∈A1wij∑i∈A1∑j∈A2wij⋯∑i∈A1∑j∈Akwij∑i∈A2∑j∈A1wij∑i∈A2∑j∈A2wij⋯∑i∈A2∑j∈Abwij∑i∈Ak∑j∈A1wij⋮⋱⋮∑i∈Ak∑j∈A2wij⋯∑i∈Ak∑j∈Akwij]Y^{T} W Y=\sum_{j=1}^{N} \sum_{i=1}^{N} y_{i} w_{i j} y_{j}^{T}=\left[\begin{array}{cccc} \sum_{i \in A_{1}} \sum_{j \in A_{1}} w_{i j} & \sum_{i \in A_{1}} \sum_{j \in A_{2}} w_{i j} & \cdots & \sum_{i \in A_{1}} \sum_{j \in A_{k}} w_{i j} \\ \sum_{i \in A_{2}} \sum_{j \in A_{1}} w_{i j} & \sum_{i \in A_{2}} \sum_{j \in A_{2}} w_{i j} & \cdots & \sum_{i \in A_{2}} \sum_{j \in A_{b}} w_{i j} \\ \sum_{i \in A_{k}} \sum_{j \in A_{1}} w_{i j} & \vdots & \ddots & \vdots \\ & \sum_{i \in A_{k}} \sum_{j \in A_{2}} w_{i j} & \cdots & \sum_{i \in A_{k}} \sum_{j \in A_{k}} w_{i j} \end{array}\right] YTWY=j=1∑N​i=1∑N​yi​wij​yjT​=⎣⎢⎢⎢⎡​∑i∈A1​​∑j∈A1​​wij​∑i∈A2​​∑j∈A1​​wij​∑i∈Ak​​∑j∈A1​​wij​​∑i∈A1​​∑j∈A2​​wij​∑i∈A2​​∑j∈A2​​wij​⋮∑i∈Ak​​∑j∈A2​​wij​​⋯⋯⋱⋯​∑i∈A1​​∑j∈Ak​​wij​∑i∈A2​​∑j∈Ab​​wij​⋮∑i∈Ak​​∑j∈Ak​​wij​​⎦⎥⎥⎥⎤​
而：

有的同学任然有疑惑，Y TWY^{T} W YTWY 好像和我们想要的结果不太一样。但是，我们关注的是 trace，所以員要对角线上的元素是一样的就可以了。令 O′=YTDY−YTWY,O^{\prime}=Y^{T} D Y-Y^{T} W Y,O′=YTDY−YTWY, 而 tr⁡(O′P−1)=tr⁡(OP−1),\operatorname{tr}\left(O^{\prime} P^{-1}\right)=\operatorname{tr}\left(O P^{-1}\right),tr(O′P−1)=tr(OP−1), 因为 O′O^{\prime}O′和O 对角线上的元素都是一样的。所以，最终我们把Ncut 目标函数化简成了矩阵的表达形式为：
Y^=arg⁡min⁡Ytr⁡{YT(D−W)Y⋅(YTDY)−1},D=diag⁡(W⋅1N)\hat{Y}=\arg \min _{Y} \operatorname{tr}\left\{Y^{T}(D-W) Y \cdot\left(Y^{T} D Y\right)^{-1}\right\}, \quad D=\operatorname{diag}\left(W \cdot 1_{N}\right)Y^=argYmin​tr{YT(D−W)Y⋅(YTDY)−1},D=diag(W⋅1N​)
其中$(D-W)$ 被称为拉普拉斯矩阵(Lapalacian Matrix)。最终，我们成功的用已知的Y 和W来完成了对目标函数Ncut 的矩阵化。有关拉普拉斯矩阵的性质，后面会讲到，这是图中一个很重要的矩阵，感兴趣的同学也可以看看https://zhuanlan.zhihu.com/p/67336297，对拉普拉斯矩阵和拉普拉斯算子的详细介绍。

3.4 小结

这一小节中，我们主要的工作就是将目标函数“Ncut 函数”化简为矩阵形式。首先我们用指示向量来表示样本所属的类别。然后利用指示函数(Y ) 和相似度矩阵(W) 来对Ncut 函数进行表示。其实我觉得这里就可以看成是特征值分解后的结果。最终的变换结果和拉普拉斯矩阵有关系，有关拉普拉斯矩阵的详细内容有兴趣的同学可以自行查阅。

4 总结(Conclusion)

这节主要讲述的是谱聚类算法，首先讲述了两种不同的聚类思路，一种就是聚合型聚类(Compactness)，另一种是连通性聚类(Connectivity) 算法。聚合性聚类更多的考虑是所有样本之间都是一视同仁的，根据特征的相似度来聚类。连通性聚类更多的考虑的是数据之间的分布结构，不同的数据之间可以有关系也可以没有关系，这样便于人们引入对数据的侧重点的分析，有点条件独立的意思在里面。而连通性聚类(Connectivity) 算法需要借助图结构来实现。我们介绍了谱聚类算法的目标函数，然后对目标函数进行了优化，为了计算的方便，又描述了目标函数的矩阵表达形式(在这个部分。