是的.
kd-
树（
k
维搜索树）是把二叉搜索树推广到多维数据的一种主存数据结构.我们将先
介绍这种思想,然后讨论怎样使这种思想适合存储的块模型.
树是一个二叉树,它的内
部结点有一个相关联的属性
a
和一个值
V
,它将数据点集分成两个部分：
值小于
的部分
和
值大于等于
的部分.
由于所有维的属性在层间交替出现,
所以树的不同层上的属性是
不同的
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树按照一定的划分规则把这个三维空间划分了多个空间,如下图所示：
常规的k-d tree的构建过程为：
对于构建过程,有两个优化点：
如之前所述,kd树中,kd代表k-dimension,每个节点即为一个k维的点.每个非叶节点可以想象为一个分割超平面,用垂直于坐标轴的超平面将空间分为两个部分,这样递归的从根节点不停的划分,直到没有实例为止.经典的构造k-d tree的规则如下：
kd树的检索是KNN算法至关重要的一步,给定点p,查询数据集中与其距离最近点的过程即为最近邻搜索.
上述两次实例表明,当查询点的邻域与分割超平面两侧空间交割时,需要查找另一侧子空间,导致检索过程复杂,效率下降.
一般来讲,最临近搜索只需要检测几个叶子结点即可,如下图所示：
但是,如果当实例点的分布比较糟糕时,几乎要遍历所有的结点,如下所示：
研究表明N个节点的K维k-d树搜索过程时间复杂度为： .
Sklearn中有KDTree的实现,仅构建了一个二维空间的k-d tree,然后对其作k近邻搜索及指定半径的范围搜索.多维空间的检索,调用方式与此例相差无多.
实现kNN算法时,最简单的实现方法就是线性扫描,正如我们上一章节内容介绍的一样- K近邻算法 ,需要计算输入实例与每一个训练样本的距离.当训练集很大时,会非常耗时.
为了提高kNN搜索的效率,可以考虑使用特殊的结构存储训练数据,以减少计算距离的次数,KD-Tree就是其中的一种方法.
K维空间数据集
其中
首先先沿 x 坐标进行切分,我们选出 x 坐标的中位点,获取最根部节点的坐标
在下一步中 ,对应 y 轴,左右两边再按照 y 轴的排序进行切分,中位点记载于左右枝的节点.得到下面的树,左边的 x 是指这该层的节点都是沿 x 轴进行分割的.
空间的切分如下
下一步中 ,对应 x 轴,所以下面再按照 x 坐标进行排序和切分,有
最后只剩下了叶子结点,就此完成了 kd 树的构造.
输入：已构造的kd树,目标点x
输出：x的k个最近邻集合L
KD-Tree的平均时间复杂度为 ,N为训练样本的数量.
KD-Tree试用于训练样本数远大于空间维度的k近邻搜索.当空间维数接近训练样本数时,他的效率会迅速下降,几乎接近线性扫描.
首先我们按照构造好的KD-Tree,从根结点开始查找
和这个节点的 x 轴比较一下,p 的 x 轴更小.所以呢我们向左枝进行搜索：
此时此刻呢需要对比 y 轴
p 的 y 值更小,所以呢向左枝进行搜索：
在二维图上是蓝色的点
所以呢,在分割线的另一端可能有更近的点.于是我们在当前结点的另一个分枝从头执行步骤1.好,我们在红线这里：
此时处于x轴切分,所以呢要用 p 和这个节点比较 x 坐标:
然后 回退,判断出不是顶端节点,往上爬.
这个距离小于 L 与 p 的最大距离,所以呢我们要到当前节点的另一个枝执行步骤1.当然,那个枝只有一个点.
计算距离发现这个点离 p 比 L 更远,所以呢不进行替代.
然后回退,不是根结点,我们向上爬
这个是已经访问过的了,所以再向上爬
再爬
我们进行计算比对发现顶端节点与p的距离比L还要更远,所以呢不进行更新.
然后计算 p 和分割线的距离发现也是更远.
所以呢也不需要检查另一个分枝.
声明：此文章为本人学习笔记,参考于：
以上就是土嘎嘎小编为大家整理的kd树构造代码java相关主题介绍,如果您觉得小编更新的文章只要能对粉丝们有用,就是我们最大的鼓励和动力,不要忘记讲本站分享给您身边的朋友哦！！