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$

分類結果良好。