线串之间的相似度

Question

我有 GPS 记录的许多轨迹，更正式地可以将其描述为许多线串。

现在，某些记录的轨迹可能是同一路线的记录，但由于 GPS 系统的不准确性，事实上，记录是在不同的场合进行的，并且它们可能是以不同的速度记录的，因此它们不会完美匹配，但当人类在地图上查看时仍然看起来足够接近，以确定它实际上与已记录的路线相同。

我想找到一种计算两个线串之间相似度的算法。我想出了一些本土方法来做到这一点，但想知道这是否是一个已经有很好的算法来解决的问题。

鉴于相似的均值代表地图上的相同路径，您将如何计算相似度？

编辑： 对于那些不确定我在说什么的人，请查看此链接以了解行字符串的定义： http://msdn.microsoft.com/en-us/library/bb895372.aspx - 我是 不是 询问字符串。

Answer 1

计算 弗雷谢距离 在每对轨道上。该距离可用于衡量轨迹的相似度。

数学警报： Fréchet 是该领域的先驱 度量空间 这与您的问题相关。

Answer 2

我会根据估计的可能错误在第一行周围添加一个缓冲区，然后确定第二行是否完全适合缓冲区。

Answer 3

要确定“相同路线”，请创建最小的归一化路径向量集，计算总功率差并将总功率差与质量度量进行比较。

1. 根据总路径长度标准化 GPS 航路点，
2. 将路径向量放在一起，根据每个路点的最短向量为每条路径创建一组新的路径向量，
3. 计算向量长度归一化路径加权中每个向量端点之间的总功率差，以及
4. 与质量测量进行比较。

直观地调整差异的功率（例如，从平方差开始）和质量度量（例如总功率差的百分比）。该算法产生路径匹配的连续质量度量以及二进制结果（路径相同吗？）

保罗·汤布林说道：我会根据估计的可能误差在第一行周围添加一个缓冲区，然后确定第二行是否完全拟合在缓冲区中。

您可以在比较归一化向量端点时修改算法。您可以确定任何端点差异是否超过特定大小（实现 Paul 的缓冲区想法），或者如果端点位于“缓冲区”之外，则可以使用该事实忽略该端点差异，从而允许进行比较 忽略旁路旅行.

Answer 4

您可以沿着 LineString A 的每个点 (Pa) 行走，测量从 Pa 到 LineString B 最近的线段的距离，并对每个距离求平均值。

这不是一个快速或完美的方法，但应该能够提供有用的数字，并且实现起来相当快。

线串的起点和终点是否相似，或者它们的范围是否非常不同？

Answer 5

如果您将单个线串视为 [x,y] 点（或 [x,y,z] 点）的序列，那么您可以使用以下公式计算每对线串之间的相似度： 尼德曼-温施 算法。正如引用的维基百科文章中所述，Needleman-Wunsch 算法需要一个“相似矩阵”来定义一对点之间的距离。然而，使用函数代替矩阵会很容易。在你的情况下，你可以简单地使用 2D 欧氏距离 函数（如果您的点有高程，则为 3D 欧几里得函数）来提供每对点之间的距离。

Answer 6

我实际上支持那个人（Aaron F），他说你可能对编辑距离问题感兴趣（并引用了 这）。在我看来，他的回答是迄今为止最好的。

更具体地说，编辑距离（也称为编辑距离）并不严格测量逐个字符的距离，但也允许您执行插入和删除。这种距离测量的最佳算法可以在二次时间内计算出来（如果你的字符串很长，那么速度会很慢），但是计算生物学家对此有很好的启发式方法，你可能会对此感兴趣。查看 爆破 和 FASTA.

在您的问题中，您似乎正在处理数字字符串之间的差异，并且您关心数字。如果您提供更多信息，我也许可以根据您的目的指导您找到正确的 BLAST/FASTA/等变体。无论如何，您都可以考虑根据您的需求调整 BLAST 和 FASTA。它们很简单。

1: http://en.wikipedia.org/wiki/Levenshtein_distance, http://www.nist.gov/dads/HTML/Levenshtein.html