矩阵之间无循环计算L2距离
实现两个矩阵的无循环计算欧氏距离 Euclidean distance
1.问题来源
kNN算法中会计算两个矩阵的距离
可以使用循环的方法来实现，效率较低
def compute_distances_one_loop(self, X):
"""
train:5000x3072
test: 500x3072
- 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):
#######################################################################
# TODO: #
# Compute the l2 distance between the ith test point and all training #
# points, and store the result in dists[i, :]. #
#######################################################################
distance=np.sqrt(np.sum(np.square(self.X_train - X[i,:]),axis=1))
dists[i,:]=distance
return dists
2.无循环计算L2 distances
一眼看到这个代码，真的是被深深折服！厉害，值得细细学习搞懂。
def compute_distances_no_loops(self, X):
"""
Compute the distance between each test point in X and each training point
in self.X_train using no explicit loops.
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))
#########################################################################
# TODO: #
# Compute the l2 distance between all test points and all training #
# points without using any explicit loops, and store the result in #
# dists. #
# #
# You should implement this function using only basic array operations; #
# in particular you should not use functions from scipy. #
# #
# HINT: Try to formulate the l2 distance using matrix multiplication #
# and two broadcast sums. #
#########################################################################
M = np.dot(X, self.X_train.T)
nrow=M.shape[0]
ncol=M.shape[1]
te = np.diag(np.dot(X,X.T))
tr = np.diag(np.dot(self.X_train,self.X_train.T))
te= np.reshape(np.repeat(te,ncol),M.shape)
tr = np.reshape(np.repeat(tr, nrow), M.T.shape)
sq=-2 * M +te+tr.T
dists = np.sqrt(sq)
return dists可能一下子有点懵，不着急 我们举个例子一步一步理解
要先知道计算L2的距离公式:
\[L2(x_{i},x_{j})=(\sum_{i=1}^{n} \mid x_{i}^{(l)} - x_{j}^{(l)} \mid ^{2})^{\frac{1}{2}}\]
计算L2距离需要得到 两点距离差的平方和的开方
再熟悉一个基本公式
\[(a-b)^{2}= a^{2}- 2ab+b^{2} \]
# 假设 x：4x3 ,y: 2x3
# 最后输出一个 2x4矩阵
import numpy as np
>>> x=np.array([[1,2,3],[3,4,5],[5,6,7],[7,8,9]])
>>> x
array([[1, 2, 3],
[3, 4, 5],
[5, 6, 7],
[7, 8, 9]])
>>> y=np.array([[2,3,4],[1,2,3]])
>>> y
array([[2, 3, 4],
[1, 2, 3]])
# 计算两个矩阵的乘积
>>> M=np.dot(y,x.T)
>>> M
array([[20, 38, 56, 74],
[14, 26, 38, 50]])
# 保存乘积矩阵的行列
>>> nrow=M.shape[0]
>>> ncol=M.shape[1]
>>> nrow
2
>>> ncol
4先计算，提取出对角元素
>>> te=np.diag(np.dot(y,y.T))
>>> tr=np.diag(np.dot(x,x.T))
>>> te
array([29, 14])
>>> tr
array([ 14, 50, 110, 194])按对角元素来进行扩充，满足矩阵计算要求
得到\(a^{2}\),\(b^{2}\)
# 继续整理
>>> te=np.reshape(np.repeat(te,ncol),M.shape) # ncol:4 ,M: 2x4
>>> tr=np.reshape(np.repeat(tr,nrow),M.T.shape) #nrow:2 ,M.T:4x2
>>> te
array([[29, 29, 29, 29],
[14, 14, 14, 14]])
>>> tr
array([[ 14, 14],
[ 50, 50],
[110, 110],
[194, 194]])\(-2ab\)就是-2*M
计算距离的开方
>>> sq=-2*M+te+tr.T
>>> dists=np.sqrt(sq)
>>> sq
array([[ 3, 3, 27, 75],
[ 0, 12, 48, 108]])
>>> dists
array([[ 1.73205081, 1.73205081, 5.19615242, 8.66025404],
[ 0. , 3.46410162, 6.92820323, 10.39230485]])
