首页 计算机 机器学习

这篇文章是以 von Neumann: 距离定义系列文章为大纲，对各种距离函数的总结。

# 距离的基础知识

若个二元函数d(x,y):S2→[0,+∞)d(x,y): S^2 \to [0,+\infty) 满足：

  1. 非负性：d(x,y)≥0,∀x,y∈Sd(x,y) \geq 0,\; \forall x,y \in S.
  2. 同一性：d(x,y)=0d(x,y) = 0 当且仅当x=yx = y.
  3. 对称性：d(x,y)=d(y,x),∀x,y∈Sd(x,y) = d(y,x),\; \forall x,y\in S.
  4. 三角不等式：d(x,z)≤d(x,y)+d(y,z),∀x,y,z∈Sd(x,z) \leq d(x,y) + d(y,z), \;\forall x,y,z \in S.

那么称该二元函数是定义在SS 上的一个距离 (distance), 又称范数 (norm).

在实际情况中，距离的对称性并不一定要满足。例如将距离定义为条件概率，即d(x,y):=E(y∣x)d(x,y) := \mathbb{E}(y|x). 这时候，尽管不满足距离的基本定义，但是其仍可以起到距离的应用，即衡量两个元素之间的差异关系。此时，我们可以将其视为广义的距离。进一步地，对于某个不满足对称性的函数f(x,y)f(x,y), 可以将其对称化为g(x,y)=(f(x,y)+f(y,x))/2g(x,y) = \big(f(x,y) + f(y,x)\big)/2. 这样就得到了通常的对称函数。

此外，对于大多数常见的距离，其是可平移的，即

d(x,y)=d(x−a,y−a),∀x,y,a∈Sd(x,y) = d(x-a,y-a), \, \forall x,y,a \in S

这时候可以采用d(x,0)d(x,0) 来描述距离的定义式。

下面我们介绍一些常用或不常用的距离函数。作为研究灵感的启发。

# 距离函数简介

# 点距离

# 欧几里得距离

最基本的距离即为欧几里得距离 (Euclidean distance), 即欧氏距离。

在二维平面下如果两点的坐标为x(x1,x2),y(y1,y2)x(x_1,x_2),\, y(y_1,y_2), 那么其欧氏距离定义为

(x1−y1)2+(x2−y2)2\sqrt{(x_1-y_1)^2 + (x_2-y_2)^2}

对于两个nn 维点x(x1,x2,…,xn),y(y1,y2,…,yn)x(x_1,x_2,\dots,x_n),\, y(y_1,y_2,\dots, y_n), 其欧式距离为

∑i=1n(xi−yi)2\sqrt{\sum_{i=1}^n(x_i-y_i)^2}

# 闵可夫斯基距离

# 定义

对于两个nn 维点x(x1,x2,…,xn),y(y1,y2,…,yn)x(x_1,x_2,\dots,x_n),\, y(y_1,y_2,\dots, y_n),

(∑i=1n(xi−yi)p)1p\left(\sum_{i=1}^n(x_i-y_i)^p\right)^{\frac{1}{p}}

称为闵可夫斯基距离 (Minkowski distance), 又称为pp - 范数或LpL^p 范数，记作∥x−y∥p\|x-y\|_p.

闵可夫斯基距离的名称来源是闵可夫斯基不等式，即

(∑i=1n(xi+yi)p)1p≤(∑i=1nxip)1p+(∑i=1nyip)1p\left(\sum_{i=1}^n(x_i + y_i)^p\right)^\frac{1}{p} \leq \left(\sum_{i=1}^nx_i^p\right)^\frac{1}{p} + \left(\sum_{i=1}^ny_i^p\right)^\frac{1}{p}

其中xi,yi>0,p≥1x_i,y_i >0,\, p \geq 1. 该不等式是LpL_p 范数的三角不等式。这也说明了LpL_p 范数就是一个距离。

# 闵可夫斯基距离的性质

对于两点x(x1,x2,…,xn),y(y1,y2,…,yn)x(x_1,x_2,\dots,x_n),\, y(y_1,y_2,\dots, y_n). 在pp 取值不同时其闵可夫斯基距离的大小也不同。若p<qp < q, 则

∥x−y∥p≤∥x−y∥q\|x-y\|_p \leq \|x-y\|_q

当且仅当x=yx=y 时等号成立。该不等式称为幂平均不等式.

# 特殊的闵可夫斯基距离

在pp 取某些值时，LpL_p 范数具有特殊的含义，例如前述欧式距离即为L2L_2 范数。此外，还有几个常用的闵可夫斯基距离。具体如下：

# L0L_0 范数

L0L_0 范数是一个不十分严谨的范数概念。对两点x(x1,x2,…,dn),y(y1,y2,…,yn)x(x_1, x_2, \dots, d_n),\, y(y_1,y_2,\dots, y_n), 其表示xx 与yy 中对应坐标分量不相同的数目。显然其满足范数的几个基本的要求。

# 曼哈顿距离

曼哈顿距离即 L1L_1 范数。对两点 x(x1,x2,…,dn),y(y1,y2,…,yn)x(x_1, x_2, \dots, d_n),\, y(y_1,y_2,\dots, y_n), 其曼哈顿距离为对应坐标的绝对值之差求和，即

∥x−y∥1=∑n=1n∣xi−yi∣\|x-y\|_1 = \sum_{n=1}^n |x_i-y_i|

该距离在几何上表示为两个点之间沿水平竖直边前进的最短路径长度，这与曼哈顿的方格状街道类似，因此称为曼哈顿距离。

该距离在一些以方格边作为路径的部分建模中可以用到。但在一般的空间中意义不是十分明显。

# 切比雪夫距离

对两点 x(x1,x2,…,dn),y(y1,y2,…,yn)x(x_1, x_2, \dots, d_n),\, y(y_1,y_2,\dots, y_n), 其切比雪夫距离 (L∞L_\infty 范数) 定义为

∥x−y∥∞=lim⁡p→∞(∑i=1n(xi−yi)p)1p=max⁡1≤i≤n{∣xi−yi∣}\|x-y\|_\infty = \lim_{p \to \infty}\left(\sum_{i=1}^n(x_i-y_i)^p\right)^{\frac{1}{p}} = \max_{1\leq i \leq n}\{|x_i-y_i|\}

该范数实质上是求解两个点之间相差最大的坐标分量。

该范数的优点是理解和计算都相对比较容易。找到相差最大的坐标分量，一方面可以将两点比较明显区分开，可以便于后续的计算，并且在计算中可以减小误差 (这是经验表明的)。

该范数的缺点也比较明显，一是该范数与坐标轴的选取强相关，即使坐标轴的标度不变，但坐标轴发生旋转也会造成范数值的变化巨大。另一方面，该范数对各个坐标轴的信息敏感度不同，其缺少了通常意义下距离的部分个坐标间的对称性。这意味着，只要两点间相差最大的坐标分量彼此不变，那么即使其余分量在一定程度上进行变化，那么最终得到的范数都是不变的，因此其不能准确探测到一些分量的微小变化。

# 弗罗贝尼乌斯范数

欧氏距离的另一个推广是弗罗贝尼乌斯范数 (Frobenius norm), 又称希尔伯特 - 施密特范数 (Hilbert-Schmidt norm) 或L2,2L_{2,2} 范数。其是将欧氏距离的定义推广到了两个相同形状的矩阵上。对于矩阵A=(aij)m×n∈Rm×nA = (a_{ij})_{m\times n} \in \mathbb{R}^{m \times n}, 其弗罗贝尼乌斯范数定义为

∥A∥F=∑i=1m∑j=1n∣aij∣2=tr(A′A)\|A\|_F = \sqrt{\sum_{i=1}^m\sum_{j=1}^n|a_{ij}|^2} = \sqrt{\text{tr}(A'A)}

若矩阵为复矩阵，即A∈Cm×nA \in \mathbb{C}^{m \times n}, 那么其弗罗贝尼乌斯范数定义为

∥A∥F=tr(A†A)\|A\|_F = \sqrt{\text{tr}(A^\dag A)}

其中 A†A^\dag 表示 AA 的共轭转置。但复矩阵在计算机科学中不十分常用。

该范数在需要求解一些基本的矩阵距离时可以使用。例如采用两个矩阵表示同类的两个对象的一些信息，然后计算信息的相似度等。这是一种基本的矩阵范数，但不具有特殊的应用。

关于弗罗贝尼乌斯范数的更详细的内容可以参考 Wikipedia: Frobenius inner product 和 Wikipedia: Hilbert–Schmidt operator.

# 标准化的欧氏距离

如果将同一对象的不同信息采用数据表示，那么可以形成一个表示该对象的多维向量。采用欧氏距离，可以得到两个对象之间的差异大小。然而，由于向量不同维度的数据常常是不同量纲的，期间的比例也难以确定。因此一个自然的想法是将不同维度的数据进行标准化。这就产生了标准化的欧氏距离。

对点集S={xi}i=1mS = \{x_i\}_{i=1}^m, 将各分量按该分量的均值方差标准化，之后再计算欧氏距离，得到的距离就是标准化的欧式距离 (standardized Euclidean distance).

若其中点 xix_i 坐标为 (xi(1),xi(2),…,xi(n))\left(x_i^{(1)}, x_i^{(2)}, \dots, x_i^{(n)}\right). 那么，xix_i 与 xjx_j 的标准化欧氏距离为

∑k=1n(xi(k)−xj(k)σ(k))2\sqrt{\sum_{k=1}^n\left(\frac{x_i^{(k)} - x_j^{(k)}}{\sigma^{(k)}}\right)^2}

# 马哈拉诺比斯距离

参考 Selva Prabhakaran: Mahalanobis Distance – Understanding the math with examples.

# 随机变量距离

对于两个随机变量，我们常常需要衡量其差异，这个差异可以称作两个随机变量间的距离。这常常用于模型训练中衡量估计模型与实际情况之间的差距。随机变量的距离也在不断实践中发展出了不同的模型。主要包括下述几个计算模型。

# 皮尔逊相关系数

皮尔逊相关系数 (Pearson Correlation)，也称为相关系数或皮尔逊积矩相关系数 (Pearson Product-moment Correlation Coefficient，PPMCC\PCCs). 在我的概率论笔记中已经有过介绍，链接如下：

这是最基本的变量相似性的衡量。

# 卡方距离