Я пытаюсь определить элементы в евклидовой матрице расстояний, которые попадают под определенный порог. Затем я беру позиционные аргументы для этого поиска и использую их для сравнения элементов во втором массиве (для демонстрации этот массив является первым собственным вектором 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, так и для вставки распараллеливания в пакетный процесс. Тем не менее, это не привело к значительному улучшению расчета времени, и у меня есть довольно строгое ограничение памяти с помощью этого итеративного метода в режиме dask (требующего принимать по 1000 штук за раз.
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. Буду признателен за любую помощь в этом, или любые рекомендации по улучшению исходного кода сравнения.