1. 从基本原理出发的思路
分类器是一种规则:它接收对某个对象的描述,并返回一个标签。有些分类器会拟合一个紧凑的模型,例如一条直线、一棵树或一张概率表。基本的暴力最近邻分类则不同,它保留带标签的样本,把基于距离的预测推迟到查询到来时才进行。为了给一个新对象打标签,它会在所选距离下找出最接近的训练对象,并让它们投票。
该方法依赖于一个平滑性假设:在特征空间中彼此接近的对象往往具有相同的标签。当这一假设对所选特征大致成立时,kNN 无需拟合固定维数的参数化决策函数就能表现良好。当该假设不成立时,kNN 的表现会变差。典型原因包括无关特征、尺度不当的特征或特征过多。理解这些失效情形,是理解该方法的重要组成部分。
2. 设定与记号
我们有一个包含 个带标签样本的训练集 ,共有 个数值特征。
- 每个 是由 d 个数值特征组成的向量,。
- 每个 是来自某个有限集合的类别标签。
- 查询是一个新的特征向量 q,我们希望预测它的标签。
- 整数 k 满足 ,并且事先固定。
3. 欧氏距离
相似度通过距离来衡量。本讲义全程使用欧氏距离(Euclidean distance):
这是两点之间的直线长度,即推广到 d 维的勾股定理。有两个事实会被反复用到。
命题 3.4.1
(距离平方给出相同的近邻顺序)
对固定查询 及训练点 , 当且仅当 。因此按距离平方排序,与按距离排序所得的顺序完全相同,平局情况也一样。
证明
(平方的单调性)
距离非负,而 在 上严格递增,所以它同时保持 与 。因此实际实现中可以省略平方根。
其次,每个坐标贡献的是其差值的平方。数值上差异较大的特征会主导求和结果,无论它是否更有信息量。这正是特征缩放一节中的尺度问题的根源。
4. 算法及其约定
定义 3.4.2
(带平局约定的 k 近邻预测)
给定 q 和 k:
- 对每个训练样本 i = 1, ..., n 计算 。
- 按距离从小到大对样本排序。
- 距离平局约定: 若两个样本与查询的距离完全相同,则下标 i 较小的排在前面。
- 这使得 k 个最近邻的集合是唯一确定的,即使平局恰好跨越第 k 个位置也是如此。
- 取该顺序中的前 k 个样本。每个样本为自己的标签投一票(不加权多数投票)。
- 预测得票最多的标签。
- 投票平局约定: 若多个标签并列获得最高票数,则在这些并列标签中,选择其最近的入选近邻距 q 最近的那个标签。
- 若仍然平局,则按照一个事先声明的固定标签顺序(例如字母顺序),选择排在最前面的标签。
为什么用奇数 k? 当恰好只有两个类别时,奇数 k 使投票平局不可能出现,因为奇数张票无法平分。这就是为什么在二分类问题中常用 1、3、5 这样的奇数值。奇数 k 有两个局限:
- 它不能消除距离平局,因此第 2 步仍需要一条规则。
- 当类别数为三个或更多时,它也不能消除投票平局:5 张票可以分成 2–2–1。
反例模式
奇数 k 不能确定预测
有人可能以为,只有两个类别而 k 是奇数时,预测完全由数据和查询决定。取一个特征,查询 ,,两个训练样本为 (R)与 (B)。两者的距离都是 1,所以距离无法决定唯一的近邻。下标规则选样本 1,预测 R;若把同样两个样本按相反顺序列出,则预测 B。奇数 k 只消除投票平局;横跨第 k 个位置的距离平局,仍需要第 2 步的约定。
上述规则是约定,而不是数学真理。任何确定性规则都可以接受,只要它在计算之前声明并且被一致地应用。
k 的选择。 这一权衡是双向的。
- 小的 k 紧密贴合训练数据,对单个噪声点很敏感。当 时,预测直接复制单个近邻的标签。
- 大的 k 使决策更平滑,但可能被较大的类别或较远的点所淹没。当 时,每个训练标签都参与投票。若某个标签在总体上具有唯一的最大计数,则该标签总是获胜;若最高票数出现平局,所声明的最近邻平局规则可能使结果依赖于查询。
应使用从训练部分中划分出的验证数据来选择 k,绝不能使用最终测试集。
5. 例题
例题 3.4.3
(土壤样本的最近邻,以及 k 的影响)
某温室项目将土壤样本标记为 R(需要重新浇水)或 B(状况良好)。它使用两个已在可比尺度上测量的特征: = 干燥指数, = 盐分指数。
| 下标 | 标签 | ||
|---|---|---|---|
| 1 | 1 | 2 | R |
| 2 | 2 | 1 | R |
| 3 | 4 | 4 | B |
| 4 | 5 | 3 | B |
| 5 | 3 | 5 | B |
| 6 | 2 | 3 | R |
查询为 。我们使用 、欧氏距离以及算法一节的约定。
第 1 步:距离。 对每个样本,用特征减去查询,将每个差值平方,把平方相加,然后开平方根。
| 下标 | 距离平方 | 距离 | 标签 | |
|---|---|---|---|---|
| 1 | (−2, −1) | 4 + 1 = 5 | R | |
| 2 | (−1, −2) | 1 + 4 = 5 | R | |
| 3 | (1, 1) | 1 + 1 = 2 | B | |
| 4 | (2, 0) | 4 + 0 = 4 | 2 | B |
| 5 | (0, 2) | 0 + 4 = 4 | 2 | B |
| 6 | (−1, 0) | 1 + 0 = 1 | 1 | R |
第 2 步:排序。 完整排名为:
6 (1),3 (1.414),4 (2),5 (2),1 (2.236),2 (2.236)。
这里有两处距离平局。样本 4 和 5 的距离都是 2,因此按下标规则 4 排在 5 之前。样本 1 和 2 的距离都是 ,因此 1 排在 2 之前。
第 3 步:选取并投票。 三个最近的样本是 6 (R)、3 (B) 和 4 (B)。投票结果为 B = 2,R = 1。
第 4 步:预测。 预测结果为 B。
第三个位置涉及平局:样本 4 和 5 的距离都是 2,而在 下只能容纳其中一个。这里两者的标签都是 B,因此预测结果不依赖于平局规则。但一般情况下可能会依赖,这正是规则必须事先确定的原因。
在同一排序下改变 k 很有启发性:
- : 只使用样本 6,因此预测为 R。单个最接近的样本是需要重新浇水的情况。
- : 使用样本 6、3、4、5 和 1(样本 1 凭下标胜过样本 2)。投票结果为 B = 3,R = 2,因此预测为 B。
预测结果在 和 之间发生了变化。两个结果都不是算术错误;它们反映的是不同程度的平滑。只有留出数据上的证据才能提示哪种选择更适合这类数据,而六个点远不足以解决这个问题。
快速检查
(沿用上面的土壤数据,取查询 及 。所列规则预测什么?)
解答 · 答案
样本 1 至 6 的距离平方为 。得票是 R (样本 1、2、6)与 B ,投票平局。入选的 R 样本中最近者的距离平方为 1,比 B 样本中最近者的 8 更近,所以预测 R。
6. 特征缩放如何改变距离
欧氏距离将各特征上的差值平方相加,仿佛每个特征的一个单位都同等重要。当特征以不同单位测量时,这种情况很少成立。
例题 3.4.4
(原始距离与最小–最大缩放距离选出不同的近邻)
考虑一个手机套餐数据集,它有两个特征:
- = 每月数据用量(MB);在训练数据中其范围为 0 到 1000。
- = 客服来电次数;在训练数据中其范围为 0 到 10。
使用以下包含四位客户的完整训练集和一个查询:
| 点 | (MB) | (次数) | 标签 |
|---|---|---|---|
| P | 180 | 1 | S(留存) |
| Q | 260 | 8 | T(流失) |
| U | 0 | 0 | S(留存) |
| V | 1000 | 10 | T(流失) |
| 查询 | 200 | 8 | ? |
原始距离。
- 到 P:差值为 (20, 7),因此 400 + 49 = 449,距离 。
- 到 Q:差值为 (60, 0),因此 3600 + 0 = 3600,距离为 60。
- 到 U:距离平方为 。
- 到 V:距离平方为 。
四个训练点均已检查;当 时,预测为 S。此处数据用量决定了结果:Q 的 60 MB 差距对其距离平方贡献了 3,600,大于 P 的全部距离平方 449。这种贡献取决于为两个特征所选的单位。
最小–最大缩放后的距离。 使用训练集的最小值和最大值对每个特征重新缩放,采用 。在这里,这意味着 变为 , 变为 。缩放后的点为 ,,查询 。
- 到 P:差值为 (0.02, 0.7),因此 0.0004 + 0.49 = 0.4904,距离 。
- 到 Q:差值为 (0.06, 0),因此为 0.0036,距离为 0.06。
- U 和 V 分别缩放为 (0, 0) 和 (1, 1);它们与查询的距离平方均为 0.68。
在全部四个点中,最近邻是 Q,预测为 T。客户本身没有任何变化;变化的只是衡量差值所用的单位。因此,缩放并不是表面功夫:它是相似度定义的一部分。
快速检查
(在手机套餐例子中,以表中顺序作下标顺序,求 时原始距离与最小–最大缩放后的预测。)
解答 · 答案
原始顺序是 P、Q、U、V,所以近邻 P(S)、Q(T)、U(S)给出 S。缩放后的距离平方是 Q 为 、P 为 ,U 与 V 都是 。下标规则取 U(S),得票为 S 、T ,预测 S。若改取 V,则会预测 T,所以这里平局规则有影响。
两种常见选择是最小–最大缩放和标准化,。每种方法都包含一个建模假设。例如,最小–最大缩放会为每个非常数特征分配大小相同的缩放区间。若某个拟合集的极差为零或标准差为零,公式将出现除以零的情况:应事先定义一项策略,例如在该拟合折中丢弃该特征,并将同一已拟合策略应用于其验证数据。被丢弃的特征无法表示之后出现的变化。如果领域知识表明某个特征更重要,应当有意识地表达这一点,例如使用特征权重,而不是任由单位的偶然选择来决定。
7. 数据泄露:只在训练数据上拟合预处理
缩放是有参数的:最小值和最大值,或均值和标准差。这些参数是从数据中学到的,因此它们是已训练模型的一部分。规则如下:
- 首先将数据划分为外层训练部分和最终测试(留出)部分。
- 对于外层训练部分内的验证划分,只在拟合子集上拟合缩放器,然后将其原样应用于该子集及其验证子集。在交叉验证中,对每一折分别重复这一过程。每个候选 k 都必须不超过最小拟合折中的样本数,以确保它在每一折中都有效。
- 利用这些验证结果选择 k。在完整的外层训练部分上重新拟合缩放器,然后将该已拟合的缩放器原样应用于最终测试集和之后的查询。
常见错误
(在划分前于整个数据集上拟合缩放器)
假设你反而在划分之前就在整个数据集上计算最小值和最大值。那么关于测试点的信息就已进入模型,因为测试点参与决定了距离的衡量方式。由此得到的测试准确率不再能衡量在真正未见数据上的表现,因为真正未见的数据不可能影响缩放器。在具体情况中,这种影响可能很小也可能很大,但评估已不再诚实。
这有两个实际后果。
- 测试值可能落在训练范围之外,使缩放值小于 0 或大于 1。这是正确的行为;不要为了“修正”它而重新拟合缩放器。
- 同样的规则也适用于选择 k。如果你尝试了多个 k 值,并保留测试得分最好的那个,那么测试集就被用于训练了。应在训练数据内部用验证划分或交叉验证来选择 k,并在每一折内部重新拟合缩放器。然后在最后只使用测试集一次。
快速检查
(缩放器在某个训练特征上拟合,最小值为 10,最大值为 50。缩放测试值 60 与训练值 30。若重新拟合时包括该测试值,会有什么改变?)
解答 · 答案
缩放值是 与 。1.25 是合理的。若重新拟合时包括 60,范围会变成 ,训练值会移到 ,即测试数据改变了训练点的几何。
8. 训练与预测的代价
计算模型。 我们假设如下:
- 单处理器上的暴力 kNN。
- 每次算术运算和每次比较各计为一个单位。
- n 个训练样本、d 个特征、k 个近邻和 m 个查询。
- 近邻按欧氏距离的平方排序,因此不计算平方根。
训练。 朴素 kNN 只存储数据。这需要 的内存,除了复制之外,基本没有计算。拟合一个最小–最大缩放器会增加两项代价,因此拟合总体为 :
- 求每个特征的最小值和最大值,每个特征约需 2(n − 1) 次比较。
- 变换所存储的数据约需 2nd 次运算(每个值一次减法和一次除法)。
单个查询的预测。 代价由三部分组成。
- 距离。 一个距离平方需要 d 次减法、d 次乘法和 次加法,共 次运算。对所有训练点,总计 。
- 选取。 找出 k 个最小距离:使用比较排序需 ,使用有界堆需 ,使用合适的随机化选择算法则期望时间为 。当下标平局规则起作用时,应比较
(distance, index)对。 - 投票。 使用常数时间的按标签索引计数器,统计票数需 ;同时记录每个标签最近的入选样本,也能支持所声明的投票平局规则。
命题 3.4.5
(暴力式预测代价)
在上述模型中,一个查询计算距离平方需 次运算,用有界堆选出 个最小者需 ,投票需 。每个查询的总代价为 , 个查询则为 。
证明
(把三个阶段相加)
各阶段依次进行,所以代价相加。 个样本各需 次运算;由于 ,投票的 被其他项吸收。各查询互相独立,所以单个查询的代价乘以 。
例题 3.4.6
(计算距离运算次数)
当 、 时,一个距离平方需 次运算,所以一个查询需 次距离运算, 个查询需 次。在边界情形 时,一个距离平方是一次减法与一次乘法,即 次运算,一个查询的次数为 。 的取值不影响距离阶段。
kNN 颠倒了通常的模式:训练便宜而预测昂贵,因为每次预测都要重新扫描所存储的数据。索引结构(k-d 树、球树)或近似搜索可以在低维情形下降低预测代价。它们不属于基本方法,而且随着 d 增大,其效果可能下降,具体取决于数据和查询。
9. 需要单独规则的变体
上述方法使用不加权多数投票。两种常见的变体改变了规则,必须单独说明。
- 距离加权投票。 每个近邻的票数被加权,通常权重为 1/d。这需要为距离为 0 的近邻(除以零)制定专门的约定,并为加权总和相等的情况制定专门的平局规则。加权结果可能与上文的不加权结果不同,两者不应混用。
- 类别不平衡。 当某一类别远比其他类别常见时,它往往会主导邻域,因此多数投票可能很少预测出少数类。可选方案包括类别特定的权重、对训练数据重采样,或者对于二分类器,调整施加在正类得票比例上的阈值。每种补救措施都定义了一个不同的分类器,必须明确说明。
10. 局限性
- 无关特征。 每个特征都会对距离产生贡献,因此噪声特征会稀释有用的特征。
- 高维情形。 对于某些分布和距离模型,随着 d 增大,相对距离会趋于集中,使最近点与最远点更难区分。这并非普遍成立:相关性和数据的几何结构都有影响。
- 如上所述,仅适用于数值特征。 类别特征需要编码或使用不同的距离。
- 解释能力有限。 kNN 可以展示使用了哪些样本,但无法给出特征与标签之间关系的紧凑概括。
11. 小结
对于一个固定的带标签训练集以及上文规定的不加权投票规则,kNN 通过找出与查询最接近的 k 个训练样本并进行投票来做出预测。还必须说明以下四项选择:
- 距离;
- 预处理;
- k 的取值;
- 平局规则。
任何预处理都只能在训练数据上拟合,选择 k 时不得触碰测试集。训练的低廉是以预测的昂贵为代价的。