《我的第一本算法书》阅读笔记 6-2 k-means 算法

我就是我 2022-11-16 10:57 168阅读 0赞

# 1 什么是聚类 #

## 1.1 将相似的对象分为一组 ##

聚类就是在输入为多个数据时，将“相似”的数据分为一组的操作。1 个组就叫作 1 个 “簇”。下面的示例中每个点都代表 1 个数据，在平面上位置较为相近、被圈起来的点就代表一 类相似的数据。也就是说，这些数据被分为了 3 个簇。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70][]

## 1.2 如何定义“相似” ##

### 1.2.1 定义数据间的差距 ###

根据数据类型不同，定义该数据是否“相似”的标准也不同。具体来说，就是要对两个数据之间的“差距”进行定义。首先来看下面的示例。

假设某所高中的某个年级中共有 400 名学生，现在我们想要将这些学生在考试中取得的语文、数学、英语成绩数据化，并将他们按照“擅长或不擅长的科目相似”进行聚类。

把每个学生都转换成“（语文成绩 , 数学成绩 , 英语成绩）”形式的数据后，就可以将两个数 据![(c\_1, m\_1, e\_1)][c_1_ m_1_ e_1]和![(c\_2, m\_2, e\_2)][c_2_ m_2_ e_2]之间的差距定义为 ![(c\_1-c\_2)^2 +(m\_1-m\_2)^2 +(e\_1-e\_2)^2][c_1-c_2_2 _m_1-m_2_2 _e_1-e_2_2] ，其中差距小的数据 就互为“相似的数据”。

### 1.2.2 符合条件的算法 ###

即使定义好了数据间的差距，聚类的方法也会有很多种。我们可以设定各种各样的条件， 比如想把数据分为 10 个簇，或者想把 1 个簇内的数据定在 30~50 人之间，再或者想把簇内数据 间的最大距离设为 10，等等。而设定什么样的条件取决于进行聚类的目的。

假如是为了开办暑期补习班而对学生进行分班，那么就要根据老师和教室的数量来确定 “簇的数量”，并根据教室的面积确定“每个簇内的数据量”。现在有很多种可以满足各类条件的 聚类算法供我们选择。

下一节就将介绍其中最基本，也是最有代表性的聚类算法“k-means 算法”。该算法可以把 数据按要求分为 k 个簇。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1][]

# 2 k-means 算法 #

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

![20210407103319752.png][]

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

![20210407103337705.png][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5][]

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

![20210407103446300.png][]

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

![2021040710351311.png][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6][]

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

--------------------

# 3 补充说明 #

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

前面的例子中我们将簇的数量定为 3，若现在使用同样的数据，将簇的数量定为 2， 那么聚类将如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 7][]

位于左边和下边的两个数据块被分到了一个簇中。就像这样，由于 k-means 算法需 要事先确定好簇的数量，所以设定的数量如果不合理，运行的结果就可能会不符合我们 的需求。

如果对簇的数量没有明确要求，那么我们可以事先对数据进行分析，推算出一个合 适的数量，或者不断改变簇的数量来试验 k-means 算法。

另外，如果簇的数量同样为 2，但中心点最初的位置不同，那么也可能会出现下图 这样的聚类结果。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 8][]

与之前的情况不同，这次右上和右下的两个数据块被分到了一个簇中。也就是说， 即使簇的数量相同，只要随机设置的中心点最初的位置不同，聚类的结果也会产生变化。 因此，我们可以通过改变随机设定的中心点位置来不断尝试 k-means 算法，再从中选择 最合适的聚类结果。

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

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

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

--------------------

《我的第一本算法书》  \[日\]石田保辉 宫崎修一/著    张贝/译

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70]: /images/20221022/0a9600398ca84d989de96dd7401122d5.png
[c_1_ m_1_ e_1]: https://latex.codecogs.com/gif.latex?%28c_1%2C%20m_1%2C%20e_1%29
[c_2_ m_2_ e_2]: https://latex.codecogs.com/gif.latex?%28c_2%2C%20m_2%2C%20e_2%29
[c_1-c_2_2 _m_1-m_2_2 _e_1-e_2_2]: https://latex.codecogs.com/gif.latex?%28c_1-c_2%29%5E2%20&plus;%28m_1-m_2%29%5E2%20&plus;%28e_1-e_2%29%5E2
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 1]: /images/20221022/8bb636bc762045eeaaa03c35c398b834.png
[20210407103319752.png]: /images/20221022/f5f67ae4284c4802b4cf26d5c09d58ae.png
[20210407103337705.png]: /images/20221022/109f6b9e9aff4dbe8ab915f821ad6737.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 2]: /images/20221022/9440bc6f86b84d58acc31cce6e380ac3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 3]: /images/20221022/1803e7f960d24743b548f327f6e4b386.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 4]: /images/20221022/4aff3b2411e146bc9d36a88a679757ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 5]: /images/20221022/d22010b04d7e4b269e1a9869e34331fa.png
[20210407103446300.png]: /images/20221022/23b14db0f90d416e9348fbdb5f03ecaf.png
[2021040710351311.png]: /images/20221022/053b7b47d1f745feb1c37886fe807f6c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 6]: /images/20221022/dce3d867e6e5404dad812413522d6c71.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 7]: /images/20221022/f42ebaa6abf048039bdeccf9b4c5d939.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0RyaWZ0ZXJfR2FsYXh5_size_16_color_FFFFFF_t_70 8]: /images/20221022/5760725718074a3fb53331da60dbde80.png