SVM 支持向量机详解

1. 什么是 SVM（支持向量机）

支持向量机（Support Vector Machine, SVM）是一种强大的监督学习算法，主要用于分类任务（也可用于回归，称为 SVR）。SVM 的核心思想是：在特征空间中找到一个最优超平面，使得不同类别之间的间隔（margin）最大化。

历史与命名

SVM 的理论基础可追溯到 Vladimir Vapnik 和 Alexei Chervonenkis 于 1963 年提出的线性分类器理论。他们研究了在有限样本下如何控制模型的泛化能力，奠定了统计学习理论的基础。然而，真正让 SVM 变得实用的是 1992 年 Bernhard Boser、Isabelle Guyon 和 Vladimir Vapnik 的突破性论文，他们将核函数技巧引入了最大间隔分类器，使得 SVM 能够处理非线性问题。

"支持向量"这个名字来源于算法的几何本质：在最终训练好的模型中，只有距离决策边界最近的那些数据点真正参与了决策边界的定义——这些关键点就被称为支持向量（support vectors）。它们"支撑"着决策边界的位置，就像支撑帐篷的杆子一样。移除任何一个支持向量都会改变决策边界，而移除其他数据点则不会影响模型。

2. 数学基础

2.1 超平面方程

在 $d$ 维空间中，超平面是一个 $d-1$ 维的子空间，由以下方程定义：

w \cdot x + b = 0

其中 $w$ 是法向量（决定超平面的方向）， $b$ 是偏置项（决定超平面距原点的距离）， $x$ 是输入特征向量。对于二分类问题，超平面将空间分为两半： $w \cdot x + b > 0$ 的一侧为正类， $w \cdot x + b < 0$ 的一侧为负类。

2.2 为什么要最大化间隔？——Vapnik 的结构风险最小化

能将两类数据分开的超平面有无数个，为什么 SVM 要选择间隔最大的那个？这不是一个任意的设计选择，而是有深刻的理论依据。

Vapnik 的结构风险最小化原理（SRM, 1995）：传统机器学习方法（如经验风险最小化 ERM）追求在训练集上的误差最小，但这容易导致过拟合。Vapnik 提出了一个更本质的框架：模型的真实风险 = 经验风险 + 复杂度惩罚。根据 VC 理论（Vapnik-Chervonenkis 维度），最大化间隔等价于最小化模型的 VC 维，从而最小化泛化误差的上界。简而言之：间隔越大 → 模型复杂度越低 → 泛化能力越强。这就是 SVM 追求最大间隔的根本原因。

2.3 间隔的数学推导

任意一点 $x$ 到超平面 $w \cdot x + b = 0$ 的距离为：

distance = | w \cdot x + b| / || w ||

我们约定支持向量满足 $|w \cdot x + b| = 1$ （通过缩放 w 和 b 总可以做到），则支持向量到超平面的距离为 $1/||w||$ ，两侧支持向量之间的总间隔为：

margin = 2 / || w ||

最大化间隔 $2/||w||$ 等价于最小化 $||w||$ ，为了数学上的方便（避免求导时的平方根），我们最小化 $½||w||²$ 。最终的优化问题：

min ½|| w ||² s.t. y i (w \cdot x i + b) \geq 1, \foralli

约束条件 $y i (w \cdot x i + b) \geq 1$ 确保每个样本都被正确分类且距离超平面至少为 $1/||w||$ 。这是一个凸二次优化问题，可以通过拉格朗日对偶问题高效求解。

3. 硬间隔与软间隔

3.1 硬间隔 SVM

上面推导的就是硬间隔 SVM——要求所有样本都被正确分类且满足间隔约束。但现实世界的数据几乎不可能完美线性可分：

硬间隔的致命缺陷：① 如果数据不是线性可分的，优化问题无解；② 即使线性可分，个别噪声点或异常值也会严重扭曲决策边界，导致过拟合。

3.2 软间隔 SVM（Cortes & Vapnik, 1995）

Corinna Cortes 和 Vladimir Vapnik 于 1995 年发表了开创性论文 "Support-vector networks"，引入了松弛变量（slack variables） $ξ i$ ，允许部分样本违反间隔约束。这是 SVM 从理论工具走向实用算法的关键一步。

min ½|| w ||² + C \sum i ξ i s.t. y i (w \cdot x i + b) \geq 1 - ξ i, ξ i \geq 0, \foralli

3.3 C 参数的权衡

C 的直觉：C 控制两个目标之间的权衡——间隔最大化 vs. 分类正确性。

C 大：严格惩罚误分类 → 间隔小，决策边界复杂 → 容易过拟合（对噪声敏感）
C 小：宽容误分类 → 间隔大，决策边界简单 → 容易欠拟合（忽略数据模式）

数学上，C 类似于正则化参数的倒数。C 越大，正则化越弱；C 越小，正则化越强。

4. 核函数技巧（Kernel Trick）

核函数技巧是 SVM 最精妙、最重要的思想。它解决了一个根本性问题：现实世界的数据往往不是线性可分的，但在更高维空间中可能变得线性可分。

4.1 为什么需要核函数？

核心洞察：一个在低维空间中非线性可分的问题，映射到足够高维的空间后，几乎一定变得线性可分（Cover 定理, 1965）。例如，二维平面上的 XOR 问题在三维空间中可以用一个平面分开。

问题：直接计算高维映射 $φ(x)$ 代价巨大——如果映射到百万维空间，存储和计算都不现实。

核函数的天才：通过对偶问题的推导，SVM 的优化和预测只需要计算数据点之间的内积 $φ(x i) \cdot φ(x j)$ ，而核函数 $K(x i, x j)$ 可以在原始空间中直接计算这个内积，无需显式映射到高维空间。

4.2 历史背景

核方法的思想最早由 Aizerman、Braverman 和 Rozonoer 于 1964 年在势函数方法中提出。1992 年，Boser、Guyon 和 Vapnik 将核函数与最大间隔分类器结合，创造了现代 SVM。他们的关键洞察是：对偶问题的目标函数只包含输入向量的内积，因此可以用核函数替代。

4.3 Mercer 定理

Mercer 定理（James Mercer, 1909）：一个函数 K(x, y) 是有效的核函数（即对应某个特征空间中的内积），当且仅当对于任何有限数据集，其核矩阵（Gram 矩阵）是半正定的。这个定理给出了判断核函数合法性的数学标准，确保核函数隐式对应的映射确实存在。

4.4 常用核函数详解

线性核 (Linear Kernel)

K(x_i, x_j) = x_i · x_j

为什么存在：当数据本身线性可分或接近线性可分时，不需要高维映射。线性核等价于不使用核函数，计算效率最高。

适用场景：高维稀疏数据（如文本分类，特征维度可达数万），样本量远小于特征数时。Joachims (1998) 证明了线性 SVM 在文本分类中表现卓越。

RBF 核 / 高斯核 (Radial Basis Function)

K(x_i, x_j) = exp(-γ ||x_i - x_j||²)

为什么强大：RBF 核隐式将数据映射到无限维的特征空间。这可以通过 Taylor 展开证明：exp(-γ||x-y||²) 展开后包含所有阶次的多项式项，每一项对应一个维度，因此对应无限维空间。根据 Cover 定理，在无限维空间中，数据几乎一定线性可分。

γ 参数：γ 控制单个样本的影响范围。γ 大 → 每个样本只影响邻近区域 → 决策边界复杂（过拟合风险）；γ 小 → 每个样本影响范围广 → 决策边界平滑（欠拟合风险）。

默认选择：Hsu, Chang & Lin (2003) 的实用指南推荐：当不确定用哪个核时，先试 RBF 核。因为它足够灵活，且只有两个超参数 (C, γ) 需要调优。

多项式核 (Polynomial Kernel)

K(x_i, x_j) = (γ x_i · x_j + r)^d

为什么存在：当数据之间的交互关系重要时（即特征之间的组合效应），多项式核可以显式建模 d 阶特征交互，而不需要手动构造交叉特征。度数 $d$ 控制非线性程度。

适用场景：自然语言处理（词袋模型的交互）、图像识别中某些结构化特征。实践中不如 RBF 核常用，因为超参数更多（d, γ, r）且数值稳定性较差。

Sigmoid 核

K(x_i, x_j) = tanh(γ x_i · x_j + r)

为什么存在：Sigmoid 核源于神经网络的激活函数 tanh。使用 sigmoid 核的 SVM 在某种意义上等价于一个两层的感知机神经网络。它的存在主要是历史原因——在神经网络和 SVM 之间建立联系。

注意：Sigmoid 核并不总是满足 Mercer 条件（只在特定 γ 和 r 值下是有效核），因此实践中很少使用。

5. 超参数调优

Hsu, Chang & Lin (2003) 在其被引用超过 20000 次的 "A Practical Guide to Support Vector Classification" 中，给出了 SVM 超参数调优的标准方法论，至今仍是最权威的参考。

5.1 C 参数

数学含义：C 是软间隔优化中的正则化参数。在对偶问题中，C 是拉格朗日乘子 $α i$ 的上界（0 ≤ α_i ≤ C）。

直觉：C 回答的是"你愿意为了正确分类每一个训练样本，付出多大的代价？"

调优范围：Hsu 等人推荐在 2^-5 到 2¹⁵ 之间以指数步长搜索，即 C ∈ {2^-5, 2^-3, ..., 2¹³, 2¹⁵}。

5.2 γ 参数（RBF 核）

数学含义：γ = 1/(2σ²)，其中 σ 是高斯函数的标准差。γ 定义了高斯核的"宽度"。

直觉：γ 回答的是"每个训练样本的影响力能到多远？"

调优范围：推荐在 2^-15 到 2³ 之间搜索，即 γ ∈ {2^-15, 2^-13, ..., 2¹, 2³}。

5.3 网格搜索 + 交叉验证

推荐流程（Hsu et al. 2003）：
1. 数据预处理：将特征缩放到 [-1, 1] 或 [0, 1]（SVM 对特征尺度敏感，因为距离计算受量纲影响）
2. 先试 RBF 核
3. 粗搜索：用 C 和 γ 的指数网格 + 交叉验证
4. 细搜索：在粗搜索最佳区域附近细化
5. 用最佳 (C, γ) 在全训练集上训练最终模型

from sklearn.svm import SVC
from sklearn.model_selection import GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

pipe = Pipeline([
    ('scaler', StandardScaler()),
    ('svc', SVC(kernel='rbf'))
])

# Hsu et al. 推荐的指数网格
param_grid = {
    'svc__C': [2**i for i in range(-5, 16, 2)],
    'svc__gamma': [2**i for i in range(-15, 4, 2)]
}

grid = GridSearchCV(pipe, param_grid, cv=5, scoring='accuracy', n_jobs=-1)
grid.fit(X_train, y_train)
print(f"最佳参数: {grid.best_params_}")
print(f"最佳交叉验证准确率: {grid.best_score_:.4f}")

6. Python 实现

6.1 基础 SVM 分类

from sklearn.svm import SVC
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import classification_report
import numpy as np

# 生成示例数据
X, y = make_classification(n_samples=1000, n_features=20,
                           n_informative=10, n_redundant=5,
                           random_state=42)

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

# 特征缩放（SVM 必须做特征缩放）
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

# 训练 SVM
svm = SVC(kernel='rbf', C=1.0, gamma='scale', random_state=42)
svm.fit(X_train_scaled, y_train)

# 评估
y_pred = svm.predict(X_test_scaled)
print(classification_report(y_test, y_pred))
print(f"支持向量个数: {svm.n_support_}")
print(f"总支持向量数: {sum(svm.n_support_)}, 占训练集: {sum(svm.n_support_)/len(X_train)*100:.1f}%")

6.2 核函数对比实验

from sklearn.svm import SVC
from sklearn.datasets import make_moons
from sklearn.model_selection import cross_val_score
from sklearn.preprocessing import StandardScaler
import numpy as np

# 非线性数据集
X, y = make_moons(n_samples=500, noise=0.2, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

kernels = {
    'Linear': SVC(kernel='linear', C=1.0),
    'RBF':    SVC(kernel='rbf', C=1.0, gamma='scale'),
    'Poly-3': SVC(kernel='poly', degree=3, C=1.0),
    'Sigmoid': SVC(kernel='sigmoid', C=1.0, gamma='scale'),
}

print(f"{'核函数':<12} {'准确率 (5-fold CV)':>20}")
print("-" * 35)
for name, model in kernels.items():
    scores = cross_val_score(model, X_scaled, y, cv=5, scoring='accuracy')
    print(f"{name:<12} {scores.mean():.4f} +/- {scores.std():.4f}")

# 对于 make_moons 数据集，RBF 核通常表现最好，
# 因为数据是非线性的月牙形，RBF 的无限维映射能很好地捕捉这种形状。

7. 多分类 SVM

SVM 本质上是一个二分类器。对于多分类问题（K 个类别），有两种经典策略：

一对一 (One-vs-One, OvO)

方法：为每一对类别训练一个 SVM，共 K(K-1)/2 个分类器。预测时每个分类器投票，票数最多的类别获胜。

为什么用 OvO：每个子问题只用两个类别的数据，训练集小，训练速度快。虽然分类器数量多，但每个分类器训练很快。sklearn 默认使用 OvO 策略，因为 Hsu & Lin (2002) 的实验表明 OvO 在实践中通常和其他方法一样好，且训练更快。

一对多 (One-vs-All / One-vs-Rest, OvA/OvR)

方法：为每个类别训练一个"该类 vs. 其他所有类"的 SVM，共 K 个分类器。预测时选择决策函数值最大的类别。

为什么用 OvA：分类器数量更少（K 个 vs. K(K-1)/2 个），每个分类器都利用了全部训练数据。但缺点是类别不平衡问题更严重（1 个类 vs. 其余所有类）。

from sklearn.svm import SVC, LinearSVC
from sklearn.multiclass import OneVsRestClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import cross_val_score
from sklearn.preprocessing import StandardScaler

X, y = load_iris(return_X_y=True)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# OvO (sklearn SVC 默认)
ovo_svm = SVC(kernel='rbf', decision_function_shape='ovo')
ovo_scores = cross_val_score(ovo_svm, X_scaled, y, cv=5)
print(f"OvO 准确率: {ovo_scores.mean():.4f}")

# OvR
ovr_svm = OneVsRestClassifier(SVC(kernel='rbf'))
ovr_scores = cross_val_score(ovr_svm, X_scaled, y, cv=5)
print(f"OvR 准确率: {ovr_scores.mean():.4f}")

8. 优势与局限

优势
1. 强泛化能力：基于结构风险最小化（SRM），而非经验风险最小化。间隔最大化直接最小化泛化误差上界。
2. 高维有效：即使特征维度远大于样本数（如基因数据 d=20000, n=100），SVM 仍能有效工作，因为它依赖支持向量而非所有数据点。
3. 核函数灵活：通过核函数可以处理任意非线性问题，且无需显式计算高维映射。
4. 全局最优：优化问题是凸的，不存在局部最优问题（不像神经网络）。
5. 稀疏解：最终模型只依赖支持向量，内存高效。

局限
1. 大数据集慢：训练时间复杂度 O(n²) ~ O(n³)（标准 QP 求解），10 万样本以上就很慢。原因：需要计算核矩阵（n×n）。
2. 对缩放敏感：由于基于距离计算，特征必须先标准化。不像树模型对尺度不变。
3. 不直接输出概率：SVM 输出的是决策函数值，不是概率。虽然可以通过 Platt Scaling（Platt, 1999）转换为概率，但这是后处理，增加计算量。
4. 超参数敏感：C 和 γ 的选择对性能影响大，需要仔细调优。
5. 可解释性有限：非线性核的 SVM 本质上是一个黑盒——无法像决策树或线性模型那样直接解释特征的贡献。

9. SVM 与其他算法对比

维度	SVM	逻辑回归	随机森林	KNN	神经网络
理论基础	结构风险最小化	最大似然估计	Bagging + 随机子空间	惰性学习	万能近似定理
非线性能力	通过核函数	需手动特征工程	天然非线性	天然非线性	天然非线性
训练速度	O(n²~n³) 慢	O(nd) 快	O(n·d·log n·T) 中	无需训练	取决于架构
预测速度	O(sv · d) 中	O(d) 快	O(T · log n) 中	O(nd) 慢	O(d) 快
小样本表现	优秀	良好	中等	良好	较差
大样本表现	受限于计算	良好	优秀	受限于计算	优秀
特征缩放	必须	推荐	不需要	必须	必须
可解释性	线性核可解释	高	中（特征重要性）	高（最近邻）	低
概率输出	间接（Platt Scaling）	直接	直接	直接	直接（Softmax）
最佳场景	中小数据集、高维、非线性	线性可分、需概率	大数据集、混合特征	小数据集、局部结构	海量数据、复杂模式

机器学习算法速查指南 -- 分类/回归/聚类全面对比

11. 常见问题

Q: SVM 为什么不适合大数据集？能不能优化？

标准 SVM 使用二次规划（QP）求解器，需要计算和存储 n×n 的核矩阵，时间复杂度 O(n²) ~ O(n³)，内存 O(n²)。对于 10 万以上样本，这在计算上不现实。替代方案：① 使用 LinearSVC（基于 liblinear，线性核 O(nd) 训练）；② 使用 SGD 近似（sklearn 的 SGDClassifier(loss='hinge')）；③ 使用 Nystroem 或 RBF Sampler 近似核映射后用线性模型；④ 使用 ThunderSVM 等 GPU 加速实现。

Q: 什么时候用线性核 vs. RBF 核？

规则：① 如果特征数 >> 样本数（如文本分类 d=10000, n=1000），用线性核——数据已经在高维空间中，非线性映射不必要且可能过拟合；② 如果样本数 >> 特征数且数据非线性，用 RBF 核；③ 如果不确定，先试 RBF 核 + 网格搜索（Hsu et al. 2003 推荐）。

Q: SVM 能处理回归问题吗？

可以。支持向量回归（SVR, Drucker et al. 1997）使用 ε-不敏感损失函数：只有当预测值偏离真实值超过 ε 时才计算损失。这产生一个管状的回归带，带内的误差被忽略。在 sklearn 中使用 SVR(kernel='rbf', C=1.0, epsilon=0.1)。

Q: SVM 的支持向量太多说明什么？

如果支持向量数量接近训练样本数（比如超过 50%），通常说明：① C 太小，模型过于宽松；② 核函数选择不当，当前核无法有效分离数据；③ 数据本身噪声太大或类别高度重叠。理想情况下，支持向量应该只占训练集的一小部分。支持向量越少，模型越稀疏、泛化越好。

Q: 为什么 SVM 需要特征缩放？

SVM 基于距离计算（间隔 = 2/||w||，核函数中的 ||x_i - x_j||）。如果某个特征的尺度远大于其他特征（如"年龄 0-100"vs."收入 0-1000000"），距离计算将被大尺度特征主导，小尺度特征的信息被忽略。标准化后每个特征对距离的贡献相当。这与树模型不同——树模型基于排序分裂，不受尺度影响。