从邻域到决策
密度估计关心某个位置附近有多少概率质量;分类则问,附近的观测有多少属于类别一。局部比例可以在不预先设定有限维公式的情况下估计条件类别概率,因此决策边界可以弯曲,但距离、特征单位和邻居个数都会影响结果。
定义 25.1.1
( 近邻投票与决策)
设 ,,是 的独立同分布副本,其中 、。固定查询点 ,按欧氏距离(Euclidean distance)排列样本;距离相同则按下标决定顺序。对 ,令 为前 个下标,定义
平票依约判为一,也可事先采用其他固定规则。
记 为条件概率的一个版本;下面的定理要求该版本在查询点连续。误判代价相等时,一个贝叶斯(Bayes)决策为 。代价不等时阈值会改变:估计概率与据此作决策是两件不同的事。
例题 25.1.2
(三个邻居与五个邻居)
训练对为 ,查询 。距离从小到大为 1、1、2、3、4,按下标处理平距后标签依次为 。 时估计为 , 时为 ;等代价下都判为一。若假阳性的代价是假阴性的四倍,行动一、零的条件风险分别为 和 ,因此只有 才判一。代入上述两个估计,行动都变为零。这些比例只是局部估计,并不保证真实条件概率等于它们。
邻居数与半径为何都重要
若 保持很小,即使邻居很近,标签仍有随机波动;若 保持很大,邻域未必收缩,远处标签会造成持续偏差。以下结果只针对一个固定查询点,不声称一致收敛或收敛速率。
定理 25.1.3
(逐点概率与超额风险一致性)
假设 在 连续,且对每个 都有 。若整数 满足 、,则 依概率收敛到 。在零一损失下,随机拟合决策 在 的条件超额风险也依概率收敛到零。
证明
(收缩半径并平均标签噪声)
固定 ,记 。球内训练特征的数目 服从二项分布,均值为 ,方差为 。最终 ;由切比雪夫(Chebyshev)不等式,。因此第 个邻居的距离 依概率趋于零。
以全部训练特征为条件,标签几乎处处条件独立且为均值 的伯努利(Bernoulli)变量。令 。投票的条件方差至多为 ,故条件切比雪夫不等式给出 (依概率)。由 在 连续和 ,有 (依概率):对于任意容差,可选适当的 ,使 时每个求和项与 的差都小于该容差。合并两项即得第一结论。
固定训练样本时,在 选择一的条件错误率为 ,选择零则为 。若拟合行动不同于某个贝叶斯行动,则 与 位于 的相反侧(平票不影响结论)。条件超额错误率至多为 ;行动相同时为零。因此得到第二结论。这里测试标签是新的,且其在 的分布由同一个 定义。
证明透视
两种不同的误差
半径论证控制附近的条件均值与目标的差;方差论证控制标签相对于这些均值的随机波动。两者缺一不可:很近的标签仍可能有噪声,而精确平均远处邻域也可能估错目标。
反例模式
一个邻居无法平均掉噪声
设所有特征都为零,标签独立服从伯努利。在 ,按平距规则,一个邻居的估计就是第一个标签。无论 多大,估计都是零或一,与 至少相差 ,所以不依概率收敛到 。对独立测试标签的期望分类错误率是 ,高于贝叶斯错误率 。
例题 25.1.4
(训练准确率完美,留一法准确率为零)
取一维四点 ,标签为 。取 并把训练点本身计入时,每个点都是自己的最近邻,距离为零,所以训练准确率为 。现在逐一留出每个点,只用其余三点分类。点 的最近邻是点 ,标签为 :错。点 的邻居 与 距离都是一,标签都是 :错。点 的邻居 与 标签都是 :错。点 的最近邻是点 ,标签为 :错。留一法准确率是 。取 时,点 的留一估计依次为 ,预测依次为 ,每个点仍然判错。这个标签排列刻意取得不平滑,但它说明 的训练准确率对新样本没有提供任何信息。
例题 25.1.5
(改变单位会改变最近邻)
取两个训练点 (标签 )与 (标签 ),查询点为 。欧氏距离到 是 ,到 是 ,所以单一邻居规则预测 。现在把第二个坐标改用大十倍的单位:、、查询点 。距离变为 与 ,最近邻变成 ,预测为 。数据相同,规则却改变了,因为欧氏距离依赖单位。因此特征缩放是流程的一部分,必须只用训练数据选定。
常见错误
(训练集上的好投票不保证测试表现)
时,训练观测通常以自己为最近邻,训练准确率可能看似完美,而新样本预测仍然很差。应仅用训练折选择 、拟合特征缩放及其他预处理,再用未参与这些选择的数据评价整个选择流程。
常见错误
(较大的 以方差换偏差)
较大的 可能降低投票方差,却也可能模糊边界。高维下,要使邻域真正局部往往需要更多数据,因此定理不是有限样本表现保证。
练习与解答
快速检查
(某查询点的五个有序标签为 。求 时的估计与等代价决策。)
对前 个标签取平均。
解答 · 答案
估计依次为 、、,决策依次为零、一、零。同一组有序数据采用不同的 可以改变决策。
快速检查
(令 ,检查定理的两个条件。若 呢?)
计算 。
解答 · 答案
平方根序列趋于无穷,且与 的比趋于零。若 ,该比为一,邻域就是全部样本,收缩邻域的论证不适用。
快速检查
(设 ,而拟合估计为 。求条件超额零一风险,并与证明中的界比较。)
先找出拟合的行动。
解答 · 答案
拟合行动为零,条件错误率为 ;贝叶斯行动为一,错误率为 。超额错误率为 ,不超过 。这里针对固定 的新标签。