大數據演算法：kNN演算法

一、kNN演算法概述

kNN是k-Nearest Neighbour的縮寫，這是一種非常簡單且易於理解的分類演算法。回想我們從小到大在認知事物的過程當中，我們是如何判斷一種事物是屬於哪種類別的?通常的一種思路就是，分析當前這個事物與我們之前所知道的類別特徵進行比對，找出最接近的一類，然後就可以把這個東西歸屬於這一個類別。kNN演算法大致就是這麼一個思路，直接通過測量不同特徵值之間的距離來達到分類的目的。

kNN中的k是指在分類過程中，我們選擇樣本數據中前k個最相似的數據，以出現次數最多的分類，作為新數據的分類。這裡的k通常是不大於20的正整數，k取3或者5的情況比較常見。

二、kNN演算法的原理

首先是訓練模型。對kNN而言，在編碼過程中訓練模型實際上就是記錄訓練集的所有數據，所以我們常說kNN沒有訓練模型這一過程。

接著是測試模型。測試過程有以下幾個步驟：

1. 依次計算測試集數據與訓練集各個數據之間的距離;

2. 對計算處理的距離進行遞增排序;

3. 選擇距離最小的k個數據;

4. 選擇這k個數據中出現頻率最高的類別作為測試數據的預測分類。

最後是評價模型。根據測試結果計算模型預測分類的準確率。

整個過程看上去非常簡單、直觀、明了。需要說明的是，文中一直提到的距離這個概念，指的是閔可夫斯基距離(Minkowski distance)，對應數學上的Lp範數。

當p=1時，為曼哈頓距離(Manhattan distance)，也稱L1距離;

當p=2時，為歐式距離(Euclidean distance)，也稱L2距離;

當p=∞時，為切比雪夫距離(distance)。

在我們使用kNN演算法時，常用L1距離和L2距離，且以L2距離使用更多。

三、演算法評價

優點：kNN是最簡單、最有效的分類器;精度高;對異常值(邊緣值)不敏感。

缺點：需要記錄所有訓練集的數據，空間複雜度高;需要進行大量的計算，計算複雜度高;無法提取出數據內涵的結構信息。

注意點：由於計算距離時使用的是離散型數據，所以kNN演算法常用於特徵值為數值型和標稱型的數據。如果數據特徵值為連續值，則需要根據實際情況，對特徵值進行離散採樣或者採用其他演算法模型。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！