使用Python和Dask的欧式距离计算

Question

我正在尝试确定欧氏距离矩阵中属于某个阈值的元素。然后，我将位置搜索参数用于此搜索，并使用它们比较第二个数组中的元素（为演示起见，该数组是PCA的第一个特征向量，但排序是与我的问题最相关的部分）。该应用程序需要适用于未知数量的观测值，但应能有效运行几百万个。

＃

import numpy as np
from scipy.spatial.distance import cdist

threshold = 10
data = np.random.uniform((1, 2, 3), 5000)

searchValues = np.where(cdist(data, data) < threshold)

＃

我的问题有两个。

首先，对于简单地应用scipy.spatial.distance.cdist（），欧几里得距离矩阵很快变得太大。为了解决此问题，我将cdist函数分批应用于数据集并迭代实现搜索。

＃

cdist(data, data) 

Traceback (most recent call last):
  File "C:\Users\tl928yx\AppData\Local\Continuum\anaconda3\lib\site-packages\IPython\core\interactiveshell.py", line 2862, in run_code
    exec(code_obj, self.user_global_ns, self.user_ns)
  File "<ipython-input-10-fb93ae543712>", line 1, in <module>
    cdist(data, data)
  File "C:\Users\tl928yx\AppData\Local\Continuum\anaconda3\lib\site-packages\scipy\spatial\distance.py", line 2142, in cdist
    dm = np.zeros((mA, mB), dtype=np.double)
MemoryError

＃

第二个问题是运行时问题，它是由迭代构造距离矩阵导致的。当我建立迭代方法时，运行时间呈指数增长。由于迭代方法的性质，这并不意外。

＃

import numpy as np
import dask.array as da
from scipy.spatial.distance import cdist
import itertools
import timeit

threshold = 10
data = np.random.uniform(1, 100, (200000,40))  #Build random data
data = da.asarray(data)

it = round(data.shape[0]/10000)
dataArrays = [data[i*10000:(i+1)*10000] for i in range(0, it)]

comparisons = itertools.combinations(dataArrays, 2)

start = timeit.default_timer()
searchvalues = []
for comparison in comparisons:
    searchvalues.append(np.where(cdist(comparison[0], comparison[1]) < threshold))
time = timeit.default_timer() - start
print(time)

＃

由于问题的性质，这些问题都不是无法预料的。为了尝试解决这两个问题，我尝试使用dask在python中实现大型数据框架，并在批处理过程中插入并行化。但是，这并没有导致时间计算上的显着改善，并且我在使用这种迭代方法时有一个非常严格的内存限制（要求一次批量获取1000 obs。

from dask.diagnostics import ProgressBar
import dask.delayed
import dask.bag

@dask.delayed
def eucDist(comparison):
    return da.asarray(cdist(comparison[0], comparison[1]))

@dask.delayed
def findValues(euclideanMatrix):
    return np.where(euclideanMatrix < threshold)

start = timeit.default_timer()
searchvalues = []
test = []
for comparison in comparisons:
    comp = dask.delayed(eucDist)(comparison)
    test.append(comp)

look = []

with ProgressBar():
    for element in test:
        look.append(dask.delayed(findValues)(element).compute())

我希望可以并行化比较以提高速度，但是我不确定如何在python中实现它。对此的任何帮助，或有关如何改进初始比较代码的任何建议，将不胜感激。

Answer 1

我相信dask-image包中有一些启用dask的距离算法。

Answer 2

您可以通过使用dask_distance.euclidean(x,y)计算Dask中的欧式距离。