68、C++项目实战：支持向量机（SVM）

支持向量机，这个名字听起来挺唬人的。说白了，它就是一种二分类算法，核心任务是在数据中找一条「分界线」，把不同类别的样本隔开。而且这条线还不是随便画的——它要离两边最近的样本点都尽可能远。

我记得刚接触SVM时，被那些拉格朗日对偶、核函数绕得晕头转向。后来在做一个文本分类项目时，硬着头皮手撸了一遍，才真正搞明白。嗯，今天我们就用C++把它从零实现一遍。

SVM的核心思想

先看一个简单场景：二维平面上有两类点，我们要画一条直线把它们分开。哪条线最好？

直觉告诉我们，应该选那条「居中」的线。因为如果线太靠近某一类点，新来的数据稍微有点波动，就可能被分错。

SVM把这个直觉数学化了：它要找的直线（在高维空间叫超平面），不仅要能分开两类数据，还要让离它最近的样本点（支持向量）到它的距离最大化。这个距离叫「间隔」。

核心公式：

最大化间隔 = 最小化 ||w||²，同时满足 yᵢ(w·xᵢ + b) ≥ 1

其中 w 是法向量，b 是偏置，yᵢ 是标签（+1或-1）。

从数学到代码：线性可分SVM

我们先处理最简单的情况——数据完全线性可分。这时候问题转化为一个凸二次规划，可以用SMO（序列最小优化）算法求解。

SMO算法的思路很巧妙：每次只优化两个拉格朗日乘子，固定其他所有乘子。这样就把大问题拆成了无数个小问题，每个小问题都能直接求解。

我在项目中遇到过一个问题：当数据量很大时，SMO的收敛速度会变慢。后来我加了一个缓存机制，把频繁访问的核函数结果存起来，速度提升了不少。

// SVM核心类定义
class SVM {
private:
    std::vector<double> alpha;  // 拉格朗日乘子
    double b;                    // 偏置
    std::vector<std::vector<double>> X; // 训练数据
    std::vector<int> y;         // 标签
    double C;                    // 惩罚参数
    double tol;                  // 容差
    int max_iter;                // 最大迭代次数

    // 核函数：这里用线性核
    double kernel(const std::vector<double>& x1, 
                  const std::vector<double>& x2) {
        double sum = 0.0;
        for (size_t i = 0; i < x1.size(); ++i) {
            sum += x1[i] * x2[i];
        }
        return sum;
    }

    // 预测单个样本
    double predict(const std::vector<double>& x) {
        double sum = 0.0;
        for (size_t i = 0; i < alpha.size(); ++i) {
            if (alpha[i] > 0) {
                sum += alpha[i] * y[i] * kernel(X[i], x);
            }
        }
        return sum + b;
    }
};

SMO算法的关键步骤

SMO的核心就两步：选择两个要优化的乘子，然后更新它们。选择策略直接影响收敛速度。

  1. 外层循环：遍历所有违反KKT条件的样本点。先找那些0 < αᵢ < C的样本，因为它们最可能违反条件。
  2. 内层循环：为选中的αᵢ找一个搭档αⱼ，使得|Eᵢ - Eⱼ|最大。E是预测误差，差值越大，说明这两个乘子一起优化时步长越大。
  3. 更新乘子：根据约束条件裁剪αⱼ，然后更新αᵢ和b。

避坑指南：我曾经在实现SMO时，忘记处理αⱼ的上下界裁剪。结果迭代了几百次都不收敛，最后发现αⱼ的值早就跑到约束范围外了。记住：每次更新后都要做裁剪，这是SMO能稳定运行的关键。

// SMO算法核心更新逻辑
bool SVM::smo() {
    int num_samples = X.size();
    int iter = 0;
    
    while (iter < max_iter) {
        int num_changed = 0;
        
        for (int i = 0; i < num_samples; ++i) {
            double Ei = predict(X[i]) - y[i];
            
            // 检查是否违反KKT条件
            if ((y[i] * Ei < -tol && alpha[i] < C) ||
                (y[i] * Ei > tol && alpha[i] > 0)) {
                
                // 选择第二个乘子
                int j = select_second(i, Ei);
                double Ej = predict(X[j]) - y[j];
                
                double old_alpha_i = alpha[i];
                double old_alpha_j = alpha[j];
                
                // 计算上下界
                double L, H;
                if (y[i] != y[j]) {
                    L = std::max(0.0, alpha[j] - alpha[i]);
                    H = std::min(C, C + alpha[j] - alpha[i]);
                } else {
                    L = std::max(0.0, alpha[i] + alpha[j] - C);
                    H = std::min(C, alpha[i] + alpha[j]);
                }
                
                if (L == H) continue;
                
                // 计算η
                double eta = 2 * kernel(X[i], X[j]) 
                           - kernel(X[i], X[i]) 
                           - kernel(X[j], X[j]);
                if (eta >= 0) continue;
                
                // 更新αⱼ
                alpha[j] -= y[j] * (Ei - Ej) / eta;
                alpha[j] = clip(alpha[j], L, H);
                
                // 更新αᵢ
                alpha[i] += y[i] * y[j] * (old_alpha_j - alpha[j]);
                
                // 更新偏置b
                double b1 = b - Ei - y[i] * (alpha[i] - old_alpha_i) 
                          * kernel(X[i], X[i]) 
                          - y[j] * (alpha[j] - old_alpha_j) 
                          * kernel(X[i], X[j]);
                double b2 = b - Ej - y[i] * (alpha[i] - old_alpha_i) 
                          * kernel(X[i], X[j]) 
                          - y[j] * (alpha[j] - old_alpha_j) 
                          * kernel(X[j], X[j]);
                
                if (alpha[i] > 0 && alpha[i] < C) b = b1;
                else if (alpha[j] > 0 && alpha[j] < C) b = b2;
                else b = (b1 + b2) / 2;
                
                num_changed++;
            }
        }
        
        if (num_changed == 0) iter++;
        else iter = 0;
    }
    return true;
}

核函数：让SVM处理非线性问题

现实中的数据很少是线性可分的。比如同心圆分布的两类点，你永远找不到一条直线把它们分开。

SVM的解决方案是：把数据映射到更高维的空间。在低维空间线性不可分，到了高维空间可能就分开了。核函数就是干这个的——它让你不用显式地做高维映射，直接在原空间计算内积。

核函数类型 公式 适用场景
线性核 K(x, z) = x·z 数据本身线性可分
多项式核 K(x, z) = (γx·z + r)ᵈ 有交互特征的数据
RBF核（高斯核） K(x, z) = exp(-γ||x - z||²) 最常用，适合大多数场景
Sigmoid核 K(x, z) = tanh(γx·z + r) 类似神经网络的激活函数

注意：RBF核虽然强大，但参数γ很敏感。γ太大容易过拟合（每个样本都变成支持向量），γ太小又欠拟合（决策边界太平滑）。我一般用交叉验证来调这个参数，或者先用默认值跑一遍，看看支持向量的数量是否合理。

软间隔：容忍噪声

如果数据中有一些离群点，硬间隔SVM会强行把它们分开，导致决策边界扭曲。这时候需要引入软间隔——允许一些样本点落在间隔内部甚至被分错。

做法是引入松弛变量ξᵢ，每个样本点可以有一定程度的「违规」。目标函数变成：

最小化 ½||w||² + C·Σξᵢ

C是惩罚参数。C越大，对违规的容忍度越低；C越小，决策边界越平滑。我在做金融风控项目时，C通常设得比较大，因为误判的代价很高。

// 软间隔SVM的预测函数
double SVM::predict_soft(const std::vector<double>& x) {
    double sum = 0.0;
    for (size_t i = 0; i < alpha.size(); ++i) {
        // 只有支持向量（alpha > 0）才参与计算
        if (alpha[i] > 1e-5) {
            sum += alpha[i] * y[i] * kernel(X[i], x);
        }
    }
    return sum + b;
}

// 判断样本是否为支持向量
bool SVM::is_support_vector(int idx) {
    return alpha[idx] > 1e-5 && alpha[idx] < C - 1e-5;
}

SVM的完整工作流程

下面这张图展示了SVM从训练到预测的完整流程。你想想看，整个流程其实就三步：数据准备、SMO训练、预测分类。

SVM训练与预测流程 数据准备 特征提取 + 标签编码 SMO训练 迭代优化α和b 模型保存 支持向量 + 权重 SMO内部迭代细节 选择违反KKT的αᵢ → 选择搭档αⱼ 更新αᵢ、αⱼ → 更新偏置b 检查收敛 → 未收敛则继续迭代 预测分类 计算决策函数 f(x) = ΣαᵢyᵢK(xᵢ, x) + b 输出：类别标签（+1 或 -1）

完整代码示例：训练与预测

最后，我们把这些模块拼起来，形成一个完整的SVM训练和预测流程。这里我用了一个简单的二维数据集做演示。

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <random>

int main() {
    // 生成线性可分数据
    std::vector<std::vector<double>> data = {
        {2.0, 3.0}, {3.0, 2.0}, {4.0, 4.0}, {1.0, 1.0},
        {5.0, 1.0}, {6.0, 2.0}, {7.0, 3.0}, {8.0, 1.0}
    };
    std::vector<int> labels = {1, 1, 1, 1, -1, -1, -1, -1};
    
    // 创建SVM对象并训练
    SVM svm;
    svm.set_params(1.0, 0.001, 1000);  // C, tol, max_iter
    svm.train(data, labels);
    
    // 预测新样本
    std::vector<double> test_point = {4.5, 2.5};
    double result = svm.predict(test_point);
    
    std::cout << "预测结果: " << (result > 0 ? "正类" : "负类") << std::endl;
    std::cout << "决策函数值: " << result << std::endl;
    
    // 输出支持向量数量
    std::cout << "支持向量数量: " << svm.get_support_vector_count() << std::endl;
    
    return 0;
}

个人经验：在实际项目中，我很少直接用自己写的SVM。但理解它的原理后，用libsvm或OpenCV的SVM接口时，调参就有底气多了。比如我知道C越大越容易过拟合，γ越大决策边界越复杂——这些都不是黑盒，而是我能掌控的参数。

SVM虽然诞生于上世纪90年代，但在小样本、高维数据的场景下依然能打。尤其是文本分类、图像识别这些领域，配合RBF核，效果往往不输深度学习。嗯，掌握它的原理和实现，对你理解整个机器学习体系都有帮助。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →