K近鄰法(k-nearst neighbors,KNN)是一種很基本的機(jī)器學(xué)習(xí)方法了，在我們平常的生活中也會不自主的應(yīng)用。比如，我們判斷一個人的人品，只需要觀察他來往最密切的幾個人的人品好壞就可以得出了。這里就運(yùn)用了KNN的思想。KNN方法既可以做分類，也可以做回歸，這點和決策樹算法相同。
KNN做回歸和分類的主要區(qū)別在于最后做預(yù)測時候的決策方式不同。KNN做分類預(yù)測時，一般是選擇多數(shù)表決法，即訓(xùn)練集里和預(yù)測的樣本特征最近的K個樣本，預(yù)測為里面有最多類別數(shù)的類別。而KNN做回歸時，一般是選擇平均法，即最近的K個樣本的樣本輸出的平均值作為回歸預(yù)測值。由于兩者區(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算法我們主要要考慮三個重要的要素，對于固定的訓(xùn)練集，只要這三點確定了，算法的預(yù)測方式也就決定了。這三個最終的要素是k值的選取，距離度量的方式和分類決策規(guī)則。
對于分類決策規(guī)則，一般都是使用前面提到的多數(shù)表決法。所以我們重點是關(guān)注與k值的選擇和距離的度量方式。
對于k值的選擇，沒有一個固定的經(jīng)驗，一般根據(jù)樣本的分布，選擇一個較小的值，可以通過交叉驗證選擇一個合適的k值。
選擇較小的k值，就相當(dāng)于用較小的領(lǐng)域中的訓(xùn)練實例進(jìn)行預(yù)測，訓(xùn)練誤差會減小，只有與輸入實例較近或相似的訓(xùn)練實例才會對預(yù)測結(jié)果起作用，與此同時帶來的問題是泛化誤差會增大，換句話說，K值的減小就意味著整體模型變得復(fù)雜，容易發(fā)生過擬合；
選擇較大的k值，就相當(dāng)于用較大領(lǐng)域中的訓(xùn)練實例進(jìn)行預(yù)測，其優(yōu)點是可以減少泛化誤差，但缺點是訓(xùn)練誤差會增大。這時候，與輸入實例較遠(yuǎn)（不相似的）訓(xùn)練實例也會對預(yù)測器作用，使預(yù)測發(fā)生錯誤，且K值的增大就意味著整體的模型變得簡單。
一個極端是k等于樣本數(shù)m，則完全沒有分類，此時無論輸入實例是什么，都只是簡單的預(yù)測它屬于在訓(xùn)練實例中最多的類，模型過于簡單。
延伸閱讀
- ssh框架 2016-09-30
- 阿里移動安全 [無線安全]玩轉(zhuǎn)無線電——不安全的藍(lán)牙鎖 2017-07-26
- 消息隊列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 論文筆記【圖片目標(biāo)分割】 2017-07-26
- 詞向量-LRWE模型-更好地識別反義詞同義詞 2017-07-26
- 從棧不平衡問題 理解 calling convention 2017-07-26
- php imagemagick 處理 圖片剪切、壓縮、合并、插入文本、背景色透明 2017-07-26
- Swift實現(xiàn)JSON轉(zhuǎn)Model - HandyJSON使用講解 2017-07-26
- 阿里移動安全 Android端惡意鎖屏勒索應(yīng)用分析 2017-07-26
- 集合結(jié)合數(shù)據(jù)結(jié)構(gòu)來看看(二) 2017-07-26
學(xué)習(xí)是年輕人改變自己的最好方式