knn算法介紹與參數調優(yōu)(共12頁)

1、KNN算法介紹與參數調優(yōu)K近鄰法(k-nearest neighbors,KNN)是一種很基本的機器學習方法了，在我們平常的生活中也會不自主的應用。比如，我們判斷一個人的人品，只需要觀察他來往最密切的幾個人的人品好壞就可以得出了。這里就運用了KNN的思想。KNN方法既可以做分類，也可以做回歸，這點和決策樹算法相同。KNN做回歸和分類的主要區(qū)別在于最后做預測時候的決策方式不同。KNN做分類預測時，一般是選擇多數表決法，即訓練集里和預測的樣本特征最近的K個樣本，預測為里面有最多類別數的類別。而KNN做回歸時，一般是選擇平均法，即最近的K個樣本的樣本輸出的平均值作為回歸預測值。由于兩者區(qū)別不大，雖然

2、本文主要是講解KNN的分類方法，但思想對KNN的回歸方法也適用。由于scikit-learn里只使用了蠻力實現(brute-force)，KD樹實現(KDTree)和球樹(BallTree)實現，本文只討論這幾種算法的實現原理。1. KNN算法三要素KNN算法我們主要要考慮三個重要的要素，對于固定的訓練集，只要這三點確定了，算法的預測方式也就決定了。這三個最終的要素是k值的選取，距離度量的方式和分類決策規(guī)則。對于分類決策規(guī)則，一般都是使用前面提到的多數表決法。所以我們重點是關注與k值的選擇和距離的度量方式。對于k值的選擇，沒有一個固定的經驗，一般根據樣本的分布，選擇一個較小的值，可以通過交叉驗

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

4、距離的度量，我們有很多的距離度量方式，但是最常用的是歐式距離，即對于兩個n維向量x和y，兩者的歐式距離定義為：Dx,y=i=1n(xi-yi)2大多數情況下，歐式距離可以滿足我們的需求，我們不需要再去操心距離的度量。當然我們也可以用他的距離度量方式。比如曼哈頓距離，定義為：Dx,y=i=1n|xi-yi|更加通用點，比如閔可夫斯基距離(Minkowski Distance)，定義為：Dx,y=pi=1n|xi-yi|p可以看出，歐式距離是閔可夫斯基距離在p=2時的特例，而曼哈頓距離是p=1時的特例。2. KNN算法蠻力實現從本節(jié)起，我們開始討論KNN算法的實現方式。首先我們看看最想當然的方式。

5、既然我們要找到k個最近的鄰居來做預測，那么我們只需要計算預測樣本和所有訓練集中的樣本的距離，然后計算出最小的k個距離即可，接著多數表決，很容易做出預測。這個方法的確簡單直接，在樣本量少，樣本特征少的時候有效。但是在實際運用中很多時候用不上，為什么呢？因為我們經常碰到樣本的特征數有上千以上，樣本量有幾十萬以上，如果我們這要去預測少量的測試集樣本，算法的時間效率很成問題。因此，這個方法我們一般稱之為蠻力實現。比較適合于少量樣本的簡單模型的時候用。既然蠻力實現在特征多，樣本多的時候很有局限性，那么我們有沒有其他的好辦法呢？有！這里我們講解兩種辦法，一個是KD樹實現，一個是球樹實現。3. KNN算法之

6、KD樹實現原理KD樹算法沒有一開始就嘗試對測試樣本分類，而是先對訓練集建模，建立的模型就是KD樹，建好了模型再對測試集做預測。所謂的KD樹就是K個特征維度的樹，注意這里的K和KNN中的K的意思不同。KNN中的K代表最近的K個樣本，KD樹中的K代表樣本特征的維數。為了防止混淆，后面我們稱特征維數為n。KD樹算法包括三步，第一步是建樹，第二部是搜索最近鄰，最后一步是預測。1.1 KD樹的建立我們首先來看建樹的方法。KD樹建樹采用的是從m個樣本的n維特征中，分別計算n個特征的取值的方差，用方差最大的第k維特征nk來作為根節(jié)點。對于這個特征，我們選擇特征nk的取值的中位數nkv對應的樣本作為劃分點，對

7、于所有第k維特征的取值小于nkv的樣本，我們劃入左子樹，對于第k維特征的取值大于等于nkv的樣本，我們劃入右子樹，對于左子樹和右子樹，我們采用和剛才同樣的辦法來找方差最大的特征來做更節(jié)點，遞歸的生成KD樹。 具體流程如下圖：比如我們有二維樣本6個，(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2)，構建kd樹的具體步驟為：1）找到劃分的特征。6個數據點在x，y維度上的數據方差分別為6.97，5.37，所以在x軸上方差更大，用第1維特征建樹。2）確定劃分點（7,2）。根據x維上的值將數據排序，6個數據的中值(所謂中值，即中間大小的值)為7，所以劃分點的數據是（7,2）。這樣，

8、該節(jié)點的分割超平面就是通過（7,2）并垂直于：劃分點維度的直線x=7；3）確定左子空間和右子空間。 分割超平面x=7將整個空間分為兩部分：x=7的部分為左子空間，包含3個節(jié)點=(2,3),(5,4),(4,7)；另一部分為右子空間，包含2個節(jié)點=(9,6)，(8,1)。4）用同樣的辦法劃分左子樹的節(jié)點(2,3),(5,4),(4,7)和右子樹的節(jié)點(9,6)，(8,1)。最終得到KD樹。最后得到的KD樹如下：1.2 KD樹搜索最近鄰當我們生成KD樹以后，就可以去預測測試集里面的樣本目標點了。對于一個目標點，我們首先在KD樹里面找到包含目標點的葉子節(jié)點。以目標點為圓心，以目標點到葉子節(jié)點樣本實例

9、的距離為半徑，得到一個超球體，最近鄰的點一定在這個超球體內部。然后返回葉子節(jié)點的父節(jié)點，檢查另一個子節(jié)點包含的超矩形體是否和超球體相交，如果相交就到這個子節(jié)點尋找是否有更加近的近鄰,有的話就更新最近鄰。如果不相交那就簡單了，我們直接返回父節(jié)點的父節(jié)點，在另一個子樹繼續(xù)搜索最近鄰。當回溯到根節(jié)點時，算法結束，此時保存的最近鄰節(jié)點就是最終的最近鄰。從上面的描述可以看出，KD樹劃分后可以大大減少無效的最近鄰搜索，很多樣本點由于所在的超矩形體和超球體不相交，根本不需要計算距離。大大節(jié)省了計算時間。我們用3.1建立的KD樹，來看對點(2,4.5)找最近鄰的過程。先進行二叉查找，先從（7,2）查找到（5,

10、4）節(jié)點，在進行查找時是由y = 4為分割超平面的，由于查找點為y值為4.5，因此進入右子空間查找到（4,7），形成搜索路徑，但 （4,7）與目標查找點的距離為3.202，而（5,4）與查找點之間的距離為3.041，所以（5,4）為查詢點的最近點；以（2，4.5）為圓心，以3.041為半徑作圓，如下圖所示?？梢娫搱A和y = 4超平面交割，所以需要進入（5,4）左子空間進行查找，也就是將（2,3）節(jié)點加入搜索路徑中得；于是接著搜索至（2,3）葉子節(jié)點，（2,3）距離（2,4.5）比（5,4）要近，所以最近鄰點更新為（2，3），最近距離更新為1.5；回溯查找至（5,4），直到最后回溯到根結點（7,

11、2）的時候，以（2,4.5）為圓心1.5為半徑作圓，并不和x = 7分割超平面交割，如下圖所示。至此，搜索路徑回溯完，返回最近鄰點（2,3），最近距離1.5。對應的圖如下：1.3 KD樹預測有了KD樹搜索最近鄰的辦法，KD樹的預測就很簡單了，在KD樹搜索最近鄰的基礎上，我們選擇到了第一個最近鄰樣本，就把它置為已選。在第二輪中，我們忽略置為已選的樣本，重新選擇最近鄰，這樣跑k次，就得到了目標的K個最近鄰，然后根據多數表決法，如果是KNN分類，預測為K個最近鄰里面有最多類別數的類別。如果是KNN回歸，用K個最近鄰樣本輸出的平均值作為回歸預測值。4.KNN算法之球樹實現原理KD樹算法雖然提高了KNN

12、搜索的效率，但是在某些時候效率并不高，比如當處理不均勻分布的數據集時,不管是近似方形，還是矩形，甚至正方形，都不是最好的使用形狀，因為他們都有角。一個例子如下圖：如果黑色的實例點離目標點星點再遠一點，那么虛線圓會如紅線所示那樣擴大，導致與左上方矩形的右下角相交，既然相 交了，那么就要檢查這個左上方矩形，而實際上，最近的點離星點的距離很近，檢查左上方矩形區(qū)域已是多余。于此我們看見，KD樹把二維平面劃分成一個一個矩形，但矩形區(qū)域的角卻是個難以處理的問題。為了優(yōu)化超矩形體導致的搜索效率的問題，牛人們引入了球樹，這種結構可以優(yōu)化上面的這種問題。我們現在來看看球樹建樹和搜索最近鄰的算法。4.1球樹的建立

13、球樹，顧名思義，就是每個分割塊都是超球體，而不是KD樹里面的超矩形體。我們看看具體的建樹流程：1) 先構建一個超球體，這個超球體是可以包含所有樣本的最小球體。2) 從球中選擇一個離球的中心最遠的點，然后選擇第二個點離第一個點最遠，將球中所有的點分配到離這兩個聚類中心最近的一個上，然后計算每個聚類的中心，以及聚類能夠包含它所有數據點所需的最小半徑。這樣我們得到了兩個子超球體，和KD樹里面的左右子樹對應。3)對于這兩個子超球體，遞歸執(zhí)行步驟2). 最終得到了一個球樹?？梢钥闯鯧D樹和球樹類似，主要區(qū)別在于球樹得到的是節(jié)點樣本組成的最小超球體，而KD得到的是節(jié)點樣本組成的超矩形體，這個超球體要與對應

14、的KD樹的超矩形體小，這樣在做最近鄰搜索的時候，可以避免一些無謂的搜索。4.2球樹搜索最近鄰使用球樹找出給定目標點的最近鄰方法是首先自上而下貫穿整棵樹找出包含目標點所在的葉子，并在這個球里找出與目標點最鄰近的點，這將確定出目標點距離它的最近鄰點的一個上限值，然后跟KD樹查找一樣，檢查兄弟結點，如果目標點到兄弟結點中心的距離超過兄弟結點的半徑與當前的上限值之和，那么兄弟結點里不可能存在一個更近的點；否則的話，必須進一步檢查位于兄弟結點以下的子樹。檢查完兄弟節(jié)點后，我們向父節(jié)點回溯，繼續(xù)搜索最小鄰近值。當回溯到根節(jié)點時，此時的最小鄰近值就是最終的搜索結果。從上面的描述可以看出，KD樹在搜索路徑優(yōu)化

15、時使用的是兩點之間的距離來判斷，而球樹使用的是兩邊之和大于第三邊來判斷，相對來說球樹的判斷更加復雜，但是卻避免了更多的搜索，這是一個權衡。5.KNN算法的擴展這里我們再討論下KNN算法的擴展，限定半徑最近鄰算法。有時候我們會遇到這樣的問題，即樣本中某系類別的樣本非常的少，甚至少于K，這導致稀有類別樣本在找K個最近鄰的時候，會把距離其實較遠的其他樣本考慮進來，而導致預測不準確。為了解決這個問題，我們限定最近鄰的一個最大距離，也就是說，我們只在一個距離范圍內搜索所有的最近鄰，這避免了上述問題。這個距離我們一般稱為限定半徑。接著我們再討論下另一種擴展，最近質心算法。這個算法比KNN還簡單。它首先把樣

16、本按輸出類別歸類。對于第 L類的Cl個樣本。它會對這Cl個樣本的n維特征中每一維特征求平均值，最終該類別所有維度的n個平均值形成所謂的質心點。對于樣本中的所有出現的類別，每個類別會最終得到一個質心點。當我們做預測時，僅僅需要比較預測樣本和這些質心的距離，最小的距離對于的質心類別即為預測的類別。這個算法通常用在文本分類處理上。6.KNN算法小結KNN算法是很基本的機器學習算法了，它非常容易學習，在維度很高的時候也有很好的分類效率，因此運用也很廣泛，這里總結下KNN的優(yōu)缺點。KNN的主要優(yōu)點有：1） 理論成熟，思想簡單，既可以用來做分類也可以用來做回歸。2） 可用于非線性分類。3） 訓練時間復雜度

17、比支持向量機之類的算法低，僅為O(n)。4） 和樸素貝葉斯之類的算法比，對數據沒有假設，準確度高，對異常點不敏感。5） 由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。6）該算法比較適用于樣本容量比較大的類域的自動分類，而那些樣本容量較小的類域采用這種算法比較容易產生誤分。KNN的主要缺點有：1）計算量大，尤其是特征數非常多的時候2）樣本不平衡的時候，對稀有類別的預測準確率低3）KD樹，球樹之類的模型建立需要大量的內存4）使用懶散學習方法，基本上不學習，導致預測時速度比起邏輯回歸之類的

18、算法慢5）相比決策樹模型，KNN模型可解釋性不強4.4.1scikit-learn 中KNN相關的類庫概述在scikit-learn 中，與近鄰法這一大類相關的類庫都在sklearn.neighbors包之中。KNN分類樹的類是KNeighborsClassifier，KNN回歸樹的類是KNeighborsRegressor。除此之外，還有KNN的擴展，即限定半徑最近鄰分類樹的類RadiusNeighborsClassifier和限定半徑最近鄰回歸樹的類RadiusNeighborsRegressor， 以及最近質心分類算法NearestCentroid。在這些算法中，KNN分類和回歸的類參數

19、完全一樣。限定半徑最近鄰法分類和回歸的類的主要參數也和KNN基本一樣。比較特別是的最近質心分類算法，由于它是直接選擇最近質心來分類，所以僅有兩個參數，距離度量和特征選擇距離閾值，比較簡單，因此后面就不再專門講述最近質心分類算法的參數。另外幾個在sklearn.neighbors包中但不是做分類回歸預測的類也值得關注。kneighbors_graph類返回用KNN時和每個樣本最近的K個訓練集樣本的位置。radius_neighbors_graph返回用限定半徑最近鄰法時和每個樣本在限定半徑內的訓練集樣本的位置。NearestNeighbors是個大雜燴，它即可以返回用KNN時和每個樣本最近的K個

20、訓練集樣本的位置，也可以返回用限定半徑最近鄰法時和每個樣本最近的訓練集樣本的位置，常常用在聚類模型中。4.2K近鄰法和限定半徑最近鄰法類庫參數小結本節(jié)對K近鄰法和限定半徑最近鄰法類庫參數做一個總結。包括KNN分類樹的類KNeighborsClassifier，KNN回歸樹的類KNeighborsRegressor， 限定半徑最近鄰分類樹的類RadiusNeighborsClassifier和限定半徑最近鄰回歸樹的類RadiusNeighborsRegressor。這些類的重要參數基本相同，因此我們放到一起講。參數KNeighborsClassifierKNeighborsRegressorRa

21、diusNeighborsClassifierRadiusNeighborsRegressorKNN中的K值n_neighborsK值的選擇與樣本分布有關，一般選擇一個較小的K值，可以通過交叉驗證來選擇一個比較優(yōu)的K值，默認值是5。如果數據是三維一下的，如果數據是三維或者三維以下的，可以通過可視化觀察來調參。不適用于限定半徑最近鄰法限定半徑最近鄰法中的半radius不適用于KNN半徑的選擇與樣本分布有關，可以通過交叉驗證來選擇一個較小的半徑，盡量保證每類訓練樣本其他類別樣本的距離較遠，默認值是1.0。如果數據是三維或者三維以下的，可以通過可視化觀察來調參。近鄰權重weights主要用于標識每個

22、樣本的近鄰樣本的權重，如果是KNN，就是K個近鄰樣本的權重，如果是限定半徑最近鄰，就是在距離在半徑以內的近鄰樣本的權重?？梢赃x擇uniform,distance 或者自定義權重。選擇默認的uniform，意味著所有最近鄰樣本權重都一樣，在做預測時一視同仁。如果是distance，則權重和距離成反比例，即距離預測目標更近的近鄰具有更高的權重，這樣在預測類別或者做回歸時，更近的近鄰所占的影響因子會更加大。當然，我們也可以自定義權重，即自定義一個函數，輸入是距離值，輸出是權重值。這樣我們可以自己控制不同的距離所對應的權重。一般來說，如果樣本的分布是比較成簇的，即各類樣本都在相對分開的簇中時，我們用默

23、認的uniform就可以了，如果樣本的分布比較亂，規(guī)律不好尋找，選擇distance是一個比較好的選擇。如果用distance發(fā)現預測的效果的還是不好，可以考慮自定義距離權重來調優(yōu)這個參數。KNN和限定半徑最近鄰法使用的算法algorithm算法一共有三種，第一種是蠻力實現，第二種是KD樹實現，第三種是球樹實現。這三種方法在中都有講述，如果不熟悉可以去復習下。對于這個參數，一共有4種可選輸入，brute對應第一種蠻力實現，kd_tree對應第二種KD樹實現，ball_tree對應第三種的球樹實現， auto則會在上面三種算法中做權衡，選擇一個擬合最好的最優(yōu)算法。需要注意的是，如果輸入樣本特征是

24、稀疏的時候，無論我們選擇哪種算法，最后scikit-learn都會去用蠻力實現brute。個人的經驗，如果樣本少特征也少，使用默認的auto就夠了。 如果數據量很大或者特征也很多，用auto建樹時間會很長，效率不高，建議選擇KD樹實現kd_tree，此時如果發(fā)現kd_tree速度比較慢或者已經知道樣本分布不是很均勻時，可以嘗試用ball_tree。而如果輸入樣本是稀疏的，無論你選擇哪個算法最后實際運行的都是brute。停止建子樹的葉子節(jié)點閾值leaf_size這個值控制了使用KD樹或者球樹時， 停止建子樹的葉子節(jié)點數量的閾值。這個值越小，則生成的KD樹或者球樹就越大，層數越深，建樹時間越長，反

25、之，則生成的KD樹或者球樹會小，層數較淺，建樹時間較短。默認是30. 這個值一般依賴于樣本的數量，隨著樣本數量的增加，這個值必須要增加，否則不光建樹預測的時間長，還容易過擬合?？梢酝ㄟ^交叉驗證來選擇一個適中的值。如果使用的算法是蠻力實現，則這個參數可以忽略。距離度量metricK近鄰法和限定半徑最近鄰法類可以使用的距離度量較多，一般來說默認的歐式距離（即p=2的閔可夫斯基距離）就可以滿足我們的需求。可以使用的距離度量參數有：a) 歐式距離“euclidean”: i=1n(xi-yi)2b) 曼哈頓距離 “manhattan”：i=1n|xi-yi|c) 切比雪夫距離“chebyshev”:m

26、ax|xi-yi|(i=1,2,n)d)閔可夫斯基距離“minkowski”(默認參數):pi=1n|xi-yi|p,，p=1為哈曼頓距離，p=2是歐式距離。e) 帶權重閔可夫斯基距離“wminkowski”:pi=1nw*|xi-yi|p f) 標準化歐式距離“seuclidean”: 即對于各特征維度做了歸一化以后的歐式距離。此時各樣本特征維度的均值為0，方差為1.g) 馬氏距離“mahalanobis”： x-yTS-1(x-y),其中，S-1為樣本協(xié)方差矩陣的逆矩陣。當樣本分布獨立時，S為單位矩陣，此時馬氏距離等同于歐式距離。還有一些其他不是實數的距離度量，一般在KNN之類的算法用不上

27、，這里也就不列了。距離度量附屬參數pp是使用距離度量參數 metric 附屬參數，只用于閔可夫斯基距離和帶權重閔可夫斯基距離中p值的選擇，p=1為曼哈頓距離， p=2為歐式距離。默認為2距離度量其他附屬參數metric_params一般都用不上，主要是用于帶權重閔可夫斯基距離的權重，以及其他一些比較復雜的距離度量的參數。并行處理任務數n_jobs主要用于多核CPU時的并行處理，加快建立KNN樹和預測搜索的速度。一般用默認的-1就可以了，即所有的CPU核都參與計算。不適用于限定半徑最近鄰法異常點類別選擇outlier_label不適用于KNN主要用于預測時，如果目標點半徑內沒有任何訓練集的樣本點

28、時，應該標記的類別，不建議選擇默認值 none,因為這樣遇到異常點會報錯。一般設置為訓練集里最多樣本的類別。不適用于限定半徑最近鄰回歸4.3使用KNeighborsRegressor做回歸的實例1數據情況：boston數據集2.建模的過程（1）標準化數據（2）初步搜索 n_neighbors,algorithm（3）搜索 leaf_size、wights（4）搜索p值（5）用最佳訓練的參數進行預測3.涉及核心內容 自定義scoring的使用1. 自定義評價函數評價函數的輸入是實際的label(y_true)和模型的輸出label(y_pred)def my_custom_loss_func(y

29、_true, y_pred): :param y_true:實際label :param y_pred: 預測的label :return: r2 =0.5* r2_score(y_true,y_pred) return r22.scoring函數的制作通過 greater_is_better 參數設定scoring的值的優(yōu)化方向通過 greater_is_better 參數設定scoring的值的優(yōu)化方向score = make_scorer(my_custom_loss_func, greater_is_better=True)from sklearn.datasets import lo

30、ad_bostonfrom sklearn.model_selection import train_test_splitfrom sklearn.preprocessing import StandardScalerimport numpy as npfrom sklearn.neighbors import KNeighborsRegressorfrom sklearn.model_selection import GridSearchCVfrom sklearn.metrics import r2_score,mean_absolute_error,mean_squared_error,

31、make_scorerdef search_best_param(clf,X,y,param_base,param_grid,scoring=r2): clf.set_params(*param_base) gs = GridSearchCV( estimator=clf, param_grid=param_grid, scoring=scoring, n_jobs=-1, iid=False, cv=5) gs.fit(X,y) param_base.update(gs.best_params_) print(nbest param:%s%str(gs.best_params_)+ best

32、 score:%s%str(gs.best_score_) return param_basedef model_select_step(clf,X,y,param_grids,scoring=r2): param_base=clf.get_params() for param_grid in param_grids: param_base = search_best_param(clf, X, y, param_base=param_base, param_grid=param_grid, scoring=scoring) return param_base自定義scoringdef my_custom_loss_func(y_true, y_pred): :param y_true:實際label :param y_pred: 預測的label :return: r2 =0.5* r2_score(y_true,y_pred) return r2if _name_=_main_: boston = load_boston() X = boston.data y = boston.target X_train,