一、KNN算法原理
KNN算法是選擇與輸入樣本在特征空間內(nèi)最近鄰的k個訓(xùn)練樣本并根據(jù)一定的決策規(guī)則，給出輸出結(jié)果 。
決策規(guī)則：
????分類任務(wù)：輸出結(jié)果為k個訓(xùn)練樣本中占大多數(shù)的類 。
????回歸任務(wù)：輸出結(jié)果為k個訓(xùn)練樣本值的平均值 。
如下圖所示房價預(yù)測任務(wù)：
二、KNN算法步驟
回歸：
? ? ? ? ? 1、計算待預(yù)測樣本與訓(xùn)練集的每個樣本的距離
????????? 2、將訓(xùn)練集的樣本按照距離從小到大排序
? ? ? ? ? 3、取前K個距離最小的訓(xùn)練樣本，計算平均值
分類：
???????????1、計算已知類別數(shù)據(jù)集中的點與當(dāng)前點之間的距離；
????????????2、按照距離遞增依次排序；
????????????3、選取與當(dāng)前點距離最小的K個點；
????????????4、確定前k個點所在類別的出現(xiàn)頻率；
????????????5、返回前k個點出現(xiàn)頻率最高的類別作為當(dāng)前點的預(yù)測分類
三、KNN算法三要素
K值的選擇、距離度量和分類決策規(guī)則是K近鄰算法的三個基本要素。當(dāng)三個要素確定后，對于任何一個新的輸入實例，它所屬的Y值也確定了，本節(jié)介紹了三要素的含義。
?1、K值的選擇：
K取值較小時，模型復(fù)雜度高，訓(xùn)練誤差會減小，泛化能力減弱；K取值較大時，模型復(fù)雜度低，訓(xùn)練誤差會增大，泛化能力有一定的提高。KNN模型的復(fù)雜度可以通過對噪聲的容忍度來理解，若模型對噪聲很敏感，則模型的復(fù)雜度高；反之，模型的復(fù)雜度低。為了更好理解模型復(fù)雜度的含義，我們?nèi)∫粋€極端，分析K=1和K="樣本數(shù)"的模型復(fù)雜度。
通過上面兩種極端的K選取結(jié)果可知，K值選擇應(yīng)適中，K值一般小于20，建議采用交叉驗證的方法選取合適的K值。
2、距離的度量：
KNN算法用距離來度量兩個樣本間的相似度。
常用的距離表示方法：
可以看出，歐式距離是閔可夫斯基距離在p=2時的特例，而曼哈頓距離是p=1時的特例 。
3. 分類決策規(guī)則：
KNN算法一般是用多數(shù)表決方法，即由輸入實例的K個鄰近的多數(shù)類決定輸入實例的類。這種思想也是經(jīng)驗風(fēng)險最小化的結(jié)果。
訓(xùn)練樣本為(xi , yi)。當(dāng)輸入實例為 x，標(biāo)記為c，是輸入實例x的k近鄰訓(xùn)練樣本集。
我們定義訓(xùn)練誤差率是K近鄰訓(xùn)練樣本標(biāo)記與輸入標(biāo)記不一致的比例，誤差率表示為：
因此，要使誤差率最小化即經(jīng)驗風(fēng)險最小，就要使(2.1)式右端的最大，即K近鄰的標(biāo)記值盡可能的與輸入標(biāo)記一致，所以多數(shù)表決規(guī)則等價于經(jīng)驗風(fēng)險最小化。
四、KNN算法優(yōu)缺點
優(yōu)點：
1）算法簡單，理論成熟，可用于分類和回歸。
2）對異常值不敏感。
3）可用于非線性分類。
4）比較適用于容量較大的訓(xùn)練數(shù)據(jù)，容量較小的訓(xùn)練數(shù)據(jù)則很容易出現(xiàn)誤分類情況。
5）KNN算法原理是根據(jù)鄰域的K個樣本來確定輸出類別，因此對于不同類的樣本集有交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為合適。
缺點：
1）時間復(fù)雜度和空間復(fù)雜度高。
2）訓(xùn)練樣本不平衡，對稀有類別的預(yù)測準(zhǔn)確率低。
3）相比決策樹模型，KNN模型可解釋性不強。
附帶代碼：K近鄰(KNN)-代碼 - 簡書
