什么是K-means聚类算法

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

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

常见的无监督学习算法，包括 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 个类，然后继续选取新的质心，即对聚类内所有数据点求均值。最后重复上述两个过程：生成新质心后重新进行聚类，然后根据聚类结果再次生成新的质心，直至划分的“类”不再变化时结束。