K臨近算法之KD樹構造
在使用k近鄰法進行分類時，對新的執行個體，根據其k個最近鄰的訓練執行個體的類别，通過多數表決的方式進行預測。由于k近鄰模型的特征空間一般是n維實數向量，是以距離的計算通常采用的是歐式距離。關鍵的是k值的選取，如果k值太小就意味着整體模型變得複雜，容易發生過拟合，即如果鄰近的執行個體點恰巧是噪聲，預測就會出錯，極端的情況是k=1，稱為最近鄰算法，對于待預測點x，與x最近的點決定了x的類别。k值得增大意味着整體的模型變得簡單，極端的情況是k=N，那麼無論輸入執行個體是什麼，都簡單地預測它屬于訓練集中最多的類，這樣的模型過于簡單。經驗是，k值一般去一個比較小的值，通常采取交叉驗證的方法來選取最優的k值。
實作k近鄰法時，主要考慮的問題是如何對訓練資料進行快速k近鄰搜尋，這點在特征空間的維數大以及訓練資料容量大時尤其重要。k近鄰法的最簡單實作是線性掃描，這時要計算輸入執行個體與每一個訓練執行個體的距離，當訓練集很大時，計算非常耗時，這種方法是不可行的。為了提高k近鄰搜尋的效率，可以考慮使用特殊的結構存儲訓練資料，以減少計算距離的次數。具體方法有很多，這裡介紹kd樹方法。
1、執行個體
先以一個簡單直覺的執行個體來介紹k-d樹算法。假設有6個二維資料點{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，資料點位于二維空間内（如圖2中黑點所示）。k-d樹算法就是要确定圖2中這些分割空間的分割線（多元空間即為分割平面，一般為超平面）。下面就要通過一步步展示k-d樹是如何确定這些分割線的。如下圖：
k-d樹算法可以分為兩大部分，一部分是有關k-d樹本身這種資料結建構立的算法，另一部分是在建立的k-d樹上如何進行最鄰近查找的算法。
2、構造kd樹
kd樹是一種對k維空間中的執行個體點進行存儲以便對其進行快速搜尋的樹形資料結構。kd樹是二叉樹，表示對k維空間的一個劃分。構造kd樹相當于不斷地用垂直于坐标軸的超平面将k維空間進行切分，構成一系列的k維超矩形區域。kd樹的每一個節點對應于一個k維超矩形區域。k-d樹是一個二叉樹，每個節點表示一個空間範圍。下表給出的是k-d樹每個節點中主要包含的資料結構。
從上面對k-d樹節點的資料類型的描述可以看出建構k-d樹是一個逐級展開的遞歸過程。下面給出的是建構k-d樹的僞碼。
算法：建構k-d樹（createKDTree）
輸入：資料點集Data-set和其所在的空間Range
輸出：Kd，類型為k-d tree
1.If Data-set為空，則傳回空的k-d tree
2.調用節點生成程式：
（1）确定split域：對于所有描述子資料（特征矢量），統計它們在每個維上的資料方差。假設每條資料記錄為64維，可計算64個方差。挑選出最大值，對應的維就是split域的值。資料方差大表明沿該坐标軸方向上的資料分散得比較開，在這個方向上進行資料分割有較好的分辨率；
（2）确定Node-data域：資料點集Data-set按其第split域的值排序。位于正中間的那個資料點被選為Node-data。此時新的Data-set' = Data-set \ Node-data（除去其中Node-data這一點）。
3.dataleft = {d屬于Data-set' && d[split] ≤ Node-data[split]}
Left_Range = {Range && dataleft}
dataright = {d屬于Data-set' && d[split] > Node-data[split]}
Right_Range = {Range && dataright}
4.left = 由（dataleft，Left_Range）建立的k-d tree，即遞歸調用createKDTree（dataleft，Left_Range）。并設定 left的parent域為Kd；
right = 由（dataright，Right_Range）建立的k-d tree，即調用createKDTree（dataleft，Left_Range）。并設定 right的parent域為Kd。
以上述舉的執行個體來看，過程如下：
由于此例簡單，資料次元隻有2維，是以可以簡單地給x，y兩個方向軸編号為0,1，也即split={0,1}。
（1）确定split域的首先該取的值。分别計算x，y方向上資料的方差得知x方向上的方差最大，是以split域值首先取0，也就是x軸方向；
（2）确定Node-data的域值。根據x軸方向的值2,5,9,4,8,7排序選出中值為7，是以Node-data = （7,2）。這樣，該節點的分割超平面就是通過（7,2）并垂直于split = 0（x軸）的直線x = 7；
（3）确定左子空間和右子空間。分割超平面x = 7将整個空間分為兩部分，如下圖所示。x <= 7的部分為左子空間，包含3個節點{（2,3），（5,4），（4,7）}；另一部分為右子空間，包含2個節點{（9,6），（8,1）}。
如算法所述，k-d樹的建構是一個遞歸的過程。然後對左子空間和右子空間内的資料重複根節點的過程就可以得到下一級子節點（5,4）和（9,6）（也就是左右子空間的’根’節點），同時将空間和資料集進一步細分。如此反複直到空間中隻包含一個資料點，如下圖所示。最後生成的k-d樹如下圖所示。
3、搜尋KD樹
在k-d樹中進行資料的查找也是特征比對的重要環節，其目的是檢索在k-d樹中與查詢點距離最近的資料點。這裡先以一個簡單的執行個體來描述最鄰近查找的基本思路。
星号表示要查詢的點（2.1,3.1）。通過二叉搜尋，順着搜尋路徑很快就能找到最鄰近的近似點，也就是葉子節點（2,3）。而找到的葉子節點并不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位于以查詢點為圓心且通過葉子節點的圓域内。為了找到真正的最近鄰，還需要進行’回溯’操作：算法沿搜尋路徑反向查找是否有距離查詢點更近的資料點。此例中先從（7,2）點開始進行二叉查找，然後到達（5,4），最後到達（2,3），此時搜尋路徑中的節點為小于（7,2）和（5,4），大于（2,3），首先以（2,3）作為目前最近鄰點，計算其到查詢點（2.1,3.1）的距離為0.1414，然後回溯到其父節點（5,4），并判斷在該父節點的其他子節點空間中是否有距離查詢點更近的資料點。以（2.1,3.1）為圓心，以0.1414為半徑畫圓，如下圖所示。發現該圓并不和超平面y = 4交割，是以不用進入（5,4）節點右子空間中去搜尋。
再回溯到（7,2），以（2.1,3.1）為圓心，以0.1414為半徑的圓更不會與x = 7超平面交割，是以不用進入（7,2）右子空間進行查找。至此，搜尋路徑中的節點已經全部回溯完，結束整個搜尋，傳回最近鄰點（2,3），最近距離為0.1414。
一個複雜點了例子如查找點為（2，4.5）。同樣先進行二叉查找，先從（7,2）查找到（5,4）節點，在進行查找時是由y = 4為分割超平面的，由于查找點為y值為4.5，是以進入右子空間查找到（4,7），形成搜尋路徑<（7,2），（5,4），（4,7）>，取（4,7）為目前最近鄰點，計算其與目标查找點的距離為3.202。然後回溯到（5,4），計算其與查找點之間的距離為3.041。以（2，4.5）為圓心，以3.041為半徑作圓，如下圖左所示。可見該圓和y = 4超平面交割，是以需要進入（5,4）左子空間進行查找。此時需将（2,3）節點加入搜尋路徑中得<（7,2），（2,3）>。回溯至（2,3）葉子節點，（2,3）距離（2,4.5）比（5,4）要近，是以最近鄰點更新為（2，3），最近距離更新為1.5。回溯至（7,2），以（2,4.5）為圓心1.5為半徑作圓，并不和x = 7分割超平面交割，如下圖右所示。至此，搜尋路徑回溯完。傳回最近鄰點（2,3），最近距離1.5。
查詢僞代碼如下：
算法：k-d樹最鄰近查找
輸入：Kd， //k-d tree類型
target //查詢資料點
輸出：nearest， //最鄰近資料點
dist //最鄰近資料點和查詢點間的距離
1. If Kd為NULL，則設dist為infinite并傳回
2. //進行二叉查找，生成搜尋路徑
Kd_point = &Kd； //Kd-point中儲存k-d tree根節點位址
nearest = Kd_point -> Node-data； //初始化最近鄰點
while（Kd_point）
push（Kd_point）到search_path中； //search_path是一個堆棧結構，存儲着搜尋路徑節點指針
/*** If Dist（nearest，target） > Dist（Kd_point -> Node-data，target）
nearest = Kd_point -> Node-data； //更新最近鄰點
Max_dist = Dist(Kd_point，target）； //更新最近鄰點與查詢點間的距離 ***/
s = Kd_point -> split； //确定待分割的方向
If target[s] <= Kd_point -> Node-data[s] //進行二叉查找
Kd_point = Kd_point -> left；
else
Kd_point = Kd_point ->right；
nearest = search_path中最後一個葉子節點； //注意：二叉搜尋時不比計算選擇搜尋路徑中的最鄰近點，這部分已被注釋
Max_dist = Dist（nearest，target）； //直接取最後葉子節點作為回溯前的初始最近鄰點
3. //回溯查找
while（search_path != NULL）
back_point = 從search_path取出一個節點指針； //從search_path堆棧彈棧
s = back_point -> split； //确定分割方向
If Dist（target[s]，back_point -> Node-data[s]） < Max_dist //判斷還需進入的子空間
If target[s] <= back_point -> Node-data[s]
Kd_point = back_point -> right； //如果target位于左子空間，就應進入右子空間
else
Kd_point = back_point -> left; //如果target位于右子空間，就應進入左子空間
将Kd_point壓入search_path堆棧；
If Dist（nearest，target） > Dist（Kd_Point -> Node-data，target）
nearest = Kd_point -> Node-data； //更新最近鄰點
Min_dist = Dist（Kd_point -> Node-data,target）； //更新最近鄰點與查詢點間的距離
當維數較大時，直接利用k-d樹快速檢索的性能急劇下降。假設資料集的維數為D，一般來說要求資料的規模N滿足條件：N遠大于2的D次方，才能達到高效的搜尋。
原文連結：https://blog.csdn.net/qll125596718/article/details/8426458