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