KNN演算法

02-03

基本思想：給定一個訓練集，對新的輸入實例，在訓練數據集中找到與該實例最鄰近的k個實例，這k個實例的多數屬於某個類，就把該輸入實例分為這個類。

$K$ 近鄰法

輸入：訓練集 $T={(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N})}$ ，實例特徵向量 $x$

輸出：實例 $x$ 所屬的類 $y$

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

（2）在 $N_{k}(x)$ 中根據分類決策規則（如多數表決）決定 $x$ 的類別 $y$ 。

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

簡單地說， $K$ 近鄰法就是找出距 $x$ 最近的 $K$ 個點，然後看這 $K$ 個點中屬於哪一類別最多， $x$ 就屬於這一類別。

$K$ 值的選擇

$K$ 值選擇過小，就意味著實例近鄰點起著非常大的作用，如果實例近鄰點恰巧是雜訊，則預測會出錯，也就是說 $K$ 值減小會使得模型變複雜，容易發生過擬合。相反， $K$ 值增大會使得模型變簡單，容易發生欠擬合。在應用中， $K$ 值一般取一個較小的數，採用交叉驗證的方法來選取最優的 $K$ 值。

$KD$ 樹

為了提高 $k$ 近鄰的搜索效率，可以考慮使用特殊的結構訓練數據，例如 $kd$ 樹。

通常，依次選擇坐標軸對空間切分，選擇訓練實例點在選定坐標軸上的中位數為切分點，這樣得到的 $kd$ 樹是最平衡的。但是它的搜索效率未必是最優的。

構造平衡 $kd$ 樹：

（1）確定spilt：對於給定的數據集，統計它們在每個維度上的方差，將方差最大的作為split劃分的坐標軸；

（2）開始：根據給定的劃分坐標軸將數據集排序，選擇中值作為根節點，劃分為左右子樹；

（3）重複：順序選擇剩下的維度，分別根據中值劃分為左右子樹；

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

搜索 $kd$ 樹：

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

（2）以此葉節點為當前最近點。

（3）遞歸的向上回退，在每個節點進行一下操作：

（a）如果該節點保存的實例比當前最近點距離目標更近，則稱該節點為當前最近點；

（b）當前最近點一定存在於該節點某個子節點對應的區域，檢查該子節點的父節點的另一子節點對應的區域是否有更近的點；

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

$kd$ 樹適用於訓練實例數目遠大於空間維數，當空間維數接近訓練數目時，它的效率會迅速下降，幾乎接近線性掃描。