距离函数

定義集合元素之間距離的數學函數

数学中,距离函数(distance function)或度量(度规)函数(metric function)是个函数,定义了集合内每一对元素之间的距离。带有度量的集合叫做度量空间。度量能导出集合上的拓扑,但不是所有拓扑都可以由度量生成。当一个拓扑空间的拓扑可以由度量来描述的时候,则称此一拓扑空间为可度量化的。

比较平面上曼哈顿度量欧几里得度量之不同:在曼哈顿度量里,三条线(红、黄、蓝)对相同的起终点有相同的长度(12);而在欧几里得度量里,绿线的长度为 ,且是唯一的最短路径。

微分几何中,“度量”一词也用来称呼定义为由微分流形切向量映射至标量双线性形式,让沿着曲线的距离可透过积分来取得。此一概念有个更适合的术语,称之为度量张量(或黎曼度量)。

定义

编辑

集合 X 上的度量为一函数(称之为“距离函数”或简称为“距离”)

d : X × XR

这里的 R实数的集合,且对于所有 X 内的 xyz,均满足如下条件:

  1. d(x, y) ≥ 0(非负性,或称分离公理)
  2. d(x, y) = 0 当且仅当 x = y(同时公理)
  3. d(x, y) = d(y, x)(对称性
  4. d(x, z) ≤ d(x, y) + d(y, z)(次加性三角不等式

条件1与条件2为正定函数的定义。条件1可由其他条件推导而出[1]

上述条件反应了对距离这个概念的直观想法。例如,不同点间之距离为正值,且从 x 至 y 的距离会等于从 y 至 x 的距离。三角不等式则意指从 x 经过 y 至 z 的距离至少会大于直接从 x 至 z 的距离。欧几里得在其著作中表示,两个点之间的最短距离为直线;这即是其几何学内之三角不等式。

上面的条件也可只保留条件2,再加上一个新的三角不等式条件:

4*. d(x, z) ≤ d(z, y) + d(y, x)

条件1可直接由条件4*导出[2]。使用条件2与条件4*可导出条件3,并因而给出条件4。

一度量被称为超度量,若该度量满足更强之三角不等式,每个点都不能落于其他点“之间”:

对于所有 M 中的 x, y, zd(x, z) ≤ max(d(x, y), d(y, z))

X 上的度量 d 叫做内在度量,如果 X 中的任两个点 xy 可以被其长度任意接近于 d(x, y) 的曲线连接起来。

对于定义了加法 + : X × XX 的集合,d 叫做平移不变度量,如果

d(x, y) = d(x + a, y + a)

,对于所有 X 中的 xya

例子

编辑
 
是定义相同拓扑的度量。(可以将   替代为任何严格正数可总和序列  。)
  • 图度量,依特定内的距离定义出之度量。
  • 编码理论里的汉明距离
  • 黎曼度量,一种适合用于任一微分流形上的度量。对任一此类流形,可在每个点 p 上选定一个对称、正定的双线性形式 L: Tp × Tp → ℝ,其中 Tp 为 p 上的切空间。因此,每个在此流形上的切向量 v 的长度即定义为 ||v|| = √L(v, v)。对于每个在此流形上的可微路径,其长度则定义为切向量之长度对路径上每个点的积分,其中其积分可透过路径参数计算之。最后,为得到定义于流形上每对点 {x, y} 上的度量,可取从 x 至 y 的所有路径间,其路径长度之最小值。具有黎曼度量之光滑流形称之为黎曼流形
  • 复投影空间上的富比尼–施图迪度量,为黎曼度量的一个例子。

度量的等价性

编辑

对于一个给定集合 X,两个度量 d1d2 被称为拓扑等价的 (一致等价的)如果恒等映射

id: (X,d1) → (X,d2)

同胚(一致同构)。

例如,如果   是度量,则    是等价于   的度量。

参见度量空间的等价性

向量空间上的度量

编辑

向量空间上的范数均等价于某个度量,且会是均匀与平移不变的。换句话说,每个范数都能决定一个度量,而某个度量能决定一个范数。

给定一个赋范向量空间 (X,||.||) ,可定义 X 上的度量为

d(x,y):=||x-y||。

度量 d 被称为由范数 ||.|| 所导出

反过来如果在向量空间 X 上的度量 d 满足下列性质

  • d(x,y) = d(x+a,y+a) (平移不变性)
  • dxy) = |α|d(x,y) (均匀性)

则可定义 X 上的范数

||x||:=d(x,0)

类似的,半范数能导出伪度量(见后),均匀(homogeneous)平移不变伪度量能导出半范数。

多重集上的度量

编辑

可将度量的概念由两个元素间之距离推广成非空有限多重集内元素之距离。多重集集合概念的推广,使得同一元素能出现多次。定义 Z=XY 为由多重集 X 与 Y 内元素所组成之多重集,亦即若 x 在 X 内出现一次,在 Y 内亦出现一次,则会在 Z 内出现两次。在非空有限多重集上的距离函数 d 是个度量[3],若

  1. d(X) = 0,若 X 内所有元素均相等,不然 d(X) > 0。(正定性)
  2. d(X) 在 X 的所有置换下不变。(对称性)
  3.  。(三角不等式

须注意,最熟悉的两个元素间之度量仅出现在条件 1 与条件 2 内的多重集 X 有两个元素,以及条件 3 内的多重集有一个元素的情形下。例如,若 X 由两个 x 所组成,则依据条件 1,d(X)=0。

一个简单的例子为由元素为整数之非空有限多重集 X 所组成之集合,具有度量  。较复杂的例子则有资讯距离归一化压缩距离[4]

推广度量

编辑

有许多放宽度量公理的方法,能给出较度量空间更为广义的不同概念。用来描述这些推广的词汇并没有统一,例如在泛函分析里的伪度量通常可由向量空间上的半范数导出,因此会很自然地称之为“半度量”。在拓扑学里,名词使用间的相互冲充时常出现。

扩展度量

编辑

一些作者允许距离函数 d 达到无限大值,亦即距离是在扩展实数线上的非负数。此一函数称之为扩展度量,或“∞-度量”。每个扩展度量均可换变成有限度量,使得度量空间在考量拓扑上之概念(如连续性收敛性)时会等价。此一有限度量可使用一个在零时值为零的次可加单调递增有界函数,如 d′(x, y) = d(x, y) / (1 + d(x, y)) or d′′(x, y) = min(1, d(x, y))。

度量的取值可由正实数 [0,∞) 推广至其他任一有向集合。在此一情形下,公理的重构会建构出一致空间:具有能比较不同点之局部拓扑的代数结构之拓扑空间。

伪度量

编辑

X 上的伪度量是个函数 d : X × X → R,满足度量的公理,除了条件 2 不一定只在相同元素时才为 0。换句话说,伪度量的公理为:

  1. d(x, y) ≥ 0
  2. d(x, x) = 0(但对于不同的值  ,也可能会出现 d(x, y)=0。)
  3. d(x, y) = d(y, x)
  4. d(x, z) ≤ d(x, y) + d(y, z).

在某些情形下,伪度量因其与半范数间的关系,会被称为半度量。

拟度量

编辑

有时,会定义拟度量为一个除对称性外,满足度量所有公理之函数[5][6]

  1. d(x, y) ≥ 0 (非负值)
  2. d(x, y) = 0   当且仅当   x = y (同时公理)
  3. d(x, y) = d(y, x) (对称性,没有)
  4. d(x, z) ≤ d(x, y) + d(y, z) (三角不等式)

在现实生活中,拟度量很常见。例如,给定一个由山村所组成之集合 X,则 X 内元素间之平均步行时间会形成一个拟度量,因为上坡会比下坡花去更多时间。另一个例子为具有单行道的计程车度量,从点 A 至点 B 的路径与从点 B 至点 A 的路径不组成不一样的集合。不过,这个概念很少用于数学之中,且其名称亦未完成统一[7]

实数上的拟度量可定义为

d(x, y) = xyxy,不然
d(x, y) = 1。其中,1可被替代为无限大或 1+10(y-x) 等值。

由此一拟度量所导出之拓扑空间为下限拓扑。此一空间可描述削去金属棒的过程:可轻易地减少其长度,但很难或不可能增加其长度。

若 d 为 X 上之拟度量,则下列式子可形成 X 上的度量 d':

d'(x, y) = 12(d(x, y) + d(y, x)).

半度量

编辑

X 上之半度量为一函数 d : X × X → R,满足前三个公理,但不一定满足三角不等式:

  1. d(x, y) ≥ 0
  2. d(x, y) = 0   当且仅当   x = y
  3. d(x, y) = d(y, x)

一些作者会使用较弱的三角不等式,如:

d(x, z) ≤ ρ (d(x, y) + d(y, z))     (ρ-放宽三角不等式)
d(x, z) ≤ ρ max(d(x, y), d(y, z))     (ρ-度量外不等式).

ρ-度量外不等式蕴涵着 ρ-放宽三角不等式(假定第一个公理成立),且 ρ-放宽三角不等式蕴涵着 2ρ-度量外不等式。三角不等式即为 1-放宽三角不等式,因此蕴涵着 2-度量外不等式,且超度量不等式恰为 1-度量外不等式。满足这些等价条件的半度量有时会被称为“拟度量”、“近度量”[8]或外度量[9]

ρ-度量外不等式被用来模拟互联网内的来回通讯延迟[9]

预度量

编辑

放宽度量的后三个公理会形成预度量,即一个满足下列条件之函数:

  1. d(x, y) ≥ 0
  2. d(x, x) = 0

其称呼并未统一。预度量有时会被用来指其他如伪半度量[10]或伪度量[11]等度量的推广。

每个预度量都能依下列方式形成拓扑。对于一个正实数 r,中心为点 p,半径为 r 的开球为

Br(p) = { x | d(x, p) < r }.

一个集合称之为“开放”的,若对于任一个集合内的点 p,均存在一个 Br(p) 包含于该集合内。每个预度量空间都是拓扑空间,并实际上,都是序列空间。一般而言,Br(p) 不一定会是此一拓扑之开集合。两个集合 A 与 B 间的距离可定义为

d(A, B) = infxA, yB d(x, y).

上式会形成预度量空间内幂集上之预度量。若从一(伪半)度量空间开始,则可得到一个伪半度量,亦即为一个对称预度量。每个预度量都可以形成一个预闭运算子,如下所示:

cl(A) = { x | d(x, A) = 0 }.

伪拟度量

编辑

可结合“伪”、“拟”、“半”等前缀词,如伪拟度量会放宽同时公理与对称公理,且仅是个具三角不等式的预度量。对于伪拟度量空间,开球可形成开集合的基。有关伪拟度量的一个非常基本的例子为集合 {0,1},具有 d(0,1) = 1 与 d(1,0) = 0 所形成之预度量。其对应之拓扑空间为谢尔宾斯基空间

威廉·劳维尔曾研究过具有扩展伪拟度量的集合,称之为“广义度量空间”[12][13]。从范畴论的观点来看,扩展拟度量空间与扩推伪拟度量空间,及其对应之不放大映射,是表现最好的度量空间范畴。可取任意多的积与上积,形成在给定范畴内的商对象。若去掉“扩展”这个条件,则只能取有限多的积与上积。若去掉“伪”这个条件,则无法形成商对象。趋近空间英语Approach space为能维持这些良好的范畴性质之度量空间的推广。

推广度量的重要情况

编辑

微分几何里会使用到度量张量,可被认为是个“无穷小”二次度量函数,被定义为在流形切空间上,具有适当之可微分性质非退化对称双线性形式。虽然度量张量不是本条目所定义之度量函数,透过对流形上之路径的度量张量之平方根积分,可导出伪半度量函数。具有度量张量的流形称为伪黎曼流形,用于相对论的几何研究内。若对度量张量上之内积加上正定性之性质,则其流形称之为黎曼流形,且其路径之积分能导出度量。

参见

编辑

注记

编辑
  1. ^ 依条件4,可知 d(x, y) + d(y, x) ≥ d(x,x)。再依条件3与条件2,可推得 2d(x, y) ≥ 0。因此,d(x, y) ≥ 0。
  2. ^ 由条件4*可得 d(y, x) ≤ d(x, x) + d(x, y) 及 d(x, x) ≤ d(x, y) + d(y, x),因此 d(x, y) ≥ 0。
  3. ^ Vitányi, Paul M. B. Information Distance in Multiples. IEEE Transactions on Information Theory. 2011-04, 57 (4): 2451–2456 [2022-03-22]. ISSN 1557-9654. doi:10.1109/TIT.2011.2110130. (原始内容存档于2022-04-20). 
  4. ^ Cohen, Andrew R.; Vitanyi, Paul M. B. Normalized Compression Distance of Multisets with Applications. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2015-08-01, 37 (8): 1602–1614 [2015-10-06]. ISSN 0162-8828. doi:10.1109/TPAMI.2014.2375175. (原始内容存档于2017-01-11). 
  5. ^ Steen & Seebach 1995
  6. ^ Smyth, M. B. Quasi-uniformities: Reconciling domains with metric spaces. Main, M. (编). Mathematical Foundations of Programming Language Semantics 298. Berlin, Heidelberg: Springer Berlin Heidelberg. 1988: 236–253. ISBN 978-3-540-19020-2. doi:10.1007/3-540-19020-1_12. 
  7. ^ Rolewicz, Stefan, Functional Analysis and Control Theory: Linear Systems, Springer, 1987, ISBN 90-277-2186-6, OCLC 13064804  书内称拟度量为“半度量”(semimetrics)。同一用词在另外两种推广度量中亦常被使用。
  8. ^ Xia, Qinglan. The Geodesic Problem in Quasimetric Spaces. Journal of Geometric Analysis. 2009-04, 19 (2): 452–479. ISSN 1050-6926. doi:10.1007/s12220-008-9065-4 (英语). 
  9. ^ 9.0 9.1 Fraigniaud, P.; Lebhar, E.; Viennot, L. The Inframetric Model for the Internet. IEEE INFOCOM 2008 - The 27th Conference on Computer Communications. 2008-04: 1085–1093 [2022-03-22]. doi:10.1109/INFOCOM.2008.163. (原始内容存档于2022-03-22). 
  10. ^ Buldygin, V.V.; Kozachenko, I.U.V., Metric characterization of random variables and random processes, 2000 .
  11. ^ Khelemskiĭ, Lectures and exercises on functional analysis, 2006 .
  12. ^ Lawvere, F. William. Metric spaces, generalized logic, and closed categories. Rendiconti del Seminario Matematico e Fisico di Milano. 1973-12, 43 (1): 135–166. ISSN 0370-7377. doi:10.1007/BF02924844 (英语). 
  13. ^ Vickers. Localic completion of generalized metric spaces II: Powerlocales. Journal of Logic and Analysis. 2009 [2022-03-22]. doi:10.4115/jla.2009.1.11. (原始内容存档于2018-06-02). 

参考资料

编辑

外部链接

编辑