K近鄰演算法（內附Kd-tree視頻演示）

K近鄰法（k-nearest neighbor,k-NN）是一種基本的分類與回歸演算法，其演算法思想概括起來就是一句話——「近朱者赤，近墨者黑」。K-NN不具有顯式的學習過程，而是利用訓練數據集對特徵向量空間進行劃分，並作為其分類的「模型」。

學習k-NN演算法，有三個基本要素：距離度量、k值選擇和分類決策規則。

距離度量

既然說是近鄰，怎麼才算是「近」呢？這個「近」是以什麼方法來度量的呢？一般來說，我們使用的是歐氏距離或者更一般的閔可夫斯基距離(MinkowskiDistance)。設特徵空間 是 維實數向量空間 ， ，則 的閔可夫斯基距離為

當p=1時，就是曼哈頓距離，當p=2時，就是歐氏距離，當p→∞時，就是切比雪夫距離。

k值選擇

k值就是要求的里目標點最近點的個數。k太小，分類結果易受雜訊點影響，容易發生過擬合；k太大，近鄰中又可能包含太多的其它類別的點，使預測發生錯誤，k值增大也就意味著模型整體變簡單。（對距離加權，可以降低k值設定的影響）。k值通常是採用交叉檢驗來確定（以k=1為基準）。有一個經驗規則， k一般低於訓練樣本數的平方根

分類決策規則

k-NN演算法中的分類決策規則往往是多數表決，即由輸入實例的k個鄰近的訓練實例中的多數類決定輸入實例的類。

k-NN的實現：Kd-tree

如何構造Kd-tree？

Kd-Tree，即K-dimensional tree，是一棵二叉樹，樹中存儲的是一些K維數據。在一個K維數據集合上構建一棵Kd-Tree代表了對該K維數據集合構成的K維空間的一個劃分，即樹中的每個結點就對應了一個K維的超矩形區域（Hyperrectangle）。

在介紹Kd-tree的相關演算法前，我們先回顧一下二叉查找樹（Binary Search Tree）的相關概念和演算法。二叉查找樹（Binary Search Tree，BST），是具有如下性質的二叉樹（來自wiki）：

1）若它的左子樹不為空，則左子樹上所有結點的值均小於它的根結點的值；

2）若它的右子樹不為空，則右子樹上所有結點的值均大於它的根結點的值；

3）它的左、右子樹也分別為二叉排序樹；

如圖為一棵二叉查找樹：

要滿足以上性質的話，則Kd-Tree的構造步驟可以分為以下兩步：

① 在K維數據集合中選擇具有最大方差的維度k，然後在該維度上選擇中位數點對該數據集合進行劃分，得到兩個子集合；同時創建了一個樹結點；如果是偶數個數據，中位數不是取排序後中間兩個的平均數，而是兩個點任選其一。

② 對兩個子集合重複（1）步驟的過程，直至所有子集合都不能再劃分為止。

如何搜索Kd-tree找到目標點P最鄰近的k個點？

1. 根據P的坐標值和每個節點的切分向下搜索（也就是比較該結點切分維度上的坐標值，比如一個結點是按照y維分的，就比較P點和結點的y坐標，若P點小，則走向左枝，若P點大，則走向右枝。

2. 當到達一個底部結點時，將其標記為已訪問。

如果L中不足k個點，則將該點加入到L中；如果L不為空且該點與P的距離小於L中離P遠的點的距離，則用該結點替換那個最遠點 。

3. 當前結點不是頂端結點時或是頂端結點卻未被標記已訪問（若是且已被被標記訪問則停止），則向上爬，若已被標記訪問，則繼續向上爬；若未被標記，則標記已訪問，並依次執行下面兩步：

1）L中不足k個點，則加入；若L已滿，則計算P與該點距離，若小於L中最大距離，則替換之。

2）計算P和當前結點切分線的距離D，若D大於L中最大距離且L已滿，則該結點的另一分支不會有更近的點，至此結束。若D小於L中最大距離或L未滿，則該結點的另一分支可能有更近的點，繼續在另一分支搜索（從1開始）。

下面來一段小視頻演示一下吧，用PPT畫的0.0

Sklearn實現

參考

《統計學習方法》李航

【量化課堂】kd 樹演算法之詳細篇