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

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

1. KNN算法三要素

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

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

 

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

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

 

對于距離的度量，我們有很多的距離度量方式，但是最常用的是歐式距離，即對于兩個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ù)情況下，歐式距離可以滿足我們的需求，我們