前面的笔记把分类看作选择一个将特征向量映射到标签的规则,也把距离作为衡量两个观测值相隔多远的方式。 近邻(kNN)分类器直接连接了这两个想法:给新点分类时,找出离它最近的训练观测,让它们投票。
想法虽简单,细节却需要仔细处理。kNN 规则取决于训练样本、距离、 的值、距离相同时的排序规则、票数相同时的处理规则,以及对特征所作的每一步预处理。如果其中任何一项没有规定,“kNN 的预测”就可能没有唯一答案。本节先在预测之前固定这些选择,再考察分类器能保证什么、不能保证什么。
动机
假设一个观测的标签往往与特征相近的观测的标签类似,那么用附近训练点中最常见的标签来猜测新点是合理的。kNN 不对决策边界的形状作参数化假设;边界完全由局部投票产生。
灵活性也有代价。“附近”是否有意义,取决于距离和特征尺度,而非标签本身。另外,少数邻居的投票是一个带噪声的概括,不能自动解释成概率。
精确定义规则
固定有限训练样本 ,其中 、,下标 表示观测在样本中的原始位置。固定整数 及 上的距离 。除非另有说明, 为欧氏(Euclidean)距离 。
定义 5.5.1
(具有固定平局规则的 kNN 分类器)
对查询点 :
- 对 计算 。
- 按二元组 的字典序排列下标:距离小者在前;距离相等时原始下标小者在前。记排列后的顺序为 。
- 邻居集合为 。
- 邻居得分为
- 若 ,预测 ;若 ,预测 。
第 5 步在票数相同时选择类别 ;只有 为偶数时才可能出现票数相同。其他约定也可以,例如优先类别 ,或退回到最近的 个邻居。关键是必须在查看任何测试标签之前选定约定,并始终一致地使用。
要区分两种平局:
- 票数平局指 。选奇数 可以避免它。
- 距离平局指若干训练点到 的距离相等。如果其中一组跨过第 个位置,邻居集合便取决于平局的排序方式。奇数 不能防止这种情况。
定理 5.5.2
(确定性与 的两个极端取值)
固定训练样本、距离、 和以上平局规则。
(a) 对每个查询点 ,预测 是唯一确定的标签。
(b) 若 ,则对所有 , 都是全体训练标签的多数类;恰有一半标签为 时选择类别 。
(c) 令 ,且 为训练点。假设每个恰好位于 的训练点的标签都是 ,则 。没有这一条件,结论可能不成立。
证明
(各部分为何成立)
(a) 各个二元组 互不相同,因为第二个坐标不同。互异二元组上的字典序是严格全序,因此 唯一,进而 、 和按阈值得到的标签也唯一。
(b) 当 时,无论 是什么,邻居集合包含所有下标。因此 等于标签 的总体比例;阈值规则给出所述多数类,并在平局时选择 。
(c) 在 处查询时,所有位于 的训练点的距离都是 ,其他点的距离均为正。因此 是位于 的点中最小的下标。根据假设,该点标签为 。若两个点位置相同但标签不同,则该位置所有训练点中下标最小的点决定两者的预测;两个冲突标签中至少有一个被误分类,见最后一道练习。
(a) 只说明确定性:对固定样本和查询点,输出是固定的。规则定义明确并不意味着得分已校准。
一维算例
例题 5.5.3
(数轴上的五个训练点)
按下标排列的训练样本为:
| 下标 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
查询 。 距离 依次为 。按 排序得到 。取 ,邻居集合为 ,三个标签均为 ,所以 ,。
查询 。 距离依次为 。下标 和 的距离同为 。当 时,下标规则把 排在前面,故 。若改为优先较大下标,预测就会是 。数据和距离本身不能在 处唯一确定 1NN 的决策;平局规则也是分类器的一部分。
同一查询,。 完整顺序为 ,因为下标 和 的距离同为 ,第三个位置落在这一平局内。下标规则选中 ,得到标签 ,所以 ,预测为 。若优先较大下标,则选中 ,得到 ,预测为 。这里 是奇数,虽然票数不可能平局,预测仍取决于距离平局如何处理。
。 五个标签中三个是 ,因此每个查询点,包括 ,都被标为 。 附近的点标签为 这一局部信息被舍弃了。
距离、尺度与特征
单调变换。 用 替换 ,其中 严格递增,会保留每个比较 和每个等式 。因此排序和所有预测均不变。这就是可以用欧氏距离的平方代替欧氏距离的原因。同样,对得分 作严格递增变换会保留查询点按得分的排序,但决策阈值也必须随得分一起变换。
特征缩放则不同。 将某个坐标乘以常数会改变几何关系,可能改变邻居的顺序。
反例模式
缩放一个特征改变最近邻
取查询点 、类别 的训练点 和类别 的训练点 。距查询点的平方距离分别为 和 ,因此 1NN 预测类别 。
现在将第一坐标乘以 。类别 的点变为 ,查询点不变;平方距离变为 和 ,因此 1NN 预测类别 。
快速检查
(在上述缩放反例中,若把**两个**坐标都乘以 ,1NN 预测会改变吗?)
比较两个距离如何变化。
解答 · 答案
不会。两个坐标同时乘以 ,每个距离都乘以 ,这是 的严格递增变换,所以顺序保持不变:平方距离变为 和 ,1NN 仍预测类别 。只有相对其他坐标单独缩放某个坐标,才会改变几何关系。
所以,用不同单位衡量特征或将特征标准化,都是建模选择;标准化并非中性的记账步骤。
无关特征。 与标签无关的坐标仍然计入每个距离。若其变动范围与有信息的坐标相当或更大,它可能近乎随机地改变邻居顺序;此时预测会趋向于由任意训练点投票所得的结果。
其他距离。 曼哈顿(Manhattan)距离 或加权欧氏距离表达了对哪些差异重要的不同判断。没有脱离问题而天然正确的距离,应通过验证比较不同选择。
例题 5.5.4
(欧氏距离与曼哈顿距离给出不同答案)
取查询点 、类别 的点 和类别 的点 。用欧氏距离,,所以 1NN 预测类别 。用曼哈顿距离, 的距离为 , 为 ,所以 1NN 预测类别 。欧氏距离偏好差异分散在两个坐标上的点;曼哈顿距离则把每个坐标的差异全部计入。两个答案都没有错,它们是不同的分类器。
高维情形。 例如,若查询点和固定有限个训练点的所有坐标均为相互独立的标准高斯(Gauss)变量,则随着 增长,它们的距离会相对集中:最远距离与最近距离之比依概率收敛到 。在这个情形下,相对距离差异缩小。这是特定分布的性质,并非关于所有高维数据的定理。集中在低维结构附近的数据可能表现好得多。
计算
对单个查询,精确的暴力 kNN 如下进行:
- 计算全部 个距离,成本为 。
- 完整排序 记录,成本为 。选择算法可以在期望 时间内找出前 条记录,但必须遵守相同字典序。
- 统计票数需 。
- 存储训练数据需 内存,以上完整排序实现还需 个距离–下标记录。
基于树或哈希的索引可能减少查询时间,其收益取决于维度和数据分布,也可能退化到接近暴力搜索的成本。近似搜索以精确性换取速度;其输出可能不同于上面定义的精确规则,因此它是另一个分类器。
加权 kNN 用权重(如 )替代等权投票。当 时该权重无定义,必须说明约定。一种约定是:如果有距离为 的邻居,就只让这些零距离邻居等权投票。
例题 5.5.5
(加权可能翻转投票,也需要零距离规则)
取训练点 ,标签 ,。在查询点 ,距离为 。不加权的得分是 ,预测为 。若用权重 ,类别 的加权比例为 ,预测为 。
在查询点 ,第一个权重会是 。按上述约定只有下标 投票,预测为 。若不说明约定,加权规则恰好在训练点上没有定义,而这正是最可能被用来检查预测的边界情形。
有限样本噪声反例
有人可能这样推理:1NN 能拟合每个训练点,所以必定表现良好。下一个结果表明,即使在极简单的情形下,这种推断也不成立。
定理 5.5.6
(纯标签噪声下的 1NN 错误率)
设 几乎必然成立,,其中 。设训练对 ()是 的独立同分布副本,查询对 与训练样本独立。则使用下标平局规则的 1NN 测试错误率为
而由较优常数分类器达到的 Bayes 错误率为 。
证明
(计算两个错误率)
所有特征值均等于 ,故全部距离为 。下标规则于是无论数据如何都选择下标 ,预测为 。
查询标签 与 独立,且二者均服从 Bernoulli,因此
由于 不携带信息,最优分类器为常数。预测 的错误概率为 ,预测 的错误概率为 ,故 Bayes 错误率为 。
令 、,则 ,因为 。等号仅在 时成立。
证明透视
独立性用在哪里
退化的特征只起一个作用:使所有距离都为 ,于是无论标签如何,下标规则都选择下标 。预测 因而是训练数据的一个固定函数,在看到任何标签之前就已选定。
其余由查询与训练样本的独立性完成:它把 变成乘积计算。若查询改为训练点本身,例如 ,同一规则的错误率就是 ;这正是拟合训练集与预测新样本之间的差距。
假设 使比较 有意义:两个错误率都为正,并且除非 ,不等式是严格的。当 或 时,两个错误率都为 。
当 时,1NN 的错误概率为 ,而 Bayes 错误率为 。
快速检查
(设 几乎必然成立,。计算 1NN 风险与 Bayes 风险。)
以 应用定理。
解答 · 答案
1NN 风险为 。最优常数分类器预测 ,错误概率为 ,所以 1NN 的风险高出 。
这里有两个教训。第一,在训练点上的预测不是对独立查询点的预测。本例中所有训练预测都等于 ,所以只有当全部训练标签一致时,分类器才完全拟合训练集;当 时未必拟合。第二, 小不意味着测试错误率小。这个结果不支持也不否定其他假设下 kNN 的渐近表现;它只是一个精确的有限样本例子。
如何影响拟合。 较大的 对更多标签取平均,降低对单个噪声标签的敏感性,却会模糊边界。没有确定性的有限样本保证说准确率随 单调增加或单调减少。正如算例所示,极端情形 完全忽略特征。
澄清误解:得分不一定是概率
常见错误
(把五个邻居中有四个读成概率 0.8)
“五个邻居中四个属于类别 1,所以 。”这个结论并不成立。得分 只取值于 ,它依赖平局规则和缩放方式,也由有限样本计算得到。
在上述噪声例子中, 时每个得分都是 或 ,但真实条件概率处处为 。得分可以用于排序;在将它解释为概率之前,应在留出数据上评估校准情况。例如按得分对留出样本分组,比较每组平均得分与实际标签为 的频率。这种评估为校准提供证据,却不是校准的证明。
无泄漏验证
选择 、距离或特征属于模型选择,必须遵守与其他模型选择相同的纪律:
- 所有依赖数据的预处理步骤都只能在训练折上学习,包括缩放均值和标准差、缺失值填补值与特征选择,然后将学得的变换应用到留出行。
- 在所有选择固定之前,最终测试集保持不被使用。
- 随机独立同分布划分假设各行可交换。聚类数据(例如同一人的多条记录)需要按组划分;按时间排列的数据需要尊重时间顺序。若存在分布偏移,验证表现未必能转移到实际应用人群。
常见错误
(留一法之前只标准化一次)
先用全部 行拟合缩放器或填补器,再做留一法评估,会让每个留出行影响它自己的预处理。必须在拟合任何预处理之前先移除留出的观测;每次留出一个样本时,都要在剩余 行上重新拟合缩放器和填补器。
练习
练习 5.5.7
(对算例数据,在 处求 2NN 预测,并讨论其他票数平局规则。)
基础
解答(3)
- 1
应用既定规则
排序的前两项为 ,距离均为 ;标签 、,故 ,对应类别 。
- 2
比较其他票数平局规则
若平局时优先类别 ,预测为 。若退回到 个邻居,则使用下标 ,预测为 。若扩展到 个邻居,就会遇到算例中下标 和 的距离平局,结果也取决于距离平局规则。
- 3
得出结论
每种规则都有其合理性,但可能得到不同的分类器,因此必须事先固定。
练习 5.5.8
(训练数据为 和 ,取 和下标平局规则。求训练预测和留一预测,并讨论泄漏。)
核心
解答(4)
- 1
计算训练预测
在 ,下标 和 的距离都是 ,下标 在前,所以两条位置重复的行都预测为 ,第 行被误分类。任何 1NN 规则都不能同时拟合位置相同而标签不同的两行。在 ,预测为 。训练错误率为 。
- 2
计算留一预测
关键一步
留出第 行时,下标 在距离 处,预测 ,真实标签为 。留出第 行时,下标 预测 ,真实标签为 。留出第 行时,下标 和 在距离 处平局,选下标 ,预测 ,真实标签为 。留一错误率为 。
- 3
检查预处理
每一步留一都必须在不含留出行的数据上重新拟合标准化器或填补器。只有一个特征时,正数倍缩放不改变邻居顺序。但留出第 行时,剩余数值 的标准差为 ,标准化器必须明确规定这种情形的处理方式。
- 4
讨论重复记录
若第 、 行是同一患者的两条记录,随机划分可能把一条放在训练集,另一条放在留出集。此时评估衡量的是对该患者的记忆,而非对新患者的泛化。把同一患者的所有记录放进同一折,可防止这种重叠。
相关笔记
- 分类规则与误分类风险
- 距离与特征标准化
- 交叉验证与留出测试
- 分类得分的校准