Ⅰ 02 KNN演算法 - KD Tree
KD Tree 是KNN演算法中用於計算最近鄰的快速簡便的構建方式。
當樣本量少的時候，用 brute 直接搜索最近鄰的方式是可行的。即計算到所有樣本的距離。但當樣本量龐大時，直接計算所有樣本距離的工作量很大，這種情況使用 KD Tree 可以節約大量時間成本。
KD樹採用從m個樣本的n維特徵中，分別計算n個特徵取值的方差，用 方差最大 的第k維特徵n k 作為 根節點 。對於這個特徵，選擇取值中的 中位數 n kv 作為樣本的劃分點，對於小於該值的樣本劃分到 左子樹 ，對於大於等於該值的樣本劃分到 右子樹 ，對左右子樹採用同樣的方式找 方差最大的特徵 作為 根節點 ，遞歸產生KD Tree。
為什麼要選擇方差最大的進行劃分？
構建樹的目的是加快我的搜索過程。
既然我想加快我的搜索過程，要就意味著我最終的數據落在某個葉子節點上。我希望只需搜索整個二叉樹的某一些列即可，那麼最好的劃分方式，就是讓我的每個分支上數據的差異性最大化。
那麼衡量數據差異性的最基礎的數學指標是什麼？
是方差。方差越大，意味著數據的離散程度就越大，我將離散程度由大到小的數據一分為二，方差小意味著數據更集中到了一起。
現在有一個二維樣本: {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
1、計算x1和x2每一列對應的方差
a、通過pandas計算出的是 樣本方差:
/ (n-1)
0| 6.966667
1| 5.366667
dtype: float64
b、通過numpy計算出的是 總體方差:
/ n
[[2 3]
[5 4]
[9 6]
[4 7]
[8 1]
[7 2]]
[ 5.80555556 4.47222222]
[ 5.80555556 4.47222222]
第一個樹的劃分：基於x 1 進行劃分
[2,4,5,7,8,9]的中位數是5和7的平均值6。
雖然嚴格意義上說中位數是6，但是在計算機中我們人為得定義x 1 的中位數是7。
左側：（2,3）（5,4）（4,7） （7,2）
右側: （9,6）（8,1）
第二個樹的劃分：根據右側（9,6）（8,1）的x 2 進行劃分
下側：x 2 ≤ 6；上側x 2 ＞6
第二個樹的劃分：根據左側（2,3）（5,4）（4,7） （7,2）的x 2 進行劃分
尋找2、3、4、7的中位數 4 進行劃分
....
注意：每次生成的劃分都是一個矩形。當葉子節點無法被繼續劃分的時候，KD樹的構建完成，遞歸結束。
我們生成了KD Tree後，現在就可以去預測測試集裡面的樣本目標點了。
1、對於一個目標點，先在KD樹里找到包含目標點的葉子節點。
2、以目標點為圓心，以 目標點 到 葉子節點樣本實例 的距離為半徑，得到一個超球體，最近鄰的點一定在這個超球體內部。
3、然後返回葉子節點的父節點，檢查另一個子節點包含的超矩形體是否和超球體相交。
4、如果相交就倒這個子節點尋找著是否有更加近的近鄰，有的話就更新最近鄰。
5、如果不相交，直接返回父節點中的父節點，在另一個子樹繼續搜索最近鄰。當回溯到根節點時，演算法結束。
6、此時保存的最近鄰節點就是最終的最近鄰。
如果現在想找(2,4.5)這點的最近鄰，該如何操作？
1、畫出二叉樹：
2、尋找(2,4.5)這點：
一個比較好的理解方式：首先找到第一個最近鄰，然後畫出一個圓。然後逐漸收縮圓的半徑，查看每次縮小後的圓是否能夠和矩形相交於一個更小的最近鄰點，如果有則更新。直到回到根節點。
Ⅱ 為啥knn演算法的數據結構是kd樹
很明顯，
kd樹只是一種為了提高knn演算法查找效率的一種數據結構，當然還有其他的數據結構了，比如ball-tree，https://en.wikipedia.org/wiki/Ball_tree
Ⅲ KNN演算法-4-演算法優化-KD樹
KNN演算法的重要步驟是對所有的實例點進行快速k近鄰搜索。如果採用線性掃描（linear scan），要計算輸入點與每一個點的距離，時間復雜度非常高。因此在查詢操作時，可以使用kd樹對查詢操作進行優化。
Kd-樹是K-dimension tree的縮寫，是對數據點在k維空間（如二維(x，y)，三維(x，y，z)，k維(x1，y，z..)）中劃分的一種數據結構，主要應用於多維空間關鍵數據的搜索（如：范圍搜索和最近鄰搜索）。本質上說，Kd-樹就是一種平衡二叉樹。
k-d tree是每個節點均為k維樣本點的二叉樹，其上的每個樣本點代表一個超平面，該超平面垂直於當前劃分維度的坐標軸，並在該維度上將空間劃分為兩部分，一部分在其左子樹，另一部分在其右子樹。即若當前節點的劃分維度為d，其左子樹上所有點在d維的坐標值均小於當前值，右子樹上所有點在d維的坐標值均大於等於當前值，本定義對其任意子節點均成立。
必須搞清楚的是，k-d樹是一種空間劃分樹，說白了，就是把整個空間劃分為特定的幾個部分，然後在特定空間的部分內進行相關搜索操作。想像一個三維(多維有點為難你的想像力了)空間，kd樹按照一定的劃分規則把這個三維空間劃分了多個空間，如下圖所示：
首先，邊框為紅色的豎直平面將整個空間劃分為兩部分，此兩部分又分別被邊框為綠色的水平平面劃分為上下兩部分。最後此4個子空間又分別被邊框為藍色的豎直平面分割為兩部分，變為8個子空間，此8個子空間即為葉子節點。
常規的k-d tree的構建過程為：
對於構建過程，有兩個優化點：
例子：採用常規的構建方式，以二維平面點(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 為例結合下圖來說明k-d tree的構建過程：
如上演算法所述，kd樹的構建是一個遞歸過程，我們對左子空間和右子空間內的數據重復根節點的過程就可以得到一級子節點（5,4）和（9,6），同時將空間和數據集進一步細分，如此往復直到空間中只包含一個數據點。
如之前所述，kd樹中，kd代表k-dimension，每個節點即為一個k維的點。每個非葉節點可以想像為一個分割超平面，用垂直於坐標軸的超平面將空間分為兩個部分，這樣遞歸的從根節點不停的劃分，直到沒有實例為止。經典的構造k-d tree的規則如下：
kd樹的檢索是KNN演算法至關重要的一步，給定點p，查詢數據集中與其距離最近點的過程即為最近鄰搜索。
如在構建好的k-d tree上搜索(3,5)的最近鄰時，對二維空間的最近鄰搜索過程作分析。
首先從根節點(7,2)出發，將當前最近鄰設為(7,2)，對該k-d tree作深度優先遍歷。
以(3,5)為圓心，其到(7,2)的距離為半徑畫圓（多維空間為超球面），可以看出(8,1)右側的區域與該圓不相交，所以(8,1)的右子樹全部忽略。
接著走到(7,2)左子樹根節點(5,4)，與原最近鄰對比距離後，更新當前最近鄰為(5,4)。
以(3,5)為圓心，其到(5,4)的距離為半徑畫圓，發現(7,2)右側的區域與該圓不相交，忽略該側所有節點，這樣(7,2)的整個右子樹被標記為已忽略。
遍歷完(5,4)的左右葉子節點，發現與當前最優距離相等，不更新最近鄰。所以(3,5)的最近鄰為(5,4)。
舉例：查詢點（2.1,3.1）
星號表示要查詢的點（2.1,3.1）。通過二叉搜索，順著搜索路徑很快就能找到最鄰近的近似點，也就是葉子節點（2,3）。而找到的葉子節點並不一定就是最鄰近的，最鄰近肯定距離查詢點更近，應該位於以查詢點為圓心且通過葉子節點的圓域內。為了找到真正的最近鄰，還需要進行相關的『回溯'操作。也就是說，演算法首先沿搜索路徑反向查找是否有距離查詢點更近的數據點。
舉例：查詢點（2，4.5）
一個復雜點了例子如查找點為（2，4.5），具體步驟依次如下：
上述兩次實例表明，當查詢點的鄰域與分割超平面兩側空間交割時，需要查找另一側子空間，導致檢索過程復雜，效率下降。
一般來講，最臨近搜索只需要檢測幾個葉子結點即可，如下圖所示：
但是，如果當實例點的分布比較糟糕時，幾乎要遍歷所有的結點，如下所示：
研究表明N個節點的K維k-d樹搜索過程時間復雜度為： 。
同時，以上為了介紹方便，討論的是二維或三維情形。但在實際的應用中，如SIFT特徵矢量128維，SURF特徵矢量64維，維度都比較大，直接利用k-d樹快速檢索（維數不超過20）的性能急劇下降，幾乎接近貪婪線性掃描。假設數據集的維數為D，一般來說要求數據的規模N滿足N»2D，才能達到高效的搜索。
Sklearn中有KDTree的實現，僅構建了一個二維空間的k-d tree，然後對其作k近鄰搜索及指定半徑的范圍搜索。多維空間的檢索，調用方式與此例相差無多。
Ⅳ opencv中是否有kdtree演算法
有，位於opencv320\opencv\sources\moles\ml\src
Ⅳ python 如何畫出KD數
簡單的KNN演算法在為每個數據點預測類別時都需要遍歷整個訓練數據集來求解距離，這樣的做法在訓練數據集特別大的時候並不高效，一種改進的方法就是使用kd樹來存儲訓練數據集，這樣可以使KNN分類器更高效。
KD樹的主要思想跟二叉樹類似，我們先來回憶一下二叉樹的結構，二叉樹中每個節點可以看成是一個數，當前節點總是比左子樹中每個節點大，比右子樹中每個節點小。而KD樹中每個節點是一個向量(也可能是多個向量)，和二叉樹總是按照數的大小劃分不同的是，KD樹每層需要選定向量中的某一維，然後根據這一維按左小右大的方式劃分數據。在構建KD樹時，關鍵需要解決2個問題：（1）選擇向量的哪一維進行劃分（2）如何劃分數據。第一個問題簡單的解決方法可以是選擇隨機選擇某一維或按順序選擇，但是更好的方法應該是在數據比較分散的那一維進行劃分（分散的程度可以根據方差來衡量）。好的劃分方法可以使構建的樹比較平衡，可以每次選擇中位數來進行劃分，這樣問題2也得到了解決。下面是建立KD樹的Python代碼：
def build_tree(data, dim, depth):
"""
建立KD樹
Parameters
----------
data:numpy.array
需要建樹的數據集
dim:int
數據集特徵的維數
depth:int
當前樹的深度
Returns
-------
tree_node:tree_node namedtuple
樹的跟節點
"""
size = data.shape[0]
if size == 0:
return None
# 確定本層劃分參照的特徵
split_dim = depth % dim
mid = size / 2
# 按照參照的特徵劃分數據集
r_indx = np.argpartition(data[:, split_dim], mid)
data = data[r_indx, :]
left = data[0: mid]
right = data[mid + 1: size]
mid_data = data[mid]
# 分別遞歸建立左右子樹
left = build_tree(left, dim, depth + 1)
right = build_tree(right, dim, depth + 1)
# 返回樹的根節點
return Tree_Node(left=left,
right=right,
data=mid_data,
split_dim=split_dim)
對於一個新來的數據點x，我們需要查找KD樹中距離它最近的節點。KD樹的查找演算法還是和二叉樹查找的演算法類似，但是因為KD樹每次是按照某一特定的維來劃分，所以當從跟節點沿著邊查找到葉節點時候並不能保證當前的葉節點就離x最近，我們還需要回溯並在每個父節點上判斷另一個未查找的子樹是否有可能存在離x更近的點（如何確定的方法我們可以思考二維的時候，以x為原點，當前最小的距離為半徑畫園，看是否與劃分的直線相交，相交則另一個子樹中可能存在更近的點），如果存在就進入子樹查找。
當我們需要查找K個距離x最近的節點時，我們只需要維護一個長度為K的優先隊列保持當前距離x最近的K個點。在回溯時，每次都使用第K短距離來判斷另一個子節點中是否存在更近的節點即可。下面是具體實現的python代碼：
def search_n(cur_node, data, queue, k):
"""
查找K近鄰，最後queue中的k各值就是k近鄰
Parameters
----------
cur_node:tree_node namedtuple
當前樹的跟節點
data:numpy.array
數據
queue:Queue.PriorityQueue
記錄當前k個近鄰，距離大的先輸出
k:int
查找的近鄰個數
"""
# 當前節點為空，直接返回上層節點
if cur_node is None:
return None
if type(data) is not np.array:
data = np.asarray(data)
cur_data = cur_node.data
# 得到左右子節點
left = cur_node.left
right = cur_node.right
# 計算當前節點與數據點的距離
distance = np.sum((data - cur_data) ** 2) ** .5
cur_split_dim = cur_node.split_dim
flag = False # 標記在回溯時是否需要進入另一個子樹查找
# 根據參照的特徵來判斷是先進入左子樹還是右子樹
if data[cur_split_dim] > cur_data[cur_split_dim]:
tmp = right
right = left
left = tmp
# 進入子樹查找
search_n(left, data, queue, k)
# 下面是回溯過程
# 當隊列中沒有k個近鄰時，直接將當前節點入隊，並進入另一個子樹開始查找
if len(queue) < k:
neg_distance = -1 * distance
heapq.heappush(queue, (neg_distance, cur_node))
flag = True
else:
# 得到當前距離數據點第K遠的節點
top_neg_distance, top_node = heapq.heappop(queue)
# 如果當前節點與數據點的距離更小，則更新隊列（當前節點入隊，原第k遠的節點出隊）
if - 1 * top_neg_distance > distance:
top_neg_distance, top_node = -1 * distance, cur_node
heapq.heappush(queue, (top_neg_distance, top_node))
# 判斷另一個子樹內是否可能存在跟數據點的距離比當前第K遠的距離更小的節點
top_neg_distance, top_node = heapq.heappop(queue)
if abs(data[cur_split_dim] - cur_data[cur_split_dim]) < -1 * top_neg_distance:
flag = True
heapq.heappush(queue, (top_neg_distance, top_node))
# 進入另一個子樹搜索
if flag:
search_n(right, data, queue, k)525354555657
以上就是KD樹的Python實踐的全部內容，由於本人剛接觸python不久，可能實現上並不優雅，也可能在演算法理解上存在偏差，如果有任何的錯誤或不足，希望各位賜教。
Ⅵ 2 Kd樹的構造與搜索
實現kNN演算法時，最簡單的實現方法就是線性掃描，正如我們上一章節內容介紹的一樣-> K近鄰演算法 ，需要計算輸入實例與每一個訓練樣本的距離。當訓練集很大時，會非常耗時。
為了提高kNN搜索的效率，可以考慮使用特殊的結構存儲訓練數據，以減少計算距離的次數，KD-Tree就是其中的一種方法。
K維空間數據集
其中
隨機生成 13 個點作為我們的數據集
首先先沿 x 坐標進行切分，我們選出 x 坐標的中位點，獲取最根部節點的坐標
並且按照該點的x坐標將空間進行切分，所有 x 坐標小於 6.27 的數據用於構建左分支，x坐標大於 6.27 的點用於構建右分支。
在下一步中 ,對應 y 軸，左右兩邊再按照 y 軸的排序進行切分，中位點記載於左右枝的節點。得到下面的樹，左邊的 x 是指這該層的節點都是沿 x 軸進行分割的。
空間的切分如下
下一步中 ，對應 x 軸，所以下面再按照 x 坐標進行排序和切分，有
最後只剩下了葉子結點，就此完成了 kd 樹的構造。
輸入：已構造的kd樹，目標點x
輸出：x的k個最近鄰集合L
KD-Tree的平均時間復雜度為 ，N為訓練樣本的數量。
KD-Tree試用於訓練樣本數遠大於空間維度的k近鄰搜索。當空間維數接近訓練樣本數時，他的效率會迅速下降，幾乎接近線性掃描。
設我們想查詢的點為 p=(−1,−5)，設距離函數是普通的距離，我們想找距離目標點最近的 k=3 個點。如下：
首先我們按照構造好的KD-Tree，從根結點開始查找
和這個節點的 x 軸比較一下，p 的 x 軸更小。因此我們向左枝進行搜索：
接下來需要對比 y 軸
p 的 y 值更小，因此向左枝進行搜索：
這個節點只有一個子枝，就不需要對比了。由此找到了葉子節點 (−4.6,−10.55)。
在二維圖上是藍色的點
此時我們要執行第二步，將當前結點插入到集合L中，並記錄下 L=[(−4.6,−10.55)]。訪問過的節點就在二叉樹上顯示為被劃掉的好了。
然後執行第三步，不是最頂端節點。我回退。上面的結點是 (−6.88,−5.4)。
執行 3a，因為我們記錄下的點只有一個，小於 k=3，所以也將當前節點記錄下，插入到集合L中，有 L=[(−4.6,−10.55),(−6.88,−5.4)].。 因為當前節點的左枝是空的，所以直接跳過，繼續回退，判斷不是頂部根節點
由於還是不夠三個點，於是將當前點也插入到集合L中，有 L=[(−4.6,−10.55),(−6.88,−5.4),(1.24,−2.86)]。
此時發現，當前節點有其他的分枝，執行3b，計算得出 p 點和 L 中的三個點的距離分別是 6.62, 5.89, 3.10，但是 p 和當前節點的分割線的距離只有 2.14，小於與 L 的最大距離：
因此，在分割線的另一端可能有更近的點。於是我們在當前結點的另一個分枝從頭執行步驟1。好，我們在紅線這里：
此時處於x軸切分，因此要用 p 和這個節點比較 x 坐標:
p 的 x 坐標更大，因此探索右枝 (1.75,12.26)，並且發現右枝已經是最底部節點，執行步驟2與3a。
經計算，(1.75,12.26) 與 p 的距離是 17.48，要大於 p 與 L 的距離，因此我們不將其放入記錄中。
然後 回退，判斷出不是頂端節點，往上爬。
執行3a，這個節點與 p 的距離是 4.91，要小於 p 與 L 的最大距離 6.62。
因此，我們用這個新的節點替代 L 中離 p 最遠的 (−4.6,−10.55)。
然後3b，我們比對 p 和當前節點的分割線的距離
這個距離小於 L 與 p 的最大距離，因此我們要到當前節點的另一個枝執行步驟1。當然，那個枝只有一個點。
計算距離發現這個點離 p 比 L 更遠，因此不進行替代。
然後回退，不是根結點，我們向上爬
這個是已經訪問過的了，所以再向上爬
再爬
此時到頂點了 。所以完了嗎？當然不，還要執行3b呢。現在是步驟1的回合。
我們進行計算比對發現頂端節點與p的距離比L還要更遠，因此不進行更新。
然後計算 p 和分割線的距離發現也是更遠。
因此也不需要檢查另一個分枝。
判斷當前節點是頂點，因此計算完成！輸出距離 p 最近的三個樣本是 L=[(−6.88,−5.4),(1.24,−2.86),(−2.96,−2.5)]。
聲明：此文章為本人學習筆記，參考於： https://zhuanlan.hu.com/p/23966698