分類演算法之鄰近演算法:KNN（理論篇）

起步

今天介紹另一種分類演算法，k鄰近演算法( k-nearest neighbors )，即 KNN 演算法。

概述

Cover 和 Hart 在 1968 年提出了最初的鄰近演算法，用於解決分類( classification )的問題。關於這個演算法在維基百科中也有介紹:https://zh.wikipedia.org/wiki/最近鄰居法 。

KNN是一種基於實例學習( instance-based learning )，或者所是將所有計算推遲到分類之後的惰性學習( lazy learning )的一種演算法，KNN是所有機器學習演算法中最簡單演算法之一。

從案例中說起

一個有關電影分類的例子：

這個一個根據打鬥次數和接吻次數作為特徵來進行類型的分類。最後一條的記錄就是待分類的數據。

KNN這個分類過程比較簡單的一個原因是它不需要創建模型，也不需要進行訓練，並且非常容易理解。把例子中打鬥次數和接吻次數看成是x軸和y軸，那麼就很容易能建立一個二維坐標，每條記錄都是坐標中的點。對於未知點來說，尋找其最近的幾個點，哪種分類數較多，未知點就屬於哪一類。

演算法說明

KNN演算法的思路是: 如果一個樣本在特徵空間中的 k 個最相似(即特徵空間中最鄰近)的樣本中的大多數屬於某一個類別，則該樣本也屬於這個類別。通常 K 的取值比較小，不會超過 20。

演算法步驟為：

• 計算未知實例到所有已知實例的距離；
• 選擇參數 K；
• 根據多數表決( majority-voting )規則，將未知實例歸類為樣本中最多數的類別。

距離的衡量方法

關於距離的測量方式有多種，這裡只介紹兩種。

歐拉距離 這種測量方式就是簡單的平面幾何中兩點之間的直線距離。

並且這種方法可以延伸至三維或更多維的情況。它的公式可以總結為:

曼哈頓距離 顧名思義，城市街區的距離就不能是點和點的直線距離，而是街區的距離。如棋盤上也會使用曼哈頓距離的計算方法：

K 值的選擇

K值的選擇會影響結果，有一個經典的圖如下:

圖中的數據集是良好的數據，即都打好了 label ，一類是藍色的正方形，一類是紅色的三角形，那個綠色的圓形是待分類的數據。

• K = 3 時，範圍內紅色三角形多，這個待分類點屬於紅色三角形。
• K = 5 時，範圍內藍色正方形多，這個待分類點屬於藍色正方形。

如何選擇一個最佳的K值取決於數據。一般情況下，在分類時較大的 K 值能夠減小雜訊的影響，但會使類別之間的界限變得模糊。因此 K 的取值一般比較小 ( K < 20 )。

改進

在下面一種情況中：

在點Y的預測中，改範圍內三角形分類數量佔優，因此將Y點歸為三角形。但是從視覺上觀測，應該是分為圓形分類更為合理。根據這種情況就在距離測量中加上權重，比如 1/d (d: 距離)。

KNN 的優缺點

優點：

• 簡單，易於理解，無需建模與訓練，易於實現；
• 適合對稀有事件進行分類；
• 適合與多分類問題，例如根據基因特徵來判斷其功能分類，kNN比SVM的表現要好。

缺點：

• 惰性演算法，內存開銷大，對測試樣本分類時計算量大，性能較低；
• 可解釋性差，無法給出決策樹那樣的規則。

推薦閱讀：