On the Equivalence of Nonnegative Matrix Factorization and Spectral Clustering,SIAM,2005

一、单词

simultaneous 同时的，同步的； bipartitle graph 二分图； symmetric 对称的；

coherent 相关的，一致的； specify 指定，详细说明； derive 导出，派生；

comprehensive 综合的，全面的； pave 铺路，铺设； prototype 原型，标准；

centroid 矩心，质心，形心； characterize 描绘...的特性/特征；

二、内容总结

1.非负矩阵分解（NMF）形式

(1) 一般形式：$Xapprox FG^{T}$

(2) 对称形式：$Xapprox HH^{T}$

(3) 带权重形式：$Xapprox HSH^{T}$

2.核心K-means和非负分解的等价

核心K-means的目标函数：

$J_{K}=sum_{k=1}^{K}sum_{iin C_{k}}left | x_{i}-m_{k} right |^{2}$

利用指示矩阵H，$H=(\mathbf{h}_1,...,\mathbf{h}_K), \mathbf{h}_{k}^{T}\mathbf{h}_{\ell}=\delta _{k\ell}$, 其中 $\mathbf{h}_k=(0,...,0,\overbrace{1,...,1}^{n_k},0,...,0)^T/n_{k}^{1/2}$，可将基本形式变为：

$max limits_{H^TH=I,Hgeq 0}J_{W}(H)=Tr(H^TX^TXH)=Tr(H^TWH)$，

其中$W=X^TX$，此时求出H就可以确定聚类结果。

下面证明它与非负矩阵分解的等价性：

[begin{eqnarray*} H&=&argmax limits_{H^TH=I,Hgeq0}Tr(H^TWH)\&=&argmin limits_{H^TH=I,Hgeq0}-2Tr(H^TWH)\&=&argmin limits_{H^TH=I,Hgeq0}-2Tr(H^TWH)+left| H^TH right|^2\&=&argmin limits_{H^TH=I,Hgeq0}left| W right|^2-2Tr(H^TWH)+left| H^TH right|^2\&=&argmin limits_{H^TH=I,Hgeq0}left| W-H^TH right|^2 end{eqnarray*}]

即$Wapprox HH^T$,与非负分解的第2种形式相同。

3.谱聚类和非负分解的等价性

我们选择NCut作为谱聚类的代表，写出NCut的目标函数为：

[J_{NC}=sum_{ell}^{K}frac{mathbf{h}_{ell}^{T}(D-W)mathbf{h}_ell}{mathbf{h}_{ell}^{T}Dmathbf{h}_ell}=sum_{ell=1}^{K}mathbf{z}_{ell}^{T}(I-widetilde{W})mathbf{z}_{ell}]

其中 $\mathbf{z}_{\ell}=D^{1/2}\mathbf{h}_{\ell}/\left\| D^{1/2}\mathbf{h}_{\ell} \right \|, Z=(\mathbf{z}_{1},...,\mathbf{z}_{K}),  \widetilde{W}=D^{-1/2}WD^{-1/2}$.

因为第一项是常量，所以最小化目标函数就变成了:

$\max \limits_{Z^TZ=I,Z\geq 0}Tr(Z^T\widetilde{W}Z)$

由核心K-means与非负矩阵分解的等价性的证明可知上式等价于

$min limits_{Zgeq 0}left | widetilde{W}-Z^TZ right |^2$

所以 $widetilde{W}approx Z^TZ$,  与非负分解等价。

4.计算对称NMF的算法

(1)对于$W=HH^T$ ，更新规则是

[H_{ik}leftarrow H_{ik}(1-beta +beta frac{(WH)_{ik}}{(HH^TH)_{ik})}]

(2) 对于 $W=HSH^T$，更新规则是

[S_{ik}leftarrow S_{ik}frac{(H^TW)_{ik}}{(HH^TSH^TH)_{ik}}]

[H_{ik}leftarrow H_{ik}(1-beta +beta frac{(WHS)_{ik}}{(HSH^THS)_{ik})}]

最后附上原文：

On the Equivalence of Nonnegative Matrix Factorization and Spectral .pdf