Сумма разности квадратов между каждой комбинацией строк матрицы 17000 на 300

Итак, у меня есть матрица с 17000 строк (примеры) и 300 столбцов (функции). Я хочу вычислить в основном евклидово расстояние между каждой возможной комбинацией строк, то есть сумму квадратов разностей для каждой возможной пары строк. Очевидно, что это много, и iPython, хотя и не полностью разбивает мой ноутбук, говорит" (занято) " на некоторое время, а затем я больше не могу ничего запускать, и он определенно сдается, хотя я могу перемещать мышь и все остальное.

Есть ли есть ли способ заставить это работать? Вот функция, которую я написал. Я использовал numpy везде, где только мог. То, что я делаю, - это сохраняю различия в матрице различий для каждой возможной комбинации. Я знаю, что нижняя диагональная часть Матрицы = верхняя диагональ, но это сэкономит только 1/2 вычислительного времени (лучше, чем ничего, но не изменит игру, я думаю).

EDIT : я только что попробовал использовать scipy.spatial.distance.pdist, но он работает уже добрую минуту, и конца ему не видно. лучший способ? Я должен также упомянуть, что у меня есть НАН-ценности там...но это, по-видимому, не проблема для numpy.

features = np.array(dataframe)
distances = np.zeros((17000, 17000))


def sum_diff():
    for i in range(17000):
        for j in range(17000):
            diff = np.array(features[i] - features[j])
            diff = np.square(diff)
            sumsquares = np.sum(diff)
            distances[i][j] = sumsquares
3 3
python numpy optimization matrix

3 ответа:

Вы всегда можете разделить время вычисления на 2, заметив, что d(i, i) = 0 и d(i, j) = d (j, i).

Но вы смотрели на sklearn.metrics.pairwise.pairwise_distances() (в v 0.18, смотрите здесь doc )?

Вы бы использовали его как: 

from sklearn.metrics import pairwise
import numpy as np

a = np.array([[0, 0, 0], [1, 1, 1], [3, 3, 3]])
pairwise.pairwise_distances(a)
2

Главное в numpy-это не использовать циклы и позволить ему творить чудеса с векторизованными операциями, поэтому есть несколько основных улучшений, которые сэкономят вам некоторое время вычислений: 

import numpy as np
import timeit

#I reduced the problem size to 1000*300 to keep the timing in reasonable range
n=1000
features = np.random.rand(n,300)
distances = np.zeros((n,n))


def sum_diff():
    for i in range(n):
        for j in range(n):
            diff = np.array(features[i] - features[j])
            diff = np.square(diff)
            sumsquares = np.sum(diff)
            distances[i][j] = sumsquares

#Here I removed the unnecessary copy induced by calling np.array
# -> some improvement
def sum_diff_v0():
    for i in range(n):
        for j in range(n):
            diff = features[i] - features[j]
            diff = np.square(diff)
            sumsquares = np.sum(diff)
            distances[i][j] = sumsquares

#Collapsing of the statements -> no improvement
def sum_diff_v1():
    for i in range(n):
        for j in range(n):
            distances[i][j] = np.sum(np.square(features[i] - features[j]))

# Using brodcasting and vetorized operations -> big improvement
def sum_diff_v2():
    for i in range(n):
        distances[i] = np.sum(np.square(features[i] - features),axis=1)

# Computing only half the distance -> 1/2 computation time
def sum_diff_v3():
    for i in range(n):
        distances[i][i+1:] = np.sum(np.square(features[i] - features[i+1:]),axis=1)
    distances[:] = distances + distances.T

print("original :",timeit.timeit(sum_diff, number=10))
print("v0 :",timeit.timeit(sum_diff_v0, number=10))
print("v1 :",timeit.timeit(sum_diff_v1, number=10))
print("v2 :",timeit.timeit(sum_diff_v2, number=10))
print("v3 :",timeit.timeit(sum_diff_v3, number=10))

Edit: для полноты я также приурочил решение Камиллери, которое намного быстрее : 

from sklearn.metrics import pairwise

def Camilleri_solution():
    distances=pairwise.pairwise_distances(features)

Результаты синхронизации (в секундах, функция выполняется 10 раз с входом 1000*300): 

original : 138.36921879299916
v0 : 111.39915344800102
v1 : 117.7582511530054
v2 : 23.702392491002684
v3 : 9.712442981006461
Camilleri's : 0.6131987979897531
Таким образом, как вы можете видеть, мы можем легко получить порядок величины, используя правильный синтаксис numpy. Обратите внимание, что при использовании только 1/20 части данных функция выполняется примерно за одну секунду, поэтому я ожидал бы, что все это будет выполняться за десятки минут, как scipt работает в N^2.
1

Забудьте о numpy, который является только удобным решением для саморасширяющихся массивов. Вместо этого используйте списки python, которые имеют очень быстрый доступ к индексации и примерно в 15 раз быстрее. Используйте его следующим образом: 

features = list(dataframe)
distances = [[None]*17000]*17000

def sum_diff():
    for i in range(17000):
        for j in range(17000):
            for k in range(300):
                diff = features[i][k] - features[j][k]
                diff = diff*diff
                sumsquares = sumsquares + diff
                distances[i][j] = sumsquares

Я надеюсь, что это быстрее, чем ваше решение, просто попробуйте его и дайте обратную связь, пожалуйста.

-3