距离测算

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

上一节讲 KNN 时，有一个词从头到尾没离开过：distance（距离）。要说 nearest neighbor——最近邻，就得先说清什么是 near、什么是 far；而距离的定义一换，“最近”的邻居可能就换了一批，结果也就跟着变。本节专门把”距离”这件事讲透：它要满足哪些数学条件、经典距离家族长什么样、二进制和高维向量各有什么专用度量、乃至面对《辛普森一家》里的卡通人物，我们怎么亲手定义一个距离。

💡 核心导读

• 距离是你定义的：“好朋友”其实是一种距离——跟你好就是距离短；不同问题要定义不同的 distance measure。
• 认知距离不等于像素距离：两张人像照片点对点做差并不远，人与狗反而难分——机器学习很多时候是关于 human perception 的。
• 四个条件：对称、自己与自己的距离为零（且仅此时为零）、非负、三角不等式——满足才算数学上 consistent 的距离。
• Look familiar：距离和向量求模只差”一个向量 vs 两个向量”——欧氏（L2）、曼哈顿（L1）、闵可夫斯基（Lp）一脉相承。
• 三种特殊兵器：二进制用汉明距离（异或数一数）、高维向量用余弦相似度（看夹角）、复杂对象用自定义距离（逐特征打分）。

好朋友，其实是你定义的一种距离

先回味上一节那个”猜英语成绩”的例子：物以类聚，人以群分——找几个最好的朋友，用他们成绩的均值来估计你的成绩。讲师现在把这件事挑明了：“好朋友”这个概念，实际上就是你定义的一种距离——有些人跟你比较好，代表你们俩之间的距离比较短；你跟某些人关系一般、甚至不好，代表你跟他的距离比较远。

所以根据不同的问题，需要定义不同的 distance measure——它在整个研究里都非常重要。讲师举了一个扎心的图像例子：

• 两张都是”人”的照片，背景、光照各不相同——把它们的像素点对点直接做差，你会发现距离其实并没有多远（对应位置上的点大体能对上）；
• 但再来第三张照片：一个人，背景、头发颜色完全不一样，甚至人站的位置都不同——你也仍然认为他们和前两张是同一类（human），尽管点对点做差会得到很大的距离；而画面里那只 dog，才是真正”不同的东西”。

也就是说：数据的底层特征距离（low-level feature distance），跟人的认知距离（human perception distance）相差得很远。机器学习的很多问题，恰恰是关于 human perception 的——在人的认知距离空间里，谁跟谁更相近，也许更重要。怎么定义 distance measure，对以后研究各种问题很重要，这门课后面还会反复遇到。

一个合法的距离：四个条件

不是随便一个数都能叫”距离”。一个 distance measure $d$ 要被认可、能用于计算、在数学上 consistent，需要满足四个条件：

1. 对称性：$d(a, b) = d(b, a)$——A 到 B 的距离，和 B 到 A 的距离是一样的；
2. 自身距离为零，且仅有此时为零：$d(a, a) = 0$——“我跟我之间的差别，一定是世界上最小的差别”；而且只有 a 是它自己时距离才为 0（if and only if $a = b$），其他任何两个不同的点，距离都不为 0；
3. 非负性：$d(a, b) \ge 0$——距离不可能是负的；
4. 三角不等式：$d(a, b) \le d(a, c) + d(b, c)$——像三角形一样，两边之和不小于第三边：直着走，不会比绕道更远。

Look familiar：从模到距离

现在看常用的距离定义。课件上的标题就是一句反问：Look familiar（看起来眼熟吗）？——确实眼熟：还记得第一章求向量的模（norm）吗？L2 norm 是 $x_1^2 + x_2^2 + \cdots + x_n^2$ 再开二次根号，也就是向量的长度；还有 L1 norm、Lp norm 一家子。

模和距离就差一步：模是关于一个向量的长度，而 distance 是关于两个向量的。把这一步跨过去——两个点的距离，就定义为它们之差的模。讲师的原话：两个量之间的距离，可以定义为这两个量之差的模。

• 欧氏距离（Euclidean distance，L2）：差的 L2 模。这就是我们最熟悉的”连接两点的直线”——欧几里得空间里最自然的度量。
• 曼哈顿距离（Manhattan distance，L1）：差的 L1 模，即各维绝对值之和。为什么叫曼哈顿？曼哈顿是纽约的 downtown，修满了街区——想从 A 点到 B 点，你没法穿过楼房走直线，必须沿着街区走：在 x 方向走一段，再在 y 方向走一段。课件配图里：绿色的直线是 L2 distance，红色的折线是 L1 distance。
• 闵可夫斯基距离（Minkowski distance，Lp）：把”差的模”推广到一般的 Lp norm——各维之差的 r 次方加和，再开 r 次根号。r=2 是欧氏，r=1 是曼哈顿。

（有兴趣的同学，可以把这几个公式带回上面四个条件里验证——你会发现它们完全满足，所以都能放心地拿来衡量两点之间的远近。）

用代码感受一下”直线”与”沿街区走”的差别：

# 演示一：同一个 A 到 B，两种距离——直线 vs 沿街区走
A, B = (1, 1), (4, 5)

euclidean = ((A[0] - B[0])**2 + (A[1] - B[1])**2) ** 0.5   # L2：两点连直线
manhattan = abs(A[0] - B[0]) + abs(A[1] - B[1])            # L1：沿街区走

print(f"A{A} -> B{B}  欧氏距离（L2，直线）: {euclidean:.0f}")
print(f"A{A} -> B{B}  曼哈顿距离（L1，沿街区）: {manhattan:.0f}")

A(1, 1) -> B(4, 5)  欧氏距离（L2，直线）: 5
A(1, 1) -> B(4, 5)  曼哈顿距离（L1，沿街区）: 7

横向差 3、纵向差 4：直线距离是漂亮的 5（3-4-5 直角三角形），而沿街区要走 3+4=7。同一个起点终点，度量的定义不同，“远近”就不同——这正是本节的主题。

二进制数据：汉明距离与 MNIST 反例

前面是点与点（数值向量）之间的距离，其实还有很多不同的距离。第一个特殊场景：当两个特征都是二进制（binary）的时候——汉明距离（Hamming distance）。

它想做的事说白了很简单：有两串 0/1 字符，想知道这两串之间的距离是多少；有三串的时候，能知道哪两串之间距离更小、哪两串更大。算法也不难——求异或（XOR）：按位比较，相同（0 对 0、1 对 1）记 0，不同（0 对 1、1 对 0）记 1，然后把结果累加。

# 演示二：汉明距离——按位异或（XOR），数一数有几个 1
def hamming(s1, s2):
    return sum(c1 != c2 for c1, c2 in zip(s1, s2))

x, y = "110011", "101010"
print(f"x = {x}")
print(f"y = {y}")
print("按位异或（不同记1）:", "".join("1" if c1 != c2 else "0" for c1, c2 in zip(x, y)))
print(f"汉明距离 = {hamming(x, y)}（三个 1：有三个位置上的 0/1 不同）")

x = 110011
y = 101010
按位异或（不同记1）: 011001
汉明距离 = 3（三个 1：有三个位置上的 0/1 不同）

讲师算例的锚点正是”三个一”：异或出来有三个 1，距离就为 3——代表有三位上的 binary 不同。

MNIST：汉明距离的用武之地与翻车现场

汉明距离看着简单到”似乎没什么用”，讲师立刻给了一个真实的用武之地：MNIST 手写数字数据集（0~9 的手写数字）。把一张 20×20 的数字图像变成 01 向量：黑色的点为 1、白色的点为 0——于是每一个数字图像都变成了一串 01 字符，可以直接拿去比较汉明距离。

但马上就有翻车现场。有同学说：这可能比得不好——比如”1”这个数字，把它写到另一个位置，它仍然是”1”，可两幅图几乎没有任何相交的部分，按位一比处处不同，汉明距离会非常大；但实际上它们俩是同一个数字——这种情况下也许就判错了。用 5×5 的小网格把这幕演出来：

# 演示三：MNIST 式反例——同一个"1"挪个位置，汉明距离就抓瞎
one_center = "00100" "00100" "00100" "00100" "00100"   # 居中的"1"
one_shift  = "00001" "00001" "00001" "00001" "00001"   # 右移两列的"1"（还是同一个数字）
two_center = "01110" "00010" "00100" "01000" "11111"   # 居中的"2"

def hamming(s1, s2):
    return sum(c1 != c2 for c1, c2 in zip(s1, s2))

print(f"d(居中1, 右移1) = {hamming(one_center, one_shift)}   # 同一个数字，只是挪了位置")
print(f"d(居中1, 居中2) = {hamming(one_center, two_center)}   # 真正不同的两个数字")
print(f"d(右移1, 居中2) = {hamming(one_shift, two_center)}")

d(居中1, 右移1) = 10   # 同一个数字，只是挪了位置
d(居中1, 居中2) = 10   # 真正不同的两个数字
d(右移1, 居中2) = 14

同一个”1”只是往右挪了两列，汉明距离（10）就已经和”1 vs 2”（也是 10）打成了平手——位置一变，汉明距离就抓瞎，这正是讲师说的”判错”情形。

但讲师紧接着给了一句很有分量的话：任何模型没有对错之分。如果你还不会更复杂的算法（比如 CNN 或其他），你至少可以用汉明距离做比较——仍然会得到一些准确率：5 和 5 之间、5 和 3 之间，总有相似的笔画能对上一些位置。这个 measure 或算法虽然很差，但确实仍然可以解决部分问题。

高维向量：余弦相似度

再介绍一个：余弦相似度（Cosine Similarity）。它想做的事情是——高维空间的两个向量 X 和 Y，求它们的余弦夹角：

$$\cos(x, y) = \frac{x \cdot y}{\Vert x \Vert \, \Vert y \Vert}$$

（分子是点积，分母是两个模的乘积。）余弦夹角代表这两个向量是比较相近还是不同：夹角小、方向一致，相似度高；夹角大，相似度低。

它在词向量上特别有用。以后我们会学到：把自然语言里的词映射成高维空间的向量（比如 LSA 一类的方法，映射到的语义空间 semantic space 以后会讲，现在不用理解是什么）。讲师给的例子正是三个词：apple、banana、boat——把它们映射到一个语义空间里，你会发现 banana 跟 apple 之间的夹角很小，而它们俩跟 boat 的夹角都很大——香蕉和苹果是一类东西，船是完全不同的另一类。

# 演示四：余弦相似度——词向量夹角，apple / banana / boat
def cosine(v, w):
    dot = sum(a * b for a, b in zip(v, w))
    nv = sum(a * a for a in v) ** 0.5
    nw = sum(b * b for b in w) ** 0.5
    return dot / (nv * nw)

apple  = [2.3, 1.8, 0.5, 1.1]
banana = [2.1, 1.9, 0.6, 1.0]
boat   = [0.3, -0.5, 2.8, -1.2]

print(f"cos(apple,  banana) = {cosine(apple, banana):+.4f}   # 夹角很小：一类东西")
print(f"cos(apple,  boat)   = {cosine(apple, boat):+.4f}   # 夹角很大：不同东西")
print(f"cos(banana, boat)   = {cosine(banana, boat):+.4f}")

cos(apple,  banana) = +0.9969   # 夹角很小：一类东西
cos(apple,  boat)   = -0.0133   # 夹角很大：不同东西
cos(banana, boat)   = +0.0168

apple 与 banana 的余弦相似度高达 0.9969——方向几乎重合；它们与 boat 的相似度都在 0 附近——接近正交、方向完全不同。（补充两条标准性质：余弦相似度取值在 $[-1, 1]$——同向取 1、反向取 −1、垂直取 0；当距离用时通常取 $1 - \cos$，称为余弦距离。）

复杂对象：自定义距离

最后一种情形最有意思：对象本身就不是向量——怎么衡量两个卡通人物的距离？ 第 3 章讲聚类时我们用过《辛普森一家》的例子（按性别聚成两类、按是否一家人聚成两类）。讲师这次问的是：Marge、Patty、Selma 三个角色之间的距离应该怎么衡量？ 这听起来就很难——总不能去求 Marge 跟 Patty 的 cosine 夹角吧？

办法是：我们人为地设计一些特征，逐项打分——指定若干特征，看两个角色在每个特征上是相同还是不同：不同记 1 分，相同记 0 分，累加起来就是距离。讲师带着大家数的四项：裙子颜色是否不同（一个绿色、一个红色，记 1 分）、是否戴耳环（一个有、一个没有，记 1 分）、高度是否相同（Marge 比较高、Selma 比较矮，记 1 分）、是否抽烟（Marge 不抽、Selma 抽，记 1 分）；再加上最显眼的发型差别，凑成五项特征。结论：Marge 跟 Selma 的距离为 5，而 Patty 跟 Selma 的距离只有 3——Patty 和 Selma 都抽烟、体型也类似，自然更近。

# 演示五：自定义距离——Simpson 角色逐特征打分（不同记 1 分，相同记 0 分）
def role_distance(r1, r2, features):
    return sum(r1[f] != r2[f] for f in features)

features = ["裙子颜色", "戴耳环", "身高", "是否抽烟", "发型"]

marge = {"裙子颜色": "绿", "戴耳环": "否", "身高": "高", "是否抽烟": "不抽", "发型": "蓝色高发"}
selma = {"裙子颜色": "红", "戴耳环": "是", "身高": "矮", "是否抽烟": "抽",  "发型": "紫色短发"}
patty = {"裙子颜色": "紫", "戴耳环": "否", "身高": "矮", "是否抽烟": "抽",  "发型": "灰色卷发"}

print(f"distance(Marge, Selma) = {role_distance(marge, selma, features)}")
print(f"distance(Patty, Selma) = {role_distance(patty, selma, features)}")

distance(Marge, Selma) = 5
distance(Patty, Selma) = 3

课件还给这类”自定义度量”起了名字——edited measure，并给了它一个原味的定义：把一个对象变成另一个对象，量一量花了多大力气——“力气”的大小，就是距离。沿着这个思想，还能长出编辑距离（改几个字符能把一个词变成另一个词）这类常用度量——它们和逐特征打分一样，都是人为设计的 measure。

收尾：KNN 的两个旋钮

到这里，KNN 这一族算法的”可调旋钮”就齐了。讲师的收尾总结：KNN 是一个比较简单、直接的算法——找最近的邻居，直接投票，就能分类或预测。但里面可做的变形有几个部分：

1. k 怎么选：k 特别小，容易 overfitting；k 比较大，得出的结果可能没有任何实际作用——选一个好的 k 非常重要（上一节已展开）；
2. 距离怎么选：如何选择 measure 来找到最近的这些邻居——本节给出的就是各种不同的可能性，尤其在不同向量空间下要选不同的距离；如果数据只是 binary，还有汉明距离。

所以，不是把这个算法拿来就用就好了——根据不同的数据、不同的问题，要重新考量这两件事。

📝 动手练一练

1. 概念题：为什么说”好朋友”其实是你定义的一种距离？一个合法的 distance measure 需要满足哪四个条件？“两张人像照片点对点做差距离不远”的例子又说明了什么？

2. 手算余弦：取 $v_1 = (3, 4)$、$v_2 = (6, 8)$、$v_3 = (-4, 3)$、$v_4 = (-3, -4)$。① 手算欧氏距离 $d(v_1, v_2)$ 与 $d(v_1, v_3)$；② 手算余弦相似度 $\cos(v_1, v_2)$、$\cos(v_1, v_3)$、$\cos(v_1, v_4)$；③ 说说这组数把”方向 vs 大小”演成了什么样。

本章小结

本节把 KNN 的”另一半”——距离——讲透了。距离不是天生给定，而是你定义的：好朋友是一种距离，不同问题需要不同的 distance measure；而底层特征距离与人的认知距离可能相差很远，机器学习很多时候正是在人的认知空间里工作。一个合法的距离要过四关：对称、自零（且仅有）、非负、三角不等式。从向量求模出发一步跨到距离（模管一个向量、距离管两个向量），欧氏（L2 直线）、曼哈顿（L1 沿街区）、闵可夫斯基（Lp）一脉相承。特殊数据有特殊兵器：二进制串用汉明距离（按位异或数 1）——MNIST 手写数字能用它做基线，但要小心”同一个数字挪个位置就判错”的翻车现场，而任何模型没有对错之分，简单模型也能解决部分问题；高维向量用余弦相似度看夹角（apple 与 banana 达 0.9969、与 boat 归零）；复杂对象（Simpson 角色）则人为设计特征、逐项打分（Marge–Selma 为 5，Patty–Selma 为 3）。收尾把 KNN 的两个旋钮拧齐：k 怎么选、距离怎么选——算法简单，变形有学问。

📋 行动清单

学完本节，你可以立即：

• 验一遍公式：把欧氏、曼哈顿、闵可夫斯基三个公式带回四个条件，亲手验证它们都满足（讲师留的作业）。
• 设计一个距离：挑一个你熟悉的对象（两部电影、两首歌、两个 App），列 5 个特征，按”不同记 1 分”定义距离，给三件东西两两打分。
• 跑一遍演示三：把”2”也右移两列再算汉明距离，体会位置失真对不同数字一样无情。

—— 小象教研组