引言
支持向量机（Support Vector Machine，SVM）是机器学习领域最经典、最强大的监督学习算法之一。由Vapnik等人于1995年提出，SVM基于结构风险最小化原则，通过寻找最优超平面来最大化分类间隔，从而获得出色的泛化能力。SVM不仅能处理线性可分问题，通过核技巧（Kernel Trick）还能高效解决非线性分类问题。本文将用Java从零实现SVM的核心机制，包括软间隔分类、核函数映射以及SMO（Sequential Minimal Optimization）优化算法，并通过经典的鸢尾花数据集验证其分类效果。
算法原理
最大间隔分类器
给定训练数据集 {(x₁, y₁), (x₂, y₂), ..., (xₙ, yₙ)}，其中 xᵢ ∈ Rᵈ，yᵢ ∈ {-1, +1}。SVM的目标是找到一个超平面 w·x + b = 0，使得：
- 正确分类所有训练样本：
yᵢ(w·xᵢ + b) ≥ 1 - 分类间隔最大化：
max 2/||w||，等价于min ½||w||²
这是一个带不等式约束的二次规划问题。
拉格朗日对偶问题
通过拉格朗日乘子法，原始问题转化为对偶问题：
max Σαᵢ - ½ΣΣαᵢαⱼyᵢyⱼK(xᵢ, xⱼ)
s.t. Σαᵢyᵢ = 0, αᵢ ≥ 0
其中 αᵢ 是拉格朗日乘子，K(xᵢ, xⱼ) 是核函数。
核函数技巧
当数据在低维空间线性不可分时，核函数将数据隐式映射到高维特征空间：
- 线性核：
K(u, v) = u·v - 多项式核：
K(u, v) = (γu·v + r)^d - RBF高斯核：
K(u, v) = exp(-γ||u-v||²)
软间隔与松弛变量
对于非线性可分数据，引入松弛变量 ξᵢ 和惩罚参数 C，允许部分样本违反约束：
min ½||w||² + CΣξᵢ
s.t. yᵢ(w·xᵢ + b) ≥ 1 - ξᵢ, ξᵢ ≥ 0
核心Java实现
SVM模型类
import java.util.*;
/**
* SVM支持向量机实现
* 基于SMO优化算法，支持线性核与RBF核
*/
public class SVM {
private final double C; // 惩罚参数
private final double tol; // 收敛容差
private final int maxIter; // 最大迭代次数
private final Kernel kernel; // 核函数
private double[] alpha; // 拉格朗日乘子
private double b; // 偏置项
private double[][] X; // 训练数据
private int[] y; // 标签
private double[] E; // 误差缓存
private int m; // 样本数量
public SVM(double C, double tol, int maxIter, Kernel kernel) {
this.C = C;
this.tol = tol;
this.maxIter = maxIter;
this.kernel = kernel;
}
/**
* 训练SVM模型
* @param X 特征矩阵，每行一个样本
* @param y 标签数组，取值为-1或+1
*/
public void fit(double[][] X, int[] y) {
this.X = X;
this.y = y;
this.m = X.length;
this.alpha = new double[m];
this.b = 0;
this.E = new double[m];
// 初始化误差缓存
for (int i = 0; i < m; i++) {
E[i] = predictRaw(X[i]) - y[i];
}
int iter = 0;
int numChanged = 0;
boolean examineAll = true;
// SMO主循环
while (iter < maxIter && (numChanged > 0 || examineAll)) {
numChanged = 0;
if (examineAll) {
// 遍历所有样本
for (int i = 0; i < m; i++) {
numChanged += examineExample(i);
}
} else {
// 仅遍历非边界样本（0 < alpha < C）
for (int i = 0; i < m; i++) {
if (alpha[i] > 0 && alpha[i] < C) {
numChanged += examineExample(i);
}
}
}
iter++;
if (examineAll) {
examineAll = false;
} else if (numChanged == 0) {
examineAll = true;
}
}
System.out.println("SMO收敛，迭代次数: " + iter);
}
/**
* SMO核心：选择两个拉格朗日乘子进行优化
*/
private int examineExample(int i2) {
int y2 = y[i2];
double alpha2 = alpha[i2];
double E2 = E[i2];
double r2 = E2 * y2;
// 检查KKT条件是否违反
boolean violateKKT = (r2 < -tol && alpha2 < C) || (r2 > tol && alpha2 > 0);
if (!violateKKT) return 0;
// 选择第二个乘子i1
// 策略1：选择|E1 - E2|最大的样本
int i1 = -1;
double maxDeltaE = 0;
for (int i = 0; i < m; i++) {
if (alpha[i] > 0 && alpha[i] < C) {
double deltaE = Math.abs(E[i] - E2);
if (deltaE > maxDeltaE) {
maxDeltaE = deltaE;
i1 = i;
}
}
}
if (i1 >= 0 && takeStep(i1, i2)) return 1;
// 策略2：遍历所有非边界样本
for (int i = 0; i < m; i++) {
if (alpha[i] > 0 && alpha[i] < C) {
if (takeStep(i, i2)) return 1;
}
}
// 策略3：遍历所有样本
for (int i = 0; i < m; i++) {
if (takeStep(i, i2)) return 1;
}
return 0;
}
/**
* 优化两个拉格朗日乘子
*/
private boolean takeStep(int i1, int i2) {
if (i1 == i2) return false;
double alpha1 = alpha[i1];
double alpha2 = alpha[i2];
int y1 = y[i1];
int y2 = y[i2];
double E1 = E[i1];
double E2 = E[i2];
// 计算边界L和H
double L, H;
if (y1 != y2) {
L = Math.max(0, alpha2 - alpha1);
H = Math.min(C, C + alpha2 - alpha1);
} else {
L = Math.max(0, alpha1 + alpha2 - C);
H = Math.min(C, alpha1 + alpha2);
}
if (L == H) return false;
// 计算核函数值
double K11 = kernel.compute(X[i1], X[i1]);
double K12 = kernel.compute(X[i1], X[i2]);
double K22 = kernel.compute(X[i2], X[i2]);
double eta = 2 * K12 - K11 - K22;
double alpha2New;
if (eta >= 0) {
// 目标函数开口向下，检查边界
double f1 = y1 * (E1 + b) - alpha1 * K11 - y1 * y2 * alpha2 * K12;
double f2 = y2 * (E2 + b) - y1 * y2 * alpha1 * K12 - alpha2 * K22;
double L1 = alpha1 + y1 * y2 * (alpha2 - L);
double H1 = alpha1 + y1 * y2 * (alpha2 - H);
double psiL = L1 * f1 + L * f2 + 0.5 * L1 * L1 * K11 + 0.5 * L * L * K22 + y1 * y2 * L * L1 * K12;
double psiH = H1 * f1 + H * f2 + 0.5 * H1 * H1 * K11 + 0.5 * H * H * K22 + y1 * y2 * H * H1 * K12;
alpha2New = (psiL < psiH - tol) ? L : ((psiL > psiH + tol) ? H : alpha2);
} else {
// 无约束最优解
alpha2New = alpha2 - y2 * (E1 - E2) / eta;
alpha2New = Math.max(L, Math.min(H, alpha2New));
}
if (Math.abs(alpha2New - alpha2) < tol * (alpha2New + alpha2 + tol)) {
return false;
}
double alpha1New = alpha1 + y1 * y2 * (alpha2 - alpha2New);
// 更新偏置b
double b1 = b - E1 - y1 * (alpha1New - alpha1) * K11 - y2 * (alpha2New - alpha2) * K12;
double b2 = b - E2 - y1 * (alpha1New - alpha1) * K12 - y2 * (alpha2New - alpha2) * K22;
if (alpha1New > 0 && alpha1New < C) {
b = b1;
} else if (alpha2New > 0 && alpha2New < C) {
b = b2;
} else {
b = (b1 + b2) / 2;
}
// 更新alpha
alpha[i1] = alpha1New;
alpha[i2] = alpha2New;
// 更新误差缓存
for (int i = 0; i < m; i++) {
E[i] = predictRaw(X[i]) - y[i];
}
return true;
}
/**
* 预测单个样本的原始输出值（未取符号）
*/
private double predictRaw(double[] x) {
double sum = 0;
for (int i = 0; i < m; i++) {
if (alpha[i] > 0) {
sum += alpha[i] * y[i] * kernel.compute(X[i], x);
}
}
return sum + b;
}
/**
* 预测样本类别
*/
public int predict(double[] x) {
return predictRaw(x) >= 0 ? 1 : -1;
}
/**
* 批量预测
*/
public int[] predict(double[][] X_test) {
int[] predictions = new int[X_test.length];
for (int i = 0; i < X_test.length; i++) {
predictions[i] = predict(X_test[i]);
}
return predictions;
}
/**
* 计算分类准确率
*/
public double score(double[][] X_test, int[] y_test) {
int[] preds = predict(X_test);
int correct = 0;
for (int i = 0; i < y_test.length; i++) {
if (preds[i] == y_test[i]) correct++;
}
return (double) correct / y_test.length;
}
/**
* 获取支持向量数量
*/
public int getSupportVectorCount() {
int count = 0;
for (double a : alpha) {
if (a > 1e-5) count++;
}
return count;
}
// ==================== 核函数接口与实现 ====================
public interface Kernel {
double compute(double[] x1, double[] x2);
}
/**
* 线性核函数
*/
public static class LinearKernel implements Kernel {
@Override
public double compute(double[] x1, double[] x2) {
double sum = 0;
for (int i = 0; i < x1.length; i++) {
sum += x1[i] * x2[i];
}
return sum;
}
}
/**
* RBF高斯核函数
*/
public static class RBFKernel implements Kernel {
private final double gamma;
public RBFKernel(double gamma) {
this.gamma = gamma;
}
@Override
public double compute(double[] x1, double[] x2) {
double sum = 0;
for (int i = 0; i < x1.length; i++) {
double diff = x1[i] - x2[i];
sum += diff * diff;
}
return Math.exp(-gamma * sum);
}
}
// ==================== 测试主程序 ====================
public static void main(String[] args) {
// 生成二维测试数据：两个同心圆（非线性可分）
int n = 200;
double[][] X = new double[n][];
int[] y = new int[n];
Random rand = new Random(42);
// 内圈：正类
for (int i = 0; i < n / 2; i++) {
double angle = 2 * Math.PI * rand.nextDouble();
double r = 1 + 0.3 * rand.nextGaussian();
X[i] = new double[]{r * Math.cos(angle), r * Math.sin(angle)};
y[i] = 1;
}
// 外圈：负类
for (int i = n / 2; i < n; i++) {
double angle = 2 * Math.PI * rand.nextDouble();
double r = 3 + 0.3 * rand.nextGaussian();
X[i] = new double[]{r * Math.cos(angle), r * Math.sin(angle)};
y[i] = -1;
}
// 划分训练集和测试集
int trainSize = (int)(n * 0.8);
double[][] X_train = Arrays.copyOfRange(X, 0, trainSize);
int[] y_train = Arrays.copyOfRange(y, 0, trainSize);
double[][] X_test = Arrays.copyOfRange(X, trainSize, n);
int[] y_test = Arrays.copyOfRange(y, trainSize, n);
// 线性核SVM
System.out.println("=== 线性核SVM ===");
SVM svmLinear = new SVM(1.0, 1e-3, 1000, new LinearKernel());
svmLinear.fit(X_train, y_train);
double linearAcc = svmLinear.score(X_test, y_test);
System.out.println("测试准确率: " + String.format("%.2f%%", linearAcc * 100));
System.out.println("支持向量数: " + svmLinear.getSupportVectorCount());
// RBF核SVM
System.out.println("\n=== RBF核SVM ===");
SVM svmRbf = new SVM(1.0, 1e-3, 1000, new RBFKernel(0.5));
svmRbf.fit(X_train, y_train);
double rbfAcc = svmRbf.score(X_test, y_test);
System.out.println("测试准确率: " + String.format("%.2f%%", rbfAcc * 100));
System.out.println("支持向量数: " + svmRbf.getSupportVectorCount());
}
}
鸢尾花数据集实战
import java.io.*;
import java.util.*;
/**
* 鸢尾花数据集分类实战
* 使用SVM对鸢尾花进行二分类（Setosa vs Versicolor）
*/
public class IrisSVMClassifier {
public static void main(String[] args) throws IOException {
// 鸢尾花数据集（简化版，取前两个特征用于可视化）
// 类别: 0=Setosa, 1=Versicolor, 2=Virginica
// 这里将Setosa(+1)与其他(-1)区分
List<double[]> dataList = new ArrayList<>();
List<Integer> labelList = new ArrayList<>();
// 使用内置的简化鸢尾花数据
double[][] irisData = loadIrisData();
int[] irisLabels = loadIrisLabels();
// 取前两个类别进行二分类，使用前两个特征
for (int i = 0; i < irisData.length; i++) {
if (irisLabels[i] < 2) { // 只取Setosa和Versicolor
dataList.add(new double[]{irisData[i][0], irisData[i][1]});
labelList.add(irisLabels[i] == 0 ? 1 : -1);
}
}
double[][] X = dataList.toArray(new double[0][]);
int[] y = labelList.stream().mapToInt(Integer::intValue).toArray();
// 打乱数据
shuffleData(X, y);
// 划分训练集(70%)和测试集(30%)
int trainSize = (int)(X.length * 0.7);
double[][] X_train = Arrays.copyOfRange(X, 0, trainSize);
int[] y_train = Arrays.copyOfRange(y, 0, trainSize);
double[][] X_test = Arrays.copyOfRange(X, trainSize, X.length);
int[] y_test = Arrays.copyOfRange(y, trainSize, X.length);
System.out.println("训练样本数: " + X_train.length);
System.out.println("测试样本数: " + X_test.length);
// 训练RBF核SVM
SVM svm = new SVM(10.0, 1e-4, 2000, new SVM.RBFKernel(0.1));
svm.fit(X_train, y_train);
// 评估
double accuracy = svm.score(X_test, y_test);
System.out.println("\n测试准确率: " + String.format("%.2f%%", accuracy * 100));
System.out.println("支持向量数量: " + svm.getSupportVectorCount());
// 打印预测结果
int[] predictions = svm.predict(X_test);
System.out.println("\n预测结果 vs 真实标签:");
for (int i = 0; i < Math.min(10, X_test.length); i++) {
System.out.println("样本" + (i+1) + ": 预测=" + predictions[i] + ", 真实=" + y_test[i]
+ ", 特征=[" + String.format("%.1f", X_test[i][0]) + ", "
+ String.format("%.1f", X_test[i][1]) + "]");
}
}
private static void shuffleData(double[][] X, int[] y) {
Random rand = new Random(42);
for (int i = X.length - 1; i > 0; i--) {
int j = rand.nextInt(i + 1);
double[] tmpX = X[i]; X[i] = X[j]; X[j] = tmpX;
int tmpY = y[i]; y[i] = y[j]; y[j] = tmpY;
}
}
// 简化的鸢尾花数据（前100条，取前2个特征）
private static double[][] loadIrisData() {
return new double[][]{
{5.1,3.5},{4.9,3.0},{4.7,3.2},{4.6,3.1},{5.0,3.6},{5.4,3.9},{4.6,3.4},
{5.0,3.4},{4.4,2.9},{4.9,3.1},{5.4,3.7},{4.8,3.4},{4.8,3.0},{4.3,3.0},
{5.8,4.0},{5.7,4.4},{5.4,3.9},{5.1,3.5},{5.7,3.8},{5.1,3.8},{5.4,3.4},
{5.1,3.7},{4.6,3.6},{5.1,3.3},{4.8,3.4},{5.0,3.0},{5.0,3.4},{5.2,3.5},
{5.2,3.4},{4.7,3.2},{4.8,3.1},{5.4,3.4},{5.2,4.1},{5.5,4.2},{4.9,3.1},
{5.0,3.2},{5.5,3.5},{4.9,3.6},{4.4,3.0},{5.1,3.4},{5.0,3.5},{4.5,2.3},
{4.4,3.2},{5.0,3.5},{5.1,3.8},{4.8,3.0},{5.1,3.8},{4.6,3.2},{5.3,3.7},
{5.0,3.3},{7.0,3.2},{6.4,3.2},{6.9,3.1},{5.5,2.3},{6.5,2.8},{5.7,2.8},
{6.3,3.3},{4.9,2.4},{6.6,2.9},{5.2,2.7},{5.0,2.0},{5.9,3.0},{6.0,2.2},
{6.1,2.9},{5.6,2.9},{6.7,3.1},{5.6,3.0},{5.8,2.7},{6.2,2.2},{5.6,2.5},
{5.9,3.2},{6.1,2.8},{6.3,2.5},{6.1,2.8},{6.4,2.9},{6.6,3.0},{6.8,2.8},
{6.7,3.0},{6.0,2.9},{5.7,2.6},{5.5,2.4},{5.5,2.4},{5.8,2.7},{6.0,2.7},
{5.4,3.0},{6.0,3.4},{6.7,3.1},{6.3,2.3},{5.6,3.0},{5.5,2.5},{5.5,2.6},
{6.1,3.0},{5.8,2.6},{5.0,2.3},{5.6,2.7},{5.7,3.0},{5.7,2.9},{6.2,2.9},
{5.1,2.5},{5.7,2.8}
};
}
private static int[] loadIrisLabels() {
int[] labels = new int[100];
for (int i = 0; i < 50; i++) labels[i] = 0; // Setosa
for (int i = 50; i < 100; i++) labels[i] = 1; // Versicolor
return labels;
}
}
复杂度分析
训练时间复杂度
SMO算法的时间复杂度主要取决于核矩阵的计算和迭代收敛速度：
- 每次迭代：需要计算两个样本与其他所有样本的核函数值，单次takeStep为 O(m)，其中 m 是样本数量。
- 总体训练：SMO通常需要 O(m²) 到 O(m³) 次迭代才能收敛。对于大规模数据集，SMO的时间复杂度约为 O(km²)，其中 k 是平均迭代次数。
- 使用核缓存：若缓存核矩阵，可将每次核计算降为O(1)查表，但空间复杂度升至 O(m²)。
预测时间复杂度
预测一个新样本时，需要计算该样本与所有支持向量的核函数值：
- 预测：O(s·d)，其中 s 是支持向量数量，d 是特征维度。
- 支持向量通常只占总样本的 10%-50%，这大大加快了预测速度。
空间复杂度
- 模型存储：O(s·d)，需要保存所有支持向量和对应的alpha值。
- 训练过程：若使用核缓存，需要 O(m²) 空间存储核矩阵。
SVM的优缺点与适用场景
优点
- 泛化能力强：基于结构风险最小化，通过最大化间隔避免过拟合。
- 核技巧强大：通过核函数隐式映射到高维空间，解决非线性问题。
- 维数无关性：仅依赖支持向量，在高维空间中仍表现良好。
- 解的稀疏性：最终模型仅由少量支持向量决定，预测效率高。
缺点
- 训练速度慢：对于大规模数据集（m > 10000），SMO收敛较慢。
- 核函数选择困难：不同核函数和超参数（C, γ）对结果影响巨大，需要交叉验证调参。
- 多分类不直接：原生SVM是二分类器，多分类需要组合多个SVM（如One-vs-One、One-vs-Rest）。
- 缺失值敏感：SVM对缺失值和异常值较为敏感。
最佳适用场景
- 中小规模数据集：样本数在1000-10000之间效果最佳。
- 高维特征：如文本分类（TF-IDF特征维度可达数万）。
- 边界清晰的分类问题：如人脸识别、手写数字识别。
- 需要强泛化能力的场景：如医学诊断、金融风险评估。
总结
SVM是机器学习领域的基石算法，其最大间隔思想和核技巧至今仍是解决分类问题的强大武器。本文通过Java从零实现了完整的SVM训练流程，包括SMO优化算法、线性核与RBF核，并通过同心圆和鸢尾花数据集验证了非线性分类能力。理解SVM的拉格朗日对偶、KKT条件和SMO优化，不仅能掌握一个经典算法，更能深入理解凸优化在机器学习中的核心作用。
