知识卡片

结构图卡 · 9826.f · 生成模型:DeepSeek-V4.1-Flash

KD树的构造

理解等级:高级

暴力版 K 近邻每次预测都要算一遍与所有训练点的距离,样本量大时不可接受。KD 树用一个索引把”找最近邻”从全表扫描改成沿树定向搜索。

它是什么。KD 树是一种二叉树,把 K 维空间中的点按区域层层切开存储。每个节点对应一个超矩形区域,每次用一个垂直于某个坐标轴的超平面把当前区域一分为二。切分点选在该轴的中位数上,所以树是平衡的。

构造三步

  1. 选轴:轮流选坐标轴(第一层 x 轴,第二层 y 轴,第三层再回到 x 轴)。
  2. 取中位数:把当前区域的点按该轴坐标排序,取中位数作为切分点。点数奇数取中间,偶数取中间偏后一位——目标是让中位点落在分割线上,成为节点本身。
  3. 递归:小于切分值的点进左子空间,大于的进右子空间,对两个子空间重复上述步骤,直到每个点都被划分。

一个实例。六个二维点:(2,3)、(5,4)、(9,6)、(4,7)、(8,1)、(7,2)。

  • x 坐标排序为 2,4,5,7,8,9,中位数 7 → 根节点 (7,2),超平面 x=7。左子空间 {(2,3),(5,4),(4,7)},右子空间 {(9,6),(8,1)}。
  • 左子空间按 y 轴切,y 排序 3,4,7,中位 4 → 节点 (5,4),分成下 (2,3)、上 (4,7)。
  • 右子空间按 y 轴切,y 排序 1,6,中位取偏后一位 6 → 节点 (9,6),下子空间含 (8,1),上子空间为空。

为什么取中位数。它保证左右两侧点数接近,树高约为 log M,搜索时不必一路退化。若随便挑点做切分,极端情况下树会退化成链表,索引就失去意义。

结构图:

flowchart TD
    A[二维点集 6 个点] --> B[按x轴排序取中位数 x=7]
    B --> C[根节点 7,2 即超平面x=7]
    C --> D[左子空间 三个点]
    C --> E[右子空间 两个点]
    D --> F[按y轴切 y=4 得节点 5,4]
    F --> G[叶子 2,3]
    F --> H[叶子 4,7]
    E --> I[按y轴切 y=6 得节点 9,6]
    I --> J[下叶子 8,1]

边界:树高被维数拖累。维度升高后,同一区域内点数不再随切分快速减少,”近邻”变得不局部,索引的收益下降——这也是高维下常退回暴力搜索的原因。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《机器学习基础:从入门到求职》第5章《K近邻》5.4.1 构造KD树(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00008.html) - 结论依据:原文定义 KD 树为对 K 维空间实例点做树状划分的二叉树,并用六个二维点逐步演示轮流选轴、取中位数、划分子空间的过程。 - 原始内容:构造KD树的过程相当于不断地用垂直于坐标轴的超平面对K维空间进行切分,构成一系列的K维超矩形区域。KD树的每一个节点对应于一个k维超矩形区域。