知识卡片

普通读书笔记卡 · 8093.q.5 · 生成模型:未记录

最近邻用区域距离下界剪枝

理解等级:中级

kd树逐层按某坐标切分点集。最近邻搜索先维护当前最小距离,再检查另一子区域到目标的距离下界;只有该下界不可能改善当前结果时才能跳过该区域。切分面距离是一种可用下界,区域包围盒可提供更强下界。

平衡树高度为 O(log n) 不保证最近邻只访问一条路径;查询可能跨越许多区域,最坏仍 O(n)。高维或高度聚集数据常削弱剪枝效果。

270允许浮点误差但认为影响不致命;实际影响依业务阈值而定,接口应约定相等距离的选择、维度匹配和空集行为。

272的03435每层选择当前维度中位点并递归构建两个子树;选择算法的成本和重复坐标分配影响构建效率。书中引用四元组BFPRT实现的最坏线性结论,不能不加证明地套用;参见最坏线性选择卡。

273的03436–03438记录当前最佳距离并依据目标到切分面的垂直距离选择一侧或两侧;若要求返回所有等距点,应按接口语义处理相等边界。空树返回null,维度和坐标有效性仍需校验。

274说平衡树能排除近半点,但某些数据和查询会在多层同时探索两侧;平衡只限制树高,不单独保证对数最近邻查询。

275的03439–03442展示高维双分支搜索增多及与穷举的实验交叉;即便树平衡,剪枝不足时查询可能接近 O(n),每次距离计算还要考虑维度d。书中一处称高维性能逼近log(n),与其后线性退化描述矛盾,应以实际访问量为准。

276提到自底向上的变种;无论顺序如何,都必须检查可能含更近点的区域。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 7 处

    • · 查看原书依据

      kd树来表示图9-18的19个点。kd树顾名思义,是沿着坐标系统的垂直坐标轴,切分一个k维的平面。在接下来的讨论中,我们假设这棵树是基于二维平面的,但是我们也要注意,kd树可以扩展到任意高维。一棵kd树是一个递归的二叉树结构,其节点包含多个点以及一个坐标标记(x或者y),这个标记表示切分线。根节点表

    • · 查看原书依据

      浮点的误差导致算法选择了错误的点,但是,由于这两个点如此接近,所以不会对结果产生致命的影响。 [1]在Voronoi图中,凸包上的区域是“开口”的,直到遇到图的边界,而内部节点的区域面积有限。

    • · 查看原书依据

      中位元素,然后将在这个元素“下方”的元素插入左子树,“上方”的元素插入右子树。这段代码适用于任何维度。 例9-4:递归构建kd树 选择操作在第4章的“快速排序”一节中已经描述过了。能够在平均情况下在O(n)时间内选择第k小的元素,但是,在最坏情况下会退化到O(n2)的性能。为了避免这种情况,我们使用

    • · 查看原书依据

      最邻近点查询的kd树实现 理解最邻近点算法的关键在于我们要能够快速定位点x所在的区域,因为这个区域内很可能存在最近的点。之后我们从根节点到这个区域,递归地检查是否存在其他的更近的点,因为kd树的矩形区域划分是根据输入集的变化而变化。在一棵不平衡的kd树中,这个检查过程的开销可能会达到O(n),因此我

    • · 查看原书依据

      两边的区域来寻找最近点时。

    • · 查看原书依据

      两个递归调用和单个递归调用发生的平均次数。 我们可以看到,在随机生成的二维数据上,产生两个调用的次数是0.3*log(n),但是在十维上,这个数目会升到342*log(n)(1000倍左右的提升)。我们可以观察到,这个估计值大约是O(log n)。但是当d增长到“足够接近”n时,会发生什么呢?图9-

    • · 查看原书依据

      从底向上遍历,最后访问根节点[1]。 [1]参见http://www.codeproject.com/KB/architecture/KDTree.aspx.

    参考来源

    - 位置:《算法技术手册》第9章《最近点查询》(spine1662;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1625.html;u269-ch09-006)。 - 结论依据:269全文、03431–03434格子、Voronoi及kd树示意实读。 - 原始内容:kd树来表示图9-18的19个点。kd树顾名思义,是沿着坐标系统的垂直坐标轴,切分一个k维的平面。在接下来的讨论中,我们假设这棵树是基于二维平面的,但是我们也要注意,kd树可以扩展到任意高维。一棵kd树是一个递归的二叉树结构,其节点包含多个点以及一个坐标标记(x或者y),这个标记表示切分线。根节点表 - 位置:《算法技术手册》第9章《输入/输出》(spine1662;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1625.html;u270-ch09-006)。 - 结论依据:270允许浮点误差但认为影响不致命;实际影响依业务阈值而定,接口应约定相等距离的选择、维度匹配和空集行为。 - 原始内容:浮点的误差导致算法选择了错误的点,但是,由于这两个点如此接近,所以不会对结果产生致命的影响。 [1]在Voronoi图中,凸包上的区域是“开口”的,直到遇到图的边界,而内部节点的区域面积有限。 - 位置:《算法技术手册》第9章《驱动因素》(spine1664;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1627.html;u272-ch09-006)。 - 结论依据:272的03435每层选择当前维度中位点并递归构建两个子树;选择算法的成本和重复坐标分配影响构建效率。书中引用四元组BFPRT实现的最坏线性结论,不能不加证明地套用;参见最坏线性选择卡。 - 原始内容:中位元素,然后将在这个元素“下方”的元素插入左子树,“上方”的元素插入右子树。这段代码适用于任何维度。 例9-4:递归构建kd树 选择操作在第4章的“快速排序”一节中已经描述过了。能够在平均情况下在O(n)时间内选择第k小的元素,但是,在最坏情况下会退化到O(n2)的性能。为了避免这种情况,我们使用 - 位置:《算法技术手册》第9章《解决方案》(spine1665;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1628.html;u273-ch09-006)。 - 结论依据:273的03436–03438记录当前最佳距离并依据目标到切分面的垂直距离选择一侧或两侧;若要求返回所有等距点,应按接口语义处理相等边界。空树返回null,维度和坐标有效性仍需校验。 - 原始内容:最邻近点查询的kd树实现 理解最邻近点算法的关键在于我们要能够快速定位点x所在的区域,因为这个区域内很可能存在最近的点。之后我们从根节点到这个区域,递归地检查是否存在其他的更近的点,因为kd树的矩形区域划分是根据输入集的变化而变化。在一棵不平衡的kd树中,这个检查过程的开销可能会达到O(n),因此我 - 位置:《算法技术手册》第9章《结论》(spine1666;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1629.html;u274-ch09-006)。 - 结论依据:274说平衡树能排除近半点,但某些数据和查询会在多层同时探索两侧;平衡只限制树高,不单独保证对数最近邻查询。 - 原始内容:两边的区域来寻找最近点时。 - 位置:《算法技术手册》第9章《分析》(spine1667;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1630.html;u275-ch09-006)。 - 结论依据:275的03439–03442展示高维双分支搜索增多及与穷举的实验交叉;即便树平衡,剪枝不足时查询可能接近 O(n),每次距离计算还要考虑维度d。书中一处称高维性能逼近log(n),与其后线性退化描述矛盾,应以实际访问量为准。 - 原始内容:两个递归调用和单个递归调用发生的平均次数。 我们可以看到,在随机生成的二维数据上,产生两个调用的次数是0.3*log(n),但是在十维上,这个数目会升到342*log(n)(1000倍左右的提升)。我们可以观察到,这个估计值大约是O(log n)。但是当d增长到“足够接近”n时,会发生什么呢?图9- - 位置:《算法技术手册》第9章《变种》(spine1668;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1631.html;u276-ch09-006)。 - 结论依据:276提到自底向上的变种;无论顺序如何,都必须检查可能含更近点的区域。 - 原始内容:从底向上遍历,最后访问根节点[1]。 [1]参见http://www.codeproject.com/KB/architecture/KDTree.aspx.