描述：本节整理 KNN 的分类与回归规则、懒惰学习、$L_p$ 距离、$k$ 值的偏差-方差权衡、多数表决的风险含义，以及 kd 树的构造和最近邻回溯搜索。

10.1 KNN 基本概念

K 近邻（k-Nearest Neighbor，KNN）是一种常用监督学习方法。

给定测试样本：

1. 根据某种距离度量，在训练集中找出距离最近的 $k$ 个样本。
2. 利用这 $k$ 个邻居的标记预测。

分类任务：

• 使用多数投票，把邻居中出现次数最多的类别作为预测。
• 也可按距离加权投票，越近的邻居权重越大。

回归任务：

• 使用邻居输出的平均值。
• 也可按距离加权平均。

10.2 懒惰学习

• KNN 是懒惰学习（lazy learning）的代表。
• 训练阶段主要保存样本，不显式拟合参数化模型，训练开销很小。
• 收到测试样本后才计算距离、寻找邻居并预测，因此预测开销较大。
• 与之相对，急切学习（eager learning）在训练阶段就拟合模型，预测时直接使用已学参数。

当以下四项确定后，KNN 对任意输入的预测规则也随之确定：

1. 训练集。
2. 距离度量。
3. $k$ 值。
4. 分类或回归决策规则。

• 这些要素共同把特征空间隐式划分成不同预测区域，因此 KNN 仍然定义了模型，只是模型由训练样本直接表示。

10.3 KNN 分类算法

训练集为

$$ T= {(\boldsymbol{x}_1,y_1), (\boldsymbol{x}_2,y_2), \ldots, (\boldsymbol{x}_N,y_N)}, $$

其中

$$ \boldsymbol{x}_i\in\mathcal X\subseteq\mathbb R^n, \qquad y_i\in\mathcal Y={c_1,c_2,\ldots,c_K}. $$

对输入 $\boldsymbol{x}$：

1. 找到训练集中与 $\boldsymbol{x}$ 最近的 $k$ 个点，邻域记为 $N_k(\boldsymbol{x})$。
2. 使用多数表决：

$$ \hat y

\mathop{\arg\max}{c_j} \sum{\boldsymbol{x}_i\in N_k(\boldsymbol{x})} \mathbb I(y_i=c_j). $$

• 若票数相同，需要预先规定平票规则，例如选择距离总和更小的类别。
• 距离加权投票可写为

$$ \hat y

\mathop{\arg\max}{c_j} \sum{\boldsymbol{x}_i\in N_k(\boldsymbol{x})} \omega_i \mathbb I(y_i=c_j), $$

其中 $\omega_i$ 随距离增大而减小。

10.4 最近邻误差界

源资料指出，最近邻分类器的泛化错误率不超过贝叶斯最优分类器错误率的两倍。

更精确地，在相应分布和渐近条件下，1-NN 的渐近错误率 $R_{\mathrm{1NN}}$ 满足 Cover-Hart 界：

$$ R_{\mathrm{1NN}} \leq R^(2-R^) \leq 2R^*, $$

其中 $R^*$ 是贝叶斯最优错误率。

• 这是渐近理论界，不表示任意有限样本、任意距离和任意维度下测试误差都严格不超过两倍。

10.5 距离度量

设

$$ \boldsymbol{x}_i =(x_i^{(1)},x_i^{(2)},\ldots,x_i^{(n)})^\mathrm T, $$

$$ \boldsymbol{x}_j =(x_j^{(1)},x_j^{(2)},\ldots,x_j^{(n)})^\mathrm T. $$

$L_p$ 距离为

$$ L_p(\boldsymbol{x}_i,\boldsymbol{x}_j)

\left( \sum_{l=1}^{n} \left| x_i^{(l)}-x_j^{(l)} \right|^p \right)^{1/p}, \qquad p\geq1. $$

10.5.1 欧氏距离

当 $p=2$：

$$ L_2(\boldsymbol{x}_i,\boldsymbol{x}_j)

\left( \sum_{l=1}^{n} \left| x_i^{(l)}-x_j^{(l)} \right|^2 \right)^{1/2}. $$

10.5.2 曼哈顿距离

当 $p=1$：

$$ L_1(\boldsymbol{x}_i,\boldsymbol{x}_j)

\sum_{l=1}^{n} \left| x_i^{(l)}-x_j^{(l)} \right|. $$

10.5.3 切比雪夫距离

当 $p\rightarrow\infty$：

$$ L_\infty(\boldsymbol{x}_i,\boldsymbol{x}_j)

\max_l \left| x_i^{(l)}-x_j^{(l)} \right|. $$

二维空间中，以原点为中心、距离为 $1$ 的单位球形状：

• 距离度量决定“近邻”的含义，可能直接改变分类边界。
• 不同特征量纲差异较大时要先标准化。

10.6 $k$ 值选择

10.6.1 较小的 $k$

• 邻域小，只有非常相似的样本参与预测。
• 近似误差较小，局部细节表达能力强。
• 估计误差较大，对单个噪声点敏感。
• 模型更复杂，容易过拟合。

10.6.2 较大的 $k$

• 邻域大，更多较远样本参与预测。
• 估计误差降低，结果更稳定。
• 近似误差增大，局部结构被平滑。
• 模型更简单，可能欠拟合。

极端情况下，

$$ k=N, $$

分类器对所有输入都预测训练集中数量最多的类别，几乎忽略输入位置。

• $k$ 应通过验证集或交叉验证选择。
• 二分类常选择奇数 $k$ 减少平票，但多分类或类别数量分布复杂时仍可能平票。

10.7 多数表决与 0-1 损失

若预测邻域 $N_k(\boldsymbol{x})$ 为类别 $c_j$，该邻域上的经验误分类率为

$$ \frac{1}{k} \sum_{\boldsymbol{x}_i\in N_k(\boldsymbol{x})} \mathbb I(y_i\neq c_j). $$

利用

$$ \mathbb I(y_i\neq c_j) =1-\mathbb I(y_i=c_j), $$

有

$$ \frac{1}{k} \sum_{\boldsymbol{x}_i\in N_k(\boldsymbol{x})} \mathbb I(y_i\neq c_j)

1- \frac{1}{k} \sum_{\boldsymbol{x}_i\in N_k(\boldsymbol{x})} \mathbb I(y_i=c_j). $$

• 因而在 0-1 损失下，选择邻域中票数最多的类别，等价于最小化邻域经验误分类率。

10.8 kd 树

kd 树是一种对 $k$ 维空间中的实例点进行组织，以便快速检索的二叉树结构。

• 每个结点对应一个由坐标轴对齐边界确定的 $k$ 维超矩形区域。
• 每次用垂直于某个坐标轴的超平面把区域分为两个子区域。
• 实例点保存在相应结点中。

10.8.1 构造过程

1. 根结点对应包含全部实例的超矩形。
2. 选择一个坐标轴和该轴上的切分点。
3. 通过切分点作垂直于该轴的超平面，把区域分为左右两个子区域。
4. 把样本分到两个子区域，并对各区域递归切分。
5. 子区域内没有更多实例可分时终止。

• 常见实现轮换坐标轴，并选择该轴坐标的中位数，使树较平衡。

10.8.2 源资料构造示例

数据集：

$$ T= { (2,3)^\mathrm T, (5,4)^\mathrm T, (9,6)^\mathrm T, (4,7)^\mathrm T, (8,1)^\mathrm T, (7,2)^\mathrm T }. $$

按坐标轴交替、取中位点构造：

• 根结点为 $(7,2)$，以 $x^{(1)}=7$ 切分。
• 左子树根为 $(5,4)$，其子结点为 $(2,3)$ 和 $(4,7)$。
• 右子树根为 $(9,6)$，其子结点为 $(8,1)$。

对应树形结构：

$$ \begin{array}{c} (7,2)\ /\qquad\backslash\ (5,4)\qquad(9,6)\ /\quad\backslash\qquad/\ (2,3)\quad(4,7)\quad(8,1) \end{array} $$

10.9 kd 树最近邻搜索

给定目标点 $\boldsymbol{x}$：

1. 从根结点按切分坐标向下访问，找到包含目标点的叶结点。
2. 把该叶结点实例作为当前最近点。
3. 从叶结点向父结点回溯。
4. 若父结点实例更近，就更新当前最近点。
5. 以目标点为球心、当前最小距离为半径形成超球体。
6. 若兄弟子树对应超矩形与超球体相交，兄弟区域内可能存在更近点，必须进入该子树继续搜索。
7. 若不相交，可剪去该子树。
8. 回溯到根且所有可能区域都已检查后，当前最近点即为结果。

源资料图示过程：

• 先找到包含目标点 $S$ 的叶结点 $D$，暂以 $D$ 为最近邻。
• 回到父结点 $B$，其另一子区域 $F$ 与以 $S$ 为圆心、$SD$ 为半径的圆不相交，剪枝。
• 回到更高层 $A$，另一子区域 $C$ 与圆相交，需进入检查。
• 区域内点 $E$ 比 $D$ 更近，因此把 $E$ 更新为最近邻。

10.10 kd 树效率与局限

• 数据较随机、树较平衡且维度较低时，平均查询可接近 $O(\log N)$。
• 最坏情况下需要检查大量结点，复杂度可退化为 $O(N)$。
• 维度升高后，超球体容易与许多超矩形相交，剪枝能力下降，出现“维数灾难”。
• 因而 kd 树适合中低维精确近邻搜索，高维数据常需近似近邻等方法。

10.11 易错点

• KNN 是有监督学习，K-Means 是无监督学习。
• KNN 的“训练开销接近 0”不表示没有存储开销；它通常要保存全部训练样本。
• $k$ 越小模型越复杂、方差越大；$k$ 越大模型越简单、偏差越大。
• 距离度量和特征标准化会直接改变近邻集合。
• 多数投票在 0-1 损失下最小化局部经验错误，不表示对所有代价函数都最优。
• 1-NN 的“两倍贝叶斯错误率”是带条件的渐近上界，不能误当作任意有限测试集保证。
• kd 树中的 $k$ 表示空间维数，不是 KNN 的邻居数量 $k$。
• kd 树搜索不能找到叶结点后立即停止，必须回溯并检查与当前超球体相交的兄弟区域。
• kd 树平均 $O(\log N)$ 依赖树平衡、维度和数据分布，最坏可退化为线性扫描。

相关知识

• 科目导航：复试常考科目导航
• 阅读顺序：上一篇：聚类 · 下一篇：PyTorch 总结
• 关联专题：距离度量与聚类

10.12 本节复盘

• KNN 保存训练样本，预测时寻找最近的 $k$ 个邻居；分类投票，回归平均，也可按距离加权。
• KNN 是懒惰学习，训练简单但预测和存储开销较大。
• $L_p$ 距离在 $p=1,2,\infty$ 时分别对应曼哈顿、欧氏和切比雪夫距离。
• 小 $k$ 低偏差高方差，容易过拟合；大 $k$ 高偏差低方差，可能欠拟合。
• 多数表决等价于在邻域内最小化 0-1 经验损失。
• kd 树用坐标轴对齐超平面递归划分空间，可通过超矩形与当前搜索超球体是否相交来剪枝。
• kd 树在低维、平衡条件下查询较快，但高维或最坏情况下可能退化为近似线性扫描。