K近鄰法(k-nearst neighbors,KNN)是一種很基本的機(jī)器學(xué)習(xí)方法了，在我們平常的生活中也會(huì)不自主的應(yīng)用。比如，我們判斷一個(gè)人的人品，只需要觀察他來(lái)往最密切的幾個(gè)人的人品好壞就可以得出了。這里就運(yùn)用了KNN的思想。KNN方法既可以做分類，也可以做回歸，這點(diǎn)和決策樹(shù)算法相同。
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ù)實(shí)現(xiàn)(KDTree)和球樹(shù)(BallTree)實(shí)現(xiàn)，本文只討論這幾種算法的實(shí)現(xiàn)原理。其余的實(shí)現(xiàn)方法比如BBF樹(shù)，MVP樹(shù)等，在這里不做討論。
1. KNN算法三要素
KNN算法我們主要要考慮三個(gè)重要的要素，對(duì)于固定的訓(xùn)練集，只要這三點(diǎn)確定了，算法的預(yù)測(cè)方式也就決定了。這三個(gè)最終的要素是k值的選取，距離度量的方式和分類決策規(guī)則。
對(duì)于分類決策規(guī)則，一般都是使用前面提到的多數(shù)表決法。所以我們重點(diǎn)是關(guān)注與k值的選擇和距離的度量方式。
對(duì)于k值的選擇，沒(méi)有一個(gè)固定的經(jīng)驗(yàn)，一般根據(jù)樣本的分布，選擇一個(gè)較小的值，可以通過(guò)交叉驗(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í)帶來(lái)的問(wèn)題是泛化誤差會(huì)增大，換句話說(shuō)，K值的減小就意味著整體模型變得復(fù)雜，容易發(fā)生過(guò)擬合；
選擇較大的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值的增大就意味著整體的模型變得簡(jiǎn)單。
一個(gè)極端是k等于樣本數(shù)m，則完全沒(méi)有分類，此時(shí)無(wú)論輸入實(shí)例是什么，都只是簡(jiǎn)單的預(yù)測(cè)它屬于在訓(xùn)練實(shí)例中最多的類，模型過(guò)于簡(jiǎn)單。
對(duì)于距離的度量，我們有很多的距離度量方式，但是最常用的是歐式距離，即對(duì)于兩個(gè)n維向量x和y，兩者的歐式距離定義為：
大多數(shù)情況下，歐式距離可以滿足我們的需求，我們
