Day 110 — SVM 与 KNN
两大经典分类算法：支持向量机（SVM）与 K 近邻（KNN）
📋 今日学习目标
- 理解 SVM 的核心思想——最大间隔分类器
- 掌握核技巧（Kernel Trick）的原理与应用
- 理解 KNN 算法的原理、K 值选择策略
- 对比不同分类算法的适用场景
- 实战：手写数字识别（SVM vs KNN）
一、SVM — 支持向量机
1.1 什么是 SVM？
SVM（Support Vector Machine，支持向量机）是一种监督学习算法，核心思想是找到一个最优超平面，使得不同类别之间的间隔（margin）最大化。
为什么选择最大间隔？
- 最大间隔意味着更好的泛化能力
- 对新数据的分类更鲁棒
- 即使数据有噪声，也能保持较好的分类效果
1.2 核心概念
超平面（Hyperplane）
在二维空间中是直线，在三维中是平面，在更高维中是超平面。
对于二分类问题，超平面方程为：
w · x + b = 0
其中：
- w 是法向量（决定超平面方向）
- b 是偏置（决定超平面位置）
间隔（Margin）
间隔是超平面到最近数据点距离的两倍：
间隔 = 2 / ||w||
最大化间隔 = 最小化 ||w||，这是一个二次规划问题。
支持向量（Support Vectors）
距离超平面最近的那些数据点，它们"支撑"着超平面的位置。只有支持向量决定了最终的分类边界。
1.3 硬间隔 vs 软间隔
硬间隔（Hard Margin）
- 要求所有样本都严格分类正确
- 对噪声极其敏感
- 要求数据线性可分
软间隔（Soft Margin）
- 允许部分样本分类错误
- 引入松弛变量 ξ（xi）
- 通过参数 C 控制"容忍度"：
最小化: ||w||²/2 + C * Σξᵢ
约束: yᵢ(w · xᵢ + b) ≥ 1 - ξᵢ, ξᵢ ≥ 0
C 的含义：
- C 越大 → 越不允许犯错（可能过拟合）
- C 越小 → 越容忍错误（可能欠拟合）
1.4 核技巧（Kernel Trick）
问题： 现实中的数据往往不是线性可分的。
解决方案： 将数据映射到高维空间，使其变得线性可分。
核技巧的妙处： 不需要真正计算高维映射，只需要计算核函数 K(xᵢ, xⱼ) = φ(xᵢ) · φ(xⱼ)，就能得到高维空间的内积。
常用核函数
| 核函数 | 公式 | 特点 | 适用场景 |
|---|---|---|---|
| 线性核 | K(x,y) = x·y | 最简单，等价于线性SVM | 线性可分数据 |
| 多项式核 | K(x,y) = (γx·y + r)^d | 非线性，参数多 | 有明确多项式特征的数据 |
| RBF核（高斯核） | K(x,y) = exp(-γ||x-y||²) | 最常用，映射到无穷维 | 通用，效果好 |
| Sigmoid核 | K(x,y) = tanh(γx·y + r) | 类似神经网络 | 特定场景 |
1.5 sklearn 中的 SVM
from sklearn.svm import SVC, LinearSVC, SVR
# 分类
clf = SVC(kernel='rbf', C=1.0, gamma='scale')
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
# 线性分类（更快）
clf = LinearSVC(C=1.0, max_iter=10000)
# 回归
reg = SVR(kernel='rbf', C=1.0)
关键参数：
- kernel：核函数类型（'linear', 'rbf', 'poly', 'sigmoid'）
- C：正则化参数（越大越严格）
- gamma：RBF核的参数（越大越复杂）
- degree：多项式核的阶数
二、KNN — K 近邻
2.1 什么是 KNN？
KNN（K-Nearest Neighbors，K 近邻）是最简单的机器学习算法之一。核心思想：物以类聚——一个样本的类别由其最近的 K 个邻居的类别投票决定。
特点：
- 懒惰学习（Lazy Learning）：没有训练过程，所有计算都在预测时进行
- 非参数方法：不假设数据的分布形式
- 直观易懂：就像"近朱者赤，近墨者黑"
2.2 算法流程
1. 选择 K 值
2. 计算待预测样本与所有训练样本的距离
3. 找到距离最近的 K 个样本
4. 统计这 K 个样本的类别
5. 投票决定待预测样本的类别（多数票）
2.3 距离度量
欧氏距离（Euclidean Distance）
d(x, y) = √(Σ(xᵢ - yᵢ)²)
最常用，适用于连续特征。
曼哈顿距离（Manhattan Distance）
d(x, y) = Σ|xᵢ - yᵢ|
适用于稀疏数据或高维空间。
闵可夫斯基距离（Minkowski Distance）
d(x, y) = (Σ|xᵢ - yᵢ|^p)^(1/p)
p=1 时为曼哈顿距离，p=2 时为欧氏距离。
2.4 K 值选择
K 值是 KNN 最重要的超参数：
| K 值 | 效果 | 风险 |
|---|---|---|
| K=1 | 最复杂，完美拟合训练集 | 过拟合，对噪声敏感 |
| K=适中 | 平衡偏差与方差 | 需要调参 |
| K=N | 最简单，总是预测多数类 | 欠拟合，无意义 |
选择策略：
1. 经验法则：K = √N（N 为样本数）
2. 交叉验证：尝试不同的 K 值，选择验证集准确率最高的
3. 奇数 K：避免平票（二分类时）
2.5 数据预处理的重要性
KNN 对特征尺度非常敏感！ 因为它基于距离计算。
# 必须做标准化！
from sklearn.preprocessing import StandardScaler
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)
2.6 sklearn 中的 KNN
from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor
# 分类
clf = KNeighborsClassifier(n_neighbors=5, weights='uniform', metric='minkowski')
clf.fit(X_train, y_train)
y_pred = clf.predict(X_test)
# 回归
reg = KNeighborsRegressor(n_neighbors=5)
关键参数：
- n_neighbors：K 值
- weights：'uniform'（等权重）或 'distance'（距离加权）
- metric：距离度量方式
- algorithm：'ball_tree', 'kd_tree', 'brute', 'auto'
三、SVM vs KNN 对比
3.1 对比总结
| 特性 | SVM | KNN |
|---|---|---|
| 类型 | 判别模型 | 基于实例 |
| 训练 | 快（有训练过程） | 慢（无需训练） |
| 预测 | 快 | 慢（需计算所有距离） |
| 内存 | 只需存支持向量 | 需存全部训练数据 |
| 可解释性 | 中等（支持向量） | 低 |
| 高维数据 | 好（核技巧） | 差（维度灾难） |
| 数据量 | 适合大数据 | 小数据效果好 |
| 特征缩放 | 需要 | 必须 |
| 噪声敏感 | 软间隔可调 | 较敏感 |
3.2 选择建议
选 SVM 当：
- 数据维度高（如文本分类）
- 数据量大
- 需要更好的泛化能力
选 KNN 当：
- 数据量小
- 需要简单快速的基线
- 数据分布不规则
四、实战：手写数字识别
4.1 任务说明
使用 sklearn 内置的手写数字数据集（8x8 像素图片），对比 SVM 和 KNN 的表现。
4.2 完整代码
见 code/03-digit-recognition.py
五、图解
5.1 SVM 最大间隔示意
○ ○ ← 类别 A（正类）
○ ○
○ ───────────── ← 最优超平面
○ ↕ 间隔/2
↕ 间隔
↕ 间隔/2
● ● ← 类别 B（负类）
● ●
5.2 核技巧示意
原始空间（线性不可分） 高维空间（线性可分）
○ ● ○ ● ○ ○ ○ ○ | ● ● ●
● ○ ● ○ ● ○ ○ ○ | ● ● ●
─────────────
无法画出直线分开 超平面可分开
5.3 KNN 分类示意
待预测样本 ?
○ ● ? ○ K=3: 2个○, 1个● → 预测为○
● ○ K=5: 3个○, 2个● → 预测为○
近邻投票决定类别
六、思考题
-
为什么 SVM 对高维数据效果好，而 KNN 不行？
- 提示：考虑"维度灾难"和核技巧 -
SVM 中参数 C 和 gamma 分别控制什么？如何联合调参？
- 提示：C 控制正则化，gamma 控制核函数的"影响力范围" -
KNN 的 weights='distance' 在什么情况下比 weights='uniform' 好？
- 提示：考虑数据分布不均匀的情况 -
如何用 SVM 处理多分类问题？
- 提示：One-vs-One (OvO) 和 One-vs-Rest (OvR) -
在实际项目中，你会先试 SVM 还是 KNN？为什么？
- 提示：考虑数据量、维度、计算资源等因素