如何构建KD树？_CDA答疑社区

2018-10-25 阅读量: 829

数据分析师机器学习

如何构建KD树？

扫码加入数据分析学习群

KD树是一个二叉树，表示对K维空间的一个划分，可以进行快速检索（那KNN计算的时候不需要对全样本进行距离的计算了）

在k维的空间上循环找子区域的中位数进行划分的过程。

假设现在有K维空间的数据集：

1、首先构造根节点，以坐标的中位数b为切分点，将根结点对应的矩形局域划分为两个区域，区域1中,区域2中

2、构造叶子节点，分别以上面两个区域中的中位数作为切分点，再次将他们两两划分，作为深度1的叶子节点，（如果a2=中位数，则a2的实例落在切分面）

3、不断重复2的操作，深度为j的叶子节点划分的时候，索取的的，直到两个子区域没有实例时停止

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

9.7428 1 2 踩关注作者收藏

暂无数据