??kd樹就是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形數據結構，可以運用在k近鄰法中，實現快速k近鄰搜索。構造kd樹相當于不斷地用垂直于坐標軸的超平面將k維空間切分。
?? 假設數據集\(T\)的大小是\(m*n\),即\(T={x_1,x_2,...x_m}\),其中\(x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T，i=1,2,...m\)。構建Kd樹的過程大致如下。
??對所有的數據,以\(x^{(1)}\)為軸，即取\(x_i^{(1)}，i=1,2,...m\),并求得其中位數\(mid^{(1)}\)，\(mid^{(1)}\)對應的點即為根節點，以\(mid^{(1)}\)為切分點，將剩余數據分為兩個集合，左子樹對應小于切分點的區域，右子樹對應大于切分點的區域，然后針對每個集合，以\(x^{(2)}\)為軸，重復上述過程，繼續切分為兩個集合，然后不斷重復上述過程，依次選擇\(x^{(j)}，j=1,2,...,n\)為軸，直到切分得到的集合中只有一個數據為止。
?? kd樹的構造相對簡單，那么如何利用kd樹進行搜索？
??給定一個目標點，搜索其最近鄰，首先按照“左小右大”的規則，找到目標點所屬區域對應的葉節點，然后從該葉節點出發，依次回退到父節點，不斷查找與目標點最鄰近的點，當確定不可能存在更近的節點時終止，這樣搜索就被限制在空間的局部區域上，效率大大提高。
??具體來說，
??（1）從根節點出發，按照“左小右大”的規則，找到目標點所屬區域對應的葉節點
??（2）然后從該葉節點出發，向上回退，在回退到的每個父節點\(f\)上，執行一下兩種操作：
????(a)判斷\(f\)與目標點的距離是否比當前最近距離更近，如果是，則將當前最近點更新為\(f\)
????(b)當前最近點一定存在于\(f\)的一個子結點對應的區域中，即一定存在于\(f\)對應的區域中，即有可能\(f\)另一個 ??子結點距離目標點更近。判斷目標點是否距離\(f\)另一個子結點對應區域更近，具體地，判斷目標點與\(f\)對應的切??分軸 的距離是否小于當前最小距離，如果小于，從該子結點出發，重復執行步驟（2）
??（3）當回退到根節點并完成對根節點步驟（2）中的兩步操作時，搜索結束。當前最近點即為目標點的最近鄰點。
以一個具體例子說明。如圖1是生成的一顆kd樹，特征空間劃分如圖2所示，要求目標點S(4.5,7.5)的最近鄰點。
??搜索過程如下：
??（1）首先在kd樹中找到了包含目標點S的葉節點D，D即為當前最近點，兩點之間的距離是當前最近距離dist；
??（2）向上回退到點B，點B距離點S更遠，并且點B以\(x^{(2)}=5.5\)為切分軸，S距離\(x^{(2)}=5.5\)的距離大于dist，不用考慮點F；
??（3）繼續向上回退到根節點點A，點A距離點S更遠，但是點A以\(x^{(1)}=5\)為切分軸，S距離\(x^{(1)}=5\)的距離小于dist，那么點S有可能距離A的右子樹區域C中的點更近
??（4）從點C出發，一直訪問到點E，點E比點D距離點S更近，點E成為當前最近點，兩點之間的距離是當前最近距離dist；
??（5）從點E向上回退到點C，點C距離點S更遠，并且點C以\(x^{(2)}=4.5\)為切分軸，S距離\(x^{(2)}=4.5\)的距離大于dist，不用考慮點G
??（6）繼續向上回退，再次回退到了根節點A，結束搜索，點E即為點S的最近鄰點。
)
)
使用)
