距离

在基于记忆的学习中，确定邻域是算法的第一步。邻域的确定需要借助距离函数。常用的距离有多种形式，比如曼哈顿街区距离、欧氏距离、闵可夫斯基距离(Minkovski)、切比雪夫距离、以及马氏(Mahalanobis)距离等。

a) 常见距离

1. 闵可夫斯基距离(Minkovski)

$x=(x_1,x_2,\ldots,x_m),y=(y_1,y_2,\ldots,y_m)$ 那么，闵可夫斯基距离定义为： $(\sum_{i=1}^m|x_i-y_i|^p)^{1/p}$ 该距离最常用的 $p$ 是 2 和 1,前者是欧几里得距离，后者是曼哈顿距离。

欧氏距离

定义：欧氏距离（ Euclidean distance）是一个通常采用的距离定义，它是在m维空间中两个点之间的真实距离。

在二维和三维空间中的欧式距离的就是两点之间的距离，二维的公式是

$d = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

三维的公式是

$d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$

推广到$n$维空间，欧式距离的公式是

$d=\sqrt{ \sum(x_{i1}-x_{i2})^2 }$

这里i=1,2..n , $x{i1}$表示第一个点的第$i$维坐标,$x{i2}$表示第二个点的第$i$维坐标. $n$维欧氏空间是一个点集,它的每个点可以表示为$(x_1,x_2,\ldots ,x_n)$,其中 $x_i,(i=1,2\ldots,n)$ 是实数,称为$x$的第$i$个坐标,两个点$x$和$y=(y_1,y_2,\ldots ,y_n)$之间的距离$d(x,y)$定义为上面的公式.

欧氏距离看作信号的相似程度。距离越近就越相似，就越容易相互干扰，误码率就越高。

import torch.nn.functional as F
feat = torch.tensor([[-1.,-1.], [1.,1.]])

feat_norm = F.normalize(feat, p=2, dim=1)
B=1
sketch_feat, shape_feat = torch.split(feat_norm, [B, B])


embedding_distance = torch.cdist(sketch_feat, shape_feat, p=2)

2.曼哈顿距离（Manhattan distance）

当$p=1$时：$\sum_{i=1}^m|x_i-y_i|$ 假设在曼哈顿街区乘坐出租车从 P 点到 Q 点，白色表示高楼大厦，灰色表示街道：

绿色的斜线表示欧几里得距离，在现实中是不可能的。其他三条折线表示了曼哈顿距离，这三条折线的长度是相等的。

3.切比雪夫距离（Chebyshev distance）

当 $p$ 趋近于无穷大时，闵可夫斯基距离转化成切比雪夫距离： $(\sum_{i=1}^m|x_i-y_i|^p)^{1/p}= max_{i=1}^m|x_i-y_i|$

b) 平面图像

若$m=2$，当$p$取不同数值时，$d(x,0) = ||x||= 1$的图像：

c) 最“另类”

马氏距离

a)中的三种方法是在数据各个维度不相关的假设下，利用数据分布特性计算距离。如果维度相互之间数据相关（例如：身高较高的信息很有可能会带来体重较重的信息，因为两者是有关联的），这时候就要用到马氏距离（Mahalanobis distance）。

马氏距离实际上是利用 Cholesky transformation 来消除不同维度之间的相关性和尺度不同的性质。比如下图中，椭圆表示等高线，从欧几里得的距离来算，绿黑距离大于红黑距离，但是从马氏距离，结果恰好相反：

Distance

距离