k 近邻密度估计与局部方法

层级：B｜按需

1. 固定邻居数、让体积自适应

KDE 固定带宽，局部包含的样本数变化；kNN 密度固定邻居数 $k$ ，让邻域半径随数据密度变化：密集区半径小，稀疏区半径大。

2. kNN 密度估计

在 $d$ 维点 $x$ ，取包含第 $k$ 个近邻的球体积 $V_k(x)$ ：

\hat p(x)=\frac{k}{nV_k(x)}

有时分子用 $k-1$ 、分母用 $n$ 或 $n-1$ ，依是否包含查询点/留一估计。核心是“局部概率质量约 $k/n$ 除以体积”。

Euclidean 半径 $r$ 的 $d$ 维球体积：

V_d(r)=\frac{\pi^{d/2}}{\Gamma(d/2+1)}r^d.

3. k 的偏差—方差

$k$ 小：邻域小、低偏差但高方差，对噪声敏感；
$k$ 大：估计稳定但跨越不同密度区域，高偏差。

一致性通常要求随 $n$ 增加：

k\to\infty, \qquad k/n\to0.

既让局部样本数增多，又让邻域相对收缩。

4. kNN 分类

找到 $k$ 个最近训练样本，估计后验：

\hat P(Y=c|x) =\frac1k\sum_{i\in N_k(x)} \mathbf1\{y_i=c\}.

预测多数类。也可按距离加权：近邻权重更大，但要处理距离为零与带宽。

kNN 是 lazy learner：训练几乎只存数据，预测时计算昂贵。

5. kNN 回归

\hat f(x)=\frac1k\sum_{i\in N_k(x)}y_i.

它估计局部条件均值；距离加权得到局部常数核回归。局部线性回归在邻域拟合斜率，可减少边界偏差。

6. 距离与缩放

邻居完全由度量决定：

数值特征需缩放；
类别特征需 Hamming/Gower/embedding；
相关特征可用 Mahalanobis/度量学习；
缺失值需专门处理；
无关高维特征会淹没有用距离。

预处理必须只在训练集拟合。

7. 维数灾难

若每个维度取值范围归一化，要覆盖每维边长比例 $r$ 的局部立方体，其体积比例为 $r^d$ 。想包含固定比例样本，高维邻域半径必须很大，不再“局部”。

距离还可能集中，最近/最远差相对缩小。kNN 需要降维、特征选择、学习表示或任务相关度量。

8. Bayes 一致性

适当条件且 $k\to\infty,k/n\to0$ 时，kNN 分类风险趋近 Bayes 风险。固定 $k=1$ 的经典结果给渐近错误率不超过 Bayes 错误率某个界，但 1-NN 本身高方差。

理论是渐近且依度量/分布，有限高维数据表现仍可能差。

9. 异常与局部离群

第 $k$ 近邻距离大表示局部稀疏，可作为异常分数。Local Outlier Factor（LOF）比较点与邻居的局部可达密度，能发现相对局部异常。

密度差异大的多簇中，全局 kNN 距离阈值会把稀疏正常簇误判，局部比较更合适。

10. 近似最近邻

精确暴力查询 $O(nd)$ 每点。可用：

kd-tree/ball tree：低中维；
HNSW 图；
IVF/PQ；
LSH；
GPU brute force。

近似索引在召回、内存、构建时间、更新和延迟间权衡。向量是否归一化决定内积与余弦/Euclidean 排名关系。

11. 数据泄漏与重复

查询点自身在训练集时距离 0，会产生过于乐观密度/准确率；训练指标需 leave-one-out。近重复样本跨训练测试也会让 kNN 看似极强，必须按实体/来源去重分组。

12. 概率校准

邻居类别比例是局部频率估计，但小 $k$ 只能取离散网格 $0,1/k,ldots,1$ ，高维与采样偏差使其不一定校准。可用更大 $k$ 、平滑、单独校准集，但不能用测试标签。

易错点

kNN 不等于 k-means，前者监督/局部邻居，后者聚类中心。
距离前必须处理尺度和特征语义。
高维最近邻可能不再局部。
查询自身/重复样本会泄漏。
kNN 比例不自动是可靠概率。

常见问答

Q1：k 为什么常取奇数？

二分类可减少平票，但多类/加权仍可能平票；应通过验证选择并定义 tie-break。

Q2：训练 kNN 时什么都不做吗？

仍需预处理、特征/度量选择、索引构建和超参数选择；只是没有传统参数拟合。

Q3：embedding 检索用余弦还是 L2？

归一化向量上两者排序等价： $\|u-v\|^2=2-2u^Tv$ 。未归一化时长度含义不同，需按训练目标选择。

练习

写出 kNN 密度核心公式。
k 太小/大各有什么问题？
kNN 分类怎样估后验？
高维为何邻域不局部？
查询自身为何要 leave-one-out？

答案与提示

$k/(nV_k(x))$ （约定可能微调）。
小高方差，大高偏差。
邻居中各类比例。
固定质量所需半径随维度增长，距离趋集中。
自身零距离会人为提高密度/正确率。