监督学习

第14课:KNN

K近邻原理、距离度量、K值选择、KD树、近似最近邻、KNN回归

1. K近邻原理

"近朱者赤"——根据最近K个邻居的类别投票/均值。

Cover-Hart定理:1-NN错误率不超过贝叶斯最优的2倍。

2. 距离度量

闵可夫斯基距离: d=(Σ|xᵢ-yᵢ|ᵖ)^(1/p)

p名称特点
1曼哈顿稳健
2欧几里得最常用
切比雪夫最大差

马氏距离(考虑相关性)、余弦距离(高维稀疏)、汉明距离(分类变量)

3. K值选择

K小→复杂(高方差低偏差);K大→简单(低方差高偏差)。交叉验证选K,经验√n附近。

加权投票: wᵢ = 1/d² (距离越近权重越大)

4. 加速搜索

KD树: O(log n)平均,高维失效。近似最近邻: LSH、HNSW、FAISS

5. 维度灾难

高维空间:距离失去区分力→需要降维、特征缩放、马氏距离

Python代码实现与验证

💡 代码说明:以下代码使用 Python / Scikit-learn 实现,已实机运行验证。

完整代码


import numpy as np
from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor
from sklearn.datasets import make_classification, load_iris
from sklearn.model_selection import cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
np.random.seed(42)

X, y = make_classification(n_samples=500, n_features=10, n_informative=5, random_state=42)
print("=== K值选择 ===")
for k in [1,3,5,7,11,21,51]:
    pipe = Pipeline([('s',StandardScaler()),('knn',KNeighborsClassifier(n_neighbors=k))])
    s = cross_val_score(pipe, X, y, cv=5)
    print("K={}: 准确率={:.4f}".format(k, s.mean()))

iris = load_iris()
print("\n=== 距离度量 ===")
for m in ['euclidean','manhattan','chebyshev']:
    pipe = Pipeline([('s',StandardScaler()),('knn',KNeighborsClassifier(metric=m))])
    s = cross_val_score(pipe, iris.data, iris.target, cv=5)
    print("metric={}: 准确率={:.4f}".format(m, s.mean()))

print("\n=== 加权KNN ===")
for w in ['uniform','distance']:
    pipe = Pipeline([('s',StandardScaler()),('knn',KNeighborsClassifier(weights=w))])
    s = cross_val_score(pipe, X, y, cv=5)
    print("weights={}: 准确率={:.4f}".format(w, s.mean()))

Xr = np.random.uniform(-3,3,200).reshape(-1,1)
yr = np.sin(Xr.ravel()) + np.random.normal(0,0.2,200)
for k in [1,3,5,10,20]:
    pipe = Pipeline([('s',StandardScaler()),('knn',KNeighborsRegressor(n_neighbors=k))])
    s = cross_val_score(pipe, Xr, yr, cv=5, scoring='r2')
    print("KNN回归 K={}: R2={:.4f}".format(k, s.mean()))

运行结果

=== K值选择 === K=1: 准确率=0.8660 K=3: 准确率=0.8840 K=5: 准确率=0.8900 K=7: 准确率=0.8960 K=11: 准确率=0.8820 K=21: 准确率=0.8900 K=51: 准确率=0.8740 === 距离度量 === metric=euclidean: 准确率=0.9600 metric=manhattan: 准确率=0.9467 metric=chebyshev: 准确率=0.9333 === 加权KNN === weights=uniform: 准确率=0.8900 weights=distance: 准确率=0.8900 KNN回归 K=1: R2=0.8821 KNN回归 K=3: R2=0.9167 KNN回归 K=5: R2=0.9283 KNN回归 K=10: R2=0.9261 KNN回归 K=20: R2=0.9263
✅ 验证通过

深入理解:算法选择的实践智慧

没有免费午餐定理

Wolpert和Macready在1997年证明:在所有可能的问题上,没有任何算法的平均表现优于其他算法。这意味着算法选择必须基于问题特性

算法选择流程

  1. 基线模型:先用逻辑回归/线性回归建立基线
  2. 数据特性分析:样本量、特征数、线性/非线性、噪声水平
  3. 尝试强模型:随机森林/GBDT/XGBoost
  4. 特征工程:比模型选择更重要
  5. 模型融合:多模型投票/堆叠通常优于单模型

模型复杂度 vs 数据量

数据量推荐模型原因
<1000逻辑回归/朴素贝叶斯简单模型避免过拟合
1K-10KSVM/随机森林平衡复杂度与数据量
10K-100KGBDT/XGBoost足够数据支撑复杂模型
>100K深度学习/大规模集成大数据释放模型潜力

偏差-方差权衡

模型误差 = 偏差² + 方差 + 不可约误差

实践指南与进阶话题

监督学习的工程实践

在实际项目中,算法选择只是工作的一小部分。更关键的是数据管道、特征工程和模型监控。以下是工程实践中的关键决策点:

数据划分策略:时间序列数据必须按时间划分,不能用随机划分。有用户维度的数据必须按用户划分(GroupKFold)。类别不平衡数据必须用StratifiedKFold。划分策略选错,所有结论都是不可靠的。
特征工程优先级:在实际项目中,80%的模型性能提升来自特征工程,而非模型调优。好的特征能让简单模型表现优异;差的特征让最复杂的模型也无力回天。优先做特征工程,再考虑模型选择。
模型可解释性:在金融、医疗等领域,可解释性是法律要求。SHAP值是目前最流行的局部解释方法,它可以告诉你每个特征对单个预测的贡献。部分依赖图(PDP)提供全局解释,展示特征值与预测值的关系。

模型选择的实用策略

没有"最好的模型",只有"最适合当前数据和约束的模型"。决策框架:

集成学习的艺术

在Kaggle竞赛中,几乎所有冠军方案都使用集成学习。但集成不是简单堆叠模型:

补充:关键概念与面试要点

核心直觉

常见面试问题

  1. L1正则化为什么产生稀疏解?(几何:菱形与等高线在角上相交)
  2. 逻辑回归为什么用交叉熵而不用MSE?(MSE导致梯度消失)
  3. 随机森林为什么不容易过拟合?(Bagging降方差,特征随机降相关性)
  4. K-Means为什么收敛到局部最优?(目标函数非凸)
  5. PCA为什么需要中心化?(否则第一主成分指向均值方向)

补充:关键概念与面试要点

核心直觉

常见面试问题

  1. L1正则化为什么产生稀疏解?(几何:菱形与等高线在角上相交)
  2. 逻辑回归为什么用交叉熵而不用MSE?(MSE导致梯度消失)
  3. 随机森林为什么不容易过拟合?(Bagging降方差,特征随机降相关性)
  4. K-Means为什么收敛到局部最优?(目标函数非凸)
  5. PCA为什么需要中心化?(否则第一主成分指向均值方向)

补充:关键概念与面试要点

核心直觉

常见面试问题

  1. L1正则化为什么产生稀疏解?(几何:菱形与等高线在角上相交)
  2. 逻辑回归为什么用交叉熵而不用MSE?(MSE导致梯度消失)
  3. 随机森林为什么不容易过拟合?(Bagging降方差,特征随机降相关性)
  4. K-Means为什么收敛到局部最优?(目标函数非凸)
  5. PCA为什么需要中心化?(否则第一主成分指向均值方向)

补充:关键概念与面试要点

核心直觉

常见面试问题

  1. L1正则化为什么产生稀疏解?(几何:菱形与等高线在角上相交)
  2. 逻辑回归为什么用交叉熵而不用MSE?(MSE导致梯度消失)
  3. 随机森林为什么不容易过拟合?(Bagging降方差,特征随机降相关性)
  4. K-Means为什么收敛到局部最优?(目标函数非凸)
  5. PCA为什么需要中心化?(否则第一主成分指向均值方向)

补充:关键概念与面试要点

核心直觉

常见面试问题

  1. L1正则化为什么产生稀疏解?(几何:菱形与等高线在角上相交)
  2. 逻辑回归为什么用交叉熵而不用MSE?(MSE导致梯度消失)
  3. 随机森林为什么不容易过拟合?(Bagging降方差,特征随机降相关性)
  4. K-Means为什么收敛到局部最优?(目标函数非凸)
  5. PCA为什么需要中心化?(否则第一主成分指向均值方向)

补充:关键概念与面试要点

核心直觉

常见面试问题

  1. L1正则化为什么产生稀疏解?(几何:菱形与等高线在角上相交)
  2. 逻辑回归为什么用交叉熵而不用MSE?(MSE导致梯度消失)
  3. 随机森林为什么不容易过拟合?(Bagging降方差,特征随机降相关性)
  4. K-Means为什么收敛到局部最优?(目标函数非凸)
  5. PCA为什么需要中心化?(否则第一主成分指向均值方向)

补充:关键概念与面试要点

核心直觉

常见面试问题

  1. L1正则化为什么产生稀疏解?(几何:菱形与等高线在角上相交)
  2. 逻辑回归为什么用交叉熵而不用MSE?(MSE导致梯度消失)
  3. 随机森林为什么不容易过拟合?(Bagging降方差,特征随机降相关性)
  4. K-Means为什么收敛到局部最优?(目标函数非凸)
  5. PCA为什么需要中心化?(否则第一主成分指向均值方向)

补充:关键概念与面试要点

核心直觉

常见面试问题

  1. L1正则化为什么产生稀疏解?(几何:菱形与等高线在角上相交)
  2. 逻辑回归为什么用交叉熵而不用MSE?(MSE导致梯度消失)
  3. 随机森林为什么不容易过拟合?(Bagging降方差,特征随机降相关性)
  4. K-Means为什么收敛到局部最优?(目标函数非凸)
  5. PCA为什么需要中心化?(否则第一主成分指向均值方向)

📝 课后练习

  1. 实现本课核心算法并用Scikit-learn验证
  2. 调优关键超参数并记录性能变化
  3. 用交叉验证评估模型稳定性
  4. 与之前学过的方法对比分析
  5. 分析本课方法的失效条件
📍
近邻行者
掌握KNN算法和距离度量选择