《統計學習方法》第三章 k近鄰算法

1. k近鄰算法定義

給定一個訓練集,對新的輸入實例,在訓練數據集彙總找到與該實例最鄰近的k個實例,這k個實例的多數屬於某個類,就把該輸入實例分爲這個類.

2. k近鄰算法模型基本要素

2.1 距離度量

特徵空間中兩個實例點的距離是兩個實例點相似程度的反映.距離度量可以使用歐式距離,或更一般的Lp距離、Minkowski距離.

2.2 k值的選擇

在應用中,k一般取一個比較小的數值(小於20),通常採用交叉驗證法來選去最優k值.

近似誤差和估計誤差的區別:
近似誤差：可以理解爲對現有訓練集的訓練誤差。
估計誤差：可以理解爲對測試集的測試誤差。

2.3 分類決策規則

k近鄰法中的分類決策規則往往是多數表決,即由輸入實例的k個鄰近的訓練實例中的多數類決定輸入實例的類.

3. k近鄰算法的實現:kd樹

3.1 構造kd樹

實現k近鄰法時,主要考慮的問題時如何對訓練數據進行快速k近鄰搜索,尤其是當特徵空間的維數大及訓練數據容量大時.
構造kd樹算法：


注：l=j(mod k) + 1，即輪流的使用k維空間的每個維度進行劃分。
如有許多個點，空間爲三維，首先使用x維，選取x軸中位數點進行劃分，然後使用y軸，選取y軸中位數點進行劃分，然後使用z軸，選取z軸中位數點進行劃分，這時點如果還沒有劃分到每個節點（即kd樹每個節點有1個點），再依次使用x、y、z軸對剩餘的點進行劃分。

注：劃分的時候取中位數該處是向上取整，如6個數取第4個。

3.2 搜索kd樹

注：kd樹每一個節點都表示包含該節點座標值的一個區域。