PRML读书笔记:9.1 K-means聚类


问题的定义

考虑寻找多维空间中数据点的分组或聚类的问题。

假设通过对$D$维欧式空间内的随机变量$\boldsymbol{x}$进行$N$次随机观测,取得数据集${\boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_N}$,目标是将数据集分为$K$类,且$K$给定。

定义一组$D$维向量表示这$K$类的中心,记为${\boldsymbol{\mu}_1, \dots, \boldsymbol{\mu}_K}$。目标是找到数据点分别属于的聚类,以及一组向量${\boldsymbol{\mu}_k}$,使得每个数据点和它最近的向量$\boldsymbol{\mu}_k$之间的距离的平方和最小。

下面引入一些符号来描述数据点的聚类情况。 对于每个数据点$\boldsymbol{x} _ n$,引入一组对应的二值指示变量$r _ {nk} \in {0, 1}$,如果数据点$\boldsymbol{x} _ n$被分配到类别$k$,则$r _ {nk} = 1$,否则$r _ {nk} = 0$。于是可以定义一个目标函数(又称失真度量(distortion measure)):

$$
J=\sum_{n=1}^{N} \sum _ {k=1}^{K} r_{n k}\left|\boldsymbol{x} _ {n}-\boldsymbol{\mu} _ {k}\right|^{2}
$$

表示每个数据点与它对应的聚类中心距离的平方和。

问题的求解

我们可以用一种两个步骤迭代的方法来求解这个问题:

  1. $r_{nk}$的最优化:保持$\boldsymbol{\mu }_ k$固定,关于$r _ {nk}$最小化$J$
  2. $\boldsymbol{\mu} _ k$的最优化:保持$r _ {nk}$固定,关于$\boldsymbol{\mu} _ k$最小化$J$

不断重复这个优化过程直到$J$收敛。这两个步骤在EM算法中分别对应E(期望)和M(最大化)步骤。下面首先介绍K-means算法,在这一算法中,也将采用E和M步骤的说法。

K-means算法

基本思路

首先确定$r_{nk}$。由于$J$对于不同的数据点是独立的,只需将每个数据点安排到离它最近的聚类中心即可。

然后确定$\boldsymbol{\mu}_k$。将$J$对$\boldsymbol{\mu}_k$求导,得到

$$2 \sum_{n=1}^{N} r_{n k}\left(\boldsymbol{x}_{n}-\boldsymbol{\mu}_{k}\right)=0$$

求解得到

$$\boldsymbol{\mu}_{k}=\frac{\sum_{n} r_{n k} \boldsymbol{x}_{n}}{\sum_{n} r_{n k}}$$

上述表达式等价于对属于类别$k$的所有点取均值,因此该算法被称为K-means。

上述步骤不断重复执行,结束条件可取为聚类不再变化或迭代次数超过某个最大值。

K-means算法的初始值最好取为$K$个随机数据点组成的子集。

拓展

由于K-means算法涉及大量欧氏距离的计算,直接使用K-means算法会比较慢。下列方法可以加速K-means算法:将数据组织成树结构,或使用距离的三角不等式避免不必要的距离计算。

K-means算法可以被写成在线随机版本。

K-means算法使用的不相似程度的度量是平方欧氏距离,可以将其拓展为一个更加一般的不相似程度的度量$\mathcal{V}(\boldsymbol{x}, \boldsymbol{x}')$,将失真度量改写为

$$\tilde{J}=\sum_{n=1}^{N} \sum_{k=1}^{K} r_{n k} \mathcal{V}\left(\boldsymbol{x}_{n}, \boldsymbol{\mu}_{k}\right)$$

于是得到了K-medoids算法。这一算法的E步骤(分配聚类)与K-means算法相同;而为了使算法能够适应于任何度量$\mathcal{V}$,通常会将聚类中心点限制为具体的数据点,于是M步骤变为在该聚类内的离散搜索。

K-means算法在每一次迭代中都将数据点分配到一个唯一的聚类,这不一定是合适的。下一节中将通过概率的方法对数据点进行“软”分配。

K-means算法实例

代码

输出结果

上述代码对老忠实间歇喷泉数据集进行了聚类,算法共执行了3步。

9.1.1 图像分割与压缩

图像分割

将图像中的每个像素看做是一个独立的数据点,运行K-means算法直至收敛,即可得到图像的一个$K$-分割。

图像分割

代码

输出结果

从左到右依次是$K=2, 3, 10$和原图。

数据压缩

通过只存储$K$个聚类中心的值和每个数据点对应哪个聚类,可以对数据进行有损压缩。


 评论