聚类算法

  • 什么是聚类
  • k-means 算法

什么是聚类

聚类指的是在分类标准未知的情况下，将相似的数据分到一组（也叫「簇」）的作业。比如，假设有一堆顾客的数据，我们想根据购买行为把他们分成几个群体，但事先并不知道该怎么分，这时候就可以用聚类来处理。

聚类和「分类」不同：分类是事先已经知道了分类的标准，把数据归到已知的类别里；而聚类是在没有标准的情况下，根据数据自身的相似程度来进行分组。

k-means 算法

k-means 算法是聚类算法中最为广泛使用的一种。k 表示簇的数量，means 表示「均值」，所以 k-means 就是「k 个均值」的意思。

操作步骤

  1. 准备数据：准备好需要聚类的数据，每个数据都有若干个属性。为方便理解，假设数据有两个属性，可以画在二维平面上。
  2. 设定簇的数量 k：事先确定好要将数据分成几组，此处设 k=3。
  3. 随机设置中心点：随机选择 k 个点作为各个簇的中心点（也叫「质心」）。
  4. 将数据分到最近的中心点所在的簇：计算各个数据分别和 k 个中心点中的哪一个点距离最近，把数据分到相应的簇中。
  5. 移动中心点：计算各个簇中数据的重心，然后将簇的中心点移动到这个位置。
  6. 重新分配：重新计算距离最近的簇的中心点，并将数据分到相应的簇中。随着中心点的移动，部分数据的「距离自己最近的中心点」也会改变。
  7. 重复：重复执行「将数据分到相应的簇中」和「将中心点移到重心的位置」这两个操作，直到中心点不再发生变化为止。

解说

k-means 算法中，随着操作的不断重复，中心点的位置必定会在某处收敛，这一点已经在数学层面上得到证明。

需要注意 k-means 的几个特点：

  • 需要事先确定簇的数量。设定的数量如果不合理，运行的结果就可能会不符合需求。如果对簇的数量没有明确要求，可以事先对数据进行分析，推算出一个合适的数量，或者不断改变簇的数量来试验。
  • 结果受初始中心点位置影响。即使簇的数量相同，只要随机设置的中心点最初的位置不同，聚类的结果也会产生变化。因此，可以通过改变随机设定的中心点位置来不断尝试 k-means 算法，再从中选择最合适的聚类结果。

补充：层次聚类

除了 k-means 算法以外，聚类算法还有很多，其中「层次聚类算法」较为有名。与 k-means 算法不同，层次聚类算法不需要事先设定簇的数量。

在层次聚类算法中，一开始每个数据都自成一类。也就是说，有 n 个数据就会形成 n 个簇。然后重复执行「将距离最近的两个簇合并为一个」的操作 n-1 次。每执行 1 次，簇就会减少 1 个。执行 n-1 次后，所有数据就都被分到了一个簇中。在这个过程中，每个阶段的簇的数量都不同，对应的聚类结果也不同，只要选择其中最为合理的 1 个结果就好。

合并簇的时候，为了找出「距离最近的两个簇」，需要先对簇之间的距离进行定义。根据定义方法不同，会有「最短距离法」「最长距离法」「中间距离法」等多种算法。