从聚类到流形

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

上一章我们把无监督学习的四件事收了线：k-means、PCA、SVD、以及从线性到非线性的 Isomap 和 LLE 开头。这一章先把两条线接得更紧——k-means 和我们很早以前学过的 EM 算法，原来是一家人；然后把上次只是带过的 流形（manifold） 概念正式展开：高维空间里那张「平滑的低维曲面」到底是什么、为什么欧氏距离在它上面会「说谎」、以及降维真正的目的——把数据最本质的特性保留下来。

💡 核心导读

• k-means 是 EM 的特例：分配（每个点归入最近中心）对应 E step，更新均值对应 M step——两个动作交替循环，结构与 EM 完全一样。
• 流形正名：manifold 中文叫流形，是「形状」的「形」——高维空间里一块平滑的低维子空间，跟「流行文化」没有任何关系。
• 球面的警告：球面上北极—赤道三角形的内角和是 $180° +$ 经度差，大于 180°——弯曲的流形有自己的几何。
• 400 维里的人脸：一张 $20 \times 20$ 的照片是 400 维向量；随机取一个点几乎不可能是人脸（是噪点），真实人脸全挤在一小块大约 10 维的子空间上。
• 降维的目的：让高维空间里数据的特性（谁近谁远）在低维空间里得以保留——欧氏距离会说谎时，就换一种距离（Isomap 的思路，回扣 16.4 节）。

聚类回顾：k-means 与 EM 的对应

先回顾上次课的主线。无监督学习的数据没有任何标签，但数据本身有特征值——比如平面上一个点的 $x$、$y$ 坐标，就是这个数据最重要的特征。特征值相近的部分为一类，另外的为另外一类：这就是聚类，道理我们已经说过——物以类聚，人以群分（16.2 节）。它的实际应用非常自然：当我们并不知道这些数据的标签是什么、又想对它们进行分析和了解的时候，靠的就是这类方法。

k-means 的流程大家已经很熟：先随机指定中心位置（比如 $c_1$ 和 $c_2$），然后重复两个动作——

• 分配：每一个数据到 $c_1$、$c_2$ 的距离谁近，就归为哪一类；
• 更新：归好类之后重新求均值，中心就从老位置跳到新位置。

如果大家还记得以前讲过的 EM 算法（expectation maximization），就会发现这两者紧密相连：k-means 可以认为是 EM 算法的一个特例。按标准的对应关系：

• 分配（assignment）= E step：对每个数据求它「属于哪个聚类」——也就是隐变量的期望归属。k-means 里没有概率，做的是硬分配（直接取最近的），结构上正是 EM 的硬分配极限；
• 更新均值 = M step：归属定了之后重新估计参数——中心取簇内均值，均值正是让簇内误差最小的那个估计。

（讲师课堂口播时把两步的称呼对调了——把「求均值」叫 E step、把「分配」叫 M step，应是口误；上面的对应才是与 EM 标准框架一致的版本。）

还有个记号细节值得留意，讲师现场专门停下来自纠过：求均值的时候，$c_i$ 的下标 $i$ 从 1 到 $k$，遍历的是聚类；做分配的时候，数据 $x_j$ 的下标 $j$ 从 1 到 $N$，遍历的是数据——一开始写反了（说成 $i$ 从 1 到 $n$、$j$ 从 1 到 $k$），随即当场纠正。数据用 $j$、聚类用 $i$，这个约定跟 16.2 节的均值公式一致：

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

把这两个动作用代码摆开，每一步显式标出它是 E 还是 M，同时盯着 16.2 节定义过的总误差 $J$（点到所属中心距离平方的总和）怎么变——注意初始中心是刻意选坏的：两个都挤在左团附近：

import math

def euclid(p, c):
    return math.sqrt((p[0] - c[0])**2 + (p[1] - c[1])**2)

points = [(1, 1), (1.5, 2), (2, 1), (5, 7), (5.5, 6.5), (6, 7)]  # 肉眼两团
centroids = [(0.5, 0.5), (1.2, 1.8)]  # 讲义设定: 初始中心都挤在左团附近

for rnd in range(1, 7):
    # E step: 求隐变量——每个点归属哪个簇(硬分配到最近中心)
    assign = []
    for p in points:
        d = [euclid(p, c) for c in centroids]
        assign.append(d.index(min(d)))
    J = sum(euclid(p, centroids[a])**2 for p, a in zip(points, assign))
    # M step: 给定归属, 极大化——中心更新为簇内均值
    new_c = []
    for k in range(2):
        members = [p for p, a in zip(points, assign) if a == k]
        new_c.append((sum(p[0] for p in members) / len(members),
                      sum(p[1] for p in members) / len(members)))
    print(f"第{rnd}轮  E步分配 {assign}  J = {J:.4f}  M步中心 [({new_c[0][0]:.3f},{new_c[0][1]:.3f}) ({new_c[1][0]:.3f},{new_c[1][1]:.3f})]")
    if new_c == centroids:
        print(f"第{rnd}轮 M 步中心不再移动: kmeans 收敛, J 单调下降至 {J:.4f}")
        break
    centroids = new_c

第1轮  E步分配 [0, 1, 1, 1, 1, 1]  J = 134.0500  M步中心 [(1.000,1.000) (4.000,4.700)]
第2轮  E步分配 [0, 0, 0, 1, 1, 1]  J = 23.3200  M步中心 [(1.500,1.333) (5.500,6.833)]
第3轮  E步分配 [0, 0, 0, 1, 1, 1]  J = 1.8333  M步中心 [(1.500,1.333) (5.500,6.833)]
第3轮 M 步中心不再移动: kmeans 收敛, J 单调下降至 1.8333

看这个输出的三个看点：第一，初始中心挤在同一侧时，第 1 轮分配大乱——右团四个点全被塞进了 1 号簇；第二，E、M 交替几轮之后算法自己救了回来（第 2 轮起分配就对了）；第三，也是最要紧的：$J$ 一路单调下降（134.05 → 23.32 → 1.83），到中心不再移动时停住——这正是 EM 算法「每轮不变得更差」的脾气在 k-means 身上的兑现。E 和 M 这两者不断地循环，跟我们以前学的 expectation maximization 是一个完全一样的道理。

降维：无监督学习的另一条主线

无监督学习还有一个很重要的问题：高维空间的数据怎么处理。任何一个 $x_i$ 都属于 $\mathbb{R}^n$——高维空间的数据，我们希望比较有效地找到它更重要的特点，办法是把它投射到一个 $m$ 维空间去（$m$ 一般小于 $n$）。这种操作我们管它叫降维（dimension reduction）。

上章讲的 PCA 和 SVD 都是一种降维的方式：PCA 把（归一化的）协方差矩阵做特征分解，取特征值大的那部分特征向量做投影；SVD 是普通的代数运算，把矩阵 $A$ 分解成 $U \Sigma V^T$ 的形式（$\Sigma$ 是对角阵），自然语言处理里的文档-词矩阵就是这么压进低维空间的（LSA，见 16.4 节）。

但这些都是线性降维。也许最重要的一部分，是如何进行非线性降维——要讲清这件事，就得先把「空间里的流形」这个概念说清楚。

流形：高维空间里平滑的低维子空间

先正名：manifold 的中文是流形，「形状」的「形」——大家千万不要把它理解成「流行文化」的「流行」。流形可以认为是高维空间里边一块比较平滑的低维子空间。

怎么建立直觉？从我们生活的三维空间出发。三维空间里可以嵌入各种平滑的、曲折的二维空间——二维空间就是一个「面」。平面上两个点的距离，用欧氏距离算：坐标之差的平方和再开根号——这是我们最熟悉的度量。但生活中往往有很多曲面：它还是二维的，可它描述的形状发生了变化。

最简单的一个流形：球面。 大家都知道，平面上随便取一个三角形，内角和肯定是 180 度。但是在球面这样的流形上，性质就不一样了：从北极沿两条经线连到赤道上的两个点——每条经线都跟赤道垂直——这样就构成了一个球面三角形：底边在赤道上，两条侧边是经线。数一数它的内角：两个底角都是 90 度（经线垂直于赤道），北极那个角是两条经线的夹角——内角和 $= 180° +$ 经度差，必然大于 180 度。用代码把这三个角真正算出来（在顶点处，沿两条大圆弧各取切向量，算切向量的夹角）：

import math

def unit(v):
    length = math.sqrt(sum(c * c for c in v))
    return tuple(c / length for c in v)

def dot(a, b):
    return sum(x * y for x, y in zip(a, b))

def tangent(p, q):
    """球面上大圆弧 p->q 在起点 p 处的单位切向量"""
    proj = tuple(dot(q, p) * c for c in p)
    return unit(tuple(a - b for a, b in zip(q, proj)))

def interior_angle(p, q, r):
    """球面三角形在顶点 p 处的内角(度): 弧 p->q 与弧 p->r 的夹角"""
    cosang = dot(tangent(p, q), tangent(p, r))
    return math.degrees(math.acos(max(-1.0, min(1.0, cosang))))

N = (0.0, 0.0, 1.0)  # 北极
print("平面三角形内角和恒为 180 度, 球面上呢?")
for theta_deg in (30.0, 60.0, 90.0):
    th = math.radians(theta_deg)
    A = (1.0, 0.0, 0.0)                     # 赤道上, 经度 0
    B = (math.cos(th), math.sin(th), 0.0)    # 赤道上, 经度 theta
    ang_N = interior_angle(N, A, B)          # 北极处两条经线的夹角
    ang_A = interior_angle(A, N, B)           # 赤道顶点 A
    ang_B = interior_angle(B, N, A)           # 赤道顶点 B
    total = ang_N + ang_A + ang_B
    print(f"经度差 {theta_deg:5.1f} 度: 北极角 {ang_N:6.2f}, 两底角 {ang_A:.2f}/{ang_B:.2f}, 内角和 {total:6.2f}")

平面三角形内角和恒为 180 度, 球面上呢?
经度差  30.0 度: 北极角  30.00, 两底角 90.00/90.00, 内角和 210.00
经度差  60.0 度: 北极角  60.00, 两底角 90.00/90.00, 内角和 240.00
经度差  90.0 度: 北极角  90.00, 两底角 90.00/90.00, 内角和 270.00

数值兑现了口头推导：北极角恰好等于经度差，两个底角恰好都是 90 度，内角和 $= 180° +$ 经度差——经度差 90 度时内角和高达 270 度。这说明高维空间里这些曲折的流形，有自己的几何性质，跟平面不是一回事。

这里还有一个容易忽略的点：球面本身是一个二维的东西，不是球。我们说的是「球的面」——它是一张弯曲的、平滑的二维曲面，嵌在三维空间里。三维空间里可以容纳的二维曲面远不止球面，还可以是各种复杂的、更曲折的形状。总结成一句话：流形，就是高维空间里不断平滑着的子空间。

把这句话数学化：数据 $x_i \in \mathbb{R}^n$，虽然名义上活在 $n$ 维空间里，但这些数据主要集中在一块 $m$ 维的流形上（$m \ll n$）——也就是说，$x_i$ 实际上都落在 $\mathbb{R}^n$ 里的一张低维曲面上。

用人脸图片把这笔账算清楚（上一章 16.4 节用 $50 \times 80$ 的图算过 4000 维的版本，有同学没跟上，这里换一张更小的一寸照片再算一遍）：一张 $20 \times 20$ 的图片是 $20 \times 20 = 400$ 个像素——一个 400 维的向量，从第 1 维一直排到第 400 维。假设这些照片都是人的一寸照片：你会发现，所有人的照片在这 400 维空间里，形成了一块低维空间的面——一个低维流形。这个空间特别巨大，随便取一个点，基本都落在人脸之外——随机生成一张 $20 \times 20$ 的图片，几乎看不出是一张人脸，基本就是噪点。为什么？因为人脸只集中在非常小的子空间里——也许大概就 10 维。有意义的照片：能看出来的场景、动物、人脸，都只占 400 维空间里非常非常小的一部分；如果人脸占很大的部分，随机取样基本就能碰到，但实际随机生成的全是噪点——大部分空间里没有任何有意义的图片。

Isomap 回顾：为什么欧氏距离会「说谎」

有了流形的概念，非线性降维就有几种办法了。第一个比较容易的就是 Isomap——16.4 节已经把做法完整讲过（把欧氏距离换成近邻图上的最短路径，用 Dijkstra 连加出来），讲师这里把里边的道理再讲清楚一遍。

拿经典的瑞士卷举例：三维空间里它实际上是一个二维的卷，数据主要分布在卷的表面上——所以它很清晰地是一个流形。问题在于：如果直接算欧氏距离做聚类，卷的两层之间「抄近道」穿过去——空间距离很近的两个点，在卷面上其实距离非常遥远。讲师描述这张图的配色值得记住：数据点用红色渐变着色，代表数据在卷上的连续变化——用 k 近邻衡量时，颜色相近的点确实聚在一起；可按空间欧氏距离算，「更近」的反而是另一头颜色差得远的点（红色对深红色）。欧氏距离在这里把「谁跟谁近」这件事说谎了。

所以需要一个办法，把这块空间展开成我们需要的面——16.4 节说的「两个小人把瑞士卷从两头拉开」，拉平之后点与点之间的关系，才是真正的数据关系。具体机制上次讲过：给定一个点找它最近的邻居，邻居的邻居再连下去（极端情况就是最近邻：1 的最近邻是 2，2 的最近邻是 1 和 3……），两点的距离就是这条链上每一段的连加。

这次要补上的是一个更深的观察——流形被局部线性所逼近：高维空间里很复杂的曲线，可以逼近成每一段都是一个线性关系、这些线性关系的组合。Dijkstra 距离里的 1 到 2，是一段欧氏的线性距离；2 到 3 也是线性距离，3 到 4 也是——但加在一起，就不一样了：1、2、3、4 沿链连加出来的距离，远远大于 1 到 4 之间的欧氏距离。整体非线性的流形，就是被这样一段一段局部线性的东西拼出来的。（「局部线性」这四个字，正是下一节 LLE——局部线性嵌入名字的来历。）于是三维的瑞士卷，变成了一个面构成的二维空间的东西；在二维空间里，只需要算每个点到每个点之间的最近邻关系就够了。

降维的目的：把特性保留下来

降维的目的是什么？在高维空间里边，数据有一些特性；降维，就是让这些特性在低维空间里得以保留。 两点的距离是高维数据身上我们要保留的特性，那么映射到低维之后，这两点的距离关系也应该是保留下来的。

讲师举了个三个点的例子（A、B、C），讲的时候先说反了一句、随即当场纠正——「好，说反了，应该 AC 小于 AB」：我们要保持的特性是 A 到 C 的距离，远小于 A 到 B 的距离。尽管在欧氏距离里，你看着 A、C 也许更大（流形上真正相近的两点，直线距离反而更长——瑞士卷抄近道的反例），但降维要做的，就是把数据的这个特性映射到低维空间里，保留我们最期望的那个特性。欧氏距离会说谎，我们就换一种不说谎的距离——这正是 Isomap 的立足点，也是评价一个降维好不好用的标尺。

📝 动手练一练

1. 概念辨析：为什么平面三角形内角和恒为 180°，而球面上「北极—赤道」三角形的内角和必然大于 180°？请不用代码、纯靠推理算出：两条经线经度差为 90° 时，这个三角形三个内角各是多少度？这说明了流形与平面几何的什么本质差别？

2. 代码实验：把上面球面三角形代码里的经度差改成 5°、1°、0.1° 跑一跑，观察内角和趋于多少；它会小于 180° 吗？结合本节「流形被局部线性逼近」的说法，说说你看到的现象说明了什么。

# 为保证本块可独立运行, 重写球面三角形角度计算
import math

def unit(v):
    length = math.sqrt(sum(c * c for c in v))
    return tuple(c / length for c in v)

def dot(a, b):
    return sum(x * y for x, y in zip(a, b))

def tangent(p, q):
    proj = tuple(dot(q, p) * c for c in p)
    return unit(tuple(a - b for a, b in zip(q, proj)))

def interior_angle(p, q, r):
    cosang = dot(tangent(p, q), tangent(p, r))
    return math.degrees(math.acos(max(-1.0, min(1.0, cosang))))

N = (0.0, 0.0, 1.0)
for theta_deg in (5.0, 1.0, 0.1):
    th = math.radians(theta_deg)
    A = (1.0, 0.0, 0.0)
    B = (math.cos(th), math.sin(th), 0.0)
    total = interior_angle(N, A, B) + interior_angle(A, N, B) + interior_angle(B, N, A)
    print(f"经度差 {theta_deg:5.1f} 度: 内角和 {total:.4f}")

经度差   5.0 度: 内角和 185.0000
经度差   1.0 度: 内角和 181.0000
经度差   0.1 度: 内角和 180.1000

本章小结

这一节做了三件事。第一，把 k-means 和 EM 正式接上：分配是 E step（求隐变量的期望归属）、更新均值是 M step（给定归属的参数重估），两者不断循环、$J$ 一路单调下降——k-means 就是 EM 算法的一个特例。第二，把流形的概念展开：它是高维空间里一块平滑的低维子空间（形状的形，不是流行文化）；球面三角形内角和 $180° +$ 经度差说明弯曲空间有自己的几何；400 维的人脸空间里，有意义的图片只挤在大概 10 维的一小块上，随机取点全是噪点。第三，明确了降维的目的：高维空间里数据的特性，要在低维空间里得以保留——欧氏距离会在流形上说谎（看着近的其实远、看着远的其实近），Isomap 的答案是把距离换成近邻图上的最短路；而「整体非线性的流形，被一段一段局部线性所逼近」这个观察，正是下一节 LLE（局部线性嵌入）的出发点。

📋 行动清单

• 口述对应：不借助资料，说清 k-means 的哪一步对应 E、哪一步对应 M，各自在「算什么、优化什么」。
• 跑改代码：把球面三角形代码的经度差改成 120°、180°，先笔算内角和再跑代码验证。
• 给人讲明白：用自己的话向同学解释「流形」——要求讲出「形状的形」的正名、球面三角形内角和的例子、以及 400 维人脸空间的账。
• 回扣上一章：默写 Isomap 换距离之后「完全没变」的那部分是什么（k-means 一行不改），再说出变的那一行（距离的运算方式）。

—— 小象教研组