KD树是怎样进行搜索的？

2018-10-25 阅读量: 882

数据分析师机器学习

扫码加入数据分析学习群

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

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

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

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

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

KD树进行KNN查找：

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

KD树搜索的复杂度：

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

添加CDA认证专家【维克多阿涛】，微信号：【cdashijiazhuang】，提供数据分析指导及CDA考试秘籍。已助千人通过CDA数字化人才认证。欢迎交流，共同成长！

0.0000 0 4 踩关注作者收藏

暂无数据

评论(0)