K Nearest Neighbors — 簡介

原文在這裏 — 這是針對這篇原文的翻譯版本. 如有問題請告知. 感謝各位.

在我的事業生涯作為分析師(原文為: analytics)的4年當中, 我建立過超過80%的classification model(分類模型), 而只有15%-20%是Regression model(回歸模型). 我猜這種比率在這一行來說是十分正常的. 這種趨勢的原因是大部份分析問題涉及”作出決定” (making a decision). 比如: 顧客是否會離開? 我們是否該用線上廣告推廣到X這個客戶群? 這顧客是否有足夠的潛力等等. 這些分析不但比較有啟發性, 而且直接與實踐行為掛鈎.

在這篇文章中, 我們會討論一個被廣泛應用的classification(分類)技術, 稱為 K-Nearest Neighbors (KNN/最近鄰居法/近鄰算法). 我們將集中於探討這個演算法是怎麼運作的, 以及輸入的變數如何影響輸出/預測.

何時使用KNN?

KNN可用來解決classification (分類)及 regression (回歸)預測問題. 但是, KNN普遍用於分類法. 就著KNN我們會看看以下3方面:

- 是否容易解釋輸出(Output)
- 所花時間
- 預測能力.

請看看以下例子:

KNN在這3方面顯得無能為力. 所以通常我們用於解釋輸出以及減低計算時間.

KNN演算法是怎麼運作的?

我們可用以下的圖片理解. 以下圖片顯示分散的紅色圓形(Red Circle)及綠色方形(Green squares).

你的目的是希望找出藍色星星所屬於哪一個類別 (紅色圓形還是綠色方形? 二選一). K在KNN的意思是藍色星星究竟屬於哪一組的?

現假設K = 3, 意即找出距離藍色星星最近的3個資料點, 即為所屬類別. 現在我們可以用藍色圈圈指定3個資料點, 如下圖:

最近這藍色星星的是紅色圓圈. 所以, 我們有信心可以認定藍色星星屬於紅色圓圈. 在此, 選擇紅色圓圈其實很明確. 而選擇使用哪一個K值顯得尤其重要.

下一步我們將探討如何選擇K

如何選擇K值?

首先我們該明白K是怎樣影響整個演算法的. 如果我們看看上一個例子, 假設紅色圓圈和綠色方形保持不變, 設定K值可讓我們知道每個類別的邊界在哪裏. 這條邊界會分開紅色圓圈和綠色方形. 以下先看看K值如何影響類別的邊界. 下圖為2個類別, 不同的K值所帶來的結果.

如果你深入看看, 你會發現當K值增加, 邊界會逐漸圓滑. 而K增加至無限的時候, 那就變成全部都是紅色圓圈或綠色方形.

訓練誤差(training error)以及驗證誤差(Validation error)是我們評估不同K值的準則. 而以下是訓練誤差(training error)在不同K值之下的結果.

你可以看到, K = 1時誤差率永遠為0. 那是因為最近的資料點就是自己, 預測永遠準確. 如果驗證誤差(Validation error)是相似的話, 那我們就選擇K=1. 以下則是驗證誤差(Validation error)在不同K值之下的結果:

這令整個故事更完整了. 當K=1, 就會出現過度擬合(overfitting)的問題. 然後, 誤差率會一直下降並達到最低點. 當K越來越大, 誤差值會越來越高.

所以, 要獲得最理想的K值, 你必需先畫出這一條驗證誤差曲線(Validation error curve). 然後取最低那一點, 該點就用於往後的預測.

結語

KNN演算法是其中一種最簡單的分類方法. 但因為它簡單, 它可能產生的結果卻非常有效果. KNN演算法亦可以用來進行回歸(Regression)預測. 分別只在於我們在Regression時取的是平均值, 而不是最近值. KNN可以用一行R來處理, 而我還在看看怎麼在SAS中使用KNN.