最近邻算法

最近邻算法 (k-Nearest Neighbors, KNN)

k-最近邻算法→监督学习中非参数/惰性学习方法→核心直觉：相似样本应有相似标签→无需训练过程→预测时基于训练集中与输入最相似的k个邻居的标签投票/平均。

算法原理

给定训练集$\{(x_i,y_i)\}_{i=1}^n$，对新样本$x$：计算$x$与$x_i$的距离$d(x,x_i)$→选距离最小的k个邻居$\mathcal{N}_k(x)$→分类：多数投票$\hat{y}=\arg\max_c\sum_{i\in\mathcal{N}_k}\mathbf{1}[y_i=c]$→回归：均值$\hat{y}=\frac{1}{k}\sum_{i\in\mathcal{N}_k}y_i$或距离加权$\hat{y}=\frac{\sum w_i y_i}{\sum w_i}$，$w_i=1/d(x,x_i)$。

距离度量：欧氏距离最常用($L_2$)→$\|\mathbf{x}-\mathbf{x}_i\|_2$；曼哈顿距离($L_1$)适用于高维稀疏→闵可夫斯基距离统一形式$\|\mathbf{x}-\mathbf{x}_i\|_p=(\sum|x_j-x_{ij}|^p)^{1/p}$；余弦相似度用于文本分类/信息检索→归一化内积度量方向相似性。

关键参数与选择

k的选择是核心权衡：k过小→过拟合，对噪声敏感，决策边界复杂曲折→k过大→欠拟合，决策边界过平滑，可能包含远距离无关样本→典型做法：交叉验证选最优k→常用奇数k避免分类平局（二分类）。

距离加权：近邻权重$w_i\propto1/d(x,x_i)^p$→近邻影响更大→降低对k的敏感度→Shepard插值特例(p→∞等价k=1)。

理论性质

非参数性：不作数据分布假设→决策边界灵活→贝叶斯风险下，$n\to\infty,k\to\infty,k/n\to0$时KNN错误率逼近贝叶斯最优分类器的两倍→Cover-Hart(1967)证明：1-NN渐近错误率≤2倍贝叶斯风险。

维数灾难：高维空间→所有点距离趋于相等→最近邻失去局部意义→有效需$n\propto\exp(d)$样本量→实践中$d>10$时谨慎→降维(PCA)/特征选择常前置。

计算加速

朴素KNN预测复杂度$O(nd)$→n为训练集大小→大规模不可行→kd树/球树空间索引结构→将搜索降至$O(\log n)$期望→局部敏感哈希(LSH)近似近邻→ANN库(如Faiss/Annoy)工业级实现。

应用与经济关联

推荐系统：用户-物品特征空间→相似用户行为预测偏好→协同过滤基础。信用评分：相似申请人历史违约记录→判定信用风险。异常检测：孤立样本的邻居距离异常大→标记异常。计量经济学：匹配估计量→反事实推断中最近邻匹配处理组与控制组→倾向得分匹配可视为KNN在得分空间的实例。

记忆：KNN="相似输入→相似输出"→无训练阶段→k控制平滑度→高维需降维→kd树加速搜索→非参数基准模型常作为复杂模型性能对比底线。