傳統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.如何標明根節點的比對數值呢？
- 選擇何值未比對值，目的也是為了要加快檢索速度。一般來說我們在構造一個二叉樹的時候，當然是希望它是一棵盡量平衡的樹，即左右子樹中的結點個數相差不大。是以這裡用目前次元的中值是比較合理的。