【机器学习】K-Means 聚类是特殊的矩阵分解（Matrix Factorization）问题

---

原文是：《k-Means Clustering Is Matrix Factorization》

本博客是该论文的阅读笔记，不免有很多细节不对之处。

还望各位看官能够见谅，欢迎批评指正。

更多相关博客请猛戳：http://blog.csdn.net/cyh_24

如需转载，请附上本文链接：http://blog.csdn.net/cyh_24/article/details/50408884

论文证明了传统的K-Means算法的目标函数可以被表达成数据矩阵与其低阶数据矩阵之间差异的Frobenius范数。

简要的说，K-Means 聚类其实是一种矩阵分解问题。

K-Means的推导，我想大家都已经很清楚了，这里不细说。它的目标函数，可以定义如下：

<script type="math/tex; mode=display" id="MathJax-Element-1">\sum_{i=1}^k \sum_{j=1}^n z_{ij} ||x_j-\mu_i||^2</script>

如果能够把目标函数表达成如下形式，那么也就证明了K-Means聚类是特殊的矩阵分解问题。

<script type="math/tex; mode=display" id="MathJax-Element-2">?=||X-MZ||^2</script> <script type="math/tex; mode=display" id="MathJax-Element-3">?=||X-XZ^T(ZZ^T)^{-1}Z||^2</script>

先不用深究，下文会详细介绍，先注意几个变量的意义：
数据集 X∈Rm∗n <script type="math/tex" id="MathJax-Element-4">X\in R^{m*n}</script> 是向量 xi∈Rm <script type="math/tex" id="MathJax-Element-5">x_i \in R^m</script> 的矩阵；
M∈Rm∗k <script type="math/tex" id="MathJax-Element-6">M\in R^{m*k}</script>，是类中心点 μi∈Rm <script type="math/tex" id="MathJax-Element-7">\mu_i \in R^m</script> 的矩阵；
Z∈Rk∗n <script type="math/tex" id="MathJax-Element-8">Z\in R^{k*n}</script>，是二值指示变量 zij <script type="math/tex" id="MathJax-Element-9">z_{ij}</script>的矩阵；若 xj∈Ci <script type="math/tex" id="MathJax-Element-10">x_j \in C_i</script>，则 zij=1 <script type="math/tex" id="MathJax-Element-11">z_{ij}=1</script>，否则 zij=0 <script type="math/tex" id="MathJax-Element-12">z_{ij}=0</script>；

数学符号说明

1. xi <script type="math/tex" id="MathJax-Element-13">x_i</script> 表示矩阵 X <script type="math/tex" id="MathJax-Element-14">X</script> 的第 j<script type="math/tex" id="MathJax-Element-15">j</script>-th列向量（好像与平常的相反了）；
2. X <script type="math/tex" id="MathJax-Element-16">X</script>的第(l,j)<script type="math/tex" id="MathJax-Element-17">(l,j)</script>的元素可以写成 xlj <script type="math/tex" id="MathJax-Element-18">x_{lj}</script>或者 (X)lj <script type="math/tex" id="MathJax-Element-19">(X)_{lj}</script> ；
3. ||x|| <script type="math/tex" id="MathJax-Element-20">||x||</script> 表示欧式距离，
4. ||X|| <script type="math/tex" id="MathJax-Element-21">||X||</script> 则表示矩阵的 Frobenius 范数，
5. 其Frobenius 范数平方形式定义如下：
   
   ||X||2=∑l,jx2lj=∑j||xj||2=∑jxTjxj=∑j(XTX)jj=tr[XTX]
   <script type="math/tex; mode=display" id="MathJax-Element-22">||X||^2 = \sum_{l,j}x_{lj}^2 = \sum_j ||x_j||^2 = \sum_j x_j^T x_j = \sum_j (X^TX)_{jj} = tr[ X^T X]</script>

推导过程

假设，数据集 X <script type="math/tex" id="MathJax-Element-23">X</script> 可以分成 k<script type="math/tex" id="MathJax-Element-24">k</script> 个类 C1,...Ck <script type="math/tex" id="MathJax-Element-25">C_1,...C_k</script>， 分别对应的类中心点是 μ1,...μk <script type="math/tex" id="MathJax-Element-26">\mu_1,...\mu_k</script>；
zij <script type="math/tex" id="MathJax-Element-27">z_{ij}</script> 是二值指示变量：若 xj∈Ci <script type="math/tex" id="MathJax-Element-28">x_j \in C_i</script>，则 zij=1 <script type="math/tex" id="MathJax-Element-29">z_{ij}=1</script>，否则 zij=0 <script type="math/tex" id="MathJax-Element-30">z_{ij}=0</script>；
那么，显然可以得到：

<script type="math/tex; mode=display" id="MathJax-Element-31">\sum_i z_{ij} = 1</script>

而每行总和刚好是这个类中的样本个数：

<script type="math/tex; mode=display" id="MathJax-Element-32">\sum_jz_{ij}=n_i=|C_i|</script>

由于 zji∈{0,1} <script type="math/tex" id="MathJax-Element-33">z_{ji} \in \{0,1\}</script>，所以 Z <script type="math/tex" id="MathJax-Element-34">Z</script>的每一列只有一个1<script type="math/tex" id="MathJax-Element-35">1</script>，所以：

<script type="math/tex; mode=display" id="MathJax-Element-36">z_{ij}\cdot z_{i^\prime j}=1\;\;(i=i^\prime)\;\;or\;\;0\;（otherwise）</script>

因此， ZZT <script type="math/tex" id="MathJax-Element-37">ZZ^T</script> 是一个对角矩阵，并且：

<script type="math/tex; mode=display" id="MathJax-Element-38">(ZZ^T)_{ii^\prime}=\sum_j(Z)_{ij}(Z^T)_{ji^\prime}=\sum_j z_{ij}z_{i^\prime j}</script> <script type="math/tex; mode=display" id="MathJax-Element-39">=n_i, \;\;if\;i=i^\prime</script> <script type="math/tex; mode=display" id="MathJax-Element-40">=0,\;otherwise</script>

Step 1: 将目标函数左边展开

Step 2: 将目标函数中间项展开

接下来，我们看目标函数的中间项。作为矩阵Frobenius范数的平方，它可以按如下方式写：

从之前的结论中，我们可以快速发现： T1=T4andT2=T5 <script type="math/tex" id="MathJax-Element-41">T_1=T_4 \;\;and\;\; T_2=T_5</script>. 所以，只要 T3=T6 <script type="math/tex" id="MathJax-Element-42">T_3=T_6</script>，那么我们假设的目标函数的第一个等式就成立了。所以，现在的目标就是证明 T3=T6 <script type="math/tex" id="MathJax-Element-43">T_3 = T_6</script>.
来看一下 T6 <script type="math/tex" id="MathJax-Element-44">T_6</script>，可以得到：

<script type="math/tex; mode=display" id="MathJax-Element-45">tr[Z^TM^TMZ] = tr[M^TMZZ^T]</script>

<script type="math/tex; mode=display" id="MathJax-Element-46">=\sum_i(M^TMZZ^T)_{ii}</script>

<script type="math/tex; mode=display" id="MathJax-Element-47">=\sum_i\sum_l(M^TM)_{il}(ZZ^T)_{li}</script>

<script type="math/tex; mode=display" id="MathJax-Element-48">=\sum_i(MTM)_{ii}(ZZ^T)_{ii}</script>

<script type="math/tex; mode=display" id="MathJax-Element-49">=\sum_i||\mu_i||^2n_i</script>

在上面的推导中，我们用到了 ZZT <script type="math/tex" id="MathJax-Element-50">ZZ^T</script> 是对角阵的特性。到此， T3=T6 <script type="math/tex" id="MathJax-Element-51">T_3=T_6</script>证明完毕，因此，目标函数的第一个等式也就证明完毕了。

Step 3: 消除矩阵 M <script type="math/tex" id="MathJax-Element-52">M</script>

现在的任务就是证明第二个等式。
回顾一下我们的目的，就是讲目标函数最小化， 因为已经证明了第一个等式，所以，其实也就是让||X−MZ||2<script type="math/tex" id="MathJax-Element-53">||X-MZ||^2</script> 最小化：

<script type="math/tex; mode=display" id="MathJax-Element-54">\frac{\delta}{\delta M}||X-MZ||^2</script> <script type="math/tex; mode=display" id="MathJax-Element-55">=\frac{\delta}{\delta M}[tr[X^TX]-2tr[X^TMZ]+tr[Z^TM^TMZ]]</script> <script type="math/tex; mode=display" id="MathJax-Element-56">=2(MZZ^T-XZ^T)</script>

令偏导等于0，可以得到：

<script type="math/tex; mode=display" id="MathJax-Element-57">M=XZ^T(ZZ^T)^{-1}</script>

代入目标函数第二个等式，就证明完毕了。

结论

我们在上面用了一大堆令人眩晕的代数表达式，终于说明了K-Means聚类问题可以被理解成是如下的受约束的矩阵分解问题：

<script type="math/tex; mode=display" id="MathJax-Element-58">目标函数\; \sum_{i=1}^k \sum_{j=1}^n z_{ij} ||x_j-\mu_i||^2 \;\;等价于\;\;min_Z||X-XZ^T(ZZ^T)Z||^2</script>

<script type="math/tex; mode=display" id="MathJax-Element-59">s.t.\;\;\;z_{ij}\in\{0,1\}</script>

<script type="math/tex; mode=display" id="MathJax-Element-60">\sum_jz_{ij}=1</script>