知识卡片
KD树的构造
暴力版 K 近邻每次预测都要算一遍与所有训练点的距离,样本量大时不可接受。KD 树用一个索引把”找最近邻”从全表扫描改成沿树定向搜索。
它是什么。KD 树是一种二叉树,把 K 维空间中的点按区域层层切开存储。每个节点对应一个超矩形区域,每次用一个垂直于某个坐标轴的超平面把当前区域一分为二。切分点选在该轴的中位数上,所以树是平衡的。
构造三步
- 选轴:轮流选坐标轴(第一层 x 轴,第二层 y 轴,第三层再回到 x 轴)。
- 取中位数:把当前区域的点按该轴坐标排序,取中位数作为切分点。点数奇数取中间,偶数取中间偏后一位——目标是让中位点落在分割线上,成为节点本身。
- 递归:小于切分值的点进左子空间,大于的进右子空间,对两个子空间重复上述步骤,直到每个点都被划分。
一个实例。六个二维点:(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 条
还没有人提交反馈。
在整书笔记中的位置
- · 第05章 K近邻
原书出处 · 1 处
- 第5章 K近邻 5.4.1 构造KD树 · 查看原书依据
构造KD树的过程相当于不断地用垂直于坐标轴的超平面对K维空间进行切分,构成一系列的K维超矩形区域。KD树的每一个节点对应于一个k维超矩形区域。
参考来源
- 位置:《机器学习基础:从入门到求职》第5章《K近邻》5.4.1 构造KD树(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00008.html)
- 结论依据:原文定义 KD 树为对 K 维空间实例点做树状划分的二叉树,并用六个二维点逐步演示轮流选轴、取中位数、划分子空间的过程。
- 原始内容:构造KD树的过程相当于不断地用垂直于坐标轴的超平面对K维空间进行切分,构成一系列的K维超矩形区域。KD树的每一个节点对应于一个k维超矩形区域。