当前位置: 首页 > article >正文

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

目录

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 minimize

class SimpleSVM:
    def __init__(self, C=1.0):
        self.C = C
        self.w = None
        self.b = None
        self.alpha = None
        self.support_vectors = None
        self.support_vector_labels = None
        
    def _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 objective
        
    def _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 constraints
        
    def fit(self, X, y):
        n_samples = len(y)
        self.X = X
        self.y = y
        
        # 初始化alpha
        alpha0 = 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-5
        sv_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和b
        self.w = np.sum(self.alpha.reshape(-1,1) * self.support_vector_labels.reshape(-1,1) * 
                       self.support_vectors, axis=0)
        
        # 计算b
        margin_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 np

class 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) ** degree
    

    def 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 minimize

class SoftMarginSVM:
    def __init__(self, C=1.0, kernel='linear'):
        self.C = C
        self.kernel = kernel
        self.alpha = None
        self.support_vectors = None
        self.support_vector_labels = None
        self.b = None
        
    def _kernel_function(self, x1, x2):
        if self.kernel == 'linear':
            return np.dot(x1, x2)
        elif self.kernel == 'rbf':
            gamma = 1.0
            return 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 K
        
    def _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 obj
        
    def fit(self, X, y):
        n_samples = len(y)
        self.X = X
        self.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
        ]
        
        # 初始化alpha
        alpha0 = np.zeros(n_samples)
        
        # 求解优化问题
        solution = minimize(
            fun=self._objective,
            x0=alpha0,
            constraints=constraints,
            method='SLSQP'
        )
        
        self.alpha = solution.x
        
        # 找出支持向量
        sv_threshold = 1e-5
        sv_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]
        
        # 计算偏置项b
        self.b = 0
        for 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的优缺点

优点:

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

缺点:

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

http://www.kler.cn/a/454833.html

相关文章:

  • 面试突击-JAVA集合类(持续更新...)
  • 如何快速找到合适的科学问题
  • 攻防世界web新手第五题supersqli
  • WordPress源码解析-数据库表结构
  • 将多个 k8s yaml 配置文件合并为一个文件
  • 【C语言练习(17)—输出杨辉三角形】
  • 前端图像处理(二)
  • docker 容器中没有ping命令和ifconfig命令和wget怎么办?
  • LeetCode-Z 字形变换(006)
  • layui动态拼接生成下拉框验证必填项失效问题
  • 曼哈顿图如何指定不同染色体不同的颜色
  • 【Linux命令】ps -a 和 ps -ef 的区别
  • MySQL 服务正在启动.MySQL 服务无法启动.服务没有报告任何错误。请键入 NET HELPMSG 3534 以获得更多的帮助。总结较全 (已解决)
  • 香港站群服务器如何排查 Linux 系统的内存泄漏问题
  • 远程作业专家指导调度系统
  • 中巨伟业推出高安全高性能32位智能卡内核可编程加密芯片SMEC88SP/ST
  • 通过百度api处理交通数据
  • Java中处理if-else的几种高级方法
  • 用Excel表格在线发布期末考试成绩单
  • USB免驱IC读写器QT小程序开发
  • 计算机网络 (9)数据链路层
  • 深度学习在图像识别中的最新进展与实践案例
  • 如何在 Vue 中处理 API 请求?
  • 第3章 并行循环调度的准则
  • c++ 打开摄像头并显示摄像头捕获的数据
  • 【进阶编程】代理模式和适配模式的比较