KD-Tree

• 实现
  • 逐次划分平面XY轴成树
  • 树的深度${\log }_{2}N$
• 找最近邻
  • 从叶子节点开始
    • 边界距离>已知最小，忽略
    • 边界的距离<已知最小，去边界区域找
  • 时间复杂度
    • 最快${\log }_{2}N$
    • 最慢n
• 缺点
  • 只参考最近点，可能有”价格洼地”
    • 正好周围学区房，但当前点不是
    • 原因是特征考虑太小
      • 先天只能强制划分
  • 极端值噪声影响大
  • 划分块数过于依赖经验
• 优化
  • 维度灾难
    • 多个划分后，所有边界距离可能都小于最小距离
      • 时间复杂度退化，变慢
    • Ball-Tree
  • 求最远点
    • 判断距离时取反
  • 最近N个点