机器学习之支持向量机

目录

1. 简介
2. 基本概念
3. 线性支持向量机
4. 软间隔支持向量机
5. 核技巧与非线性支持向量机
6. 支持向量回归
7. SVM的优缺点
8. 实际应用
9. 实现示例

---

简介

支持向量机（Support Vector Machine，简称SVM）是一种强大的监督学习算法，由 Vladimir Vapnik 和他的同事在 20 世纪 90 年代提出。SVM 主要用于分类和回归问题，在文本分类、图像识别、生物信息学等领域有广泛应用。

SVM 的核心思想是：在特征空间中找到一个最优的超平面，使得不同类别的样本能够被最大程度地分开。

---

基本概念

超平面

在 $d$ 维空间中，超平面是一个 $d-1$ 维的子空间。对于二维空间，超平面是一条直线；对于三维空间，超平面是一个平面。

超平面的方程可以表示为：

$$w^{T}x+b=0$$

其中：

• $w$ 是法向量（权重向量）
• $x$ 是输入特征向量
• $b$ 是偏置项

间隔

间隔是指超平面到最近样本点的距离。SVM 的目标是最大化这个间隔。

点到超平面的距离公式为：

$$d=\frac{|w^{T}x+b|}{\Vert w\Vert }$$

支持向量

支持向量是指距离超平面最近的那些样本点。这些点决定了超平面的位置和方向，因此被称为"支持"向量。

---

线性支持向量机

硬间隔 SVM

对于线性可分的数据集，SVM 寻找一个能够正确划分所有样本且间隔最大的超平面。

优化问题：

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2$$

约束条件：

$$y_i(w^T{x}_i+b)\ge 1,i=1,2,\dots ,n$$

其中 y i ∈ { − 1 , + 1 } y_i \in \{-1, +1\} yi​∈{−1,+1} 是类别标签。

对偶问题

通过拉格朗日对偶，原问题可以转化为对偶问题：

$$\underset{\alpha }{\max }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$

约束条件：

$$\sum _{i=1}^n{\alpha }_i{y}_i=0$$
$${\alpha }_i\ge 0,i=1,2,\dots ,n$$

其中 ${\alpha }_i$ 是拉格朗日乘子。

决策函数

求解对偶问题后，决策函数为：

$$f(x)=\text{sign}\left(\sum _{i=1}^n{\alpha }_i{y}_i{x}_i^{T}x+b\right)$$

---

软间隔支持向量机

在实际应用中，数据往往不是完全线性可分的。软间隔 SVM 允许一定的分类错误，通过引入松弛变量 ${\xi }_i$ 来处理。

优化问题

$$\underset{w,b,\xi }{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n{\xi }_i$$

约束条件：

$$y_i(w^T{x}_i+b)\ge 1-{\xi }_i,i=1,2,\dots ,n$$
$${\xi }_i\ge 0,i=1,2,\dots ,n$$

其中：

• $C$ 是惩罚参数，控制间隔最大化和分类错误之间的权衡
• ${\xi }_i$ 是松弛变量，表示样本点违反间隔约束的程度

对偶问题

$$\underset{\alpha }{\max }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$$

约束条件：

$$\sum _{i=1}^n{\alpha }_i{y}_i=0$$
$$0\le {\alpha }_i\le C,i=1,2,\dots ,n$$

---

核技巧与非线性支持向量机

核函数的思想

对于非线性可分的数据，核技巧通过将数据映射到高维特征空间，使其在高维空间中变得线性可分。

设映射函数为 $\varphi (x):{\mathbb{R}}^d\to {\mathbb{R}}^D$，其中 $D>d$。

核函数定义为：

$$K(x_i,x_j)=\varphi (x_i{)}^T\varphi (x_j)$$

核函数的优势在于：我们不需要显式计算映射 $\varphi (x)$，只需要计算核函数 $K(x_i,x_j)$。

常见核函数

1. 线性核 (Linear Kernel)

$$K(x_i,x_j)=x_i^T{x}_j$$

适用于线性可分的数据。

2. 多项式核 (Polynomial Kernel)

$$K(x_i,x_j)=(x_i^T{x}_j+c{)}^d$$

其中 $d$ 是多项式次数，$c$ 是常数。

3. 高斯核 / 径向基函数核 (RBF Kernel)

$$K(x_i,x_j)=\exp \left(-\frac{\Vert x_i-x_j{\Vert }^2}{2{\sigma }^2}\right)$$

其中 $\sigma$ 是带宽参数。这是最常用的核函数之一。

4. Sigmoid 核

$$K(x_i,x_j)=\tanh (\gamma x_i^T{x}_j+r)$$

类似于神经网络的激活函数。

核函数的性质

有效的核函数必须满足 Mercer 条件：

• 对称性：$K(x_i,x_j)=K(x_j,x_i)$
• 半正定性：对于任意有限样本集 { x 1 , x 2 , … , x n } \{x_1, x_2, \ldots, x_n\} {x1​,x2​,…,xn​}，核矩阵 $K_{ij}=K(x_i,x_j)$ 是半正定的。

非线性 SVM 的决策函数

使用核函数后，决策函数变为：

$$f(x)=\text{sign}\left(\sum _{i=1}^n{\alpha }_i{y}_{i}K(x_i,x)+b\right)$$

---

支持向量回归

SVM 也可以用于回归问题，称为支持向量回归（SVR）。

$ϵ$-不敏感损失

SVR 使用 $ϵ$-不敏感损失函数：

$$L_{ϵ}(y,f(x))=\max (0,|y-f(x)|-ϵ)$$

这意味着当预测值与真实值的差值小于 $ϵ$ 时，损失为零。

优化问题

$$\underset{w,b,\xi ,{\xi }^{\ast }}{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^n({\xi }_i+{\xi }_i^{\ast })$$

约束条件：

$$y_i-(w^T{x}_i+b)\le ϵ+{\xi }_i$$
$$(w^T{x}_i+b)-y_i\le ϵ+{\xi }_i^{\ast }$$
$${\xi }_i,{\xi }_i^{\ast }\ge 0,i=1,2,\dots ,n$$

决策函数

$$f(x)=\sum _{i=1}^n({\alpha }_i-{\alpha }_i^{\ast })K(x_i,x)+b$$

---

SVM的优缺点

优点

1. 理论基础扎实：基于统计学习理论，有坚实的数学基础。
2. 泛化能力强：通过最大化间隔，能够获得较好的泛化性能。
3. 高维数据处理：适合处理高维特征空间，即使特征数量大于样本数量也能有效工作。
4. 核技巧：通过核函数可以处理非线性问题。
5. 全局最优解：凸优化问题，能够保证找到全局最优解。
6. 支持向量稀疏：只有支持向量影响决策函数，模型相对简洁。

缺点

1. 计算复杂度高：训练时间复杂度为 $O(n^2)$ 到 $O(n^3)$，不适合大规模数据集。
2. 内存消耗大：需要存储核矩阵，内存消耗为 $O(n^2)$。
3. 参数敏感：需要对核函数参数和惩罚参数 $C$ 进行调优。
4. 对缺失数据敏感：需要预处理缺失值。
5. 难以解释：对于非线性 SVM，模型的解释性较差。

---

实际应用

1. 文本分类

SVM 在文本分类中表现优异，如：

• 垃圾邮件检测
• 新闻分类
• 情感分析

2. 图像识别

• 人脸识别
• 手写数字识别（如 MNIST 数据集）
• 物体检测

3. 生物信息学

• 蛋白质分类
• 基因表达数据分析
• 疾病诊断

4. 金融领域

• 信用评分
• 欺诈检测
• 股票价格预测

5. 其他应用

• 手写识别
• 语音识别
• 异常检测

---

实现示例

Python 使用 scikit-learn

分类任务

from sklearn import svm
from sklearn.model_selection import train_test_split
from sklearn.datasets import make_classification
from sklearn.metrics import accuracy_score

# 生成示例数据
X, y = make_classification(n_samples=1000, n_features=20, 
                           n_informative=15, 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 分类器
clf = svm.SVC(kernel='rbf', C=1.0, gamma='scale')

# 训练模型
clf.fit(X_train, y_train)

# 预测
y_pred = clf.predict(X_test)

# 计算准确率
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy:.4f}")

# 获取支持向量
print(f"Number of support vectors: {len(clf.support_vectors_)}")

回归任务

from sklearn.svm import SVR
from sklearn.model_selection import train_test_split
from sklearn.datasets import make_regression
from sklearn.metrics import mean_squared_error, r2_score
import numpy as np

# 生成示例数据
X, y = make_regression(n_samples=1000, n_features=10, 
                       noise=0.1, random_state=42)

# 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

# 创建 SVR 回归器
svr = SVR(kernel='rbf', C=1.0, epsilon=0.1)

# 训练模型
svr.fit(X_train, y_train)

# 预测
y_pred = svr.predict(X_test)

# 评估
mse = mean_squared_error(y_test, y_pred)
r2 = r2_score(y_test, y_pred)
print(f"MSE: {mse:.4f}")
print(f"R² Score: {r2:.4f}")

不同核函数的比较

from sklearn import svm
from sklearn.datasets import make_circles
import matplotlib.pyplot as plt
import numpy as np

# 生成非线性可分数据
X, y = make_circles(n_samples=300, noise=0.05, factor=0.5, random_state=42)

# 创建不同的 SVM 模型
models = [
    ('Linear SVM', svm.SVC(kernel='linear')),
    ('Polynomial SVM', svm.SVC(kernel='poly', degree=3)),
    ('RBF SVM', svm.SVC(kernel='rbf'))
]

# 绘制决策边界
def plot_decision_boundary(model, X, y, ax, title):
    h = 0.02
    x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
    y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    
    model.fit(X, y)
    Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    
    ax.contourf(xx, yy, Z, alpha=0.4)
    ax.scatter(X[:, 0], X[:, 1], c=y, s=20, edgecolors='k')
    ax.set_title(title)

fig, axes = plt.subplots(1, 3, figsize=(15, 4))
for (name, model), ax in zip(models, axes):
    plot_decision_boundary(model, X, y, ax, name)

plt.tight_layout()
plt.show()

---

参数调优

关键参数

1. C（惩罚参数）：

   • 控制间隔最大化和分类错误之间的权衡
   • 较大的 C 值：更关注分类正确，可能导致过拟合
   • 较小的 C 值：更关注间隔最大化，可能欠拟合

2. gamma（核参数，用于 RBF 核）：

   • 控制单个训练样本的影响范围
   • 较大的 gamma：每个样本影响范围小，决策边界复杂
   • 较小的 gamma：每个样本影响范围大，决策边界平滑

3. kernel（核函数）：

   • ‘linear’：线性核
   • ‘poly’：多项式核
   • ‘rbf’：高斯核
   • ‘sigmoid’：Sigmoid 核

4. epsilon（SVR 参数）：

   • 控制对误差的容忍度
   • 较大的 epsilon：允许更大的误差，模型更简单

网格搜索示例

from sklearn.model_selection import GridSearchCV
from sklearn.svm import SVC

# 定义参数网格
param_grid = {
    'C': [0.1, 1, 10, 100],
    'gamma': ['scale', 'auto', 0.001, 0.01, 0.1, 1],
    'kernel': ['rbf', 'poly', 'sigmoid']
}

# 创建 SVM 模型
svc = SVC()

# 网格搜索
grid_search = GridSearchCV(svc, param_grid, cv=5, scoring='accuracy', n_jobs=-1)
grid_search.fit(X_train, y_train)

# 输出最佳参数
print(f"Best parameters: {grid_search.best_params_}")
print(f"Best cross-validation score: {grid_search.best_score_:.4f}")

# 使用最佳模型预测
best_model = grid_search.best_estimator_
y_pred = best_model.predict(X_test)

---

总结

支持向量机是一种强大且理论完善的机器学习算法。其核心思想是通过最大化间隔来找到最优分类超平面。通过核技巧，SVM 可以有效地处理非线性问题。

关键要点：

1. SVM 适用于中小规模、高维数据集
2. 核函数的选择对模型性能至关重要
3. 需要对参数进行适当的调优
4. 在文本分类、图像识别等领域有广泛应用
5. 对于大规模数据集，可能需要考虑其他算法或使用近似方法