在軟件開(kāi)發(fā)和數(shù)據(jù)分析的過(guò)程中，有很多不同的距離的計(jì)算方法，如歐氏距離，馬氏距離，等等。對(duì)這些距離的理解，有助于我們更好的建立模型，規(guī)劃數(shù)據(jù)平臺(tái)的存儲(chǔ)和索引功能。網(wǎng)上對(duì)這些距離概念的介紹已經(jīng)很多，本文的主要目的，是對(duì)這些概念做一個(gè)歸納和總結(jié)。
首先，我們需要對(duì)”距離”本身進(jìn)行一些約束。我們所描述的距離，指的是度量空間（Metric space）的距離。良好的測(cè)距函數(shù)應(yīng)具備以下特征：
- 距離大于等于0；
- 距離是對(duì)稱(chēng)的，即 a 到 b 的距離應(yīng)等于 b 到 a 的距離；
- 相同的輸入，距離為0；
- 滿(mǎn)足三角不等式；
本文對(duì)一系列常見(jiàn)的，滿(mǎn)足上述原則的距離定義，作以下分類(lèi)：
1，連續(xù) m 維空間中，點(diǎn)和點(diǎn)的距離
閔可夫斯基距離（明氏距離）適用于多維連續(xù)空間中兩個(gè)點(diǎn)位置的判斷。每個(gè)空間內(nèi)的數(shù)值必須是連續(xù)的。 這一類(lèi)距離定義包括：歐幾里得距離（歐氏距離），曼哈頓距離，切比雪夫距離。 而這一族距離的定義，統(tǒng)稱(chēng)為閔可夫斯基距離。定義如下：
連續(xù) n 維空間中兩點(diǎn)
之間的明氏距離（閔可夫斯基距離）公式為:
p取1或2時(shí)的明氏距離是最為常用的：
歐氏距離是這里面我們最熟悉的類(lèi)型，以2維空間為例，歐氏距離即兩點(diǎn)之間的直線距離。曼哈頓距離就是各坐標(biāo)差的絕對(duì)值的和。而切比雪夫距離則是各坐標(biāo)上差的絕對(duì)值的最大值。
閔氏距離，包括曼哈頓距離、歐氏距離和切比雪夫距離都存在一些缺點(diǎn)：
各個(gè)分量的單位必須是等價(jià)的。如果有量綱不相等的維度，就無(wú)法適用。舉例來(lái)說(shuō)，考慮樓宇內(nèi)的定位問(wèn)題：水平方向上的單位是米，垂直方向的單位是”層“，在這種情況下就無(wú)法直接使用閔氏距離。通常這種情況下需要對(duì)數(shù)據(jù)做正規(guī)化；
沒(méi)有考慮各個(gè)分量的分布（期望，方差等)可能是不同的 ；
各個(gè)維度必須是互相獨(dú)立的，也就是“正交”的；
馬哈拉諾比斯距離（馬氏距離）針對(duì)上述第1，3個(gè)缺點(diǎn)做出了改進(jìn)。Wiki 描述如下：
它是一種有效的計(jì)算兩個(gè)未知樣本集的相似度的方法。與歐氏距離不同的是它考慮到各種特性之間的聯(lián)系（例如：一條關(guān)于身高的信息會(huì)帶來(lái)一條關(guān)于體重的信息，因?yàn)閮烧呤怯嘘P(guān)聯(lián)的）并且是尺度無(wú)關(guān)的（scale-invariant），即獨(dú)立于測(cè)量尺度。 對(duì)于一個(gè)均值為
協(xié)方差矩陣為
的多變量向量
其馬氏距離為
如果協(xié)方差矩陣為單位矩陣，馬哈拉諾比斯距離就簡(jiǎn)化為歐氏距離。
2，連續(xù) m 維空間中，向量和向量的距離
向量和向量之間的相似度，包含了兩層概念：角度的相似度，和大小的相似度。常見(jiàn)的向量距離計(jì)算方法是余弦距離（余弦相似度）。
兩個(gè)向量 A 和 B 之間的余弦相似度定義如下：
這里的
和
分別代表向量 A 和 B 的各分量。
對(duì)上述公式直觀的解釋?zhuān)窗驯容^對(duì)象各個(gè)方向上的長(zhǎng)度作為分母，各個(gè)方向分量的乘積和作為分子，這樣可以得到兩者的同一方向的分量“相同的程度”。 的值，當(dāng)
為0時(shí)為1，表示它們的指向是完全相同的，當(dāng)
為
時(shí)為-1，意味著兩個(gè)向量指向的方向正好相反。
余弦距離常被用于文本相似度的比較，如TF-IDF 權(quán)重的比較中。
3，m 維無(wú)序離散空間中的距離
這類(lèi)的距離，度量的是 m 維離散，無(wú)序空間中兩個(gè)變量之間的差異。兩個(gè)變量之間，只有距離的大小，沒(méi)有絕對(duì)值大小的區(qū)別。這里的變量的實(shí)際形式，可以是一組標(biāo)簽，一個(gè)字符串，等等。這類(lèi)距離中比較常見(jiàn)的有：
1. 編輯距離：編輯距離是一組定義的集合，指的是給定 2 個(gè)字符串 a, b，將 a 轉(zhuǎn)換為 b 的最少操作次數(shù)。
通常我們所說(shuō)的編輯距離，指的是萊文斯坦距離，字符操作只允許如下 3 種：
- 插入一個(gè)字符，例如：fj -> fxj
- 刪除一個(gè)字符，例如：fxj -> fj
- 替換一個(gè)字符，例如：jxj -> fyj
對(duì)編輯距離的計(jì)算需要使用動(dòng)態(tài)規(guī)劃法，時(shí)間復(fù)雜度為。
另外，Hamming distance 海明/漢明距離也是編輯距離的一種，但必須作用在等長(zhǎng)字符串上。 典型的應(yīng)用，有判斷圖像的相似度，先將圖像變?yōu)橄嗤叽绲暮诎讏D再計(jì)算。
2. Jaccard 距離：判斷兩個(gè)集合的相似度。Jaccard 相似度和 Jaccard 距離的計(jì)算方法如下：
Jaccard Index = (the number in both sets) / (the number in either set) * 100
Jaccard Distance = 1- Jaccard Index
Jaccard 距離很容易轉(zhuǎn)化為兩個(gè)等長(zhǎng)二進(jìn)制字符串的判斷，任意位上的1表示擁有該 item，0表示不具備該 item。計(jì)算 （不一樣的 bit 數(shù))/(總 bit 數(shù))% 即得到 Jaccard 距離。
這類(lèi)距離的索引，是軟件實(shí)現(xiàn)的噩夢(mèng)，而噩夢(mèng)的名稱(chēng)，就叫做維數(shù)災(zāi)難。常規(guī)的樹(shù)狀索引結(jié)構(gòu)，只能適用于有序數(shù)據(jù)，目前并沒(méi)有一種有效的索引結(jié)構(gòu)能夠?qū)崿F(xiàn)足夠高效的集合距離的查找（我沒(méi)有詳細(xì)查過(guò)相關(guān)論文，但我猜測(cè)理論上也不會(huì)存在這樣的索引結(jié)構(gòu)）。當(dāng)然，辦法還是有的。比較常見(jiàn)的方案是BK樹(shù)。然而對(duì)于特別大的數(shù)據(jù)集來(lái)說(shuō)，BK樹(shù)的剪枝效果遠(yuǎn)遠(yuǎn)談不上理想。在實(shí)際的應(yīng)用中，如 simhash 距離的查找中，只能采用一些比較 tricky 的方法來(lái)優(yōu)化，并且?guī)в兄T多限制。
總結(jié)
本文主要?dú)w納了各種距離定義的共性和適用范圍?；跀?shù)學(xué)的角度，分類(lèi)可能并不嚴(yán)謹(jǐn)，也不夠形式化，但我希望它能為相關(guān)軟件系統(tǒng)的設(shè)計(jì)提供一些參考。后續(xù)我會(huì)再總結(jié)一下，針對(duì)上述各種類(lèi)型的距離，我們是如何實(shí)現(xiàn)計(jì)算和索引功能的。
參考資料
本文除了文中自帶的鏈接外，應(yīng)該至少還參考了下列資料：
- 各種距離介紹：https://cloud.tencent.com/developer/article/1049090
- 協(xié)方差矩陣：https://zhuanlan.zhihu.com/p/37609917
- 協(xié)方差：https://www.cnblogs.com/chaosimple/p/3182157.html
- 概率論數(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
- 各種“差”的區(qū)別：http://hejunhao.me/archives/1163
