l2 距离无循环计算方法
[toc]
描述
对于一个向量 X[x0, x1, ... xn] 和向量 Y[y0, y1, ... yn]。其 L2 距离表示为
\[
d = \sqrt{\sum_{i=0}(xi - yi)^2}
\]
一维向量 x 一维向量
两个一维向量计算 l2 距离
x,y
x.shape
(4, )
y.shape
(4,)
d = np.sqrt(np.sum(np.square(x-y)))
逐步解释
x-y: 逐元素相减，大小为 (4, )np.square: 逐元素平方，操作结果为(4, )np.sum: 聚合操作，所有元素求和，操作结果为 一个值np.sqrt：逐元素操作，对元素进行开方，结果为一个值
如果两个向量，一个一维向量和一个多维向量，进行 l2 据
一维向量 x 多维度向量
一个一维向量和一个多维向量计算 l2 距离
假设x(n, ) y (2, n) ，需要将 x 分别和 y 中的每一行做 l2 距离计算，所得的结果应该是 (2, )
为了将 x 和 y 每一行都做 l2 距离计算，需要将 x 进行复制， x(n, ) -> x(2, n)\ 这样只需要将 x - y 得到的每一行都是 x 与 yi 操作的结果，然后统一别对每行进行聚合运算即可，在扩展 x 之后，后续的操作和一维向量相同。
x.shape
(4, )
y.shape
(2, 4)
d = np.sqrt(np.sum(np.square(x-y), axis=1))
axis=1: 对聚合操作来说，axis 为多少，表示在该维度上进行运算，压缩该维度
多维向量 x 多维向量
多维向量与多维向量的 l2 距离结果应该是一个二维矩阵 d[x,y]。 d[xi,yi] 表示 x 中的第 i 行与 y 中第 i 行的距离
方法一
假设 x[m, p], y[n, p]，可以进行升维度，变为 x[m,n,p], y[m,n,p]，维度相同之后，就可以进行逐元素减法，x - y，然后沿着最后一个维度聚合，得到 d[m, n]
x = x.reshape(x.shape[0], 1, x.shape[1])
y = y.reshape(1, y.shape[0], y.shape[1])
d = np.sqrt(np.sum(np.square(x-y), axis=2))
方法二
根据计算公式 $$ d = \sqrt{\sum_{i=0}^n(x_i - y_i)^2} $$
\[
d = \sqrt{\sum_{i=0}^nx_i^2 + \sum_{i=0}^ny_i^2 - 2\sum_{i=0}^{n}x_iy_i}
\]
即对于2个多维矩阵x[m,p] y[n,p]，可以分三个部分分别计算，首先分别计算这两个矩阵的平方和
x_square_sum = np.sum(np.square(x), axis=1)
y_square_sum = np.sum(np.square(y), axis=1)
x_square_sum.shape
(m, )
y_square_sum.shape
(n, )
然后将这两个矩阵进行升维，后求和计算
x_square_sum = x_square_sum[:, np.newaxis]
(m, 1)
y_square_sum = y_square_sum[np.newaxis, :]
(1, n)
x_y_square_sum = x_square_sum + y_square_sum
(m,n)
其中 x_y_square_sum[i,j] 表示 x 的第 i 个向量与 y 的第 j 个向量的平方加和
式子的第二部分，恰好与矩阵乘法一致
x_y_dot = np.dot(x, y.T)
x_y_dot.shape
(m, n)
此时就得到了两个大小均为 （m,n） 的矩阵，将两个式子组合，最终的距离向量矩阵计算为
x_square_sum = np.sum(np.square(x), axis=1)
y_square_sum = np.sum(np.square(y), axis=1)
x_y_square_sum = x_square_sum.reshap[:, np.newaxis] +
y_square_sum[np.newaxis, 1]
x_y_dot = np.dot(x, y.T)
d = np.sqrt(x_y_square_sum - 2*x_y_dot)