distance - 有没有一种快速的方法来计算点依赖距离函数下数据集中的最近点

Question

我正在寻找一种（快速）方法来计算数据集中与（x，y）相关距离函数下给定点 x 的最近点 y。

我的距离函数的形式为：d(x,y) = 1/f(x,y) * |||xy||^2，其中 ||x|| 表示标准欧几里得范数。函数 f(x,y) 满足所有必要属性，例如 d(x,y) 是距离测量，即正、对称、...

对于“正常”距离函数，我可以对数据本身进行一些转换并使用一些 k 最近邻方法。但是对于这种情况，我找不到有用的东西。有人有想法吗？

现在，我正在使用 Julia 来实现。

标签： distancenearest-neighbor

Answer 1

只要 d(x,y) 是“凸的”，您就应该能够使用大多数标准空间索引（kd-tree、r-tree、四叉树和它们的导数）。

“凸”是指围绕 P 的等距点曲线是凸的。例如，对于欧几里得，这是一个圆形，对于曼哈顿/出租车距离，它是一个正方形。

这是必需的，因为这些索引通常将数据划分为正方形、矩形或半空间（kd-tree），因此它们依赖于通过计算到边界矩形的角或边的距离来计算到一组点的最小距离. 只要您的距离函数是凸的（或至少不是凹的），那么这些索引的任何索引都应该起作用。