R 中的数据挖掘算法/分类/支持向量机

简介

支持向量机 (SVM) 是一种监督学习方法，用于分类和回归任务，起源于统计学习理论 。作为一种分类方法，SVM 是一种全局分类模型，它生成非重叠分区，通常使用所有属性。实体空间在一次遍历中被划分，因此生成平坦的线性分区。SVM 基于最大边缘线性判别，类似于概率方法，但不考虑属性之间的依赖关系 。

传统的“神经网络”方法在泛化方面存在困难，由于用于参数选择的优化算法和用于选择最佳模型的统计度量，产生的模型过度拟合数据。SVM 因其许多吸引人的特性和有希望的经验性能而越来越受欢迎。它们基于结构风险最小化 (SRM) 原则 已经证明优于传统神经网络采用的经验风险最小化 (ERM) 原则。ERM 最小化训练数据的误差，而 SRM 最小化预期风险的上限。这使得 SRM 具有更强的泛化能力，这是统计学习的目标 。根据 ，SVM 依赖于对数据的预处理，以在高维空间中表示模式，通常比原始特征空间高得多。当使用适当的非线性映射到足够高的维度时，来自两个类别的數據总可以通过超平面分离。

分类任务通常涉及训练集和测试集，它们包含数据实例。训练集中的每个实例都包含一个目标值（类标签）和几个属性（特征）。分类器的目标是生成一个模型，能够预测测试集中数据实例的目标值，对于这些实例，只知道属性。不失一般性，分类问题可以看作一个两类问题，其中目标是通过从可用示例中诱导的函数来分离两类。目标是生成一个能够很好泛化的分类器，即在看不见的示例上表现良好的分类器。下图是一个例子，其中各种线性分类器可以分离数据。但是，只有一个最大化了它本身与每个类最近示例之间的距离（即边缘），因此被称为最佳分离超平面。直观上预计，这个分类器比其他选项具有更好的泛化能力 。SVM 分类器的基本思想就是使用这种方法，即选择具有最大边缘的超平面。

图 1：分离超平面的示例

算法

令 D 为一个分类数据集，在 d 维空间 D = {(x_i, y_i)} 中有 n 个点，其中 i = 1, 2, ..., n，并且只有两个类标签，使得 y_i 为 +1 或 -1。超平面 h(x) 在 d 维中给出了一个线性判别函数，并将原始空间分成两个半空间

$h(x)=w^{T}x+b=w_{1}x_{1}+w_{2}x_{2}+...+w_{d}x_{d}+b\,$,

其中 w 是一个 d 维权重向量，b 是一个标量偏差。超平面上的点具有 h(x) = 0，即超平面由所有满足 w^Tx = -b 的点定义。

根据 ，如果数据集是线性可分的，则可以找到一个分离超平面，使得对于所有标签为 -1 的点，h(x) < 0，对于所有标签为 +1 的点，h(x) > 0。在这种情况下，h(x) 充当线性分类器或线性判别器，用于预测任何点的类别。此外，权重向量 w 与超平面正交，因此给出垂直于超平面的方向，而偏差 b 固定超平面在 d 维空间中的偏移。

给定一个分离超平面 h(x) = 0，可以通过以下公式计算每个点 x_i 与超平面之间的距离

$\delta _{i}={\tfrac {y_{i}h(x_{i})}{||w||}}$

线性分类器的边缘定义为所有 n 个点到分离超平面的最小距离。

$\delta ^{*}=\min _{x_{i}}\{{\tfrac {y_{i}h(x_{i})}{||w||}}\}$

所有实现此最小距离的点（向量 x^*_i）被称为线性分类器的支持向量。换句话说，支持向量是指正好位于分类超平面的边缘上的点。

在超平面的规范表示中，对于每个带有标签 y^*_i 的支持向量 x^*_i，我们有 $y_{i}^{*}h(x_{i}^{*})=1$。类似地，对于任何不是支持向量的点，我们有 $y_{i}h(x_{i})>1\,$，因为根据定义，它必须比支持向量离超平面更远。因此，我们有 $y_{i}h(x_{i})\geq 1,\ \forall x_{i}\in D$。

支持向量机背后的基本思想是选择具有最大间隔的超平面，即最佳规范超平面。为此，需要找到权重向量 w 和偏差 b，它们在所有可能的分割超平面中产生最大间隔，即最大化 ${\tfrac {1}{||w||}}$ 的超平面。因此问题就变成了解决一个凸优化问题（注意，而不是最大化间隔 ${\tfrac {1}{||w||}}.$，可以得到一个等效的公式，即最小化 $||w||$），并带有线性约束，如下所示

目标函数

$min{\tfrac {||w||^{2}}{2}}$

线性约束

$y_{i}h(x_{i})\geq 1,\ \forall x_{i}\in D$

这个最小化问题可以使用拉格朗日乘子方法来解决，该方法为每个约束引入一个拉格朗日乘子 α

$\alpha _{i}(y_{i}h(x)-1)=0\ {\text{with}}\ \alpha _{i}\geq 0$

该方法指出，对于所有距离大于 ${\tfrac {1}{||w||}}$ 的点的 α_i = 0，并且只有那些恰好位于间隔上的点，即支持向量，α_i > 0。分类器的权重向量被获得为支持向量的线性组合，而偏差是每个支持向量获得的偏差的平均值。

支持向量机可以处理线性不可分的点，这些点在一定程度上重叠，使得完美的分割是不可能的。通过引入松弛变量 ε_i，对于 D 中的每个点 x_i。如果 0 ≤ ε_i < 1，则该点仍然被正确分类。否则，如果 ε_i > 1，则该点被错误分类。因此，分类的目标就变成了找到具有最大间隔的超平面（w 和 b），同时最小化松弛变量的总和。需要一种类似于上面描述的方法来找到权重向量 w 和偏差 b。

支持向量机 (SVM) 也可以解决具有非线性决策边界的分类问题。其主要思想是将原始的 *d* 维空间映射到一个 *d'* 维空间 (*d'* > *d*)，在该空间中点可能线性可分。给定原始数据集 *D = {x_i, y_i}*，其中 *i = 1,...,n*，以及转换函数 Φ，在转换空间中得到新的数据集 *D_Φ = {Φ(x_i), y_i}*，其中 *i = 1,...,n*。找到 *d'* 维空间中的线性决策面后，将其映射回原始 *d* 维空间中的非线性曲面。为了得到 *w* 和 *b*，不需要单独计算 *Φ(x)*。在转换空间中唯一需要的操作是内积 *Φ(x_i)^TΦ(x_j)*，它通过 *x_i* 和 *x_j* 之间的核函数 (K) 定义。在 SVM 中常用的核函数包括：

• 多项式核

$K(x_{i},x_{j})=(x_{i}^{T}x_{j}+1)^{q}$，其中 $q$ 是多项式的次数

• 高斯核

$K(x_{i},x_{j})=e^{-{\frac {||x_{i}-x_{j}||^{2}}{2\sigma ^{2}}}}$，其中 $\sigma$ 是扩展或标准差。

• 高斯径向基函数 (RBF)

$K(x_{i},x_{j})=e^{-\gamma ||x_{i}-x_{j}||^{2}},\,\gamma \geq 0$

• 拉普拉斯径向基函数 (RBF) 核

$K(x_{i},x_{j})=e^{-\gamma ||x_{i}-x_{j}||},\,\gamma \geq 0$

• 双曲正切核

$K(x_{i},x_{j})=\tanh(x_{i}^{T}x_{j}+{\text{offset}})$

• S 型核

$K(x_{i},x_{j})=\tanh(ax_{i}^{T}x_{j}+{\text{offset}})$

• 第一类贝塞尔函数核

$K(x_{i},x_{j})=\left({\tfrac {Bessel_{v+1}^{n}(\sigma ||x_{i}-x_{j}||)}{(||x_{i}-x_{j}||)^{-n(v+1)}}}\right)$

• ANOVA 径向基核

$K(x_{i},x_{j})=\left(\sum _{k=1}^{n}e^{-\sigma (x_{i}^{k}-x_{j}^{k})^{2}}\right)^{d}$

• 一维线性样条核

$K(x_{i},x_{j})=1+x_{i}x_{j}\min(x_{i},x_{j})-{\tfrac {x_{i}+x_{j}}{2}}\min(x_{i},x_{j})^{2}+{\tfrac {\min(x_{i},x_{j})^{3}}{3}}$

根据，高斯和拉普拉斯 RBF 以及贝塞尔核是当没有关于数据的先验知识时使用的一般用途核。线性核在处理大型稀疏数据向量时很有用，这在文本分类中很常见。多项式核在图像处理中很流行，而 sigmoid 核主要用作神经网络的代理。样条和 ANOVA RBF 核通常在回归问题中表现良好。

R 中的可用实现

R 是一种用于统计计算和图形的语言和环境。有五个包在 R 中实现了 SVM

• e1071
• kernlab
• klaR
• svmpath
• shogun

本文档将重点介绍 e1071 包，因为它最直观。有关其他内容的信息，请参见上面引用的参考资料以及 的报告。

e1071 包

e1071 包是 R 中第一个实现 SVM 的包。svm() 函数提供了一个接口，用于访问 libsvm ，辅以可视化和调整功能。libsvm 是分类中最流行的 SVM 公式 (C 和$\nu$)) 的快速易用实现，并包含最常见的内核（线性、多项式、RBF 和 sigmoid）。多类分类是使用一对一投票方案提供的。它还包括对预测的决策和概率值的计算，在拟合过程中的收缩启发式方法，分类模式中的类权重，稀疏数据的处理以及交叉验证。

R 实现基于 S3 类机制。它基本上提供了一个具有标准和公式接口的训练函数，以及一个 predict() 方法。此外，还提供了 plot() 方法，用于可视化数据、支持向量和决策边界。超参数调整是使用 tune() 框架完成的，该框架对指定的参数范围执行网格搜索。

安装和启动 e1071 包

要在 R 中安装 e1071 包，请键入

    install.packages('e1071', dependencies = TRUE)

要开始使用该包，请键入

    library(e1071)

e1071 包中用于训练、测试和可视化的主要函数

在 R 中使用 SVM 进行任何分类过程中，一些 e1071 包函数非常重要，因此将在下面介绍。

第一个函数是 svm()，用于训练支持向量机。一些重要的参数包括

• data：一个可选数据框，包含模型中的变量。如果使用此选项，则下面描述的 x 和 y 参数将不再需要；

• x：一个数据矩阵、向量或稀疏矩阵，它表示数据集的实例及其各自的属性。行表示实例，列表示属性；

• y：一个响应向量，每个行（实例）都有一个标签；

• type：设置 svm() 的工作方式。分类的可能值包括：C、nu 和 one（用于新颖性检测）；

• kernel：定义训练和预测中使用的内核。选项包括：linear、polynomial、radial basis 和 sigmoid；

• degree：如果内核是多项式，则需要此参数（默认值：3）；

• gamma：除了线性之外的所有类型的内核都需要此参数（默认值：1/(数据维度)）；

• coef0：多项式和 sigmoid 内核需要此参数（默认值：0）；

• cost：约束违反的成本（默认值：1）。这是拉格朗日公式中正则化项的“C”常数；

• cross：指定交叉验证。k>0 是必需的。在这种情况下，将执行训练数据以评估模型的质量：分类的准确率；

• probability：逻辑值，指示模型是否应允许概率预测。

下面给出了 svm() 用法的示例

    library(MASS)
    data(cats)
    model <- svm(Sex~., data = cats)

前两个命令指定了 cats 数据集的使用方式，该数据集包含 144 个实例，每个实例包含 2 个数值属性（“Bwt” 和 “Hwt”），以及每个实例的类别（属性“Sex”）。实例类别可以是 “F”，表示女性，或 “M”，表示男性。在第三个命令中，参数“Sex~.” 指示要作为实例类别使用的数据集的属性（列）。

有关模型参数和支持向量数量的信息，请键入

    print(model)
    summary(model)

summary 命令的结果如下所示

  Call:
  svm(formula = Sex ~ ., data = cats)
  
  Parameters:
     SVM-Type:  C-classification 
   SVM-Kernel:  radial 
         cost:  1 
        gamma:  0.5 
  
  Number of Support Vectors:  84
  
   ( 39 45 )
  
  
  Number of Classes:  2 
  
  Levels: 
   F M

要查看构建的模型以及输入的散点图，可以使用 plot() 函数。此函数可以选择绘制类区域的填充等高线图。该函数的主要参数如下所示

• model：svm 数据类的对象，由 svm() 函数生成；

• data：要可视化的数据。它应该是 svm() 函数中用于构建模型的相同数据；

• symbolPalette、svSymbol、dataSymbol 和 colorPalette：这些参数控制用于表示支持向量和其他数据点的颜色和符号。

以下命令将生成下面的图表，其中支持向量显示为 “X”，真实类别通过符号颜色突出显示，预测的类别区域使用彩色背景可视化。

    plot(model, cats)

predict() 函数根据由 svm 训练的模型预测值。对于分类问题，它返回一个预测标签向量。有关其用法的信息，请使用以下命令。

    help(predict.svm)

首先，将 cats 数据集划分为训练集和测试集

    index <- 1:nrow(cats)
    testindex <- sample(index, trunc(length(index)/3))
    testset <- cats[testindex,]
    trainset <- cats[-testindex,]

现在，我们再次运行该模型，使用训练集并使用测试集预测类别，以验证该模型是否具有良好的泛化能力。

    model <- svm(Sex~., data = trainset)
    prediction <- predict(model, testset[,-1])

-1 是因为因变量 Sex 在第 1 列。

真实值与预测值的交叉表（混淆矩阵）

    tab <- table(pred = prediction, true = testset[,1])

如果键入 tab，您将看到如下所示的混淆矩阵

      true
  pred  F  M
     F 10  8
     M  6 24

有了这些信息，就可以计算模型对测试集的敏感度、特异度和精确度。

可以使用 classAgreement() 函数计算模型的准确率

    classAgreement(tab)

tune() 函数可用于使用网格搜索在提供的参数范围内调整统计方法的超参数。

    tuned <- tune.svm(Sex~., data = trainset, gamma = 10^(-6:-1), cost = 10^(1:2))
    summary(tuned)

这些命令将列出最佳参数、最佳性能以及测试参数值的详细信息，如下所示。

  Parameter tuning of `svm':
  
  - sampling method: 10-fold cross validation 
  
  - best parameters:
   gamma cost
     0.1  100
  
  - best performance: 0.1566667 
  
  - Detailed performance results:
     gamma cost     error dispersion
  1  1e-06   10 0.2600000  0.1095195
  2  1e-05   10 0.2600000  0.1095195
  3  1e-04   10 0.2600000  0.1095195
  4  1e-03   10 0.2600000  0.1095195
  5  1e-02   10 0.2833333  0.1230890
  6  1e-01   10 0.1788889  0.1359264
  7  1e-06  100 0.2600000  0.1095195
  8  1e-05  100 0.2600000  0.1095195
  9  1e-04  100 0.2600000  0.1095195
  10 1e-03  100 0.2833333  0.1230890
  11 1e-02  100 0.1788889  0.1359264
  12 1e-01  100 0.1566667  0.1014909

案例研究

在本节中，我们使用一个数据集进行乳腺癌诊断，并在其中应用 svm。svm 模型将能够区分良性和恶性肿瘤。

数据集

可以在 [1] 下载此数据集。在此数据集中，有 569 个实例，每个实例包含 32 个属性。第一个属性是实例的标识，第二个是实例类别的标签，可以是 M（恶性肿瘤）或 B（良性肿瘤）。接下来的 30 个属性是实数值输入特征，这些特征是根据乳腺肿块细针穿刺 (FNA) 的数字化图像计算得出。最后，数据集中有 357 个良性实例和 212 个恶性实例。

要读取数据集，请在下载并保存数据集后在 R 中键入

dataset <- read.csv('/home/myprofile/wdbc.data', head = FALSE)

'/home/myprofile/' 是保存数据集的路径。

准备数据集

现在，我们将随机将数据集划分为两个子集，一个子集大约包含 70% 的实例用于训练，另一个子集大约包含剩余的 30% 的实例用于测试

index <- 1:nrow(dataset)

testindex <- sample(index, trunc(length(index)*30/100))

testset <- dataset[testindex,]

trainset <- dataset[-testindex,]

选择参数

现在，我们将使用 tune() 函数对提供的参数范围（C - 成本，$\gamma$ - gamma）进行网格搜索，使用训练集。gamma 参数的范围介于 0.000001 和 0.1 之间。对于成本参数，范围从 0.1 到 10。

了解这两个参数的影响非常重要，因为 SVM 模型的准确率在很大程度上取决于它们的选取。例如，如果 C 太大，则对不可分离点的惩罚很高，我们可能会存储很多支持向量并过拟合。如果它太小，我们可能会出现欠拟合 。

请注意，数据库中没有列（属性）的名称。然后，R 为它们考虑默认名称，例如 V1 表示第一列，V2 表示第二列，依此类推。可以键入以下内容来检查这一点

names(dataset)

然后，由于类别标签是数据集的第二列，因此 tune() 函数的第一个参数将是 V2

tuned <- tune.svm(V2~., data = trainset, gamma = 10^(-6:-1), cost = 10^(-1:1))

结果使用以下命令显示

summary(tuned)

Parameter tuning of `svm':

- sampling method: 10-fold cross validation 

- best parameters:
 gamma cost
 0.001   10

- best performance: 0.02006410 

- Detailed performance results:
   gamma cost      error dispersion
1  1e-06  0.1 0.36333333 0.05749396
2  1e-05  0.1 0.36333333 0.05749396
3  1e-04  0.1 0.36333333 0.05749396
4  1e-03  0.1 0.30064103 0.06402773
5  1e-02  0.1 0.06256410 0.04283663
6  1e-01  0.1 0.08512821 0.05543939
7  1e-06  1.0 0.36333333 0.05749396
8  1e-05  1.0 0.36333333 0.05749396
9  1e-04  1.0 0.28314103 0.05862576
10 1e-03  1.0 0.05506410 0.04373139
11 1e-02  1.0 0.02756410 0.02188268
12 1e-01  1.0 0.03256410 0.02896982
13 1e-06 10.0 0.36333333 0.05749396
14 1e-05 10.0 0.28314103 0.05862576
15 1e-04 10.0 0.05500000 0.04684490
16 1e-03 10.0 0.02006410 0.01583519
17 1e-02 10.0 0.02256410 0.01845738
18 1e-01 10.0 0.05532051 0.04110686

训练模型

要构建一个 svm 模型以使用 C=10 和 gamma=0.001 预测乳腺癌，这些是之前运行的 tune() 函数确定的最佳值，请键入

model  <- svm(V2~., data = trainset, kernel = "radial", gamma = 0.001, cost = 10) 

要查看模型的结果，以及支持向量的数量，请键入

summary(model)

结果如下

Call:
svm(formula = V2 ~ ., data = trainset, kernel = "radial", gamma = 0.001, cost = 10)


Parameters:
   SVM-Type:  C-classification 
 SVM-Kernel:  radial 
       cost:  10 
      gamma:  0.001 

Number of Support Vectors:  79

 ( 39 40 )


Number of Classes:  2 

Levels: 
 B M

测试模型

现在，我们将再次运行测试集上的模型以预测类别。

prediction <- predict(model, testset[,-2])

-2 是因为实例类别标签列 V2 在第二列。

要生成混淆矩阵，请键入

tab <- table(pred = prediction, true = testset[,2])

混淆矩阵为

    true
pred   B   M
   B 103   6
   M   0  61

这意味着测试集中有 103 个良性实例，所有这些实例都被预测为良性实例。另一方面，测试集中有 67 个恶性实例，其中 61 个被正确预测，6 个被预测为良性实例。

令

• TP：真阳性，即正确预测的恶性实例
• FP：假阳性，即被预测为恶性的良性实例
• TN：真阴性，即正确预测的良性实例
• |N|：良性实例的总数
• |P|：恶性实例的总数

$sensitivity={\frac {TP}{|P|}}$

$specificity={\frac {TN}{|N|}}$

$precision={\frac {TP}{TP+FP}}$

对于此问题，我们有

$sensitivity={\frac {61}{61+6}}=0.91$

$specificity={\frac {103}{103}}=1$

$precision={\frac {61}{61+0}}=1$

分类结果良好。