K-means

K-means 是一种简单的聚类算法，属于无监督学习算法（Unsupervised learning）。

给定样本集 $D=\{{\mathit{x}}_{\mathbf{1}},{\mathit{x}}_{\mathbf{2}},\cdots ,{\mathit{x}}_{\mathit{m}}\}$ ，K-means 的目标是：把 $m$ 个样本点划分到 $k$ （由用户提供 $k$ 值）个类簇中，使得簇划分 $\mathcal{C}=\{C_1,C_2,\cdots ,C_k\}$ 使下面的平方误差最小：
$$E=\sum _{i=1}^k\sum _{\mathit{x}\in C_i}\Vert \mathit{x}-{\mathit{\mu }}_{\mathit{i}}{\Vert }^2$$
其中 ${\mathit{\mu }}_{\mathit{i}}=\frac{1}{|C_i|}\sum _{\mathit{x}\in C_i}\mathit{x}$ 是簇 $C_i$ 的均值向量。上式中，距离度量采用的是欧氏距离，不过，你也可以采用其它距离。从上式看， $E$ 值越小意味着簇内样本的相似度越高。
不过，最小化 $E$ 并不容易，找到它的最优解需要考察样本集 $D$ 所有可能的簇划分，这是一个 NP 难问题。 K-means 算法采用了贪心策略，通过迭代优化来近似求解最小化 $E$ 对应的簇划分。

K-means 算法如图 1 所示。

其中，第 1 行对均值向量进行初始化，在第 4-8 行与第 9-16 行依次对当前簇划分及均值向量迭代更新，若迭代更新后聚类结果保持不变，则将当前簇划分结果返回。

下面以图 2 所示的西瓜相关数据集为例来演示 K-means 算法的学习过程。

为方便叙述，我们将编号为 $i$ 的样本称为 ${\mathit{x}}_{\mathit{i}}$ ，这是一个包含“密度”与“含糖率”两个属性值的二维向量。

假定聚类簇数 $k=3$ ，算法开始时随机选取三个样本 ${\mathit{x}}_{\mathbf{6}},{\mathit{x}}_{\mathbf{12}},{\mathit{x}}_{\mathbf{27}}$ 作为初始均值向量，即：
$$\begin{array}{rl}{\mathit{\mu }}_{\mathbf{1}}& =(0.403,0.237)\\ {\mathit{\mu }}_{\mathbf{2}}& =(0.343,0.099)\\ {\mathit{\mu }}_{\mathbf{3}}& =(0.532,0.472)\end{array}$$
考察样本 ${\mathit{x}}_{\mathbf{1}}=(0.697,0.460)$ ，它与当前均值向量 ${\mathit{\mu }}_{\mathbf{1}},{\mathit{\mu }}_{\mathbf{2}},{\mathit{\mu }}_{\mathbf{3}}$ 的距离分别为 0.369，0.506，0.166，因此 ${\mathit{x}}_{\mathbf{1}}$ 将被划入簇 $C_3$ 中。类似地，对数据集中的所有样本考察一遍后，可得当前簇划分为：
$$\begin{array}{rl}{C}_1& =\{{\mathit{x}}_{\mathbf{5}},{\mathit{x}}_{\mathbf{6}},{\mathit{x}}_{\mathbf{7}},{\mathit{x}}_{\mathbf{8}},{\mathit{x}}_{\mathbf{9}},{\mathit{x}}_{\mathbf{10}},{\mathit{x}}_{\mathbf{13}},{\mathit{x}}_{\mathbf{14}},{\mathit{x}}_{\mathbf{15}},{\mathit{x}}_{\mathbf{17}},{\mathit{x}}_{\mathbf{18}},{\mathit{x}}_{\mathbf{19}},{\mathit{x}}_{\mathbf{20}},{\mathit{x}}_{\mathbf{23}}\}\\ C_2& =\{{\mathit{x}}_{\mathbf{11}},{\mathit{x}}_{\mathbf{12}},{\mathit{x}}_{\mathbf{16}}\}\\ C_3& =\{{\mathit{x}}_{\mathbf{1}},{\mathit{x}}_{\mathbf{2}},{\mathit{x}}_{\mathbf{3}},{\mathit{x}}_{\mathbf{4}},{\mathit{x}}_{\mathbf{21}},{\mathit{x}}_{\mathbf{22}},{\mathit{x}}_{\mathbf{24}},{\mathit{x}}_{\mathbf{25}},{\mathit{x}}_{\mathbf{26}},{\mathit{x}}_{\mathbf{27}},{\mathit{x}}_{\mathbf{28}},{\mathit{x}}_{\mathbf{29}},{\mathit{x}}_{\mathbf{30}}\}\end{array}$$
于是，可从 $C_1,C_2,C_3$ 分别求出新的均值向量：
$$\begin{array}{rl}{\mathit{\mu }}_{\mathbf{1}}^{\prime }& =(0.473,0.214)\\ {\mathit{\mu }}_{\mathbf{2}}^{\prime }& =(0.394,0.066)\\ {\mathit{\mu }}_{\mathbf{3}}^{\prime }& =(0.623,0.388)\end{array}$$
更新当前均值向量后，不断重复上述过程，如图 3 所示，第五轮迭代产生的结果与第四轮迭代相同，于是算法停止，得到最终的簇划分。

K-means 算法有下面的不足：
1、类簇个数 $k$ 需要事先给定，但很多时候，事先不知道给定数据集分成多少个类别才合适。
2、需要人为地确定初始聚类中心（前面算法描述中是随机地选择初始聚类中心），不同的初始聚类中心可能导致完全不同的聚类结果。

关于第 2 点不足可以使用 K-means++ 算法来解决，这里不介绍 K-means++算法。

本文主要摘自：《机器学习，周志华，2016》，9.4.1 k均值算法