k均值

k均值(k-means)是聚类算法的一种,聚类分析是根据在数据中发现的描述对象及其关系的信息,将数据对象分组。其目标是,组内的对象相互之间是相似的,而不同组中的对象是不同的。组内的相似性越大,组间差别越大,聚类就越好。

举个例子,在二维平面上有几百个点,在笛卡儿坐标系中有(x,y)坐标,把它们点到纸上,问题是如何把它们分成不同组,每个组里点彼此之前都比较相近,而离其它组的成员又比较远。下面介绍的k均值就能干这种事。

基本k均值

基本k均值思想很简单,首先,选择k个初始质心,其中k是用户指定的参数,即所期望的簇的个数。每个点被指派到最近的质心,而指派到一个质心的点集为一个簇。然后根据指派到簇的点,更新每个簇的质心。重复指派和更新步骤,直到簇不发生变化,或等价的,直到质心不发生变化。

伪代码:

选择k个点作为初始质心。
repeat
  将每个点指派到最近的质心,形成k个簇
  重新计算每个簇的质心
util 质心不发生变化


1:指派点到最近的质心。为了将点指派到最近的质心,我们需要邻近性度量来量化所考虑的数据的“最近”的概念。判断两项的相似度,在上篇文章里已经提到过,可以选择一个合适的算法。通常,对欧式空间里的点适用欧几里德距离,对文档用余弦相似性

2:质心和目标函数。因为在计算k均值的过程中要迭代计算每个簇的质心,我们用均值来当作一个簇的质心,例如第一个簇有点(1,2) (1,1),(2,1),那么我们就用 ( (1 + 1 + 2) / 3, (2 + 1 + 1) /3 )作为质心(相当于各维数据相加,然后除以这组的点数)。而目标函数是我们用来计算产生n个组的算法效果:当我们产生n个组后,计算每个组的所有点的中心点(各维数据相加,然后除以这组的点数),我们称这个点为质心,然后计算每个组中每个点到这个质心的距离,把这个距离相加得到一个组内的距离之和Sum_1,再把每个组这种距离之后相加,即Sum_1 + Sum_2 + … Sum_n,得到这个总距离和就可以判定这次分组质量的好坏,显然,这个值越小越好。

列下k均值常用的邻近度,质心和目标函数的选择:

  • 邻近度函数:曼哈顿距离。质心:中位数。目标函数:最小化对象到其簇质心的距离和
  • 邻近度函数:平方欧几里德距离。质心:均值。目标函数:最小化对象到其簇质心的距离的平方和
  • 邻近度函数:余弦。质心:均值。最大化对象与其质心的余弦相似度和
  • 邻近度函数:Bregman 散度。质心:均值。目标函数:最小化对象到其簇质心的Bregman散度和

选择适当的初始质心是基本k均值的关键步骤。常见的方法是随机地选取初始质心,但是簇地质量会比较差。一个方法是多次运行,每次适用一组不同的随机初始质心,然后选取具有最小目标函数和的簇集。但是这样也只是取得多次运行中较好的,仍然非常依赖开始时质心的位置。

在我的测试数据中,随机产生了100个点,其中每10点给它们一个范围,例如第一组点的横坐标和纵坐标都在10~20之间随机,第二组点的都在40~50之间随机,这样就人为产生了10个簇点。然后适用基本k均值算法,指定k=10,得到的10个簇。如此运行50次。我们期望的结果是分成10个簇后,每个簇有10个点,和我们想的数据相符。但是即使运行50次,得到的也是非常不均匀的,有的簇点有20~30个,有的簇的点只有2,3个,甚至产生了空簇,这说明本来应该在这个簇的点被划到了其它簇。可见对于初始点的指定还是很重要的。

而k均值的变种---二分k均值则对初始化问题不大敏感。

二分k均值

基本思想是:为了得到k个簇,将所有点的集合分裂成两个簇,从这些簇中选取一个继续分裂,如此下去,直到产生k个簇。

伪代码:

初始化簇表,使之包含由所有的点组成的簇。
repeat
   从簇表中取出一个簇。
   {对选定的簇进行多次二分试验}
   for i=1 to 试验次数 do
       使用基本k均值,二分选定的簇。
   endfor
   从二分试验中选择具有最小误差的两个簇。
   将这两个簇添加到簇表中。
until 簇表中包含k个簇

比如要分成5个组,第一次分裂产生2个组,然后从这2个组中选一个目标函数产生的误差比较大的,分裂这个组产生2个,这样加上开始那1个就有3个组了,然后再从这3个组里选一个分裂,产生4个组,重复此过程,产生5个组。这算是一中基本求精的思想。二分k均值不太受初始化的困扰,因为它执行了多次二分试验并选取具有最小误差的试验结果,还因为每步只有两个质心。

同样是上面的那组数据,当我使用二分k均值算法时,产生的10个簇正好每个都是10个点,就是和我们预想的簇一样,非常均匀。

优点与缺点

k均值简单并且可以用于各种数据类型,它相当有效,尽管常常多次运行。然后k均值并不适合所有的数据类型。它不能处理非球形簇,不同尺寸和不同密度的簇。对包含离群点(噪声点)的数据进行聚类时,k均值也有问题。

基本k均值和二分k均值的代码,由于比较长就不贴了,通过看上面的伪代码,理解了其思想,代码还是比较容易写出来的。

参考书目:
数据挖掘导论
Programming Collective Intelligence

– EOF –

0 comments:

Leave a Reply

Your email address will not be published. Required fields are marked *