一、引言

    生活中，我们有时会遇到这样的情况：在一片操场上，散落着很多同学，其中一个班级里的，自然站的更靠近一些。一个人想要知道一共来了多少个班级，他只需要站到主席台上去，用肉眼观察操场上有多少“团”人，就可以知道操场上来了多少个班级。

    这个例子中，可以简单的理解为，一个班级的同学就是一类人，也就是说这一群站的比较靠近的人是一类人。我们通过操场上有多少“团”人，来判断操场上来了多少个班级。

    现在我们反过来想这个例子，如果现在已知的是操场上有多少个班级，你该如何判断哪些人是一个班的呢？自然是看他们哪些人聚在了一起。但是这个仅仅我们肉眼看到的，如果把这些数据放到计算机里，每一个操场上的人只用一个坐标表示，我们该如何判断哪些人是一类人呢，这就要用到我们今天要说的k-means啦。

二、问题直观描述

K-Means要解决的问题

    直观的来说，k-means要解决的问题其实就如上图（图是偷的）。

    在一个坐标系中拥有很多个点的坐标，现在要让计算机把他们聚成很多类，也就是所谓的聚类算法。

三、算法实现

k-means算法实现

    算法的思路比较容易理解，在这里我直接复制粘贴了：

    从上图中，我们可以看到，A，B，C，D，E是五个在图中点。而灰色的点是我们的种子点，也就是我们用来找点群的点。有两个种子点，所以K=2。

    然后，K-Means的算法如下：

     1、随机在图中取K（这里K=2）个种子点。

     2、然后对图中的所有点求到这K个种子点的距离，假如点Pi离种子点Si最近，那么Pi属于Si点群。（上图中，我们可以看到A，B属于上面的种子点，C，D，E属于下面中部的种子点）

     3、接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步）

     4、然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了A，B，C，下面的种子点聚合了D，E）。

    这个算法很简单，只需要知道求距离的公式和求点群中心的算法就能完成。在这里我不详细介绍需要使用的数学知识，因为最简单的求点群中心点的算法就是使用各个点的X/Y坐标的平均值。当然还有更高端的算法，有兴趣的可以自己查找资料。

四、举例说明

    说到这里，其实最重要的算法核心思路已经说完了，但是一个正常人肯定会觉得这个算法没有实际使用的价值，因为让计算机去玩几个简单的坐标简直是大材小用，现实生活中给出坐标需要聚类的问题也很少。那么这里我就要反驳一下，举几个简单的可以使用k-means算法的例子。

    最简单的，二位空间中点的聚类可以清晰肉眼判断出，但是更高维度的就必须要用到计算机了。比如给出宇宙中所有星球的三维坐标，用k-means就可以找出哪些星球是属于一个星系的。这还仅仅是一个三位的例子，如果是五维的呢？如果是一千维的呢？就跟需要电脑去计算了。

    说到一千维，可能有人觉得是夸张了，其实不用想得那么复杂，举一个我刚刚遇到的问题作为例子：你拿到了一万张图片，每张图片上有0-9之间的一个数字，但这写数字都不是标准的，而是用画图工具随手画的，也就是说两张图片上的“1”虽然长得差不多，但不完全一样。现在需要你将这一万张图片按照上面所画的图片，分成十类。

    这个问题一拿到手似乎难以解决，因为都是图片，而且每张相同数字的图片也不相同。但这可就可以用k-means来解决。

    我们可以把每张图片看成32*32=1024个像素组成的。这些像素有的是白色的，有的画过的地方就是黑色的。我们设白色像素为0，黑色像素为1，这样就可以把每张图片看成一个1024维空间里的一个点。比如，某个张图的坐标可能就是（0，0，0，1，1，0，0，1，……）。

    虽然每张相同数字的图片不完全相同，但他们在这个1024维空间里代表的点位置是相近的。用k-means算法，就可以将这一万张图片按照上面所画的图片，分成十类。

    最后再举一个例子，一个高三班级有五十个同学，现在有他们十次模考成绩，想给他们分个上中下等。因为每次考试难度不同，卷子总分值也不同，直接求平均分是不合适的。用k-means给他们分等级就很合适了，用每次考试的成绩作为某一维度的长度，这样每个同学也就成为这个十维空间里的点了，把他们的类聚一聚，就分出上中下三等了。

五、总结

    k-means在数据挖掘中是一种很有效的而且简单的聚类算法，虽然有比如初始点需要随机放置等缺点，但依然是不错的算法，并且有不错的用途空间。总之有所了解总不是坏事。