kd树构造代码java,kd树索引

什么叫平衡二叉树，KD树是不是就是平衡二叉树呢？

是的。

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。构造与调整方法 平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci数列 1是根节点 F(n-1)是左子树的节点数量 F(n-2)是右子数的节点数量。

kd-

树（

k

维搜索树）是把二叉搜索树推广到多维数据的一种主存数据结构。我们将先

介绍这种思想，然后讨论怎样使这种思想适合存储的块模型。

kd-

树是一个二叉树，它的内

部结点有一个相关联的属性

a

和一个值

V

，它将数据点集分成两个部分：

a

值小于

V

的部分

和

a

值大于等于

V

的部分。

由于所有维的属性在层间交替出现，

所以树的不同层上的属性是

不同的

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近邻搜索及指定半径的范围搜索。多维空间的检索，调用方式与此例相差无多。

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)]。

声明：此文章为本人学习笔记，参考于：