k近鄰法

          k近鄰法（k-nearest neighbor，k-NN）是一種基本分類與迴歸方法。本書只討論分類 問題中的k近鄰法。k近鄰法的輸入爲實例的特徵向量，對應於特徵空間的點；輸出爲實例 的類別，可以取多類。k近鄰法假設給定一個訓練數據集，其中的實例類別已定。分類 時，對新的實例，根據其k個最近鄰的訓練實例的類別，通過多數表決等方式進行預測。 因此，k近鄰法不具有顯式的學習過程。k近鄰法實際上利用訓練數據集對特徵向量空間進 行劃分，並作爲其分類的「模型」。k值的選擇、距離度量及分類決策規則是k近鄰法的三個 基本要素。k近鄰法1968年由Cover和Hart提出。 本章首先敘述k近鄰算法，然後討論k近鄰法的模型及三個基本要素，最後講述k近鄰 法的一個實現方法——kd樹，介紹構造kd樹和搜索kd樹的算法。

      k近鄰算法

        k近鄰算法簡單、直觀：給定一個訓練數據集，對新的輸入實例，在訓練數據集中找 到與該實例最鄰近的k個實例，這k個實例的多數屬於某個類，就把該輸入實例分爲這個 類。下面先敘述k近鄰算法，然後再討論其細節。 算法3.1（k近鄰法） 輸入：訓練數據集      其中，xi∊x⊆Rn爲實例的特徵向量，yi∊＝{c1，c2 ,…,cK}爲實例的類別，i＝1,2,…,N；實 例特徵向量x； 輸出：實例x所屬的類y。

（1）根據給定的距離度量，在訓練集T中找出與x最鄰近的k個點，涵蓋這k個點的x 的鄰域記作Nk(x)；

（2）在Nk(x)中根據分類決策規則（如多數表決）決定x的類別y：

 

式（3.1）中，I爲指示函數，即當yi＝cj時I爲1，否則I爲0。 k近鄰法的特殊情況是k＝1的情形，稱爲最近鄰算法。對於輸入的實例點（特徵向 量）x，最近鄰法將訓練數據集中與x最鄰近點的類作爲x的類。 k近鄰法沒有顯式的學習過程。

      k近鄰模型

k近鄰法使用的模型實際上對應於對特徵空間的劃分。模型由三個基本要素——距離 度量、k值的選擇和分類決策規則決定。k近鄰法中，當訓練集、距離度量（如歐氏距離）、k值及分類決策規則（如多數表 決）確定後，對於任何一個新的輸入實例，它所屬的類唯一地確定。這相當於根據上述要 素將特徵空間劃分爲一些子空間，確定子空間裏的每個點所屬的類。這一事實從最近鄰算 法中可以看得很清楚。 特徵空間中，對每個訓練實例點ix，距離該點比其他點更近的所有點組成一個區域， 叫作單元（cell）。每個訓練實例點擁有一個單元，所有訓練實例點的單元構成對特徵空 間的一個劃分。最近鄰法將實例ix的類iy作爲其單元中所有點的類標記（class label）。這樣每個單元的實例點的類別是確定的。

圖3.1是二維特徵空間劃分的一個例子。

特徵空間中兩個實例點的距離是兩個實例點相似程度的反映。k近鄰模型的特徵空間 一般是n維實數向量空間Rn。使用的距離是歐氏距離，但也可以是其他距離，如更一般的 Lp距離（Lp distance）或Minkowski距離（Minkowski distance）。

 

   k值的選擇會對k近鄰法的結果產生重大影響。 如果選擇較小的k值，就相當於用較小的鄰域中的訓練實例進行預測，「學習」的近似 誤差（approximation error）會減小，只有與輸入實例較近的（相似的）訓練實例纔會對 預測結果起作用。但缺點是「學習」的估計誤差（estimation error）會增大，預測結果會對 近鄰的實例點非常敏感[2]。如果鄰近的實例點恰巧是噪聲，預測就會出錯。換句話說，k 值的減小就意味着整體模型變得複雜，容易發生過擬合。 如果選擇較大的k值，就相當於用較大鄰域中的訓練實例進行預測。其優點是可以減 少學習的估計誤差。但缺點是學習的近似誤差會增大。這時與輸入實例較遠的（不相似 的）訓練實例也會對預測起作用，使預測發生錯誤。k值的增大就意味着整體的模型變得 簡單。 如果k＝N，那麼無論輸入實例是什麼，都將簡單地預測它屬於在訓練實例中最多的 類。這時，模型過於簡單，完全忽略訓練實例中的大量有用信息，是不可取的。 在應用中，k值一般取一個比較小的數值。通常採用交叉驗證法來選取最優的k值。

      k近鄰法中的分類決策規則往往是多數表決，即由輸入實例的k個鄰近的訓練實例中的 多數類決定輸入實例的類。 多數表決規則（majority voting rule）有如下解釋：如果分類的損失函數爲0-1損失函 數，分類函數爲：

           

   那麼誤分類的概率是  

k近鄰法的實現：kd樹

      實現k近鄰法時，主要考慮的問題是如何對訓練數據進行快速k近鄰搜索。這點在特徵 空間的維數大及訓練數據容量大時尤其必要。 k近鄰法最簡單的實現方法是線性掃描（linear scan）。這時要計算輸入實例與每一個 訓練實例的距離。當訓練集很大時，計算非常耗時，這種方法是不可行的。 爲了提高k近鄰搜索的效率，可以考慮使用特殊的結構存儲訓練數據，以減少計算距 離的次數。具體方法很多，下面介紹其中的kd樹（kd tree）方法

         kd樹是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形數據結構。 kd樹是二叉樹，表示對k維空間的一個劃分（partition）。構造kd樹相當於不斷地用垂直於座標軸的超平面將k維空間切分，構成一系列的k維超矩形區域。kd樹的每個結點對應於一 個k維超矩形區域。

          構造kd樹的方法如下：構造根結點，使根結點對應於k維空間中包含所有實例點的超 矩形區域；通過下面的遞歸方法，不斷地對k維空間進行切分，生成子結點。在超矩形區 域（結點）上選擇一個座標軸和在此座標軸上的一個切分點，確定一個超平面，這個超平 面通過選定的切分點並垂直於選定的座標軸，將當前超矩形區域切分爲左右兩個子區域 （子結點）；這時，實例被分到兩個子區域。這個過程直到子區域內沒有實例時終止（終 止時的結點爲葉結點）。在此過程中，將實例保存在相應的結點上。 通常，依次選擇座標軸對空間切分，選擇訓練實例點在選定座標軸上的中位數 （median）[2]爲切分點，這樣得到的kd樹是平衡的。注意，平衡的kd樹搜索時的效率未必 是最優的。

（1）開始：構造根結點，根結點對應於包含T的k維空間的超矩形區域。 選擇x (1)爲座標軸，以T中所有實例的x (1)座標的中位數爲切分點，將根結點對應的超矩形區域切分爲兩個子區域。切分由通過切分點並與座標軸x (1)垂直的超平面實現。 由根結點生成深度爲1的左、右子結點：左子結點對應座標x (1)小於切分點的子區域， 右子結點對應於座標x (1)大於切分點的子區域。 將落在切分超平面上的實例點保存在根結點。

（2）重複：對深度爲j的結點，選擇x (l)爲切分的座標軸，l＝j(modk)+1，以該結點的 區域中所有實例的x (l)座標的中位數爲切分點，將該結點對應的超矩形區域切分爲兩個子 區域。切分由通過切分點並與座標軸x (l)垂直的超平面實現。 由該結點生成深度爲j+1的左、右子結點：左子結點對應座標x (l)小於切分點的子區 域，右子結點對應座標x (l)大於切分點的子區域。 將落在切分超平面上的實例點保存在該結點。

（3）直到兩個子區域沒有實例存在時停止。從而形成kd樹的區域劃分。

搜索kd樹

    下面介紹如何利用kd樹進行k近鄰搜索。可以看到，利用kd樹可以省去對大部分數據 點的搜索，從而減少搜索的計算量。這裏以最近鄰爲例加以敘述，同樣的方法可以應用到 k近鄰。

     給定一個目標點，搜索其最近鄰。首先找到包含目標點的葉結點；然後從該葉結點出 發，依次回退到父結點；不斷查找與目標點最鄰近的結點，當確定不可能存在更近的結點 時終止。這樣搜索就被限制在空間的局部區域上，效率大爲提高。

     包含目標點的葉結點對應包含目標點的最小超矩形區域。以此葉結點的實例點作爲當 前最近點。目標點的最近鄰一定在以目標點爲中心並通過當前最近點的超球體的內部（參閱圖3.5）。然後返回當前結點的父結點，如果父結點的另一子結點的超矩形區域與超球 體相交，那麼在相交的區域內尋找與目標點更近的實例點。如果存在這樣的點，將此點作 爲新的當前最近點。算法轉到更上一級的父結點，繼續上述過程。如果父結點的另一子結 點的超矩形區域與超球體不相交，或不存在比當前最近點更近的點，則停止搜索。

 

下面敘述用kd樹的最近鄰搜索算法。

算法3.3（用kd樹的最近鄰搜索）

輸入：已構造的kd樹；目標點x； 輸出：x的最近鄰。

（1）在kd樹中找出包含目標點x的葉結點：從根結點出發，遞歸地向下訪問kd樹。若 目標點x當前維的座標小於切分點的座標，則移動到左子結點，否則移動到右子結點。直 到子結點爲葉結點爲止。

（2）以此葉結點爲「當前最近點」。

（3）遞歸地向上回退，在每個結點進行以下操作：

         （a）如果該結點保存的實例點比當前最近點距離目標點更近，則以該實例點爲「當前 最近點」。

         （b）當前最近點一定存在於該結點一個子結點對應的區域。檢查該子結點的父結點 的另一子結點對應的區域是否有更近的點。具體地，檢查另一子結點對應的區域是否與以 目標點爲球心、以目標點與「當前最近點」間的距離爲半徑的超球體相交。如果相交，可能在另一個子結點對應的區域內存在距目標點更近的點，移動到另一個 子結點。接着，遞歸地進行最近鄰搜索； 如果不相交，向上回退。

（4）當回退到根結點時，搜索結束。最後的「當前最近點」即爲x的最近鄰點。

如果實例點是隨機分佈的，kd樹搜索的平均計算複雜度是O(logN)，這裏N是訓練實 例數。kd樹更適用於訓練實例數遠大於空間維數時的k近鄰搜索。當空間維數接近訓練實 例數時，它的效率會迅速下降，幾乎接近線性掃描

下面通過一個例題來說明搜索方法。

例3.3   給定一個如圖3.5所示的kd樹，根結點爲A，其子結點爲B，C等。樹上共存儲 7個實例點；另有一個輸入目標實例點S，求S的最近鄰。

 解 :

      首先在kd樹中找到包含點S的葉結點D（圖中的右下區域），以點D作爲近似最 近鄰。真正最近鄰一定在以點S爲中心通過點D的圓的內部。然後返回結點D的父結點B， 在結點B的另一子結點F的區域內搜索最近鄰。結點F的區域與圓不相交，不可能有最近鄰 點。繼續返回上一級父結點A，在結點A的另一子結點C的區域內搜索最近鄰。結點C的區 域與圓相交；該區域在圓內的實例點有點E，點E比點D更近，成爲新的最近鄰近似。最後 得到點E是點S的最近鄰。