一、kNN算法概述
? ? ? ?kNN是k-Nearest Neighbour的縮寫，這是一種非常簡單且易于理解的分類算法?；叵胛覀儚男〉酱笤谡J(rèn)知事物的過程當(dāng)中，我們是如何判斷一種事物是屬于哪種類別的？通常的一種思路就是，分析當(dāng)前這個(gè)事物與我們之前所知道的類別特征進(jìn)行比對(duì)，找出最接近的一類，然后就可以把這個(gè)東西歸屬于這一個(gè)類別。kNN算法大致就是這么一個(gè)思路，直接通過測(cè)量不同特征值之間的距離來達(dá)到分類的目的。
? ? ? ?kNN中的k是指在分類過程中，我們選擇樣本數(shù)據(jù)中前k個(gè)最相似的數(shù)據(jù)，以出現(xiàn)次數(shù)最多的分類，作為新數(shù)據(jù)的分類。這里的k通常是不大于20的正整數(shù)，k取3或者5的情況比較常見。
二、kNN算法的原理
? ? ? 首先是訓(xùn)練模型。對(duì)kNN而言，在編碼過程中訓(xùn)練模型實(shí)際上就是記錄訓(xùn)練集的所有數(shù)據(jù)，所以我們常說kNN沒有訓(xùn)練模型這一過程。
? ? ? 接著是測(cè)試模型。測(cè)試過程有以下幾個(gè)步驟：
1. 依次計(jì)算測(cè)試集數(shù)據(jù)與訓(xùn)練集各個(gè)數(shù)據(jù)之間的距離；
2. 對(duì)計(jì)算處理的距離進(jìn)行遞增排序；
3. 選擇距離最小的k個(gè)數(shù)據(jù)；
4. 選擇這k個(gè)數(shù)據(jù)中出現(xiàn)頻率最高的類別作為測(cè)試數(shù)據(jù)的預(yù)測(cè)分類。
? ? ? ?最后是評(píng)價(jià)模型。根據(jù)測(cè)試結(jié)果計(jì)算模型預(yù)測(cè)分類的準(zhǔn)確率。? ?
? ? ? ?整個(gè)過程看上去非常簡單、直觀、明了。需要說明的是，文中一直提到的距離這個(gè)概念，指的是閔可夫斯基距離（Minkowski distance），對(duì)應(yīng)數(shù)學(xué)上的Lp范數(shù)。
? ? ? 當(dāng)p=1時(shí)，為曼哈頓距離（Manhattan distance），也稱L1距離；
? ? ? 當(dāng)p=2時(shí)，為歐式距離（Euclidean distance），也稱L2距離；
? ? ? 當(dāng)p=∞時(shí)，為切比雪夫距離（distance）。
? ? ??在我們使用kNN算法時(shí)，常用L1距離和L2距離，且以L2距離使用更多。
三、算法評(píng)價(jià)
? ? ? 優(yōu)點(diǎn)：kNN是最簡單、最有效的分類器；精度高；對(duì)異常值（邊緣值）不敏感。
? ? ? 缺點(diǎn)：需要記錄所有訓(xùn)練集的數(shù)據(jù)，空間復(fù)雜度高；需要進(jìn)行大量的計(jì)算，計(jì)算復(fù)雜度高；無法提取出數(shù)據(jù)內(nèi)涵的結(jié)構(gòu)信息。
? ? ? 注意點(diǎn)：由于計(jì)算距離時(shí)使用的是離散型數(shù)據(jù)，所以kNN算法常用于特征值為數(shù)值型和標(biāo)稱型的數(shù)據(jù)。如果數(shù)據(jù)特征值為連續(xù)值，則需要根據(jù)實(shí)際情況，對(duì)特征值進(jìn)行離散采樣或者采用其他算法模型。
