• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

K均值最优k值选取

ml admin 3年前 (2017-05-18) 1329次浏览 0个评论 扫描二维码

本文主要基于 Anand Rajaraman 和 Jeffrey David Ullman 合著,王斌翻译的《大数据-互联网大规模数据挖掘与分布式处理》一书。

KMeans 算法是最常用的聚类算法,主要思想是:在给定 K 值和 K 个初始类簇中心点的情况下,把每个点(亦即数据记录)分到离其最近的类簇中心点所代表的类簇中,所有点分配完毕之后,根据一个类簇内的所有点重新计算该类簇的中心点(取平均值),然后再迭代的进行分配点和更新类簇中心点的步骤,直至类簇中心点的变化很小,或者达到指定的迭代次数。

KMeans 算法本身思想比较简单,但是合理的确定 K 值和 K 个初始类簇中心点对于聚类效果的好坏有很大的影响。

1. 确定 K 个初始类簇中心点

最简单的确定初始类簇中心点的方法是随机选择 K 个点作为初始的类簇中心点,但是该方法在有些情况下的效果较差,如下(下图中的数据是用五个二元正态高斯分布生成的,颜色代表聚类效果):

《大数据》一书中提到 K 个初始类簇点的选取还有两种方法:1)选择彼此距离尽可能远的 K 个点 2)先对数据用层次聚类算法或者 Canopy 算法进行聚类,得到 K 个簇之后,从每个类簇中选择一个点,该点可以是该类簇的中心点,或者是距离类簇中心点最近的那个点。

1) 选择批次距离尽可能远的 K 个点

首先随机选择一个点作为第一个初始类簇中心点,然后选择距离该点最远的那个点作为第二个初始类簇中心点,然后再选择距离前两个点的最近距离最大的点作为第三个初始类簇的中心点,以此类推,直至选出 K 个初始类簇中心点。

该方法经过我测试效果很好,用该方法确定初始类簇点之后运行 KMeans 得到的结果全部都能完美区分五个类簇:

2) 选用层次聚类或者 Canopy 算法进行初始聚类,然后利用这些类簇的中心点作为 KMeans 算法初始类簇中心点。

常用的层次聚类算法有 BIRCH 和 ROCK,在此不作介绍,下面简单介绍一下 Canopy 算法,主要摘自 Mahout 的 Wiki:

首先定义两个距离 T1 和 T2,T1>T2.从初始的点的集合 S 中随机移除一个点 P,然后对于还在 S 中的每个点 I,计算该点 I 与点 P 的距离,如果距离小于 T1,则将点 I 加入到点 P 所代表的 Canopy 中,如果距离小于 T2,则将点 I 从集合 S 中移除,并将点 I 加入到点 P 所代表的 Canopy 中。迭代完一次之后,重新从集合 S 中随机选择一个点作为新的点 P,然后重复执行以上步骤。

Canopy 算法执行完毕后会得到很多 Canopy,可以认为每个 Canopy 都是一个 Cluster,与 KMeans 等硬划分算法不同,Canopy 的聚类结果中每个点有可能属于多个 Canopy。我们可以选择距离每个 Canopy 的中心点最近的那个数据点,或者直接选择每个 Canopy 的中心点作为 KMeans 的初始 K 个类簇中心点。

2. K 值的确定。

《大数据》中提到:给定一个合适的类簇指标,比如平均半径或直径,只要我们假设的类簇的数目等于或者高于真实的类簇的数目时,该指标上升会很缓慢,而一旦试图得到少于真实数目的类簇时,该指标会急剧上升。

类簇的直径是指类簇内任意两点之间的最大距离。

类簇的半径是指类簇内所有点到类簇中心距离的最大值。

废话少说,上图。下图是当 K 的取值从 2 到 9 时,聚类效果和类簇指标的效果图:

左图是 K 取值从 2 到 7 时的聚类效果,右图是 K 取值从 2 到 9 时的类簇指标的变化曲线,此处我选择类簇指标是 K 个类簇的平均质心距离的加权平均值。从上图中可以明显看到,当 K 取值 5 时,类簇指标的下降趋势最快,所以 K 的正确取值应该是 5.为以下是具体数据:

复制代码
 1 2 个聚类
 2 所有类簇的半径的加权平均值 8.51916676443
 3 所有类簇的平均质心距离的加权平均值 4.82716260322
 4 3 个聚类
 5 所有类簇的半径的加权平均值 7.58444829472
 6 所有类簇的平均质心距离的加权平均值 3.37661824845
 7 4 个聚类
 8 所有类簇的半径的加权平均值 5.65489660064
 9 所有类簇的平均质心距离的加权平均值 2.22135360453
10 5 个聚类
11 所有类簇的半径的加权平均值 3.67478798553
12 所有类簇的平均质心距离的加权平均值 1.25657641195
13 6 个聚类
14 所有类簇的半径的加权平均值 3.44686996398
15 所有类簇的平均质心距离的加权平均值 1.20944264145
16 7 个聚类
17 所有类簇的半径的加权平均值 3.3036641135
18 所有类簇的平均质心距离的加权平均值 1.16653919186
19 8 个聚类
20 所有类簇的半径的加权平均值 3.30268530308
21 所有类簇的平均质心距离的加权平均值 1.11361639906
22 9 个聚类
23 所有类簇的半径的加权平均值 3.17924400582
24 所有类簇的平均质心距离的加权平均值 1.07431888569
转载自 http://www.cnblogs.com/kemaswill/archive/2013/01/26/2877434.html

参考文献:

[1] 《大数据-互联网大规模数据挖掘与分布式处理》 Anand Rajaraman,Jeffrey David Ullman 著,王斌译。

[2]  Mahout Wiki-Canopy


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明K 均值最优 k 值选取
喜欢 (0)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!