支持向量机入门指南：从原理到实践

目录

1 支持向量机的基本概念

1.2 数学表达

2 间隔与支持向量

2.1 几何间隔

2.2 支持向量的概念

2.3 规范化超平面

2.4 支持向量的深入分析

2.4.1 支持向量的特征

 2.4.2 支持向量的作用

2.4.3 支持向量的代数表示

2.5 KKT条件

3 最优化问题

3.1 问题的形成

3.2 规范化处理

3.3 拉格朗日对偶性

3.3.1 构建拉格朗日函数

3.3.2 原始问题转化

3.3.3 对偶问题推导

3.4 求解过程

3.5 KKT条件分析

3.5.1 稳定性条件

3.5.2 可行性条件

3.5.3 互补松弛条件

3.6 SMO算法

3.6.1 基本思想

3.6.2 变量选择策略

 4 核函数

4.1 线性不可分问题

4.2 核技巧的基本思想

4.3 核函数的数学原理

4.3.1 特征空间映射

4.4 Mercer条件

4.5 常用核函数详解

4.5.1 线性核

4.5.2 多项式核

 4.5.3 高斯核(RBF核)

4.5.4 Sigmoid核

4.6 核函数的选择

5 软间隔与正则化

5.1 硬间隔的局限性

5.2 引入软间隔的原因

5.3 软间隔的数学描述

5.3.1 松弛变量

5.3.2 优化目标

5.4 正则化与参数C

5.4.1 惩罚参数C的作用

5.4.2 参数选择策略

6 SVM的优缺点

---

1 支持向量机的基本概念

在介绍支持向量机之前，我们先回顾一下最简单的线性分类器——感知机。感知机寻找一个超平面将两类样本分开，但这个超平面可能有无数个。而支持向量机则更进一步，不仅要将样本分开，还要找到"最优"的分隔超平面。

支持向量机最初是为解决二分类问题而设计的。其核心思想是:在特征空间中寻找一个最优超平面，使得两类样本分别位于超平面的两侧，并且使得两类样本到超平面的距离(称为间隔)尽可能大。

1.2 数学表达

假设我们的分隔超平面方程为：

w^T x + b = 0

 对于线性可分的数据集 {(x₁,y₁), (x₂,y₂), ..., (xₙ,yₙ)}，其中 yᵢ ∈ {+1,-1}，分类器可以表示为：

f(x) = sign(w^T x + b)

 要使得样本被正确分类，需要满足：

yᵢ(w^T xᵢ + b) > 0

2 间隔与支持向量

2.1 几何间隔

对于一个样本点到超平面的距离（几何间隔）计算公式为：

• 函数间隔：

  • 定义：γ̂ᵢ = yᵢ(w^T xᵢ + b)
  • 特点：依赖于w和b的取值，不是标准化的度量

• 几何间隔：

  • 定义：γᵢ = yᵢ(w^T xᵢ + b)/||w||
  • 特点：与w和b的缩放无关，是标准化的度量
  • 实际应用中更有意义

支持向量机的核心思想是寻找最大间隔分隔超平面。这里的"间隔"指的是什么？

1. 几何间隔：样本点到分隔超平面的垂直距离
2. 总体间隔：所有样本点中到超平面最小的距离的两倍

为什么要最大化间隔？

• 更大的间隔意味着分类器对噪声和新样本有更好的鲁棒性
• 这种策略可以有效降低过拟合的风险
• 数学上可以证明，最大间隔分类器是唯一的 

2.2 支持向量的概念

支持向量是训练数据集中距离分隔超平面最近的样本点。它们具有以下特点：

1. 决定性作用：

   • 仅支持向量参与确定最优分隔超平面
   • 其他样本点对模型没有影响

2. 稀疏性：

   • 通常支持向量数量远少于样本总数
   • 这种稀疏性使得SVM在预测时很高效

3. 鲁棒性：

   • 模型只依赖于支持向量
   • 非支持向量的扰动不影响模型

2.3 规范化超平面

为了使问题便于求解，我们通常对分隔超平面进行规范化：

将约束条件统一为：

yᵢ(w^T xᵢ + b) ≥ 1

 此时，支持向量满足：

yᵢ(w^T xᵢ + b) = 1

间隔大小为：

margin = 2/||w||

这种规范化使得最大化间隔的问题转化为最小化 ||w|| 的问题，这是一个凸二次规划问题，可以使用成熟的优化方法求解。

2.4 支持向量的深入分析

2.4.1 支持向量的特征

1. 位置特征：

   • 落在间隔边界上
   • 满足条件 yᵢ(w^T xᵢ + b) = 1

2. 数学特征：

   • 对应的拉格朗日乘子 αᵢ > 0
   • 是最优化问题的活动约束

3. 影响特征：

   • 决定超平面位置和方向
   • 移除非支持向量不影响模型

 2.4.2 支持向量的作用

2.4.3 支持向量的代数表示

对于任意支持向量 (xs,ys)，有：

w = ∑αᵢyᵢxᵢ

其中 αᵢ 是拉格朗日乘子，只有支持向量对应的 αᵢ 不为零。

2.5 KKT条件

最优解必须满足KKT条件：

互补松弛条件：

αᵢ(yᵢ(w^T xᵢ + b) - 1) = 0

 约束条件：

yᵢ(w^T xᵢ + b) - 1 ≥ 0
αᵢ ≥ 0

3 最优化问题

3.1 问题的形成

从几何角度看，我们要找到间隔最大的分离超平面。这可以分两步理解：

• 分类要求：所有样本被正确分类

yᵢ(w^T xᵢ + b) > 0, i=1,2,...,n

• 间隔最大化：最大化所有样本到超平面的最小距离

max min(yᵢ(w^T xᵢ + b)/||w||), i=1,2,...,n

3.2 规范化处理

为了简化计算，我们对超平面进行规范化：

• 将约束条件缩放为 yᵢ(w^T xᵢ + b) ≥ 1
• 此时间隔等于 2/||w||

因此，最优化问题可以写成：

min 1/2 ||w||²
s.t. yᵢ(w^T xᵢ + b) ≥ 1, i=1,2,...,n

3.3 拉格朗日对偶性

3.3.1 构建拉格朗日函数

引入拉格朗日乘子 αᵢ ≥ 0，构建拉格朗日函数：

L(w,b,α) = 1/2 ||w||² - ∑αᵢ[yᵢ(w^T xᵢ + b) - 1]

3.3.2 原始问题转化

原始问题等价于：

min max L(w,b,α)
w,b  α≥0

3.3.3 对偶问题推导

1. 对w和b求偏导并令其为0：

∂L/∂w = w - ∑αᵢyᵢxᵢ = 0
∂L/∂b = -∑αᵢyᵢ = 0

 得到：

w = ∑αᵢyᵢxᵢ
∑αᵢyᵢ = 0

将这些结果代回拉格朗日函数，得到对偶问题：

max -1/2 ∑∑αᵢαⱼyᵢyⱼ(xᵢ^T xⱼ) + ∑αᵢ
s.t. ∑αᵢyᵢ = 0αᵢ ≥ 0, i=1,2,...,n

3.4 求解过程

import numpy as np
from scipy.optimize import minimizeclass SimpleSVM:def __init__(self, C=1.0):self.C = Cself.w = Noneself.b = Noneself.alpha = Noneself.support_vectors = Noneself.support_vector_labels = Nonedef _kernel(self, x1, x2):return np.dot(x1, x2)  # 线性核def _objective(self, alpha, X, y):# 目标函数n_samples = len(y)kernel_matrix = np.zeros((n_samples, n_samples))for i in range(n_samples):for j in range(n_samples):kernel_matrix[i,j] = self._kernel(X[i], X[j])objective = 0.5 * np.sum(np.outer(alpha * y, alpha * y) * kernel_matrix) - np.sum(alpha)return objectivedef _constraints(self, n_samples):# 约束条件constraints = [{'type': 'eq', 'fun': lambda alpha, y: np.dot(alpha, y), 'args': (self.y,)},{'type': 'ineq', 'fun': lambda alpha: alpha},{'type': 'ineq', 'fun': lambda alpha: self.C - alpha}]return constraintsdef fit(self, X, y):n_samples = len(y)self.X = Xself.y = y# 初始化alphaalpha0 = np.zeros(n_samples)# 定义约束constraints = self._constraints(n_samples)# 求解优化问题solution = minimize(fun=self._objective,x0=alpha0,args=(X, y),method='SLSQP',constraints=constraints)self.alpha = solution.x# 找出支持向量sv_threshold = 1e-5sv_idx = np.where(self.alpha > sv_threshold)[0]self.support_vectors = X[sv_idx]self.support_vector_labels = y[sv_idx]self.alpha = self.alpha[sv_idx]# 计算w和bself.w = np.sum(self.alpha.reshape(-1,1) * self.support_vector_labels.reshape(-1,1) * self.support_vectors, axis=0)# 计算bmargin_vectors = self.support_vectors[0]self.b = self.support_vector_labels[0] - np.dot(self.w, margin_vectors)def predict(self, X):return np.sign(np.dot(X, self.w) + self.b)

3.5 KKT条件分析

KKT条件是最优解的必要条件：

3.5.1 稳定性条件

∂L/∂w = w - ∑αᵢyᵢxᵢ = 0
∂L/∂b = -∑αᵢyᵢ = 0

3.5.2 可行性条件

yᵢ(w^T xᵢ + b) - 1 ≥ 0
αᵢ ≥ 0

3.5.3 互补松弛条件

αᵢ(yᵢ(w^T xᵢ + b) - 1) = 0

3.6 SMO算法

序列最小优化(SMO)算法是解决SVM优化问题的高效算法：

3.6.1 基本思想

1. 每次选择两个变量进行优化
2. 固定其他变量
3. 解析求解这个二次规划问题

3.6.2 变量选择策略

1. 第一个变量选择：

   • 违反KKT条件最严重的点
   • 启发式搜索

2. 第二个变量选择：

   • 使目标函数下降最快的点
   • 通常选择使间隔最大的点

 4 核函数

4.1 线性不可分问题

在实际应用中，很多数据集是线性不可分的。例如以下情况：

4.2 核技巧的基本思想

1. 映射思想：

   • 将数据从原始空间映射到高维特征空间
   • 在高维空间中寻找线性分类面

2. 计算技巧：

   • 避免显式地计算高维特征空间中的内积
   • 直接在原始空间中计算核函数值

4.3 核函数的数学原理

4.3.1 特征空间映射

定义映射 Φ：X → H，将原始空间的数据映射到特征空间：

x → Φ(x)

在特征空间中的内积可表示为：

K(x,z) = <Φ(x),Φ(z)>

4.4 Mercer条件

核函数需满足Mercer条件：

1. 对称性：K(x,z) = K(z,x)
2. 半正定性：对任意函数g(x)，满足:

∫∫K(x,z)g(x)g(z)dxdz ≥ 0

4.5 常用核函数详解

4.5.1 线性核

最简单的核函数：

K(x,z) = x^T z

4.5.2 多项式核

K(x,z) = (γx^T z + r)^d

参数：

• d：多项式的次数
• γ：核系数
• r：常数项

 4.5.3 高斯核(RBF核)

K(x,z) = exp(-γ||x-z||²)

特点：

• 将样本映射到无穷维空间
• γ控制高斯分布的宽度

4.5.4 Sigmoid核

K(x,z) = tanh(γx^T z + r)

我们看一个实现这些核函数的代码示例：

import numpy as npclass KernelFunctions:def linear_kernel(X1, X2):"""线性核函数K(x,z) = x^T z"""return np.dot(X1, X2.T)def polynomial_kernel(X1, X2, degree=3, gamma=1, coef0=1):"""多项式核函数K(x,z) = (gamma * x^T z + coef0)^degree"""return (gamma * np.dot(X1, X2.T) + coef0) ** degreedef rbf_kernel(X1, X2, gamma=1):"""高斯RBF核函数K(x,z) = exp(-gamma ||x-z||^2)"""# 计算欧氏距离的平方X1_norm = np.sum(X1**2, axis=1).reshape(-1,1)X2_norm = np.sum(X2**2, axis=1).reshape(1,-1)distances = X1_norm + X2_norm - 2 * np.dot(X1, X2.T)return np.exp(-gamma * distances)def sigmoid_kernel(X1, X2, gamma=1, coef0=1):"""Sigmoid核函数K(x,z) = tanh(gamma * x^T z + coef0)"""return np.tanh(gamma * np.dot(X1, X2.T) + coef0)def kernel_matrix(self, X1, X2, kernel_type='rbf', **kwargs):"""计算核矩阵"""kernel_functions = {'linear': self.linear_kernel,'poly': self.polynomial_kernel,'rbf': self.rbf_kernel,'sigmoid': self.sigmoid_kernel}if kernel_type not in kernel_functions:raise ValueError(f"Unknown kernel type: {kernel_type}")return kernel_functions[kernel_type](X1, X2, **kwargs)# 使用示例
if __name__ == "__main__":# 生成示例数据X1 = np.array([[1, 2], [3, 4]])X2 = np.array([[5, 6], [7, 8]])kf = KernelFunctions()# 计算不同核函数的值print("Linear Kernel Matrix:")print(kf.kernel_matrix(X1, X2, kernel_type='linear'))print("\nRBF Kernel Matrix:")print(kf.kernel_matrix(X1, X2, kernel_type='rbf', gamma=0.5))

4.6 核函数的选择

• 先验知识：

  • 根据数据特征选择合适的核函数
  • 考虑问题的物理背景

• 数据特点：

  • 样本数量和维度
  • 数据分布特征

• 经验法则：

  • 小样本：线性核
  • 中等样本：RBF核
  • 特征关系复杂：多项式核

5 软间隔与正则化

5.1 硬间隔的局限性

5.2 引入软间隔的原因

1. 噪声数据：

   • 训练数据可能包含错误标记
   • 存在异常点(outliers)

2. 过拟合问题：

   • 严格的硬间隔容易过拟合
   • 降低模型泛化能力

3. 现实可行性：

   • 数据可能本身就不是线性可分的
   • 需要在分类准确性和模型复杂度之间权衡

5.3 软间隔的数学描述

5.3.1 松弛变量

引入松弛变量 ξᵢ ≥ 0，修改约束条件：

yᵢ(w^T xᵢ + b) ≥ 1 - ξᵢ

5.3.2 优化目标

新的优化问题变为：

min 1/2 ||w||² + C∑ξᵢ
s.t. yᵢ(w^T xᵢ + b) ≥ 1 - ξᵢξᵢ ≥ 0, i=1,2,...,n

其中：

• C > 0 是惩罚参数
• ∑ξᵢ 表示总的错误程度

我们看一个实现软间隔SVM的代码示例：

import numpy as np
from scipy.optimize import minimizeclass SoftMarginSVM:def __init__(self, C=1.0, kernel='linear'):self.C = Cself.kernel = kernelself.alpha = Noneself.support_vectors = Noneself.support_vector_labels = Noneself.b = Nonedef _kernel_function(self, x1, x2):if self.kernel == 'linear':return np.dot(x1, x2)elif self.kernel == 'rbf':gamma = 1.0return np.exp(-gamma * np.sum((x1 - x2) ** 2))def _compute_kernel_matrix(self, X1, X2):n1, n2 = len(X1), len(X2)K = np.zeros((n1, n2))for i in range(n1):for j in range(n2):K[i,j] = self._kernel_function(X1[i], X2[j])return Kdef _objective(self, alpha):# 目标函数：最大化对偶问题n = len(alpha)K = self._compute_kernel_matrix(self.X, self.X)# 计算目标函数值obj = 0.5 * np.sum(np.outer(alpha * self.y, alpha * self.y) * K) - np.sum(alpha)return objdef fit(self, X, y):n_samples = len(y)self.X = Xself.y = y# 构建约束条件constraints = [{'type': 'eq', 'fun': lambda alpha: np.sum(alpha * y)},  # sum(alpha_i * y_i) = 0{'type': 'ineq', 'fun': lambda alpha: alpha},  # alpha_i >= 0{'type': 'ineq', 'fun': lambda alpha: self.C - alpha}  # alpha_i <= C]# 初始化alphaalpha0 = np.zeros(n_samples)# 求解优化问题solution = minimize(fun=self._objective,x0=alpha0,constraints=constraints,method='SLSQP')self.alpha = solution.x# 找出支持向量sv_threshold = 1e-5sv_idx = np.where((self.alpha > sv_threshold) & (self.alpha < self.C - sv_threshold))[0]self.support_vectors = X[sv_idx]self.support_vector_labels = y[sv_idx]self.support_vector_alphas = self.alpha[sv_idx]# 计算偏置项bself.b = 0for i in range(len(sv_idx)):self.b += self.support_vector_labels[i]self.b -= np.sum(self.support_vector_alphas * self.support_vector_labels * self._compute_kernel_matrix(self.support_vectors, [self.support_vectors[i]]))self.b /= len(sv_idx)def predict(self, X):K = self._compute_kernel_matrix(self.support_vectors, X)return np.sign(np.sum(self.support_vector_alphas * self.support_vector_labels * K, axis=0) + self.b)# 使用示例
if __name__ == "__main__":# 生成示例数据np.random.seed(0)X = np.r_[np.random.randn(20, 2) - [2, 2], np.random.randn(20, 2) + [2, 2]]y = np.array([-1]*20 + [1]*20)# 训练模型svm = SoftMarginSVM(C=1.0)svm.fit(X, y)# 预测y_pred = svm.predict(X)accuracy = np.mean(y == y_pred)print(f"准确率: {accuracy:.2f}")

5.4 正则化与参数C

5.4.1 惩罚参数C的作用

1. 平衡作用：

   • 控制间隔最大化和误分类最小化之间的平衡
   • C越大，对误分类的惩罚越重

2. 模型复杂度：

   • C越小，模型越简单，泛化能力越强
   • C越大，模型越复杂，更容易过拟合

5.4.2 参数选择策略

1. 交叉验证：

   • 使用网格搜索找最优C值
   • 通常尝试 C ∈ {0.1, 1, 10, 100, ...}

2. 经验法则：

   • 数据噪声大时，选择较小的C
   • 数据质量好时，可以选择较大的C

6 SVM的优缺点

优点：

• 有严格的数学理论支持
• 解是全局最优而非局部最优
• 可以处理高维数据
• 泛化能力强

缺点：

• 对参数调节较敏感
• 计算复杂度高
• 对缺失数据敏感
• 对样本规模敏感