k-means是一种广泛使用的聚类算法。k-means算法是基于相似性的无监督算法，其通过比较样本之间的相似性，将较为相似的样本划分到同一类中。
相似性的度量
对于样本$X$和$Y$，要度量其相似性，我们定义距离函数$d(X,Y)$来表示样本$X$和样本$Y$之间的相似性。常用的距离函数有闵可夫斯基距离（Minkowski Distance）、曼哈顿距离（Manhattan Distance）和欧氏距离（Euclidean Distance）。
假设有两个点$P$和$Q$，其对应的坐标分别为：
\begin{equation}
\begin{aligned}
P &= (x_1, x_2, \cdots, x_n) \in \mathbb{R}^n \\
Q &= (y_1, y_2, \cdots, y_n) \in \mathbb{R}^n
\end{aligned}
\tag{1}
\end{equation}
则$P$和$Q$之间的闵可夫斯基距离定义为：
\begin{equation}
d(P, Q) = \left( \sum_{i = 1}^n \left(x_i - y_i \right)^p \right)^{\frac{1}{p}}
\tag{2}
\end{equation}
$P$和$Q$之间的曼哈顿距离定义为：
\begin{equation}
d(P, Q) = \sum_{i = 1}^{n} | x_i - y_ i|
\tag{3}
\end{equation}
$P$和$Q$之间的欧氏距离定义为：
\begin{equation}
d(P, Q) = \sqrt{\sum_{i = 1}^{n} \left( x_i - y_i \right)^2}
\tag{4}
\end{equation}
k-means算法原理
k-means是基于数据划分的无监督聚类算法。首先定义聚类类别数$k$，然后随机初始化$k$个聚类中心，通过计算每一个样本与聚类中心之间的相似度，将样本点划分到最相似的类别中。
我们假设有$m$个样本$\{ X^{(1)}, X^{(2)}, \cdots, X^{(m)} \}$。其中，$X^{(i)}$表示第$i$个样本，每一个样本中包含$n$个特征$ X^{(i)} =\{ x_1^{(i)}, x_2^{(i)}, \cdots, x_n^{(i)} \} $。首先初始化$k$个聚类中心，通过每个样本与$k$个聚类中心之间的相似度，确定每个样本所属类别，再通过每个类别中的样本重新计算每个类的聚类中心，重复这样的过程，直到聚类中心不再改变，最终确定每个样本所属的类别以及每个类的聚类中心。
k-means算法与矩阵分解
假设训练数据集$X$中有$m$个样本$\{ X^{(1)}, X^{(2)}, \cdots, X^{(m)} \}$。其中，每一个样本$X^{(i)}$为$n$维的向量，此时样本可表示成一个$m \times n$的矩阵：
\begin{equation}
X_{m \times n} = \left( X^{(1)}, X^{(2)}, \cdots, X^{(m)} \right) =
\left[
\begin{matrix}
x_1^{(1)} & x_2^{(2)} & \cdots & x_n^{(1)} \\
x_1^{(2)} & x_2^{(2)} & \cdots & x_n^{(2)} \\
\vdots & \vdots & \cdots & \vdots \\
x_1^{(m)} & x_2^{(m)} & \cdots & x_n^{(m)}
\end{matrix}
\right]
\tag{5}
\end{equation}
假设有$k$个类，分别为：$C_1, C_2, \cdots, C_k$。k-means算法目标是使得每一个样本$X^{(i)}$被划分到最相似的类别中，利用每个类别中的样本重新计算聚类中心$C_k$：
\begin{equation}
C_k^\prime = \frac{ \sum_{X^{(i)} \in C_k} X^{(i)}} {\#(X^{(i)} \in C_k)}
\tag{6}
\end{equation}
其中$\sum_{X^{(i)} \in C_k} X^{(i)}$表示的是$C_k$类中的所有样本的特征向量的和，$\#(X^{(i)} \in C_k)$表示的是类别$C_k$中的样本个数。
k-means算法停止条件是最终的聚类中心不再改变。此时，所有样本被划分到了最近的聚类中心所属的类别中。
\begin{equation}
min \sum_{i = 1}^{m} \sum_{j = 1}^{k} z_{ij} \left|\left| X^{(i)} -C_j \right|\right|^2
\tag{7}
\end{equation}
其中，样本$X^{(i)}$是数据集$X_{m \times n}$的第$i$行。$C_j$表示的是第$j$个类别的聚类中心。假设$M_{k \times n}$为$k$个聚类中心构成的矩阵。矩阵$Z_{n \times k}$是由$z_{ij}$构成的$0-1$矩阵，$z_{ij}$为：
\begin{equation}
z_{ij} = \left\{
\begin{aligned}
&1, X^{(i)} \in C_j \\
&0, otherwise
\end{aligned}
\right.
\tag{8}
\end{equation}
\begin{equation}
\begin{aligned}
\because \sum_{i = 1}^{m} \sum_{j = 1}^{k} z_{ij} \left|\left| X^{(i)} -C_j \right|\right|^2
&= (X^{(i)} - C_j)(X^{(i)} - C_j)^T \\
&= \sum_{i = 1}^{m} \sum_{j = 1}^{k} z_{ij} \left( (X^{(i)})(X^{(i)})^T - 2X^{(i)}C_j^T + C_jC_j^T \right) \\
&= \sum_{i = 1}^{m} \sum_{j = 1}^{k} z_{ij} (X^{(i)})(X^{(i)})^T - 2\sum_{i = 1}^{m} \sum_{j = 1}^{k} z_{ij}X^{(i)}C_j^T + \sum_{i = 1}^{m} \sum_{j = 1}^{k} z_{ij}C_jC_j^T \\
&= \sum_{i = 1}^{m} \sum_{j = 1}^{k} z_{ij} \left|\left| X^{(i)} \right|\right|^2 - 2\sum_{i = 1}^{m} \sum_{j = 1}^{k} z_{ij} \sum_{t = 1}^n X_t^{(i)}C_{jt} + \sum_{i = 1}^{m} \sum_{j = 1}^{k} z_{ij} \left|\left| C_j \right|\right|^2
\end{aligned}
\tag{9}
\end{equation}
又：
\begin{equation}
\because \sum_j z_{ij} = 1
\tag{10}
\end{equation}
即每一个样本$X^{(i)}$只属于一个类别。则：
\begin{equation}
\begin{aligned}
\sum_{i = 1}^{m} \sum_{j = 1}^{k} z_{ij} \left|\left| X^{(i)} -C_j \right|\right|^2 &=\sum_{i = 1}^{m} \left|\left| X^{(i)} \right|\right|^2 - 2\sum_{i = 1}^{m} \sum_{t = 1}^n X_t^{(i)} \sum_{j = 1}^n z_{ij} C_{jt} + \sum_{j = 1}^{k} z_{ij} \left|\left| C_j \right|\right|^2 m_j \\
&= tr(XX^T) - 2 \sum_{i}\sum_{t}X_{it}(ZM)_{it} + \sum\left|\left| C_j \right|\right|^2 \\
&= tr(XX^T) - 2\sum_i \left( X \cdot(ZM)^T \right)_{ii} + \sum\left|\left| C_j \right|\right|^2 \\
&= tr(XX^T) -2tr(X\cdot (ZM)^T) + \sum\left|\left| C_j \right|\right|^2
\end{aligned}
\tag{11}
\end{equation}