\一、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算法常用于特征值為數值型和标稱型的資料。如果資料特征值為連續值，則需要根據實際情況，對特征值進行離散采樣或者采用其他算法模型。