機器學(xué)習(xí)中距離和相似性度量方法

1、在機器學(xué)習(xí)和數(shù)據(jù)挖掘中，我們經(jīng)常需要知道個體間差異的大小，進而評價個體 的相似性和類別。最常見的是數(shù)據(jù)分析中的相關(guān)分析，數(shù)據(jù)挖掘中的分類和聚 類算法，如K最近鄰(KNN)和K均值(K-Means)等等。根據(jù)數(shù)據(jù)特性的不同，可以采用不同的度量方法。一般而言，定義一個距離函數(shù) d(x,y),需要滿足下面幾個準(zhǔn)則：1) d(x,x) = 0/到自己的距離為02) d(x,y) = 0/ 距離非負(fù)3) d(x,y) = d(y,x)/對稱性：如果 A至U B距離是a,那么B到A的距離也應(yīng)該是a4) d(x,k)+ d(k,y) = d(x,y) /三角形法則：(兩邊之和大于第三邊)這篇博客主要介紹機器

2、學(xué)習(xí)和數(shù)據(jù)挖掘中一些常見的距離公式，包括:1 .閔可夫斯基距離2 .歐幾里得距離3 .曼哈頓距離4 .切比雪夫距離5 .馬氏距離6 .余弦相似度7 .皮爾遜相關(guān)系數(shù)8 .漢明距離9 .杰卡德相似系數(shù)10 .編輯距離11 . DTW距離12 . KL散度1 .閔可夫斯基距離閔可夫斯基距離(Minkowski distance )是衡量數(shù)值點之間距離的一種非常常見的方法，假設(shè)數(shù)值點 P和Q坐標(biāo)如下：P =（雹入1方7重刀and Q =（如,眥） Rn那么，閔可夫斯基距離定義為:1/?該距離最常用的p是2和1,前者是歐幾里得距離(Euclidean distance),后者是曼哈頓距離(Manhat

3、tan distance )。假設(shè)在曼哈頓街區(qū)乘坐出租車從P點到Q點，白色表示高樓大廈，灰色表示街道：綠色的斜線表示歐幾里得距離，在現(xiàn)實中是不可能的。其他三條折線表示了曼哈頓距離，這三條折線的長度是相等的。當(dāng)p趨近于無窮大時，閔可夫斯基距離轉(zhuǎn)化成 切比雪夫距離（Chebyshevdistance）:我們知道平面上到原點歐幾里得距離（p = 2）為1的點所組成的形狀是一個圓,當(dāng)p取其他數(shù)值的時候呢？注意，當(dāng)p 1時，閔可夫斯基距離不再符合三角形法則，舉個例子：當(dāng)p 2,而（0,1）到這兩個點的距離都是1。閔可夫斯基距離比較直觀，但是它與數(shù)據(jù)的分布無關(guān)，具有一定的局限性，如果x方向的幅值遠遠大于y

4、方向的值，這個距離公式就會過度放大x維度的作用。所以，在計算距離之前，我們可能還需要對數(shù)據(jù)進行z-transform 處理，即減去均值，除以標(biāo)準(zhǔn)差：產(chǎn)1 一口工協(xié)一口八（徹 i 敢）T （-）M：該維度上的均值。：該維度上的標(biāo)準(zhǔn)差可以看到，上述處理開始體現(xiàn)數(shù)據(jù)的統(tǒng)計特性了。這種方法在假設(shè)數(shù)據(jù)各個維度不相關(guān)的情況下利用數(shù)據(jù)分布的特性計算出不同的距離。 如果維度相互之間數(shù)據(jù) 相關(guān)(例如：身高較高的信息很有可能會帶來體重較重的信息， 因為兩者是有關(guān) 聯(lián)的)，這時候就要用到 馬氏距離(Mahalanobis distance) 了。2 .馬氏距離考慮下面這張圖，橢圓表示等高線，從歐幾里得的距離來算，綠

5、黑距離大于紅黑 距離，但是從馬氏距離，結(jié)果恰好相反：Y八distance (red, black) disUnce(greenF black) X馬氏距離實際上是利用 Cholesky transformation來消除不同維度之間的相關(guān)性 和尺度不同的性質(zhì)。假設(shè)樣本點(列向量)之間的協(xié)方差對稱矩陣是 ,通過Cholesky Decomposition (實際上是對稱矩陣 LU分解的一種特殊形式，可參考 之前的援笈)可以轉(zhuǎn)化為下三角矩陣和上三角矩陣的乘積： = LLT 0消除不同維度之間的相關(guān)性和尺度不同，只需要對樣本點x做如下處理：；=-1(一,力。處理之后的歐幾里得距離就是原樣本的馬氏距離

6、：為了書寫方便，這里求馬氏距離的平方)：= (L1(x-p)T(L1(x-ij)(x -(j)T (LL7)1 (x - p)T -1二切工(X . P)下圖藍色表示原樣本點的分布，兩顆紅星坐標(biāo)分別是(3, 3) , (2,-2)由于x, y方向的尺度不同，不能單純用歐幾里得的方法測量它們到原點的距 離。并且，由于x和y是相關(guān)的(大致可以看出斜向右上)，也不能簡單地在 x和y方向上分別減去均值，除以標(biāo)準(zhǔn)差。最恰當(dāng)?shù)姆椒ㄊ菍υ紨?shù)據(jù)進行Cholesky變換，即求馬氏距離(可以看到，右邊的紅星離原點較近)：將上面兩個圖的繪制代碼和求馬氏距離的代碼貼在這里，以備以后查閱:View Code馬氏距離的

7、變換和 PCA分解的白化處理頗有異曲同工之妙.不同之處在于：就 二維來看，PCA是將數(shù)據(jù)主成分旋轉(zhuǎn)到x軸（正交矩陣的酉變換），再在尺度 上縮放（對角矩陣），實現(xiàn)尺度相同。而馬氏距離的L逆矩陣是一個下三角，總體來說是一個仿射變換。3 .向量內(nèi)積向量內(nèi)積是線性代數(shù)里最為常見的計算，實際上它還是一種有效并且直觀的相似性測量手段。向量內(nèi)積的定義如下：直觀的解釋是：如果x高的地方y(tǒng)也比較高，x低的地方y(tǒng)也比較低，那么 整體的內(nèi)積是偏大的，也就是說 x和y是相似的。舉個例子，在一段長的序列 信號A中尋找哪一段與短序列信號 a最匹配，只需要將a從A信號開頭逐 個向后平移，每次平移做一次內(nèi)積，內(nèi)積最大的相似度

8、最大。信號處理中DFT和 DCT也是基于這種內(nèi)積運算計算出不同頻域內(nèi)的信號組分（DFT和DCT是正交標(biāo)準(zhǔn)基，也可以看做投影）。向量和信號都是離散值，如果是連續(xù)的函數(shù)值， 比如求區(qū)間-1,1兩個函數(shù)之間的相似度，同樣也可以得到（系數(shù)）組分，這 種方法可以應(yīng)用于多項式逼近連續(xù)函數(shù)，也可以用到連續(xù)函數(shù)逼近離散樣本點（最小二乘問題，OLS coefficients ）中，扯得有點遠了 -!。向量內(nèi)積的結(jié)果是沒有界限的，一種解決辦法是除以長度之后再求內(nèi)積，這就是應(yīng)用十分廣泛的 余弦相似度（Cosine similarity）：余弦相似度與向量的幅值無關(guān)，只與向量的方向相關(guān)，在文檔相似度（TF-JDF）和

9、圖片相似性（histogram ）計算上都有它的身影。需要注意一點的是，余弦相 似度受到向量的平移影響，上式如果將x平移到x+1,余弦值就會改變。怎樣才能實現(xiàn)平移不變性？這就是下面要說的皮爾遜相關(guān)系數(shù)（Pearson correlation ）,有時候也直接叫 相關(guān)系數(shù)：皮爾遜相關(guān)系數(shù)具有平移不變性和尺度不變性，計算出了兩個向量(維度)的相 關(guān)性。不過，一般我們在談?wù)撓嚓P(guān)系數(shù)的時候，將 x與y對應(yīng)位置的兩個數(shù)值 看作一個樣本點，皮爾遜系數(shù)用來表示這些樣本點分布的相關(guān)性。由于皮爾遜系數(shù)具有的良好性質(zhì)， 在各個領(lǐng)域都應(yīng)用廣泛，例如，在推薦系統(tǒng)根 據(jù)為某一用戶查找喜好相似的用戶，進而提供推薦,優(yōu)點是

10、可以不受每個用戶評 分標(biāo)準(zhǔn)不同和觀看影片數(shù)量不一樣的影響。4 .分類數(shù)據(jù)點間的距離漢明距離(Hamming distance )是指，兩個等長字符串si與s2之間的漢明距離定義為將其中一個變?yōu)榱硗庖粋€所需要作的最小替換次數(shù)。舉個維基百科上的例子： 10111011001001之間的漢明距離是2.2143896與2233796之間的漢明距離是工 toned與roses之間的漢明距離是3還可以用簡單的 匹配系數(shù)來表示兩點之間的相似度 匹配字符數(shù)/總字符數(shù) 在一些情況下，某些特定的值相等并不能代表什么。舉個例子，用 1表示用戶看過該電影，用0表示用戶沒有看過，那么用戶看電影的的信息就可用0,1表示成

11、一個序列?？紤]到電影基數(shù)非常龐大，用戶看過的電影只占其中非常小的一部分，如果兩個用戶都沒有看過某一部電影（兩個都是0）,并不能說明兩者相似。反而言之，如果兩個用戶都看過某一部電影（序列中都是 1）,則說明用戶有很大的相似度。在這個例子中，序列中等于1所占的權(quán)重應(yīng)Ig遠遠大于 0的 權(quán)重，這就引出下面要說的 杰卡彳惠相似系數(shù)（Jaccard similarity）。在上面的例子中，用 M11表示兩個用戶都看過的電影數(shù)目，M10表示用戶A看過，用戶B沒看過的電影數(shù)目，M01表示用戶A沒看過，用戶B看過的電影數(shù)目，M00表示兩個用戶都沒有看過的電影數(shù)目。Jaccard相似性系數(shù)可以 表小為：Afoi

12、 + A/io + AfiiJaccard similarity還可以用集合的公式來表達，這里就不多說了。如果分類數(shù)值點是用樹形結(jié)構(gòu)來表示的，它們的相似性可以用相同路徑的長度來表示，比如，7product/spot/ballgame /basketball ”離product/spot/ballgame/soccer/shoes ” 的距離小于到/product/luxury/handbags的距離，以為前者相同父節(jié)點路徑更長。5 .序列之間的距離上一小節(jié)我們知道，漢明距離可以度量兩個長度相同的字符串之間的相似度，如果要比較兩個不同長度的字符串，不僅要進行替換，而且要進行插入與刪除的運 算，在

13、這種場合下，通常使用更加復(fù)雜的 編輯距離(Edit distance, Levenshtein distance)等算法。編輯距離是指兩個字用之間，由一個轉(zhuǎn)成另一個所需的最少 編輯操作次數(shù)。許可的編輯操作包括將一個字符替換成另一個字符，插入一 個 字符，刪除一個字符。編輯距離求的是最少編輯次數(shù)，這是一個動態(tài)規(guī)劃的問題， 有興趣的同學(xué)可以自己研究研究。時間序列是序列之間距離的另外一個例子。 DTW 距離(Dynamic Time Warp) 是序列信號在時間或者速度上不匹配的時候一種衡量相似度的方法。 神馬意思？ 舉個例子，兩份原本一樣聲音樣本 A、B都說了 “你好” A在時間上發(fā)生了扭曲，“你

14、”這個音延長了幾秒。最后A: “你好”，B: “你好” DTW正是這樣一種可以 用來匹配A、B之間的最短距離的算法。DTW距離在保持信號先后順序的限制下對時間信號進行“膨脹”或者“收縮”找到 最優(yōu)的匹配，與編輯距離相似，這其實也是一個動態(tài)規(guī)劃的問題：今天天靠好好啊韓阻今今今爭爭天天標(biāo)最策真標(biāo)好好好好鞭啊實現(xiàn)代碼（轉(zhuǎn)自McKelvins Blog ）View Code6 .概率分布之間的距離前面我們談?wù)摰亩际莾蓚€數(shù)值點之間的距離，實際上兩個概率分布之間的距離是可以測量的。在統(tǒng)計學(xué)里面經(jīng)常需要測量兩組樣本分布之間的距離，進而判斷出 它們是否出自同一個 population ,常見的方法有 卡方檢驗

15、(Chi-Square )和KL散 度(KL-Divergence),下面說一說 KL散度吧。先從信息嫡說起，假設(shè)一篇文章的標(biāo)題叫做“黑洞到底吃什么”，包含詞語分別是黑洞，到底，吃什么,我們現(xiàn)在要根據(jù)一個詞語推測這篇文章的類別。 哪個詞語 給予我們的信息最多？很容易就知道是“黑洞”,因為“黑洞”這個詞語在所有的文 檔中出現(xiàn)的概率太低 啦，一旦出現(xiàn)，就表明這篇文章很可能是在講科普知識。而其他兩個詞語“到底”和“吃什么”出現(xiàn)的概率很高，給予我們的信息反而越少。如何用一個函數(shù)h(x)表示詞語給予的信息量呢？第一，肯定是與p(x)相關(guān)，并且是負(fù)相關(guān)。第二，假設(shè)x和y是獨立的(黑洞和宇宙不相互獨立，談到

16、黑 洞必然會說宇宙)，即p(x,y) = p(x)p(y),那么獲得的信息也是疊加的，即h(x, y)= h(x) + h(y)。滿足這兩個條件的函數(shù)肯定是負(fù)對數(shù)形式：對假設(shè)一個發(fā)送者要將隨機變量 X產(chǎn)生的一長串隨機值傳送給接收者，接受者獲得的平均信息量就是求它的數(shù)學(xué)期望：Hx = (貨)lnp(z)這就是嫡的概念。另外一個重要特點是，嫡的大小與字符平均最短編碼長度是一樣的(shannon)。設(shè)有一個未知的分布 p(x),而q(x)是我們所獲得的一個對 p(x)的近似，按照q(x)對該隨機變量的各個值進行編碼，平均長度比按照真實分布的p(x)進行編碼要額外長一些，多出來的長度這就是 KL散度(之所以不說距離，是因為不滿足對稱性和三角形法則)，即：KL(plk)I In g(x) dx(/ p(x) lnp(x) dx=-/小)】“鬻待補充的方法：卡方檢驗Chi-Square衡量 categorical attributes 相關(guān)性的 mutual informationSpearmans rank coefficient二