一、算法原理

支持向量机（Support Vector Machine, SVM）是一种经典的监督学习算法，主要用于分类和回归任务。其核心思想是找到一个最优超平面，使得不同类别的数据点之间的间隔（Margin）最大化，从而提高模型的泛化能力。

1. SVM 的基本思想

（1） 线性可分情况

假设数据是线性可分的（即可以用一条直线或超平面完全分开），SVM 的目标是找到一个决策边界（超平面），使得：
正确分类所有训练样本。
最大化分类间隔（即两类数据点到超平面的最小距离之和）。
数学表示：
给定训练数据：X={(xi,yi)}i=1n，其中xi∈Rd是特征向量，yi∈{−1,+1}是类别标签X=\{(x_i,y_i)\}_{i=1}^n，其中x_i \in R^d是特征向量，y_i\in\{-1,+1\}是类别标签X={(xi​,yi​)}i=1n​，其中xi​∈Rd是特征向量，yi​∈{−1,+1}是类别标签
超平面方程为：
${\mathbf{w}}^{\mathbf{t}}\mathbf{x}+b=0$
其中,$\mathbf{w}是法向量，b是偏置。$
分类间隔
对于任意样本，到超平面的距离为：
$d_i=\frac{|{\mathbf{w}}_{\mathbf{t}}{\mathbf{x}}_{\mathbf{i}}+\mathbf{b}|}{||\mathbf{w}||}$
由于yi∈{−1,+1}y_i \in\{-1,+1\}yi​∈{−1,+1}，则：
$d_i=\frac{y_i({\mathbf{w}}_{\mathbf{t}}{\mathbf{x}}_{\mathbf{i}}+b)}{||\mathbf{w}||}$
分类间隔（Margin）定义为所有样本到超平面的最小距离的两倍：
$Magin=\frac{2}{||\mathbf{w}||}$
优化目标
为了最大化间隔，SVM 的优化问题可以表示为：
${\min }_{\mathbf{w},b}\frac{1}{2}||\mathbf{w}|{|}^2,s.t.y_i({\mathbf{w}}_{\mathbf{t}}{\mathbf{x}}_{\mathbf{i}}+b)\ge 1,\forall i$
即：
1、最小化$||\mathbf{w}||$等价于最大化$Margin$。
2、确保所有样本正确分类（约束条件）。
损失函数：
铰链损失（Hinge Loss）函数：
$HingeLoss=\max (0,1-y_i({\mathbf{w}}_{\mathbf{i}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{i}}+b))$

优化方法:随机梯度下降（SGD）和 序列最小优化算法（SMO）
SGD（随机梯度下降）
用途：通用优化算法，用于最小化任意可微的损失函数（如线性回归、逻辑回归、神经网络等）。
目标：通过迭代更新参数（如权重 w和偏置b），逐步逼近损失函数的全局最小值。
适用场景：大规模数据集、在线学习（数据流式到达）。
SMO（序列最小优化算法）
用途：专门用于解决支持向量机（SVM）的对偶问题（即优化拉格朗日乘子 α）。
目标：快速求解 SVM 的二次规划（QP）问题，找到最优的 α向量（满足 KKT 条件）。
适用场景：中小规模数据集（SVM 的训练通常需要存储核矩阵，内存消耗较大）。

（2）软间隔 SVM（处理非线性可分数据）

实际数据往往不是完全线性可分的（可能存在噪声或异常点）。为了允许少量误分类，引入松弛变量（Slack Variables） ${\xi }_i\ge 0:$
${\min }_{\mathbf{w},b,\xi }\frac{1}{2}||\mathbf{w}|{|}^2+C{\sum }_{i=1}^n{\xi }_i,s.t.y_i({\mathbf{w}}_{\mathbf{t}}{\mathbf{x}}_{\mathbf{i}}+b)\ge 1-{\xi }_i,{\xi }_i\ge 0,\forall i$
其中：C>0是正则化参数，控制对误分类的惩罚程度。
C越大，模型越严格（不允许误分类）。
C越小，模型越宽松（允许更多误分类）。

2. 对偶问题与核方法

（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{\mathbf{x}}_{\mathbf{i}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{j}},s.t.{\sum }_{i=1}^n{a}_i{y}_i=0,0\le a_i\le C,\forall i$
其中，${\alpha }_i$是拉格朗日乘子（对应原始问题的约束）。
只用${\alpha }_i>0$的样本是支持向量（Support Vectors），它们决定了超平面的位置。
决策函数
最终分类决策函数为：
$f(x)=sign({\sum }_{i=1}^n{a}_i{y}_i{\mathbf{x}}_{\mathbf{i}}^{\mathbf{T}}\mathbf{x}+b)$

3、核方法（Kernel Trick）

当数据非线性可分时，可以通过核函数（Kernel Function）将数据映射到更高维的特征空间，使其线性可分。
常见的核函数包括：

（1）线性核（Linear Kernel）：

$K({\mathbf{x}}_{\mathbf{i}},{\mathbf{x}}_{\mathbf{j}})={\mathbf{x}}_{\mathbf{i}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{j}}$

（2）多项式核（Polynomial Kernel）：

$K({\mathbf{x}}_{\mathbf{i}},{\mathbf{x}}_{\mathbf{j}})=({\mathbf{x}}_{\mathbf{i}}^{\mathbf{T}}{\mathbf{x}}_{\mathbf{j}}+c{)}^d$

（3）高斯核（RBF Kernel）：

$K({\mathbf{x}}_{\mathbf{i}},{\mathbf{x}}_{\mathbf{j}})=exp(-\gamma ||{\mathbf{x}}_{\mathbf{i}}-{\mathbf{x}}_{\mathbf{j}}|{|}^2)$
其中$\gamma >0$控制高斯分布的宽度。
核化决策函数
使用核函数后，决策函数变为：
$f(x)=sign({\sum }_{i=1}^n{a}_i{y}_{i}K({\mathbf{x}}_{\mathbf{i}},\mathbf{x})+b)$

4、序列最小优化（SMO, Sequential Minimal Optimization）

（1）每次只优化两个拉格朗日乘子 ${\alpha }_i$和${\alpha }_j$（因为$\sum {\alpha }_i{y}_i=0的约束。$）
（2）固定其他的${\alpha }_k(k\ne i,j)$，求解这两个变量的优化问题。
（3）重复这两个步骤，直到所有${\alpha }_k$满足KKT 条件（最优性条件）。

二、参考代码

class SVMSMO:
    def __init__(self, C=1.0, kernel='rbf', gamma='auto', tol=1e-3, max_iter=100, cache_size=100):
        self.C = C
        self.kernel = kernel
        self.gamma = gamma
        self.tol = tol
        self.max_iter = max_iter
        self.cache_size = cache_size
        self.alpha = None
        self.b = 0
        self.X = None
        self.y = None
        self.support_vectors = None
        self.support_alpha = None
        self.support_y = None
        self.kernel_cache = {}  # 核函数缓存
        self.E_cache = {}      # 误差缓存

    def _kernel(self, x1, x2):
        """计算核函数（线性核或 RBF 核），使用缓存优化"""
        # 生成唯一键（基于数据内容而非内存地址）
        key = (tuple(x1), tuple(x2)) if hasattr(x1, '__len__') else (x1, x2)
        
        if key in self.kernel_cache:
            return self.kernel_cache[key]
        
        if self.kernel == 'linear':
            result = np.dot(x1, x2)
        elif self.kernel == 'rbf':
            if self.gamma == 'auto':
                self.gamma = 1.0 / self.X.shape[1] if self.X is not None else 1.0
            result = np.exp(-self.gamma * np.linalg.norm(x1 - x2) ** 2)
        else:
            raise ValueError("Unsupported kernel")
        
        # 限制缓存大小
        if len(self.kernel_cache) < self.cache_size:
            self.kernel_cache[key] = result
        return result

    def _compute_E(self, i):
        """计算预测误差 E_i = f(x_i) - y_i，使用缓存优化"""
        if i in self.E_cache:
            return self.E_cache[i]
        
        f_xi = 0.0
        for j in range(self.X.shape[0]):
            f_xi += self.alpha[j] * self.y[j] * self._kernel(self.X[j], self.X[i])
        f_xi += self.b
        E_i = f_xi - self.y[i]
        
        # 缓存误差
        if len(self.E_cache) < self.cache_size:
            self.E_cache[i] = E_i
        return E_i

    def _violate_kkt(self, i, E_i):
        """检查样本i是否违反KKT条件"""
        return ((self.y[i] * E_i < -self.tol and self.alpha[i] < self.C) or 
                (self.y[i] * E_i > self.tol and self.alpha[i] > 0))

    def _select_j(self, i, E_i):
        """选择第二个变量j（使|E_i - E_j|最大），使用误差缓存"""
        max_diff = -1
        best_j = -1
        E_j = 0
        
        # 优先考虑alpha>0的样本（支持向量候选）
        candidates = [idx for idx in range(self.X.shape[0]) if idx != i and self.alpha[idx] > 1e-5]
        if not candidates:
            candidates = [idx for idx in range(self.X.shape[0]) if idx != i]
        
        for j in candidates:
            E_j_tmp = self._compute_E(j)
            diff = abs(E_i - E_j_tmp)
            if diff > max_diff:
                max_diff = diff
                best_j = j
                E_j = E_j_tmp
        return best_j, E_j

    def _update_alpha(self, i, j):
        """更新alpha_i和alpha_j，优化核函数计算"""
        if i == j:
            return False

        x_i, y_i, alpha_i = self.X[i], self.y[i], self.alpha[i]
        x_j, y_j, alpha_j = self.X[j], self.y[j], self.alpha[j]
        E_i, E_j = self._compute_E(i), self._compute_E(j)

        # 计算边界L和H
        if y_i != y_j:
            L, H = max(0, alpha_j - alpha_i), min(self.C, self.C + alpha_j - alpha_i)
        else:
            L, H = max(0, alpha_i + alpha_j - self.C), min(self.C, alpha_i + alpha_j)
        
        if L == H:
            return False

        # 计算eta（二次项系数）
        eta = 2 * self._kernel(x_i, x_j) - self._kernel(x_i, x_i) - self._kernel(x_j, x_j)
        if eta >= 0:
            return False

        # 更新alpha_j和alpha_i
        new_alpha_j = alpha_j - y_j * (E_i - E_j) / eta
        new_alpha_j = np.clip(new_alpha_j, L, H)
        if abs(new_alpha_j - alpha_j) < 1e-5:
            return False

        new_alpha_i = alpha_i + y_i * y_j * (alpha_j - new_alpha_j)
        self.alpha[i], self.alpha[j] = new_alpha_i, new_alpha_j

        # 更新偏置b
        b1 = self.b - E_i - y_i * (new_alpha_i - alpha_i) * self._kernel(x_i, x_i) - y_j * (new_alpha_j - alpha_j) * self._kernel(x_i, x_j)
        b2 = self.b - E_j - y_i * (new_alpha_i - alpha_i) * self._kernel(x_i, x_j) - y_j * (new_alpha_j - alpha_j) * self._kernel(x_j, x_j)
        if 0 < new_alpha_i < self.C:
            self.b = b1
        elif 0 < new_alpha_j < self.C:
            self.b = b2
        else:
            self.b = (b1 + b2) / 2

        return True

    def fit(self, X, y):
        """训练SVM"""
        self.X = np.array(X)
        self.y = np.array(y).flatten()
        n_samples = self.X.shape[0]
        self.alpha = np.zeros(n_samples)
        self.b = 0
        self.kernel_cache = {}
        self.E_cache = {}

        for _ in range(self.max_iter):
            num_changed_alphas = 0
            for i in range(n_samples):
                E_i = self._compute_E(i)
                if self._violate_kkt(i, E_i):
                    j, E_j = self._select_j(i, E_i)
                    if j != -1 and self._update_alpha(i, j):
                        num_changed_alphas += 1
            if num_changed_alphas == 0:
                break

        # 保存支持向量
        sv_idx = self.alpha > 1e-5
        self.support_vectors = self.X[sv_idx]
        self.support_alpha = self.alpha[sv_idx]
        self.support_y = self.y[sv_idx]

    def predict(self, X):
        """预测"""
        X = np.array(X)
        if X.ndim == 1:
            X = X.reshape(1, -1)
        y_pred = np.zeros(X.shape[0])
        for i in range(X.shape[0]):
            prediction = 0
            for alpha, sv_y, sv in zip(self.support_alpha, self.support_y, self.support_vectors):
                prediction += alpha * sv_y * self._kernel(X[i], sv)
            y_pred[i] = prediction + self.b
        return np.sign(y_pred)

    def generate_svm_data(self, n_samples=100, dataset_type="linear", noise=0.1, random_state=42):
        """生成数据（仅返回 X, y，不划分训练集/测试集）"""
        np.random.seed(random_state)
        if dataset_type == "linear":
            X, y = make_blobs(n_samples=n_samples, centers=2, cluster_std=0.5, random_state=random_state)
        elif dataset_type == "moons":
            X, y = make_moons(n_samples=n_samples, noise=noise, random_state=random_state)
        elif dataset_type == "circles":
            X, y = make_circles(n_samples=n_samples, noise=noise, factor=0.4, random_state=random_state)
        else:
            raise ValueError("dataset_type mustbe 'linear', 'moons' or 'circles'")
        y = np.where(y == 0, -1, 1)
        X += np.random.normal(scale=noise, size=X.shape)
        return X, y
    def plot_decision_boundary(self, X, y, title):
    # 创建网格
        x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
        y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
        xx, yy = np.meshgrid(np.linspace(x_min, x_max, 100),
                            np.linspace(y_min, y_max, 100))
        
        # 预测网格点
        Z = self.predict(np.c_[xx.ravel(), yy.ravel()])
        Z = Z.reshape(xx.shape)
        
        # 绘图
        plt.figure(figsize=(8, 6))
        plt.contourf(xx, yy, Z, cmap='coolwarm', alpha=0.3)
        plt.scatter(self.support_vectors[:, 0], self.support_vectors[:, 1], 
                    facecolors='none', edgecolors='m', s=20, linewidths=2)
        plt.scatter(X[:, 0], X[:, 1], c=y, cmap='viridis', edgecolors='k', s=50)
        plt.title(title)
        plt.xlabel('Feature 1')
        plt.ylabel('Feature 2')
        plt.show()

三、应用场景和优缺点

1、SVM 的应用场景

图像分类（如手写数字识别）。
文本分类（如垃圾邮件检测）。
生物信息学（如基因分类）。
金融风控（如信用评分）。
医学诊断（如疾病预测）。

2、优点

高维数据有效：核方法可以处理高维数据。
泛化能力强：最大化间隔的策略减少了过拟合风险。
适用于小样本：即使样本较少，也能找到最优超平面。
理论保证：有严格的数学理论支持（如 VC 维理论）。

3、缺点

计算复杂度高：训练时间复杂度为
O($n^3$)（SMO 优化后有所改善）。
对参数敏感：核函数参数（如 γ）和正则化参数 C需要调优。
难以处理大规模数据：内存消耗大（需要存储核矩阵）。
对噪声敏感：软间隔 SVM 可以缓解，但仍可能受极端值影响。

四、SMO和SGD方法比较

1、线性数据（n=500,n_features=2）

SGDSVM参数：learning_rate=0.001, lambda_param=0.01, n_iters=1000
准确率:100%。

SMOSVM参数kernel=‘linear’, C=100.0,max_iter=10000
准确率:97.00%。

2、非线性数据

SGDSVM参数：learning_rate=0.001, lambda_param=0.01, n_iters=1000
准确率：62.00%，基本上不能应用。

SMOSVM参数：kernel=‘rbf’, C=100.0,max_iter=10000
准确率：92%，正常使用。