C++实现支持向量机(SVM)从入门到实战：原理详解与代码实现

1次阅读

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

支持向量机 (SVM) 是机器学习中经典的监督学习算法，特别适合解决中小规模数据集的分类问题。它的核心思想是在特征空间中找到一个最优超平面，使得不同类别的数据点能够被最大间隔分开。SVM 在文本分类、图像识别、生物信息学等领域都有广泛应用。

相比 Python 生态中成熟的 scikit-learn 库，用 C ++ 实现 SVM 可以更好地理解算法细节，并且在性能敏感场景中获得更高效的计算。本文将带您从零开始，用现代 C ++ 实现一个完整的 SVM 分类器。

SVM 的核心是寻找一个超平面 wx + b = 0，使得两类样本到这个超平面的最小距离 (即间隔) 最大化。这个优化问题可以表示为：

$$
\min_{w,b} \frac{1}{2}||w||^2 \quad \text{s.t.} \quad y_i(wx_i + b) \geq 1, \forall i
$$

在解这个优化问题时，只有少数靠近决策边界的样本点 (称为支持向量) 会影响最终结果。这些支持向量满足 y_i(wx_i + b) = 1。

对于非线性可分问题，SVM 通过核函数将数据映射到高维空间，使其在高维空间中线性可分。常用的核函数包括：

线性核：$K(x_i, x_j) = x_i^T x_j$
RBF 核：$K(x_i, x_j) = \exp(-\gamma ||x_i – x_j||^2)$

我们使用 Eigen 库来处理矩阵运算，这是现代 C ++ 中高效的线性代数库。

#include <Eigen/Dense>
#include <vector>

struct SVM {
    Eigen::VectorXd alphas;  // 拉格朗日乘子
    Eigen::VectorXd w;       // 权重向量(仅线性核)
    double b = 0;            // 偏置项
    std::vector<Eigen::VectorXd> support_vectors; // 支持向量
    std::vector<double> support_vector_labels;    // 支持向量标签
    std::vector<double> support_vector_alphas;    // 支持向量对应的 alpha
};

序列最小优化 (SMO) 是求解 SVM 对偶问题的高效算法。其核心思想是每次选择两个变量进行优化，固定其他变量。

void SMO(const Eigen::MatrixXd& X, const Eigen::VectorXd& y, SVM& model, 
         double C = 1.0, double tol = 1e-3, int max_passes = 5) {
    // 初始化
    int m = X.rows();
    Eigen::VectorXd alphas = Eigen::VectorXd::Zero(m);
    double b = 0;

    int passes = 0;
    while (passes < max_passes) {
        // 实现 SMO 的主循环
        // ...
    }

    // 保存模型参数
    model.alphas = alphas;
    model.b = b;
    // 提取支持向量...
}

下面是一个简化但完整的 SVM 实现框架：

#include <iostream>
#include <Eigen/Dense>
#include <cmath>
#include <vector>

// 核函数接口
class Kernel {
public:
    virtual double compute(const Eigen::VectorXd& x1, const Eigen::VectorXd& x2) const = 0;
};

// 线性核
class LinearKernel : public Kernel {
public:
    double compute(const Eigen::VectorXd& x1, const Eigen::VectorXd& x2) const override {return x1.dot(x2);
    }
};

// RBF 核
class RBFKernel : public Kernel {
public:
    RBFKernel(double gamma) : gamma(gamma) {}

    double compute(const Eigen::VectorXd& x1, const Eigen::VectorXd& x2) const override {return exp(-gamma * (x1 - x2).squaredNorm());
    }

private:
    double gamma;
};

// SVM 类实现
class SVM {
public:
    void train(const Eigen::MatrixXd& X, const Eigen::VectorXd& y, const Kernel* kernel, 
               double C = 1.0, double tol = 1e-3, int max_passes = 5);

    double predict(const Eigen::VectorXd& x);

private:
    // 成员变量和方法实现...
};

// 训练函数实现
void SVM::train(const Eigen::MatrixXd& X, const Eigen::VectorXd& y, const Kernel* kernel, 
                double C, double tol, int max_passes) {
    // SMO 算法实现
    // ...
}

// 预测函数
double SVM::predict(const Eigen::VectorXd& x) {
    // 使用支持向量进行预测
    // ...
    return result;
}

int main() {
    // 示例数据
    Eigen::MatrixXd X(4, 2);
    X << 1, 1,
         2, 2,
         1, 2,
         2, 1;
    Eigen::VectorXd y(4);
    y << 1, 1, -1, -1;

    // 训练 SVM
    RBFKernel rbf_kernel(0.1);
    SVM svm;
    svm.train(X, y, &rbf_kernel);

    // 测试预测
    Eigen::VectorXd test(2);
    test << 1.5, 1.5;
    std::cout << "Prediction:" << svm.predict(test) << std::endl;

    return 0;
}