機器學習系列——K最近鄰算法

k近鄰法(k-nearest neighbor, k-NN)是一種基本分類與回歸方法。本文讨論分類問題中的k近鄰法。

k近鄰算法

k近鄰法：

輸入：訓練資料集

其中

輸出：執行個體所屬的類

• (1) 根據給定的距離度量，在訓練集中找出與最近的k個點，涵蓋這k個點的鄰域記作
• (2) 在中根據分類決策規則(如多數表決)決定的類别：

其中 。為訓示函數，相等為1否則為0

k近鄰法沒有顯示的學習過程。

k值的選擇

k值的選擇對k近鄰的結果産生重大影響。

如果k過小，對近鄰的執行個體點十分敏感，容易過拟合

如果k過大，可以減國小習的估計誤差，但是近似誤差會增大，欠拟合

一般k取一個較小的值，采用交叉驗證法來選擇最優的k值

k近鄰法的實作：kd樹

實作k近鄰法，主要考慮的問題是如何快速k近鄰搜尋。這點在高次元，資料量大時尤為重要。

構造kd樹

kd樹是一種對k維空間中的執行個體點進行存儲以便對其進行快速檢索的樹形資料結構。

kd樹是二叉樹，表示對k維空間的一個劃分。

構造平衡kd樹：

輸入：k維空間資料集

輸出：kd樹

• (1) 開始：構造根結點，根結點對應于包含的k維空間的超矩形區域。

  選擇為坐标軸，以所有執行個體的坐标軸的中位數作為切分點，沿着通過切分點并與坐标軸垂直的超平面将超矩形區域切成兩個子區域。

  由根結點生成深度為1的左右子結點，左子結點對應坐标小于切分點的子區域。将落在切分超平面上的執行個體點儲存在根結點。

• (2) 重複：對深度為j的結點，選擇為切分的坐标軸，l=j(mod k) + 1。以該結點的區域中所有執行個體的坐标的中位數為切分點，沿着通過切分點并與坐标軸垂直的超平面将超矩形區域切成兩個子區域
• (3) 直到兩個子區域都沒有執行個體存在則停止。

搜尋kd樹

• (1)在kd樹中找出包含目标點x的葉節點，從根結點出發，遞歸向下通路kd樹。若x目前維的坐标小于切分點的坐标，則移動到左子結點，否則移動到又子結點。直到子結點為葉子節點為止
• (2)以此葉節點為“目前最近點”
• (3)遞歸向上回歸，每個結點進行以下操作：

• (a)如果該結點儲存的執行個體比目前最近點距離目标點更近，則以該執行個體點為“目前最近點”
• (b)目前最近點一定存在于該結點一個子結點對應的區域。檢查該子結點的父結點的另一個子結點對應的區域是否有更近的點。具體的，檢查另一子結點對應的區域是否與以目标點為球心，以目标點與目前最近點間的距離為半徑的超球體相交。

• 如果相交，可能在另一個子結點對應的區域記憶體在距目标點更近的點，移動到另一個子結點。接着，遞歸的進行最近鄰搜尋。
• 如果不相交，向上回退

• (4)當回退到根結點時，搜尋結束，最後的“目前最近點”即為x的最近鄰點。