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

1次阅读

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

支持向量机 (Support Vector Machine, SVM) 是机器学习中一种强大的监督学习算法，尤其在二分类问题上表现突出。它的核心思想是通过寻找最优超平面来最大化分类间隔，这使得 SVM 在小样本、高维数据中表现出色。SVM 广泛应用于文本分类、图像识别、生物信息学等领域。

SVM 的核心目标是找到一个超平面，使得两类数据点到这个超平面的最小距离（即间隔）最大。这个最优超平面可以表示为：

w^T x + b = 0

其中 w 是法向量，b 是偏置项。对于线性可分的数据，SVM 的优化问题可以表示为：

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

支持向量是距离超平面最近的那些数据点，它们决定了超平面的位置。在实际应用中，只有这些支持向量对分类器产生影响，这使得 SVM 具有很好的稀疏性。

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

线性核：K(x_i,x_j) = x_i^T x_j
RBF 核（高斯核）：K(x_i,x_j) = exp(-γ||x_i - x_j||^2)

我们使用 Eigen 库来处理矩阵运算，这是现代 C ++ 中高效的线性代数库。首先定义一些基本数据结构：

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

using namespace Eigen;

struct DataPoint {
    VectorXd features;
    int label;
};

class SVM {
private:
    std::vector<DataPoint> supportVectors;
    VectorXd weights;
    double bias;
    double C; // 惩罚参数

    // 核函数相关
    typedef double (*KernelFunc)(const VectorXd&, const VectorXd&);
    KernelFunc kernel;

public:
    SVM(double c = 1.0) : C(c) {}

    void train(const std::vector<DataPoint>& trainingData);
    int predict(const VectorXd& features) const;

    // 核函数
    static double linearKernel(const VectorXd& x1, const VectorXd& x2);
    static double rbfKernel(const VectorXd& x1, const VectorXd& x2, double gamma = 0.1);
};

序列最小优化 (Sequential Minimal Optimization, SMO) 算法是求解 SVM 对偶问题的高效算法。其核心思想是每次只优化两个拉格朗日乘子，直到收敛。

void SVM::train(const std::vector<DataPoint>& trainingData) {
    // 初始化参数
    int m = trainingData.size();
    VectorXd alpha = VectorXd::Zero(m);

    // SMO 主循环
    bool changed = true;
    while(changed) {
        changed = false;

        for(int i = 0; i < m; ++i) {double Ei = predict(trainingData[i].features) - trainingData[i].label;

            if((trainingData[i].label * Ei < -0.001 && alpha[i] < C) || 
               (trainingData[i].label * Ei > 0.001 && alpha[i] > 0)) {int j = selectSecondAlpha(i, m);
                double Ej = predict(trainingData[j].features) - trainingData[j].label;

                // 保存旧 alpha 值
                double alphaIold = alpha[i];
                double alphaJold = alpha[j];

                // 计算边界
                double L, H;
                if(trainingData[i].label != trainingData[j].label) {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;

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

                if(eta >= 0) continue;

                // 更新 alpha[j]
                alpha[j] -= trainingData[j].label * (Ei - Ej) / eta;
                alpha[j] = std::min(H, std::max(L, alpha[j]));

                if(abs(alpha[j] - alphaJold) < 0.00001) continue;

                // 更新 alpha[i]
                alpha[i] += trainingData[i].label * trainingData[j].label * (alphaJold - alpha[j]);

                // 更新 bias
                double b1 = bias - Ei - trainingData[i].label * (alpha[i] - alphaIold) * kernel(trainingData[i].features, trainingData[i].features)
                           - trainingData[j].label * (alpha[j] - alphaJold) * kernel(trainingData[i].features, trainingData[j].features);

                double b2 = bias - Ej - trainingData[i].label * (alpha[i] - alphaIold) * kernel(trainingData[i].features, trainingData[j].features)
                           - trainingData[j].label * (alpha[j] - alphaJold) * kernel(trainingData[j].features, trainingData[j].features);

                if(0 < alpha[i] && alpha[i] < C) bias = b1;
                else if(0 < alpha[j] && alpha[j] < C) bias = b2;
                else bias = (b1 + b2) / 2.0;

                changed = true;
            }
        }
    }

    // 保存支持向量
    for(int i = 0; i < m; ++i) {if(alpha[i] > 0) {supportVectors.push_back(trainingData[i]);
        }
    }

    // 计算权重向量（仅对线性核有效）if(kernel == linearKernel) {weights = VectorXd::Zero(trainingData[0].features.size());
        for(int i = 0; i < m; ++i) {weights += alpha[i] * trainingData[i].label * trainingData[i].features;
        }
    }
}

double SVM::linearKernel(const VectorXd& x1, const VectorXd& x2) {return x1.dot(x2);
}

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

int SVM::predict(const VectorXd& features) const {
    double result = 0.0;

    if(kernel == linearKernel) {result = weights.dot(features) + bias;
    } else {
        // 使用支持向量进行预测
        for(const auto& sv : supportVectors) {result += sv.label * kernel(sv.features, features);
        }
        result += bias;
    }

    return result > 0 ? 1 : -1;
}

SMO 算法的时间复杂度主要取决于：
1. 核函数的计算复杂度
2. 支持向量的数量
3. 迭代收敛速度

对于线性核，时间复杂度约为 O(n²)，其中 n 是特征维度。对于非线性核，时间复杂度可能高达 O(n³)。

使用稀疏矩阵存储稀疏数据
采用缓存机制存储常用核函数计算结果
定期清理非支持向量的数据

使用 Eigen 库进行高效的矩阵运算
实现核函数缓存机制
采用并行计算加速核函数计算

数据标准化：SVM 对特征的尺度敏感，务必对数据进行标准化处理
参数选择：C 参数和核函数参数的选择对性能影响巨大，建议使用交叉验证
核函数选择：线性核适用于线性可分数据，RBF 核适用于非线性问题但计算开销大
数值稳定性：注意处理核函数计算中的数值稳定性问题

多分类 SVM：通过一对多或一对一策略扩展二分类 SVM
在线学习 SVM：实现增量式学习算法，适应流式数据
结构化 SVM：处理结构化输出问题
大规模 SVM：研究适用于大数据的近似算法

如何修改代码以支持多分类问题？
当数据量非常大时，有哪些策略可以加速 SVM 训练？
除了线性核和 RBF 核，还有哪些核函数适用于特定类型的数据？

本文详细介绍了如何在 C ++ 中实现支持向量机，从基本原理到完整的代码实现。我们使用 Eigen 库高效处理矩阵运算，实现了 SMO 算法和两种常见的核函数。对于机器学习初学者来说，理解 SVM 的实现细节有助于更好地应用和调优这一强大算法。在实践中，建议从线性核开始，逐步尝试更复杂的核函数，并通过交叉验证选择最佳参数。

完整的实现代码和示例数据可以在我的 GitHub 仓库中找到。希望这篇文章能帮助你理解 SVM 的工作原理，并启发你探索更多机器学习算法的实现细节。

正文完