一、KNN算法概述

最近鄰算法，或者說K最近鄰(KNN，K-NearestNeighbor)分類算法是數(shù)據(jù)挖掘分類技術(shù)中最簡(jiǎn)單的方法之一。所謂K最近鄰，就是K個(gè)最近的鄰居的意思，說的是每個(gè)樣本都可以用它最接近的K個(gè)鄰居來代表。KNN是一種分類(classification)算法，它輸入基于實(shí)例的學(xué)習(xí)（instance-based learning），屬于懶惰學(xué)習(xí)（lazy learning）；即KNN沒有顯式的學(xué)習(xí)過程，也就是說沒有訓(xùn)練階段，沒有要學(xué)習(xí)的參數(shù)，直接進(jìn)行推理 / 測(cè)試。數(shù)據(jù)集事先已有了特征值和分類標(biāo)簽，待收到新樣本后直接進(jìn)行處理。與急切學(xué)習(xí)（eager learning）相對(duì)應(yīng)。

KNN是通過計(jì)算不同樣本的距離進(jìn)行分類的 , 其思路是：

如果一個(gè)樣本在特征空間中的K個(gè)最鄰近的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也劃分為這個(gè)類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對(duì)象。該方法在決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。
　　提到KNN，網(wǎng)上最常見的就是下面這個(gè)圖，可以幫助大家理解。
　　我們要確定綠點(diǎn)屬于哪個(gè)顏色（紅色或者藍(lán)色），要做的就是選出距離目標(biāo)點(diǎn)距離最近的K個(gè)點(diǎn)，看這K個(gè)點(diǎn)的大多數(shù)顏色是什么顏色。當(dāng)K取3的時(shí)候，我們可以看出距離最近的三個(gè)，分別是紅色、紅色、藍(lán)色，因此得到目標(biāo)點(diǎn)為紅色。

算法的描述：

1）計(jì)算測(cè)試數(shù)據(jù)與各個(gè)訓(xùn)練數(shù)據(jù)之間的距離；
2）按照距離的遞增關(guān)系進(jìn)行排序；
3）選取距離最小的K個(gè)點(diǎn)；
4）確定前K個(gè)點(diǎn)所在類別的出現(xiàn)頻率；
5）返回前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為測(cè)試數(shù)據(jù)的預(yù)測(cè)分類

二、關(guān)于K的取值

K：臨近數(shù)，即在預(yù)測(cè)目標(biāo)點(diǎn)時(shí)取幾個(gè)臨近的點(diǎn)來預(yù)測(cè)。
K值得選取非常重要，因?yàn)椋?br> （1）如果當(dāng)K的取值過小時(shí)，一旦有噪聲得成分存在們將會(huì)對(duì)預(yù)測(cè)產(chǎn)生比較大影響，例如取K值為1時(shí)，一旦最近的一個(gè)點(diǎn)是噪聲，那么就會(huì)出現(xiàn)偏差，K值的減小就意味著整體模型變得復(fù)雜，容易發(fā)生過擬合；
（2）如果K的值取的過大時(shí)，就相當(dāng)于用較大鄰域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)，學(xué)習(xí)的近似誤差會(huì)增大。這時(shí)與輸入目標(biāo)點(diǎn)較遠(yuǎn)實(shí)例也會(huì)對(duì)預(yù)測(cè)起作用，使預(yù)測(cè)發(fā)生錯(cuò)誤。K值的增大就意味著整體的模型變得簡(jiǎn)單；
（3）如果K==N的時(shí)候，那么就是取全部的實(shí)例，即為取實(shí)例中某分類下最多的點(diǎn)，就對(duì)預(yù)測(cè)沒有什么實(shí)際的意義了；
　　K的取值盡量要取奇數(shù)，以保證在計(jì)算結(jié)果最后會(huì)產(chǎn)生一個(gè)較多的類別，如果取偶數(shù)可能會(huì)產(chǎn)生相等的情況，不利于預(yù)測(cè)。

K的取法：

常用的方法是從k=1開始，使用驗(yàn)證集估計(jì)分類器的誤差率。重復(fù)該過程，每次K增值1，允許增加一個(gè)近鄰。選取產(chǎn)生最小誤差率的K。一般k的取值不超過20，上限是n的開方，隨著數(shù)據(jù)集的增大，K的值也要增大。
注：從驗(yàn)證集中學(xué)習(xí)超參數(shù)K

三、關(guān)于距離的選取

① Euclidean Distance（歐幾里得距離）L2
② Manhattan distance（曼哈頓距離） L1

四、總結(jié)

• KNN算法是最簡(jiǎn)單有效的分類算法，簡(jiǎn)單且容易實(shí)現(xiàn)。當(dāng)訓(xùn)練數(shù)據(jù)集很大時(shí)，需要大量的存儲(chǔ)空間，而且需要計(jì)算待測(cè)樣本和訓(xùn)練數(shù)據(jù)集中所有樣本的距離，所以非常耗時(shí)。
• KNN對(duì)于隨機(jī)分布的數(shù)據(jù)集分類效果較差，對(duì)于類內(nèi)間距小，類間間距大的數(shù)據(jù)集分類效果好，而且對(duì)于邊界不規(guī)則的數(shù)據(jù)效果好于線性分類器。
• KNN對(duì)于樣本不均衡的數(shù)據(jù)效果不好，需要進(jìn)行改進(jìn)。改進(jìn)的方法時(shí)對(duì)K個(gè)近鄰數(shù)據(jù)賦予權(quán)重，比如距離測(cè)試樣本越近，權(quán)重越大。
• KNN很耗時(shí)，時(shí)間復(fù)雜度為O(n)，一般適用于樣本數(shù)較少的數(shù)據(jù)集，當(dāng)數(shù)據(jù)量大時(shí)，可以將數(shù)據(jù)以樹的形式呈現(xiàn)，能提高速度，常用的有kd-tree和ball-tree。