2019-03-18

2019 年 3 月

第 34 卷，第 3 期

[C#]

使用 C# 的支持向量机

支持向量机 (SVM) 是可使用数据进行预测的软件系统。SVM 的原始类型旨在执行二元分类，例如根据身高、体重和年收入来预测是男性还是女性。此外，SVM 的变体还可以执行多元分类（预测三个或多个类中的一个）和回归（预测数值）。

本文介绍了仅使用原始 C#（而未使用任何外部库）实现的 SVM 的完整有效示例。了解本文所述观点的一个好方法是，查看图 1 中所示的演示程序。

图 1：SVM 演示程序实际效果

首先，演示程序创建 8 个虚拟定型数据项。每项都有三个预测因子值，后跟要预测的类（编码为 -1 或 +1）。虚拟数据并不代表实际问题，所以预测因子值没有任何特定意义。在实际 SVM 问题中，请务必规范化预测因子值，具体方法通常是应用最小值-最大值规范化，让所有值都介于 0.0 和 1.0 之间。

演示程序创建使用多项式内核函数的 SVM 分类器。（我很快就会介绍内核函数。）定型 SVM 模型生成了三个支持向量：(4, 5, 7)、(7, 4, 2) 和 (9, 7, 5)。这些是定型数据项 [0]、[1] 和 [4]。每个支持向量都有关联的权重值：(-0.000098, -0.000162, 0.000260)。此外，SVM 模型还有一个偏差值；对于演示数据，此值为 -2.505727。

支持向量、权重和偏差定义了定型的 SVM 模型。演示程序使用此模型分别为 8 个定型项生成预测类值。负决策值对应于预测类标签 -1，正决策值对应于预测类标签 +1。因此，已定型模型正确地预测所有 8 个定型项。这不足为奇，因为这个问题如此简单。

最后，演示程序为预测因子值为 (3, 5, 7) 且之前没有见过的新项预测类。计算出的决策值为 -1.274，所以预测类标签为 -1。本文稍后将会介绍决策值的计算。

若要更好地理解本文，需要拥有中等或更高水平的 C# 编程技能，但无需对 SVM 有任何了解。演示程序使用 C# 进行编码，尽管复杂，但如果愿意，你应该能够将它重构为其他语言（如 Java 或 Python）。

虽然演示程序的代码过长而无法在本文中全部展示，但随附的文件下载中提供了完整源代码。为了尽可能地让主要思想清晰明确，已删除所有常见错误检查。

程序的整体结构

演示程序的结构如图 2 所示。所有控制逻辑都包含在一个 Main 方法中。演示程序定义的类 SupportVectorMachine 将所有成员字段声明为公共字段，这样就能以编程方式更轻松地检查它们。

虽然我使用 Visual Studio 2017 创建演示程序，但并不非常依赖 .NET Framework，所以任何版本的 Visual Studio 都可以使用。我新建了 C# 控制台应用程序，并将它命名为 SVM_CSharp。当模板代码在编辑器窗口中加载后，我删除了所有不需要的 using 语句，并添加了对 Collections.Generic 程序集的引用。在“解决方案资源管理器”窗口中，我右键单击了文件 Program.cs，将它重命名为 SVM_Program.cs，并允许 Visual Studio 自动重命名类 Program。

图 2 演示程序结构

using System;
using System.Collections.Generic;
namespace SVM_CSharp
{
  class SVM_Program
  {
    static void Main(string[] args)
    {
      // Set up training data
      // Create SVM object, set parameters
      // Train the SVM
      // Display SVM properties
      // Use trained SVM to make a prediction
    }
  }
  public class SupportVectorMachine
  {
    // All member fields are declared public
    public SupportVectorMachine(string kernelType,
      int seed) . .
    public double PolyKernel(double[] v1, double[] v2) . .
    public double ComputeDecision(double[] input) . .
    public int Train(double[][] X_matrix,
      int[] y_vector, int maxIter) . .
    public double Accuracy(double[][] X_matrix,
      int[] y_vector) . .
    private bool TakeStep(int i1, int i2,
      double[][] X_matrix, int[] y_vector) . .
    private int ExamineExample(int i2, double[][] X_matrix,
      int[] y_vector) . .
    private double ComputeAll(double[] vector,
      double[][] X_matrix, int[] y_vector) . .
  }
}

使用 SVM

演示程序创建 8 个硬编码的定型项：

double[][] train_X = new double[8][] {
  new double[] { 4,5,7 },
  ...
  new double[] { 8,9,10 }  };
int[] train_y = new int[8]{ -1, -1, -1, -1, 1, 1, 1, 1 };

在非演示程序方案中，应规范化预测因子值，并可能会将数据存储在文本文件中。SVM 分类器的创建如下所示：

var svm = new SupportVectorMachine("poly", 0);
svm.gamma = 1.0;
svm.coef = 0.0;
svm.degree = 2;

“poly”参数实际上是虚拟值，因为 SVM 被硬编码为使用多项式内核函数。参数 0 是定型算法的随机部分的种子值。gamma、coef（亦称为 constant）和 degree 参数是多项式内核函数的参数。接下来，指定定型算法的参数：

svm.complexity = 1.0;
svm.epsilon = 0.001;
svm.tolerance = 0.001;
int maxIter = 1000;

所有这些值都是必须通过试错来确定的超参数。使用 SVM 的任何实现时，主要的挑战是理解要使用哪个内核，以及理解内核参数和定型参数。定型由一个语句执行：

int iter = svm.Train(train_X, train_y, maxIter);

定型 SVM 分类器是一个迭代过程，方法 Train 返回已执行的实际迭代次数，有助于在出现问题时进行调试。定型后，SVM 对象保留支持向量的 List<double[]> 集合，即保留模型权重（每个支持向量一个）和一个偏差值的数组。它们显示如下：

foreach (double[] vec in svm.supportVectors) {
  for (int i = 0; i < vec.Length; ++i)
    Console.Write(vec[i].ToString("F1") + "  ");
  Console.WriteLine("");
}
for (int i = 0; i < svm.weights.Length; ++i)
  Console.Write(svm.weights[i].ToString("F6") + " ");
Console.WriteLine("");
Console.WriteLine("Bias = " + svm.bias.ToString("F6") + "\n");

最后，演示程序进行如下预测：

double[] unknown = new double[] { 3, 5, 7 };
double predDecVal = svm.ComputeDecision(unknown);
Console.WriteLine("Predicted value for (3.0 5.0 7.0) = " +
  predDecVal.ToString("F3"));
int predLabel = Math.Sign(predDecVal);
Console.WriteLine("Predicted label for (3.0 5.0 7.0) = " +
  predLabel);

决策值的类型为 Double。如果决策值为负，预测类为 -1；如果决策值为正，预测类为 +1。

了解 SVM

SVM 相当难理解，而且极难实现。请看图 3 中的曲线图。目标是创建区分红色数据和蓝色数据的规则。下图展示的问题中数据只有两个维度（预测因子变量数），所以可以直观呈现问题，但 SVM 可处理包含三个或多个维度的数据。

图 3：基本 SVM 概念

SVM 的工作原理是，先查找分离两个类的最宽可能通道，再在每个类中标识最接近分离通道边缘的一个或多个点。

若要对之前没有见过的新数据点进行分类，只需确定新点落入通道中间线的哪一侧即可。在图 3 中，(0.3, 0.65) 处带红圈的红点，以及 (0.5, 0.75) 和 (0.65, 0.6) 处带蓝圈的蓝点称为“支持向量”。不过，就我而言，我将它们视为“支持点”，因为我通常将向量看成是线。

必须应对三个主要挑战，才能实现可用 SVM。第一，如果数据不是像图 3**** 一样线性可分，该怎么办？第二，如何找到支持向量、权重和偏差值？第三，如何处理位于边界通道错误一侧的异常定型数据点？

如本文所述，可使用所谓的内核函数来处理非线性可分数据。可使用序列最小优化 (SMO) 算法来确定支持向量、权重和偏差值。此外，还可使用惩罚错误数据的 complexity 概念来处理不一致的定型数据。

内核函数

内核函数有很多种不同类型。简言之，内核函数需要使用两个向量，并以某种方式组合它们，以生成一个标量值。尽管并不显而易见，但使用内核函数，可以让 SVM 处理非线性可分数据。这称为“内核技巧”。

假设有两个变量，分别为 v1 = (3, 5, 2) 和 v2 = (4, 1, 0)。一种非常简单的内核称为“线性内核”，它返回向量元素的乘积之和：

K(v1, v2) = (3 * 4) + (5 * 1) + (2 * 0) = 17.0

许多内核函数都有可选的比例因子，通常称为“gamma”。对于前面的示例，如果 gamma 设置为 0.5，则：

K(v1, v2) = 0.5 * [(3 * 4) + (5 * 1) + (2 * 0)] = 8.5

演示程序使用 degree = 2、gamma = 1.0、constant = 0 的多项式内核。用语言来表述就是，计算乘积之和，再乘以 gamma，加上 constant，最后求 degree 次方。例如，

K(v1, v2) = [1.0 * ((3*4) + (5*1) + (2*0)) + 0]^2 = (1 * 17 + 0)^2 = 289.0

演示程序按如下所示实现多项式内核：

public double PolyKernel(double[] v1, double[] v2)
{
  double sum = 0.0;
  for (int i = 0; i < v1.Length; ++i)
    sum += v1[i] * v2[i];
  double z = this.gamma * sum + this.coef;
  return Math.Pow(z, this.degree);
}

gamma、degree 和 constant（命名为 coef 是为了避免与语言关键字发生名称冲突）值是类成员，它们的值在其他位置提供。演示程序硬编码内核函数，因此若要尝试不同的函数，必须自行实现它。

径向基函数 (RBF) 内核通常可替代多项式内核。用语言来表述就是，计算元素间均方误差之和，乘以负 gamma，再求 e（欧拉数，约为 2.718）次方。在代码中，RBF 内核如下所示：

public double RbfKernel(double[] v1, double[] v2)
{
  double sum = 0.0;
  for (int i = 0; i < v1.Length; ++i)
    sum += (v1[i] - v2[i]) * (v1[i] - v2[i]);
    return Math.Exp(-this.gamma * sum);
}

请注意，不同内核函数的参数也不同。线性内核和 RBF 内核只需要 gamma，但多项式内核需要 gamma、degree 和 constant。选择要使用的内核函数和应用于要使用的内核函数的参数值都是在选择自由参数，必须通过试错来确定。所有机器学习分类技术都有超参数，但 SVM 往往对超参数值尤为敏感。

序列最小优化算法

可用于确定支持向量来解决 SVM 问题的算法有很多。SMO 算法最常见。演示程序遵循 1998 年研究论文“序列最小优化：定型支持向量机的快速算法”中有关 SMO 的原始说明，可以在 Internet 上的许多地方找到这篇论文。

SMO 算法非常复杂，完整解释大概需要 200 页篇幅（我之所以知道这一点是因为，我曾经看过专门介绍 SMO 的一整本书）。SMO 有三个重要函数：顶级 Train 函数调用帮助程序 ExamineExample 函数，进而调用帮助程序 TakeStep 函数。

TakeStep 的签名是：private bool TakeStep(int i1, int i2, double[][] X_matrix, int[] y_vector)。参数 X_matrix 保留定型数据预测因子值。参数 y_vector 保留定型数据目标值（-1 或 +1）。i1 和 i2 参数是指向定型数据的第一个和第二个索引。每次调用 TakeStep 时，此算法都会尝试寻找更好的解决方案。如果使用两个定型数据项发现了改进，便会返回 true；否则，返回 false。

ExamineExample 的签名是：private int ExamineExample(nt i2, double[][] X_matrix, int[] y_vector)。此函数返回更改数，以便 TakeStep 能够确定是否已取得任何进展。

TakeStep 和 ExamineExample 都使用类作用域变量 complexity。complexity 值越大，就越会惩罚离群值定型数据，并强制 SMO 算法尝试寻找解决方案来处理它们，但这会以模型过度拟合为牺牲。因为 complexity 是 SMO 使用的参数，所以它始终存在，这不同于与所用内核函数关联的参数，这些参数可能存在，也可能不存在。

TakeStep 函数使用类作用域变量 epsilon，而 ExamineExample 函数则使用类作用域变量 tolerance。这两个变量的值都很小，在演示程序中默认设置为 0.001。epsilon 是在内部使用，用于确定何时停止迭代，进而影响发现的支持向量数。tolerance 是在计算误差时使用。epsilon 和 tolerance 值都是自由参数，更改它们所产生的效果大小有所不同（介于很小和很大之间），具体视要解决的特定问题而定。

方法 Train 的代码如图 4 所示。此方法是迭代的，返回所执行的迭代数。此方法接受 maxIter 参数，以设置所执行迭代数的硬性上限。从理论上讲，SMO 算法始终聚合和停止迭代，但对于像 SMO 这样复杂的算法，理论并不总是与实践一致。

图 4：定型方法

public int Train(double[][] X_matrix, int[] y_vector, int maxIter)
{
  int N = X_matrix.Length;
  this.alpha = new double[N];
  this.errors = new double[N];
  int numChanged = 0;
  bool examineAll = true;
  int iter = 0;
  while (iter < maxIter && numChanged > 0 || examineAll == true) {
    ++iter;
    numChanged = 0;
    if (examineAll == true) {
      for (int i = 0; i < N; ++i)
        numChanged += ExamineExample(i, X_matrix, y_vector);
    }
    else {
      for (int i = 0; i < N; ++i)
        if (this.alpha[i] != 0 && this.alpha[i] !=
          this.complexity)
          numChanged += ExamineExample(i, X_matrix, y_vector);
    }
    if (examineAll == true)
      examineAll = false;
    else if (numChanged == 0)
      examineAll = true;
  } // While
  List<int> indices = new List<int>();  // support vectors
  for (int i = 0; i < N; ++i) {
    // Only store vectors with Lagrange multipliers > 0
    if (this.alpha[i] > 0) indices.Add(i);
  }
  int num_supp_vectors = indices.Count;
  this.weights = new double[num_supp_vectors];
  for (int i = 0; i < num_supp_vectors; ++i) {
    int j = indices[i];
    this.supportVectors.Add(X_matrix[j]);
    this.weights[i] = this.alpha[j] * y_vector[j];
  }
  this.bias = -1 * this.bias;
  return iter;
}

除了显式返回所执行的迭代数外，Train 还查找并存储作为支持向量的定型数据项的索引。在支持向量数已知后，就可以对保留权重值的数组进行分配了。权重值是非零的 alpha 值。

Train 方法有许多可能的自定义点。例如，演示程序代码将支持向量存储为 List<double[]> 集合。一种替代方法是，直接在 List<int> 集合或 int[] 数组对象中存储支持向量的索引。仔细探究 Train 方法是开始了解 SVM 和 SMO 算法的最佳方式。

了解 SVM 机制

如果参阅图 1****，便会发现已定型 SVM 有三个支持向量：(4, 5, 7)、(7, 4, 2) 和 (9, 7, 5)。模型有三个权重值 = (-0.000098, -0.000162, 0.000260) 和偏差 = -2.506。输入 (3, 5, 7) 的决策值计算方法为，分别使用三个支持向量来计算内核函数的值，再将每个内核值乘以对应的权重值、求和并加上偏差：

x = (3, 5, 7)
sv1 = (4, 5, 7)
sv2 = (7, 4, 2)
sv3 = (9, 7, 5)
K(x, sv1) * wt1 = 7396.0 * -0.000098 = -0.725
K(x, sv2) * wt2 = 3025.0 * -0.000162 = -0.490
K(x, sv3) * wt3 = 9409.0 * 0.000260 = 2.446
decision = -0.725 + -0.490 + 2.446 + -2.506 = -1.274
prediction = Sign(decision) = -1

请注意，如果未规范化预测因子值（如演示程序一样），内核值可能会非常大，导致权重值变得非常小，进而可能会导致算术误差。

SVM 机制指出了此技术的优势和劣势。SVM 仅专注于关键支持向量，因此往往能适应错误的定型数据。当支持向量数较小时，SVM 在某种程度上是可解释的，这与其他许多技术相比是一项优势。与其他许多分类技术（主要是神经网络）相比，SVM 通常能够很好地处理有限定型数据，但无法处理非常大的定型数据集。SVM 的主要缺点是，SVM 非常复杂，需要指定许多超参数的值。

总结

正如本文所述，支持向量机的实现相当复杂和困难。正因为此，可用的 SVM 库实现很少。大多数 SVM 库基于名为 LibSVM 的 C++ 实现，这是由一组研究人员创建的。因为调用 C++ 通常很困难，所以有几个库提供包装 LibSVM 的包装器（使用 Python、Java、C# 和其他语言编写而成）。

通过尝试本文中的代码，你将能充分了解 SVM 的确切工作原理，并能更有效地使用库实现。因为本文中的代码是简化后的独立式代码，所以你将能探索替代内核函数及其参数，以及 SMO 定型算法参数 epsilon、tolerance 和 complexity。

Dr.James McCaffrey 供职于华盛顿地区雷蒙德市沃什湾的 Microsoft Research。他参与开发过多个重要 Microsoft 产品（包括 Internet Explorer 和必应）。Dr.可通过 jamccaff@microsoft.com 与 McCaffrey 取得联系。

衷心感谢以下 Microsoft 技术专家对本文的审阅：Yihe Dong、Chris Lee

通过