核心要点

  • KNN 是惰性学习：训练只存数据，预测时才计算距离并投票，无显式训练过程

  • 用广播一次性算出测试集到训练集的距离矩阵，再用 np.argpartition 取每行最近 K 个，比全排序快

  • 投票用 np.bincount 统计 K 个邻居的标签，取众数；平票可按距离加权或回退更小的 K

  • 距离尺度敏感，特征需先标准化；K 太小易过拟合（受噪声影响），太大则欠拟合

标准回答

KNN 不学习参数，预测时对每个测试样本计算它到所有训练样本的距离，选出最近的 K 个邻居，由它们的标签多数投票决定类别。工程上的关键是向量化：用广播构造距离矩阵，再用 argpartition 做 Top-K 选择（O(N) 而非排序的 O(N log N)），并对每个样本用 bincount 投票。下面是可运行实现：

python
import numpy as np

class KNNClassifier:
    def __init__(self, k=3):
        self.k = k

    def fit(self, X, y):
        # 惰性学习：仅保存训练数据
        self.X_train = np.asarray(X, dtype=float)
        self.y_train = np.asarray(y)
        return self

    def predict(self, X):
        X = np.asarray(X, dtype=float)
        # 平方欧氏距离矩阵：(a-b)^2 = a^2 + b^2 - 2ab，向量化避免循环
        dist2 = (
            (X ** 2).sum(1)[:, None]
            + (self.X_train ** 2).sum(1)[None, :]
            - 2 * X @ self.X_train.T
        )
        # argpartition 取每行最近 k 个邻居的索引（无需全排序）
        knn_idx = np.argpartition(dist2, kth=self.k - 1, axis=1)[:, :self.k]
        preds = np.empty(X.shape[0], dtype=self.y_train.dtype)
        for i, idx in enumerate(knn_idx):
            votes = self.y_train[idx]
            preds[i] = np.bincount(votes).argmax()   # 多数投票取众数
        return preds

if __name__ == '__main__':
    rng = np.random.default_rng(0)
    X0 = rng.normal(0, 1, (50, 2)); X1 = rng.normal(4, 1, (50, 2))
    X = np.vstack([X0, X1]); y = np.array([0] * 50 + [1] * 50)
    clf = KNNClassifier(k=5).fit(X, y)
    test = np.array([[0.0, 0.0], [4.0, 4.0]])
    print(clf.predict(test))   # -> [0 1]

常见误区

⚠️ 常见踩坑

bincount 要求标签是非负整数，若标签是字符串需先做 LabelEncoder 映射，否则报错。另一易错点是忘记标准化特征，量纲大的维度会主导欧氏距离；以及偶数 K 在二分类时可能平票。

追问

追问 1：复杂度是多少？如何优化？

朴素预测每个查询是 O(N·D)，N 个训练样本全扫一遍。优化：用 KD-Tree（低维有效）或球树降低查询复杂度；高维大规模用 FAISS / HNSW 等近似最近邻；也可对训练集做聚类或编辑（Condensed NN）减少候选点。

追问 2：如何处理类别不平衡与距离权重？

可对邻居按距离倒数加权投票（越近权重越大），缓解远邻干扰；不平衡时可对少数类样本投票加权，或先做重采样。还可结合马氏距离等度量学习让距离更贴合数据分布。

延伸学习

与本题相关的知识库文章、术语、工具与行业资讯。

📚 知识库

📖 术语表

🎯 相关面试题