K-Means聚类

1. 什么是聚类

“物以类聚,人以群分”,聚类就是将数据划分成有意义或有用的组(簇)。给定一个元素集合D,其中每个元素具有n个特征(或者说可观察属性),聚类的目标是将元素进行分组,使得组内的元素相互之间是相似的(相关的),而不同组中的元素是不同的(不相关的)。组内的相似性(同质性)越大,组间差别越大,则聚类的效果就越好。

2. 相似度度量

根据聚类的目标,我们需要找到一个度量来刻画元素之间的相关性,用数学的语言表述如下:

设元素$X=\{x_1,x_2,\cdots,,x_n\}$,元素$Y=\{y_1,y_2,\cdots,y_n\}$,$x_i,y_i$分别是元素$X,Y$的特征(属性),定义$X$和$Y$的相似度为$d(X,Y)=f(X,Y) \rightarrow \mathbb{R}$,其中$\mathbb{R}$表示实数域,也就是说相似度是两个元素对实数域的一个映射。

相似度的计算主要有以下几个公式:

  • 欧氏距离
    $$
    d(X,Y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+\cdots+(x_n-y_n)^2}
    $$
  • 曼哈顿距离
    $$
    d(X,Y)=|x_1-y_1|+|x_2-y_2|+\cdots+|x_n-y_n|
    $$
  • 闵可夫斯基距离
    $$
    d(X,Y)=\sqrt[p]{(x_1-y_1)^p+(x_2-y_2)^p+\cdots+(x_n-y_n)^p}
    $$
  • 余弦相似度
    $$
    d(X,Y)=\frac{X^{T}Y}{||X||Y||}
    $$

其中,欧氏距离和曼哈顿距离可看做是闵可夫斯基距离在$p=2$和$p=1$下的特例,闵可夫斯基距离越大,则相似度越低。

3. K-Means聚类

接下来,我们看看到底什么是K-Means(K均值)聚类。K-Means的算法过程非常简单:

  1. 从$D$中随机选取$K$个元素,作为$K$个簇各自的初始中心;
  2. 分别计算其余元素到这$K$个簇中心的相似度,将这些元素指派到相似度最高的簇;
  3. 根据上一步的聚类结果,重新计算$K$个簇各自的中心,一般是取簇中所有元素在各个属性维度的算术平均;
  4. 将D中全部元素按照新的中心重新聚类;
  5. 重复第4步,直到聚类结果不再变化;
  6. 输出结果.

4. K-Means算法实例

这里举一个简单的例子,说明K-Means算法的计算过程。如图所示,考虑图中的二维数据,一共有六个元素(点),现在我们想把这六个元素聚成两个簇,也就是划分为两类,因此$K=2$。

应用K-Means算法进行聚类,迭代过程如下:
[1]. 随机选取两个元素作为初始聚类中心,这里我们选择点5和点6,当然也可以选择其他两个点,将这两个初始聚类中心记为A,B;
[2]. 计算点1,2,3,4到点5,6的距离,这里我们选择欧氏距离,很明显,点1,2,3,4离点5的距离最近,因此它们被分到A中,而点6还是在B中,此时簇A中有5个元素,而簇B只有一个元素;
[3]. 计算簇A的中心点$C_{A1}$,即

$$
\left (\frac{x_1+x_2+x_3+x_4+x_5}{5}, \frac{y_1+y_2+y_3+y_4+y_5}{5}
\right)
$$

簇B的中心点$C_{B1}$为$(x_6, y_6)$,因此得到

$$
C_{A1}=(1.6,0.4)
$$

$$
C_{B1}=(4.0,1.0)
$$

[4]. 将5个点重新聚类,计算5个点分别到$C_{A1}$和$C_{B1}$的距离,经计算可知,点1,2,3和4到$C_{A1}$的距离最近,而点5和6到$C_{B1}$的距离最近,因此点1,2,3和4被分配到簇A,点5和6被分配到簇B;

[5]. 再次计算簇A的中心点$C_{A2}$,即

$$
\left (\frac{x_1+x_2+x_3+x_4}{4}, \frac{y_1+y_2+y_3+y_4}{4}
\right)
$$

簇B的中心点$C_{B2}$,即
$$
\left(\frac{x_5+x_6}{2},\frac{y_5+y_6}{2}\right)
$$

得到$C_{A2}=(1.25,0.25)$,$C_{B2}=(3.5,1.0)$;

[6]. 重复第4步,将5个点重新聚类,计算5个点分别到$C_{A2}$和$C_{B2}$的距离,经计算可知,点1,2,3和4被分配到簇A,点5和6被分配到簇B。此时,聚类的结果跟上一步一样,因此得到最终聚类结果,即点1,2,3和4划分为一类A,点5和6划分为另一类B。

将上面的迭代过程用表格展示如下:

步骤 类A元素 类A中心 类B元素 类B中心
1 5 (3.0,1.0) 6 (4.0,1.0)
2 1,2,3,4,5 (1.6,0.4) 6 (4.0,1.0)
3 1,2,3,4 (1.25,0.25) 5,6 (3.5,1.0)
4 1,2,3,4 (1.25,0.25) 5,6 (3.5,1.0)

另外一个有趣的例子可参考博文算法杂货铺——k均值聚类,作者采集了亚洲15只球队在2005年到2010年间大型杯赛的战绩,然后将这15只球队聚成3类,得到下面结果,呵呵:

  • 亚洲一流:日本,韩国,伊朗,沙特
  • 亚洲二流:乌兹别克斯坦,巴林,朝鲜
  • 亚洲三流:中国,伊拉克,卡塔尔,阿联酋,泰国,越南,阿曼,印尼

5. K-Means算法改进

由上面K-Means算法的思想不难发现,K-Means算法存在两个比较大的缺陷:

  • K需要事先给定,但在实际中K值是难以估计的。一般情况下,给定一个数据集,也不知道要分成多少类才是最合适的;
  • 初始聚类中心是随机选取的,选取不同的初始聚类中心,可能结果会有很大差异;

针对上面两个缺陷,可采用K-Means++算法wiki上对该算法的描述如下:

  1. 从输入的数据点集合中随机选择一个点作为第一个聚类中心;
  2. 对于数据集合中的每个点x,找到离它最近的聚类中心y,计算x与y的距离D(x);
  3. 在数据点集合中,选取下一个点加入聚类中心的集合,每个点x被选取的概率正比于$D(x)^2$;
  4. 如果聚类中心点集合数目没有达到预定的数目,回到2,否则到5;
  5. 执行K-Means算法.

关于K-Means++算法的进一步分析和讨论还可参考博文K-Means++

6. 参考资料