使用自定义距离函数的Accord KDTree

Question

我有一个图形数据结构，代表着一张路网（节点是道路上的点/交叉口，边是道路）。节点对象与纬度和经度相关联。

我正在使用Accord的KDTree类来查找给定GPS坐标附近的节点。由于Accord似乎没有Haversine距离作为内置距离函数（我错了吗？），所以我定义了自己的定制距离函数，并将其作为额外参数传递给KDTree.FromData()方法，如下所示：

        var nodes = graph.Nodes;
        //Initialize KD-tree with distance function defined as the cartesian approximate distance (in meters) 
        Func<double[], double[], double> distanceFunc = (x, y) => DistanceFunctions.ApproximateDistance(x,y);
        kdTreeOfNodes = KDTree.FromData<Node>(nodes.Select(x => new double[] { x.Value.Latitude, x.Value.Longitude }).ToArray(), nodes.ToArray(), distanceFunc);

请注意，'ApproximateDistance'是在一个单独的类中定义为静态方法，并且是对更正确的Haversine距离的笛卡尔近似值。

当尝试执行最后一行时，我会收到异常。在这一行中，我传递要放入KDTree中的数据（即包含纬度/经度数组的数组），以及相关联的节点，还有我的自定义距离函数。似乎这个FromData构造函数实际上（因为某种原因？）调用了我的ApproximateDistance函数，并将数组[1]和[1]作为两个输入参数，显然会引发异常，因为该方法需要两个二维数组。

我不知道为什么这个构造函数会调用我的ApproximateDistance函数（特别是使用这些奇怪的参数），并且似乎无法使用调试器找出原因...

- mchristos

---

你得到了什么异常？ - Oofpez

索引超出范围异常（ApproximateDistance函数期望传入二维数组，但实际传入了一维数组）。 - mchristos

Answer 1

K-d树在搜索过程中并不使用点对点距离，直到它们到达实际数据点。

相反，这是从分割平面的一个一维偏差。在这里，它可以是纬度或经度。

这就是为什么k-d-tree支持很少除了闵可夫斯基范数之外的其他东西的原因。

- Has QUIT--Anony-Mousse

---

对。你是在说我应该有一个一维距离函数吗？这对于纬度/经度来说会有问题，因为它们在技术上需要单独的距离函数（而经度的距离取决于“参考纬度” - 我们只能知道经度变化所对应的距离，如果我们知道当前所处的纬度）... 无论如何，为什么这个KDTree构造函数会调用这个方法？毕竟这个异常应该只在我尝试使用该类时才出现吧？ - mchristos

是的。除非你能将你的距离分解成一维函数，否则我认为这不会起作用。 - Has QUIT--Anony-Mousse

我不相信那个... 不过我对KD树的工作原理还没有完全理解。但是Accord有多个可以指定的距离函数，包括例如欧几里得距离（这基本上是一种多维距离，无法用一维距离函数来代替...）。 - mchristos

另外，还有一个问题仍然存在 - 为什么FromData构造函数调用distance方法？它是输入自己的“测试”值还是使用输入数据？ - mchristos

此外，关于多维距离：FromData方法的最后一个参数接受一个类型为Func<double[] , double[] , double>的函数对象，明确表示它期望一个多维距离函数（否则它只需要一个类型为Func<double, double, double>的函数）。 - mchristos

阅读kd-tree相关资料。我所知道的所有kd-tree实现都只支持闵可夫斯基范数，甚至只支持欧几里得范数。我从未使用过Accord（我不使用任何.net），因此我对构造函数的作用一无所知。请查看源代码。它可能使用double[]以便于使用，因为作者不想添加一个同时支持double[]（用于点）和double（仅用于kd-tree）的函数。 - Has QUIT--Anony-Mousse

Answer 2

Accord.NET中的K-d树在没有进行查找（即调用任何.Nearest或ApproximateNearest函数）时不应调用您的距离函数。正如Anony-Mousse所述，K-d树直到到达实际数据点（即进行搜索时）才使用点对点距离。

检查当前代码（Inspecting the current code），我无法看到代码如何在构建树之前调用ApproximateDistance，因为该方法仅在最后设置。

如果您仍然遇到此问题，请在问题跟踪器中注册，并提供触发问题的小示例，以便最终修复该问题。

此外，如果您需要其他依赖于点间距离的树种，您可能还想看一下最近添加的Vantage-Point Trees。

免责声明：我是Accord.NET中k-d树实现的作者。

- Cesar

---

谢谢你的回复！事实上，我在寻找图中的相邻边，所以寻找相邻节点是错误的方法，最终我采用了自己实现的基于网格的搜索，效果不错。 无论如何，距离方法被调用的问题很奇怪，但是目前我无法再复制这个问题了。 附：Vantage-Point Trees听起来很棒！ - mchristos