漫谈：机器学习中距离和相似性度量方法
在機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中，我們經(jīng)常需要知道個(gè)體間差異的大小，進(jìn)而評(píng)價(jià)個(gè)體的相似性和類別。最常見的是數(shù)據(jù)分析中的相關(guān)分析，數(shù)據(jù)挖掘中的分類和聚類算法，如 K 最近鄰（KNN）和 K 均值（K-Means）等等。根據(jù)數(shù)據(jù)特性的不同，可以采用不同的度量方法。一般而言，定義一個(gè)距離函數(shù) d(x,y), 需要滿足下面幾個(gè)準(zhǔn)則：
1) d(x,x) = 0 ? ? ? ? ? ? ? ? ? ?// 到自己的距離為0
2) d(x,y) >= 0 ? ? ? ? ? ? ? ? ?// 距離非負(fù)
3) d(x,y) = d(y,x) ? ? ? ? ? ? ? ? ? // 對(duì)稱性: 如果 A 到 B 距離是 a，那么 B 到 A 的距離也應(yīng)該是 a
4) d(x,k)+ d(k,y) >= d(x,y) ? ?// 三角形法則: (兩邊之和大于第三邊)
這篇博客主要介紹機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘中一些常見的距離公式，包括：
?
1. 閔可夫斯基距離
閔可夫斯基距離（Minkowski distance）是衡量數(shù)值點(diǎn)之間距離的一種非常常見的方法，假設(shè)數(shù)值點(diǎn) P 和 Q 坐標(biāo)如下：
那么，閔可夫斯基距離定義為：
該距離最常用的 p 是 2 和 1, 前者是歐幾里得距離（Euclidean distance），后者是曼哈頓距離（Manhattan distance）。假設(shè)在曼哈頓街區(qū)乘坐出租車從 P 點(diǎn)到 Q 點(diǎn)，白色表示高樓大廈，灰色表示街道：
綠色的斜線表示歐幾里得距離，在現(xiàn)實(shí)中是不可能的。其他三條折線表示了曼哈頓距離，這三條折線的長(zhǎng)度是相等的。
當(dāng) p 趨近于無窮大時(shí)，閔可夫斯基距離轉(zhuǎn)化成切比雪夫距離（Chebyshev distance）：
我們知道平面上到原點(diǎn)歐幾里得距離（p = 2）為 1 的點(diǎn)所組成的形狀是一個(gè)圓，當(dāng) p 取其他數(shù)值的時(shí)候呢？
注意，當(dāng) p?<?1 時(shí)，閔可夫斯基距離不再符合三角形法則，舉個(gè)例子：當(dāng) p?<?1, (0,0) 到 (1,1) 的距離等于 (1+1)^{1/p}?>?2, 而 (0,1) 到這兩個(gè)點(diǎn)的距離都是 1。
閔可夫斯基距離比較直觀，但是它與數(shù)據(jù)的分布無關(guān)，具有一定的局限性，如果 x 方向的幅值遠(yuǎn)遠(yuǎn)大于 y 方向的值，這個(gè)距離公式就會(huì)過度放大 x 維度的作用。所以，在計(jì)算距離之前，我們可能還需要對(duì)數(shù)據(jù)進(jìn)行?z-transform?處理，即減去均值，除以標(biāo)準(zhǔn)差：
?: 該維度上的均值
?: 該維度上的標(biāo)準(zhǔn)差
可以看到，上述處理開始體現(xiàn)數(shù)據(jù)的統(tǒng)計(jì)特性了。這種方法在假設(shè)數(shù)據(jù)各個(gè)維度不相關(guān)的情況下利用數(shù)據(jù)分布的特性計(jì)算出不同的距離。如果維度相互之間數(shù)據(jù)相關(guān)（例如：身高較高的信息很有可能會(huì)帶來體重較重的信息，因?yàn)閮烧呤怯嘘P(guān)聯(lián)的），這時(shí)候就要用到馬氏距離（Mahalanobis distance）了。
?
2. 馬氏距離
考慮下面這張圖，橢圓表示等高線，從歐幾里得的距離來算，綠黑距離大于紅黑距離，但是從馬氏距離，結(jié)果恰好相反：
馬氏距離實(shí)際上是利用 Cholesky transformation 來消除不同維度之間的相關(guān)性和尺度不同的性質(zhì)。假設(shè)樣本點(diǎn)（列向量）之間的協(xié)方差對(duì)稱矩陣是??， 通過 Cholesky Decomposition（實(shí)際上是對(duì)稱矩陣 LU 分解的一種特殊形式，可參考之前的博客）可以轉(zhuǎn)化為下三角矩陣和上三角矩陣的乘積：??。消除不同維度之間的相關(guān)性和尺度不同，只需要對(duì)樣本點(diǎn) x 做如下處理：?。處理之后的歐幾里得距離就是原樣本的馬氏距離：為了書寫方便，這里求馬氏距離的平方）：
下圖藍(lán)色表示原樣本點(diǎn)的分布，兩顆紅星坐標(biāo)分別是（3, 3），（2, -2）:
由于 x， y 方向的尺度不同，不能單純用歐幾里得的方法測(cè)量它們到原點(diǎn)的距離。并且，由于 x 和 y 是相關(guān)的（大致可以看出斜向右上），也不能簡(jiǎn)單地在 x 和 y 方向上分別減去均值，除以標(biāo)準(zhǔn)差。最恰當(dāng)?shù)姆椒ㄊ菍?duì)原始數(shù)據(jù)進(jìn)行 Cholesky 變換，即求馬氏距離（可以看到，右邊的紅星離原點(diǎn)較近）：
將上面兩個(gè)圖的繪制代碼和求馬氏距離的代碼貼在這里，以備以后查閱：
?View Code?
馬氏距離的變換和 PCA 分解的白化處理頗有異曲同工之妙，不同之處在于：就二維來看，PCA 是將數(shù)據(jù)主成分旋轉(zhuǎn)到 x 軸（正交矩陣的酉變換），再在尺度上縮放（對(duì)角矩陣），實(shí)現(xiàn)尺度相同。而馬氏距離的 L逆矩陣是一個(gè)下三角，先在 x 和 y 方向進(jìn)行縮放，再在 y 方向進(jìn)行錯(cuò)切（想象矩形變平行四邊形），總體來說是一個(gè)沒有旋轉(zhuǎn)的仿射變換。
?
3. 向量?jī)?nèi)積
向量?jī)?nèi)積是線性代數(shù)里最為常見的計(jì)算，實(shí)際上它還是一種有效并且直觀的相似性測(cè)量手段。向量?jī)?nèi)積的定義如下：
直觀的解釋是：如果 x 高的地方 y 也比較高， x 低的地方 y 也比較低，那么整體的內(nèi)積是偏大的，也就是說 x 和 y 是相似的。舉個(gè)例子，在一段長(zhǎng)的序列信號(hào) A 中尋找哪一段與短序列信號(hào) a 最匹配，只需要將 a 從 A 信號(hào)開頭逐個(gè)向后平移，每次平移做一次內(nèi)積，內(nèi)積最大的相似度最大。信號(hào)處理中 DFT 和 DCT 也是基于這種內(nèi)積運(yùn)算計(jì)算出不同頻域內(nèi)的信號(hào)組分（DFT 和 DCT 是正交標(biāo)準(zhǔn)基，也可以看做投影）。向量和信號(hào)都是離散值，如果是連續(xù)的函數(shù)值，比如求區(qū)間[-1, 1]?兩個(gè)函數(shù)之間的相似度，同樣也可以得到（系數(shù)）組分，這種方法可以應(yīng)用于多項(xiàng)式逼近連續(xù)函數(shù)，也可以用到連續(xù)函數(shù)逼近離散樣本點(diǎn)（最小二乘問題，OLS coefficients）中，扯得有點(diǎn)遠(yuǎn)了- -!。
向量?jī)?nèi)積的結(jié)果是沒有界限的，一種解決辦法是除以長(zhǎng)度之后再求內(nèi)積，這就是應(yīng)用十分廣泛的余弦相似度（Cosine similarity）：
余弦相似度與向量的幅值無關(guān)，只與向量的方向相關(guān)，在文檔相似度（TF-IDF）和圖片相似性（histogram）計(jì)算上都有它的身影。需要注意一點(diǎn)的是，余弦相似度受到向量的平移影響，上式如果將 x 平移到 x+1, 余弦值就會(huì)改變。怎樣才能實(shí)現(xiàn)平移不變性？這就是下面要說的皮爾遜相關(guān)系數(shù)（Pearson correlation），有時(shí)候也直接叫相關(guān)系數(shù):
皮爾遜相關(guān)系數(shù)具有平移不變性和尺度不變性，計(jì)算出了兩個(gè)向量（維度）的相關(guān)性。不過，一般我們?cè)谡務(wù)撓嚓P(guān)系數(shù)的時(shí)候，將 x 與 y 對(duì)應(yīng)位置的兩個(gè)數(shù)值看作一個(gè)樣本點(diǎn)，皮爾遜系數(shù)用來表示這些樣本點(diǎn)分布的相關(guān)性。
由于皮爾遜系數(shù)具有的良好性質(zhì)，在各個(gè)領(lǐng)域都應(yīng)用廣泛，例如，在推薦系統(tǒng)根據(jù)為某一用戶查找喜好相似的用戶,進(jìn)而提供推薦，優(yōu)點(diǎn)是可以不受每個(gè)用戶評(píng)分標(biāo)準(zhǔn)不同和觀看影片數(shù)量不一樣的影響。
?
4. 分類數(shù)據(jù)點(diǎn)間的距離
漢明距離（Hamming distance）是指，兩個(gè)等長(zhǎng)字符串s1與s2之間的漢明距離定義為將其中一個(gè)變?yōu)榱硗庖粋€(gè)所需要作的最小替換次數(shù)。舉個(gè)維基百科上的例子：
還可以用簡(jiǎn)單的匹配系數(shù)來表示兩點(diǎn)之間的相似度——匹配字符數(shù)/總字符數(shù)。
在一些情況下，某些特定的值相等并不能代表什么。舉個(gè)例子，用 1 表示用戶看過該電影，用 0 表示用戶沒有看過，那么用戶看電影的的信息就可用 0,1 表示成一個(gè)序列。考慮到電影基數(shù)非常龐大，用戶看過的電影只占其中非常小的一部分，如果兩個(gè)用戶都沒有看過某一部電影（兩個(gè)都是 0），并不能說明兩者相似。反而言之，如果兩個(gè)用戶都看過某一部電影（序列中都是 1），則說明用戶有很大的相似度。在這個(gè)例子中，序列中等于 1 所占的權(quán)重應(yīng)該遠(yuǎn)遠(yuǎn)大于 0 的權(quán)重，這就引出下面要說的杰卡德相似系數(shù)（Jaccard similarity）。
在上面的例子中，用 M11 表示兩個(gè)用戶都看過的電影數(shù)目，M10 表示用戶 A 看過，用戶 B 沒看過的電影數(shù)目，M01 表示用戶 A 沒看過，用戶 B 看過的電影數(shù)目，M00 表示兩個(gè)用戶都沒有看過的電影數(shù)目。Jaccard 相似性系數(shù)可以表示為：
Jaccard similarity 還可以用集合的公式來表達(dá)，這里就不多說了。
如果分類數(shù)值點(diǎn)是用樹形結(jié)構(gòu)來表示的，它們的相似性可以用相同路徑的長(zhǎng)度來表示，比如，“/product/spot/ballgame/basketball” 離“product/spot/ballgame/soccer/shoes” 的距離小于到 "/product/luxury/handbags" 的距離，以為前者相同父節(jié)點(diǎn)路徑更長(zhǎng)。
?
5. 序列之間的距離
上一小節(jié)我們知道，漢明距離可以度量?jī)蓚€(gè)長(zhǎng)度相同的字符串之間的相似度，如果要比較兩個(gè)不同長(zhǎng)度的字符串，不僅要進(jìn)行替換，而且要進(jìn)行插入與刪除的運(yùn)算，在這種場(chǎng)合下，通常使用更加復(fù)雜的編輯距離（Edit distance, Levenshtein distance）等算法。編輯距離是指兩個(gè)字串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)字符，刪除一個(gè)字符。編輯距離求的是最少編輯次數(shù)，這是一個(gè)動(dòng)態(tài)規(guī)劃的問題，有興趣的同學(xué)可以自己研究研究。
時(shí)間序列是序列之間距離的另外一個(gè)例子。DTW 距離（Dynamic Time Warp）是序列信號(hào)在時(shí)間或者速度上不匹配的時(shí)候一種衡量相似度的方法。神馬意思？舉個(gè)例子，兩份原本一樣聲音樣本A、B都說了“你好”，A在時(shí)間上發(fā)生了扭曲，“你”這個(gè)音延長(zhǎng)了幾秒。最后A:“你~~~好”，B：“你好”。DTW正是這樣一種可以用來匹配A、B之間的最短距離的算法。
DTW 距離在保持信號(hào)先后順序的限制下對(duì)時(shí)間信號(hào)進(jìn)行“膨脹”或者“收縮”，找到最優(yōu)的匹配，與編輯距離相似，這其實(shí)也是一個(gè)動(dòng)態(tài)規(guī)劃的問題:
實(shí)現(xiàn)代碼（轉(zhuǎn)自?McKelvin's Blog?）:
?View Code?
6. 概率分布之間的距離
前面我們談?wù)摰亩际莾蓚€(gè)數(shù)值點(diǎn)之間的距離，實(shí)際上兩個(gè)概率分布之間的距離是可以測(cè)量的。在統(tǒng)計(jì)學(xué)里面經(jīng)常需要測(cè)量?jī)山M樣本分布之間的距離，進(jìn)而判斷出它們是否出自同一個(gè) population，常見的方法有卡方檢驗(yàn)（Chi-Square）和?KL 散度（ KL-Divergence），下面說一說 KL 散度吧。
先從信息熵說起，假設(shè)一篇文章的標(biāo)題叫做“黑洞到底吃什么”，包含詞語(yǔ)分別是 {黑洞, 到底, 吃什么}, 我們現(xiàn)在要根據(jù)一個(gè)詞語(yǔ)推測(cè)這篇文章的類別。哪個(gè)詞語(yǔ)給予我們的信息最多？很容易就知道是“黑洞”，因?yàn)椤昂诙础边@個(gè)詞語(yǔ)在所有的文檔中出現(xiàn)的概率太低啦，一旦出現(xiàn)，就表明這篇文章很可能是在講科普知識(shí)。而其他兩個(gè)詞語(yǔ)“到底”和“吃什么”出現(xiàn)的概率很高，給予我們的信息反而越少。如何用一個(gè)函數(shù) h(x) 表示詞語(yǔ)給予的信息量呢？第一，肯定是與 p(x) 相關(guān)，并且是負(fù)相關(guān)。第二，假設(shè) x 和 y 是獨(dú)立的（黑洞和宇宙不相互獨(dú)立，談到黑洞必然會(huì)說宇宙）,即 p(x,y) = p(x)p(y), 那么獲得的信息也是疊加的，即 h(x, y) = h(x) + h(y)。滿足這兩個(gè)條件的函數(shù)肯定是負(fù)對(duì)數(shù)形式：
對(duì)假設(shè)一個(gè)發(fā)送者要將隨機(jī)變量 X 產(chǎn)生的一長(zhǎng)串隨機(jī)值傳送給接收者， 接受者獲得的平均信息量就是求它的數(shù)學(xué)期望：
這就是熵的概念。另外一個(gè)重要特點(diǎn)是，熵的大小與字符平均最短編碼長(zhǎng)度是一樣的（shannon）。設(shè)有一個(gè)未知的分布 p(x), 而 q(x) 是我們所獲得的一個(gè)對(duì) p(x) 的近似，按照 q(x) 對(duì)該隨機(jī)變量的各個(gè)值進(jìn)行編碼，平均長(zhǎng)度比按照真實(shí)分布的 p(x) 進(jìn)行編碼要額外長(zhǎng)一些，多出來的長(zhǎng)度這就是 KL 散度（之所以不說距離，是因?yàn)椴粷M足對(duì)稱性和三角形法則），即：
KL 散度又叫相對(duì)熵（relative entropy）。了解機(jī)器學(xué)習(xí)的童鞋應(yīng)該都知道，在 Softmax 回歸（或者 Logistic 回歸），最后的輸出節(jié)點(diǎn)上的值表示這個(gè)樣本分到該類的概率，這就是一個(gè)概率分布。對(duì)于一個(gè)帶有標(biāo)簽的樣本，我們期望的概率分布是：分到標(biāo)簽類的概率是 1，?其他類概率是 0。但是理想很豐滿，現(xiàn)實(shí)很骨感，我們不可能得到完美的概率輸出，能做的就是盡量減小總樣本的 KL 散度之和（目標(biāo)函數(shù)）。這就是 Softmax 回歸或者 Logistic 回歸中 Cost function 的優(yōu)化過程啦。（PS：因?yàn)楦怕屎蜑?1，一般的 logistic 二分類的圖只畫了一個(gè)輸出節(jié)點(diǎn)，隱藏了另外一個(gè)）
?
?
待補(bǔ)充的方法：
卡方檢驗(yàn) Chi-Square
衡量 categorical attributes 相關(guān)性的 mutual information
Spearman's rank coefficient
Earth Mover's Distance
SimRank 迭代算法等。
?
參考資料：
?
from：http://www.cnblogs.com/daniel-D/總結(jié)
以上是生活随笔為你收集整理的漫谈：机器学习中距离和相似性度量方法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 逻辑回归Logistic Regress
- 下一篇： 机器学习中导数最优化方法(基础篇)