Изчисляването на евклидови разстояния с Python работи твърде бавно

Чета набори от данни от файл в numpy масиви като този:

def read_data(filename):
   data = np.empty(shape=[0, 65], dtype=int)
   with open(filename) as f:
       for line in f:
           data = np.vstack((data, np.array(list(map(int, line.split(','))), dtype=int)))
   return data

Използвам numpy за изчисляване на евклидовото разстояние между два списъка:

def euclidean_distance(x, z):
   return np.linalg.norm(x-z)

След това изчислявам евклидовите разстояния по следния начин:

for data in testing_data:
   for data2 in training_data:
       dist = euclidean_distance(data, data2)

Проблемът ми е, че този код работи много бавно, отнема около ~10 минути, за да завърши. Как мога да подобря това, какво пропускам?
Трябва да използвам разстоянията в друг алгоритъм, така че скоростта е много важна.


person Fogarasi Norbert    schedule 06.05.2019    source източник
comment
Използвайте cdist - docs.scipy.org/doc /scipy/reference/generated/?   -  person Divakar    schedule 06.05.2019
comment
Разбира се, сложността тук е O(N*M), където N и M са размера на testing_data & training_data респ. Така че зависи колко големи са и двата набора от данни..   -  person kmario23    schedule 06.05.2019
comment
Наборът от данни за тестване се състои от 3823, а наборът от данни за обучение 1797 данни. Така че това означава, че трябва да се изчислят 6 869 931 разстояния, което не мисля, че е толкова много, че трябва да отнеме 10 минути.   -  person Fogarasi Norbert    schedule 06.05.2019
comment
@FogarasiNorbert Съгласен съм, това не е много! Една оптимизация може да бъде да се отървем от ръчното създаване на list и просто да използваме np.fromiter(map(int, line.split(','))), въпреки че мисля, че може да не даде толкова подобрение. Друго нещо може да е да се отървете от функцията euclidean_distance() и да вградите кода директно, тъй като е само един ред. Може да даде малък тласък, тъй като избягваме 6,8 милиона извиквания на функции   -  person kmario23    schedule 06.05.2019
comment
@Divakar Използвах cdist, както и ръчно внедряване с помощта на numpy.linalg.norm и не наблюдавах голяма разлика по отношение на скоростта.   -  person kmario23    schedule 06.05.2019
comment
Нещо странно нещо се случва тук. Опитах cdist и работи за 2 секунди и ако подобря кода си, както казахте @kmario23, отнема същото време като преди. Не искам да използвам cdist, защото това създава матрица. Как е възможно?   -  person Fogarasi Norbert    schedule 06.05.2019
comment
По какъв начин искате да получите изхода, ако не 2d numpy масив?   -  person max9111    schedule 07.05.2019
comment
Това изчисляване на разстоянието е част от алгоритъм, начинът, по който искам да използвам, е да дам два списъка с дължина 64 като параметри за моята функция euclidean_distance.   -  person Fogarasi Norbert    schedule 07.05.2019


Отговори (1)


Можете да използвате sklearn.metrics.pairwise_distances, което ви позволява да разпределите работят с всичките ви ядра. Паралелното конструиране на матрица на разстоянието обсъжда същата тема и предоставя добра дискусия за разликите между pdist, cdist и pairwise_distances

Ако разбирам правилно вашия пример, вие искате разстоянието между всяка проба в набора за обучение и всяка проба в набора за тестване. За да направите това, можете да използвате:

dist = pairwise_distances(training_data, testing_data, n_jobs=-1)
person Grr    schedule 06.05.2019