专项 · 人工智能第 4 课 / 共 6 课免费阅读

k 近邻 · 人工智能基础

程序怎么通过看相似的例子，给一个新东西贴上标签？

课程目录

为什么需要它

k 近邻（kNN）是一个完全不用训练的分类器：要给一个新点贴标签，就找出已有例子里最相似的 k 个，让它们投票。它很好理解，是一个可靠的基线方法；而且「找最近的」这个想法也支撑着推荐和搜索，最后一课还会再见到它。

直觉理解

按特征把每个例子放到网格上，用标签给它上色。来了一个新点：

量出它到每个例子的距离：math.dist(a, b) 给出直线距离
取最近的 k 个
它们当中最常见的标签胜出

怎么选 k：

k = 1 直接照搬最近那个例子的标签，所以一个标错的例子就会改变它周围的答案
k 大一些能抹平噪声，但太大的话，数量最多的那一类会到处都赢
只有两类时，用奇数的 k 可以避免平票

距离是直接把各个特征加在一起算的，所以先缩放（第 1 课）。否则「以元为单位的工资」会淹没「以年为单位的年龄」。

定义

分类

Predicting a category, such as spam or not spam, instead of a number.
预测一个类别（比如是不是垃圾邮件），而不是一个数。

k 近邻

Labelling a point by a vote among the k closest training examples.
让最近的 k 个训练样本投票，给一个点贴标签。

距离

How far apart two points are. math.dist gives the straight-line (Euclidean) distance.
两个点相隔多远。math.dist 给出直线（欧几里得）距离。

示例

距离

动手试试

勾股定理：横 3 竖 4，斜边长 5。

import math

print(math.dist((1, 2), (4, 6)))
print(math.dist((0, 0, 0), (1, 2, 2)))

输出

5.0
3.0

逐步执行

L3差是 3 和 4：√(9 + 16) = 5。5.0
L4任意多个特征都行：√(1 + 4 + 4) = 3。3.0

邻居投票

动手试试

靠近红色角落的点被判为红色，靠近蓝色角落的判为蓝色。

import math
from collections import Counter

train = [
    ((1, 1), "red"), ((2, 1), "red"), ((1, 2), "red"),
    ((6, 5), "blue"), ((7, 7), "blue"), ((6, 6), "blue"),
]

def knn(point, k):
    nearest = sorted(train, key=lambda item: math.dist(item[0], point))[:k]
    votes = Counter(label for xy, label in nearest)
    return votes.most_common(1)[0][0]

print(knn((2, 2), 3))
print(knn((5, 5), 3))
print(knn((4, 5), 5))

输出

red
blue
blue

逐步执行

L10把例子按从近到远排序，保留 k 个。
L11数一数邻居们的标签。
L12票数最多的标签。平票时，先出现的（更近的那个）胜出。
L16在两群点之间，5 个邻居：3 个蓝色，2 个红色。blue

常见错误

没有缩放的特征

数字最大的那个特征会独自决定所有距离。先把每个特征缩放到 0…1。

两类却用偶数的 k

两红两蓝就平票了，结果由平票规则而不是数据决定。用奇数的 k。

数据一多就慢

每次预测都要算到每一个例子的距离。数据有几百万行时，就需要专门的近邻搜索索引。

小测验

1. 这段代码会输出什么？

import math

points = {"A": (0, 0), "B": (3, 4), "C": (1, 1)}
target = (2, 2)
print(sorted(points, key=lambda n: math.dist(points[n], target)))

A
```
['C', 'B', 'A']
```
B
```
['A', 'C', 'B']
```
C
```
['C', 'A', 'B']
```

查看答案

答案：A

到 (2, 2) 的距离：C ≈ 1.41，B ≈ 2.24，A ≈ 2.83。

2. 有一个训练样本的标签错了。哪个 k 受影响最大？

Ak = 1
Bk = 7
C所有 k 都一样

查看答案

答案：A

k = 1 时，这个错误的例子独自决定它附近所有点；k = 7 时它会被其他票压过。

动手练习

3 道练习，分三层：先预测程序的输出，再按新需求改程序，最后从零写一个。代码在浏览器里运行，提交马上判题。

预测输出数票
准确写出它打印的内容。
改需求只看横向
nearest 应该返回最近那个例子的标签，但它只比较了 x 坐标。改成用两个点之间的完整距离（math.dist）。
从零写k 近邻
写一个 knn(train, point, k)。train 是一个由 ((x, y), 标签) 组成的列表。返回离 point 最近的 k 个例子里最常见的标签。
平票：按从近到远的顺序数标签；平票时，先出现的标签胜出。Counter(...).most_common(1) 本来就是这样的。如果 k 比 train 还大，就用全部数据。

在互动课里练这一课

打开互动课，这些例子都能直接改、直接运行，练习题提交马上判题。免费开始，不用注册。

打开互动课课程地图

互动课按顺序解锁：前面的课还没学，会先带你到课程地图。

本课术语

术语	中文	英文定义
Classification	分类	Predicting a category instead of a number.
k-nearest neighbours	k 近邻	Voting among the k closest examples.
Euclidean distance	欧几里得距离	Straight-line distance between two points.