支持向量机实战：超平面与支持向量确定的数学推导与Python实现

1次阅读

没有评论

共计 4194 个字符，预计需要花费 11 分钟才能阅读完成。

在支持向量机中，超平面方程 $w^Tx + b = 0$ 的数学含义可以从几何间隔的角度理解。几何间隔是指数据点到超平面的最短距离，计算公式为：

$$\text{几何间隔} = \frac{|w^Tx + b|}{|w|}$$

最大化几何间隔等价于最小化 $|w|$，这就是 SVM 优化问题的核心目标。理解这个几何意义有助于我们把握 SVM 的本质——寻找一个能最大化分类间隔的决策边界。

对于一个线性可分的数据集，我们可以将 SVM 问题表述为以下优化问题：

原始优化问题：
$$\min_{w,b} \frac{1}{2}|w|^2$$
约束条件：
$$y_i(w^Tx_i + b) \geq 1, \forall i$$
构造拉格朗日函数：
$$L(w,b,\alpha) = \frac{1}{2}|w|^2 – \sum_{i=1}^n \alpha_i[y_i(w^Tx_i + b) – 1]$$

KKT 条件是求解带约束优化问题的关键，对于 SVM 来说主要包括：

原始可行性条件：
$$y_i(w^Tx_i + b) \geq 1$$
对偶可行性条件：
$$\alpha_i \geq 0$$
互补松弛条件：
$$\alpha_i[y_i(w^Tx_i + b) – 1] = 0$$
梯度为零条件：
$$\nabla_w L = 0 \Rightarrow w = \sum_{i=1}^n \alpha_i y_i x_i$$
$$\nabla_b L = 0 \Rightarrow \sum_{i=1}^n \alpha_i y_i = 0$$

支持向量是那些位于间隔边界上的数据点，对应的 $\alpha_i > 0$。识别支持向量的方法很简单：

求解得到所有 $\alpha_i$ 后，非零的 $\alpha_i$ 对应的就是支持向量
计算偏置项 $b$ 时，只需要使用支持向量：
$$b = y_j – w^Tx_j \quad \text{对于任意支持向量} x_j$$

import numpy as np
from cvxopt import matrix, solvers

def linear_svm(X, y):
    """
    线性 SVM 实现
    X: 特征矩阵(n_samples, n_features)
    y: 标签向量(n_samples,), 取值±1
    """
    n_samples, n_features = X.shape

    # 构造二次规划问题的参数
    P = matrix(np.outer(y, y) * np.dot(X, X.T))  # 二次项系数
    q = matrix(-np.ones(n_samples))               # 一次项系数
    G = matrix(-np.eye(n_samples))                # 不等式约束
    h = matrix(np.zeros(n_samples))               # 不等式约束右侧
    A = matrix(y.reshape(1, -1).astype(float))    # 等式约束
    b = matrix(0.0)                               # 等式约束右侧

    # 求解二次规划
    solution = solvers.qp(P, q, G, h, A, b)
    alphas = np.array(solution['x']).flatten()

    # 提取支持向量
    sv = alphas > 1e-5
    support_vectors = X[sv]
    support_vector_labels = y[sv]
    support_vector_alphas = alphas[sv]

    # 计算权重向量和偏置
    w = np.sum((support_vector_alphas * support_vector_labels).reshape(-1, 1) * support_vectors, axis=0)
    b = np.mean(support_vector_labels - np.dot(support_vectors, w))

    return w, b, support_vectors

import matplotlib.pyplot as plt

def plot_decision_boundary(X, y, w, b, support_vectors):
    """可视化决策边界和支持向量"""
    plt.scatter(X[:, 0], X[:, 1], c=y, cmap=plt.cm.Paired)

    # 绘制决策边界
    ax = plt.gca()
    xlim = ax.get_xlim()
    ylim = ax.get_ylim()

    # 创建网格来评估模型
    xx = np.linspace(xlim[0], xlim[1], 30)
    yy = np.linspace(ylim[0], ylim[1], 30)
    YY, XX = np.meshgrid(yy, xx)
    xy = np.vstack([XX.ravel(), YY.ravel()]).T
    Z = np.dot(xy, w) + b

    # 绘制决策边界和间隔
    Z = Z.reshape(XX.shape)
    ax.contour(XX, YY, Z, colors='k', levels=[-1, 0, 1], 
               alpha=0.5, linestyles=['--', '-', '--'])

    # 标记支持向量
    ax.scatter(support_vectors[:, 0], support_vectors[:, 1], 
               s=100, linewidth=1, facecolors='none', edgecolors='k')
    plt.show()

处理线性不可分情况，我们需要引入松弛变量 $\xi_i$:

def soft_margin_svm(X, y, C=1.0):
    """
    带松弛变量的软间隔 SVM
    C: 正则化参数，控制对误分类的惩罚力度
    """
    n_samples, n_features = X.shape

    # 构造二次规划问题的参数
    P = matrix(np.outer(y, y) * np.dot(X, X.T))
    q = matrix(-np.ones(n_samples))

    # 不等式约束(alpha_i <= C)
    G = matrix(np.vstack((-np.eye(n_samples), np.eye(n_samples))))
    h = matrix(np.hstack((np.zeros(n_samples), np.ones(n_samples) * C)))

    A = matrix(y.reshape(1, -1).astype(float))
    b = matrix(0.0)

    solution = solvers.qp(P, q, G, h, A, b)
    alphas = np.array(solution['x']).flatten()

    # 提取支持向量(0 < alpha_i < C)
    sv = (alphas > 1e-5) & (alphas < C)
    support_vectors = X[sv]
    support_vector_labels = y[sv]
    support_vector_alphas = alphas[sv]

    # 计算权重和偏置
    w = np.sum((support_vector_alphas * support_vector_labels).reshape(-1, 1) * support_vectors, axis=0)
    b = np.mean(support_vector_labels - np.dot(support_vectors, w))

    return w, b, support_vectors

当使用核函数时，计算复杂度会显著增加：

高斯核 (RBF) 的计算复杂度为 $O(n^2d)$，其中 $n$ 是样本数，$d$ 是特征维度
多项式核的计算复杂度为 $O(nd^k)$，$k$ 是多项式次数
对于大规模数据，核矩阵可能无法放入内存

序列最小优化 (SMO) 算法是解决大规模 SVM 问题的有效方法：

每次只优化两个拉格朗日乘子，保持其他乘子固定
可以高效处理核函数，不需要存储整个核矩阵
实现时需要注意启发式选择乘子的策略

SVM 对特征的尺度非常敏感：

不同特征量纲差异大会导致模型偏向大尺度特征
建议使用标准化 (StandardScaler) 或归一化(MinMaxScaler)
对于 RBF 核，特征缩放尤其重要

参数 C 控制模型复杂度与训练误差的权衡：

C 值越大，对误分类的惩罚越大，可能导致过拟合
C 值越小，允许更多误分类，模型更简单
可以使用网格搜索 + 交叉验证寻找最佳 C 值

对于不平衡数据集，可以采取以下策略：

对少数类样本使用更大的惩罚系数 C
使用 class_weight 参数调整类别权重
考虑欠采样或过采样技术

from sklearn.base import BaseEstimator, ClassifierMixin

class LinearSVM(BaseEstimator, ClassifierMixin):
    def __init__(self, C=1.0, kernel='linear'):
        self.C = C
        self.kernel = kernel

    def fit(self, X, y):
        # 实现拟合逻辑
        pass

    def predict(self, X):
        # 实现预测逻辑
        pass

import unittest

class TestLinearSVM(unittest.TestCase):
    def test_linear_separable(self):
        # 构造线性可分数据
        X = np.array([[1,1], [2,2], [1,2], [2,1], [5,5], [6,6], [5,6], [6,5]])
        y = np.array([1,1,1,1,-1,-1,-1,-1])

        svm = LinearSVM()
        svm.fit(X, y)
        pred = svm.predict(X)

        self.assertTrue(np.all(pred == y))

在文本分类任务中：