在軟件開發(fā)和數(shù)據(jù)分析的過程中探遵，有很多不同的距離的計算方法，如歐氏距離妓柜，馬氏距離箱季，等等。對這些距離的理解棍掐，有助于我們更好的建立模型藏雏，規(guī)劃數(shù)據(jù)平臺的存儲和索引功能。網(wǎng)上對這些距離概念的介紹已經(jīng)很多作煌，本文的主要目的掘殴，是對這些概念做一個歸納和總結(jié)。

首先最疆，我們需要對”距離”本身進(jìn)行一些約束杯巨。我們所描述的距離，指的是度量空間（Metric space）的距離努酸。良好的測距函數(shù)應(yīng)具備以下特征：

• 距離大于等于0；
• 距離是對稱的杜恰，即 a 到 b 的距離應(yīng)等于 b 到 a 的距離获诈；
• 相同的輸入，距離為0心褐；
• 滿足三角不等式舔涎；

本文對一系列常見的，滿足上述原則的距離定義逗爹，作以下分類：

1亡嫌，連續(xù) m 維空間中嚎于，點和點的距離

閔可夫斯基距離（明氏距離）適用于多維連續(xù)空間中兩個點位置的判斷。每個空間內(nèi)的數(shù)值必須是連續(xù)的挟冠。 這一類距離定義包括：歐幾里得距離（歐氏距離）于购，曼哈頓距離，切比雪夫距離知染。 而這一族距離的定義肋僧，統(tǒng)稱為閔可夫斯基距離。定義如下：

連續(xù) n 維空間中兩點

之間的明氏距離（閔可夫斯基距離）公式為:

p取1或2時的明氏距離是最為常用的：

1. p=2即為歐氏距離
2. p=1時則為曼哈頓距離控淡。
3. 當(dāng)p取無窮時的極限情況下嫌吠，可以得到切比雪夫距離：
   

歐氏距離是這里面我們最熟悉的類型，以2維空間為例掺炭，歐氏距離即兩點之間的直線距離辫诅。曼哈頓距離就是各坐標(biāo)差的絕對值的和。而切比雪夫距離則是各坐標(biāo)上差的絕對值的最大值涧狮。

二維空間的歐氏距離和曼哈頓距離

閔氏距離炕矮，包括曼哈頓距離、歐氏距離和切比雪夫距離都存在一些缺點：

1. 各個分量的單位必須是等價的勋篓。如果有量綱不相等的維度吧享，就無法適用。舉例來說譬嚣，考慮樓宇內(nèi)的定位問題：水平方向上的單位是米钢颂，垂直方向的單位是”層“，在這種情況下就無法直接使用閔氏距離拜银。通常這種情況下需要對數(shù)據(jù)做正規(guī)化殊鞭；

2. 沒有考慮各個分量的分布（期望，方差等)可能是不同的 尼桶；

3. 各個維度必須是互相獨立的操灿，也就是“正交”的；

馬哈拉諾比斯距離（馬氏距離）針對上述第1泵督，3個缺點做出了改進(jìn)趾盐。Wiki 描述如下：

它是一種有效的計算兩個未知樣本集的相似度的方法。與歐氏距離不同的是它考慮到各種特性之間的聯(lián)系（例如：一條關(guān)于身高的信息會帶來一條關(guān)于體重的信息小腊，因為兩者是有關(guān)聯(lián)的）并且是尺度無關(guān)的（scale-invariant）救鲤，即獨立于測量尺度。 對于一個均值為

協(xié)方差矩陣為 的多變量向量 其馬氏距離為

如果協(xié)方差矩陣為單位矩陣，馬哈拉諾比斯距離就簡化為歐氏距離入问。

2丹锹，連續(xù) m 維空間中稀颁，向量和向量的距離

向量和向量之間的相似度，包含了兩層概念：角度的相似度楣黍，和大小的相似度匾灶。常見的向量距離計算方法是余弦距離（余弦相似度）。

兩個向量 A 和 B 之間的余弦相似度定義如下：

這里的 和 分別代表向量 A 和 B 的各分量锡凝。

對上述公式直觀的解釋粘昨，即把比較對象各個方向上的長度作為分母，各個方向分量的乘積和作為分子窜锯，這樣可以得到兩者的同一方向的分量“相同的程度”张肾。 的值，當(dāng) 為0時為1锚扎，表示它們的指向是完全相同的隔盛，當(dāng) 為 時為-1丽已，意味著兩個向量指向的方向正好相反坯癣。

向量的余弦距離

余弦距離常被用于文本相似度的比較炸庞，如TF-IDF 權(quán)重的比較中。

3翠勉，m 維無序離散空間中的距離

這類的距離妖啥，度量的是 m 維離散，無序空間中兩個變量之間的差異对碌。兩個變量之間荆虱，只有距離的大小，沒有絕對值大小的區(qū)別朽们。這里的變量的實際形式怀读，可以是一組標(biāo)簽，一個字符串骑脱，等等菜枷。這類距離中比較常見的有：

1. 編輯距離：編輯距離是一組定義的集合，指的是給定 2 個字符串 a, b叁丧，將 a 轉(zhuǎn)換為 b 的最少操作次數(shù)啤誊。

通常我們所說的編輯距離，指的是萊文斯坦距離拥娄，字符操作只允許如下 3 種：

• 插入一個字符坷衍，例如：fj -> fxj
• 刪除一個字符，例如：fxj -> fj
• 替換一個字符条舔，例如：jxj -> fyj

對編輯距離的計算需要使用動態(tài)規(guī)劃法，時間復(fù)雜度為乏矾。

另外孟抗，Hamming distance 海明/漢明距離也是編輯距離的一種迁杨，但必須作用在等長字符串上。 典型的應(yīng)用凄硼，有判斷圖像的相似度铅协，先將圖像變?yōu)橄嗤叽绲暮诎讏D再計算。

2. Jaccard 距離：判斷兩個集合的相似度摊沉。Jaccard 相似度和 Jaccard 距離的計算方法如下：

Jaccard Index = (the number in both sets) / (the number in either set) * 100
Jaccard Distance = 1- Jaccard Index

Jaccard 指數(shù)即“交集/并集”

Jaccard 距離很容易轉(zhuǎn)化為兩個等長二進(jìn)制字符串的判斷狐史，任意位上的1表示擁有該 item，0表示不具備該 item说墨。計算 （不一樣的 bit 數(shù))/(總 bit 數(shù))% 即得到 Jaccard 距離骏全。

這類距離的索引，是軟件實現(xiàn)的噩夢尼斧，而噩夢的名稱姜贡，就叫做維數(shù)災(zāi)難。常規(guī)的樹狀索引結(jié)構(gòu)棺棵，只能適用于有序數(shù)據(jù)楼咳，目前并沒有一種有效的索引結(jié)構(gòu)能夠?qū)崿F(xiàn)足夠高效的集合距離的查找（我沒有詳細(xì)查過相關(guān)論文，但我猜測理論上也不會存在這樣的索引結(jié)構(gòu)）烛恤。當(dāng)然母怜，辦法還是有的。比較常見的方案是BK樹缚柏。然而對于特別大的數(shù)據(jù)集來說苹熏，BK樹的剪枝效果遠(yuǎn)遠(yuǎn)談不上理想。在實際的應(yīng)用中船惨，如 simhash 距離的查找中柜裸，只能采用一些比較 tricky 的方法來優(yōu)化，并且?guī)в兄T多限制粱锐。

總結(jié)

本文主要歸納了各種距離定義的共性和適用范圍疙挺。基于數(shù)學(xué)的角度怜浅，分類可能并不嚴(yán)謹(jǐn)铐然，也不夠形式化，但我希望它能為相關(guān)軟件系統(tǒng)的設(shè)計提供一些參考恶座。后續(xù)我會再總結(jié)一下搀暑，針對上述各種類型的距離，我們是如何實現(xiàn)計算和索引功能的跨琳。

參考資料

本文除了文中自帶的鏈接外自点，應(yīng)該至少還參考了下列資料：

1. 各種距離介紹：https://cloud.tencent.com/developer/article/1049090
2. 協(xié)方差矩陣：https://zhuanlan.zhihu.com/p/37609917
3. 協(xié)方差：https://www.cnblogs.com/chaosimple/p/3182157.html
4. 概率論數(shù)字特征：https://blog.csdn.net/thesnowboy_2/article/details/69564226#%E5%8D%8F%E6%96%B9%E5%B7%AE%E7%9F%A9%E9%98%B5
5. 各種“差”的區(qū)別：http://hejunhao.me/archives/1163