1-NN分类器：距离、平局与无泄漏特征

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练矩阵N×D有限数，labels任意可保留标记；queries Q×D。距离为平方Euclidean、tie按输入顺序，不默认cosine或k>1投票。
• 题目只有1-NN名称，数据与正式metric未给；本文是明确合同的算法训练，不报告真实面试成绩。

解题路线

1. 逐query计算每个train距离Σ_j(x_j−q_j)²，argmin取最早训练下标输出其label；不用sqrt，因为单调不改变最小值。
2. 特征量纲影响距离，scaler仅fit train再用于query。分类标签不进距离；one-hot类别或文本embedding是否适合该metric需要验证。
3. 训练自身预测包含自身会几乎全对，不能当泛化评估。leave-one-out时只排除当前样本identity，不误删所有同特征样本；近重复需group split。
4. 大N/D用exact block扫描减少临时内存，ANN改善延迟但可能改变预测，需measure recall与分类指标。距离溢出/NaN不可让argmin静默产错误label。

手动走一遍

train−1/label left与+1/right，query0等距，训练按最早下标返回left；输入顺序变则tie结果变，需声明。5001组整数特征用独立逐坐标/全部样本距离扫描核对。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

import numpy as np

def predict(train_features,train_labels,queries):
    x=np.asarray(train_features,dtype=float);q=np.asarray(queries,dtype=float);labels=list(train_labels)
    if x.ndim!=2 or not len(x) or not x.shape[1] or q.ndim!=2 or q.shape[1]!=x.shape[1] or len(labels)!=len(x):raise ValueError('shape/nonempty training')
    if not np.isfinite(x).all() or not np.isfinite(q).all():raise ValueError('finite features')
    output=[]
    for query in q:
        difference=x-query;distance=np.sum(difference*difference,axis=1)
        if not np.isfinite(distance).all():raise ValueError('distance overflow')
        output.append(labels[int(np.argmin(distance))])
    return output

复杂度

Qqueries、Ntrain、Dfeatures，时间O(QND)，示例每query O(ND)临时difference，输入O(ND)。一次保存所有query×train差为O(QND)内存没有必要；输出O(Q)。

易错点与追问

容易失分的边界

• 把训练集含自身高准确率当test结果。
• scaler在全数据fit造成信息泄漏。

继续深挖

• 改cosine距离时零向量与归一化怎么处理？
• 选择K>1后投票权重、平局与类概率如何定？