引言

上一节针对$\text{k-Means}$算法的缺陷，介绍了谱聚类($\text{Spectral Clustering}$)的结构描述以及目标函数。本节将目标函数转化成矩阵形式，并引出拉普拉斯矩阵。

回顾：谱聚类——目标函数表示

谱聚类关于处理聚类任务的朴素思想是：通过对样本的合适划分，使样本的划分代价最小。假设一个样本集合 X = { x ( 1 ) , x ( 2 ) , ⋯   , x ( N ) } \mathcal X = \{x^{(1)},x^{(2)},\cdots,x^{(N)}\} X={x(1),x(2),⋯,x(N)}，它对应的图结构描述如下：
G = { V , E } \mathcal G = \{\mathcal V,\mathcal E\} G={V,E}
其中$\mathcal{V}$表示结点集合，结点数量与样本数量相同；而边集合$\mathcal{E}$可视作一个权重矩阵，矩阵中的元素表示结点之间的关联关系：
V = { v ( 1 ) , v ( 2 ) , ⋯   , v ( N ) } E ⇒ W = [ W v ( i ) ⇔ v ( j ) ] N × N \begin{aligned} \mathcal V & = \{v^{(1)},v^{(2)},\cdots,v^{(N)}\} \\ \mathcal E & \Rightarrow \mathcal W = [\mathcal W_{v^{(i)} \Leftrightarrow v^{(j)}}]_{N \times N} \end{aligned} VE​={v(1),v(2),⋯,v(N)}⇒W=[Wv(i)⇔v(j)​]N×N​​
而结点$v^{(i)},v^{(j)}$之间的关联关系${\mathcal{W}}_{v^{(i)}\iff v^{(j)}}$通常使用样本之间的核函数($\text{Kernel Function}$)表示。这里以高斯核函数为例：
$${\mathcal{W}}_{v^{(i)}\iff v^{(j)}}=\kappa (x^{(i)},x^{(j)})=\exp \left\{-\frac{||x^{(i)}-x^{(j)}|{|}_2^2}{2{\sigma }^2}\right\}\text{assert}⟨v^{(i)},v^{(j)}⟩\in \mathcal{E}$$
假设使用规则将图$\mathcal{G}$划分成$\mathcal{K}$个子图，各子图的结点集合分别表示为： { A 1 , A 2 , ⋯   , A K } \{\mathcal A_1,\mathcal A_2,\cdots,\mathcal A_{\mathcal K}\} {A1​,A2​,⋯,AK​}，并且有：
{ V = A 1 ∪ A 2 ∪ ⋯ ∪ A K A i ∩ A j = ϕ ∀ i , j ∈ { 1 , 2 , ⋯   , K } \begin{cases} \mathcal V = \mathcal A_1 \cup \mathcal A_2 \cup \cdots \cup \mathcal A_{\mathcal K} \\ \mathcal A_i \cap \mathcal A_j = \phi \quad \forall i,j \in \{1,2,\cdots,\mathcal K\} \end{cases} {V=A1​∪A2​∪⋯∪AK​Ai​∩Aj​=ϕ∀i,j∈{1,2,⋯,K}​
至此，在执行划分后关于结点集合$\mathcal{V}$的代价函数$\text{Cut}(\mathcal{V})$可表示为：
其中$\overline{{\mathcal{A}}_k}$表示${\mathcal{A}}_k$的补集。
$$\begin{array}{rl}\text{Cut}(\mathcal{V})& =\text{Cut}({\mathcal{A}}_1,{\mathcal{A}}_2,\cdots ,{\mathcal{A}}_{\mathcal{K}})\\ & =\sum _{k=1}^{\mathcal{K}}\psi ({\mathcal{A}}_k,\overline{{\mathcal{A}}_k})\\ & =\sum _{k=1}^{\mathcal{K}}\sum _{j\ne k}^{\mathcal{K}}\psi ({\mathcal{A}}_k,{\mathcal{A}}_j)\end{array}$$
最后对$\psi ({\mathcal{A}}_k,{\mathcal{A}}_j)$进行标准化后，作为图划分的目标函数：
$$\{\begin{array}{l}\text{Normalized-Cut}(\mathcal{V})={\sum }_{k=1}^{\mathcal{K}}\frac{\psi ({\mathcal{A}}_k,\overline{{\mathcal{A}}_k})}{\text{degree}({\mathcal{A}}_k)}\\ \text{degree}({\mathcal{A}}_k)={\sum }_{v^{(i)}\in {\mathcal{A}}_k}{\sum }_{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}\end{array}$$
最终将切分的选择问题转化为数学中的优化问题：
min ⁡ { A k } k = 1 K Normalized-Cut ( V ) \mathop{\min}\limits_{\{\mathcal A_k\}_{k=1}^{\mathcal K}} \text{Normalized-Cut}(\mathcal V) {Ak​}k=1K​min​Normalized-Cut(V)

引入指示向量

为了能够更方便地对优化问题进行求解，通常将优化函数的连加形式转化为矩阵的乘法形式。首先观察 { A k } k = 1 K \{\mathcal A_k\}_{k=1}^{\mathcal K} {Ak​}k=1K​，它表示结点子集的集合：
{ A k } k = 1 K ⇒ { A 1 , A 2 , ⋯   , A K } \{\mathcal A_k\}_{k=1}^{\mathcal K} \Rightarrow \{\mathcal A_1,\mathcal A_2,\cdots,\mathcal A_{\mathcal K}\} {Ak​}k=1K​⇒{A1​,A2​,⋯,AK​}
将这个 { A k } k = 1 K \{\mathcal A_k\}_{k=1}^{\mathcal K} {Ak​}k=1K​描述为指示向量($\text{Indicator Vector}$)的形式：

• 所谓‘指示向量’$y^{(i)}(i=1,2,\cdots ,N)$，就是描述结点$v^{(i)}$位于结点子集${\mathcal{A}}_k(k=1,2,\cdots ,\mathcal{K})$的信息。使用$\text{one-hot}$向量进行表达。
• 例如某结点$v^{(i)}$对应的指示向量$y^{(i)}$结果为$\underset{\mathcal{K}个元素}{\underbrace{(1,0,\cdots ,0)}}$,那么该向量表示为$v^{(i)}$属于${\mathcal{A}}_1$结点子集。随着划分结点子集数量的变化，$\text{one-hot}$向量的长度也随之发生变化。
  { y ( i ) ∈ { 0 , 1 } K ∑ k = 1 K y v ( i ) ∈ A k = 1 \begin{cases} y^{(i)} \in \{0,1\}^{\mathcal K} \\ \sum_{k=1}^{\mathcal K} y_{v^{(i)} \in \mathcal A_{k}} = 1 \end{cases} {y(i)∈{0,1}K∑k=1K​yv(i)∈Ak​​=1​

至此，使用一个$\mathcal{K}$维的$\text{one-hot}$向量表示样本$x^{(i)}$对应结点的归属信息，对于整个样本集合$\mathcal{X}$，对应的归属信息$\mathcal{Y}$可表示为：
$$\begin{array}{rl}\mathcal{Y}& =(y^{(1)},y^{(2)},\cdots ,y^{(N)}{)}^T\\ & ={\left[\begin{array}{c}{y}_1^{(1)},y_2^{(1)},\cdots ,y_{\mathcal{K}}^{(1)}\\ y_1^{(2)},y_2^{(2)},\cdots ,y_{\mathcal{K}}^{(2)}\\ ⋮\\ y_1^{(N)},y_2^{(N)},\cdots ,y_{\mathcal{K}}^{(N)}\end{array}\right]}_{N\times \mathcal{K}}\end{array}$$
最终关于优化问题可转化为如下形式：
$$\hat{\mathcal{Y}}=\underset{\mathcal{Y}}{\mathrm{argmin}}\text{Normalized-Cut}(\mathcal{V})$$

优化问题的化简过程

小插曲：观察$\text{Normalize-Cut}(\mathcal{V})$

对于$\text{Normalize-Cut}(\mathcal{V})$：
$$\begin{array}{rl}\text{Normalize-Cut}(\mathcal{V})& =\sum _{k=1}^{\mathcal{K}}\frac{\psi ({\mathcal{A}}_k,\overline{{\mathcal{A}}_k})}{\text{degree}({\mathcal{A}}_k)}\\ & =\sum _{k=1}^{\mathcal{K}}\frac{{\sum }_{m\ne k}{\sum }_{v^{(i)}\in {\mathcal{A}}_k}{\sum }_{v^{(j)}\in {\mathcal{A}}_m}{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}}{{\sum }_{v^{(i)}\in {\mathcal{A}}_k}{\sum }_{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}}\\ & =\sum _{k=1}^{\mathcal{K}}\sum _{v^{(i)}\in {\mathcal{A}}_k}\frac{{\sum }_{m\ne k}{\sum }_{v^{(j)}\in {\mathcal{A}}_m}{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}}{{\sum }_{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}}\end{array}$$
观察展开项，可以发现项$\frac{{\sum }_{m\ne k}{\sum }_{v^{(j)}\in {\mathcal{A}}_m}{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}}{{\sum }_{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}}\le 1$恒成立。并在当前结点子集${\mathcal{A}}_k$中只有$v^{(i)}$一个结点时取等。

化简过程

将$\text{Normalize-Cut}(\mathcal{V})$表示成矩阵运算的形式。这里将${\sum }_{k=1}^{\mathcal{K}}\frac{\psi ({\mathcal{A}}_k,\overline{{\mathcal{A}}_k})}{\text{degree}({\mathcal{A}}_k)}$中的每一项看作是某对角矩阵的主对角线元素，通过对该矩阵求迹的方式对$\text{Normalize-Cut}(\mathcal{V})$进行表示：
需要注意的是，矩阵的秩$(\text{Rank})$和矩阵的迹$(\text{Trace})$不是一个东西，矩阵的秩表示对角阵中非零元素的数目;而迹表示对角阵元素的和。
$$\begin{array}{rl}\text{Normalize-Cut}(\mathcal{V})& =\sum _{k=1}^{\mathcal{K}}\frac{\psi ({\mathcal{A}}_k,\overline{{\mathcal{A}}_k})}{\text{degree}({\mathcal{A}}_k)}\\ & =\text{tr}\left\{{\left[\begin{array}{cccc}\frac{\psi ({\mathcal{A}}_1,\overline{{\mathcal{A}}_1})}{\text{degree}({\mathcal{A}}_1)}& & & \\ & \frac{\psi ({\mathcal{A}}_2,\overline{{\mathcal{A}}_2})}{\text{degree}({\mathcal{A}}_2)}& & \\ & & \ddots & \\ & & & \frac{\psi ({\mathcal{A}}_{\mathcal{K}},\overline{{\mathcal{A}}_{\mathcal{K}}})}{\text{degree}({\mathcal{A}}_{\mathcal{K}})}\end{array}\right]}_{\mathcal{K}\times \mathcal{K}}\right\}\end{array}$$
可以继续将上述矩阵进行分解，分解成两个对角阵相乘的形式：

• 关于元素$\frac{1}{\text{degree}({\mathcal{A}}_k)}(k=1,2,\cdots ,\mathcal{K})$的矩阵，直接使用逆矩阵的形式表示。
• 为节省空间，$\text{Normalize-Cut}(\mathcal{V})$直接用$\mathcal{I}$进行表示。
  $$\begin{array}{rl}\mathcal{I}& =\text{tr}\left\{\underset{记作\mathcal{O}}{\underbrace{{\left[\begin{array}{cccc}\psi ({\mathcal{A}}_1,\overline{{\mathcal{A}}_1})& & & \\ & \psi ({\mathcal{A}}_2,\overline{{\mathcal{A}}_2})& & \\ & & \ddots & \\ & & & \psi ({\mathcal{A}}_{\mathcal{K}},\overline{{\mathcal{A}}_{\mathcal{K}}})\end{array}\right]}_{\mathcal{K}\times \mathcal{K}}}}\cdot \underset{记作\mathcal{P}}{\underbrace{{\left[\begin{array}{cccc}\text{degree}({\mathcal{A}}_1)& & & \\ & \text{degree}({\mathcal{A}}_2)& & \\ & & \ddots & \\ & & & \text{degree}({\mathcal{A}}_{\mathcal{K}})\end{array}\right]}_{\mathcal{K}\times \mathcal{K}}^{-1}}}\right\}\\ & =\text{tr}(\mathcal{O}\cdot {\mathcal{P}}^{-1})\end{array}$$

此时已经将优化问题转化为矩阵的表达形式，下一步通过 已知的划分出的结点子集 { A k } k = 1 K ⇒ Y \{\mathcal A_k\}_{k=1}^{\mathcal K} \Rightarrow \mathcal Y {Ak​}k=1K​⇒Y以及对应的权重矩阵$\mathcal{E}\Rightarrow \mathcal{W}=[{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}{]}_{N\times N}$来表示矩阵$\mathcal{O},\mathcal{P}$。
需要说明的点：为什么说'指示向量' { A k } k = 1 K ⇒ Y \{\mathcal A_k\}_{k=1}^{\mathcal K} \Rightarrow \mathcal Y {Ak​}k=1K​⇒Y是已知的。从流程上观察，整个过程是基于目标函数$\text{Normalize-Cut}(\mathcal{V})$的迭代过程，只有执行了划分之后，才能够计算出$\text{Normalize-Cut}(\mathcal{V})$的值，因而$\mathcal{Y}$在每次迭代过程中都是已知的，只不过初始状态划分效果不佳，$\text{Normalize-Cut}(\mathcal{V})$数值较大而已。通过不断减小$\text{Normalize-Cut}(\mathcal{V})$的值来优化划分方式$\Rightarrow \mathcal{Y}$.

矩阵$\mathcal{P}$的化简过程

重新观察$\mathcal{Y}$，以及${\mathcal{Y}}^T\mathcal{Y}$：
$$\begin{array}{rl}{\mathcal{Y}}^T\mathcal{Y}& ={\left[y^{(1)},y^{(2)},\cdots ,y^{(N)}\right]}_{\mathcal{K}\times N}\cdot {\left[y^{(1)},y^{(2)},\cdots ,y^{(N)}\right]}_{N\times \mathcal{K}}^T\\ & ={\left[\sum _{i=1}^N{y}^{(i)}[y^{(i)}{]}^T\right]}_{\mathcal{K}\times \mathcal{K}}\end{array}$$
由于$y^{(i)}$是一个$\text{one-hot}$向量，因而$y^{(i)}[y^{(i)}{]}^T$是一个只有一个元素是1的$\mathcal{K}\times \mathcal{K}$矩阵，并且这个元素一定在对角线的位置上，这个位置具体取决于$y^{(i)}$数值为1对应的列数。 因而${\mathcal{Y}}^T\mathcal{Y}$对应的$\mathcal{K}\times \mathcal{K}$矩阵内容可描述为：
其中$N_1$的物理意义是：$N$个样本中属于结点子集${\mathcal{A}}_1$的样本数量。也可表示成$N_1=|{\mathcal{A}}_1|={\sum }_{v^{(i)}\in {\mathcal{A}}_1}\cdot 1$,以此类推。
$$\begin{array}{rl}{\left[\sum _{i=1}^N{y}^{(i)}[y^{(i)}{]}^T\right]}_{\mathcal{K}\times \mathcal{K}}& ={\left[\begin{array}{cccc}{N}_1& & & \\ & N_2& & \\ & & \ddots & \\ & & & N_{\mathcal{K}}\end{array}\right]}_{\mathcal{K}\times \mathcal{K}}\sum _{k=1}^{\mathcal{K}}{N}_k=N\\ & ={\left[\begin{array}{cccc}{\sum }_{v^{(i)}\in {\mathcal{A}}_1}\cdot 1& & & \\ & {\sum }_{v^{(i)}\in {\mathcal{A}}_2}\cdot 1& & \\ & & \ddots & \\ & & & {\sum }_{v^{(i)}\in {\mathcal{A}}_{\mathcal{K}}}\cdot 1\end{array}\right]}_{\mathcal{K}\times \mathcal{K}}\end{array}$$
至此，我们完全可以使用${\mathcal{Y}}^T\mathcal{Y}$来描述矩阵$\mathcal{P}$了：

• 其中${\sum }_{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}$内部只有与$v^{(i)}$存在边相连的若干项是有值的，其余均是$0$.
• 由于${\sum }_{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}$是一个实数，并且$[y^{(i)}{]}^T$中不含$j$,直接将连加号带进去即可.
  $$\begin{array}{rl}\text{degree}({\mathcal{A}}_k)& =\sum _{v^{(i)}\in {\mathcal{A}}_k}\sum _{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}\\ & =\sum _{v^{(i)}\in {\mathcal{A}}_k}\sum _{j=1}^N\left\{[y^{(i)}{]}^T\cdot {\mathcal{W}}_{v^{(i)}\iff v^{(j)}}\cdot y^{(i)}\right\}\\ & =\sum _{v^{(i)}\in {\mathcal{A}}_k}[y^{(i)}{]}^T\left\{\sum _{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}\right\}{y}^{(i)}\\ \mathcal{P}& ={\left[\begin{array}{cccc}{\sum }_{v^{(i)}\in {\mathcal{A}}_1}{\sum }_{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}& & & \\ & {\sum }_{v^{(i)}\in {\mathcal{A}}_2}{\sum }_{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}& & \\ & & \ddots & \\ & & & {\sum }_{v^{(i)}\in {\mathcal{A}}_{\mathcal{K}}}{\sum }_{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}})\end{array}\right]}_{\mathcal{K}\times \mathcal{K}}\\ & =(y^{(1)},y^{(2)},\cdots ,y^{(N)}{)}_{\mathcal{K}\times N}\underset{记作\mathcal{D}}{\underbrace{{\left[\begin{array}{cccc}{\sum }_{j=1}^N{\mathcal{W}}_{v^{(1)}\iff v^{(j)}}& & & \\ & {\sum }_{j=1}^N{\mathcal{W}}_{v^{(2)}\iff v^{(j)}}& & \\ & & \ddots & \\ & & & {\sum }_{j=1}^N{\mathcal{W}}_{v^{(N)}\iff v^{(j)}})\end{array}\right]}_{N\times N}}}{\left(\begin{array}{c}{y}^{(1)}\\ y^{(2)}\\ ⋮\\ y^{(N)}\end{array}\right)}_{N\times \mathcal{K}}\\ & ={\mathcal{Y}}^T\mathcal{DY}\end{array}$$

继续观察矩阵$\mathcal{D}$，可以发现$\mathcal{D}$中的每一个元素均可以使用$\mathcal{W}$进行表示：

• 其中${\mathcal{W}}_i$表示权重矩阵的第$i$行;${\mathcal{I}}_{N\times 1}$表示元素均为1,并且长度为$N$的列向量.
• $\text{diag}(\mathcal{W}\cdot {\mathcal{I}}_{N\times 1})$表示将列向量$\mathcal{W}\cdot {\mathcal{I}}_{N\times 1}$中的所有元素按顺序放置在矩阵对角线位置，从而构成对角阵 -> 对角转化
  $$\{\begin{array}{l}{\sum }_{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}=[{\mathcal{W}}_i{]}_{1\times N}\cdot {\mathcal{I}}_{N\times 1}\\ \mathcal{D}=\text{diag}(\mathcal{W}\cdot {\mathcal{I}}_{N\times 1})\end{array}$$

矩阵$\mathcal{O}$的化简过程

至此，可以使用权重矩阵$\mathcal{W}$描述矩阵$\mathcal{P}$，继续观察矩阵$\mathcal{O}$：

• 首先观察矩阵$\mathcal{O}$中元素的表达形式，可以将其修改成如下形式：
  结点集合补集的定义：${\mathcal{A}}_k\cup \overline{{\mathcal{A}}_k}=\mathcal{V}$
  $$\begin{array}{rl}\psi ({\mathcal{A}}_k,\overline{{\mathcal{A}}_k})& =\psi ({\mathcal{A}}_k,\mathcal{V})-\psi ({\mathcal{A}}_k,{\mathcal{A}}_k)\\ & =\sum _{v^{(i)}\in {\mathcal{A}}_k}\sum _{j=1}^N{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}-\sum _{v^{(i)}\in {\mathcal{A}}_k}\sum _{v^{(j)}\in {\mathcal{A}}_k}{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}\\ & =\text{degree}({\mathcal{A}}_k)-\psi ({\mathcal{A}}_k,{\mathcal{A}}_k)\end{array}$$
• 对应的矩阵$\mathcal{O}$可表示成如下形式：
  $$\begin{array}{rl}\mathcal{O}& ={\left[\begin{array}{cccc}\psi ({\mathcal{A}}_1,\overline{{\mathcal{A}}_1})& & & \\ & \psi ({\mathcal{A}}_2,\overline{{\mathcal{A}}_2})& & \\ & & \ddots & \\ & & & \psi ({\mathcal{A}}_{\mathcal{K}},\overline{{\mathcal{A}}_{\mathcal{K}}})\end{array}\right]}_{\mathcal{K}\times \mathcal{K}}\\ & ={\left[\begin{array}{cccc}\text{degree}({\mathcal{A}}_1)& & & \\ & \text{degree}({\mathcal{A}}_2)& & \\ & & \ddots & \\ & & & \text{degree}({\mathcal{A}}_{\mathcal{K}})\end{array}\right]}_{\mathcal{K}\times \mathcal{K}}-\left[\begin{array}{cccc}\psi ({\mathcal{A}}_1,{\mathcal{A}}_1)& & & \\ & \psi ({\mathcal{A}}_2,{\mathcal{A}}_2)& & \\ & & \ddots & \\ & & & \psi ({\mathcal{A}}_{\mathcal{K}},{\mathcal{A}}_{\mathcal{K}})\end{array}\right]\end{array}$$

第一项我们认识，它就是${\mathcal{Y}}^T\mathcal{DY}$。在观察第二项之前，先认识一个$\mathcal{K}\times \mathcal{K}$的矩阵：${\mathcal{Y}}^T\mathcal{WY}$。先将${\mathcal{Y}}^T\mathcal{WY}$展开，其结果表示如下：
$$\begin{array}{rl}{\mathcal{Y}}^T\mathcal{WY}& ={\left(y^{(1)},y^{(2)},\cdots ,y^{(N)}\right)}_{\mathcal{K}\times N}{\left[\begin{array}{c}{\mathcal{W}}_{v^{(1)}\iff v^{(1)}},{\mathcal{W}}_{v^{(1)}\iff v^{(2)}},\cdots ,{\mathcal{W}}_{v^{(1)}\iff v^{(N)}}\\ {\mathcal{W}}_{v^{(2)}\iff v^{(1)}},{\mathcal{W}}_{v^{(2)}\iff v^{(2)}},\cdots ,{\mathcal{W}}_{v^{(2)}\iff v^{(N)}}\\ ⋮\\ {\mathcal{W}}_{v^{(N)}\iff v^{(1)}},{\mathcal{W}}_{v^{(N)}\iff v^{(2)}},\cdots ,{\mathcal{W}}_{v^{(N)}\iff v^{(N)}}\end{array}\right]}_{N\times N}{\left(\begin{array}{c}{y}^{(1)}\\ y^{(2)}\\ ⋮\\ y^{(N)}\end{array}\right)}_{N\times \mathcal{K}}\\ & ={\left[\sum _{i=1}^N{y}^{(i)}\cdot {\mathcal{W}}_{v^{(i)}\iff v^{(1)}}\cdots ,\sum _{i=1}^N{y}^{(i)}\cdot {\mathcal{W}}_{v^{(i)}\iff v^{(N)}}\right]}_{\mathcal{K}\times N}{\left(\begin{array}{c}{y}^{(1)}\\ y^{(2)}\\ ⋮\\ y^{(N)}\end{array}\right)}_{N\times \mathcal{K}}\\ & =\sum _{i=1}^N\sum _{j=1}^N{\left\{y^{(i)}[y^{(j)}{]}^T\cdot \underset{实数}{\underbrace{{\mathcal{W}}_{v^{(i)}\iff v^{(j)}}}}\right\}}_{\mathcal{K}\times \mathcal{K}}\end{array}$$
如果将上式的$\mathcal{K}\times \mathcal{K}$展开，可以表示成如下形式：
这里个人出现一个误区： { y ( i ) [ y ( j ) ] T } K × K \{y^{(i)}[y^{(j)}]^T\}_{\mathcal K \times \mathcal K} {y(i)[y(j)]T}K×K​在$i,j$不属于同一个结点集合时，其矩阵结果并不是全零元素。而是存在一个$1$元素。示例：如果$v^{(i)}\in {\mathcal{A}}_1,v^{(j)}\in {\mathcal{A}}_{\mathcal{K}}$,那么对应的 { y ( i ) [ y ( j ) ] T } K × K \{y^{(i)}[y^{(j)}]^T\}_{\mathcal K \times \mathcal K} {y(i)[y(j)]T}K×K​应该是这个的样子:
v ( i ) ∈ A 1 , v ( j ) ∈ A K ⇒ { y ( i ) [ y ( j ) ] T } K × K = ( 0 0 ⋯ 0 0 0 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 1 0 ⋯ 0 ) K × K Y T W Y = ( ∑ v ( i ) ∈ A 1 ∑ v ( j ) ∈ A 1 W v ( i ) ⇔ v ( j ) ∑ v ( i ) ∈ A 1 ∑ v ( j ) ∈ A 2 W v ( i ) ⇔ v ( j ) ⋯ ∑ v ( i ) ∈ A 1 ∑ v ( j ) ∈ A K W v ( i ) ⇔ v ( j ) ∑ v ( i ) ∈ A 2 ∑ v ( j ) ∈ A 1 W v ( i ) ⇔ v ( j ) ∑ v ( i ) ∈ A 2 ∑ v ( j ) ∈ A 2 W v ( i ) ⇔ v ( j ) ⋯ ∑ v ( i ) ∈ A 2 ∑ v ( j ) ∈ A K W v ( i ) ⇔ v ( j ) ⋮ ⋮ ⋱ ⋮ ∑ v ( i ) ∈ A K ∑ v ( j ) ∈ A 1 W v ( i ) ⇔ v ( j ) ∑ v ( i ) ∈ A K ∑ v ( j ) ∈ A 2 W v ( i ) ⇔ v ( j ) ⋯ ∑ v ( i ) ∈ A K ∑ v ( j ) ∈ A K W v ( i ) ⇔ v ( j ) ) K × K = [ ψ ( A 1 , A 1 ) ψ ( A 1 , A 2 ) ⋯ ψ ( A 1 , A K ) ψ ( A 2 , A 1 ) ψ ( A 2 , A 2 ) ⋯ ψ ( A 2 , A K ) ⋮ ⋮ ⋱ ⋮ ψ ( A K , A 1 ) ψ ( A K , A 2 ) ⋯ ψ ( A K , A K ) ] K × K \begin{aligned} & v^{(i)}\in\mathcal A_{1},v^{(j)} \in \mathcal A_{\mathcal K} \Rightarrow \{y^{(i)}[y^{(j)}]^T\}_{\mathcal K \times \mathcal K} = \begin{pmatrix} 0 & 0 &\cdots &0 \\ 0 & 0 & \cdots &0 \\ \vdots & \vdots & \ddots & \vdots\\ 1 & 0 & \cdots & 0 \end{pmatrix}_{\mathcal K \times \mathcal K} \\ \mathcal Y^T\mathcal W \mathcal Y & = \begin{pmatrix} \sum_{v^{(i)} \in \mathcal A_1}\sum_{v^{(j)} \in \mathcal A_1 \mathcal W_{v^{(i)} \Leftrightarrow v^{(j)}}} & \sum_{v^{(i)} \in \mathcal A_1}\sum_{v^{(j)} \in \mathcal A_2 \mathcal W_{v^{(i)} \Leftrightarrow v^{(j)}}} &\cdots &\sum_{v^{(i)} \in \mathcal A_1}\sum_{v^{(j)} \in \mathcal A_{\mathcal K} \mathcal W_{v^{(i)} \Leftrightarrow v^{(j)}}} \\ \sum_{v^{(i)} \in \mathcal A_2}\sum_{v^{(j)} \in \mathcal A_1 \mathcal W_{v^{(i)} \Leftrightarrow v^{(j)}}} & \sum_{v^{(i)} \in \mathcal A_2}\sum_{v^{(j)} \in \mathcal A_2 \mathcal W_{v^{(i)} \Leftrightarrow v^{(j)}}} & \cdots & \sum_{v^{(i)} \in \mathcal A_2}\sum_{v^{(j)} \in \mathcal A_{\mathcal K} \mathcal W_{v^{(i)} \Leftrightarrow v^{(j)}}} \\ \vdots & \vdots & \ddots & \vdots\\ \sum_{v^{(i)} \in \mathcal A_{\mathcal K}}\sum_{v^{(j)} \in \mathcal A_1 \mathcal W_{v^{(i)} \Leftrightarrow v^{(j)}}} & \sum_{v^{(i)} \in \mathcal A_{\mathcal K}}\sum_{v^{(j)} \in \mathcal A_2 \mathcal W_{v^{(i)} \Leftrightarrow v^{(j)}}} & \cdots & \sum_{v^{(i)} \in \mathcal A_{\mathcal K}}\sum_{v^{(j)} \in \mathcal A_{\mathcal K} \mathcal W_{v^{(i)} \Leftrightarrow v^{(j)}}} \end{pmatrix}_{\mathcal K \times \mathcal K} \\ & = \begin{bmatrix} \psi(\mathcal A_1,\mathcal A_1) & \psi(\mathcal A_1,\mathcal A_2) &\cdots &\psi(\mathcal A_1,\mathcal A_{\mathcal K}) \\ \psi(\mathcal A_2,\mathcal A_1) & \psi(\mathcal A_2,\mathcal A_2) & \cdots &\psi(\mathcal A_2,\mathcal A_{\mathcal K}) \\ \vdots & \vdots & \ddots & \vdots\\ \psi(\mathcal A_{\mathcal K},\mathcal A_1) & \psi(\mathcal A_{\mathcal K},\mathcal A_2) & \cdots & \psi(\mathcal A_{\mathcal K},\mathcal A_{\mathcal K}) \end{bmatrix}_{\mathcal K \times \mathcal K} \end{aligned} YTWY​v(i)∈A1​,v(j)∈AK​⇒{y(i)[y(j)]T}K×K​= ​00⋮1​00⋮0​⋯⋯⋱⋯​00⋮0​ ​K×K​= ​∑v(i)∈A1​​∑v(j)∈A1​Wv(i)⇔v(j)​​∑v(i)∈A2​​∑v(j)∈A1​Wv(i)⇔v(j)​​⋮∑v(i)∈AK​​∑v(j)∈A1​Wv(i)⇔v(j)​​​∑v(i)∈A1​​∑v(j)∈A2​Wv(i)⇔v(j)​​∑v(i)∈A2​​∑v(j)∈A2​Wv(i)⇔v(j)​​⋮∑v(i)∈AK​​∑v(j)∈A2​Wv(i)⇔v(j)​​​⋯⋯⋱⋯​∑v(i)∈A1​​∑v(j)∈AK​Wv(i)⇔v(j)​​∑v(i)∈A2​​∑v(j)∈AK​Wv(i)⇔v(j)​​⋮∑v(i)∈AK​​∑v(j)∈AK​Wv(i)⇔v(j)​​​ ​K×K​= ​ψ(A1​,A1​)ψ(A2​,A1​)⋮ψ(AK​,A1​)​ψ(A1​,A2​)ψ(A2​,A2​)⋮ψ(AK​,A2​)​⋯⋯⋱⋯​ψ(A1​,AK​)ψ(A2​,AK​)⋮ψ(AK​,AK​)​ ​K×K​​
很明显，${\mathcal{Y}}^T\mathcal{WY}$和$\mathcal{O}$中的第二项是不同的。但如果将${\mathcal{Y}}^T\mathcal{WY}$替代第二项，记作${\mathcal{O}}^{\prime }$。由于要求解的是$\text{tr}(\mathcal{O}\cdot {\mathcal{P}}^{-1})$，但是$\mathcal{P}$是对角矩阵(${\mathcal{P}}^{-1}$自然也是对角矩阵)，那么会出现这样的现象：
其中${\mathcal{O}}^{\prime }$和对角阵${\mathcal{P}}^{-1}$相乘，它仅影响对角线上的元素，对其他位置的元素虽然也影响，但其他位置我们并不关心，因为我们只关心$\text{tr}({\mathcal{O}}^{\prime }{\mathcal{P}}^{-1})$,也就是它主对角线上的元素和。
$$\begin{array}{rl}{\mathcal{O}}^{\prime }& ={\mathcal{Y}}^T\mathcal{DY}-{\mathcal{Y}}^T\mathcal{WY}\\ & ={\left[\begin{array}{cccc}\psi ({\mathcal{A}}_1,\overline{{\mathcal{A}}_1})& -\psi ({\mathcal{A}}_1,{\mathcal{A}}_2)& \cdots & -\psi ({\mathcal{A}}_1,{\mathcal{A}}_{\mathcal{K}})\\ -\psi ({\mathcal{A}}_2,{\mathcal{A}}_1)& \psi ({\mathcal{A}}_2,\overline{{\mathcal{A}}_2})& \cdots & -\psi ({\mathcal{A}}_2,{\mathcal{A}}_{\mathcal{K}})\\ ⋮& ⋮& \ddots & ⋮\\ -\psi ({\mathcal{A}}_{\mathcal{K}},{\mathcal{A}}_1)& -\psi ({\mathcal{A}}_{\mathcal{K}},{\mathcal{A}}_2)& \cdots & \psi ({\mathcal{A}}_{\mathcal{K}},\overline{{\mathcal{A}}_{\mathcal{K}}})\end{array}\right]}_{\mathcal{K}\times \mathcal{K}}\\ & \Rightarrow \text{tr}({\mathcal{O}}^{\prime }{\mathcal{P}}^{-1})=\text{tr}(\mathcal{O}{\mathcal{P}}^{-1})\end{array}$$

目标函数整理与拉普拉斯矩阵

至此，$\mathcal{O},\mathcal{P}$都可以使用$\mathcal{W},\mathcal{Y}$进行表示。关于目标函数可转化至如下形式：
矩阵的逆应该放在外面，上面也是，latex用的不好~，见笑。
$$\begin{array}{rl}\hat{\mathcal{Y}}& =\underset{\mathcal{Y}}{\mathrm{argmin}}\sum _{k=1}^{\mathcal{K}}\frac{\psi ({\mathcal{A}}_k,\overline{{\mathcal{A}}_k})}{\text{degree}({\mathcal{A}}_k)}\\ & =\underset{\mathcal{Y}}{\mathrm{argmin}}\text{tr}(\mathcal{O}{\mathcal{P}}^{-1})\\ & =\underset{\mathcal{Y}}{\mathrm{argmin}}\text{tr}({\mathcal{O}}^{\prime }{\mathcal{P}}^{-1})\\ & =\underset{\mathcal{Y}}{\mathrm{argmin}}\text{tr}\left[\underset{{\mathcal{O}}^{\prime }}{\underbrace{{\mathcal{Y}}^T(\mathcal{D}-\mathcal{W})\mathcal{Y}}}\cdot \underset{\mathcal{P}}{\underbrace{{\left({\mathcal{Y}}^T\mathcal{DY}\right)}^{-1}}}\right]\end{array}$$
通常令$\mathcal{L}=\mathcal{D}-\mathcal{W}$，其中$\mathcal{L}$也被称作拉普拉斯矩阵($\text{Laplacian Matrix}$)

相关参考：
机器学习-谱聚类（3）-模型的矩阵形式-Indicator Vector
机器学习-谱聚类（4）-模型的矩阵形式-对角矩阵
机器学习-谱聚类（5）-模型的矩阵形式-Laplacian Matrix