全面歸納距離和相似度方法 -7 種-

距離 (distance，差異程度)、相似度(similarity，相似程度) 方法可以看作是以某種的距離函數計算元素間的距離，這些方法作爲機器學習的基礎概念，廣泛應用於如：Kmeans 聚類、協同過濾推薦算法、相似度算法、MSE 損失函數、正則化範數等等。本文對常用的距離計算方法進行歸納以及解析，分爲以下幾類展開：

一、閔氏距離（Minkowski Distance）類

二、相似度（Similarity)

三、字符串距離 (Distance of Strings)

四、集合距離 (Distance of Sets)

五、信息論距離 (Information Theory measures)

六、時間系列、圖結構的距離

七、度量學習 (Metric Learning)

附、常用的度量方法彙總

一、閔氏距離（Distance）類

對於點 x=(x1,x2...xn) 與點 y=(y1,y2...yn) , 閔氏距離可以用下式表示：

閔氏距離是對多個距離度量公式的概括性的表述，p=1 退化爲曼哈頓距離；p=2 退化爲歐氏距離；切比雪夫距離是閔氏距離取極限的形式。

曼哈頓距離 公式：

歐幾里得距離公式：

如下圖藍線的距離即是曼哈頓距離（想象你在曼哈頓要從一個十字路口開車到另外一個十字路口實際駕駛距離就是這個 “曼哈頓距離”，此即曼哈頓距離名稱的來源，也稱爲城市街區距離），紅線爲歐幾里得距離：

切比雪夫距離起源於國際象棋中國王的走法，國際象棋中國王每次只能往周圍的 8 格中走一步，那麼如果要從棋盤中 A 格 (x1,y1) 走到 B 格 (x2,y2) 最少需要走幾步？你會發現最少步數總是 max(|x2-x1|,|y2-y1|)步。有一種類似的一種距離度量方法叫切比雪夫距離。

切比雪夫距離就是當 p 趨向於無窮大時的閔氏距離：

閔氏距離的相關知識

距離函數並不一定是距離度量，當距離函數要作爲距離度量，需要滿足：由此可見，閔氏距離可以作爲距離度量，而大部分的相似度並不能作爲距離度量。

向量的範數可以簡單形象的理解爲向量的長度，或者向量到零點的距離，或者相應的兩個點之間的距離。

閔氏距離也是 Lp 範數（如 p==2 爲常用 L2 範數正則化）的一般化定義。下圖給出了一個 Lp 球（ ||X||p = 1 ）的形狀隨着 P 的減少的可視化圖：

距離度量隨着空間的維度 d 的不斷增加，計算量複雜也逐增，另外在高維空間下，在維度越高的情況下，任意樣本之間的距離越趨於相等（樣本間最大與最小歐氏距離之間的相對差距就趨近於 0），也就是維度災難的問題，如下式結論：

對於維度災難的問題，常用的有 PCA 方法進行降維計算。

假設各樣本有年齡、工資兩個變量，計算歐氏距離（p=2）的時候，(年齡 1 - 年齡 2)² 的值要遠小於 (工資 1 - 工資 2)² ，這意味着在不使用特徵縮放的情況下，距離會被工資變量（大的數值）主導, 特別當 p 越大，單一維度的差值對整體的影響就越大。因此，我們需要使用特徵縮放來將全部的數值統一到一個量級上來解決此問題。基本的解決方法可以對數據進行“標準化” 和“歸一化”。

另外可以使用馬氏距離（協方差距離），與歐式距離不同其考慮到各種特性之間的聯繫是（量綱）尺度無關 (Scale Invariant) 的，可以排除變量之間的相關性的干擾，缺點是誇大了變化微小的變量的作用。馬氏距離定義爲：

馬氏距離原理是使用矩陣對兩兩向量進行投影后，再通過常規的歐幾里得距離度量兩對象間的距離。當協方差矩陣爲單位矩陣，馬氏距離就簡化爲歐氏距離；如果協方差矩陣爲對角陣，其也可稱爲正規化的歐氏距離。

二、相似度（Similarity)

根據向量 x,y 的點積公式：

我們可以利用向量間夾角的 cos 值作爲向量相似度 [1]：餘弦相似度的取值範圍爲：-1~1，1 表示兩者完全正相關，-1 表示兩者完全負相關，0 表示兩者之間獨立。餘弦相似度與向量的長度無關，只與向量的方向有關，但餘弦相似度會受到向量平移的影響（上式如果將 x 平移到 x+1, 餘弦值就會改變）。

協方差是衡量多維數據集中，變量之間相關性的統計量。如下公式 X，Y 的協方差即是，X 減去其均值 乘以 Y 減去其均值，所得每一組數值的期望（平均值）。如果兩個變量之間的協方差爲正值，則這兩個變量之間存在正相關，若爲負值，則爲負相關。

皮爾遜相關係數數值範圍也是 [-1，1]。皮爾遜相關係數可看作是在餘弦相似度或協方差基礎上做了優化（變量的協方差除以標準差）。它消除每個分量標準不同（分數膨脹）的影響，具有平移不變性和尺度不變性。

卡方檢驗 X2，主要是比較兩個分類變量的關聯性、獨立性分析。如下公式，A 代表實際頻數；E 代表期望頻數：

三、字符串距離 (Distance of Strings)

Levenshtein 距離是 編輯距離 (Editor Distance) 的一種，指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數。允許的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。像 hallo 與 hello 兩個字符串編輯距離就是 1，我們通過替換”a“  爲 ”e“，就可以完成轉換。

漢明距離爲兩個等長字符串對應位置的不同字符的個數，也就是將一個字符串變換成另外一個字符串所需要替換的字符個數。例如：1011101 與 1001001 之間的漢明距離是 2，“toned” 與 “roses” 之間的漢明距離是 3

對於字符串距離來說，不同字符所佔的份量是不一樣的。比如”我樂了 “與【“我怒了”，” 我樂了啊” 】的 Levenshtein 距離都是 1，但其實兩者差異還是很大的，因爲像 “啊” 這種語氣詞的重要性明顯不如“樂”，考慮字符（特徵）權重的相似度方法有：TF-IDF、BM25、WMD 算法。

四、集合距離 (Distance of Sets)

Jaccard 取值範圍爲 0~1，0 表示兩個集合沒有重合，1 表示兩個集合完全重合。

但 Dice 不滿足距離函數的三角不等式，不是一個合適的距離度量。

五、信息論距離 (Information Theory measures)

基礎地介紹下，信息熵用來衡量一個隨機變量的不確定性程度。對於一個隨機變量 X，其概率分佈爲：

互信息用於衡量兩個變量之間的關聯程度，衡量了知道這兩個變量其中一個，對另一個不確定度減少的程度。公式爲：如下圖，條件熵表示已知隨機變量 X 的情況下，隨機變量 Y 的信息熵，因此互信息實際上也代表了已知隨機變量 X 的情況下，隨機變量 Y 的 (信息熵) 不確定性的減少程度。

JS 散度解決了 KL 散度不對稱的問題，定義爲：

羣體穩定性指標（Population Stability Index，PSI）， 可以看做是解決 KL 散度非對稱性的一個對稱性度量指標，用於度量分佈之間的差異（常用於風控領域的評估模型預測的穩定性）。

PSI 與 JS 散度的形式是非常類似的，如下公式：

PSI 的含義等同 P 與 Q，Q 與 P 之間的 KL 散度之和。

六、時間系列、圖結構的距離

DTW 距離用於衡量兩個序列之間的相似性，適用於不同長度、不同節奏的時間序列。DTW 採用了動態規劃 DP（dynamic programming）的方法來進行時間規整的計算，通過自動 warping 扭曲 時間序列（即在時間軸上進行局部的縮放），使得兩個序列的形態儘可能的一致，得到最大可能的相似度。(具體可參考 [5])

圖結構間的相似度計算，有圖同構、最大共同子圖、圖編輯距離、Graph Kernel 、圖嵌入計算距離等方法（具體可參考 [4][6]）。

七、度量學習 (Metric Learning)

度量學習的對象通常是樣本特徵向量的距離，度量學習的關鍵在於如何有效的度量樣本間的距離，目的是通過訓練和學習，減小或限制同類樣本之間的距離，同時增大不同類別樣本之間的距離，簡單歸類如下 [2]：

八、常用的度量方法彙總

最後，附上常用的距離和相似度度量方法 [3]：

_參考資料： _

[1] https://kexue.fm/archives/7388

_[2] https://zhuanlan.zhihu.com/p/80656461 _

_[3] https://www.pianshen.com/article/70261312162/ _

_[4] https://arxiv.org/pdf/2002.07420.pdf _

_[5] https://zhuanlan.zhihu.com/p/32849741 _

[6] https://github.com/ysig/GraKeL

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/AKx9N01-xlLgL2_oFa1KUg

猜你喜歡