k-means算法

k-means算法是聚类算法中的一种，它可以根据事先给定的簇的数量进行聚类

首先准备好需要聚类的数据，然后决定簇的数量。本例中我们将簇的数量定为3.此处用点表示数据，用两点间的直线距离表示数据间的差距。

随机选择3个点作为簇的中心点。

计算各个数据分别和3个中心点中的哪一个点距离最近。

将数据分到相应的簇中。这样，3个簇的聚类就完成了。

计算各个簇中数据的重心，然后将簇的中心点移动到这个位置。

重新计算距离最近的簇的中心点，并将数据分到相应的簇中。

重复执行"将数据分到相应的簇中"和"将中心点移到重心的位置"这两个操作，直到中心点不再发生变化为止。

3轮操作结束后，结果如上图所示。

4轮操作结束后，结果如上图所示。即使继续重复操作，中心点也不会再发生变化，操作到此结束，聚类也就完成了。

解说

• k-means算法中，随着操作的不断重复，中心点的位置必定会在某处收敛，这一点已经在数学层面上得到证明。
  -前面的列子中将簇的数量定为3,若现在使用同样的数据，将簇的数量定位2,那么聚类将如下图所示。
  
  位于左边和下边的两个数据块被分到了一个簇中。就像这样，由于k-means算法需要事先确定好簇的数量，所以设定的数量如果不合理，运行的结果就可能不符合需求。
  如果对簇的数量没有明确要求，那么可以实现对数据进行分析，推算出一个合适的数量，或者不断改变簇的数量来实验k-means算法。
  另外，如果簇的数量同样为2,但中心点最初的位置不同，那么也可能会出现下图这样的聚类结果。
  
  与之前的情况不同，这次右上和右下的两个数据块被分到了一个簇中。也就是说，即使簇的数量相同，只要随机设置的中心点最初的位置不同，聚类的结果也会产生变化。因此，我们可以通过改变随机设定的中心点位置来不断尝试k-means算法，再从中选择最合适的聚类结果。

补充说明

除了k-means算法意外，聚类算法还有很多，其中"层次聚类算法"较为有名。与k-means算法不同，层次聚类算法不需要事先设定簇的数量。
在层次聚类算法中，一开始每个数据都自成一类。也就是说，有n个数据就会形成n个簇。然后重复执行"将距离最近的两个簇合并为一个"的操作n-1次。每执行一次，簇就会减少1个。执行n-1次后，所有数据就都被分到了一个簇中。在这个过程中，每个阶段的簇的数量都不同，对应的聚类结果也不同。只要选择其中最为合理的个结果就好。
合并簇的时候，为了找出“距离最近的两个簇”，需要先对簇之间的距离进行定义。根据定义方法不同，会有"最短距离法" “最长距离法” “中间距离法” 等多种算法。