k-means聚类方法

k-means可能是最简单的一种聚类方法,它通常也被当作一种基准方法,用于比较其他聚类方法的性能。它的基本思想是假定数据分布为k个簇(cluster);所以,先随机或者按照某种启发式方法选择k个质心(cluster centroids)作为起始簇,然后为每个数据点寻找距离最近的质心,并把它分配(assign)给该质心对应的簇,处理完所有数据点后,重新给这k个簇更新质心到该簇所有点的平均值;然后,不断迭代,直到质心稳定不变。

这里我们给定 $N$ 个样本 $\{x^1,\dots,x^N\}$ ,算法步骤如下:

  1. 随机初始化 $K$ 个质心 $\mu_1,\dots,\mu_K \in \Re^n$
  2. 重复下面的步骤,直到收敛。

    (1) 对每个样本 $i$ ,计算其应该属于的类:

    $$
    c^i := \operatorname*{arg\,min}_j \|x^i - \mu_j\|^2
    $$

    (2) 对每个类 $j$ ,重新计算该类的质心:

    $$
    \mu_j := {\sum_{i=1}^N \mathrm{sign}(c^i=j) x^i \over \sum_{i=1}^N \mathrm{sign}(c^i=j)}
    $$

其中, $K$ 是我们假定的簇数; $c^i \in \{1,\dots,K\}$ 是样本 $i$ 距离最近的质心所属的簇;函数 $\mathrm{sign}(c^i=j)$ 中等式为真时为1,否则为0。

k-means算法一定能保证收敛吗?形式化定义distortion function:

$$
J(c,\mu) = \sum_{i=1}^N \|x^i - \mu_{c^i}\|^2
$$

其中,函数 $J$ 表示每个样本 $x^i$ 到相应质心 $c^i$ 的平方和,k-means算法收敛即是最小化 $J$ 。其实,算法步骤2的每个循环内都是在最小化 $J$ :先固定质心,取距离质心最近的点分配到该类,这会最小化 $J$ ;再固定分类,然后重新调整该类内的质心,这也在最小化 $J$ 。所以,每个循环都是 $J$ 单调递减的过程,即k-means算法会收敛。

k-means算法虽然能保证收敛,但有时也可能得不到全局最优解:

  1. 随机选择的 $K$ 个初始质心的位置,最终可能会收敛到一个不太满意的局部最优解。二分k-means算法可以解决这种问题,即每次只把样本划分成两个簇,然后选择其中一个簇继续二分,直到达到 $K$ 个簇;选择标准是挑选可以最大程度最小化 $J$ 值的那个簇继续二分。
  2. 初始的 $K$ 值选择,如果不是很了解样本的大致分布情况,就不太好确定 $K$ 的大小。有一种预处理方法canopy算法,可以用来估计初始质心的数量和位置。

参考

2012-09-10 15:30
status: part
comments powered by Disqus