K近鄰法(k-nearst neighbors,KNN)是一種很基本的機(jī)器學(xué)習(xí)方法了，在我們平常的生活中也會(huì)不自主的應(yīng)用。比如，我們判斷一個(gè)人的人品，只需要觀察他來往最密切的幾個(gè)人的人品好壞就可以得出了。這里就運(yùn)用了KNN的思想。KNN方法既可以做分類，也可以做回歸，這點(diǎn)和決策樹算法相同。

　　　　KNN做回歸和分類的主要區(qū)別在于最后做預(yù)測(cè)時(shí)候的決策方式不同。KNN做分類預(yù)測(cè)時(shí)，一般是選擇多數(shù)表決法，即訓(xùn)練集里和預(yù)測(cè)的樣本特征最近的K個(gè)樣本，預(yù)測(cè)為里面有最多類別數(shù)的類別。而KNN做回歸時(shí)，一般是選擇平均法，即最近的K個(gè)樣本的樣本輸出的平均值作為回歸預(yù)測(cè)值。由于兩者區(qū)別不大，雖然本文主要是講解KNN的分類方法，但思想對(duì)KNN的回歸方法也適用。由于scikit-learn里只使用了蠻力實(shí)現(xiàn)(brute-force)，KD樹實(shí)現(xiàn)(KDTree)和球樹(BallTree)實(shí)現(xiàn)，本文只討論這幾種算法的實(shí)現(xiàn)原理。其余的實(shí)現(xiàn)方法比如BBF樹，MVP樹等，在這里不做討論。

1. KNN算法三要素

　　　　KNN算法我們主要要考慮三個(gè)重要的要素，對(duì)于固定的訓(xùn)練集，只要這三點(diǎn)確定了，算法的預(yù)測(cè)方式也就決定了。這三個(gè)最終的要素是k值的選取，距離度量的方式和分類決策規(guī)則。

　　　　對(duì)于分類決策規(guī)則，一般都是使用前面提到的多數(shù)表決法。所以我們重點(diǎn)是關(guān)注與k值的選擇和距離的度量方式。

?

　　　　對(duì)于k值的選擇，沒有一個(gè)固定的經(jīng)驗(yàn)，一般根據(jù)樣本的分布，選擇一個(gè)較小的值，可以通過交叉驗(yàn)證選擇一個(gè)合適的k值。

　　　　選擇較小的k值，就相當(dāng)于用較小的領(lǐng)域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)，訓(xùn)練誤差會(huì)減小，只有與輸入實(shí)例較近或相似的訓(xùn)練實(shí)例才會(huì)對(duì)預(yù)測(cè)結(jié)果起作用，與此同時(shí)帶來的問題是泛化誤差會(huì)增大，換句話說，K值的減小就意味著整體模型變得復(fù)雜，容易發(fā)生過擬合；
　　　　選擇較大的k值，就相當(dāng)于用較大領(lǐng)域中的訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè)，其優(yōu)點(diǎn)是可以減少泛化誤差，但缺點(diǎn)是訓(xùn)練誤差會(huì)增大。這時(shí)候，與輸入實(shí)例較遠(yuǎn)（不相似的）訓(xùn)練實(shí)例也會(huì)對(duì)預(yù)測(cè)器作用，使預(yù)測(cè)發(fā)生錯(cuò)誤，且K值的增大就意味著整體的模型變得簡單。
　　　　一個(gè)極端是k等于樣本數(shù)m，則完全沒有分類，此時(shí)無論輸入實(shí)例是什么，都只是簡單的預(yù)測(cè)它屬于在訓(xùn)練實(shí)例中最多的類，模型過于簡單。

?

　　　　對(duì)于距離的度量，我們有很多的距離度量方式，但是最常用的是歐式距離，即對(duì)于兩個(gè)n維向量x和y，兩者的歐式距離定義為：

D(x,y)=(x1?y1)2+(x2?y2)2+...+(xn?yn)2???????????????????????????????√=∑i=1n(xi?yi)2??????????√D(x,y)=(x1?y1)2+(x2?y2)2+...+(xn?yn)2=∑i=1n(xi?yi)2

　　　　大多數(shù)情況下，歐式距離可以滿足我們的需求，我們不需要再去操心距離的度量。

　　　　當(dāng)然我們也可以用他的距離度量方式。比如曼哈頓距離，定義為：

D(x,y)=|x1?y1|+|x2?y2|+...+|xn?yn|=∑i=1n|xi?yi|D(x,y)=|x1?y1|+|x2?y2|+...+|xn?yn|=∑i=1n|xi?yi|

　　　　更加通用點(diǎn)，比如閔可夫斯基距離(Minkowski Distance)，定義為：

D(x,y)=(|x1?y1|)p+(|x2?y2|)p+...+(|xn?yn|)p??????????????????????????????????√p=∑i=1n(|xi?yi|)p???????????√pD(x,y)=(|x1?y1|)p+(|x2?y2|)p+...+(|xn?yn|)pp=∑i=1n(|xi?yi|)pp

　　　　可以看出，歐式距離是閔可夫斯基距離距離在p=2時(shí)的特例，而曼哈頓距離是p=1時(shí)的特例。

2. KNN算法蠻力實(shí)現(xiàn)

　　　　從本節(jié)起，我們開始討論KNN算法的實(shí)現(xiàn)方式。首先我們看看最想當(dāng)然的方式。

　　　　既然我們要找到k個(gè)最近的鄰居來做預(yù)測(cè)，那么我們只需要計(jì)算預(yù)測(cè)樣本和所有訓(xùn)練集中的樣本的距離，然后計(jì)算出最小的k個(gè)距離即可，接著多數(shù)表決，很容易做出預(yù)測(cè)。這個(gè)方法的確簡單直接，在樣本量少，樣本特征少的時(shí)候有效。但是在實(shí)際運(yùn)用中很多時(shí)候用不上，為什么呢？因?yàn)槲覀兘?jīng)常碰到樣本的特征數(shù)有上千以上，樣本量有幾十萬以上，如果我們這要去預(yù)測(cè)少量的測(cè)試集樣本，算法的時(shí)間效率很成問題。因此，這個(gè)方法我們一般稱之為蠻力實(shí)現(xiàn)。比較適合于少量樣本的簡單模型的時(shí)候用。

　　　　既然蠻力實(shí)現(xiàn)在特征多，樣本多的時(shí)候很有局限性，那么我們有沒有其他的好辦法呢？有！這里我們講解兩種辦法，一個(gè)是KD樹實(shí)現(xiàn)，一個(gè)是球樹實(shí)現(xiàn)。

3. KNN算法之KD樹實(shí)現(xiàn)原理

　　　　KD樹算法沒有一開始就嘗試對(duì)測(cè)試樣本分類，而是先對(duì)訓(xùn)練集建模，建立的模型就是KD樹，建好了模型再對(duì)測(cè)試集做預(yù)測(cè)。所謂的KD樹就是K個(gè)特征維度的樹，注意這里的K和KNN中的K的意思不同。KNN中的K代表特征輸出類別，KD樹中的K代表樣本特征的維數(shù)。為了防止混淆，后面我們稱特征維數(shù)為n。

　　　　KD樹算法包括三步，第一步是建樹，第二部是搜索最近鄰，最后一步是預(yù)測(cè)。

3.1 KD樹的建立

　　　　我們首先來看建樹的方法。KD樹建樹采用的是從m個(gè)樣本的n維特征中，分別計(jì)算n個(gè)特征的取值的方差，用方差最大的第k維特征nknk來作為根節(jié)點(diǎn)。對(duì)于這個(gè)特征，我們選擇特征nknk的取值的中位數(shù)nkvnkv對(duì)應(yīng)的樣本作為劃分點(diǎn)，對(duì)于所有第k維特征的取值小于nkvnkv的樣本，我們劃入左子樹，對(duì)于第k維特征的取值大于等于nkvnkv的樣本，我們劃入右子樹，對(duì)于左子樹和右子樹，我們采用和剛才同樣的辦法來找方差最大的特征來做更節(jié)點(diǎn)，遞歸的生成KD樹。

　　　　具體流程如下圖：

　　　　比如我們有二維樣本6個(gè)，{(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)}，構(gòu)建kd樹的具體步驟為：

　　　　1）找到劃分的特征。6個(gè)數(shù)據(jù)點(diǎn)在x，y維度上的數(shù)據(jù)方差分別為6.97，5.37，所以在x軸上方差更大，用第1維特征建樹。

　　　　2）確定劃分點(diǎn)（7,2）。根據(jù)x維上的值將數(shù)據(jù)排序，6個(gè)數(shù)據(jù)的中值(所謂中值，即中間大小的值)為7，所以劃分點(diǎn)的數(shù)據(jù)是（7,2）。這樣，該節(jié)點(diǎn)的分割超平面就是通過（7,2）并垂直于：劃分點(diǎn)維度的直線x=7；

　　　　3）確定左子空間和右子空間。 分割超平面x=7將整個(gè)空間分為兩部分：x<=7的部分為左子空間，包含3個(gè)節(jié)點(diǎn)={(2,3),(5,4),(4,7)}；另一部分為右子空間，包含2個(gè)節(jié)點(diǎn)={(9,6)，(8,1)}。

　　　　4）用同樣的辦法劃分左子樹的節(jié)點(diǎn){(2,3),(5,4),(4,7)}和右子樹的節(jié)點(diǎn){(9,6)，(8,1)}。最終得到KD樹。

?

　　　　最后得到的KD樹如下：

3.2 KD樹搜索最近鄰　　

　　　　當(dāng)我們生成KD樹以后，就可以去預(yù)測(cè)測(cè)試集里面的樣本目標(biāo)點(diǎn)了。對(duì)于一個(gè)目標(biāo)點(diǎn)，我們首先在KD樹里面找到包含目標(biāo)點(diǎn)的葉子節(jié)點(diǎn)。以目標(biāo)點(diǎn)為圓心，以目標(biāo)點(diǎn)到葉子節(jié)點(diǎn)樣本實(shí)例的距離為半徑，得到一個(gè)超球體，最近鄰的點(diǎn)一定在這個(gè)超球體內(nèi)部。然后返回葉子節(jié)點(diǎn)的父節(jié)點(diǎn)，檢查另一個(gè)子節(jié)點(diǎn)包含的超矩形體是否和超球體相交，如果相交就到這個(gè)子節(jié)點(diǎn)尋找是否有更加近的近鄰,有的話就更新最近鄰。如果不相交那就簡單了，我們直接返回父節(jié)點(diǎn)的父節(jié)點(diǎn)，在另一個(gè)子樹繼續(xù)搜索最近鄰。當(dāng)回溯到根節(jié)點(diǎn)時(shí)，算法結(jié)束，此時(shí)保存的最近鄰節(jié)點(diǎn)就是最終的最近鄰。

　　　　從上面的描述可以看出，KD樹劃分后可以大大減少無效的最近鄰搜索，很多樣本點(diǎn)由于所在的超矩形體和超球體不相交，根本不需要計(jì)算距離。大大節(jié)省了計(jì)算時(shí)間。

　　　　我們用3.1建立的KD樹，來看對(duì)點(diǎn)(2,4.5)找最近鄰的過程。

　　　　先進(jìn)行二叉查找，先從（7,2）查找到（5,4）節(jié)點(diǎn)，在進(jìn)行查找時(shí)是由y = 4為分割超平面的，由于查找點(diǎn)為y值為4.5，因此進(jìn)入右子空間查找到（4,7），形成搜索路徑<(7,2)，(5,4)，(4,7)>，但 （4,7）與目標(biāo)查找點(diǎn)的距離為3.202，而（5,4）與查找點(diǎn)之間的距離為3.041，所以（5,4）為查詢點(diǎn)的最近點(diǎn)；?以（2，4.5）為圓心，以3.041為半徑作圓，如下圖所示。可見該圓和y = 4超平面交割，所以需要進(jìn)入（5,4）左子空間進(jìn)行查找，也就是將（2,3）節(jié)點(diǎn)加入搜索路徑中得<(7,2)，(2,3)>；于是接著搜索至（2,3）葉子節(jié)點(diǎn)，（2,3）距離（2,4.5）比（5,4）要近，所以最近鄰點(diǎn)更新為（2，3），最近距離更新為1.5；回溯查找至（5,4），直到最后回溯到根結(jié)點(diǎn)（7,2）的時(shí)候，以（2,4.5）為圓心1.5為半徑作圓，并不和x = 7分割超平面交割，如下圖所示。至此，搜索路徑回溯完，返回最近鄰點(diǎn)（2,3），最近距離1.5。

　　　　對(duì)應(yīng)的圖如下：

　　　　

3.3 KD樹預(yù)測(cè)　

　　　　有了KD樹搜索最近鄰的辦法，KD樹的預(yù)測(cè)就很簡單了，在KD樹搜索最近鄰的基礎(chǔ)上，我們選擇到了第一個(gè)最近鄰樣本，就把它置為已選。在第二輪中，我們忽略置為已選的樣本，重新選擇最近鄰，這樣跑k次，就得到了目標(biāo)的K個(gè)最近鄰，然后根據(jù)多數(shù)表決法，如果是KNN分類，預(yù)測(cè)為K個(gè)最近鄰里面有最多類別數(shù)的類別。如果是KNN回歸，用K個(gè)最近鄰樣本輸出的平均值作為回歸預(yù)測(cè)值。

4. KNN算法之球樹實(shí)現(xiàn)原理

　　　　KD樹算法雖然提高了KNN搜索的效率，但是在某些時(shí)候效率并不高，比如當(dāng)處理不均勻分布的數(shù)據(jù)集時(shí),不管是近似方形，還是矩形，甚至正方形，都不是最好的使用形狀，因?yàn)樗麄兌加薪恰Ｒ粋€(gè)例子如下圖：

　　　　如果黑色的實(shí)例點(diǎn)離目標(biāo)點(diǎn)星點(diǎn)再遠(yuǎn)一點(diǎn)，那么虛線圓會(huì)如紅線所示那樣擴(kuò)大，導(dǎo)致與左上方矩形的右下角相交，既然相 交了，那么就要檢查這個(gè)左上方矩形，而實(shí)際上，最近的點(diǎn)離星點(diǎn)的距離很近，檢查左上方矩形區(qū)域已是多余。于此我們看見，KD樹把二維平面劃分成一個(gè)一個(gè)矩形，但矩形區(qū)域的角卻是個(gè)難以處理的問題。

　　　　為了優(yōu)化超矩形體導(dǎo)致的搜索效率的問題，牛人們引入了球樹，這種結(jié)構(gòu)可以優(yōu)化上面的這種問題。

　　　　我們現(xiàn)在來看看球樹建樹和搜索最近鄰的算法。

4.1 球樹的建立

　　　　球樹，顧名思義，就是每個(gè)分割塊都是超球體，而不是KD樹里面的超矩形體。

　　　　我們看看具體的建樹流程：

　　　　1) 先構(gòu)建一個(gè)超球體，這個(gè)超球體是可以包含所有樣本的最小球體。

　　　　2) 從球中選擇一個(gè)離球的中心最遠(yuǎn)的點(diǎn)，然后選擇第二個(gè)點(diǎn)離第一個(gè)點(diǎn)最遠(yuǎn)，將球中所有的點(diǎn)分配到離這兩個(gè)聚類中心最近的一個(gè)上，然后計(jì)算每個(gè)聚類的中心，以及聚類能夠包含它所有數(shù)據(jù)點(diǎn)所需的最小半徑。這樣我們得到了兩個(gè)子超球體，和KD樹里面的左右子樹對(duì)應(yīng)。

　　　　3)對(duì)于這兩個(gè)子超球體，遞歸執(zhí)行步驟2). 最終得到了一個(gè)球樹。

　　　　可以看出KD樹和球樹類似，主要區(qū)別在于球樹得到的是節(jié)點(diǎn)樣本組成的最小超球體，而KD得到的是節(jié)點(diǎn)樣本組成的超矩形體，這個(gè)超球體要與對(duì)應(yīng)的KD樹的超矩形體小，這樣在做最近鄰搜索的時(shí)候，可以避免一些無謂的搜索。

4.2 球樹搜索最近鄰

　　　　? 使用球樹找出給定目標(biāo)點(diǎn)的最近鄰方法是首先自上而下貫穿整棵樹找出包含目標(biāo)點(diǎn)所在的葉子，并在這個(gè)球里找出與目標(biāo)點(diǎn)最鄰近的點(diǎn)，這將確定出目標(biāo)點(diǎn)距離它的最近鄰點(diǎn)的一個(gè)上限值，然后跟KD樹查找一樣，檢查兄弟結(jié)點(diǎn)，如果目標(biāo)點(diǎn)到兄弟結(jié)點(diǎn)中心的距離超過兄弟結(jié)點(diǎn)的半徑與當(dāng)前的上限值之和，那么兄弟結(jié)點(diǎn)里不可能存在一個(gè)更近的點(diǎn)；否則的話，必須進(jìn)一步檢查位于兄弟結(jié)點(diǎn)以下的子樹。

　　　　檢查完兄弟節(jié)點(diǎn)后，我們向父節(jié)點(diǎn)回溯，繼續(xù)搜索最小鄰近值。當(dāng)回溯到根節(jié)點(diǎn)時(shí)，此時(shí)的最小鄰近值就是最終的搜索結(jié)果。

　　　　從上面的描述可以看出，KD樹在搜索路徑優(yōu)化時(shí)使用的是兩點(diǎn)之間的距離來判斷，而球樹使用的是兩邊之和大于第三邊來判斷，相對(duì)來說球樹的判斷更加復(fù)雜，但是卻避免了更多的搜索，這是一個(gè)權(quán)衡。

5. KNN算法的擴(kuò)展

　　　　這里我們?cè)儆懻撓翶NN算法的擴(kuò)展，限定半徑最近鄰算法。

　　　　有時(shí)候我們會(huì)遇到這樣的問題，即樣本中某系類別的樣本非常的少，甚至少于K，這導(dǎo)致稀有類別樣本在找K個(gè)最近鄰的時(shí)候，會(huì)把距離其實(shí)較遠(yuǎn)的其他樣本考慮進(jìn)來，而導(dǎo)致預(yù)測(cè)不準(zhǔn)確。為了解決這個(gè)問題，我們限定最近鄰的一個(gè)最大距離，也就是說，我們只在一個(gè)距離范圍內(nèi)搜索所有的最近鄰，這避免了上述問題。這個(gè)距離我們一般稱為限定半徑。

　　　　接著我們?cè)儆懻撓铝硪环N擴(kuò)展，最近質(zhì)心算法。這個(gè)算法比KNN還簡單。它首先把樣本按輸出類別歸類。對(duì)于第 L類的ClCl個(gè)樣本。它會(huì)對(duì)這ClCl個(gè)樣本的n維特征中每一維特征求平均值，最終該類別所有維度的n個(gè)平均值形成所謂的質(zhì)心點(diǎn)。對(duì)于樣本中的所有出現(xiàn)的類別，每個(gè)類別會(huì)最終得到一個(gè)質(zhì)心點(diǎn)。當(dāng)我們做預(yù)測(cè)時(shí)，僅僅需要比較預(yù)測(cè)樣本和這些質(zhì)心的距離，最小的距離對(duì)于的質(zhì)心類別即為預(yù)測(cè)的類別。這個(gè)算法通常用在文本分類處理上。

6. KNN算法小結(jié)

　　　　KNN算法是很基本的機(jī)器學(xué)習(xí)算法了，它非常容易學(xué)習(xí)，在維度很高的時(shí)候也有很好的分類效率，因此運(yùn)用也很廣泛，這里總結(jié)下KNN的優(yōu)缺點(diǎn)。

?

　　　　KNN的主要優(yōu)點(diǎn)有：

　　　　1） 理論成熟，思想簡單，既可以用來做分類也可以用來做回歸

　　　　2） 可用于非線性分類

　　　　3） 訓(xùn)練時(shí)間復(fù)雜度比支持向量機(jī)之類的算法低，僅為O(n)

　　　　4） 和樸素貝葉斯之類的算法比，對(duì)數(shù)據(jù)沒有假設(shè)，準(zhǔn)確度高，對(duì)異常點(diǎn)不敏感

5） 由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合 6）該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分

　　　　

　　　　KNN的主要缺點(diǎn)有：

　　　　1）計(jì)算量大，尤其是特征數(shù)非常多的時(shí)候

　　　　2）樣本不平衡的時(shí)候，對(duì)稀有類別的預(yù)測(cè)準(zhǔn)確率低

　　　　3）KD樹，球樹之類的模型建立需要大量的內(nèi)存

　　　　4）使用懶散學(xué)習(xí)方法，基本上不學(xué)習(xí)，導(dǎo)致預(yù)測(cè)時(shí)速度比起邏輯回歸之類的算法慢

5）相比決策樹模型，KNN模型可解釋性不強(qiáng)

　　　　以上就是KNN算法原理的一個(gè)總結(jié)，希望可以幫到朋友們，尤其是在用scikit-learn學(xué)習(xí)KNN的朋友們。

?原文地址：http://www.cnblogs.com/pinard/p/6061661.html

（歡迎轉(zhuǎn)載，轉(zhuǎn)載請(qǐng)注明出處。歡迎溝通交流： pinard.liu@ericsson.com）?　

總結(jié)

以上是生活随笔為你收集整理的K近邻法(KNN)原理小结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。