• 递归地将空间划分为k维的超矩形区域
  • 优点：适用于低维数据(通常d<20)，平均查询复杂度O(log n)
    2.精确最近邻搜索
  1. 1
    2
    3
    from sklearn.neighbors import KDTree
    tree = KDTree(points)
    dist, ind = tree.query(query_point, k=k)

KD树构建过程

  1. 选择当前维度（通常循环选择或选择方差最大的维度）
  2. 找到当前维度上的中位数作为分割点
  3. 将数据集分为小于中位数和大于中位数的两部分
  4. 对两个子集递归构建左右子树

KD树搜索过程

（1）向下搜索

  1. 从根节点开始，比较 查询点 和 当前节点 在 当前分割维度 上的值：
    • 如果 query[axis] < node.point[axis]，进入 左子树。
    • 否则，进入 右子树。
  2. 递归执行，直到到达叶子节点。

（2）回溯检查

  • 在找到最近候选点后，检查 另一侧子树是否可能存在更近的点：
    • 计算 查询点到当前分割平面的距离 dist = abs(query[axis] - node.point[axis])。
    • 如果 dist < 当前最近距离，说明另一侧子树可能包含更近的点，需要搜索(同1)。

（3）更新最近邻

  • 在搜索过程中，维护 当前最近邻 和 最小距离，遇到更近的点时更新。

KD树需要存储所有原始数据点，一棵存储 n个m维点 的KD树，其空间复杂度为 O(n·m)，与暴力存储相同，每个节点还需记录分割维度和左右子节点指针O(n)
KD树是一种特殊的二叉树，具有以下二叉树的特征：

  1. 每个节点最多有两个子节点（左子树和右子树）。
  2. 递归结构：左/右子树也是KD树。

KD树核心知识点测验（10道选择/判断题）

选择题

  1. KD树最适合处理什么类型的数据？
    A) 高维稀疏数据
    B) 低维稠密数据 ✓
    C) 时间序列数据
    D) 图结构数据

  2. 构建KD树时，选择分割维度的常用策略不包括：
    A) 循环选择各维度
    B) 选择方差最大的维度
    C) 随机选择维度 ✓
    D) 选择数据范围最大的维度

  3. KD树搜索的平均时间复杂度是：
    A) O(1)
    B) O(log n) ✓
    C) O(n)
    D) O(n log n)

  4. 当数据维度超过多少时，KD树的效率会显著下降？
    A) 5
    B) 10
    C) 20 ✓
    D) 50

  5. KD树回溯搜索的关键判断依据是：
    A) 查询点到分割平面的距离是否小于当前最近距离 ✓
    B) 子树中点的数量是否足够多
    C) 查询点所在的象限
    D) 数据点的分布密度

判断题

  1. KD树可以保证找到精确的最近邻而非近似结果。 (✓) 正确

  2. KD树适合频繁更新的动态数据集。 (×) 错误（插入/删除成本高）

  3. 在构建KD树时，总是选择第一个维度进行分割是最佳实践。 (×) 错误（应交替或选方差最大）

  4. KD树在高维空间中的效率可能退化为近似暴力搜索。 (✓) 正确

  5. KD树的搜索过程只需要沿着一条路径向下查找，不需要回溯。 (×) 错误（必须回溯检查相邻区域）