一儡湾、kNN算法概述
? ? ? ?kNN是k-Nearest Neighbour的縮寫该酗，這是一種非常簡單且易于理解的分類算法悠砚。回想我們從小到大在認知事物的過程當(dāng)中米奸，我們是如何判斷一種事物是屬于哪種類別的昼接？通常的一種思路就是，分析當(dāng)前這個事物與我們之前所知道的類別特征進行比對悴晰，找出最接近的一類慢睡，然后就可以把這個東西歸屬于這一個類別逐工。kNN算法大致就是這么一個思路，直接通過測量不同特征值之間的距離來達到分類的目的漂辐。
? ? ? ?kNN中的k是指在分類過程中泪喊，我們選擇樣本數(shù)據(jù)中前k個最相似的數(shù)據(jù)，以出現(xiàn)次數(shù)最多的分類髓涯，作為新數(shù)據(jù)的分類袒啼。這里的k通常是不大于20的正整數(shù)，k取3或者5的情況比較常見纬纪。
二瘤泪、kNN算法的原理
? ? ? 首先是訓(xùn)練模型。對kNN而言育八，在編碼過程中訓(xùn)練模型實際上就是記錄訓(xùn)練集的所有數(shù)據(jù)对途，所以我們常說kNN沒有訓(xùn)練模型這一過程。
? ? ? 接著是測試模型髓棋。測試過程有以下幾個步驟：
1. 依次計算測試集數(shù)據(jù)與訓(xùn)練集各個數(shù)據(jù)之間的距離实檀；
2. 對計算處理的距離進行遞增排序；
3. 選擇距離最小的k個數(shù)據(jù)按声；
4. 選擇這k個數(shù)據(jù)中出現(xiàn)頻率最高的類別作為測試數(shù)據(jù)的預(yù)測分類膳犹。
? ? ? ?最后是評價模型。根據(jù)測試結(jié)果計算模型預(yù)測分類的準(zhǔn)確率签则。? ?
? ? ? ?整個過程看上去非常簡單须床、直觀、明了渐裂。需要說明的是豺旬，文中一直提到的距離這個概念，指的是閔可夫斯基距離（Minkowski distance）柒凉，對應(yīng)數(shù)學(xué)上的Lp范數(shù)族阅。
? ? ? 當(dāng)p=1時，為曼哈頓距離（Manhattan distance）膝捞，也稱L1距離坦刀；
? ? ? 當(dāng)p=2時，為歐式距離（Euclidean distance）蔬咬，也稱L2距離鲤遥；
? ? ? 當(dāng)p=∞時，為切比雪夫距離（distance）林艘。
? ? ??在我們使用kNN算法時盖奈，常用L1距離和L2距離，且以L2距離使用更多北启。
三卜朗、算法評價
? ? ? 優(yōu)點：kNN是最簡單、最有效的分類器咕村；精度高场钉；對異常值（邊緣值）不敏感。
? ? ? 缺點：需要記錄所有訓(xùn)練集的數(shù)據(jù)懈涛，空間復(fù)雜度高逛万；需要進行大量的計算，計算復(fù)雜度高批钠；無法提取出數(shù)據(jù)內(nèi)涵的結(jié)構(gòu)信息宇植。
? ? ? 注意點：由于計算距離時使用的是離散型數(shù)據(jù)，所以kNN算法常用于特征值為數(shù)值型和標(biāo)稱型的數(shù)據(jù)埋心。如果數(shù)據(jù)特征值為連續(xù)值指郁，則需要根據(jù)實際情況，對特征值進行離散采樣或者采用其他算法模型拷呆。
