機(jī)器學(xué)習(xí)十大經(jīng)典算法之KNN最近鄰算法

KNN簡(jiǎn)介

KNN（K-NearestNeighbor）是機(jī)器學(xué)習(xí)入門級(jí)的分類算法，非常簡(jiǎn)單。它實(shí)現(xiàn)將距離近的樣本點(diǎn)劃為同一類別；KNN中的K指的是近鄰個(gè)數(shù)，也就是最近的K個(gè)點(diǎn) ；根據(jù)它距離最近的K個(gè)點(diǎn)是什么類別來判斷屬于哪個(gè)類別。

KNN算法步驟

我們有一堆樣本點(diǎn)，類別已知，如下圖左，藍(lán)色為一類，黃色為另一類。現(xiàn)在有個(gè)新樣本點(diǎn)，也就是圖中黑色的叉叉，需要判斷它屬于哪一類。

KNN做的就是選出距離目標(biāo)點(diǎn)黑叉叉距離最近的k個(gè)點(diǎn)，看這k個(gè)點(diǎn)的大多數(shù)顏色是什么顏色。這里的距離用歐氏距離來度量。

給定兩個(gè)樣本 和 ，其中n表示特征數(shù) ，X和Y兩個(gè)向量間的歐氏距離(Euclidean Distance)表示為：

當(dāng)我們?cè)O(shè)定k=1時(shí)，距離目標(biāo)點(diǎn)最近的點(diǎn)是黃色，就認(rèn)為目標(biāo)點(diǎn)屬于黃色那類。當(dāng)k設(shè)為3時(shí)，我們可以看到距離最近的三個(gè)點(diǎn)，有兩個(gè)是藍(lán)色，一個(gè)是黃色，因此認(rèn)為目標(biāo)點(diǎn)屬于藍(lán)色的一類。

所以，K的選擇不同，得到的結(jié)果也會(huì)不同。

K值選擇

KNN的決策邊界一般不是線性的，也就是說KNN是一種非線性分類器，如下圖。

K越小越容易過擬合，當(dāng)K=1時(shí)，這時(shí)只根據(jù)單個(gè)近鄰進(jìn)行預(yù)測(cè)，如果離目標(biāo)點(diǎn)最近的一個(gè)點(diǎn)是噪聲，就會(huì)出錯(cuò)，此時(shí)模型復(fù)雜度高，穩(wěn)健性低，決策邊界崎嶇。

但是如果K取的過大，這時(shí)與目標(biāo)點(diǎn)較遠(yuǎn)的樣本點(diǎn)也會(huì)對(duì)預(yù)測(cè)起作用，就會(huì)導(dǎo)致欠擬合，此時(shí)模型變得簡(jiǎn)單，決策邊界變平滑。

尋找最合適的K值，比較經(jīng)典的方法是N折交叉驗(yàn)證。

上圖展示的是5折交叉驗(yàn)證，也就是將已知樣本集等分為5份，其中4份作為訓(xùn)練集，1份為驗(yàn)證集，做出5個(gè)模型。

具體過程

將樣本數(shù)據(jù)按照一定比例，拆分出訓(xùn)練用的數(shù)據(jù)和驗(yàn)證用的數(shù)據(jù)，比如6：4拆分出部分訓(xùn)練數(shù)據(jù)和驗(yàn)證數(shù)據(jù)，從選取一個(gè)較小的K值開始，不斷增加K的值，然后計(jì)算驗(yàn)證集合的方差，最終找到一個(gè)比較合適的K值。

通過交叉驗(yàn)證計(jì)算方差后你大致會(huì)得到下面這樣的圖：

由上圖可知，當(dāng)你增大k的時(shí)候，一般錯(cuò)誤率會(huì)先降低，因?yàn)橛兄車嗟臉颖究梢越梃b了，分類效果會(huì)變好。但注意，和K-means不一樣，當(dāng)K值更大的時(shí)候，錯(cuò)誤率會(huì)更高。這也很好理解，比如說你一共就35個(gè)樣本，當(dāng)你K增大到30的時(shí)候，KNN基本上就沒意義了。

所以選擇K點(diǎn)的時(shí)候可以選擇一個(gè)較大的臨界K點(diǎn)，當(dāng)它繼續(xù)增大或減小的時(shí)候，錯(cuò)誤率都會(huì)上升，比如圖中的K=10。

PS:處理數(shù)據(jù)要先對(duì)其進(jìn)行標(biāo)準(zhǔn)化

也可以采用標(biāo)準(zhǔn)差標(biāo)準(zhǔn)化：

KNN優(yōu)缺點(diǎn)

KNN的優(yōu)點(diǎn)在于原理簡(jiǎn)單，容易實(shí)現(xiàn)，對(duì)于邊界不規(guī)則數(shù)據(jù)的分類效果好于線性分類器。

缺點(diǎn)：

• 要保存全部數(shù)據(jù)集，需要大量的存儲(chǔ)空間；
• 需要計(jì)算每個(gè)未知點(diǎn)到全部已知點(diǎn)的距離，非常耗時(shí)；
• 對(duì)于不平衡數(shù)據(jù)效果不好，需要進(jìn)行改進(jìn)；
• 不適用于特征空間維度高的情況。

代碼實(shí)現(xiàn)

偽代碼

對(duì)測(cè)試樣本點(diǎn)進(jìn)行以下操作：

(1)計(jì)算已知類別數(shù)據(jù)集中的點(diǎn)與當(dāng)前點(diǎn)之間的距離；

(2)按照距離遞增次序排序；

(3)選取與當(dāng)前點(diǎn)距離最小的k個(gè)點(diǎn)；

(4)確定前k個(gè)點(diǎn)所在類別的出現(xiàn)頻率；

(5)返回前k個(gè)點(diǎn)出現(xiàn)頻率最高的類別作為當(dāng)前點(diǎn)的預(yù)測(cè)分類。

具體實(shí)現(xiàn)

https://github.com/GreedyAIAcademy/Machine-Learning/tree/master/2.KNN

參考文章

https://www.cnblogs.com/listenfwind/p/10311496.html