谱聚类的原理

谱聚类

谱聚类算法流程：
i n p u t :     X = { x 1 , x 2 , . . . , x n }    o u t p u t :     C = { c 1 , c 2 , . . . c k 2 }     （ 1 ）根据输入的相似矩阵生成方式构建样本的相似矩阵 S （ 2 ）根据相似矩阵 S 构建邻接矩阵 W ，构建度矩阵 D         （ 3 ）计算出拉普拉斯矩阵 L                                             （ 4 ）构建标准化后的拉普拉斯矩阵 D − 1 2 L D − 1 2                 （ 5 ）计算最小的 D − 1 2 L D − 1 2 k 1 个特征值所各自对应的特征 向量 f （ 6 ）将各自对应的特征向量 f 组成的矩阵进行标准化，       最终组成 n × k 1 维的特征矩阵 F （ 7 ）对 F 中的每一行作为一个 k 1 维的样本，共 n 个样本， 用输入的聚类方法进行聚类，聚类维数为 k 2 。 （ 8 ）得到簇划分 ( c 1 , . . . , c k 2 )                                          input:\ \ \ X=\{x_1,x_2,...,x_n \}\ \ \\ output:\ \ \ C=\{c_1,c_2,...c_{k2} \}\ \ \ \\ \\ （1）根据输入的相似矩阵生成方式构建样本的相似矩阵S\\ \\ （2）根据相似矩阵S构建邻接矩阵W，构建度矩阵D\ \ \ \ \ \ \ \\ \\ （3）计算出拉普拉斯矩阵L\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \\ （4）构建标准化后的拉普拉斯矩阵D^{-\frac12}LD^{-\frac12}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ \\ （5）计算最小的D^{-\frac12}LD^{-\frac12}k_1个特征值所各自对应的特征\\向量f \\ \\ （6）将各自对应的特征向量f组成的矩阵进行标准化，\ \ \ \ \ \ \\最终组成n×k_1维的特征矩阵F\\ \\ （7）对F中的每一行作为一个k1维的样本，共n个样本，\\用输入的聚类方法进行聚类，聚类维数为k2。\\ \\ （8）得到簇划分(c_1,...,c_{k2})\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ input:   X={ x1​,x2​,...,xn​}  output:   C={ c1​,c2​,...ck2​}   （1）根据输入的相似矩阵生成方式构建样本的相似矩阵S（2）根据相似矩阵S构建邻接矩阵W，构建度矩阵D       （3）计算出拉普拉斯矩阵L                                           （4）构建标准化后的拉普拉斯矩阵D−21​LD−21​               （5）计算最小的D−21​LD−21​k1​个特征值所各自对应的特征向量f（6）将各自对应的特征向量f组成的矩阵进行标准化，      最终组成n×k1​维的特征矩阵F（7）对F中的每一行作为一个k1维的样本，共n个样本，用输入的聚类方法进行聚类，聚类维数为k2。（8）得到簇划分(c1​,...,ck2​)                                        
一般情况下，$k_1$是等于$k_2$的

谱聚类思想

​ 谱聚类的思想来源于图论，它把待聚类的数据集中的每一个样本看做是图中一个顶点，这些顶点连接在一起，连接的这些边上有权重，权重的大小表示这些样本之间的相似程度。同一类的顶点它们的相似程度很高，在图论中体现为同一类的顶点中连接它们的边的权重很大，不在同一类的顶点连接它们的边的权重很小。于是谱聚类的最终目标就是找到一种切割图的方法，使得切割之后的各个子图内的权重很大，子图之间的权重很小。

Graph-based（带权重的无向图）
样本数据 :   X = ( x 1 , . . . , x N ) ⊤ 无向图 :   G = { V , E } 顶点集 :   V = { 1 , 2 , . . . , N } ⇔ X 边集 :   E : s i m i l a r i t y    m a t r i x ( a f f i m t y    m a t r i x ) W = [ w 11 w 12 . . . w 1 N w 21 w 22 . . . w 2 N . . . . . . . . . . . . w N 1 w N 2 . . . w N N ] = [ w i j ] , 1 ≤ i , j ≤ N 其中 w i j = { K ( x i , x j ) = e x p { − ∣ ∣ x i − x j ∣ ∣ 2 2 2 θ 2 } if  ( i , j ) ∈ E 0 if  ( i , j ) ∉ E 顶点 i 的度 :   d i = ∑ j = 1 N w i j 度矩阵 : D = d i a g ( W 1 N ) = [ d 1 0 . . . 0 0 d 2 . . . 0 . . . . . . . . . . . . 0 0 . . . d N ] = [ ∑ j = 1 N w 1 j 0 . . . 0 0 ∑ j = 1 N w 2 j . . . 0 . . . . . . . . . . . . 0 0 . . . ∑ j = 1 N w N j ] L a p l a c i a n   M a t r i x : L = D − W 样本数据: \ X=(x_1,...,x_N)^\top\\ \\ 无向图:\ G=\{V,E\}\\ \\ 顶点集:\ V=\{1,2,...,N\}⇔X\\ \\ 边集:\ E:similarity\ \ matrix(affimty\ \ matrix)\\ \\ W= \begin{bmatrix} w_{11} & w_{12} & ... & w_{1N} \\ w_{21} & w_{22} & ... & w_{2N}\\ ... & ... & ... & ...\\ w_{N1} & w_{N2} & ... & w_{NN} \end{bmatrix} =[w_{ij}],1≤i,j≤N\\ \\ 其中w_{ij}= \begin{cases} K(x_i,x_j)=exp\{-\frac{||x_i-x_j||_2^2}{2\theta ^2} \} & \text{if } (i,j)∈E \\ \\ 0 & \text{if } (i,j)∉E \\ \end{cases}\\ \\ 顶点i的度:\ d_i=\sum_{j=1}^Nw_{ij}\\ \\ 度矩阵:D=diag(W\mathbf{1}_N)= \begin{bmatrix} d_1 & 0 & ... & 0 \\ 0 & d_2 & ... & 0\\ ... & ... & ... & ...\\ 0 & 0 & ... & d_N \end{bmatrix}= \begin{bmatrix} \sum_{j=1}^Nw_{1j} & 0 & ... & 0 \\ 0 & \sum_{j=1}^Nw_{2j} & ... & 0\\ ... & ... & ... & ...\\ 0 & 0 & ... & \sum_{j=1}^Nw_{Nj} \end{bmatrix}\\ \\ Laplacian \ Matrix:L=D-W 样本数据: X=(x1​,...,xN​)⊤无向图: G={ V,E}顶点集: V={ 1,2,...,N}⇔X边集: E:similarity  matrix(affimty  matrix)W= ​w11​w21​...wN1​​w12​w22​...wN2​​............​w1N​w2N​...wNN​​ ​=[wij​],1≤i,j≤N其中wij​=⎩ ⎨ ⎧​K(xi​,xj​)=exp{ −2θ2∣∣xi​−xj​∣∣22​​}0​if (i,j)∈Eif (i,j)∈/E​顶点i的度: di​=j=1∑N​wij​度矩阵:D=diag(W1N​)= ​d1​0...0​0d2​...0​............​00...dN​​ ​= ​∑j=1N​w1j​0...0​0∑j=1N​w2j​...0​............​00...∑j=1N​wNj​​ ​Laplacian Matrix:L=D−W

定义：
$$\begin{gathered} A\subset V,B\subset V,A\cap B=\varnothing \\ \to W(A,B)=\sum _{i\in A,j\in B}{w}_{ij} \end{gathered}$$
假如一共K个类别:
$$Cut(V)=Cut(A_1,...,A_K)=\sum _{k=1}^{K}W(A_k,{\overline{A}}_k)=\sum _{k=1}^{K}W(A_k,V)-\sum _{k=1}^{K}W(A_k,A_k)$$
目标：
m i n   { A k } k = 1 K N c u t ( V ) \underset{\{A_k\}_{k=1}^K}{min\ }Ncut(V) { Ak​}k=1K​min ​Ncut(V)
Ncut的定义：
$$\begin{gathered} cut(V)=\sum _{k=1}^{K}W(A_k,{\overline{A}}_k) \\ \to Ncut=\sum _{k=1}^K\frac{W(A_k,{\overline{A}}_k)}{\Delta } \\ \Delta =degree(A_k)=\sum _{i\in A_k}{d}_i{d}_i=\sum _{j=1}^N{w}_{ij} \\ \to Ncut=\sum _{k=1}^K\frac{W(A_k,{\overline{A}}_k)}{{\sum }_{i\in A_k}{d}_i}{d}_i=\sum _{j=1}^N{w}_{ij} \\ =\sum _{k=1}^K\frac{W(A_k,V)-W(A_k,A_k)}{{\sum }_{i\in A_k}{d}_i} \\ =\sum _{k=1}^K\frac{W(A_k,V)-W(A_k,A_k)}{{\sum }_{i\in A_k}{\sum }_{j=1}^N{w}_{ij}} \end{gathered}$$
Model
m i n   { A k } k = 1 K N c u t ( V ) = m i n   { A k } k = 1 K ∑ k = 1 K W ( A k , A ‾ k ) ∑ i ∈ A k d i → { A k } k = 1 K = a r g m i n   { A k } k = 1 K N c u t ( V ) \underset{\{A_k\}_{k=1}^K}{min\ }Ncut(V)=\underset{\{A_k\}_{k=1}^K}{min\ }\sum_{k=1}^K\frac{W(A_k,\overline A_k)}{\sum_{i∈A_k}d_i}\\ \\ \\ →\{A_k\}_{k=1}^K=arg \underset{\{A_k\}_{k=1}^K}{min\ }Ncut(V) { Ak​}k=1K​min ​Ncut(V)={ Ak​}k=1K​min ​k=1∑K​∑i∈Ak​​di​W(Ak​,Ak​)​→{ Ak​}k=1K​=arg{ Ak​}k=1K​min ​Ncut(V)
indicator vector：
{ y i ∈ { 0 , 1 } K ∑ j = 1 K y i j = 1           y i = [ y i 1 y i 2 . . . y i K ]          y i j = 1 ⇔ 第  i 个样本属于第  j 个类别 \begin{cases} y_i ∈\{0,1\}^K \\ \\ \sum_{j=1}^Ky_{ij}=1 \\ \end{cases}\ \ \ \ \ \ \ \ \ y_i= \begin{bmatrix} y_{i1}\\ y_{i2}\\ ... \\ y_{iK} \end{bmatrix} \ \ \ \ \ \ \ \ \\ y_{ij}=1⇔第\ i个样本属于第\ j个类别 ⎩ ⎨ ⎧​yi​∈{ 0,1}K∑j=1K​yij​=1​         yi​= ​yi1​yi2​...yiK​​ ​        yij​=1⇔第 i个样本属于第 j个类别

$$\begin{gathered} Y=[y_1,...y_K{]}_{N\times K}^{\top } \\ 将问题模型转换:\hat{Y}=arg\underset{\hat{Y}}{\min }Ncut(V) \end{gathered}$$

​ 将问题模型转换: $\hat{Y}=arg\underset{\hat{Y}}{\min }Ncut(V)$

将Ncut转换成矩阵的形式：
$$\begin{gathered} Ncut=\sum _{k=1}^K\frac{W(A_k,{\overline{A}}_k)}{{\sum }_{i\in A_k}{d}_i} \\ =Tr\left[\begin{array}{cccc}\frac{W(A_1,{\overline{A}}_1)}{{\sum }_{i\in A_1}{d}_i}& 0& ...& 0\\ 0& \frac{W(A_2,{\overline{A}}_2)}{{\sum }_{i\in A_2}{d}_i}& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& \frac{W(A_K,{\overline{A}}_K)}{{\sum }_{i\in A_K}{d}_i}\end{array}\right] \\ =Tr\left[\begin{array}{cccc}W(A_1,{\overline{A}}_1)& 0& ...& 0\\ 0& W(A_2,{\overline{A}}_2)& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& W(A_K,{\overline{A}}_K)\end{array}\right]{\left[\begin{array}{cccc}{\sum }_{i\in A_1}{d}_i& 0& ...& 0\\ 0& {\sum }_{i\in A_2}{d}_i& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& {\sum }_{i\in A_K}{d}_i\end{array}\right]}^{-1} \end{gathered}$$

$$\begin{gathered} 记O_{K\times K}=\left[\begin{array}{cccc}W(A_1,{\overline{A}}_1)& 0& ...& 0\\ 0& W(A_2,{\overline{A}}_2)& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& W(A_K,{\overline{A}}_K)\end{array}\right] \\ {P}_{K\times K}=\left[\begin{array}{cccc}{\sum }_{i\in A_1}{d}_i& 0& ...& 0\\ 0& {\sum }_{i\in A_2}{d}_i& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& {\sum }_{i\in A_K}{d}_i\end{array}\right] \end{gathered}$$

现在问题转化为：$Ncut(V)=Tr(O{P}^{-1})$

已知W、Y，求O、P：

先求解P：
$$\begin{gathered} Y^{\top }Y=[y_1,...y_N]\left[\begin{array}{c}{y}_1^T\\ y_2^T\\ ...\\ y_N^T\end{array}\right]=\sum _{i=1}^N{y}_i{y}_i^T={\left[\begin{array}{cccc}{N}_1& 0& ...& 0\\ 0& N_2& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& N_K\end{array}\right]}_{K\times K}= \\ {\left[\begin{array}{cccc}{\sum }_{i\in A_1}1& 0& ...& 0\\ 0& {\sum }_{i\in A_2}1& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& {\sum }_{i\in A_K}1\end{array}\right]}_{K\times K} \end{gathered}$$
$N_k$ 的含义：在N个样本中，属于类别k的样本个数。${\sum }_{k=1}^N{N}_k=N,N_k=|A_k|={\sum }_{i\in A_k}1$
$$\begin{gathered} \sum _{i=1}^N{y}_i{d}_i{y}_i^T=y_1{d}_1{y}_1^T+y_2{d}_2{y}_2^T...+y_N{d}_N{y}_N^T=Y^{T}DY \\ {P}_{K\times K}=\left[\begin{array}{cccc}{\sum }_{i\in A_1}{d}_i& 0& ...& 0\\ 0& {\sum }_{i\in A_2}{d}_i& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& {\sum }_{i\in A_K}{d}_i\end{array}\right]=Y^{T}DY \\ 其中,D=\left[\begin{array}{cccc}{d}_1& 0& ...& 0\\ 0& d_2& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& d_N\end{array}\right]=diag(W{1}_N)=\left[\begin{array}{cccc}{\sum }_{j=1}^N{w}_{1j}& 0& ...& 0\\ 0& {\sum }_{j=1}^N{w}_{2j}& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& {\sum }_{j=1}^N{w}_{Nj}\end{array}\right] \end{gathered}$$
所以我们求解的P为：
$$\begin{gathered} P=Y^{T}DY \\ 其中,D=diag(W{1}_N) \end{gathered}$$
再求解O：
$$\begin{gathered} O_{K\times K}=\left[\begin{array}{cccc}W(A_1,{\overline{A}}_1)& 0& ...& 0\\ 0& W(A_2,{\overline{A}}_2)& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& W(A_K,{\overline{A}}_K)\end{array}\right] \\ W(A_k,\overline{A_k})=\underset{{\sum }_{i\in A_k}{d}_i}{\underbrace{W(A_k,V)}}-\underset{{\sum }_{i\in A_k}{\sum }_{j\in A_k}{w}_{ij}}{\underbrace{W(A_k,A_k)}} \\ \to O=\left[\begin{array}{cccc}{\sum }_{i\in A_1}{d}_i& 0& ...& 0\\ 0& {\sum }_{i\in A_2}{d}_i& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& {\sum }_{i\in A_K}{d}_i\end{array}\right]-\left[\begin{array}{cccc}W(A_1,A_1)& 0& ...& 0\\ 0& W(A_2,A_2)& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& W(A_K,A_K)\end{array}\right] \end{gathered}$$
前面的矩阵我们知道:$Y^{T}DY$, 再来看后面部分:
$$\left[\begin{array}{cccc}W(A_1,A_1)& 0& ...& 0\\ 0& W(A_2,A_2)& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& W(A_K,A_K)\end{array}\right]$$

$$=\left[\begin{array}{cccc}{\sum }_{i\in A_1}{\sum }_{j\in A_1}{w}_{ij}& 0& ...& 0\\ 0& {\sum }_{i\in A_2}{\sum }_{j\in A_2}{w}_{ij}& ...& 0\\ ...& ...& ...& ...\\ 0& ...& ...& {\sum }_{i\in A_K}{\sum }_{j\in A_K}{w}_{ij}\end{array}\right]$$

猜想后半部分是否等于$Y^{T}WY$ 验证一下：
$$\begin{gathered} Y^{T}WY维度是K\times K维 \\ {Y}^{T}WY=[y_1,...y_N]\left[\begin{array}{cccc}{w}_{11}& w_{12}& ...& w_{1N}\\ w_{21}& w_{22}& ...& w_{2N}\\ ...& ...& ...& ...\\ w_{N1}& w_{N2}& ...& w_{NN}\end{array}\right]\left[\begin{array}{c}{y}_1^T\\ y_2^T\\ ...\\ y_N^T\end{array}\right] \\ =[\sum _{i=1}^N{y}_i{w}_{i1},...,\sum _{i=1}^N{y}_i{w}_{Ni}]\left[\begin{array}{c}{y}_1^T\\ y_2^T\\ ...\\ y_N^T\end{array}\right] \\ =\sum _{i=1}^N\sum _{j=1}^N{y}_i{w}_{ij}{y}_i^T=\sum _{i=1}^N\sum _{j=1}^N{y}_i{y}_i^T{w}_{ij} \\ =\left[\begin{array}{cccc}{\sum }_{i\in A_1}{\sum }_{j\in A_1}{w}_{ij}& {\sum }_{i\in A_1}{\sum }_{j\in A_2}{w}_{ij}& ...& {\sum }_{i\in A_1}{\sum }_{j\in A_K}{w}_{ij}\\ {\sum }_{i\in A_2}{\sum }_{j\in A_1}{w}_{ij}& {\sum }_{i\in A_2}{\sum }_{j\in A_2}{w}_{ij}& ...& {\sum }_{i\in A_2}{\sum }_{j\in A_K}{w}_{ij}\\ ...& ...& ...& ...\\ {\sum }_{i\in A_K}{\sum }_{j\in A_1}{w}_{ij}& {\sum }_{i\in A_K}{\sum }_{j\in A_2}{w}_{ij}& ...& {\sum }_{i\in A_K}{\sum }_{j\in A_K}{w}_{ij}\end{array}\right] \end{gathered}$$
观察上式和O的后半部分：
$$\left[\begin{array}{cccc}{\sum }_{i\in A_1}{\sum }_{j\in A_1}{w}_{ij}& 0& ...& 0\\ 0& {\sum }_{i\in A_2}{\sum }_{j\in A_2}{w}_{ij}& ...& 0\\ ...& ...& ...& ...\\ 0& ...& ...& {\sum }_{i\in A_K}{\sum }_{j\in A_K}{w}_{ij}\end{array}\right]$$

$$\left[\begin{array}{cccc}{\sum }_{i\in A_1}{\sum }_{j\in A_1}{w}_{ij}& {\sum }_{i\in A_1}{\sum }_{j\in A_2}{w}_{ij}& ...& {\sum }_{i\in A_1}{\sum }_{j\in A_K}{w}_{ij}\\ {\sum }_{i\in A_2}{\sum }_{j\in A_1}{w}_{ij}& {\sum }_{i\in A_2}{\sum }_{j\in A_2}{w}_{ij}& ...& {\sum }_{i\in A_2}{\sum }_{j\in A_K}{w}_{ij}\\ ...& ...& ...& ...\\ {\sum }_{i\in A_K}{\sum }_{j\in A_1}{w}_{ij}& {\sum }_{i\in A_K}{\sum }_{j\in A_2}{w}_{ij}& ...& {\sum }_{i\in A_K}{\sum }_{j\in A_K}{w}_{ij}\end{array}\right]$$

我们发现，这两个矩阵对角线元素是相同的，又因为我们是对迹求最小，即只考虑对角线的元素。所以将O的后半部分换成$Y^TWY $并不影响我们的结果

记 $O^{\prime }=Y^{T}DY-Y^{T}WY$ 那么$O^{\prime }P$相当于对$O^{\prime }$的对角线做一些变化。那么就有$Tr(OP)=Tr(O^{\prime }P)$。

至此我们解出了$O$ ，并且提出了用$O^{\prime }$ 代替$O$ 可以达到同样的目的。
$$O^{\prime }=Y^{T}DY-Y^{T}WY$$

我们最终的优化问题变为：
$$\begin{gathered} \hat{Y}=arg\underset{\hat{Y}}{\min }Tr(Y^T(D-W)Y(Y^{T}DY{)}^{-1}) \\ =\hat{Y}=arg\underset{\hat{Y}}{\min }Tr(Y^{T}LY(Y^{T}DY{)}^{-1}) \\ 这里L=D-W是拉普拉斯矩阵 \end{gathered}$$

To minimaze $Tr(Y^{T}LY(Y^{T}DY{)}^{-1})$

$Tr(Y^{T}LY(Y^{T}DY{)}^{-1})$

其中$Y\in R^{N\times K}$ ，每一行是ONE-HOT，表示第i行属于哪一类。$Y$ 形如：
$$\left[\begin{array}{ccccccc}0& ...& 0& 1& 0& ...& 0\\ 0& ...& 1& 0& 0& ...& 0\\ ...& ...& ...& ...& ...& ...& ...\\ 0& ...& 0& 0& 0& ...& 1\\ 1& ...& 0& 1& 0& ...& 0\end{array}\right]$$
记：
$$\begin{gathered} P=Y^{T}DY=diag(\sum _{i\in A_1}{d}_i,\sum _{i\in A_2}{d}_i,...,\sum _{i\in A_K}{d}_i)=diag(p_1,p_2,...,p_k) \\ 原式=Tr(Y^{T}LY{P}^{-1})=Tr(Y^{T}LY{P}^{-\frac{1}{2}}{P}^{-\frac{1}{2}})=Tr(P^{-\frac{1}{2}}{Y}^{T}LY{P}^{-\frac{1}{2}}) \end{gathered}$$
记：
$$\begin{gathered} H=Y{P}^{-\frac{1}{2}},H^T=P^{-\frac{1}{2}}{Y}^T \\ {H}^{T}H=P^{-\frac{1}{2}}{Y}^{T}Y{P}^{-\frac{1}{2}}=P^{-\frac{1}{2}}I{P}^{-\frac{1}{2}}=P^{-1} \end{gathered}$$

$$原式=Tr(H^{T}LH)$$
定理1：

对于半正定矩阵L， 特征值（eigenvalue）：$0\le {\lambda }_1\le {\lambda }_2\le ...\le {\lambda }_n$

​ 特征基（eigbasis）： { v ‾ 1 , v ‾ 2 , . . . , v ‾ n } \{\overline v_1,\overline v_2,...,\overline v_n\} { v1​,v2​,...,vn​} →Orthonormal，标准正交化之后的特征向量

当$\mathbf{x}\in R^N,and{\mathbf{x}}^T\mathbf{x}=1$ 时，${\mathbf{x}}^{T}L\mathbf{x}$ 的最小值在$\mathbf{x}={\overline{v}}_1$ 时取到。

proof：
$$\begin{gathered} \mathbf{x}可以用eigbasis表示,因为eigbasis是orthonormal \\ \mathbf{x}=c_1{\overline{v}}_1+c_2{\overline{v}}_2+...+c_n{\overline{v}}_n \\ L\mathbf{x}=\lambda \mathbf{x}=c_1{\lambda }_1{\overline{v}}_1+c_2{\lambda }_2{\overline{v}}_2+...+c_n{\lambda }_n{\overline{v}}_n \\ \to {\mathbf{x}}^{T}L\mathbf{x}=c_1^2{\lambda }_1+c_2^2{\lambda }_2+...+c_n^2{\lambda }_n \\ 因为{\mathbf{x}}^T\mathbf{x}=1\to c_1^2+c_2^2+...+c_n^2 \\ \to {\mathbf{x}}^{T}L\mathbf{x}=c_1^2{\lambda }_1+c_2^2{\lambda }_2+...+c_n^2{\lambda }_n\ge {\lambda }_1 \\ 当c_1^2=1,c_i=0,i\ne 1时等号成立\iff \mathbf{x}={\overline{v}}_{1}or\mathbf{x}=-{\overline{v}}_1 \end{gathered}$$
定理2：

对于半正定矩阵L， 特征值（eigenvalue）：$0\le {\lambda }_1\le {\lambda }_2\le ...\le {\lambda }_n$

​ 特征基（eigbasis）： { v ‾ 1 , v ‾ 2 , . . . , v ‾ n } \{\overline v_1,\overline v_2,...,\overline v_n\} { v1​,v2​,...,vn​} →Orthonormal，标准正交化之后的特征向量

当$F\in R^{N\times K},and{F}^{T}F=I$ 时，$Tr(F^{T}LF)$ 的最小值在$F=[{\overline{v}}_1,{\overline{v}}_2,...,{\overline{v}}_K]$ 时取到

proof:
$$\begin{gathered} DenoteF=[f_1,f_2,...,f_K] \\ Tr(F^{T}LF)=\sum _{i=1}^K{f}_i^{T}L{f}_i \\ 由于定理2f_1={\overline{v}}_1,f_2={\overline{v}}_2,...,f_n={\overline{v}}_n时,Tr(F^{T}LF)最小 \end{gathered}$$
因为$F^{T}F=I$，所以F是orthonormal matrix，故不能每列都是${\overline{v}}_1$

原始优化问题$Tr(H^{T}LH)$ 并没有$H^{T}H=I$的性质，无法用定理2，于是对H做一些变换。

$$\begin{gathered} H^{T}DH=P^{-\frac{1}{2}}{Y}^{T}DY{P}^{-\frac{1}{2}}=P^{-\frac{1}{2}}P{P}^{-\frac{1}{2}}=I \\ 记F=D^{\frac{1}{2}}H\to F^{T}F=(D^{\frac{1}{2}}H{)}^T{D}^{\frac{1}{2}}H=H^T{D}^{\frac{1}{2}}{D}^{\frac{1}{2}}H=H^{T}DH=I \\ 则H=D^{-\frac{1}{2}}F \\ \to Tr(H^{T}LH)=Tr(F^T{D}^{-\frac{1}{2}}L{D}^{-\frac{1}{2}}F),F^{T}F=I \end{gathered}$$
至此我们得到最终的优化目标：
$$Tr(F^T{D}^{-\frac{1}{2}}L{D}^{-\frac{1}{2}}F),F^{T}F=I$$
在解出的F上再做一次k-means，最终求得Y