一、KNN算法原理
KNN算法是選擇與輸入樣本在特征空間內(nèi)最近鄰的k個(gè)訓(xùn)練樣本并根據(jù)一定的決策規(guī)則，給出輸出結(jié)果 及皂。
決策規(guī)則：
????分類(lèi)任務(wù)：輸出結(jié)果為k個(gè)訓(xùn)練樣本中占大多數(shù)的類(lèi) 验烧。
????回歸任務(wù)：輸出結(jié)果為k個(gè)訓(xùn)練樣本值的平均值 碍拆。
如下圖所示房?jī)r(jià)預(yù)測(cè)任務(wù)：
二、KNN算法步驟
回歸：
? ? ? ? ? 1近哟、計(jì)算待預(yù)測(cè)樣本與訓(xùn)練集的每個(gè)樣本的距離
????????? 2吉执、將訓(xùn)練集的樣本按照距離從小到大排序
? ? ? ? ? 3戳玫、取前K個(gè)距離最小的訓(xùn)練樣本币绩，計(jì)算平均值
分類(lèi)：
???????????1缆镣、計(jì)算已知類(lèi)別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離董瞻；
????????????2、按照距離遞增依次排序眠蚂；
????????????3逝慧、選取與當(dāng)前點(diǎn)距離最小的K個(gè)點(diǎn)笛臣；
????????????4、確定前k個(gè)點(diǎn)所在類(lèi)別的出現(xiàn)頻率诞丽；
????????????5、返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類(lèi)別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類(lèi)
三懂衩、KNN算法三要素
K值的選擇浊洞、距離度量和分類(lèi)決策規(guī)則是K近鄰算法的三個(gè)基本要素枷餐。當(dāng)三個(gè)要素確定后毛肋，對(duì)于任何一個(gè)新的輸入實(shí)例惊暴，它所屬的Y值也確定了辽话，本節(jié)介紹了三要素的含義典徘。
?1逮诲、K值的選擇：
K取值較小時(shí)，模型復(fù)雜度高齐唆，訓(xùn)練誤差會(huì)減小，泛化能力減弱锭弊；K取值較大時(shí)，模型復(fù)雜度低桃犬，訓(xùn)練誤差會(huì)增大土匀，泛化能力有一定的提高就轧。KNN模型的復(fù)雜度可以通過(guò)對(duì)噪聲的容忍度來(lái)理解，若模型對(duì)噪聲很敏感，則模型的復(fù)雜度高惋啃；反之，模型的復(fù)雜度低。為了更好理解模型復(fù)雜度的含義椭坚，我們?nèi)∫粋€(gè)極端，分析K=1和K="樣本數(shù)"的模型復(fù)雜度垂涯。
通過(guò)上面兩種極端的K選取結(jié)果可知尿背，K值選擇應(yīng)適中残家，K值一般小于20陪捷，建議采用交叉驗(yàn)證的方法選取合適的K值啡直。
2、距離的度量：
KNN算法用距離來(lái)度量?jī)蓚€(gè)樣本間的相似度。
常用的距離表示方法：
可以看出早芭，歐式距離是閔可夫斯基距離在p=2時(shí)的特例，而曼哈頓距離是p=1時(shí)的特例 司抱。
3. 分類(lèi)決策規(guī)則：
KNN算法一般是用多數(shù)表決方法资溃，即由輸入實(shí)例的K個(gè)鄰近的多數(shù)類(lèi)決定輸入實(shí)例的類(lèi)溶锭。這種思想也是經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化的結(jié)果拱绑。
訓(xùn)練樣本為(xi , yi)。當(dāng)輸入實(shí)例為 x猎拨，標(biāo)記為c膀藐，是輸入實(shí)例x的k近鄰訓(xùn)練樣本集。
我們定義訓(xùn)練誤差率是K近鄰訓(xùn)練樣本標(biāo)記與輸入標(biāo)記不一致的比例红省，誤差率表示為：
因此额各，要使誤差率最小化即經(jīng)驗(yàn)風(fēng)險(xiǎn)最小，就要使(2.1)式右端的最大吧恃，即K近鄰的標(biāo)記值盡可能的與輸入標(biāo)記一致虾啦，所以多數(shù)表決規(guī)則等價(jià)于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化。
四蚜枢、KNN算法優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
1）算法簡(jiǎn)單缸逃，理論成熟针饥，可用于分類(lèi)和回歸厂抽。
2）對(duì)異常值不敏感。
3）可用于非線性分類(lèi)丁眼。
4）比較適用于容量較大的訓(xùn)練數(shù)據(jù)筷凤，容量較小的訓(xùn)練數(shù)據(jù)則很容易出現(xiàn)誤分類(lèi)情況。
5）KNN算法原理是根據(jù)鄰域的K個(gè)樣本來(lái)確定輸出類(lèi)別苞七，因此對(duì)于不同類(lèi)的樣本集有交叉或重疊較多的待分樣本集來(lái)說(shuō)藐守，KNN方法較其他方法更為合適。
缺點(diǎn)：
1）時(shí)間復(fù)雜度和空間復(fù)雜度高蹂风。
2）訓(xùn)練樣本不平衡卢厂，對(duì)稀有類(lèi)別的預(yù)測(cè)準(zhǔn)確率低。
3）相比決策樹(shù)模型惠啄，KNN模型可解釋性不強(qiáng)慎恒。
