K-Means算法之K值的选择

1 min read

K-Means是一个超级简单的聚类方法,说他简单,主要原因是使用它时只需设置一个K值(设置需要将数据聚成几类)。但问题是,有时候我们拿到的数据根本不知道要分为几类,对于二维的数据,我们还能通过肉眼观察法进行确定,超过二维的数据怎么办?今天就一起来学习下。

拍脑袋法

一个非常快速的,拍脑袋的方法是将样本量除以2再平方出来的值作为K值,具体公式为:

    \[K\approx \sqrt{n/2}\]

肘部法则(Elbow Method)

Elbow Method :Elbow意思是手肘,如下图左所示,此种方法适用于 K 值相对较小的情况,当选择的k值小于真正的时,k每增加1,cost值就会大幅的减小;当选择的k值大于真正的K时, k每增加1,cost值的变化就不会那么明显。这样,正确的k值就会在这个转折点,类似elbow的地方。 如下图:

通过画K与cost function的关系曲线图,如左图所示,肘部的值(cost function开始时下降很快,在肘部开始平缓了)做为K值,K=3。并不是所有的问题都可以通过画肘部图来解决,有的问题如右边的那个图,肘点位置不明显(肘点可以是3,4,5),这时就无法确定K值了。故肘部图是可以尝试的一种方法,但是并不是对所有的问题都能画出如左边那么好的图来确定K值。

Elbow Method公式:

    \[D_k = \sum_{i=1}^{K}{\sum {dist(x,c_i)^2}}\]

Python实现:

间隔统计量 Gap Statistic

根据肘部法则选择最合适的K值有事并不是那么清晰,因此斯坦福大学的Robert等教授提出了Gap Statistic方法。

这里我们要继续使用上面的D_k。Gap Statistic的定义为:

    \[Gap_n(k)=E^*_n(log(D_k))-logD_k\]

这里{E}(\log D_k)指的是log D_k的期望。这个数值通常通过蒙特卡洛模拟产生,我们在样本里所在的矩形区域中(高维的话就是立方体区域)按照均匀分布随机地产生和原始样本数一样多的随机样本,并对这个随机样本做K-Means,从而得到一个D_k。如此往复多次,通常20次,我们可以得到20个log D_k。对这20个数值求平均值,就得到了{E}(\log D_k)的近似值。最终可以计算Gap Statisitc。而Gap statistic取得最大值所对应的K就是最佳的K。

Gap Statistic的基本思路是:引入参考的测值,这个参考值可以有Monte Carlo采样的方法获得。

    \[E^*_n(log(D_k)) =(1/B)\sum_{b=1}^{B}log(D_{kb}^*)\]

B是sampling的次数。为了修正MC带来的误差,我们计算sk也即标准差来矫正Gap Statistic。

    \[w' = (1/B)\sum_{b=1}^{B}log(D^*_{kb})\]

    \[sd(k) = \sqrt{(1/B)\sum_b(logD^*_{kb}-w')^2}\]

    \[s_k = \sqrt{\frac{1+B}{B}}sd(k)\]

选择满足Gap_k >= Gap_{k+1}-s_{k+1}的最小的k作为最优的聚类个数。下图阐释了Gap Statistic的过程。

Python实现:

轮廓系数(Silhouette Coefficient)

Silhouette method 会衡量对象和所属簇之间的相似度——即内聚性(cohesion)。当把它与其他簇做比较,就称为分离性(separation)。该对比通过 silhouette 值来实现,后者在 [-1, 1] 范围内。Silhouette 值接近 1,说明对象与所属簇之间有密切联系;反之则接近 -1。若某模型中的一个数据簇,生成的基本是比较高的 silhouette 值,说明该模型是合适、可接受的。

方法:

1)计算样本i到同簇其他样本的平均距离a(i)。a(i)越小,说明样本i越应该被聚类到该簇。将a(i)称为样本i的簇内不相似度。簇C中所有样本的a(i)均值称为簇C的簇不相似度。

2)计算样本i到其他某簇C(j)的所有样本的平均距离b(ij),称为样本i与簇C(j)的不相似度。定义为样本i的簇间不相似度:b(i) =min{bi1, bi2, …, bik},b(i)越大,说明样本i越不属于其他簇。

3)根据样本i的簇内不相似度a i 和簇间不相似度b i ,定义样本i的轮廓系数:

4)判断:

  • s(i)接近1,则说明样本i聚类合理
  • s(i)接近-1,则说明样本i更应该分类到另外的簇
  • 若s(i) 近似为0,则说明样本i在两个簇的边界上

所有样本的s(i )的均值称为聚类结果的轮廓系数,是该聚类是否合理、有效的度量。但是,其缺陷是计算复杂度为O(n^2),需要计算距离矩阵,那么当数据量上到百万,甚至千万级别时,计算开销会非常巨大。

Python实现:

Canopy算法

肘部法则(Elbow Method)和轮廓系数(Silhouette Coefficient)来对k值进行最终的确定,但是这些方法都是属于“事后”判断的,而Canopy算法的作用就在于它是通过事先粗聚类的方式,为k-means算法确定初始聚类中心个数和聚类中心点。

与传统的聚类算法(比如K-Means)不同,Canopy聚类最大的特点是不需要事先指定k值(即clustering的个数),因此具有很大的实际应用价值。与其他聚类算法相比,Canopy聚类虽然精度较低,但其在速度上有很大优势,因此可以使用Canopy聚类先对数据进行“粗”聚类,得到k值,以及大致的k个中心点,再使用K-Means进行进一步“细”聚类。所以Canopy+K-Means这种形式聚类算法聚类效果良好。

Canopy算法解析:

  1. 原始数据集合List按照一定的规则进行排序(这个规则是任意的,但是一旦确定就不再更改),初始距离阈值为T1、T2,且T1>T2(T1、T2的设定可以根据用户的需要,或者使用交叉验证获得)。
  2. 在List中随机挑选一个数据向量A,使用一个粗糙距离计算方式计算A与List中其他样本数据向量之间的距离d。
  3. 根据第2步中的距离d,把d小于T1的样本数据向量划到一个canopy中,同时把d小于T2的样本数据向量从候选中心向量名单(这里可以理解为就是List)中移除。
  4. 重复第2、3步,直到候选中心向量名单为空,即List为空,算法结束。

算法原理比较简单,就是对数据进行不断遍历,T2<dis<T1的可以作为中心名单,dis<T2的认为与canopy太近了,以后不会作为中心点,从list中删除,这样的话一个点可能属于多个canopy。

canopy效果图如下:

Canopy算法优势:

  • Kmeans对噪声抗干扰较弱,通过Canopy对比较小的NumPoint的Cluster直接去掉 有利于抗干扰。
  • Canopy选择出来的每个Canopy的centerPoint作为Kmeans比较科学。
  • 只是针对每个Canopy的内容做Kmeans聚类,减少相似计算的数量。

Canopy算法缺点:

  • 算法中 T1、T2(T2 < T1) 的确定问题

Python实现:

参考资料:

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

Excel比较多列并取获最小值或最大值取列名

最近在Excel中分析数据的时候需要要比较多列数据,并返回列中最小值所在列的列名,具体场景如下:
2 sec read

怎样理解numpy中的axis?

6 sec read

密度聚类算法之OPTICS

3 min read

Leave a Reply

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