kd-tree

鎖定

• 隨着樹的深度輪流選擇軸當作分割面。（例如：在三維空間中根節點是 x 軸垂直分割面，其子節點皆為 y 軸垂直分割面，其孫節點皆為 z 軸垂直分割面，其曾孫節點則皆為 x 軸垂直分割面，依此類推。）
• 點由垂直分割面之軸座標的中位數區分並放入子樹

1. 從根節點開始，遞歸的往下移。往左還是往右的決定方法與插入元素的方法一樣(如果輸入點在分區面的左邊則進入左子節點，在右邊則進入右子節點)。
2. 一旦移動到葉節點，將該節點當作"當前最佳點"。
3. 解開遞歸，並對每個經過的節點運行下列步驟：
1. 如果當前所在點比當前最佳點更靠近輸入點，則將其變為當前最佳點。
2. 檢查另一邊子樹有沒有更近的點，如果有則從該節點往下找。
4. 當根節點搜索完畢後完成最鄰近搜索。

維數災難讓大部分的搜索算法在高維情況下都顯得花哨且不實用。 同樣的，在高維空間中，k-d樹葉並不能做很高效的最鄰近搜索。一般的準則是：在k維情況下，數據點數目N應當遠遠大於

時，k-d樹的最鄰近搜索才可以很好地發揮其作用。不然的話，大部分的點都會被查詢，最終算法效率也不會比全體查詢一遍要好到哪裏去。另外，如果只是需要一個足夠快，且不必最優的結果，那麼可以考慮使用近似鄰近查詢的方法。

k-d樹算法可以分為兩大部分，一部分是有關k-d樹本身這種數據結構建立的算法，另一部分是在建立的k-d樹上如何進行最鄰近查找的算法。

圖1

圖2

圖3

圖4

1. 從root節點開始，DFS搜索直到葉子節點，同時在stack中順序存儲已經訪問的節點。
2. 如果搜索到葉子節點，當前的葉子節點被設為最近鄰節點。
3. 然後通過stack回溯:如果當前點的距離比最近鄰點距離近，更新最近鄰節點.然後檢查以最近距離為半徑的圓是否和父節點的超平面相交.如果相交，則必須到父節點的另外一側，用同樣的DFS搜索法，開始檢查最近鄰節點。如果不相交，則繼續往上回溯，而父節點的另一側子節點都被淘汰，不再考慮的範圍中.
4. 當搜索回到root節點時，搜索完成，得到最近鄰節點。

圖5 & 圖6

from sklearn.neighbors import KDTree

import numpy as np
from sklearn.neighbors import KDTree
 
np.random.seed(0)
X = np.array([[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]])
 
tree = KDTree(X, leaf_size=2)
dist, ind = tree.query(X[:1], k=3)
 
print(dist)  # 3個最近的距離
print(ind)  # 3個最近的索引
print(X[ind])  # 3個最近的點
 
#
[[0.         3.16227766 4.47213595]]
[[0 1 3]]
[[[2 3]
  [5 4]
  [4 7]]]

 
 
class KDNode(object):
    def __init__(self, value, split, left, right):
        # value=[x,y]
        self.value = value
        self.split = split
        self.right = right
        self.left = left
 
 
class KDTree(object):
    def __init__(self, data):
        # data=[[x1,y1],[x2,y2]...,]
        # 維度
        k = len(data[0])
 
        def CreateNode(split, data_set):
            if not data_set:
                return None
            data_set.sort(key=lambda x: x[split])
            # 整除2
            split_pos = len(data_set) // 2
            median = data_set[split_pos]
            split_next = (split + 1) % k
 
            return KDNode(median, split, CreateNode(split_next, data_set[: split_pos]),
                          CreateNode(split_next, data_set[split_pos + 1:]))
 
        self.root = CreateNode(0, data)
        
    def search(self, root, x, count=1):
        nearest = []
        for i in range(count):
            nearest.append([-1, None])
        self.nearest = np.array(nearest)
 
        def recurve(node):
            if node is not None:
                axis = node.split
                daxis = x[axis] - node.value[axis]
                if daxis < 0:
                    recurve(node.left)
                else:
                    recurve(node.right)
                dist = sqrt(sum((p1 - p2) ** 2 for p1, p2 in zip(x, node.value)))
                for i, d in enumerate(self.nearest):
                    if d[0] < 0 or dist < d[0]:  # 如果當前nearest內i處未標記（-1），或者新點與x距離更近
                        self.nearest = np.insert(self.nearest, i, [dist, node.value], axis=0)  # 插入比i處距離更小的
                        self.nearest = self.nearest[:-1]
                        break
                # 找到nearest集合裏距離最大值的位置，為-1值的個數
                n = list(self.nearest[:, 0]).count(-1)
                # 切分軸的距離比nearest中最大的小（存在相交）
                if self.nearest[-n - 1, 0] > abs(daxis):
                    if daxis < 0:  # 相交，x[axis]< node.data[axis]時，去右邊（左邊已經遍歷了）
                        recurve(node.right)
                    else:  # x[axis]> node.data[axis]時，去左邊，（右邊已經遍歷了）
                        recurve(node.left)
        recurve(root)
        return self.nearest
 
 
# 最近座標點、最近距離和訪問過的節點數
result = namedtuple("Result_tuple", "nearest_point nearest_dist nodes_visited")
 
data = [[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]]
kd = KDTree(data)
 
#[3, 4.5]最近的3個點
n = kd.search(kd.root, [3, 4.5], 3)
print(n)
 
#[[1.8027756377319946 list([2, 3])]
 [2.0615528128088303 list([5, 4])]
 [2.692582403567252 list([4, 7])]]

參考資料

• 1.    李航．統計學習方法（第2版）．北京：清華大學出版社，2019：53
• 2.    kd樹算法研究  ．51CTO[引用日期2012-10-30]
• 3.    劉宇, 熊有倫, LiuYu, et al. 基於有界k-d樹的最近點搜索算法[J]. 華中科技大學學報（自然科學版）, 2008, 36(7):73-76.