计算科学 - 一种寻找最近邻的有效算法 - 吾爱随笔录

一种寻找最近邻的有效算法

计算科学算法表现

2021-12-12 02:15:19

所以想象我有一个 $m$ 向量每个维度 $d$ . 让我们打电话给他们， $\vec x_{i}$ ，和 $i = 1, 2, 3, 4, 5, \dots, m$ . 现在的想法是找到的邻居 $\vec x_{i}$ （打电话给他们 $\vec x_{j}$ )，在一个半径的球内 $r$ . 所以，

| | {\vec{x}}_{i} - {\vec{x}}_{j} | | \leq r

$|| \vec x_{i} - \vec x_{j} || \le r$ .

笔记： $|| \cdots ||$ 是欧几里得范数。

天真地可以计算所有之间的距离 $j$ 是针对特定的 $i$ , 然后对它们进行排序，只保留小于的元素 $r$ . 这对于大型计算来说是昂贵的 $m$ 和 $d$ .

所以问题是我如何有效地计算邻居 $x_{j}$ ?

1个回答

我怀疑您可以利用以下事实来逃避信息的一部分

‖ x_{i} - x_{j} ‖ = ‖ x_{i} - x_{k} + x_{k} - x_{j} ‖ \geq ‖ x_{i} - x_{k} ‖ - ‖ x_{k} - x_{j} ‖ .

$\|x_i-x_j\| = \|x_i-x_k+x_k-x_j\| \ge \|x_i-x_k\| - \|x_k-x_j\|.$ 您可以通过以下方式使用它：说，你想要

r = 1

$r=1$ . 如果

x_{1}

$x_1$ 和

x_{2}

$x_2$ 相距四个单位（不是邻居），并且

x_{2}

$x_2$ 和

x_{3}

$x_3$ 距离一个单位，那么

x_{1}

$x_1$ 和

x_{3}

$x_3$ 至少三个单位相距 - 也不是邻居。我不需要计算之间的距离

x_{1}

$x_1$ 和

x_{3}

$x_3$ 来确定。

这意味着可以通过仅知道距离矩阵条目的子集来使用这种“反向三角不等式”来确定邻域

D_{i j} = ‖ x_{i} - x_{j} ‖ .

$D_{ij} = \|x_i-x_j\|.$ 问题是：您需要知道什么子集才能做出所有决定？如果确定最小子集的算法是 NP，我不会感到很惊讶，但人们可能会想出一种更便宜的算法，从

D_{i j}

$D_{ij}$ 确定哪些条目不需要计算，然后计算其他一些当前未知的条目，并迭代直到每个条目

D

$D$ 你要么计算了它的值，要么确定你不需要它。

其它你可能感兴趣的问题

上一篇具有条件约束和一些未知指标变量的约束规划问题下一篇基于状态方程的变系数隐式方法