一、项目背景详细介绍

机器学习分类算法在计算机视觉、自然语言处理、推荐算法、医学诊断等领域得到广泛应用，在深度学习出现之前，传统机器学习算法主导了大部分实际工业场景。而在传统机器学习领域中，**支持向量机（SVM，Support Vector Machine）**长期被认为是表现最优、泛化能力极强的分类器之一。

SVM 的核心思想是：

• 将数据映射到高维空间

• 寻找能够最大化分类边界（间隔 margin）的超平面

• 仅少量具有代表性的训练样本（支持向量）影响最终模型

因此它具有优雅的数学结构、稳定的泛化性能，并在小样本任务中表现极其优秀。

虽然现代工业多使用深度神经网络，但在以下场景中 SVM 依然非常强大：

• 样本数量较小但维度较高（如文本分类）

• 数据线性不可分但可通过核函数提升区分能力

• 需要严格控制模型复杂度和推理时间

• 对训练稳定性要求较高场景

本项目目标是用 C++ 手写一个可运行的 SVM 分类器，不依赖 OpenCV、libsvm 等库，从原理出发实现：

• 线性硬间隔 SVM

• 线性软间隔 SVM

• 使用 SMO 算法求解

• 支持核函数（线性、RBF）

本项目将实现一个 可完整训练、预测 的 SVM，并提供详细注释，非常适合学习 SVM 原理、C++ 数值优化实现、ML 基础算法开发。

---

二、项目需求详细介绍

要实现一个完整的 SVM 分类系统，需要具备以下核心功能：

✔ 1. 输入训练数据

• 支持二维及多维特征

• 标签为 +1 / -1

✔ 2. 模型训练

需要完成：

• 拉格朗日对偶形式构建

• 求解 α（拉格朗日指标）

• 求解 b（偏置项）

• 支持核函数

• 使用 SMO 算法迭代优化

✔ 3. 模型预测

• 根据 α、支持向量、核函数计算 f(x)

• 输出分类结果 sign(f(x))

✔ 4. 支持核函数

至少需要：

• 线性核

• RBF 核函数（高斯核）

✔ 5. 代码结构清晰、可直接复用

我们将拆分成：

• svm.h

• svm.cpp

• main.cpp

并放入单个代码块展示。

---

三、相关技术详细介绍

4. SMO 算法

SMO(Sequential Minimal Optimization)通过迭代优化两个 α 值使模型收敛，过程包括：

• 选择 α_i

• 选择 α_j

• 更新它们

• 修正 b

SMO 的优点：

• 不需要解大规模二次规划

• 每次只解决 2 个变量的优化

• 可在 C++ 中高效实现

---

四、实现思路详细介绍

实现逻辑如下：

1. 定义核函数

采用函数指针或 lambda 支持线性/RBF 核。

2. 构建 SVM 类

成员包括：

• 训练数据 X, y

• 训练参数 C, tol, max_iter

• α 数组

• 核矩阵

• 支持向量

• 偏置 b

3. SMO 训练流程

重复迭代直到 α 收敛：

for iter in max_iter: for i in samples: 计算误差 Ei 选择 j 更新 α_i, α_j 更新 b

4. 训练完成后保存支持向量

支持向量满足 α_i > 0。

5. 实现 predict 方法

通过核函数计算 f(x)：

---

五、完整实现代码

/******************************************************
 * 文件：svm.h
 * 功能：定义 SVM 类与核函数
 ******************************************************/
#ifndef SVM_H
#define SVM_H

#include <vector>
#include <cmath>
#include <functional>

class SVM {
public:
    // 核函数类型：输入向量 xi, xj -> 返回 double
    using KernelFunc = std::function<double(const std::vector<double>&,
                                            const std::vector<double>&)>;

    // 构造函数
    SVM(double C = 1.0, double tol = 1e-3, int max_iter = 1000);

    // 设置核函数
    void setKernel(KernelFunc func);

    // 训练模型
    void fit(const std::vector<std::vector<double>>& X,
             const std::vector<int>& y);

    // 预测单个样本
    int predict(const std::vector<double>& x) const;

private:
    double C;                 // 惩罚系数
    double tol;               // 容忍误差
    int max_iter;             // 最大迭代次数
    double b;                 // 偏置项

    std::vector<std::vector<double>> X; // 训练数据
    std::vector<int> y;                 // 标签
    std::vector<double> alpha;          // 拉格朗日参数

    KernelFunc kernel;                  // 核函数

    // SMO 中核心计算：预测 f(x)
    double calcFx(int i) const;

    // 误差 Ei
    double calcEi(int i) const;
};

#endif

/******************************************************
 * 文件：svm.cpp
 * 功能：SVM 实现（SMO求解）
 ******************************************************/
#include "svm.h"
#include <cstdlib>
#include <iostream>

SVM::SVM(double C, double tol, int max_iter)
    : C(C), tol(tol), max_iter(max_iter), b(0) {

    // 默认线性核： xi·xj
    kernel = [](const std::vector<double> &xi,
                const std::vector<double> &xj) {
        double sum = 0;
        for (size_t k = 0; k < xi.size(); k++)
            sum += xi[k] * xj[k];
        return sum;
    };
}

void SVM::setKernel(KernelFunc func) {
    kernel = func;
}

double SVM::calcFx(int i) const {
    double result = b;
    for (size_t j = 0; j < X.size(); j++) {
        if (alpha[j] > 0) {
            result += alpha[j] * y[j] * kernel(X[j], X[i]);
        }
    }
    return result;
}

double SVM::calcEi(int i) const {
    return calcFx(i) - y[i];
}

void SVM::fit(const std::vector<std::vector<double>>& X,
              const std::vector<int>& y) {

    this->X = X;
    this->y = y;
    int n = X.size();
    alpha.assign(n, 0);

    int iter = 0;

    while (iter < max_iter) {
        bool alpha_changed = false;

        for (int i = 0; i < n; i++) {
            double Ei = calcEi(i);

            // 检查 KKT 条件，若不满足则优化
            if ((y[i] * Ei < -tol && alpha[i] < C) ||
                (y[i] * Ei > tol && alpha[i] > 0)) {

                // 随机选择 j != i
                int j = rand() % n;
                while (j == i) j = rand() % n;

                double Ej = calcEi(j);

                double alpha_i_old = alpha[i];
                double alpha_j_old = alpha[j];

                // 计算 L, H
                double L, H;
                if (y[i] != y[j]) {
                    L = std::max(0.0, alpha[j] - alpha[i]);
                    H = std::min((double)C, C + alpha[j] - alpha[i]);
                } else {
                    L = std::max(0.0, alpha[j] + alpha[i] - C);
                    H = std::min((double)C, alpha[j] + alpha[i]);
                }
                if (L == H) continue;

                // 计算 eta
                double eta = 2 * kernel(X[i], X[j])
                           - kernel(X[i], X[i])
                           - kernel(X[j], X[j]);

                if (eta >= 0) continue;

                // 更新 α_j
                alpha[j] -= y[j] * (Ei - Ej) / eta;

                // 剪裁
                if (alpha[j] > H) alpha[j] = H;
                else if (alpha[j] < L) alpha[j] = L;

                if (fabs(alpha[j] - alpha_j_old) < 1e-5) continue;

                // 更新 α_i
                alpha[i] += y[i] * y[j] * (alpha_j_old - alpha[j]);

                // 更新 b
                double b1 = b - Ei
                    - y[i] * (alpha[i] - alpha_i_old) * kernel(X[i], X[i])
                    - y[j] * (alpha[j] - alpha_j_old) * kernel(X[i], X[j]);

                double b2 = b - Ej
                    - y[i] * (alpha[i] - alpha_i_old) * kernel(X[i], X[j])
                    - y[j] * (alpha[j] - alpha_j_old) * 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;

                alpha_changed = true;
            }
        }

        if (!alpha_changed) iter++;
        else iter = 0;
    }

    std::cout << "SVM 训练完成！" << std::endl;
}

int SVM::predict(const std::vector<double>& x) const {
    double result = b;
    for (size_t i = 0; i < X.size(); i++) {
        if (alpha[i] > 0) {
            result += alpha[i] * y[i] * kernel(X[i], x);
        }
    }
    return (result >= 0) ? 1 : -1;
}

/******************************************************
 * 文件：main.cpp
 * 功能：demo 示例
 ******************************************************/
#include "svm.h"
#include <iostream>

int main() {
    // 简单二分类问题
    std::vector<std::vector<double>> X = {
        {2, 3}, {3, 3}, {2, 2},
        {7, 8}, {8, 8}, {7, 7}
    };

    std::vector<int> y = {1, 1, 1, -1, -1, -1};

    SVM svm(1.0, 1e-3, 1000);

    // 设置 RBF 核函数
    double gamma = 0.5;
    svm.setKernel([gamma](const std::vector<double>& a,
                          const std::vector<double>& b) {
        double sum = 0;
        for (size_t i = 0; i < a.size(); i++)
            sum += (a[i] - b[i]) * (a[i] - b[i]);
        return exp(-gamma * sum);
    });

    svm.fit(X, y);

    std::vector<double> test = {3, 2};
    std::cout << "预测结果：" << svm.predict(test) << std::endl;

    return 0;
}