闵可夫斯基距离是由坐标向量表示的点之间的一族距离,其计算方法是将各坐标差的绝对值取 p 次幂后求和,再取 p 次方根。当 p≥1 时,它是由 p-范数诱导的距离,在有限维实坐标空间上定义了一个度量。这族距离以赫尔曼·闵可夫斯基的名字命名,包括 p=1 时的曼哈顿距离、p=2 时的欧几里得距离,以及作为极限情形的 p=∞ 时的切比雪夫距离。它广泛应用于几何学、数值计算和数据分析。
定义
对于 Rn 中的两点 x=(x1,…,xn) 和 y=(y1,…,yn),以及实参数 1≤p<∞,闵可夫斯基距离定义为
dp(x,y)=(i=1∑n∣xi−yi∣p)1/p.
其中,∣xi−yi∣ 是第 i 个坐标之差的绝对值。等价地,
dp(x,y)=∥x−y∥p.
极限情形定义为
d∞(x,y)=1≤i≤nmax∣xi−yi∣,
并满足
p→∞limdp(x,y)=d∞(x,y).
参数 p 有时称为距离的阶数,它决定了各坐标差的汇总方式。其值越大,最大的坐标差所受到的相对重视程度就越高。
将绝对值替换为复数的模后,同一公式也适用于坐标为复数的向量。
重要特例
曼哈顿距离
当 p=1 时,
d1(x,y)=i=1∑n∣xi−yi∣.
它也称为街区距离或出租车距离,衡量的是沿各坐标方向的位移总量。在没有障碍物的矩形街道网格上,如果只能沿坐标方向行进,它给出的就是最短路线长度。
欧几里得距离
当 p=2 时,
d2(x,y)=i=1∑n(xi−yi)2.
这就是欧几里得空间中通常所说的直线距离,可由勾股定理得到。它是这族距离中由标准内积诱导的距离。
切比雪夫距离
当 p=∞ 时,
d∞(x,y)=imax∣xi−yi∣.
它也称为最大值距离,只取决于最大的坐标差。在二维情形下,若水平、竖直和斜向移动的代价均为一个单位,它描述的就是国际象棋中的王在没有障碍的棋盘上,从一个方格移动到另一个方格所需的最少步数。
例如,若 x=(1,2)、y=(4,6),则两个坐标差的绝对值分别为 3 和 4,因此
d1(x,y)=7,d2(x,y)=5,d∞(x,y)=4.
度量性质
对于每个 p∈[1,∞],闵可夫斯基距离都满足:
非负性: dp(x,y)≥0。
同一性: dp(x,y)=0 当且仅当 x=y。
对称性: dp(x,y)=dp(y,x)。
三角不等式:
dp(x,z)≤dp(x,y)+dp(y,z).
当 p 为有限值时,三角不等式可由闵可夫斯基不等式推出:
(i∑∣ai+bi∣p)1/p≤(i∑∣ai∣p)1/p+(i∑∣bi∣p)1/p.
闵可夫斯基距离具有平移不变性,并随整体缩放而按比例变化:
dp(x+a,y+a)=dp(x,y),dp(cx,cy)=∣c∣dp(x,y).
对坐标进行置换,或对两个点的相应坐标同时反号,都不会改变这族距离中的任何一种。不过,在至少二维的空间中,只有 p=2 时的距离在所有欧几里得旋转下都保持不变。对于其他 p 值,所选的坐标轴也是几何结构的一部分。
几何形状与不同阶数的比较
闭单位球为
Bp={x∈Rn:i∑∣xi∣p≤1},
其中 B∞={x:maxi∣xi∣≤1}。它们都是凸集。
在二维空间中,单位球的形状为:
- 当 p=1 时,是顶点位于坐标轴上的菱形;
- 当 p=2 时,是圆盘;
- 当 p=∞ 时,是各边平行于坐标轴的正方形。
当 1<p<∞ 时,单位球是严格凸的:其边界不含任何非退化的直线段。因此,不计参数化方式的差异,两点之间的唯一最短路径就是连接它们的直线段。当 p=1 或 p=∞ 时,则可能存在不同的最短路径。
对于固定向量 v∈Rn 以及 1≤p<q≤∞,有
∥v∥q≤∥v∥p≤n1/p−1/q∥v∥q,
其中 1/∞=0。因此,固定两点之间未经归一化的距离随 p 增大而单调不增。
这些界还表明,在固定的有限维空间上,所有闵可夫斯基距离都生成相同的拓扑:它们具有相同的收敛序列和开集。不过,它们所确定的最近邻以及点对之间距离的排序不一定相同。
加权形式与归一化形式
加权闵可夫斯基距离通常定义为
dp,w(x,y)=(i=1∑nwi∣xi−yi∣p)1/p,wi>0.
它等价于将第 i 个坐标乘以 wi1/p 后得到的普通闵可夫斯基距离。严格为正的权重能够保留度量性质。如果某些权重为零,那么仅在这些坐标上不同的两个不同向量之间,距离也可能为零;此时得到的是整个坐标空间上的伪度量,而不是度量。
一种归一化形式为
dˉp(x,y)=(n1i=1∑n∣xi−yi∣p)1/p=n−1/pdp(x,y).
对于固定的 n 和 p,归一化相当于将所有距离乘以同一个正常数,因此不会改变最近邻的排序。它随 p 变化的规律与未经归一化的距离不同:作为各坐标差绝对值的幂平均,dˉp 随 p 增大而单调不减。
加权方式并没有统一约定。若求和项写为 ∣wi(xi−yi)∣p,则实际系数是 wip,而不是 wi。
指数小于一的情形
当 0<p<1 时,同一代数表达式有时也被称为闵可夫斯基距离,但它通常不是度量。
例如,令 x=(1,0)、y=(0,0)、z=(0,1),则
dp(x,z)=21/p>2=dp(x,y)+dp(y,z),
因此三角不等式不成立。相应的表达式是一个拟范数,其单位球在至少二维的空间中不是凸集。
需要特别区分这个表达式与它的 p 次幂。当 0<p<1 时,
ρp(x,y)=i∑∣xi−yi∣p
确实定义了一个度量,因为对于非负的 a,b,有 (a+b)p≤ap+bp。正是最外层的指数 1/p 使通常的公式无法满足三角不等式。
应用与局限
闵可夫斯基距离用于最近邻搜索、聚类分析、模式识别以及机器学习的其他领域。参数 p 提供的是一族几何结构,而不是一种普遍最优的相似性度量。
当 p=1 时,直接将各坐标差的绝对值相加。当 p=2 时,平方运算使较大的差异得到更高的相对重视。当 p=∞ 时,距离仅由最大的差异决定。对于固定的查询点和有限的 p,最小化 dp 等价于最小化
dp(x,y)p=i∑∣xi−yi∣p,
因为取正的 p 次方根不会改变大小顺序。不过,当 p>1 时,这个取幂后的表达式本身通常不是度量。
以下几个问题会影响对距离的解释:
- 坐标尺度: 采用数值较大的单位计量的变量可能主导距离。重新缩放坐标会改变各变量的相对影响。
- 变量之间的依赖关系: 普通闵可夫斯基距离不考虑协方差。马哈拉诺比斯距离则利用协方差矩阵构造了另一种距离。
- 较大的差异: p 越大,异常大的坐标差所受到的相对重视就越高。但仅仅采用较小的 p,并不能保证统计方法具有稳健性。
- 高维性: 在某些高维数据模型中,距离会趋于集中,区分能力随之减弱,这是维数灾难的一个方面。
- 坐标的含义: 用数值对类别进行编码,并不意味着这些数值之差就能作为有意义的距离。
当有限的 p 很大时,直接计算 ∣xi−yi∣p 可能导致数值上溢或下溢。若
m=imax∣xi−yi∣>0,
则可使用以下等价的缩放公式:
dp(x,y)=m(i∑(m∣xi−yi∣)p)1/p.
归一化后的差值位于 [0,1] 内,可降低幂运算发生上溢的风险。当 m=0 时,距离为零。
与函数空间及时空的关系
闵可夫斯基距离对应于Lp 空间中由范数诱导的距离的有限维情形;在后者中,求和被替换为积分:
dp(f,g)=(∫∣f−g∣pdμ)1/p.
在这种情形下,几乎处处相等的函数被视为同一个元素,从而使零距离对应于空间中的同一个元素。有限维空间中所有 p-范数的等价性不能原样推广到无限维空间:不同的指数可能要求本质上不同的可积性条件。
尽管名称相同,闵可夫斯基距离并不是狭义相对论中的时空间隔。后者采用不定二次型,区分类时、类空和类光间隔,并不是上述意义下的非负度量。