R 中的資料探勘演算法/分類/kNN

介紹

本章介紹了用於分類的 k 最近鄰 (kNN) 演算法。kNN 最初由 Fix 和 Hodges ^[1] 提出，是一種非常簡單的“基於例項”的學習演算法。儘管它很簡單，但在某些問題上可以提供非常好的效能。我們對演算法進行了高階概述，解釋了相關的引數和實現選擇，然後逐步進行了案例研究。

k 最近鄰

kNN 演算法與其他基於例項的演算法一樣，在分類方面不尋常，因為它沒有顯式模型訓練。雖然需要訓練資料集，但它僅僅用於用已知類別的例項填充搜尋空間的樣本。在此階段沒有執行實際的模型或學習；出於這個原因，這些演算法也被稱為惰性學習演算法。可以使用不同的距離度量，具體取決於資料的性質。歐幾里德距離通常用於連續變數，但其他度量可用於分類資料。專門的度量通常對特定問題有用，例如文字分類。當要評估的類未知的例項出現時，演算法會計算其 k 個最近鄰，並透過對這些鄰近點進行投票來分配類別。為了防止平局，人們通常使用奇數 k 用於二元分類。對於多個類別，可以使用眾數投票或多數投票。後者有時會導致未將任何類別分配給例項，而前者會導致分類的低支援率。還可以透過距離到被分類例項的倒數函式對每個鄰近點進行加權。kNN 用於分類的主要優點是

非常簡單的實現。
對搜尋空間具有魯棒性；例如，類別不必線性可分。
當出現具有已知類別的新例項時，分類器可以以非常低的成本線上更新。
很少的引數需要調整：距離度量和 k。

演算法的主要缺點是

對每個例項的測試成本很高，因為我們需要計算它到所有已知例項的距離。針對特定問題和距離函式，存在專門的演算法和啟發式方法，可以緩解此問題。對於具有大量屬性的資料集，這是一個問題。當例項數量遠大於屬性數量時，可以使用 R 樹或 kd 樹來儲存例項，從而實現快速準確的鄰居識別。
對噪聲或不相關屬性的敏感性，這會導致不太有意義的距離數字。縮放和/或特徵選擇通常與 kNN 結合使用以緩解此問題。
對高度不平衡資料集的敏感性，其中大多數實體屬於一個或幾個類別，因此不常見的類別在大多數鄰近點中通常占主導地位。這可以透過在訓練階段對更流行的類別進行平衡取樣來緩解，可能還會與整合方法結合使用。

演算法描述

kNN 的訓練階段僅包括簡單地儲存所有已知例項及其類標籤。可以使用表格表示，或使用 kd 樹等專門結構。如果我們想調整“k”的值和/或執行特徵選擇，則可以使用 n 折交叉驗證在訓練資料集上進行。針對新的例項“t”、給定已知集合“I”的測試階段如下

計算“t”與“I”中每個例項之間的距離
按數值升序對距離進行排序，並選擇前“k”個元素
計算並返回“k”個最近鄰中最頻繁的類別，可以選擇透過每個例項到“t”的距離的倒數對每個例項的類別進行加權

可用實現

R 中至少有三種 kNN 分類實現，它們都可以在 CRAN 上獲得

knn
kknn
RWeka，它是流行的 WEKA ^[2] 機器和資料探勘工具包的橋樑，它提供了 kNN 實現以及數十種用於分類、聚類、迴歸和資料工程的演算法。

在本教程中，我們選擇 RWeka，因為它提供的不僅僅是 kNN 分類，並且下面顯示的示例會話可用於生成其他分類器，只需稍作修改即可。

安裝和執行 RWeka

RWeka 是一個 CRAN 包，因此可以在 R 內部安裝

> install.packages("RWeka", dependencies = TRUE)

大多數 R 圖形使用者介面還透過其 UI 提供包管理。安裝完成後，RWeka 可以作為庫載入

> library(RWeka)

它附帶幾個眾所周知的資料集，可以作為 ARFF 檔案（Weka 的預設檔案格式）載入。我們現在載入一個示例資料集，著名的 Iris 資料集 ^[3]，並使用預設引數學習一個 kNN 分類器。

> iris <- read.arff(system.file("arff", "iris.arff", package = "RWeka"))
> classifier <- IBk(class ~., data = iris)
> summary(classifier)

=== Summary ===

Correctly Classified Instances         150              100      %
Incorrectly Classified Instances         0                0      %
Kappa statistic                          1     
Mean absolute error                      0.0085
Root mean squared error                  0.0091
Relative absolute error                  1.9219 %
Root relative squared error              1.9335 %
Total Number of Instances              150     

=== Confusion Matrix ===

  a  b  c   <-- classified as
 50  0  0 |  a = Iris-setosa
  0 50  0 |  b = Iris-versicolor
  0  0 50 |  c = Iris-virginica

雖然在上一個會話中，我們只使用了預設引數，但 RWeka 允許我們以多種方式自定義 KNN 分類器，除了設定 k 的值之外

我們可以透過它們到目標例項的距離的倒數，或透過 1 - 距離來對鄰近點進行加權。
我們可以使用留一交叉驗證在訓練資料中選擇 k 的最佳值。
我們可以使用訓練例項的滑動視窗，因此一旦分類器瞭解了 W 個例項，當新增新的例項時，舊的例項就會被丟棄。
我們可以自定義演算法儲存已知例項的方式，這使我們能夠在大型資料集上使用 kd 樹和類似的資料結構來加快鄰居搜尋。

案例研究

我們現在將對 Iris 資料集進行更詳細的探索，使用交叉驗證進行實際測試統計，並進行一些引數調整。

資料集

Iris 資料集包含 150 個例項，對應於三種等頻的鳶尾花物種（Iris setosa、Iris versicolour 和 Iris virginica）。下圖顯示了 Iris versicolor，來自 Wikimedia Commons。

每個例項包含四個屬性：萼片長度（釐米）、萼片寬度（釐米）、花瓣長度（釐米）和花瓣寬度（釐米）。下一張圖片顯示了每個屬性相對於其他屬性的繪製，不同類別的顏色不同。

執行和結果

我們將生成一個 kNN 分類器，但我們會讓 RWeka 自動在 1 到 20 之間找到 k 的最佳值。我們還將使用 10 折交叉驗證來評估我們的分類器

> classifier <- IBk(class ~ ., data = iris, 
                    control = Weka_control(K = 20, X = TRUE))
> evaluate_Weka_classifier(classifier, numFolds = 10)
=== 10 Fold Cross Validation ===

=== Summary ===

Correctly Classified Instances         142               94.6667 %
Incorrectly Classified Instances         8                5.3333 %
Kappa statistic                          0.92  
Mean absolute error                      0.041 
Root mean squared error                  0.1414
Relative absolute error                  9.2339 %
Root relative squared error             29.9987 %
Total Number of Instances              150     

=== Confusion Matrix ===

  a  b  c   <-- classified as
 50  0  0 |  a = Iris-setosa
  0 46  4 |  b = Iris-versicolor
  0  4 46 |  c = Iris-virginica

> classifier
IB1 instance-based classifier
using 6 nearest neighbour(s) for classification

由於交叉驗證會生成資料集的隨機分割槽，因此您的結果可能會有所不同。但是，通常情況下，模型會犯不超過 10 個錯誤。

分析

這個簡單的案例研究表明，kNN 分類器在資料集上犯的錯誤很少，儘管簡單，但它不是線性可分的，如散點圖所示，以及透過檢視混淆矩陣，其中所有誤分類都在 Iris Versicolor 和 Iris Virginica 例項之間。案例研究還展示了 RWeka 如何使學習分類器（以及預測器和聚類模型）變得非常容易，以及如何試驗其引數。在這個經典的資料集中，kNN 分類器犯的錯誤很少。

參考文獻

^ Fix, E., Hodges, J.L. (1951); Discriminatory analysis, nonparametric discrimination: Consistency properties. Technical Report 4, USAF School of Aviation Medicine, Randolph Field, Texas.
^ Mark Hall, Eibe Frank, Geoffrey Holmes, Bernhard Pfahringer, Peter Reutemann, Ian H. Witten (2009); The WEKA Data Mining Software: An Update. SIGKDD Explorations, 11(1).
^ Fisher,R.A. (1936); The use of multiple measurements in taxonomic problems. Annual Eugenics, 7, Part II, 179-188.

[1]

[2]

[3]