Вычисление евклидовых расстояний с помощью 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 минут. Как я могу улучшить это, что я упускаю?
Мне нужно использовать расстояния в другом алгоритме, поэтому скорость очень важна.


python numpy performance euclidean-distance linear-algebra
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)


arrow_upward
2
arrow_downward

Вы можете использовать sklearn.metrics.pairwise_distances, который позволяет распределять работать на все ваши ядра. Параллельное построение матрицы расстояний обсуждает ту же тему и предоставляет хорошее обсуждение различий pdist, cdist и pairwise_distances

Если я правильно понимаю ваш пример, вам нужно расстояние между каждым образцом в обучающем наборе и каждым образцом в тестовом наборе. Для этого вы можете использовать:

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