算法初接触 | 聚类[什么是聚类、k-means算法]

敞开生长之旅！这是我参与「日新方案 12月更文应战」的第2天

什么是聚类

将类似的对象分为一组

聚类便是在输入为多个数据时，将“类似”的数据分为一组的操作。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个成果就好。
兼并簇的时分，为了找出“间隔最近的两个簇”，需求先对簇之间的间隔进行界说。根据界说办法不同，会有“最短间隔法”“最长间隔法”“中间间隔法”等多种算法。