距离度量方法-FlyAI

距离度量方法

深度学习

最后更新 2021-07-19 09:51 阅读 7553

最后更新 2021-07-19 09:51

阅读 7553

深度学习

# 距离度量方法

### 欧氏距离

最常见的两点之间或多点之间的距离表示法，又称之为欧几里得度量，它定义于欧几里得空间中，如点 $x = (x_1,\ldots,x_n)$ 和 $y = (y_1,\ldots,y_n)$ 之间的距离为：

$$
d(x,y)=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+...+(x_n-y_n)^2}=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}
$$

二维平面上两点$a(x_1,y_1)$与$b(x_2,y_2)$间的欧氏距离：
$$
d=\sqrt{\left(x_{1}-x_{2}\right)^{2}+\left(y_{1}-y_{2}\right)^{2}}
$$
三维空间两点$a(x_1,y_1,z_1)$与$b(x_2,y_2,z_2)$间的欧氏距离：
$$
d=\sqrt{\left(x_{1}-x_{2}\right)^{2}+\left(y_{1}-y_{2}\right)^{2}+\left(z_{1}-z_{2}\right)^{2}}
$$
两个n维向量$a(x_{11},x_{12},\ldots,x_{1n})$与 $b(x_{21},x_{22},\ldots,x_{2n})$间的欧氏距离：
$$
d=\sqrt{\sum_{k=1}^{n}\left(x_{1 k}-x_{2 k}\right)^{2}}
$$
也可以用表示成向量运算的形式：

$$
d=\sqrt{(a-b)(a-b)^{T}}
$$

### 曼哈顿距离

定义曼哈顿距离的正式意义为L1-距离或城市区块距离，也就是在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。例如在平面上，坐标$（x_1, y_1）$的点$P_1$与坐标$（x_2, y_2）$的点$P_2$的曼哈顿距离为：$|x_1-x_2|+|y_1-y_2|$，曼哈顿距离依赖座标系统的转度，而非系统在座标轴上的平移或映射。

通俗来讲，想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。而实际驾驶距离就是这个“曼哈顿距离”，此即曼哈顿距离名称的来源， 同时，曼哈顿距离也称为城市街区距离。

二维平面两点$a(x_1,y_1)$与$b(x_2,y_2)$间的曼哈顿距离 :
$$
d=|x_1-x_2|+|y_1-y_2|
$$
两个$n$维向量$a(x_{11},x_{12},\ldots,x_{1n})$与 $b(x_{21},x_{22},\ldots,x_{2n})$间的曼哈顿距离:

$$
d=\sum_{k=1}^{n}\left|x_{1 k}-x_{2 k}\right|
$$

### 切比雪夫距离

若二个向量或二个点$p$和$q$，其座标分别为$p_i$及$q_i$，则两者之间的切比雪夫距离定义如下：
$$
d = max_{x_i}(|x_2-x_1|,|y_1-y_1|)
$$
这也等于以下Lp度量的极值：$\lim_{x\rightarrow\infty}(\sum_{i=1}^n|p_i-q_i|^k)^{\frac{1}{k}}$ ，因此切比雪夫距离也称为L∞度量。

以数学的观点来看，切比雪夫距离是由一致范数（或称为上确界范数）所衍生的度量，也是超凸度量的一种。

在平面几何中，若二点p及q的直角坐标系坐标为$(x_1,y_1)$及$(x_2,y_2)$，则切比雪夫距离为：
$$
D_{\text {Chess}}=\max \left(\left|x_{2}-x_{1}\right|,\left|y_{2}-y_{1}\right|\right)
$$

> 玩过国际象棋的朋友或许知道，国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？。你会发现最少步数总是max( | x2-x1 | , | y2-y1 | ) 步 。有一种类似的一种距离度量方法叫切比雪夫距离。

二维平面两点$a(x_1,y_1)$与$b(x_2,y_2)$间的切比雪夫距离 ：
$$
d = max_{x_i}(|x_2-x_1|,|y_1-y_1|)
$$
两个n维向量$a(x_{11},x_{12},\ldots,x_{1n})$与$b(x_{21},x_{22},\ldots,x_{2n})$间的切比雪夫距离：
$$
d=\max _{i}\left(\left|x_{1 i}-x_{2 i}\right|\right)
$$
这个公式的另一种等价形式是

$$
d=lim_{k\to\infty}(\sum_{i=1}^{n}|x_{1i}-x_{2i}|^k)^{1/k}
$$

### 闵可夫斯基距离

闵氏距离不是一种距离，而是一组距离的定义。两个n维变量$a(x_{11},x_{12},\ldots,x_{1n})$与 $b(x_{21},x_{22},\ldots,x_{2n})$ 间的闵可夫斯基距离定义为： 
$$
d=\sqrt[p]{\sum_{k=1}^{n}|x_{1k}-x_{2k}|^p}
$$
其中p是一个变参数。当p=1时，就是曼哈顿距离当p=2时，就是欧氏距离当p→∞时，就是切比雪夫距离。根据变参数的不同，闵氏距离可以表示一类的距离。

### 标准化欧氏距离

标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，那先将各个分量都“标准化”到均值、方差相等。至于均值和方差标准化到多少，先复习点统计学知识。

假设样本集X的数学期望或均值为m，标准差为s，那么X的“标准化变量”X*表示为：(X-m）/s，而且标准化变量的数学期望为0，方差为1。即，样本集的标准化过程用公式描述就是：
$$
X^*=\frac{X-m}{s}
$$
标准化后的值 =  ( 标准化前的值  － 分量的均值 ) /分量的标准差　　
经过简单的推导就可以得到两个n维向量$a(x_{11},x_{12},\ldots,x_{1n})$与 $b(x_{21},x_{22},\ldots,x_{2n})$ 间的标准化欧氏距离的公式：
$$
d=\sqrt{\sum_{k=1}^{n}(\frac{x_{1k}-x_{2k}}{s_k})^2}
$$

### 马氏距离

有M个样本向量$X_1,\ldots,X_m$，协方差矩阵记为$S$，均值记为向量$\mu$，则其中样本向量$X$到$\mu$的马氏距离表示为：
$$
D(X)=\sqrt{(X-u)^TS^{-1}(X_i-X_j)}
$$
若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了欧氏距离：
$$
D(X_i,X_j)=\sqrt{(X_i-X_j)^T(X_i-X_j)}
$$
若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离。

马氏距离的优缺点：量纲无关，排除变量之间的相关性的干扰。

### 巴氏距离

在统计中，巴氏距离距离测量两个离散或连续概率**分布的相似性**。它与衡量两个统计样品或种群之间的重叠量的巴氏距离系数密切相关。同时，Bhattacharyya系数可以被用来确定两个样本被认为相对接近的，它是用来测量中的类分类的可分离性。对于离散概率分布 p和q在同一域 X，它被定义为：
$$
D_B(p,q)=-lnBC(p,q)
$$
其中：
$$
BC(p,q)=\sum_{x\in_{}X}\sqrt{p(x)q(x)}
$$
是Bhattacharyya系数。

### 汉明距离

两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。

### 夹角余弦

几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。

在二维空间中向量$A(x_1,y_1)$与向量$B(x_2,y_2)$的夹角余弦公式：
$$
cos\theta=\frac{x_1x_2+y_1y_2}{\sqrt{x_1^2+y_1^2}\sqrt{x_2^2+y_2^2}}
$$
两个n维样本点$a(x_{11},x_{12},\ldots,x_{1n})$和$b(x_{21},x_{22},\ldots,x_{2n})$的夹角余弦：
$$
cos\theta=\frac{a*b}{|a||b|}
$$
夹角余弦取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小，夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小值-1。

### 杰卡德相似系数

**两个集合A和B的交集元素在A，B的并集中所占的比例**，称为两个集合的杰卡德相似系数，用符号J(A,B)表示。杰卡德相似系数是**衡量两个集合的相似度**一种指标。
$$
J(A,B)=\frac{|A\cap_{}B|}{|A\cup_{}B|}
$$
与杰卡德相似系数相反的概念是杰卡德距离：
$$
J_{\delta}(A,B)=1-J(A,B)=\frac{|A\cup_{}B|-|A\cap_{}B|}{|A\cup_{}B|}
$$

### 皮尔逊系数

在统计学中，皮尔逊积矩相关系数用于度量两个变量X和Y之间的相关（**线性相关**），其值介于-1与1之间。通常情况下通过以下取值范围判断变量的相关强度：

> 0.8-1.0     极强相关
> 0.6-0.8     强相关
> 0.4-0.6     中等程度相关
> 0.2-0.4     弱相关
> 0.0-0.2     极弱相关或无相关

### 距离小结

简单说来，各种“距离”的应用场景简单概括为，

- 空间：欧氏距离，
- 路径：曼哈顿距离，国际象棋国王：切比雪夫距离，
- 以上三种的统一形式:闵可夫斯基距离，
- 加权：标准化欧氏距离，
- 排除量纲和依存：马氏距离，
- 向量差距：夹角余弦，
- 编码差别：汉明距离，
- 集合近似度：杰卡德类似系数与距离，
- 相关：相关系数与相关距离。

# 常见问题

### 余弦相似度 与 欧式距离的区别与联系

- 区别：

欧式距离和余弦相似度都能度量2个向量之间的相似度，但是欧式距离从2点之间的距离去考量，余弦相似从2个向量之间的夹角去考量。举例如下：

> 假设 2人对三部电影的评分分别是 `A = [3, 3, 3]` 和 `B = [5, 5, 5]`
	>
	> 那么2人的欧式距离是 根号12 = 3.46， A、B的余弦相似度是1（方向完全一致）。

从上例可以发出，2人对三部电影的评价趋势是一致的，但是欧式距离并不能反映出这一点，余弦相似则能够很好地反应。余弦相似可以很好地规避指标刻度的差异，最常见的应用是计算**文本的相似度** 。

- 联系：

**归一化后计算的欧式距离是关于余弦相似的单调函数**，可以认为归一化后，余弦相似与欧式距离效果是一致的（欧式距离越小等价于余弦相似度越大）。

因此可以将 **求余弦相似转为求欧式距离** ，余弦相似的计算复杂度过高，转为求欧式距离后，可以借助`KDTree`（KNN算法用到）或者`BallTree`（对高维向量友好）来降低复杂度。

比如：$A(x_1,y_1)$,$B(x_2,y_2)$,余弦定义：$cos(\theta) = \frac{<A,B>}{|A||B|}$。

归一化后
	$$
	A\left(\frac{x_{1}}{\sqrt{x_{1}^{2}+y_{1}^{2}}}, \frac{y_{1}}{\sqrt{x_{1}^{2}+y_{1}^{2}}}\right), B\left(\frac{x_{2}}{\sqrt{x_{2}^{2}+y_{2}^{2}}}, \frac{y_{2}}{\sqrt{x_{2}^{2}+y_{2}^{2}}}\right)
	$$
	余弦相似度：
	$$
	\cos =\frac{x_{1}}{\sqrt{x_{1}^{2}+y_{1}^{2}}} \times \frac{x_{2}}{\sqrt{x_{2}^{2}+y_{2}^{2}}}+\frac{y_{1}}{\sqrt{x_{1}^{2}+y_{1}^{2}}} \times \frac{y_{2}}{\sqrt{x_{2}^{2}+y_{2}^{2}}}
	$$
	欧氏距离：
	$$
	\begin{aligned}
	e u c &=\sqrt{\left(\frac{x_{1}}{\sqrt{x_{1}^{2}+y_{1}^{2}}}-\frac{x_{2}}{\sqrt{x_{2}^{2}+y_{2}^{2}}}\right)^{2}+\left(\frac{y_{1}}{\sqrt{x_{1}^{2}+y_{1}^{2}}}-\frac{y_{2}}{\sqrt{x_{2}^{2}+y_{2}^{2}}}\right)^{2}} \\
	&=\sqrt{2-2 \times \cos }
	\end{aligned}
	$$

# 参考

1. [机器学习——几种距离度量方法比较](

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可，转载请附上原文出处链接和本声明。
本文链接地址：https://flyai.com/article/art617a84b4f907be693c132a91?type=e

讨论

500字

表情

发送

删除确认

是否删除该条评论？

取消删除