生成稀疏成对距离矩阵 python 避免内存错误

Question

我有一些地理空间数据，我正在尝试生成点之间的成对半正弦距离。不幸的是，大约有 50k 个数据点，这将产生一个 50000x50000 的距离矩阵。由于这个距离矩阵是对称的，我在想这个矩阵可能是稀疏的。我希望能够直接从距离计算中生成一个稀疏矩阵，这样我就不会出现内存错误。到目前为止，这是我的代码：

def convert_to_arrays(df1, df2):
    d1 = np.array(df1[['x','y']].values.tolist())
    d2 = np.array(df2[['x','y']].values.tolist())
    return d1,d2

def haversine(data1, data2):
    data1 = np.deg2rad(data1)                     
    data2 = np.deg2rad(data2)                     

    lat1 = data1[:,0]                     
    lng1 = data1[:,1]         

    lat2 = data2[:,0]                     
    lng2 = data2[:,1]         

    diff_lat = lat1[:,None] - lat2
    diff_lng = lng1[:,None] - lng2
    d = np.sin(diff_lat/2)**2 + np.cos(lat1[:,None])*np.cos(lat2) * np.sin(diff_lng/2)**2
    return 2 * 6371 * np.arcsin(np.sqrt(d))

dist = haversine(*convert_to_arrays(df, df))

其中 df 是一个包含 'x' 和 'y' 列的 pandas 数据框。当我运行这段代码有大约 50k 点时，我得到一个内存错误：

MemoryError: Unable to allocate 19.3 GiB for an array with shape (50893, 50893) and data type float64

有没有办法确保使用（下三角或上三角）稀疏矩阵作为预期输出执行计算？

Answer 1

我发现实现这一点的方法相当蛮力；如果您有更优雅的解决方案，请 post 吧。本质上，我以块的形式从第一个数据帧中提取点，并计算与第二个数据帧中所有点的成对距离，从而生成一个 Nx50893 数组。然后我将这个数组转换为稀疏下三角矩阵。最后，我计算下一个块，转换为下三角并将这些数组堆叠起来。

def haversine(data1, data2):
    data1 = np.deg2rad(data1)                     
    data2 = np.deg2rad(data2)                     

    lat1 = data1[:,0]                     
    lng1 = data1[:,1]         

    lat2 = data2[:,0]                     
    lng2 = data2[:,1]         

    #chunk it out 
    N = 2000 #chunk size
    start = 0
    end = N
    #First iteration
    diff_lat = lat1[:N,None] - lat2
    diff_lng = lng1[start:end,None] - lng2()
    d = np.sin(diff_lat/2)**2 + np.cos(lat1[start:end,None])*np.cos(lat2) * np.sin(diff_lng/2)**2
    D = scipy.sparse.tril((2 * 6378137 * np.arcsin(np.sqrt(d))).astype(np.float32))
    start = end
    end += N
    L = len(lat1) - end
    #A bunch more iterations
    while L>0:
        diff_lat = lat1[start:end,None] - lat2
        diff_lng = lng1[start:end,None] - lng2
        d = np.sin(diff_lat/2)**2 + np.cos(lat1[start:end,None])*np.cos(lat2) * np.sin(diff_lng/2)**2
        d = scipy.sparse.tril((2 * 6378137 * np.arcsin(np.sqrt(d))).astype(np.float32))
        D = scipy.sparse.vstack([D,d])
        start = end
        end += N
        L = len(lat1) - end
    #Last iteration    
    diff_lat = lat1[start:,None] - lat2
    diff_lng = lng1[start:,None] - lng2
    d = np.sin(diff_lat/2)**2 + np.cos(lat1[start:,None])*np.cos(lat2) * np.sin(diff_lng/2)**2
    d = scipy.sparse.tril((2 * 6378137 * np.arcsin(np.sqrt(d))).astype(np.float32))
    D = scipy.sparse.vstack([D,d])
        
    return D

dist = haversine(*convert_to_arrays(df, df)

生成稀疏成对距离矩阵 python 避免内存错误

Produce sparse pairwise distance matrix python avoiding memory error

python

scipy

sparse-matrix

distance-matrix