K-means 算法

小象实战讲义 · 机器学习算法精讲

从这次课开始，我们讲 unsupervised learning（无监督学习）。以前课程里看到的都是 supervised learning——那么不靠标签，我们能对数据做什么？本节先分清「分类」和「聚类」这两个词，然后介绍无监督聚类里最经典的第一个算法：K-means（K 均值），最后看看它在什么形状的数据上会失灵——那正是接下来几节的入口。

💡 核心导读

• 监督 vs 无监督：监督学习有 $(x_i, y_i)$ 成对数据学映射；无监督学习的数据集里只有 $x$，没有标签。
• topic model 之问：topic model 本身没有任何标签，是无监督学习；但它的表示可以拿去做监督任务（文本情感分类）——表示是无监督的，分类是监督的。
• 分类 ≠ 聚类：有标签的叫分类（classification），无标签找结构的叫聚类（clustering）；聚类的基本道理是「物以类聚，人以群分」——长得像的点是一类。
• K-means 两步走：assignment（每个点归入最近的中心）+ updating（中心更新为簇内均值），迭代到稳定——它最小化的正是点到所属中心距离平方的总和。
• 失灵的形状：环形、新月形数据 K-means 聚不好——它衡量的是欧氏距离；距离的算法，代表了不同算法延伸的可能性。

从监督到无监督

先回顾监督学习（第 14 章开篇我们给过它的函数定位）：给定 $f: x \rightarrow y$，给了 $(x_1, y_1)$ 这样的一对数据，一直到 $N$ 对数据，我们想学它们之间的关联关系——$x_i$ 怎么映射到 $y_i$。$y$ 是连续值时是预测（回归）问题，离散的 0/1 时是分类问题。这是标准的 supervised learning。

unsupervised learning 跟它不一样的地方在于：数据库 $D$ 里边其实只有 $x_1, x_2, \ldots, x_N$——我们并没有关于这些数据的描述和标签。

那大家想象一下：我们上次描述的 topic model，它是一个 supervised learning 还是 unsupervised learning 呢？——topic model 本身自己没有任何的标签。它所描述的是：给了很多不同的文本，文本里边有不同的词，我们实际学到的是它内部的一种表示方法，所以它是一个 unsupervised learning。

但它可不可以用到 supervised learning 里边？当然可以。比如做文本分类：现在有好多文本 $d_1, d_2, \ldots, d_M$，我可以告诉你其中一部分属于两类不同情感里的「正面」、另一部分是「反面」，怎么分类？我们首先可以用 topic model 的方法，把所有的文本 $d$ 都表示成关于 topic 的形式——变成关于 $t_1, t_2, \ldots, t_K$ 的一个长向量；这一个长向量对应的是 positive，又一个长向量对应的是 negative……然后在这个表示上做分类。所以它首先是一个 supervised learning（给了对应的标签），但它这种 representation（表示方法）本身，是一种 unsupervised learning。

分类、聚类：两个不一样的词

现在看一组数据：它呈现一定的特性，没有任何标签，但每个点都有自己的位置信息——任何一个 $x$ 的横轴、纵轴坐标值，就代表这个数据的基本特性。如果把这些数据看成不同的两类，怎么给它聚类？

注意这里我们换了词。最开始有标签的叫分类（classification）；今天讲叫聚类（clustering），聚合的意思。两者是非常不一样的：classification 都是 supervised learning 问题，聚类 clustering 是 unsupervised learning。

聚类的道理用一句古语就能说透：物以类聚，人以群分。还记得讲 ensemble learning（集成学习）的时候，我们也用了一句古语——「三个臭皮匠顶个诸葛亮」，集成学习的基本核心道理就是它；而聚类的基本道理，就是我们说的「物以类聚，人以群分」：长得像的点，它们是一类；长得不像的点，是不同的类别。

具体怎么聚，其实取决于你怎么看。讲师举了辛普森一家：好多不同的人物——辛普森一家，还有其他漫画里的邻居这些人。聚类的时候，你可以把辛普森的妈妈、爸爸和孩子聚成一类，其他非他们家的人聚成一类；也可以把女士聚为一类、男士聚为另一类——这些都是可以的。所以聚类的方法和考虑的方式，基本上是我们不同人的 bias（偏见/视角）来决定的。

讲师当场还留了一个思考题：现在有鸡、有牛、有草（chicken、cow、grass），三个不同的物品——如果给它聚成两类，你怎么聚？（讲师说「大家考虑一下，我们一会再回头说这件事」，后续课程并未再展开；这个问题没有标准答案，留给各位自己掂量——你想按什么标准分，你的 bias 就是什么。）

K-means：第一个聚类算法

对这种普通的聚类问题，讲师介绍一种最简单的算法——第一个 unsupervised learning 的聚类算法，叫 k-means。means 是均值的意思，所以很多人管它叫 K 均值算法。

K 均值的算法其实非常简单。比如说我们首先要指定一个 $K$：$K=2$ 时，代表把这些数据分成两个聚类。

第一步：随机指定两个中心点——在整个平面里边随机选。

第二步（assignment，分配）：对于现在所有的数据，比如第一个数据，算它到这个中心点和到第二个中心点之间的距离——距离短的，就把它画成这边的一类（比如绿色）。对于另一个数据做差，仍然这边短，那它也属于绿色的聚类；再一个数据，算完距离发现离另一个中心更近，那它就是蓝色的。按这种方式不断细分，就把数据分成了两类：绿色是一大类，蓝色是另外一类。这一步对每一个数据 $x_i$ 给它一个所属的聚类 $c_i$——给它指定最近的类别时，它带来的误差是最小的。

第三步（updating，更新中心）：一旦知道了它们都属于哪一个聚类，就可以更新中心的位置。比如最开始的蓝色中心是随机选定的，但把这些点都归为一类之后，求这些新点的均值——这个中心就更新到均值所在的位置了，原先那个中心就消失了（直接跳到了新的地方）；绿色部分同理，均值算出来在哪个位置，绿色中心就更新到哪里。这样我们就重新构造出了两个新的中心点。

然后回到第二步：每一个数据重新算到新中心的距离——这边最短，下次就被分为蓝色；那边近，就变成绿色。于是又得到新的 assignment，这一轮的结果看起来比最开始的好很多了。如此往复：先算均值，均值之后算每一个 assignment，之后再算均值……

均值怎么写？$C_i$ 的最新位置，就是所有以 $C_i$ 为聚类的这些数据的均值：累加，再比上有多少个——也就是 $C_i$ 的 cardinality（元素个数）：

$$c_i^{new} = \frac{1}{|C_i|} \sum_{x_j \in C_i} x_j$$

讲师在这里专门停了一下做记号说明：这个小写的 $c$ 代表均值（中心点），底下的大写 $C$ 代表所有属于这个聚类的集合——「我要区分一下，好吧？」（这个大写集合、小写均值的记法，请跟上一节的 $\theta$、$\phi$ 一样留意。）

用代码把整个流程跑一遍——7 个点、$K=2$、初始中心由固定随机种子选定：

import math
import random

def euclidean_distance(p1, p2):
    """计算两点间的欧氏距离"""
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

def kmeans_simple(points, k, max_iters=100):
    """
    极简版 K-means 实现
    points: 数据点列表，例如 [(1,2), (3,4), ...]
    k: 簇的数量
    max_iters: 最大迭代次数
    """
    # 1. 初始化：随机选择 k 个点作为初始中心
    random.seed(42)  # 固定随机种子，确保结果可复现
    centroids = random.sample(points, k)

    for iteration in range(max_iters):
        # 2. 分配步骤（assignment）：为每个点分配最近的簇
        clusters = [[] for _ in range(k)]
        for point in points:
            distances = [euclidean_distance(point, cent) for cent in centroids]
            closest = distances.index(min(distances))
            clusters[closest].append(point)

        # 3. 更新步骤（updating）：每个簇的新中心 = 簇内均值
        new_centroids = []
        for cluster in clusters:
            avg_x = sum(p[0] for p in cluster) / len(cluster)
            avg_y = sum(p[1] for p in cluster) / len(cluster)
            new_centroids.append((avg_x, avg_y))

        # 4. 中心不再变化即收敛
        if new_centroids == centroids:
            print(f"算法在第 {iteration+1} 次迭代后收敛。")
            break
        centroids = new_centroids

    return centroids, clusters

# 极小数据集：7 个点，肉眼可判断应聚为 2 类
data_points = [(1, 1), (1.5, 2), (3, 4), (5, 7), (3.5, 5), (4.5, 5), (3.5, 4.5)]

final_centroids, final_clusters = kmeans_simple(data_points, k=2)

print("最终簇中心:", final_centroids)
# 打印每个点被分配到的簇索引（0 或 1）
assignments = []
for point in data_points:
    for cluster_idx, cluster in enumerate(final_clusters):
        if point in cluster:
            assignments.append(cluster_idx)
            break
print("点分配结果:", assignments)

算法在第 2 次迭代后收敛。
最终簇中心: [(3.9, 5.1), (1.25, 1.5)]
点分配结果: [1, 1, 0, 0, 0, 0, 0]

跑出来：簇 0 的中心是 $(3.9, 5.1)$，收下了右上方向五个点；簇 1 的中心是 $(1.25, 1.5)$，收下了左下角两个点——与我们肉眼观察的分布一致。而且只用了两轮「分配 → 更新」就稳定了：中心不再移动，assignment 也不再变化。

K-means 在优化什么

这两个简单的步骤，背后其实在 minimize 一个 error（误差）。如果我们分成两个聚类：聚类里边的点，到它所属中心的距离——做差、求所有差的平方——再加上另一个聚类里边所有点到它中心的距离平方，这个和是最小的。这就是 k-means 所持续优化的函数：任何的 $x_i$ 减去它所对应的 $c_j$，把所有 $i$ 和 $j$ 进行连加、取平方，结果最小：

$$J = \sum_{i=1}^{N} \sum_{k=1}^{K} \mathbb{1}\lbrace x_i \in C_k\rbrace \; \Vert x_i - c_k \Vert_2^2$$

其中指示函数 $\mathbb{1}\lbrace x_i \in C_k\rbrace$ 在 $x_i$ 属于簇 $C_k$ 时取 1、否则取 0（文献里这个量常称「簇内误差平方和」）。每一步 assignment 把点给最近的中心（单独看这个点，误差最小），每一步 updating 把中心挪到簇均值（单独看这个簇，误差最小）——整个算法就在一步步地把 $J$ 往下压。

所以你会发现，这是一个非常简单、不可能更简单、而且特别有效的一个算法。但是这个算法虽简单，其实里边包含的东西，也比我们想象的要复杂。

它不擅长的形状：环形与新月形

先算均值、算每一个 assignment、再算均值——这种更新的形式大家已经很熟悉了。但是对某些特殊形状的数据，它会栽跟头。

想象数据长成这样：外圈是一圈数据，中间还有一小团。可能有的人很清楚地会发现——好神奇，也许外圈的这些数据应该聚成一类、里边的这个部分是一类。但是你会发现，给定刚才的 k-means 算法，根本得不到这样的聚类形式，尽管这个 pattern 还是很明显的。

类似的数据挺多。还有一种我们经常熟悉的叫新月型数据——像一条弯月、一个月亮，这边一个形状、那边一个形状，两个形状之间的关系看得很清楚，真正能聚成的两类就应该是这两个。但我们用 K-means，大家也能想象得到：它衡量的是欧氏距离，所以在这种情况下，它没办法去做很好的分类。

到这个时候大家可以回想一下以前提过的：在这个空间里边进行聚类的时候，就像我们原先使用 k nearest neighbor（k 近邻） 找最近的 $k$ 个邻居一样——关键是距离的算法，距离的算法代表了不同算法延伸的可能性。我们可以求普通的欧氏距离，相当于 L2 norm；也可以求绝对值，L1 norm，对应的是曼哈顿距离；这些都是线性的、求向量的模——L0、L1、L2，甚至 LP norm，我们都可以拿去算不同的距离形式。而对刚才描述的那种形状，这些距离都会遇到困难。

那这种数据怎么办？我们其实也可以解决这些问题——马上接下来的课，就给大家介绍怎么做这种形式的数据。

📝 动手练一练

1. 概念辨析：「分类（classification）」和「聚类（clustering）」有什么本质区别？各举一个例子，并说明 topic model 在哪一边、为什么。

2. 代码实验：把上面示例代码中的 data_points 改为 [(1,1), (2,2), (8,8), (9,9)]，仍然 k=2 运行。观察聚类结果；再想一想，如果初始中心选得不好（比如两个中心都落在同一侧的点附近），K-means 会得到什么？这反映了它什么特性？

# 为保证本块可独立运行，重写极简 K-means
import math
import random

def euclidean_distance(p1, p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

def kmeans_simple(points, k, max_iters=100):
    random.seed(42)
    centroids = random.sample(points, k)
    for iteration in range(max_iters):
        clusters = [[] for _ in range(k)]
        for point in points:
            distances = [euclidean_distance(point, cent) for cent in centroids]
            clusters[distances.index(min(distances))].append(point)
        new_centroids = []
        for cluster in clusters:
            avg_x = sum(p[0] for p in cluster) / len(cluster)
            avg_y = sum(p[1] for p in cluster) / len(cluster)
            new_centroids.append((avg_x, avg_y))
        if new_centroids == centroids:
            print(f"算法在第 {iteration+1} 次迭代后收敛。")
            break
        centroids = new_centroids
    return centroids, clusters

new_data_points = [(1, 1), (2, 2), (8, 8), (9, 9)]
final_centroids, final_clusters = kmeans_simple(new_data_points, k=2)
print("最终簇中心:", final_centroids)
assignments = []
for point in new_data_points:
    for cluster_idx, cluster in enumerate(final_clusters):
        if point in cluster:
            assignments.append(cluster_idx)
            break
print("点分配结果:", assignments)

算法在第 2 次迭代后收敛。
最终簇中心: [(1.5, 1.5), (8.5, 8.5)]
点分配结果: [0, 0, 1, 1]

本章小结

本节开启了无监督学习：数据集里只有 $x$、没有标签；topic model 就是典型——它学到的是数据内部的表示，而这份表示又可以拿去喂给监督任务。用词上，「分类」属于有标签的监督学习，「聚类」是无监督地找结构，基本道理是「物以类聚，人以群分」——但怎么聚，取决于你的 bias（辛普森一家按家庭聚还是按性别聚，都对；鸡、牛、草怎么分两类，讲师留给了我们）。K-means 用两个动作反复迭代：assignment（每个点归入最近中心，单点误差最小）和 updating（中心更新为簇内均值），整体在最小化「点到所属中心距离平方的总和」。它简单到不可能更简单、特别有效，但对环形、新月形这类形状无能为力——它衡量的是欧氏距离；而距离的算法，正代表了不同算法延伸的可能性。接下来几节，我们就沿着「换一种看待距离的方式」往下走。

📋 行动清单

• 口述两步：不借助资料，把 K-means 的 assignment 和 updating 两步讲清楚，并说出每一步各自在最小化什么。
• 跑改代码：运行本节的 K-means 代码，把 $K$ 改成 3、或把数据点挪一挪，观察簇中心和分配怎么变。
• 掂量 bias：回到讲师留的鸡、牛、草问题——给出你自己的两种分法，并说出每种分法背后的标准（你的 bias 是什么）。
• 找个反例：在纸上画一组 K-means 会明显聚错的数据（环形或新月形之外，再想一种新形状），并说说为什么欧氏距离在这里讲不清「像不像」。

—— 小象教研组