计算两条 GPS 轨迹线的相似度

Question

我用 GPS 追踪器记录了约 2500 次户外活动。我想自动对类似的活动进行分组。让我们看一下两个相关但不完全相同的活动：

一个基本问题是我不能只是“压缩”每项活动中的点并期望它们相邻。不同的速度会很快破坏对齐。因此，我创建了一种相似性度量，该度量基于给定点从一个活动到任何活动的最小距离。人们可以将其绘制为从短期活动到长期活动的所有点的分位数分布：

在这里可以看到，超过 90% 的短活动点与长活动的距离在 7.5 米以内。鉴于 GPS 测量之间的距离和一般测量不确定性，可以说这些部分是重叠的。大约 3% 的点距离可达 20 m。所以距离还不是很远。这是有道理的，较短的活动实际上是较大活动的子集。

然后可以反过来做。由于较长的活动具有独特的点，因此分位数分布上升得更快：

我们看到大约 30% 的点在做空活动中有密切的对应关系。但随后距离只会增加，有些点距离较短活动的最近点有 1000 米。这显然是一条不同的路线。

这个指标看起来还不错。问题是，即使我只从一项活动中抽取 50 或 100 个点，我也需要根据参考的所有点来检查它们。两者都采样会导致很大的差距并且不起作用。计算需要一秒的时间。

大约有 2500 项活动，我需要进行大约 6,250,000 次成对比较。这大约需要 180 个小时，也就是一个多星期。当添加新活动时，增量工作也会花费很多分钟，我觉得这太长了。

我尝试通过检查起点和终点是否接近来减少比较次数，但这也需要相当长的时间。

根本问题是，这种相似性检测方法的复杂度为 O(N²)，而 O(N log N) 之类的方法会更好。为了实现这一点，我需要能够找到一种传递比较的方法，以便我可以将它们排列在树状结构中，甚至可能找到一种分桶技术。

可以做的一件事是将纬度/经度空间平铺成精细网格，然后根据起点创建二维桶。人们只会与同一存储桶内的活动进行比较。但是，当类似的活动位于同一个存储桶中时，这将会失败。而且它会再次变成 O(N²)，因为我的活动中有很大一部分是沿着同一条路线去杂货店。

是否有某种方法可以将活动数量 N = ~2500 中的相似度降低到 O(N log N) 甚至 O(N)？

Answer 1

这里真正的问题是，“如何在不使用暴力的情况下有效地找到该集合中与该集合中的任何值最接近的值？”

答案是使用一些为其设计的数据结构，例如四叉树。然后用它来进行最近邻搜索。

您可以使用库自行编程来实现该数据结构，也可以将数据存储在知道如何执行此操作的数据库中。例如，PostgreSQL 对最近邻搜索有良好的支持。假设您安装了 PostGIS，相关查询将帮助您解决您的问题。