【機(jī)器學(xué)習(xí)】全面歸納距離和相似度方法(7種)

距離(distance，差異程度)、相似度(similarity，相似程度)方法可以看作是以某種的距離函數(shù)計算元素間的距離，這些方法作為機(jī)器學(xué)習(xí)的基礎(chǔ)概念，廣泛應(yīng)用于如：Kmeans聚類、協(xié)同過濾推薦算法、相似度算法、MSE損失函數(shù)、正則化范數(shù)等等。本文對常用的距離計算方法進(jìn)行歸納以及解析，分為以下幾類展開：

一、閔氏距離（Minkowski Distance）類

二、相似度（Similarity)

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

四、集合距離 (Distance of Sets)

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

六、時間系列、圖結(jié)構(gòu)的距離

七、度量學(xué)習(xí)(Metric Learning)

附、常用的度量方法匯總

一、閔氏距離（Distance）類

• 閔氏距離（Minkowski?Distance）

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

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

• 曼哈頓距離（Manhattan?Distance）VS? 歐幾里得距離（Euclidean?Distance）

曼哈頓距離 公式：

歐幾里得距離公式：

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

• 切比雪夫距離（Chebyshev?Distance）

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

切比雪夫距離就是當(dāng)p趨向于無窮大時的閔氏距離：

閔氏距離的相關(guān)知識

• 距離度量的定義

距離函數(shù)并不一定是距離度量，當(dāng)距離函數(shù)要作為距離度量，需要滿足：由此可見，閔氏距離可以作為距離度量，而大部分的相似度并不能作為距離度量。

• Lp范數(shù)

向量的范數(shù)可以簡單形象的理解為向量的長度，或者向量到零點的距離，或者相應(yīng)的兩個點之間的距離。

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

• 維度災(zāi)難的問題

距離度量隨著空間的維度d的不斷增加，計算量復(fù)雜也逐增，另外在高維空間下，在維度越高的情況下，任意樣本之間的距離越趨于相等（樣本間最大與最小歐氏距離之間的相對差距就趨近于0），也就是維度災(zāi)難的問題，如下式結(jié)論：

對于維度災(zāi)難的問題，常用的有PCA方法進(jìn)行降維計算。

• 量綱差異問題

假設(shè)各樣本有年齡、工資兩個變量，計算歐氏距離（p=2）的時候，(年齡1-年齡2)2 的值要遠(yuǎn)小于(工資1-工資2)2 ，這意味著在不使用特征縮放的情況下，距離會被工資變量（大的數(shù)值）主導(dǎo), 特別當(dāng)p越大，單一維度的差值對整體的影響就越大。因此，我們需要使用特征縮放來將全部的數(shù)值統(tǒng)一到一個量級上來解決此問題?；镜慕鉀Q方法可以對數(shù)據(jù)進(jìn)行“標(biāo)準(zhǔn)化”和“歸一化”。

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

馬氏距離原理是使用矩陣對兩兩向量進(jìn)行投影后，再通過常規(guī)的歐幾里得距離度量兩對象間的距離。當(dāng)協(xié)方差矩陣為單位矩陣，馬氏距離就簡化為歐氏距離；如果協(xié)方差矩陣為對角陣，其也可稱為正規(guī)化的歐氏距離。

二、相似度（Similarity)

• 余弦相似度 (Cosine Similarity)

根據(jù)向量x,y的點積公式：

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

• 協(xié)方差

協(xié)方差是衡量多維數(shù)據(jù)集中，變量之間相關(guān)性的統(tǒng)計量。如下公式X，Y的協(xié)方差即是，X減去其均值 乘以 Y減去其均值，所得每一組數(shù)值的期望（平均值）。如果兩個變量之間的協(xié)方差為正值，則這兩個變量之間存在正相關(guān)，若為負(fù)值，則為負(fù)相關(guān)。

• 皮爾遜相關(guān)系數(shù) (Pearson Correlation)

皮爾遜相關(guān)系數(shù)數(shù)值范圍也是[-1，1]。皮爾遜相關(guān)系數(shù)可看作是在余弦相似度或協(xié)方差基礎(chǔ)上做了優(yōu)化（變量的協(xié)方差除以標(biāo)準(zhǔn)差）。它消除每個分量標(biāo)準(zhǔn)不同（分?jǐn)?shù)膨脹）的影響，具有平移不變性和尺度不變性。

• 卡方檢驗

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

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

• Levenshtein 距離

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

• 漢明距離

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

• 帶權(quán)重的字符串距離

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

四、集合距離 (Distance of Sets)

• Jaccard 系數(shù)

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

• Dice 系數(shù)Dice 系數(shù)取值范圍為0~1，與Jaccard系數(shù)可以相互轉(zhuǎn)換。

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

• Tversky 系數(shù)Tversky 系數(shù)可以理解為 Jaccard 系數(shù)和 Dice 系數(shù)的一般化，當(dāng) ?α，β為1時為 Jaccard 系數(shù)，當(dāng) α，β為0.5時為 Dice 系數(shù)（X\Y表示集合的相對補(bǔ)集）。

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

基礎(chǔ)地介紹下，信息熵用來衡量一個隨機(jī)變量的不確定性程度。對于一個隨機(jī)變量 X，其概率分布為：

• 互信息

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

• 相對熵 (Relative Entropy) 相對熵又稱之為 KL 散度 (Kullback-Leibler Divergence)，用于衡量兩個分布P、Q（注：KL具有不對稱）之間的差異，定義為：

• JS 散度 (Jensen-Shannon Divergence)

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

• PSI

群體穩(wěn)定性指標(biāo)（Population Stability Index，PSI）， 可以看做是解決KL散度非對稱性的一個對稱性度量指標(biāo)，用于度量分布之間的差異（常用于風(fēng)控領(lǐng)域的評估模型預(yù)測的穩(wěn)定性）。

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

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

• 交叉熵交叉熵常作為機(jī)器學(xué)習(xí)中的分類的損失函數(shù)，用于衡量模型預(yù)測分布和實際數(shù)據(jù)分布之間的差異性。

六、時間系列、圖結(jié)構(gòu)的距離

• DTW (Dynamic Time Warping) 距離

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

• 圖結(jié)構(gòu)的距離

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

七、度量學(xué)習(xí)(Metric Learning)

度量學(xué)習(xí)的對象通常是樣本特征向量的距離，度量學(xué)習(xí)的關(guān)鍵在于如何有效的度量樣本間的距離，目的是通過訓(xùn)練和學(xué)習(xí)，減小或限制同類樣本之間的距離，同時增大不同類別樣本之間的距離，簡單歸類如下[2]：

• 基于降維的度量學(xué)習(xí)算法是學(xué)習(xí)一個到低維的映射矩陣，使得映射后的樣本具有某些性質(zhì)。包括無監(jiān)督的PCA、有監(jiān)督的LDA和ANMM。
• 基于Centroids的度量學(xué)習(xí)算法，即通過類中心進(jìn)行分類的算法，而不是基于最近鄰。
• 基于信息論推導(dǎo)的一些距離度量學(xué)習(xí)算法，比如ITML和MCML等通常是使用距離度量矩陣定義一個分布，然后推導(dǎo)出最小化兩個分布的KL距離或者Jeffery距離等等。
• 基于深度度量學(xué)習(xí)：利用深度網(wǎng)絡(luò)學(xué)習(xí)一個表示（Embedding），采用各種采樣方法（Sampling），比如成對/三元組訓(xùn)練樣本（Triplet），計算一個帶有Margin/最近鄰等分類或聚類算法的損失。

八、常用的度量方法匯總

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