Как найти евклидово растояние двух матриц?
Есть numpy array X, размерностью (num_test, D), где D - матрица некоторого размера. Есть numpy array X_train, размерностью (num_train, D).
Нужно найти Евклидово расстояние между каждой матрицей в X и между каждой матрицей в X_train. Не используя циклов и используя только базовые операции над матрицами. Нельзя использовать библиотеку scipy и np.linalg.norm().
То есть, нужно заполнить numpy array размерностью (num_test, num_train), где каждая запись это расстояние между i-той матрией из X и j-ой матрицей из X_train.
До этого нужно было написать тоже самое, но используя два цикла:
def compute_distances_two_loops(self, X):
"""
Compute the distance between each test point in X and each training point
in self.X_train using a nested loop over both the training data and the
test data.
Inputs:
- X: A numpy array of shape (num_test, D) containing test data.
Returns:
- dists: A numpy array of shape (num_test, num_train) where dists[i, j]
is the Euclidean distance between the ith test point and the jth training
point.
"""
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
for i in range(num_test):
for j in range(num_train):
#####################################################################
# TODO: #
# Compute the l2 distance between the ith test point and the jth #
# training point, and store the result in dists[i, j]. You should #
# not use a loop over dimension, nor use np.linalg.norm(). #
#####################################################################
# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
dists[i, j] = np.sqrt(np.sum((X[i] - self.X_train[j])**2))
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
return dists
И один цикл:
def compute_distances_one_loop(self, X):
"""
Compute the distance between each test point in X and each training point
in self.X_train using a single loop over the test data.
Input / Output: Same as compute_distances_two_loops
"""
num_test = X.shape[0]
num_train = self.X_train.shape[0]
dists = np.zeros((num_test, num_train))
for i in range(num_test):
#######################################################################
# TODO: #
# Compute the l2 distance between the ith test point and all training #
# points, and store the result in dists[i, :]. #
# Do not use np.linalg.norm(). #
#######################################################################
# *****START OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
dists[i, :] = np.sqrt(np.sum((X[i] - self.X_train)**2, axis=1))
# *****END OF YOUR CODE (DO NOT DELETE/MODIFY THIS LINE)*****
return dists
Как сделать тоже самое но не используя циклов, у меня дойти не получается.
Если что это домашка из Стэнфордского курса по компьютерному зрению. Я не пытаюсь сжульничить в настоящей домашке, за которую ставят оценки. Просто пытась понять, как это сделать. Поэтому, будет ещё лучше если вы объясните с точки зрения математики, что вы делаете.
Ответы (1 шт):
Решение, подсмотренное здесь:
def dist_pairwise(a, b):
P = np.add.outer(np.sum(a**2, axis=1), np.sum(b**2, axis=1))
N = np.dot(a, b.T)
return np.sqrt(P - 2*N)
Примеры:
In [196]: a = np.random.randint(10, size=(5, 3))
In [197]: b = np.random.randint(10, size=(4, 3))
In [198]: a
Out[198]:
array([[3, 5, 0],
[2, 6, 2],
[4, 4, 6],
[3, 0, 6],
[4, 7, 6]])
In [199]: b
Out[199]:
array([[7, 1, 5],
[7, 9, 2],
[4, 8, 1],
[2, 1, 1]])
In [200]: dists = dist_pairwise(a, b)
In [201]: dists
Out[201]:
array([[ 7.54983444, 6. , 3.31662479, 4.24264069],
[ 7.68114575, 5.83095189, 3. , 5.09901951],
[ 4.35889894, 7.07106781, 6.40312424, 6.164414 ],
[ 4.24264069, 10.63014581, 9.48683298, 5.19615242],
[ 6.78232998, 5.38516481, 5.09901951, 8.06225775]])
In [202]: dists.shape
Out[202]: (5, 4)
Проверка для первой строки:
In [210]: np.linalg.norm(a[0] - b[0])
Out[210]: 7.54983443527075
In [211]: np.linalg.norm(a[0] - b[1])
Out[211]: 6.0
In [212]: np.linalg.norm(a[0] - b[2])
Out[212]: 3.3166247903554
In [213]: np.linalg.norm(a[0] - b[3])
Out[213]: 4.242640687119285
Пояснение формулы:
Чтобы понять как работает это решение можно рассмотреть тривиальный случай расчета расстояния между двумя точками [A(x1, y1) и B(x2, y2)] в двумерном пространстве:
Евклидово расстояние между точками A и B:
dist = sqrt((x2-x1)**2 + (y2-y1)**2)
если раскрыть скобки внутри функции sqrt(...) то получится:
x2**2 - 2*x2*x1 + x1**2 + y2**2 - 2*y2*y1 + y1**2
или, упростив:
(x1**2 + x2**2 + y1**2 + y2**2 - 2*(x1*x2 + y1*y2))