1

我正在尝试计算一个 DTW 距离矩阵，该矩阵将查看 150,000 个时间序列，每个时间序列具有 13 到 24 个观测值 - 也就是说，生成的距离矩阵将是一个大小约为 (150,000 x 150,000)/2= 11,250,000,000 的列表。

我在一个大小为 200GB 的大数据集群上运行它，但出现内存错误。

我正在使用 dtaidisatance 库并使用了distance_matrix_fast函数，我可以在列表中一次传递整个时间序列，但是我遇到了类似的内存错误，但是从包中出来了。但是，一旦我运行它，错误就会立即被抛出。我还使用了包中的块功能，但似乎无法一次将所有时间序列都带入。

所以我决定通过一个循环计算每两对时间序列之间的距离，然后将其附加到一个列表中。但是，在运行了很长时间后，我确实再次遇到了与以下相同的内存错误：

文件“/root/anaconda2/test/final_clustering_2.py”，第 93 行，在 distance_matrix_scaled.append(dtw.distance_fast(Series_scaled[i], Series_scaled[j])) MemoryError

这是我下面的代码：

distance_matrix_scaled = []

m=len(Series_scaled)
#m=100000
for i in range(0, m - 1):
    for j in range(i + 1, m):

distance_matrix_scaled.append(dtw.distance_fast(Series_scaled[i], Series_scaled[j]))

# save it to the disk
np.save('distance_entire',  distance_matrix_scaled)

你能帮忙回答为什么我会收到这个内存错误吗？是python列表限制还是我的集群大小导致了这个？numpy中是否有一种聪明的方法或格式可以用来解决这个问题？

4

2 回答 2

2

如果您正在计算诸如欧几里得距离之类的东西，请查看计算任务的内存成本，您将生成一个中间临时数组，150000*149999/2*(13~24)其中

  • 150000*149999/2表示 150000 个时间序列中无序对的数量（不包括 self-self 对）

  • 表示两个时间序列向量之间的13~24差异，norm稍后将对其进行编辑并减少到每对一个数字。

每个数字通常是 4 或 8 字节的浮点数或双精度数。所以算法会占用1T~4T内存，显然200G会爆炸。

除了手动划分较小的任务外，还有一些技巧可以降低内存成本：

  • 如果你坚持搭配numpy，一定要选小一点dtype的s比如float32。如果你的数字很小，你甚至可以考虑像int16or之类的东西int8。不要使用float16，因为它在 CPU 上没有计算支持（非常慢）。

  • 如果不是这样，你可能会考虑numba，它允许你将 python 循环编译为高效的 CPU 代码并使其运行在所有内核上，这应该是 CPU 上的最佳解决方案（它不需要生成临时数组） .

  • Scipy 也有scipy.spatial.distance.pdict。不完全确定它在内存方面的表现如何，但你可以试一试。

于 2018-10-24T03:22:28.577 回答
2

您的双 for 循环有 4999950000 次迭代。您将多次附加到列表中。还是很奇怪？

如果距离是标量，那么您确实可以通过预先分配一个那么大的数组来节省内存（并希望最好的，内存方面的）：

import numpy as np

m = 100000
distances = np.empty(m*(m-1)/2) # size: 4999950000
k = 0
for i in range(0, m - 1):
    for j in range(i + 1, m):
         distances[k] = dtw.distance_fast(Series_scaled[i], Series_scaled[j])
         k += 1

由于 numpy 数组占用连续的内存块，因此它们在大规模上比原生列表更有效。数组本身的开销几乎可以忽略不计，因此您主要获得实际数据的大小。

如果这个巨大的数组不适合你的记忆，你就有麻烦了。您必须切割数据并以较小的块工作。或者也许使用某种内存映射。

然而，需要注意的是：我们正在填充的数组（假设为 64 位双精度数）占用大约 37 GB 的 RAM。好多啊。如果你能记住它，你将不得不等待一个 python（双）循环的 50亿次迭代。这将需要……很多时间。不要屏住呼吸。

于 2018-10-23T23:00:43.880 回答