如何构建KD树？求KD树学习资源及练习案例正确性校验

一、KD树的构建步骤 #

• 选择划分维度：要么按循环轮询（比如2D数据先x轴，再y轴，循环往复），要么挑选方差最大的维度（能让划分出的子集更均匀）。
• 确定划分点：在选定维度上，取中位数对应的样本点，将数据集拆成两半——小于中位数的样本归左子树，大于的归右子树。
• 递归构建子树：对左右两个子集重复上述操作，直到子集为空或只剩单个样本为止。

二、优质学习资源 #

• 视频类：
  • 斯坦福CS229机器学习课程中的KD树章节，讲解侧重实际应用场景，逻辑清晰。
  • B站“白板推导系列”的KD树专题，从原理到构建过程逐步拆解，适合入门理解。
• 论文&文档类：
  • 原始论文《Multidimensional binary search trees used for associative searching》，是KD树的奠基性文献，能了解设计初衷。
  • scikit-learn官方文档中KD树相关章节，结合代码示例讲解工程实现细节，实用性强。

三、你的案例构建检查 #

你给出的6个点：(30,40)、(5,25)、(10,12)、(70,70)、(50,30)、(35,45)，正确的构建流程如下：

1. 根节点（第1层，按x轴划分）：
   所有点的x坐标为5、10、30、35、50、70，中位数对应第3和第4个点之间，选实际存在的样本的话，(30,40)或(35,45)都合理。假设选(30,40)，左子集为{(5,25),(10,12)}，右子集为{(35,45),(50,30),(70,70)}。
2. 左子节点（第2层，按y轴划分）：
   左子集的y坐标为12、25，中位数选(5,25)，它的左子树为{(10,12)}，右子树为空。
3. 右子节点（第2层，按y轴划分）：
   右子集的y坐标为30、45、70，中位数是(35,45)，它的左子集为{(50,30)}，右子集为{(70,70)}。
4. 叶子节点：剩下的(10,12)、(50,30)、(70,70)均为叶子节点。

如果你的构建中根节点选的是(35,45)也完全正确，只要每一层划分维度符合规则、划分点是对应维度的中位数样本，结构就没问题。

内容的提问来源于stack exchange，提问作者necrotoxin