距離函數

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

數學中,距離函數(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). 

參考資料

外部連結