python - 以最快的方式处理大数据集的豪斯多夫距离

Question

我的数据集中的行数超过 500000。我需要每个 id 与其他 id 之间的豪斯多夫距离。并对整个数据集重复此操作

我有一个巨大的数据集。这是一小部分:

df = 

id_easy ordinal latitude    longitude            epoch  day_of_week
0   aaa     1.0  22.0701       2.6685   01-01-11 07:45       Friday
1   aaa     2.0  22.0716       2.6695   01-01-11 07:45       Friday
2   aaa     3.0  22.0722       2.6696   01-01-11 07:46       Friday
3   bbb     1.0  22.1166       2.6898   01-01-11 07:58       Friday
4   bbb     2.0  22.1162       2.6951   01-01-11 07:59       Friday
5   ccc     1.0  22.1166       2.6898   01-01-11 07:58       Friday
6   ccc     2.0  22.1162       2.6951   01-01-11 07:59       Friday

我要计算Haudorff Distance :

import pandas as pd
import numpy as np

from scipy.spatial.distance import directed_hausdorff
from scipy.spatial.distance import pdist, squareform

u = np.array([(2.6685,22.0701),(2.6695,22.0716),(2.6696,22.0722)]) # coordinates of `id_easy` of taxi `aaa`
v = np.array([(2.6898,22.1166),(2.6951,22.1162)]) # coordinates of `id_easy` of taxi `bbb`
directed_hausdorff(u, v)[0]

输出为0.05114626086039758

<小时/>

现在我想计算整个数据集的这个距离。对于所有id_easy。所需的输出是对角线上有 0 的矩阵(因为 aaa 和 aaa 之间的距离是 0):

     aaa      bbb    ccc
aaa    0  0.05114   ...
bbb    ...   0
ccc             0

Answer 1

您正在谈论计算 500000^2+ 距离。如果每秒计算 1000 个这样的距离，则需要 7.93 年才能完成矩阵。我不确定 Hausdorff distance 是否是对称的，但即使是对称的，也只能节省两倍(3.96 年)。

该矩阵还将占用大约 1 TB 的内存。

我建议仅在需要时才计算此值，或者如果您确实需要整个矩阵，则需要并行计算。从好的方面来说，这个问题很容易解决。例如，对于四个核心，您可以这样分割问题(​​用伪代码):

n = len(u)
m = len(v)
A = hausdorff_distance_matrix(u[:n], v[:m])
B = hausdorff_distance_matrix(u[:n], v[m:])
C = hausdorff_distance_matrix(u[n:], v[:m])
D = hausdorff_distance_matrix(u[n:], v[m:])
results = [[A, B],
           [C, D]]

其中 hausdorff_distance_matrix(u, v) 返回 u 和 v 之间的所有距离组合。不过，您可能需要将其分成四个以上的部分。

什么是应用程序？您可以只根据需要分段计算这些吗？