k 近邻回归 | Codeboy's Blog

形式陈述

设有 $n\ge1$ 个训练对 $(X_i,Y_i)\in\mathbb R^d\times\mathbb R$ ，查询输入为 $x$ 。平方损失回归的目标是条件均值 $m(x)=E(Y\mid X=x)$ 。 $k$ 近邻回归先找距离 $x$ 最近的 $k$ 个训练输入，再平均它们的响应。

预先固定距离、整数 $1\le k\le n$ 和每条记录的唯一编号。按 $(\|X_i-x\|_2,i)$ 的字典序排列，取前 $k$ 个编号组成 $N_k(x)$ ，返回

\widehat m_k(x)=\frac1k\sum_{i\in N_k(x)}Y_i.\tag{1}

编号只用于打破距离并列，不能根据响应挑选。重复坐标仍是不同观测； $k$ 计记录数。训练输入为空或 $k$ 越界时报告输入错误，不临时改变 $k$ 。可另行约定不同距离或随机并列规则，但它们构成另一条完整算法。

式(1)在给定输入、 $k$ 和并列规则后对响应是线性的。它不要求 $m$ 是直线，也不要求把整个输入空间划成固定 $k$ 块。给定设计 $X_{1:n}$ ，若

Y_i=m(X_i)+\varepsilon_i,\qquad E(\varepsilon_i\mid X_{1:n})=0,

且噪声条件独立、条件方差 $\sigma_i^2<\infty$ ，则

b_X(x)=E(\widehat m_k(x)\mid X_{1:n})-m(x) =\frac1k\sum_{i\in N_k(x)}[m(X_i)-m(x)],

v_X(x)=\operatorname{Var}(\widehat m_k(x)\mid X_{1:n}) =\frac1{k^2}\sum_{i\in N_k(x)}\sigma_i^2.\tag{2}

IID 训练对及有限条件方差满足上述条件化结构；条件方差可以随输入变化。若训练记录共享未建模噪声，方差还含协方差项。

直觉

邻域承担两种相反作用。多收几位邻居，独立噪声能平均得更稳；但邻居更远，其条件均值未必接近查询处。 $k$ 固定了使用多少条记录，邻域半径则随样本密度而变：密集处收得紧，稀疏处伸得远。

“近”取决于量纲。用米还是千米记录一个坐标，若不同时调整距离，其邻居名单会改变。标准化也是学习流程的一部分；尺度若由数据估计，应只用相应训练折。类别编号之间的整数差通常不代表真实距离。

例子与边界

并列规则决定一份可复算的输出

四条记录依编号为 $(0,0),(1,2),(3,6),(4,8)$ ，查询 $x=2$ 。距离依次是 $(2,1,1,2)$ ，所以排序为 $2,3,1,4$ 。

$k=1$ 时返回 $2$ ；距离同为1的第三条没有因为响应较大而优先
$k=2$ 时返回 $(2+6)/2=4$
$k=3$ 时返回 $(2+6+0)/3=8/3$

若第三个邻居改取第四条，结果为 $16/3$ 。这说明并列不是只影响显示顺序。若 $m(t)=2t$ 且条件噪声方差均为1， $k=2$ 的条件偏差为零、方差为 $1/2$ ； $k=3$ 的偏差为 $-4/3$ 、方差为 $1/3$ ，条件均方误差为 $16/9+1/3=19/9$ 。这个局部数据上，多一个邻居反而使误差上升。

一次单位变换可以交换最近邻

查询为 $(0,0)$ ，只有A点 $(0,3)$ 、响应0，B点 $(2,0)$ 、响应10。普通欧氏距离分别为3和2，1近邻预测10。若第二个坐标改用原单位的十分之一，坐标变为 $(0,0.3)$ 与 $(2,0)$ ，预测变为0。要保持原几何，应在新坐标距离中相应补回因子10；把改单位误当成增加信息，会使结果不可解释。

固定 k 留下噪声，固定比例留下非局部偏差

若 $m\equiv0$ 且噪声独立、方差1，任意样本量下固定 $k=1$ 都有方差1。邻居无限接近查询处也不能消掉该观测本身的噪声。

另令 $X\sim U[0,1]$ 、 $Y=X$ 、查询 $x=0$ ，取 $k=n$ 。预测趋于 $1/2$ ，与连续版本 $m(0)=0$ 相差 $1/2$ 。这里没有观测噪声，失败来自邻域始终覆盖整个区间。位于输入支持之外的查询也不能靠普通近邻保证一致：数据不会自动提供外推依据。

推论与应用

从局部几何得到误差界

若 $m$ 满足 $|m(u)-m(v)|\le L\|u-v\|_2$ ，噪声方差至多 $\sigma^2$ ，记第 $k$ 个邻居距离为 $R_k(x)$ 。式(2)与偏差—方差分解给出有限样本条件界

E[(\widehat m_k(x)-m(x))^2\mid X_{1:n}] \le L^2R_k(x)^2+\frac{\sigma^2}{k}.\tag{3}

第一项由每个邻居均在半径 $R_k$ 内得到，第二项由独立加权求和得到。它把统计误差和检索任务接在一起，却没有假设任何检索数据结构。

现取IID输入，所有输入到固定查询 $x$ 的距离至多 $D$ ，并假定在 $0<r\le r_0$ 时有局部质量下界

P(\|X-x\|_2\le r)\ge c r^d,\qquad c>0.

取 $r=(2k/(cn))^{1/d}\le r_0$ 。球内数量 $N_r$ 是二项计数，均值 $\mu\ge2k$ 。事件 $R_k>r$ 蕴含 $N_r<k\le\mu/2$ ，故二项下尾 Chernoff 界给

P(R_k>r)\le e^{-\mu/8}\le e^{-k/4}.

分别在 $R_k\le r$ 和其补集上界住平方距离，得到

E[(\widehat m_k(x)-m(x))^2] \le L^2\left[\left(\frac{2k}{cn}\right)^{2/d}+D^2e^{-k/4}\right]+\frac{\sigma^2}{k}.\tag{4}

因此 $k\to\infty$ 、 $k/n\to0$ 在这组明确条件下给点态均方一致性。平衡 $(k/n)^{2/d}$ 与 $1/k$ ，取 $k\asymp n^{2/(d+2)}$ ，得到 $O(n^{-2/(d+2)})$ 的点态MSE上界。 $d=1$ 时指数为 $2/3$ ， $d=4$ 时仅为 $1/3$ ；只比较这个幂次、忽略常数，MSE上界的幂次部分缩小十倍所需样本倍数分别为 $10^{3/2}$ 与 $10^3$ 。这不是对具体数据的精确样本量承诺。

光滑度、质量下界和有界直径是本证明的条件。欧氏空间还有更一般的普适一致性定理，但不能把式(4)的定量率直接移给任意分布、任意距离或一个低密度尾部点。

实现与代价

最直接的查询计算 $n$ 个 $d$ 维距离，排序后求和，成本为 $O(nd+n\log n+k)$ 、保存数据需 $O(nd+n)$ 。维护大小 $k$ 的最大堆可把排序部分改为 $O(n\log(k+1))$ ；初始化空堆，依既定距离/编号比较保留最小的 $k$ 条，扫描结束即停止。近似检索若漏掉真正邻居，应报告近似规则，式(3)应改用实际所选点的最大半径。

k-d tree可为合适维数和数据加速距离搜索，但其最近邻查询最坏仍可能扫描全部数据。检索快不等于回归风险低。选择 $k$ 可接入局部方法的验证协议；验证时必须在删点后重新找足 $k$ 个邻居。

自测与答案

四点例中用 $k=4$ 预测查询2，条件噪声方差仍为1，偏差和方差是多少？预测均值为4，偏差0，方差 $1/4$ 。 $k$ 增大时偏差不必逐项单调。
把同一条噪声读数复制 $k$ 次再平均，会有方差 $\sigma^2/k$ 吗？不会；完全共享噪声时协方差项补回全部差额，平均的方差仍为 $\sigma^2$ 。

参考资料

Ryan Tibshirani, Nonparametric Regression, CMU Statistical Machine Learning, Spring 2017，§1.6–1.7，PDF pp. 3–5：近邻定义、条件偏差方差与维数问题。式(4)给出本页另行写全的局部质量条件及二项下尾推导。
László Györfi, Michael Kohler, Adam Krzyżak and Harro Walk, A Distribution-Free Theory of Nonparametric Regression, 2002，§6.2–6.3；更一般一致性与速率的后续阅读，本页不以该书未展开的定理替代式(4)的证明。

形式陈述 ​

并列规则决定一份可复算的输出 ​

一次单位变换可以交换最近邻 ​

固定 k 留下噪声，固定比例留下非局部偏差 ​

从局部几何得到误差界 ​

实现与代价 ​

自测与答案 ​

反向链接