在道路网络图中区分两条路径？

Question

这是一个关于真实数据集的图论问题。我有一个大约100M个点的数据集，记录了城市中汽车在不同时间被摄像头拍摄到的情况，可以将其视为{摄像头ID、车牌号码ID、时间戳}元组。城市中大约有2000个摄像头，我们知道它们的位置，在我们有数据的一个月内，大约有1000万辆不同的车（车牌）。我试图确定任意两个摄像头（节点）之间存在多少唯一路径。这里的“路径”只是指相邻摄像头在时间上接近连续观察到相同车牌的情况。

问题是其中1/3的摄像头拍摄缺失：大多数摄像头的识别准确率为80%，而有些摄像头的准确率为0-10%。主要问题是：我们如何确定两条路径是否真正不同，而不仅仅是具有一些缺失观测的基础路径？

例如，考虑一些高流量路线A->C。如果只有一种从A到C的方式，比如通过B，那么你仍然会在A处看到很多汽车，而直接在C处是没有的，因为摄像头B恰好没有拍到它们（由于这个缺失数据点事实，大约1/3的总流量将是AC），因此AC看起来也是一条热门路径，而ABC才是人们从A到C真正走的唯一路径。目标是区分这些路径，以便我们可以在一天结束时计算A到C的独特路径数量，以研究交通网络对道路关闭的鲁棒性。

一种方法是比较路径的平均时间，但是通过空间的两条不同路线可能需要非常相似的时间。以下是我针对特定情况解决问题的方法：考虑从A到C的两条路线：ABC和AB'C，其中没有边B->B'。我们知道这实际上不能是一个基础路线ABB'C，因为那么我们会看到一个边B->B'，而我们没有看到。我想知道这个启发式方法是否可以推广（但当然，即使BB'是一个边，我们仍然希望区分路径，因为在这种情况下，我们不能保证ABB'C是唯一的真实路径）。

我也愿意使用外部API（如Google Maps）获取更多信息，但不太确定这会使问题变得更容易。我旨在解决两个任意远的摄像头之间任意长的路径问题，但我认为大多数这样的问题都可以简化为上述ABC vs AC问题的版本。

这是一个问题实例的图片示例。左下角可以看作是节点A，右上角是C。然后它变成了AC vs ABC vs ABDC问题。数据显示AC被选了19次，ABC被选了46次，ABDC被选了86次。问题是要找出这三条路径中有多少是人们真正走过的路径。当然，在地图上根据道路网络手动计算更容易，但问题是基于手头的数据对所有点进行算法计算，而不是绘制。

这里是数据的一个例子。我们将数据分成代表真实汽车行程的组。因此，同一辆车牌在不同的摄像头上被拍摄到的时间足够接近（当然是在同一天内）。这是一个组的示例（与上面的图片无关），类似于这样的组约有1000万个。

index     camera_ID   encoded_plate     date      time_seconds   velocity
9200     480301111       660.0       2021-03-11       62000.0          54
9201     480321111       660.0       2021-03-11       62135.0          28
9202     480331111       660.0       2021-03-11       62235.0           5
9203     480341112       660.0       2021-03-11       62302.0          42
9204     450371112       660.0       2021-03-11       62648.0          32

- Tanishq Kumar

---

我有一个问题，这与SO的主题有什么关系？你在这里提出了一堆问题和要求，但似乎没有尝试自己解决它。 - Mad Physicist

有一个明确定义的问题：AB vs ABC。我有一整段话解释了我如何尝试自己解决它（一种方法是......这是我是如何解决的...）。 - Tanishq Kumar

解决这个问题可能是一个不错的博士研究课题。 - Bob

Answer 1

这里有一种可能的方法：按摄像头点数降序排序记录的旅程类型（例如ABCD有四个点，则应在EFG之前出现，后者只有三个点）。然后对于每种旅程类型，估计你期望看到多少个错觉子序列的观察结果，从实际每个子序列的观察结果中减去该数字（例如，如果我们认为有100次ABCD旅行，那么我们会期望ABC、ABD、ACD和BCD的每个序列都有100*p(1-p)^3个虚假观察结果，以及更短的子序列）。

同时要跟踪每个计数的不确定性，它最初是零，但每次从某个旅程类型的计数中减去一个估计值时，将该估计值的方差加到该旅程类型的不确定性上。然后可以使用方差来估计测量应该真正为零的可能性；如果是这样，当你处理到该旅程类型时，请忽略它并转移到下一个旅程类型。

最后，"真实"旅程类型是其中计数为零不太可能基于估计计数和方差的那些。别忘了还要调整"真实"旅程的计数，例如，路径ABCD有(1-p)^4的不正确记录几率，因此你应该将估计计数除以该因子进行补偿。这个调整应该在估计从子序列中扣除多少虚假观察结果之前进行。

- kaya3

---

有趣的问题——你建议如何计算方差？你是说较小子序列的虚假观测数量来自某个二项分布吗？ - Tanishq Kumar

如果有100个ABCD旅程，每个旅程都有概率q = p(1-p)^3被记录为ABD，那么我们可以将真正的ABCD作为伪造ABD的数量视为具有参数100和q的二项分布，因此它将具有平均值100q和方差100q(1-q)。当这100也只是一个估计值时（因为它是通过1/(1-p)^4因子调整的测量值，并且可能还通过减去一些估计的伪造观察值进行了调整），所以如果精度很重要，您可能需要咨询数学家以确保细节正确。 - kaya3

另一个问题是，该算法可能会输出比实际记录的旅程总数略有不同的数字，因为当基于方差估计计数为零时，但其平均值不为零时，该非零平均值将“缺失”于总数中。例如，如果您认为有100个ABCD，也许您期望有10个虚假的ABD，并且您观察到了11个ABD，那么您可能会猜测真正的ABD为0。逻辑上，额外的1应该属于ABCD - 或者ABED或ABFD...所以如果您想要正确地处理它，就需要更多的细节。但这大体上是我会使用的方法。 - kaya3

我认为你不能太相信概率（在独立性方面）。摄像头在高峰期可能会漏拍更多的情况（当车挨着车或每秒钟经过太多车辆时很难看清），这也是人们可能改变路线的时间。 - Hans Olsson

@HansOlsson 是的，这是一个公平的观点，但我认为它比你想象的要少关注一些——独立性假设并不需要从每次旅程的概率q中获得n个旅程的nq估计值；这只是期望线性性的结果。独立性用于推导nq(1-q)的方差，但方差仅用于估计是否应将调整后的计数视为零。依赖性会改变方差，但它与使用例如95%置信区间而不是99%的效果基本相同，而且这是任意的。 - kaya3