KD树

KD(k-dimensional)树的概念自1975年提出,试图解决的是在k维空间为数据集建立索引的问题。依上文所述,已知样本空间如何快速查询得到其近邻?唯有以空间换时间,建立索引便是计算机世界的解决之道。但是索引建立的方式各有不同,kd树只是是其中一种。它的思想如同分治法,即:利用已有数据对k维空间进行切分。

在机器学习KNN中,KD树也是必不可少的理论基础部分,分文介绍并提供示例代码

参考:

 

概述

二叉树在时间复杂度上是O(logN),远远优于全遍历算法。对于该树,可以在空间上理解:树的每个节点把对应父节点切成的空间再切分,从而形成各个不同的子空间。查找某点的所在位置时,就变成了查找点所在子空间。而KD树引申于二叉树

以二维KD树为例,假设有6个二维数据点{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}。

将二维的平面想像成一块方型蛋糕,kd树构建就是面点师要将蛋糕切成上面示意图的模样。先将平面上的六个点在蛋糕上做好标记。

 

KD树

1. KD树的构建

以本例的第一次切分为例,需要知道以x轴还是y轴进行切分比较好,需要判断两个维度的方差,选择最大的来切分

KD树

计算可得,x方差较大,按x进行切分。

考虑到让二叉树的深度尽量小,使用二分原则进行划分。即按照中间索引的点作为根节点,剩下按照大小各分左右。

之后,将分好的两个数据也按照此原则进行划分,最终构建出KD树

结果如图所示:

KD树

 

2. KD树的查找

在k-d树中进行数据的查找也是特征匹配的重要环节,其目的是检索在k-d树中与查询点距离最近的数据点。

回到面点师切好的糕点平面图,用目标数据在kd树中寻找最近邻时,最核心的两个部分是: 

1 寻找近似点-寻找最近邻的叶子节点作为目标数据的近似最近点。

2 回溯-以目标数据和最近邻的近似点的距离沿树根部进行回溯和迭代。

回溯和迭代的目的是因为找到的点不一定就是最邻近的,最邻近肯定距离查询点更近,应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻还需要进行‘回溯‘操作:算法沿搜索路径反向查找是否有距离查询点更近的数据点。

 

 

代码

 1 import math
 2 
 3 import numpy as np
 4 
 5 class KdNode:
 6     data = None
 7     left = None
 8     right = None
 9 
10     def __init__(self, data, left, right):
11         self.data = data
12         self.left = left
13         self.right = right
14 
15 
16 def distance(p1, p2):
17     dimension = p1.size
18     sum = 0.
19     for i in range(0, dimension):
20         sum += (p1[i] - p2[i]) ** 2
21     return math.sqrt(sum)
22 
23 
24 class Kdtree:
25 
26     def __init__(self, data):
27         self.tree = self.buildChildTree(np.array(data))
28 
29     def buildChildTree(self, data):
30         if len(data) == 0 or data is None:
31             return None
32         dimension = data.ndim
33         if data.size == dimension:  # data.shape[1] 对一维情况会报错,出此下策。。。
34             return KdNode(data[0,], None, None)
35         vars = []
36         for i in range(dimension):
37             vars.append(np.var(data[:,i]))
38         max_dimension = vars.index(max(vars))
39         data_sorted = data[np.argsort(data[:,max_dimension]),:]
40         mid_i = data_sorted.shape[0] // 2
41         n = KdNode(None, None, None)
42         n.left = self.buildChildTree(data_sorted[:mid_i,])
43         n.right = self.buildChildTree(data_sorted[mid_i+1:,])
44         n.data = data_sorted[mid_i,]
45         return n
46 
47     def findNearestPoint(self, point):
48         cur = self.tree
49         nearest = self.tree.data
50         search_path = []
51         while 1:
52             search_path.append(nearest)
53             root = cur
54             if cur.left is None and cur.right is None:
55                 break
56             if root.left:
57                 if distance(root.left.data, point) < distance(nearest, point):
58                     cur = root.left
59                     nearest = root.left.data
60                     continue
61             elif root.right:
62                 if distance(root.right.data, point) < distance(nearest, point):
63                     cur = root.right
64                     nearest = root.right.data
65                     continue
66             break
67         return nearest, search_path
68 
69 
70 if __name__ == __main__:
71     kd = Kdtree([(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)])
72     n,p = kd.findNearestPoint(np.array([2, 4.5]))
73     print(nearest point: , n,    search path: ,p)   

 

KD树

上一篇:一颗高度为3的B+树能存多少行数据?


下一篇:如何选择 Linux 操作系统版本?