K-mean算法的实现

K-mean算法的实现

k均值聚类算法(k-means clustering algorithm)是一种迭代求解的聚类分析算法,其步骤是,预将数据分为K组,则随机选取K个对象作为初始的聚类中心,然后计算每个对象与各个种子聚类中心之间的距离,把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本,聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有(或最小数目)对象被重新分配给不同的聚类,没有(或最小数目)聚类中心再发生变化,误差平方和局部最小。

分类:分类其实是从特定的数据中挖掘模式,作出判断的过程。比如Gmail邮箱里有垃圾邮件分类器,一开始的时候可能什么都不过滤,在日常使用过程中,我人工对于每一封邮件点选“垃圾”或“不是垃圾”,过一段时间,Gmail就体现出一定的智能,能够自动过滤掉一些垃圾邮件了。这是因为在点选的过程中,其实是给每一条邮件打了一个“标签”,这个标签只有两个值,要么是“垃圾”,要么“不是垃圾”,Gmail就会不断研究哪些特点的邮件是垃圾,哪些特点的不是垃圾,形成一些判别的模式,这样当一封信的邮件到来,就可以自动把邮件分到“垃圾”和“不是垃圾”这两个我们人工设定的分类的其中一个。

聚类:聚类的目的也是把数据分类,但是事先我是不知道如何去分的,完全是算法自己来判断各条数据之间的相似性,相似的就放在一起。在聚类的结论出来之前,我完全不知道每一类有什么特点,一定要根据聚类的结果通过人的经验来分析,看看聚成的这一类大概有什么特点。

聚类和分类最大的不同在于:分类的目标是事先已知的,而聚类则不一样,聚类事先不知道目标变量是什么,类别没有像分类那样被预先定义出来。

K-Means

聚类算法有很多种(几十种),K-Means是聚类算法中的最常用的一种,算法最大的特点是简单,好理解,运算速度快,但是只能应用于连续型的数据,并且一定要在聚类前需要手工指定要分成几类。

下面,我们描述一下K-means算法的过程,为了尽量不用数学符号,所以描述的不是很严谨,大概就是这个意思,“物以类聚、人以群分”:

  1. 首先输入k的值,即我们希望将数据集经过聚类得到k个分组。
  2. 从数据集中随机选择k个数据点作为初始大哥(质心,Centroid)
  3. 对集合中每一个小弟,计算与每一个大哥的距离(距离的含义后面会讲),离哪个大哥距离近,就跟定哪个大哥。
  4. 这时每一个大哥手下都聚集了一票小弟,这时候召开人民代表大会,每一群选出新的大哥(其实是通过算法选出新的质心)。
  5. 如果新大哥和老大哥之间的距离小于某一个设置的阈值(表示重新计算的质心的位置变化不大,趋于稳定,或者说收敛),可以认为我们进行的聚类已经达到期望的结果,算法终止。
  6. 如果新大哥和老大哥距离变化很大,需要迭代3~5步骤。

K-Means的细节问题:

  1. K值怎么定?我怎么知道应该几类? 答:这个真的没有确定的做法,分几类主要取决于个人的经验与感觉,通常的做法是多尝试几个K值,看分成几类的结果更好解释,更符合分析目的等。或者可以把各种K值算出的SSE做比较,取最小的SSE的K值。
  2. 初始的K个质心怎么选? 答:最常用的方法是随机选,初始质心的选取对最终聚类结果有影响,因此算法一定要多执行几次,哪个结果更reasonable,就用哪个结果。 当然也有一些优化的方法,第一种是选择彼此距离最远的点,具体来说就是先选第一个点,然后选离第一个点最远的当第二个点,然后选第三个点,第三个点到第一、第二两点的距离之和最小,以此类推。第二种是先根据其他聚类算法(如层次聚类)得到聚类结果,从结果中每个分类选一个点。
  3. K-Means会不会陷入一直选质心的过程,永远停不下来? 答:不会,有数学证明K-Means一定会收敛,大致思路是利用SSE的概念(也就是误差平方和),即每个点到自身所归属质心的距离的平方和,这个平方和是一个函数,然后能够证明这个函数是可以最终收敛的函数。
  4. 判断每个点归属哪个质心的距离怎么算? 答:这个问题必须不得不提一下数学了…… 第一种,欧几里德距离(欧几里德这位爷还是很厉害的,《几何原本》被称为古希腊数学的高峰,就是用5个公理推导出了整个平面几何的结论),这个距离就是平时我们理解的距离,如果是两个平面上的点,也就是(X1,Y1),和(X2,Y2),那这俩点距离是多少初中生都会,就是√( (x1-x2)^2+(y1-y2)^2) ,如果是三维空间中呢?√( (x1-x2)^2+(y1-y2)^2+(z1-z2)^2 ;推广到高维空间公式就以此类推。可以看出,欧几里德距离真的是数学加减乘除算出来的距离,因此这就是只能用于连续型变量的原因。 第二种,余弦相似度,余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量,余弦相似度更加注重两个向量在方向上的差异,而非距离或长度上。下图表示余弦相似度的余弦是哪个角的余弦,A,B是三维空间中的两个向量,这两个点与三维空间原点连线形成的角,如果角度越小,说明这两个向量在方向上越接近,在聚类时就归成一类: cos 看一个例子(也许不太恰当):歌手大赛,三个评委给三个歌手打分,第一个评委的打分(10,8,9) 第二个评委的打分(4,3,2),第三个评委的打分(8,9,10) 如果采用余弦相似度来看每个评委的差异,虽然每个评委对同一个选手的评分不一样,但第一、第二两个评委对这四位歌手实力的排序是一样的,只是第二个评委对满分有更高的评判标准,说明第一、第二个评委对音乐的品味上是一致的。 因此,用余弦相似度来看,第一、第二个评委为一类人,第三个评委为另外一类。 如果采用欧氏距离, 第一和第三个评委的欧氏距离更近,就分成一类人了,但其实不太合理,因为他们对于四位选手的排名都是完全颠倒的。 总之,如果注重数值本身的差异,就应该用欧氏距离,如果注重的是上例中的这种的差异(我概括不出来到底是一种什么差异……),就要用余弦相似度来计算。 还有其他的一些计算距离的方法,但是都是欧氏距离和余弦相似度的衍生,简单罗列如下:明可夫斯基距离、切比雪夫距离、曼哈顿距离、马哈拉诺比斯距离、调整后的余弦相似度、Jaccard相似系数……
  5. 还有一个重要的问题是,大家的单位要一致! 比如X的单位是米,Y也是米,那么距离算出来的单位还是米,是有意义的 但是如果X是米,Y是吨,用距离公式计算就会出现“米的平方”加上“吨的平方”再开平方,最后算出的东西没有数学意义,这就有问题了。 还有,即使X和Y单位一致,但是如果数据中X整体都比较小,比如都是1到10之间的数,Y很大,比如都是1000以上的数,那么,在计算距离的时候Y起到的作用就比X大很多,X对于距离的影响几乎可以忽略,这也有问题。 因此,如果K-Means聚类中选择欧几里德距离计算距离,数据集又出现了上面所述的情况,就一定要进行数据的标准化(normalization),即将数据按比例缩放,使之落入一个小的特定区间。去除数据的单位限制,将其转化为无量纲的纯数值,便于不同单位或量级的指标能够进行计算和比较。 标准化方法最常用的有两种:
    • min-max标准化(离差标准化):对原始数据进行线性变换,是结果落到【0,1】区间,转换方法为 X’=(X-min)/(max-min),其中max为样本数据最大值,min为样本数据最小值。
    • z-score标准化(标准差标准化):处理后的数据符合标准正态分布(均值为0,方差为1),转换公式:X减去均值,再除以标准差
  6. 每一轮迭代如何选出新的质心? 答:各个维度的算术平均,比如(X1,Y1,Z1)、(X2,Y2,Z2)、(X3,Y3,Z3),那就新质心就是【(X1+X2+X3)/3,(Y1+Y2+Y3)/3,(Z1,Z2,Z3)/3】,这里要注意,新质心不一定是实际的一个数据点。
  7. 关于离群值? 答:离群值就是远离整体的,非常异常、非常特殊的数据点,在聚类之前应该将这些“极大”“极小”之类的离群数据都去掉,否则会对于聚类的结果有影响。但是,离群值往往自身就很有分析的价值,可以把离群值单独作为一类来分析。
  8. 用SPSS作出的K-Means聚类结果,包含ANOVA(单因素方差分析),是什么意思? 答:答简单说就是判断用于聚类的变量是否对于聚类结果有贡献,方差分析检验结果越显著的变量,说明对聚类结果越有影响。对于不显著的变量,可以考虑从模型中剔除。

具体实例分析

demo.py