您当前的位置:首页 > 计算机 > 编程开发 > 人工智能

什么是K-means聚类算法

时间:10-06来源:作者:点击数:

机器学习算法主要分为两大类:有监督学习和无监督学习,它们在算法思想上存在本质的区别。

有监督学习,主要对有标签的数据集(即有“参考答案”)去构建机器学习模型,但在实际的生产环境中,其实大量数据是处于没有被标注的状态,这时因为“贴标签”的工作需要耗费大量的人力,如果数据量巨大,或者调研难度大的话,生产出一份有标签的数据集是非常困难的。再者就算是使用人工来标注,标注的速度也会比数据生产的速度慢的多。因此要想对没有被标注的数据进行分类,就要使用无监督学习算法。

常见的无监督学习算法,包括 K-means 聚类算法、均值漂移聚类算法、主成分分析法(即 PCA 算法)、EM算法(期望最大化算法)等。本节介绍无监督学习中最为经典的 K-means 算法,它是聚类算法簇中的一个,也是最为经典的聚类算法,其原理简单、容易理解,因此得到广泛的应用。通过对该算法的学习,您将掌握什么是聚类问题,以及如何解决聚类问题。

聚类和分类的区别

聚类算法与分类算法的最终的目的都是将数据区分开来,但是两者的实现过程完全不同。分类问题,通过对已有标签的数据进行训练来确定最佳预测模型,然后对新样本的所属类别进行预测,在这个过程中算法模型只要尽可能的实现最佳拟合就 OK 了。与分类问题不同,聚类问题没有任何标签,可谓是一遍茫然,就像做练习题没有参考答案一样,不知道自己做的是否正确。在这种情况下,如果您想证明自己做的题目是否对,在没有参考答案的情况下,您会怎么做呢?没错,您可以多找同学几位同学,甚至找全班同学去对比。

举个简单的例子:一道选择题,你的选择答案是 A,通过询问后您发现全班 85% 以上同学都选择的 A,其余 15% 都选择的 C,那么您心里就会认为自己选择的是正确的,毕竟选择 A 选项占了多数,但是在老师没有公布正确答案之前,什么也说不准,也许会发生“真理只掌握在少数人手里”的事情,因此选择 C 的同学也并不一定就是是错误的,通过这种“找相似”的方法即使在没有“参考答案”的前提下,也能实现分类。因此“找相似”是解决聚类问题的核心方法。

找相似

俗话说“物以类聚,人以群分”,从这句成语中就能体会到“找相似”奥妙,兴趣相投人总会相互吸引,相似的物也总会放在一起。同样的道理,在一份数据集中拥有相似特征的数据也要聚集在一起,这样才便于将这些数据区分开来,但世界上并不存在完全相同的两片叶子,因此聚类算法在实现分类时,只能尽可能找相同点,相同点越多,说明他们就属于同一类,而不同点越多,就说明两者不是同一类。

我们知道,动物种类可以按照科属进行划分,比如豹子、老虎、猫咪都属于猫科动物,有时你可能无法相信,温顺的猫咪竟然和凶猛的老虎同属猫科动物,这就说明他们身上有相似的地方,比如都善于攀爬以及跳跃、皮毛柔软、爪子锋利并可伸缩等等。其实,科学家们最初也没有一个明确的答案知道什么是“猫科动物”,他们通过找相似特征的方法,最终将动物们分门别类,因此这个过程也可以看做是“无监督学习”。

通过上述知识的学习,我们知道解决聚类问题的关键就是“找相似”,下面我们来看一看,K-means 聚类算法是如何在数据集中寻找相同点的。

簇是什么

在聚类问题中,有一个非常重要的概念“簇”(Cluster),那到底什么是簇呢,样本数据集通过聚类算法最终会聚集成一个个“类”,这些类在机器学习中的术语称为“簇”(注意,这里的前提是使用“聚类算法”),因此“簇”是解决聚类问题的表现形式,数据集中的数据样本最终会以“簇”的形式分开。那么当要解决一个聚类问题时,到底要汇集成多少簇呢?

对于分类问题而言,由于有参考答案,因此要分成多少类是已知的,但是聚类则不同,由于没有参考答案,所以形成多少个簇,事先谁也不知道。

举个简单的例子:有同样大小的正方形和圆形各 3 个,每个方形和圆形的颜色两两相同,分别是黄色、红色、绿色,如果按照形状分类的话,可以分为圆形和正方形两个簇,如果按照颜色分类的话,可以分为黄色、红色、绿色三个簇。由此可见选择的分簇条件不同,形成的簇的数量也不同,从而聚类的结果也不同。

不同聚类算法采取了不同的思路,主要分为划分法、层次法、密度法和网格法,这些方法大致可总结为两类,一类是预先设定有多少个簇,另一类则是在聚类的过程中形成。

理解K的含义

K-means 就是一种采用了划分法的聚类算法,K-means 聚类算法与前面的 KNN 分类算法一样,都带有字母“K”,前面我们说过,机器学习喜欢用字母“K”来表示“多”,就像数学中常用字母“n”来表示是同样的道理,但 K-means 中的 K 究竟是什么意思呢?不妨先回顾一下 KNN 分类算法中的 K。

我们知道,KNN 分类算法采用了“多数表决的方法”,最终样本类能够完成分类,完全依赖于该方法,比如 KNN 中的 K 表示有多少个样本点参与表决,这里的 K 对于样本的分类起到了关键性的作用,因此可以换个说法,多数表决是需要限定在 K 规定范围内的。

再说 K-means 中的 K,由于该算法是没有参考标准的。如果不加以限定的话,它会形多任意数量的“簇”,这就要求我们要预先设定“簇”的数量,就像田忌赛马一样,根据马的自身的特点,将其分为上、中、下三个档次,因此 K-means 中 K 是聚集成几个“簇”,形成几个“类”的意思。

如何量化“相似”

前面我们提到过解决“聚类问题”的关键是找到“相似”之处,只有找到了相同点才可以实现类别的划分,说的直白一点,聚类的过程就是让相似的样本互相抱团的过程,这个过程看上去很简单,但实际上要怎样去操作呢?

注意,这里所说的“相似”有时也称之为“相似度”与之含义相反的是“相异度”,相异度越低,相似度就越高,这些词语主用于是衡量对象之间的相似程度。

不妨先回顾一下 KNN 最近邻分类算法,该算法以待分类样本点为中心,通过度量距离找出与其最近邻的 K 个样本点,哪个类别的样本点数量多,那么就认为待分类的样本点属于哪一类。在这个过程中有两点是解决分类问题的关键,一是以待分类样本为“中心点”;二是通过度量距离来确定 K 个最邻近中心的样本点,从而找到哪几个样本点拥有表决权。

在聚类算法中“相似”其实并不是一个具体的指标,就像“人以群分”这句成语,它没有提供具体的划分标准,即“以什么分”,可能是性格、爱好,也可能是志向,甚至是人的高低贵贱,因此量化相似也要根据具体的场景,也就是确定比较的标准(即度量相似的标准)。

K-means 聚类算法与 KNN 算法有许多相似之处(即使在本质它们并不相同),KNN 通过度量距离确定距离自己最近的“朋友圈”,其实换个角度来看的话,这个“朋友圈”就相当于 K-means 中的“簇”,因此我们可以采用与 KNN 相同的度量工具作为量化“相似”的标准。

1) 随机选择质心

从 KNN 解决分类问题的过程不难看出,要想解决 K-means 聚类问题,同样需要一个“中心点”。

假设聚类问题的样本数据也能找出 K 个中心点,就能以该点为中心,以距离为度量画出范围来,将同一范围内的样本点作为一个簇,从而解决聚类问题,在 K-means 聚类算法中,这样的中心点称为“质心”。

聚类算法是无监督学习,因此数据中的样本点完全不知道自己属于哪一个簇, 就更别谈缺点“质心”了,为了解决这一问题,K-means 算法通过随机选择方式来确定质心,但由于是随机选择,因此无法保证随机选择的 K 个质心就恰好是完成聚类后的 K 个簇的中心点,这时就用到了“mean”,它是“均值”的意思,通过均值可以不断的调整质心,由此可知质心在 K-means 算法中是不断改变的。

2) 求出新质心点

假设现在随机了 K 个质心得到了 K 个簇,接下来要怎样让这 K 个簇形成新的质心呢?做法有很多,K-means 算法选择了最简单的一种,求平均。

每个簇都有若干数据点,求出这些数据点的坐标值均值,就得到了新质心的坐标点,比如一个簇中有三个数据点,分别 (3,2),(3,1),(2,3),那么新质心点位于:

x:(3+3+2)/3 约等于 2.666
y:(2+1+3)/3 = 2
质心坐标:(2.666,2)

这其实也是一种变相的多数表决。根据全体拥有表决权的数据点的坐标来共同决定新的质心在哪里,而表决权则由簇决定。

在 K-means 聚类的过程中会经历多次质心计算,数据点到底归属于哪个簇可能会频繁变动,比如同一个数据点可能在本轮与一群样本点进行簇 A 的质心计算,而在下一轮就与另一群样本点进行簇 B 的质心计算,这也是 K-means 算法与 KNN 算法最大的不同之处。

总结

K-means 聚类算法的聚类过程,可以看成是不断寻找簇的质心的过程,这个过程从随机设定 K 个质心开始,直到找到 K 个真正质心为止。

K-means 聚类算法的大致过程如下所示:

  • 第一步,既然现在有了 K 个质心,对于其他数据点来说,根据其距离哪个质心近就归为哪个簇的办法,可以聚成 K 个簇。但请注意,这只是第一步,并不是最后完成聚类的结果;
  • 第二步,对于聚成的 K 个簇,需要重新选取质心。这里运用了多数表决原则,根据一个簇内所有样本点各自的维度值来求均值,得到该簇的新的坐标值;
  • 第三步是生成新的质心,其实就是重复上述过程。对于根据均值计算得到的 K 个新质心,重复第一步中离哪个质心近就归为哪个簇的过程,再次将全部样本点聚成 K 个簇,经过不断重复,当质心不再变化后,就完成了聚类。

最后总结一下:K-means 算法首先逐个计算数据集中的点到各自质心的距离,根据距离的远近,将数据样本点分别划归到距离最近的质心,从而形成 K 个类,然后继续选取新的质心,即对聚类内所有数据点求均值。最后重复上述两个过程:生成新质心后重新进行聚类,然后根据聚类结果再次生成新的质心,直至划分的“类”不再变化时结束。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门