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         &#

2、160;        / 距離非負(fù)3) d(x,y) = d(y,x)                   / 對稱性: 如果 A 到 B 距離是 a，那么 B 到 A 的距離也應(yīng)該是 a4) d(x,k)+ d(k,y) >= d(x,y)    / 三角形法則: (兩邊之和大于第三邊)這篇博客主要介紹機器學(xué)習(xí)和數(shù)據(jù)挖掘中一些常見的距離公式，包括：1. 閔可夫斯基距離2. 歐幾里得距離3. 曼哈頓距離4. 切比雪夫距離5. 馬氏距離6.

3、 余弦相似度7. 皮爾遜相關(guān)系數(shù)8. 漢明距離9. 杰卡德相似系數(shù)10. 編輯距離11. DTW 距離12. KL 散度 1. 閔可夫斯基距離閔可夫斯基距離（Minkowski distance）是衡量數(shù)值點之間距離的一種非常常見的方法，假設(shè)數(shù)值點 P 和 Q 坐標(biāo)如下：那么，閔可夫斯基距離定義為：該距離最常用的 p 是 2 和 1, 前者是歐幾里得距離（Euclidean distance），后者是曼哈頓距離（Manhattan distance）。假設(shè)在曼哈頓街區(qū)乘坐出租車從 P 點到 Q 點，白色表示高樓大廈，灰色表示街道：綠色的斜線表示歐幾里得距離，在現(xiàn)實中是不可能的。其他三

4、條折線表示了曼哈頓距離，這三條折線的長度是相等的。當(dāng) p 趨近于無窮大時，閔可夫斯基距離轉(zhuǎn)化成切比雪夫距離（Chebyshev distance）：我們知道平面上到原點歐幾里得距離（p = 2）為 1 的點所組成的形狀是一個圓，當(dāng) p 取其他數(shù)值的時候呢？注意，當(dāng) p < 1 時，閔可夫斯基距離不再符合三角形法則，舉個例子：當(dāng) p < 1, (0,0) 到 (1,1) 的距離等于 (1+1)1/p > 2, 而 (0,1) 到這兩個點的距離都是 1。閔可夫斯基距離比較直觀，但是它與數(shù)據(jù)的分布無關(guān)，具有一定的局限性，如

5、果 x 方向的幅值遠遠大于 y 方向的值，這個距離公式就會過度放大 x 維度的作用。所以，在計算距離之前，我們可能還需要對數(shù)據(jù)進行 z-transform 處理，即減去均值，除以標(biāo)準(zhǔn)差： : 該維度上的均值 : 該維度上的標(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. 馬氏距離考慮下面這張圖，橢

6、圓表示等高線，從歐幾里得的距離來算，綠黑距離大于紅黑距離，但是從馬氏距離，結(jié)果恰好相反：馬氏距離實際上是利用 Cholesky transformation 來消除不同維度之間的相關(guān)性和尺度不同的性質(zhì)。假設(shè)樣本點（列向量）之間的協(xié)方差對稱矩陣是  ， 通過 Cholesky Decomposition（實際上是對稱矩陣 LU 分解的一種特殊形式，可參考之前的博客）可以轉(zhuǎn)化為下三角矩陣和上三角矩陣的乘積：  。消除不同維度之間的相關(guān)性和尺度不同，只需要對樣本點 x 做如下處理： 。處理之后的歐幾里得距離就是原樣本的馬氏距離：為了書寫方便，這里求馬

7、氏距離的平方）：下圖藍色表示原樣本點的分布，兩顆紅星坐標(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  馬氏距離的變換和 PCA 分解的白化處理頗有異曲同工之妙，不同之處在于：就二維來看，PCA 是將數(shù)據(jù)主成分旋轉(zhuǎn)到

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

9、算計算出不同頻域內(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-IDF）和圖片相似性（histogram）計算

10、上都有它的身影。需要注意一點的是，余弦相似度受到向量的平移影響，上式如果將 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)點是可以不受每個用戶評分標(biāo)準(zhǔn)不同和觀看影片

11、數(shù)量不一樣的影響。 4. 分類數(shù)據(jù)點間的距離漢明距離（Hamming distance）是指，兩個等長字符串s1與s2之間的漢明距離定義為將其中一個變?yōu)榱硗庖粋€所需要作的最小替換次數(shù)。舉個維基百科上的例子：還可以用簡單的匹配系數(shù)來表示兩點之間的相似度匹配字符數(shù)/總字符數(shù)。在一些情況下，某些特定的值相等并不能代表什么。舉個例子，用 1 表示用戶看過該電影，用 0 表示用戶沒有看過，那么用戶看電影的的信息就可用 0,1 表示成一個序列。考慮到電影基數(shù)非常龐大，用戶看過的電影只占其中非常小的一部分，如果兩個用戶都沒有看過某一部電影（兩個都是 0），并不能說明兩者相似。反而言之，如果兩個用戶

12、都看過某一部電影（序列中都是 1），則說明用戶有很大的相似度。在這個例子中，序列中等于 1 所占的權(quán)重應(yīng)該遠遠大于 0 的權(quán)重，這就引出下面要說的杰卡德相似系數(shù)（Jaccard similarity）。在上面的例子中，用 M11 表示兩個用戶都看過的電影數(shù)目，M10 表示用戶 A 看過，用戶 B 沒看過的電影數(shù)目，M01 表示用戶 A 沒看過，用戶 B 看過的電影數(shù)目，M00 表示兩個用戶都沒有看過的電影數(shù)目。Jaccard 相似性系數(shù)可以表示為：Jaccard similarity 還可以用集合的公式來表達，這里就不多說了。如果分類數(shù)值點是用樹形結(jié)構(gòu)來表示的，它們的相似性可以用相同路徑的長度

13、來表示，比如，“/product/spot/ballgame /basketball” 離“product/spot/ballgame/soccer/shoes” 的距離小于到 "/product/luxury/handbags" 的距離，以為前者相同父節(jié)點路徑更長。 5. 序列之間的距離上一小節(jié)我們知道，漢明距離可以度量兩個長度相同的字符串之間的相似度，如果要比較兩個不同長度的字符串，不僅要進行替換，而且要進行插入與刪除的運算，在這種場合下，通常使用更加復(fù)雜的編輯距離（Edit distance, Levenshtein distance）等算法。編輯距離是指兩

14、個字串之間，由一個轉(zhuǎn)成另一個所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個字符替換成另一個字符，插入一 個字符，刪除一個字符。編輯距離求的是最少編輯次數(shù)，這是一個動態(tài)規(guī)劃的問題，有興趣的同學(xué)可以自己研究研究。時間序列是序列之間距離的另外一個例子。DTW 距離（Dynamic Time Warp）是序列信號在時間或者速度上不匹配的時候一種衡量相似度的方法。神馬意思？舉個例子，兩份原本一樣聲音樣本A、B都說了“你好”，A在時間上發(fā)生了扭曲，“你”這個音延長了幾秒。最后A:“你好”，B：“你好”。DTW正是這樣一種可以用來匹配A、B之間的最短距離的算法。DTW 距離在保持信號先后順序的限制下對時間

15、信號進行“膨脹”或者“收縮”，找到最優(yōu)的匹配，與編輯距離相似，這其實也是一個動態(tài)規(guī)劃的問題:實現(xiàn)代碼（轉(zhuǎn)自 McKelvin's Blog ）:View Code  6. 概率分布之間的距離前面我們談?wù)摰亩际莾蓚€數(shù)值點之間的距離，實際上兩個概率分布之間的距離是可以測量的。在統(tǒng)計學(xué)里面經(jīng)常需要測量兩組樣本分布之間的距離，進而判斷出它們是否出自同一個 population，常見的方法有卡方檢驗（Chi-Square）和 KL 散度（ KL-Divergence），下面說一說 KL 散度吧。先從信息熵說起，假設(shè)一篇文章的標(biāo)題叫做“黑洞到底吃什么”，包含

16、詞語分別是 黑洞, 到底, 吃什么, 我們現(xiàn)在要根據(jù)一個詞語推測這篇文章的類別。哪個詞語給予我們的信息最多？很容易就知道是“黑洞”，因為“黑洞”這個詞語在所有的文檔中出現(xiàn)的概率太低 啦，一旦出現(xiàn)，就表明這篇文章很可能是在講科普知識。而其他兩個詞語“到底”和“吃什么”出現(xiàn)的概率很高，給予我們的信息反而越少。如何用一個函數(shù) h(x) 表示詞語給予的信息量呢？第一，肯定是與 p(x) 相關(guān)，并且是負(fù)相關(guān)。第二，假設(shè) x 和 y 是獨立的（黑洞和宇宙不相互獨立，談到黑洞必然會說宇宙）,即 p(x,y) = p(x)p(y), 那么獲得的信息也是疊加的，即 h(x, y) = h(x) + h(y)。滿

17、足這兩個條件的函數(shù)肯定是負(fù)對數(shù)形式：對假設(shè)一個發(fā)送者要將隨機變量 X 產(chǎn)生的一長串隨機值傳送給接收者， 接受者獲得的平均信息量就是求它的數(shù)學(xué)期望：這就是熵的概念。另外一個重要特點是，熵的大小與字符平均最短編碼長度是一樣的（shannon）。設(shè)有一個未知的分布 p(x), 而 q(x) 是我們所獲得的一個對 p(x) 的近似，按照 q(x) 對該隨機變量的各個值進行編碼，平均長度比按照真實分布的 p(x) 進行編碼要額外長一些，多出來的長度這就是 KL 散度（之所以不說距離，是因為不滿足對稱性和三角形法則），即：   待補充的方法：卡方檢驗 Chi-Square衡量 categorical attributes 相關(guān)性的 mutual informationSpearman's rank coefficien