傳統KNN缺點：數據量特別大時，需要計算參考點和每個樣本點的距離，計算量非常大，所以提出一種優化算法-----kd-tree.
為了提高kNN搜索的效率，可以考慮使用特殊的結構存儲訓練數據，以減小計算距離的次數。
kd樹(K-dimension tree)是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形數據結構。kd樹是是一種二叉樹，表示對k維空間的一個劃分，構造kd樹相當於不斷地用垂直於座標軸的超平面將K維空間切分，構成一系列的K維超矩形區域。kd樹的每個結點對應於一個k維超矩形區域。利用kd樹可以省去對大部分數據點的搜索，從而減少搜索的計算量。
構造kd-tree
輸入：多維空間數據集
輸出：kd樹
（1）開始：構造根結點。選擇X為切分座標軸，以所有實例X座標的中位數為切分點，將根結點對應的區域切分為左、右兩個子區域。左子結點對應座標小於切分點的子區域，右子結點對應於座標大於切分點的子區域。將落在切分超平面上的實例點保存在根結點。
（2）重複。對左右子區域，輪換切分座標軸，繼續以座標軸對應座標的中位數為切分點。直到所有的點都切分完畢。
舉個簡單的例子：
例. 給定一個二維空間數據集{（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，構造一個平衡kd樹。
解：根結點對應包含數據集T的矩形，選擇軸，6個數據點的座標中位數是6，這裡選最接近的(7,2)點，以平面將空間分為左、右兩個子矩形（子結點）；接著左矩形以分為兩個子矩形（左矩形中{(2,3),(5,4),(4,7)}點的座標中位數正好為4），右矩形以分為兩個子矩形，如此遞歸，最後得到如下圖所示的特徵空間劃分和kd樹。
搜索kd樹
利用kd樹可以省去對大部分數據點的搜索，從而減少搜索的計算量。下面以搜索最近鄰點為例加以敘述：給定一個目標點，搜索其最近鄰，首先找到包含目標點的葉節點；然後從該葉結點出發，依次回退到父結點；不斷查找與目標點最近鄰的結點，當確定不可能存在更近的結點時終止。這樣搜索就被限制在空間的局部區域上，效率大為提高。
用kd樹的最近鄰搜索：
輸入： 已構造的kd樹；目標點；
輸出：最近鄰。
（1） 在kd樹中找出包含目標點的葉結點：從根結點出發，遞歸的向下訪問kd樹。若目標點當前維的座標值小於切分點的座標值，則移動到左子結點，否則移動到右子結點。直到子結點為葉結點為止；
（2） 以此葉結點為“當前最近點”；
（3） 遞歸的向上回退，在每個結點進行以下操作：
（a） 如果該結點保存的實例點比當前最近點距目標點更近，則以該實例點為“當前最近點”；
（b） 當前最近點一定存在於該結點一個子結點對應的區域。檢查該子結點的父結點的另一個子結點對應的區域是否有更近的點。具體的，檢查另一個子結點對應的區域是否與以目標點為球心、以目標點與“當前最近點”間的距離為半徑的超球體相交。如果相交，可能在另一個子結點對應的區域內存在距離目標更近的點，移動到另一個子結點。接著，遞歸的進行最近鄰搜索。如果不相交，向上回退。
（4） 當回退到根結點時，搜索結束。最後的“當前最近點”即為的最近鄰點。
注意：這裡的搜索，也是跟上邊構造一樣，首先先搜索x(1),再搜索x(2)..以此類推下去。
以先前構建好的kd樹為例，查找目標點（3,4.5）的最近鄰點。同樣先進行二叉查找，先從（7,2）查找到（5,4）節點，在進行查找時是由y = 4為分割超平面的，由於查找點為y值為4.5，因此進入右子空間查找到（4,7），形成搜索路徑：（7,2）→（5,4）→（4,7），取（4,7）為當前最近鄰點。以目標查找點為圓心，目標查找點到當前最近點的距離2.69為半徑確定一個紅色的圓。然後回溯到（5,4），計算其與查找點之間的距離為2.06，則該結點比當前最近點距目標點更近，以(5,4)為當前最近點。用同樣的方法再次確定一個綠色的圓，可見該圓和y = 4超平面相交，所以需要進入（5,4）結點的另一個子空間進行查找。（2,3）結點與目標點距離為1.8，比當前最近點要更近，所以最近鄰點更新為（2，3），最近距離更新為1.8，同樣可以確定一個藍色的圓。接著根據規則回退到根結點(7,2)，藍色圓與x=7的超平面不相交，因此不用進入（7,2）的右子空間進行查找。至此，搜索路徑回溯完，返回最近鄰點（2,3），最近距離1.8。
kd-tree的幾個問題：
1.如何決定每次根據哪個維度對子空間進行劃分呢？
直觀的來看，我們一般會選擇輪流來。先根據第一維，然後是第二維，然後第三……，那麼到底輪流來行不行呢，這就要回到最開始我們為什麼要研究選擇哪一維進行劃分的問題。我們研究Kd-Tree是為了優化在一堆數據中高頻查找的速度，用樹的形式，也是為了儘快的縮小檢索範圍，所以這個“比對維”就很關鍵，通常來說，更為分散的維度，我們就更容易的將其分開，是以這裡我們通過求方差，用方差最大的維度來進行劃分——這也就是最大方差法（max invarince）。
2.如何選定根節點的比對數值呢？
選擇何值未比對值，目的也是為了要加快檢索速度。一般來說我們在構造一個二叉樹的時候，當然是希望它是一棵儘量平衡的樹，即左右子樹中的結點個數相差不大。所以這裡用當前維度的中值是比較合理的。
---------------------
原文：
https://blog.csdn.net/weixin_41770169/article/details/81565514
