KD树是怎样进行搜索的？

291294878

2018-10-25 阅读量: 1137

KD树是怎样进行搜索的？

1、首先从根节点开始递归往下找到包含x的叶子节点，每一层都是找对应的xi

2、将这个叶子节点认为是当前的“近似最近点”

3、递归向上回退，如果以x圆心，以“近似最近点”为半径的球与根节点的另一半子区域边界相交，则说明另一半子区域中存在与x更近的点，则进入另一个子区域中查找该点并且更新”近似最近点“

4、重复3的步骤，直到另一子区域与球体不相交或者退回根节点

5、最后更新的”近似最近点“与x真正的最近点

KD树进行KNN查找：

通过KD树的搜索找到与搜索目标最近的点，这样KNN的搜索就可以被限制在空间的局部区域上了，可以大大增加效率

KD树搜索的复杂度：

当实例随机分布的时候，搜索的复杂度为log(N)，N为实例的个数，KD树更加适用于实例数量远大于空间维度的KNN搜索，如果实例的空间维度与实例个数差不多时，它的效率基于等于线性扫描。

0.0000

关注作者

发表评论

暂无数据

CDA考试动态

CDA报考指南

推荐帖子