人工智能-机器学习-kmeans聚类中,如何确定k的大小

开课吧开课吧锤锤2021-02-04 15:33

kmeans聚类中,如何确定k的大小

这是一个老生常谈的经典问题,面试中也经常问。

人工智能面试

K-均值聚类算法首先会随机确定k个中心位置,然后将各个数据项分配给最临近的中心点。待分配完成之后,聚类中心就会移到分配给该聚类的所有节点的平均位置处,然后整个分配过程重新开始。这一过程会一直重复下去,直到分配过程不再产出变化为止。

人工智能面试

如上图所示,有A,B,C,D,E五个数据项,随机生成两个数据项(黑点处),将距离最近的的数据合为一类,取平均后生成新的两个数据项(黑点处),再次将距离最近的数据合为一类,如此重复,直到数据固定。

对于K-means中K的选择,通常有四种方法。

1 按需选择

2 观察法

3 手肘法

4 Gap Statistics方法

一、按需选择

简单地说就是按照建模的需求和目的来选择聚类的个数。比如说,一个游戏公司想把所有玩家做聚类分析,分成顶级、高级、中级、菜鸟四类,那么K=4;如果房地产公司想把当地的商品房分成高中低三档,那么K=3。按需选择虽然合理,但是未必能保证在做K-Means时能够得到清晰的分界线。

二、观察法

就是用肉眼看,看这些点大概聚成几堆。这个方法虽然简单,但是同时也模棱两可。

人工智能面试

人工智能面试

人工智能面试

人工智能面试

第一张是原始点,第二张分成了两类,第三张是三类,第四张是四类。至于K到底是选3还是选4,可能每个人都有不同的选择。

观察法的另一个缺陷就是:原始数据维数要低,一般是两维(平面散点)或者三维(立体散点),否则人类肉眼则无法观察。对于高维数据,我们通常利用PCA降维,然后再进行肉眼观察。

三、手肘法Elbow Method

手肘法本质上也是一种间接的观察法。这里需要一点K-Means的背景知识。当K-Means算法完成后,我们将得到K个聚类的中心点Mi,i=1,2,⋯,Ki=1,2,⋯,K。以及每个原始点所对应的聚类Ci,i=1,2,⋯,K。我们通常采用所有样本点到它所在的聚类的中心点的距离的和作为模型的度量,记为DK。人工智能面试

这里距离可以采用欧式距离。

对于不同的K,最后我们会得到不同的中心点和聚类,所有会有不同的度量。

我们把K作为横坐标,DK作为纵坐标,可以得到下面的折线。

人工智能面试

很显然K越大,距离和越小。但是我们注意到K=3是一个拐点,就像是我们的肘部一样,K=1到3下降很快,K=3之后趋于平稳。手肘法认为这个拐点就是最佳的K。

换句话说,曲线类似于人的手肘,“肘关节”部分对应的 K 值就是最恰当的 K 值

人工智能面试

但是并不是所有代价函数曲线都存在明显的“肘关节”,例如下面的曲线:

人工智能面试

一般来说,K-Means 得到的聚类结果是服务于我们的后续目的(如通过聚类进行市场分析),所以不能脱离实际而单纯以数学方法来选择  KK  值。在下面这个例子中,假定我们的衣服想要是分为 S,M,L 三个尺码,就设定  K=3,如果我们想要 XS、S、M、L、XL 5 个衣服的尺码,就设定  K=5:

人工智能面试

手肘法是一个经验方法,而且肉眼观察也因人而异,特别是遇到模棱两可的时候。相比于直接观察法,手肘法的一个优点是,适用于高维的样本数据。有时候人们也会把手肘法用于不同的度量上,如组内方差组间方差比。

四、Gap Statistic法

这个方法是源自斯坦福几个machine learning大牛的paper Estimating the number of clusters in a data set via the gap statistic 。

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

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

用上图的例子,我们计算了K=1,2,..9对应的Gap Statisitc. 

人工智能面试

Gap Statistic的优点是,我们不再需要肉眼了。我们只需要找到最大gap statistic所对应的K即可。所以这种方法也适用于“批量化作业”。如果我们要做1000次聚类分析,不需要肉眼去看1000次了。

人工智能在计算机领域内,得到了愈加广泛的重视。并在机器人,经济政治决策,控制系统,仿真系统中得到应用。发展前景很可观,有对人工智能感兴趣的同学就赶快学习起来吧。以上就是小编今天为大家整理发布的“人工智能-机器学习-kmeans聚类中,如何确定k的大小”一文,希望为正在学习人工智能的朋友提供学习参考,更多人工智能面试尽在开课吧广场人工智能面试频道!

有用
分享