KNN 是基于实例的监督学习算法，通过找最相似的 K 个样本进行预测，核心思想是"物以类聚"。
工作流程
- 计算距离：新样本与所有训练样本的距离
- 找 K 个最近邻：选出距离最小的 K 个
- 投票/平均：分类用多数投票，回归用平均
距离度量
| 距离 | 公式 |
|---|
| 欧氏距离 | $d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$ |
| 曼哈顿距离 | $d(x, y) = \sum_{i=1}^{n} |
| 闵可夫斯基距离 | $d(x, y) = (\sum_{i=1}^{n} |
理论性质
最近邻错误率 $R$ 满足：
$$R^* \le R \le 2R^(1 - R^)$$
其中 $R^*$ 是贝叶斯最优错误率。
优缺点
| 优点 | 缺点 |
|---|
| 简单直观 | 预测复杂度 O(N) |
| 无需训练 | 高维效果差 |
| 支持多分类 | 需归一化 |
适用场景
代码示例
1
2
3
4
5
| from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train, y_train)
y_pred = knn.predict(X_test)
|
最新进展
| 方向 | 说明 |
|---|
| 深度学习结合 | KNN 作为神经网络最后一层 |
| 度量学习 | 学习更好的距离度量 |
| 近似搜索 | FAISS、HNSW 处理大规模数据 |
张芷铭的个人博客
Comments