一、K-Means算法的基本原理
K-Means算法是较为经典的聚类算法，假设训练数据集X X 为：{x1,x2,⋯,xn}{x1,x2,⋯,xn}，其中，每一个样本xj x j 为m m 维的向量。此时的样本为一个m×nm×n的矩阵：
Xm×n=(x1x2⋯xn)=⎛⎝⎜⎜⎜⎜x1,1x2,1⋮xm,1x1,2x2,2⋮xm,2⋯⋯⋯x1,nx2,n⋮xm,n⎞⎠⎟⎟⎟⎟m×n X m × n = ( x 1 x 2 ⋯ x n ) = ( x 1 , 1 x 1 , 2 ⋯ x 1 , n x 2 , 1 x 2 , 2 ⋯ x 2 , n ⋮ ⋮ ⋮ x m , 1 x m , 2 ⋯ x m , n ) m × n
假设有k k 个类，分别为：{C1,⋯,Ck}{C1,⋯,Ck}。k-Means算法通过欧式距离的度量方法计算每一个样本xj x j 到质心之间的距离，并将其划分到较近的质心所属的类别中并重新计算质心，重复以上的过程，直到质心不再改变为止，上述的过程可以总结为：
- 初始化常数K，随机选取初始点为质心
- 重复计算以下过程，直到质心不再改变
- 计算样本与每个质心之间的相似度，将样本归类到最相似的类中
- 重新计算质心
- 输出最终的质心以及每个类
二、K-Means与矩阵分解的等价
2.1、K-Means的目标函数
K-Means的目标使得每一个样本xj x j 被划分到离质心ui u i 最近的类别中，而质心为：
ui=∑xj∈Cixj#(xj∈Ci) u i = ∑ x j ∈ C i x j # ( x j ∈ C i )
其中，∑xj∈Cixj ∑ x j ∈ C i x j 表示的是所有Ci C i 类中的所有的样本的和，#(xj∈Ci) # ( x j ∈ C i ) 表示的是类别Ci C i 中的样本的个数。
最终使得质心不再改变，这就意味着每一个样本被划分到了最近的质心所属的类别中，即：
min∑i=1k∑j=1nzij‖‖xj−ui‖‖2 m i n ∑ i = 1 k ∑ j = 1 n z i j ‖ x j − u i ‖ 2
其中，样本xj x j 是数据集Xm×n X m × n 的第j j 列。uiui表示的是第i i 个类别的聚类中心。假设Mm×kMm×k为聚类中心构成的矩阵。矩阵Zk×n Z k × n 是由zij z i j 构成的0-1矩阵，zij z i j 为：
zij={10 if xi∈Ci otherwise z i j = { 1 if x i ∈ C i 0 otherwise
上述的优化目标可以表示成：(在下面会做证明)
min‖X−MZ‖2 m i n ‖ X − M Z ‖ 2
2.2、矩阵分解的等价
2.2.1、优化目标一
对于上述的最小化问题：
min∑i=1k∑j=1nzij‖‖xj−ui‖‖2 m i n ∑ i = 1 k ∑ j = 1 n z i j ‖ x j − u i ‖ 2
则有：
∑i,jzij‖‖xj−ui‖‖2=∑i,jzij(xTjxj−2xTjui+uTiui)=∑i,jzijxTjxj−2∑i,jzijxTjui+∑i,jzijuTiui ∑ i , j z i j ‖ x j − u i ‖ 2 = ∑ i , j z i j ( x j T x j − 2 x j T u i + u i T u i ) = ∑ i , j z i j x j T x j − 2 ∑ i , j z i j x j T u i + ∑ i , j z i j u i T u i
下面分别对上式中的三项进行计算:
- 对于∑i,jzijxTjxj ∑ i , j z i j x j T x j ：
∑i,jzijxTjxj=∑i,jzij‖‖xj‖‖2=∑j‖‖xj‖‖2=tr[XTX] ∑ i , j z i j x j T x j = ∑ i , j z i j ‖ x j ‖ 2 = ∑ j ‖ x j ‖ 2 = t r [ X T X ]
已知：∑izij=1 ∑ i z i j = 1 。
- 对于∑i,jzijxTjui ∑ i , j z i j x j T 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 , j z i j x j T u i = ∑ i , j z i j ∑ l x l j u l i = ∑ j , l x l j ∑ i u l i z i j = ∑ j , l x l j ( M Z ) l j = ∑ j ∑ l ( X T ) j l ( M Z ) l j = ∑ j ( X T M Z ) j j = t r [ X T M Z ]
- 对于∑i,juTiui ∑ i , j u i T u i ：
∑i,jzijuTiui=∑i,jzij‖ui‖2=∑i‖ui‖2ni ∑ i , j z i j u i T u i = ∑ i , j z i j ‖ u i ‖ 2 = ∑ i ‖ u i ‖ 2 n i
最终：
∑i,jzij‖‖xj−ui‖‖2=tr[XTX]−2tr[XTMZ]+∑i‖ui‖2ni ∑ i , j z i j ‖ x j − u i ‖ 2 = t r [ X T X ] − 2 t r [ X T M Z ] + ∑ i ‖ u i ‖ 2 n i
2.2.2、优化目标二
对于上述的优化目标的矩阵写法：
min‖X−MZ‖2 m i n ‖ X − M Z ‖ 2
则有：
‖X−MZ‖2=tr[(X−MZ)T(X−MZ)]=tr[XTX]−2tr[XTMZ]+tr[ZTMTMZ] ‖ X − M Z ‖ 2 = t r [ ( X − M Z ) T ( X − M Z ) ] = t r [ X T X ] − 2 t r [ X T M Z ] + t r [ Z T M T M Z ]
对于tr[ZTMTMZ] t r [ Z T M T M Z ] ：
tr[ZTMTMZ]=tr[MTMZZT]=∑i(MTMZZT)ii=∑i∑l(MTM)il(ZZT)li=∑i(MTM)ii(ZZT)ii=∑i‖ui‖2ni t r [ Z T M T M Z ] = t r [ M T M Z Z T ] = ∑ i ( M T M Z Z T ) i i = ∑ i ∑ l ( M T M ) i l ( Z Z T ) l i = ∑ i ( M T M ) i i ( Z Z T ) i i = ∑ i ‖ u i ‖ 2 n i
因此得证，两种优化目标等价。
2.2.3、求最优的矩阵M M
最终的目标是求得聚类中心，因此，对矩阵MM求偏导数：
∂∂M‖X−MZ‖2=∂∂M[tr[XTX]−2tr[XTMZ]+tr[ZTMTMZ]]=2(MZZT−XZT) ∂ ∂ M ‖ X − M Z ‖ 2 = ∂ ∂ M [ t r [ X T X ] − 2 t r [ X T M Z ] + t r [ Z T M T M Z ] ] = 2 ( M Z Z T − X Z T )
令其为0 0 ：
M=XZT(ZZT)−1M=XZT(ZZT)−1
即可得：
ui=∑jzijxj∑jzij=1ni∑xj∈Cixj u i = ∑ j z i j x j ∑ j z i j = 1 n i ∑ x j ∈ C i x j
三、结论
K-Means算法等价于求下述问题的最小值：
minZ‖‖X−XZT(ZZT)−1Z‖‖2 m i n Z ‖ X − X Z T ( Z Z T ) − 1 Z ‖ 2
s.t.zij∈{0,1},∑jzij=1 s . t . z i j ∈ { 0 , 1 } , ∑ j z i j = 1
参考文献
- 《k-Means Clustering Is Matrix Factorization》