aiwiki.page
中文
数学 / 几何与拓扑 / minkowski-distance

闵可夫斯基距离

闵可夫斯基距离是以指数为参数的一族坐标向量距离,包括曼哈顿距离、欧几里得距离和切比雪夫距离。

21 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
范数(数学)度量空间欧几里得距离绝对值复数欧几里得空间勾股定理内积闵可夫斯基…

闵可夫斯基距离是由坐标向量表示的点之间的一族距离,其计算方法是将各坐标差的绝对值取 pp 次幂后求和,再取 pp 次方根。当 p≥1p\geq 1 时,它是由 pp-范数诱导的距离,在有限维实坐标空间上定义了一个度量。这族距离以赫尔曼·闵可夫斯基的名字命名,包括 p=1p=1 时的曼哈顿距离、p=2p=2 时的欧几里得距离,以及作为极限情形的 p=∞p=\infty 时的切比雪夫距离。它广泛应用于几何学、数值计算和数据分析。

定义

对于 Rn\mathbb{R}^n 中的两点 x=(x1,…,xn)x=(x_1,\ldots,x_n) 和 y=(y1,…,yn)y=(y_1,\ldots,y_n),以及实参数 1≤p<∞1\leq p<\infty,闵可夫斯基距离定义为

dp(x,y)=(∑i=1n∣xi−yi∣p)1/p.d_p(x,y)=\left(\sum_{i=1}^{n}|x_i-y_i|^p\right)^{1/p}.

其中,∣xi−yi∣|x_i-y_i| 是第 ii 个坐标之差的绝对值。等价地,

dp(x,y)=∥x−y∥p.d_p(x,y)=\|x-y\|_p.

极限情形定义为

d∞(x,y)=max⁡1≤i≤n∣xi−yi∣,d_\infty(x,y)=\max_{1\leq i\leq n}|x_i-y_i|,

并满足

lim⁡p→∞dp(x,y)=d∞(x,y).\lim_{p\to\infty}d_p(x,y)=d_\infty(x,y).

参数 pp 有时称为距离的阶数,它决定了各坐标差的汇总方式。其值越大,最大的坐标差所受到的相对重视程度就越高。

将绝对值替换为复数的模后,同一公式也适用于坐标为复数的向量。

重要特例

曼哈顿距离

当 p=1p=1 时,

d1(x,y)=∑i=1n∣xi−yi∣.d_1(x,y)=\sum_{i=1}^{n}|x_i-y_i|.

它也称为街区距离或出租车距离,衡量的是沿各坐标方向的位移总量。在没有障碍物的矩形街道网格上,如果只能沿坐标方向行进,它给出的就是最短路线长度。

欧几里得距离

当 p=2p=2 时,

d2(x,y)=∑i=1n(xi−yi)2.d_2(x,y)=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2}.

这就是欧几里得空间中通常所说的直线距离,可由勾股定理得到。它是这族距离中由标准内积诱导的距离。

切比雪夫距离

当 p=∞p=\infty 时,

d∞(x,y)=max⁡i∣xi−yi∣.d_\infty(x,y)=\max_i|x_i-y_i|.

它也称为最大值距离,只取决于最大的坐标差。在二维情形下,若水平、竖直和斜向移动的代价均为一个单位,它描述的就是国际象棋中的王在没有障碍的棋盘上,从一个方格移动到另一个方格所需的最少步数。

例如,若 x=(1,2)x=(1,2)、y=(4,6)y=(4,6),则两个坐标差的绝对值分别为 33 和 44,因此

d1(x,y)=7,d2(x,y)=5,d∞(x,y)=4.d_1(x,y)=7,\qquad d_2(x,y)=5,\qquad d_\infty(x,y)=4.

度量性质

对于每个 p∈[1,∞]p\in[1,\infty],闵可夫斯基距离都满足:

  • 非负性: dp(x,y)≥0d_p(x,y)\geq 0。

  • 同一性: dp(x,y)=0d_p(x,y)=0 当且仅当 x=yx=y。

  • 对称性: dp(x,y)=dp(y,x)d_p(x,y)=d_p(y,x)。

  • 三角不等式:

    dp(x,z)≤dp(x,y)+dp(y,z).d_p(x,z)\leq d_p(x,y)+d_p(y,z).

当 pp 为有限值时,三角不等式可由闵可夫斯基不等式推出:

(∑i∣ai+bi∣p)1/p≤(∑i∣ai∣p)1/p+(∑i∣bi∣p)1/p.\left(\sum_i|a_i+b_i|^p\right)^{1/p} \leq \left(\sum_i|a_i|^p\right)^{1/p} + \left(\sum_i|b_i|^p\right)^{1/p}.

闵可夫斯基距离具有平移不变性,并随整体缩放而按比例变化:

dp(x+a,y+a)=dp(x,y),dp(cx,cy)=∣c∣ dp(x,y).d_p(x+a,y+a)=d_p(x,y), \qquad d_p(cx,cy)=|c|\,d_p(x,y).

对坐标进行置换,或对两个点的相应坐标同时反号,都不会改变这族距离中的任何一种。不过,在至少二维的空间中,只有 p=2p=2 时的距离在所有欧几里得旋转下都保持不变。对于其他 pp 值,所选的坐标轴也是几何结构的一部分。

几何形状与不同阶数的比较

闭单位球为

Bp={x∈Rn:∑i∣xi∣p≤1},B_p=\left\{x\in\mathbb{R}^n:\sum_i|x_i|^p\leq 1\right\},

其中 B∞={x:max⁡i∣xi∣≤1}B_\infty=\{x:\max_i|x_i|\leq1\}。它们都是凸集。

在二维空间中,单位球的形状为:

  • 当 p=1p=1 时,是顶点位于坐标轴上的菱形;
  • 当 p=2p=2 时,是圆盘;
  • 当 p=∞p=\infty 时,是各边平行于坐标轴的正方形。

当 1<p<∞1<p<\infty 时,单位球是严格凸的:其边界不含任何非退化的直线段。因此,不计参数化方式的差异,两点之间的唯一最短路径就是连接它们的直线段。当 p=1p=1 或 p=∞p=\infty 时,则可能存在不同的最短路径。

对于固定向量 v∈Rnv\in\mathbb{R}^n 以及 1≤p<q≤∞1\leq p<q\leq\infty,有

∥v∥q≤∥v∥p≤n 1/p−1/q∥v∥q,\|v\|_q\leq\|v\|_p \leq n^{\,1/p-1/q}\|v\|_q,

其中 1/∞=01/\infty=0。因此,固定两点之间未经归一化的距离随 pp 增大而单调不增。

这些界还表明,在固定的有限维空间上,所有闵可夫斯基距离都生成相同的拓扑:它们具有相同的收敛序列和开集。不过,它们所确定的最近邻以及点对之间距离的排序不一定相同。

加权形式与归一化形式

加权闵可夫斯基距离通常定义为

dp,w(x,y)=(∑i=1nwi∣xi−yi∣p)1/p,wi>0.d_{p,w}(x,y)= \left(\sum_{i=1}^{n}w_i|x_i-y_i|^p\right)^{1/p}, \qquad w_i>0.

它等价于将第 ii 个坐标乘以 wi1/pw_i^{1/p} 后得到的普通闵可夫斯基距离。严格为正的权重能够保留度量性质。如果某些权重为零,那么仅在这些坐标上不同的两个不同向量之间,距离也可能为零;此时得到的是整个坐标空间上的伪度量,而不是度量。

一种归一化形式为

dˉp(x,y)=(1n∑i=1n∣xi−yi∣p)1/p=n−1/pdp(x,y).\bar d_p(x,y)= \left(\frac{1}{n}\sum_{i=1}^{n}|x_i-y_i|^p\right)^{1/p} =n^{-1/p}d_p(x,y).

对于固定的 nn 和 pp,归一化相当于将所有距离乘以同一个正常数,因此不会改变最近邻的排序。它随 pp 变化的规律与未经归一化的距离不同:作为各坐标差绝对值的幂平均,dˉp\bar d_p 随 pp 增大而单调不减。

加权方式并没有统一约定。若求和项写为 ∣wi(xi−yi)∣p|w_i(x_i-y_i)|^p,则实际系数是 wipw_i^p,而不是 wiw_i。

指数小于一的情形

当 0<p<10<p<1 时,同一代数表达式有时也被称为闵可夫斯基距离,但它通常不是度量。

例如,令 x=(1,0)x=(1,0)、y=(0,0)y=(0,0)、z=(0,1)z=(0,1),则

dp(x,z)=21/p>2=dp(x,y)+dp(y,z),d_p(x,z)=2^{1/p}>2=d_p(x,y)+d_p(y,z),

因此三角不等式不成立。相应的表达式是一个拟范数,其单位球在至少二维的空间中不是凸集。

需要特别区分这个表达式与它的 pp 次幂。当 0<p<10<p<1 时,

ρp(x,y)=∑i∣xi−yi∣p\rho_p(x,y)=\sum_i|x_i-y_i|^p

确实定义了一个度量,因为对于非负的 a,ba,b,有 (a+b)p≤ap+bp(a+b)^p\leq a^p+b^p。正是最外层的指数 1/p1/p 使通常的公式无法满足三角不等式。

应用与局限

闵可夫斯基距离用于最近邻搜索、聚类分析、模式识别以及机器学习的其他领域。参数 pp 提供的是一族几何结构,而不是一种普遍最优的相似性度量。

当 p=1p=1 时,直接将各坐标差的绝对值相加。当 p=2p=2 时,平方运算使较大的差异得到更高的相对重视。当 p=∞p=\infty 时,距离仅由最大的差异决定。对于固定的查询点和有限的 pp,最小化 dpd_p 等价于最小化

dp(x,y)p=∑i∣xi−yi∣p,d_p(x,y)^p=\sum_i|x_i-y_i|^p,

因为取正的 pp 次方根不会改变大小顺序。不过,当 p>1p>1 时,这个取幂后的表达式本身通常不是度量。

以下几个问题会影响对距离的解释:

  • 坐标尺度: 采用数值较大的单位计量的变量可能主导距离。重新缩放坐标会改变各变量的相对影响。
  • 变量之间的依赖关系: 普通闵可夫斯基距离不考虑协方差。马哈拉诺比斯距离则利用协方差矩阵构造了另一种距离。
  • 较大的差异: pp 越大,异常大的坐标差所受到的相对重视就越高。但仅仅采用较小的 pp,并不能保证统计方法具有稳健性。
  • 高维性: 在某些高维数据模型中,距离会趋于集中,区分能力随之减弱,这是维数灾难的一个方面。
  • 坐标的含义: 用数值对类别进行编码,并不意味着这些数值之差就能作为有意义的距离。

当有限的 pp 很大时,直接计算 ∣xi−yi∣p|x_i-y_i|^p 可能导致数值上溢或下溢。若

m=max⁡i∣xi−yi∣>0,m=\max_i|x_i-y_i|>0,

则可使用以下等价的缩放公式:

dp(x,y)=m(∑i(∣xi−yi∣m)p)1/p.d_p(x,y)= m\left(\sum_i \left(\frac{|x_i-y_i|}{m}\right)^p \right)^{1/p}.

归一化后的差值位于 [0,1][0,1] 内,可降低幂运算发生上溢的风险。当 m=0m=0 时,距离为零。

与函数空间及时空的关系

闵可夫斯基距离对应于LpL^p 空间中由范数诱导的距离的有限维情形;在后者中,求和被替换为积分:

dp(f,g)=(∫∣f−g∣p dμ)1/p.d_p(f,g)= \left(\int |f-g|^p\,d\mu\right)^{1/p}.

在这种情形下,几乎处处相等的函数被视为同一个元素,从而使零距离对应于空间中的同一个元素。有限维空间中所有 pp-范数的等价性不能原样推广到无限维空间:不同的指数可能要求本质上不同的可积性条件。

尽管名称相同,闵可夫斯基距离并不是狭义相对论中的时空间隔。后者采用不定二次型,区分类时、类空和类光间隔,并不是上述意义下的非负度量。