一、K-Means算法的基本原理
K-Means算法是较为经典的聚类算法，假设训练数据集XXX为：{x1,x2,⋯,xn}{x1,x2,⋯,xn}left { mathbf{x}_1,mathbf{x}_2,cdots , mathbf{x}_n right }，其中，每一个样本xjxj mathbf{x}_j为mmm维的向量。此时的样本为一个m×nm×nmtimes n的矩阵：
Xm×n=(x1x2⋯xn)=⎛⎝⎜⎜⎜⎜x1,1x2,1⋮xm,1x1,2x2,2⋮xm,2⋯⋯⋯x1,nx2,n⋮xm,n⎞⎠⎟⎟⎟⎟m×nXm×n=(x1x2⋯xn)=(x1,1x1,2⋯x1,nx2,1x2,2⋯x2,n⋮⋮⋮xm,1xm,2⋯xm,n)m×n
X_{mtimes n}=begin{pmatrix} mathbf{x}_{1} & mathbf{x}_{2} & cdots & mathbf{x}_{n} end{pmatrix}=begin{pmatrix} x_{1,1} & x_{1,2} & cdots & x_{1,n}\ x_{2,1} & x_{2,2} & cdots & x_{2,n}\ vdots & vdots & &vdots \ x_{m,1} & x_{m,2} & cdots & x_{m,n} end{pmatrix}_{mtimes n}
假设有kkk个类，分别为：{C1,⋯,Ck}{C1,⋯,Ck}left { C_1,cdots ,C_k right }。k-Means算法通过欧式距离的度量方法计算每一个样本xjxjmathbf{x}_{j}到质心之间的距离，并将其划分到较近的质心所属的类别中并重新计算质心，重复以上的过程，直到质心不再改变为止，上述的过程可以总结为：
- 初始化常数K，随机选取初始点为质心
- 重复计算以下过程，直到质心不再改变
- 计算样本与每个质心之间的相似度，将样本归类到最相似的类中
- 重新计算质心
- 输出最终的质心以及每个类
二、K-Means与矩阵分解的等价
2.1、K-Means的目标函数
K-Means的目标使得每一个样本xjxjmathbf{x}_{j}被划分到离质心uiuimathbf{u}_i最近的类别中，而质心为：
ui=∑xj∈Cixj#(xj∈Ci)ui=∑xj∈Cixj#(xj∈Ci)
mathbf{u}_i=frac{sum_{mathbf{x}_j in C_i}mathbf{x}_j}{# left ( mathbf{x}_j in C_i right )}
其中，∑xj∈Cixj∑xj∈Cixjsum_{mathbf{x}_j in C_i}mathbf{x}_j表示的是所有CiCiC_i类中的所有的样本的和，#(xj∈Ci)#(xj∈Ci)# left ( mathbf{x}_j in C_i right )表示的是类别CiCiC_i中的样本的个数。
最终使得质心不再改变，这就意味着每一个样本被划分到了最近的质心所属的类别中，即：
min∑i=1k∑j=1nzij‖‖xj−ui‖‖2min∑i=1k∑j=1nzij‖xj−ui‖2
min; sum_{i=1}^{k}sum_{j=1}^{n}z_{ij}left | mathbf{x}_j-mathbf{u}_i right |^2
其中，样本xjxjmathbf{x}_j是数据集Xm×nXm×nX_{mtimes n}的第jjj列。uiuimathbf{u}_i表示的是第iii个类别的聚类中心。假设Mm×kMm×kM_{mtimes k}为聚类中心构成的矩阵。矩阵Zk×nZk×nZ_{ktimes n}是由zijzijz_{ij}构成的0-1矩阵，zijzijz_{ij}为：
zij={10 if xi∈Ci otherwise zij={1 if xi∈Ci0 otherwise
z_{ij}=begin{cases} 1 & text{ if } mathbf{x}_iin C_i \ 0 & text{ otherwise } end{cases}
上述的优化目标可以表示成：(在下面会做证明)
min‖X−MZ‖2min‖X−MZ‖2
min; left | X-MZright |^2
2.2、矩阵分解的等价
2.2.1、优化目标一
对于上述的最小化问题：
min∑i=1k∑j=1nzij‖‖xj−ui‖‖2min∑i=1k∑j=1nzij‖xj−ui‖2
min; sum_{i=1}^{k}sum_{j=1}^{n}z_{ij}left | mathbf{x}_j-mathbf{u}_i right |^2
则有：
∑i,jzij‖‖xj−ui‖‖2=∑i,jzij(xTjxj−2xTjui uTiui)=∑i,jzijxTjxj−2∑i,jzijxTjui ∑i,jzijuTiui∑i,jzij‖xj−ui‖2=∑i,jzij(xjTxj−2xjTui uiTui)=∑i,jzijxjTxj−2∑i,jzijxjTui ∑i,jzijuiTui
begin{matrix} sum_{i,j}z_{ij}left | mathbf{x}_j-mathbf{u}_i right |^2\ =sum_{i,j}z_{ij}left ( mathbf{x}_j^Tmathbf{x}_j-2mathbf{x}_j^Tmathbf{u}_i mathbf{u}_i^Tmathbf{u}_i right )\ =sum_{i,j}z_{ij}mathbf{x}_j^Tmathbf{x}_j-2sum_{i,j}z_{ij}mathbf{x}_j^Tmathbf{u}_i sum_{i,j}z_{ij}mathbf{u}_i^Tmathbf{u}_i end{matrix}
下面分别对上式中的三项进行计算:
- 对于∑i,jzijxTjxj∑i,jzijxjTxjsum_{i,j}z_{ij}mathbf{x}_j^Tmathbf{x}_j：
∑i,jzijxTjxj=∑i,jzij‖‖xj‖‖2=∑j‖‖xj‖‖2=tr[XTX]∑i,jzijxjTxj=∑i,jzij‖xj‖2=∑j‖xj‖2=tr[XTX]
begin{align*} sum_{i,j}z_{ij}mathbf{x}_j^Tmathbf{x}_j &= sum_{i,j}z_{ij}left | mathbf{x}_j right |^2\ &= sum_{j}left | mathbf{x}_j right |^2\ &= trleft [ X^TX right ] end{align*}
已知：∑izij=1∑izij=1sum_{i}z_{ij}=1。
- 对于∑i,jzijxTjui∑i,jzijxjTuisum_{i,j}z_{ij}mathbf{x}_j^Tmathbf{u}_i：
∑i,jzijxTjui=∑i,jzij∑lxljuli=∑j,lxlj∑iulizij=∑j,lxlj(MZ)lj=∑j∑l(XT)jl(MZ)lj=∑j(XTMZ)jj=tr[XTMZ]∑i,jzijxjTui=∑i,jzij∑lxljuli=∑j,lxlj∑iulizij=∑j,lxlj(MZ)lj=∑j∑l(XT)jl(MZ)lj=∑j(XTMZ)jj=tr[XTMZ]
begin{align*} sum_{i,j}z_{ij}mathbf{x}_j^Tmathbf{u}_i &= sum_{i,j}z_{ij}sum_{l}x_{lj}u_{li}\ &= sum_{j,l}x_{lj}sum_{i}u_{li}z_{ij}\ &= sum_{j,l}x_{lj}left ( MZ right )_{lj}\ &= sum_{j}sum_{l}left ( X^T right )_{jl}left ( MZ right )_{lj}\ &= sum_{j}left ( X^TMZ right )_{jj}\ &= trleft [ X^TMZ right ] end{align*}
- 对于∑i,juTiui∑i,juiTuisum_{i,j}mathbf{u}_i^Tmathbf{u}_i：
∑i,jzijuTiui=∑i,jzij‖ui‖2=∑i‖ui‖2ni∑i,jzijuiTui=∑i,jzij‖ui‖2=∑i‖ui‖2ni
begin{align*} sum_{i,j}z_{ij}mathbf{u}_i^Tmathbf{u}_i &= sum_{i,j}z_{ij}left | mathbf{u}_i right |^2\ &= sum_{i} left | mathbf{u}_i right |^2n_i end{align*}
最终：
∑i,jzij‖‖xj−ui‖‖2=tr[XTX]−2tr[XTMZ] ∑i‖ui‖2ni∑i,jzij‖xj−ui‖2=tr[XTX]−2tr[XTMZ] ∑i‖ui‖2ni
sum_{i,j}z_{ij}left | mathbf{x}_j-mathbf{u}_i right |^2=trleft [ X^TX right ]-2trleft [ X^TMZ right ] sum_{i} left | mathbf{u}_i right |^2n_i
2.2.2、优化目标二
对于上述的优化目标的矩阵写法：
min‖X−MZ‖2min‖X−MZ‖2
min; left | X-MZright |^2
则有：
‖X−MZ‖2=tr[(X−MZ)T(X−MZ)]=tr[XTX]−2tr[XTMZ] tr[ZTMTMZ]‖X−MZ‖2=tr[(X−MZ)T(X−MZ)]=tr[XTX]−2tr[XTMZ] tr[ZTMTMZ]
begin{align*} left | X-MZright |^2 &= trleft [ left ( X-MZ right )^Tleft ( X-MZ right ) right ]\ &= trleft [ X^TX right ]-2trleft [ X^TMZ right ] trleft [ Z^TM^TMZ right ] end{align*}
对于tr[ZTMTMZ]tr[ZTMTMZ]trleft [ Z^TM^TMZ right ]：
tr[ZTMTMZ]=tr[MTMZZT]=∑i(MTMZZT)ii=∑i∑l(MTM)il(ZZT)li=∑i(MTM)ii(ZZT)ii=∑i‖ui‖2nitr[ZTMTMZ]=tr[MTMZZT]=∑i(MTMZZT)ii=∑i∑l(MTM)il(ZZT)li=∑i(MTM)ii(ZZT)ii=∑i‖ui‖2ni
begin{align*} trleft [ Z^TM^TMZ right ] &= trleft [ M^TMZZ^T right ]\ &= sum_{i}left ( M^TMZZ^T right )_{ii}\ &= sum_{i}sum_{l}left ( M^TM right )_{il}left ( ZZ^T right )_{li}\ &= sum_{i}left ( M^TM right )_{ii}left ( ZZ^T right )_{ii}\ &= sum_{i}left | mathbf{u}_i right |^2n_{i} end{align*}
因此得证，两种优化目标等价。
2.2.3、求最优的矩阵MMM
最终的目标是求得聚类中心，因此，对矩阵MMM求偏导数：
∂∂M‖X−MZ‖2=∂∂M[tr[XTX]−2tr[XTMZ] tr[ZTMTMZ]]=2(MZZT−XZT)∂∂M‖X−MZ‖2=∂∂M[tr[XTX]−2tr[XTMZ] tr[ZTMTMZ]]=2(MZZT−XZT)
begin{align*} frac{partial }{partial M}left | X-MZright |^2 &= frac{partial }{partial M}left [ trleft [ X^TX right ]-2trleft [ X^TMZ right ] trleft [ Z^TM^TMZ right ] right ]\ &=2left ( MZZ^T-XZ^T right ) end{align*}
令其为000：
M=XZT(ZZT)−1M=XZT(ZZT)−1
M=XZ^Tleft ( ZZ^T right )^{-1}
即可得：
ui=∑jzijxj∑jzij=1ni∑xj∈Cixjui=∑jzijxj∑jzij=1ni∑xj∈Cixj
mathbf{u}_i=frac{sum_{j}z_{ij}mathbf{x}_j}{sum_{j}z_{ij}}=frac{1}{n_i}sum_{mathbf{x}_jin C_i}mathbf{x}_j
三、结论
K-Means算法等价于求下述问题的最小值：
minZ‖‖X−XZT(ZZT)−1Z‖‖2minZ‖X−XZT(ZZT)−1Z‖2
underset{Z}{min}left | X-XZ^Tleft ( ZZ^T right )^{-1}Z right |^2
s.t.zij∈{0,1},∑jzij=1s.t.zij∈{0,1},∑jzij=1
s.t.; z_{ij}in left { 0,1 right },; sum_{j}z_{ij}=1
参考文献
- 《k-Means Clustering Is Matrix Factorization》
