如何更有效地存储距离矩阵？

问题描述 投票：1回答：2

我有这个python代码来计算不同点之间的坐标距离。

IDs,X,Y,Z
0-20,193.722,175.733,0.0998975
0-21,192.895,176.727,0.0998975
7-22,187.065,178.285,0.0998975
0-23,192.296,178.648,0.0998975
7-24,189.421,179.012,0.0998975
8-25,179.755,179.347,0.0998975
8-26,180.436,179.288,0.0998975
7-27,186.453,179.2,0.0998975
8-28,178.899,180.92,0.0998975

这段代码可以完美的运行，但是由于我现在的坐标量非常大（~50000），我需要优化这段代码，否则无法运行。谁能给我推荐一个更节省内存的方法？谢谢大家的建议。

#!/usr/bin/env python
import pandas as pd
import scipy.spatial as spsp

df_1 =pd.read_csv('Spots.csv', sep=',')
coords = df_1[['X', 'Y', 'Z']].to_numpy()
distances = spsp.distance_matrix(coords, coords)
df_1['dist'] = distances.tolist()

# CREATES columns d0, d1, d2, d3
dist_cols = df_1['IDs']
df_1[dist_cols] = df_1['dist'].apply(pd.Series)

df_1.to_csv("results_Spots.csv")
python pandas numpy scipy numpy-ndarray
2个回答
1
投票

你在代码中要求的是一个约50000×约50000矩阵中的点到点的距离。如果你真的喜欢存储它，结果会非常大。矩阵是密集的，因为每个点都有一个正的距离到另一个点.我建议重新审视你的业务需求。你真的需要预先计算所有这些点，并将它们存储在磁盘上的文件中吗？有时，最好是在飞行中进行所需的计算；scipy.spacial速度很快，甚至可能不会比读取一个预先计算的值慢多少。

EDIT (根据评论):你可以通过一个阈值过滤计算出的距离 (这里用于说明：5.0)，然后在 DataFrame 中查找 IDs

import pandas as pd
import scipy.spatial as spsp

df_1 =pd.read_csv('Spots.csv', sep=',')
coords = df_1[['X', 'Y', 'Z']].to_numpy()
distances = spsp.distance_matrix(coords, coords)

adj_5 = np.argwhere(distances[:] < 5.0)
pd.DataFrame(zip(df_1['IDs'][adj_5[:,0]].values,
                 df_1['IDs'][adj_5[:,1]].values),
             columns=['from', 'to'])
3
投票

有几种方法可以节省空间。第一种是只存储矩阵的上三角，并确保你的指数总是反映出这一点。第二种是只存储符合你的阈值的值。这可以通过使用稀疏矩阵来集体完成，稀疏矩阵支持你可能需要的大部分操作，并且只存储你需要的元素。

为了存储一半的数据，当你访问你的矩阵时，对你的指数进行预处理。所以对于你的矩阵，访问索引 [i, j] 像这样。

getitem(A, i, j):
    if i > j:
        i, j = j, i
    return dist[i, j]

scipy.sparse 支持多种稀疏矩阵格式。BSR, 协调, 企业社会责任, CSC, 对角线, DOK, LIL. 根据《公约》的规定。用法参考构建矩阵的最简单方法是使用DOK或LIL格式。为了简单起见，我将展示后者，尽管前者可能更有效。一旦展示了一个基本的功能方法，我将把它留给读者来衡量不同的选择。在做矩阵数学时，记得要转换为CSR或CSC格式。

我们将牺牲速度来换取空间效率，一次只构造一行。

N = coords.shape[0]
threshold = 2

threshold2 = threshold**2  # minor optimization to save on some square roots
distances = scipy.sparse.lil_matrix((N, N))
for i in range(N):
    # Compute square distances
    d2 = np.sum(np.square((coords[i + 1:, :] - coords[i])), axis=1)
    # Threshold
    mask = np.flatnonzero(d2 <= threshold2)
    # Apply, only compute square root if necessary
    distances[i, mask + i + 1] = np.sqrt(d2[mask])

对于你的玩具例子，我们发现只有四个元素真正通过了阈值，使得存储效率非常高。

>>> distances.nnz
4
>>> distances.toarray()
array([[0.        , 1.29304486, 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        ],
       [0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        ],
       [0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 1.1008038 , 0.        ],
       [0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        ],
       [0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        ],
       [0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.68355102, 0.        , 1.79082802],
       [0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        ],
       [0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        ],
       [0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        , 0.        ]])

利用这个结果 scipy.spatial.distance_matrix 证实了这些数字事实上是准确的。

如果你想填充矩阵（有效地将存储量增加一倍，这应该不是令人望而却步的），你可能应该在这样做之前远离LIL格式。只需在原始矩阵中加入转置就可以将其填满。

这里显示的方法解决了你的存储问题，但你可以使用空间排序和其他地理空间技术来提高整个计算的效率。例如，您可以使用 "空间排序 "和其他地理空间技术来提高整个计算的效率。scipy.spatial.KDTree 或类似 scipy.spatial.cKDTree 来直接有效地安排你的数据集和查询邻居在一个特定的阈值内。

例如，下面将用一种可能更有效的方法来替换这里显示的矩阵结构。

tree = scipy.spatial.KDTree(coords)
distances = tree.sparse_distance_matrix(tree, threshold)
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.