算法初接触 | 聚类[什么是聚类、k-means算法]
什么是聚类
将相似的对象分为一组
聚类就是在输入为多个数据时，将“相似”的数据分为一组的操作。1个组就叫作1个“簇”。下面的示例中每个点都代表1个数据，在平面上位置较为相近、被圈起来的点就代表一类相似的数据。也就是说，这些数据被分为了3个簇
如何定义“相似”
定义数据间的差距
根据数据类型不同，定义该数据是否“相似”的标准也不同。具体来说，就是要对两个数据之间的“差距”进行定义。首先来看下面的示例。
假设某所高中的某个年级中共有400名学生，现在我们想要将这些学生在考试中取得的语文、数学、英语成绩数据化，并将他们按照“擅长或不擅长的科目相似”进行聚类。
把每个学生都转换成“(语文成绩，数学成绩，英语成绩)”形式的数据后，就可以将两个数据(c，m，e)和(c，m，e2)之间的差距定义为(ci-c.)+(m-my +(e；-e.)，其中差距小的数据就互为“相似的数据”。
符合条件的算法
即使定义好了数据间的差距，聚类的方法也会有很多种。我们可以设定各种各样的条件，比如想把数据分为10个簇，或者想把1个簇内的数据定在30-50人之间，再或者想把簇内数据间的最大距离设为10，等等。而设定什么样的条件取决于进行聚类的目的。
假如是为了开办暑期补习班而对学生进行分班，那么就要根据老师和教室的数量来确定“簇的数量”，并根据教室的面积确定“每个簇内的数据量”。现在有很多种可以满足各类条件的聚类算法供我们选择。
k-means算法
k-means算法是聚类算法中的一种，它可以根据事先给定的簇的数量进行聚类
图解
01
首先准备好需要聚类的数据，然后决定簇的数量。本例中我们将簇的数量定为3。此处用点表示数据，用两点间的直线距离表示数据间的差距
02
随机选择三个点作为簇的中心点
03
计算各个数据分别和3个中心点中的哪一个点距离最近
04
将数据分到相应的簇中，这样，3个簇的聚类就完成了
05
计算各个簇中数据的重心，然后将簇的中心点移动到这个位置
06
重新计算距离最近的簇的中心点，并将数据分到相应的簇中
07
重复执行“将数据分到相应的簇中”和“将中心点移到重心的位置”这两个操作，直到中心点不再发生变化为止
08
3轮操作结束后，结果如图
09
4轮操作结束后，结果如上图所示。即使继续重复操作，中心点也不会再发生变化，操作到此结束，聚类也就完成了
解说
k-means算法中，随着操作的不断重复，中心点的位置必定会在某处收敛，这一点已经在数学层面上得到证明。
前面的例子中我们将簇的数量定为3，若现在使用同样的数据，将簇的数量定为2，那么聚类将如下图所示。
位于左边和下边的两个数据块被分到了一个簇中。就像这样，由于k-means算法需要事先确定好簇的数量，所以设定的数量如果不合理，运行的结果就可能会不符合我们的需求。
如果对簇的数量没有明确要求，那么我们可以事先对数据进行分析，推算出一个合适的数量，或者不断改变簇的数量来试验k-means算法。
另外，如果簇的数量同样为2，但中心点最初的位置不同，那么也可能会出现下图这样的聚类结果。
与之前的情况不同，这次右上和右下的两个数据块被分到了一个簇中。也就是说，即使簇的数量相同，只要随机设置的中心点最初的位置不同，聚类的结果也会产生变化。因此，我们可以通过改变随机设定的中心点位置来不断尝试k-means算法，再从中选择最合适的聚类结果。
补充说明
除了k-means算法以外，聚类算法还有很多，其中“层次聚类算法”较为有名。与k-means算法不同，层次聚类算法不需要事先设定簇的数量。
在层次聚类算法中，一开始每个数据都自成一类。也就是说，有n个数据就会形成n个簇。然后重复执行“将距离最近的两个簇合并为一个”的操作n-1次。每执行1次，簇就会减少1个。执行n-1次后，所有数据就都被分到了一个簇中。在这个过程中，每个阶段的簇的数量都不同，对应的聚类结果也不同。只要选择其中最为合理的1个结果就好。
合并簇的时候，为了找出“距离最近的两个簇”，需要先对簇之间的距离进行定义。根据定义方法不同，会有“最短距离法”“最长距离法”“中间距离法”等多种算法。
作者：_沉潜
链接：https://juejin.cn/post/7168617821155360781