轉載自:http://blog.csdn.net/leonis_v/article/details/50531820
在機器學習和資料挖掘中,我們經常需要知道個體間差異的大小,進而評價個體的相似性和類别。最常見的是資料分析中的相關分析,資料挖掘中的分類和聚類算法,如 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. 闵可夫斯基距離
闵可夫斯基距離(Minkowski distance)是衡量數值點之間距離的一種非常常見的方法,假設數值點 P 和 Q 坐标如下:
那麼,闵可夫斯基距離定義為:
該距離最常用的 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. 馬氏距離
考慮下面這張圖,橢圓表示等高線,從歐幾裡得的距離來算,綠黑距離大于紅黑距離,但是從馬氏距離,結果恰好相反:
馬氏距離實際上是利用 Cholesky transformation 來消除不同次元之間的相關性和尺度不同的性質。假設樣本點(列向量)之間的協方差對稱矩陣是
, 通過 Cholesky Decomposition(實際上是對稱矩陣 LU 分解的一種特殊形式,可參考之前的部落格)可以轉化為下三角矩陣和上三角矩陣的乘積:
。消除不同次元之間的相關性和尺度不同,隻需要對樣本點 x 做如下處理:
。處理之後的歐幾裡得距離就是原樣本的馬氏距離:為了書寫友善,這裡求馬氏距離的平方):
下圖藍色表示原樣本點的分布,兩顆紅星坐标分别是(3, 3),(2, -2):
由于 x, y 方向的尺度不同,不能單純用歐幾裡得的方法測量它們到原點的距離。并且,由于 x 和 y 是相關的(大緻可以看出斜向右上),也不能簡單地在 x 和 y 方向上分别減去均值,除以标準差。最恰當的方法是對原始資料進行 Cholesky 變換,即求馬氏距離(可以看到,右邊的紅星離原點較近):
将上面兩個圖的繪制代碼和求馬氏距離的代碼貼在這裡,以備以後查閱:
[java] view plain copy
- # -*- coding=utf-8 -*-
- # code related at: http://www.cnblogs.com/daniel-D/
- import numpy as np
- import pylab as pl
- import scipy.spatial.distance as dist
- def plotSamples(x, y, z=None):
- stars = np.matrix([[3., -2., 0.], [3., 2., 0.]])
- if z is not None:
- x, y = z * np.matrix([x, y])
- stars = z * stars
- pl.scatter(x, y, s=10) # 畫 gaussian 随機點
- pl.scatter(np.array(stars[0]), np.array(stars[1]), s=200, marker='*', color='r') # 畫三個指定點
- pl.axhline(linewidth=2, color='g') # 畫 x 軸
- pl.axvline(linewidth=2, color='g') # 畫 y 軸
- pl.axis('equal')
- pl.axis([-5, 5, -5, 5])
- pl.show()
- # 産生高斯分布的随機點
- mean = [0, 0] # 平均值
- cov = [[2, 1], [1, 2]] # 協方差
- x, y = np.random.multivariate_normal(mean, cov, 1000).T
- plotSamples(x, y)
- covMat = np.matrix(np.cov(x, y)) # 求 x 與 y 的協方差矩陣
- Z = np.linalg.cholesky(covMat).I # 仿射矩陣
- plotSamples(x, y, Z)
- # 求馬氏距離
- print '\n到原點的馬氏距離分别是:'
- print dist.mahalanobis([0,0], [3,3], covMat.I), dist.mahalanobis([0,0], [-2,2], covMat.I)
- # 求變換後的歐幾裡得距離
- dots = (Z * np.matrix([[3, -2, 0], [3, 2, 0]])).T
- print '\n變換後到原點的歐幾裡得距離分别是:'
- print dist.minkowski([0, 0], np.array(dots[0]), 2), dist.minkowski([0, 0], np.array(dots[1]), 2)
馬氏距離的變換和 PCA 分解的 白化處理 頗有異曲同工之妙,不同之處在于:就二維來看,PCA 是将資料主成分旋轉到 x 軸(正交矩陣的酉變換),再在尺度上縮放(對角矩陣),實作尺度相同。而馬氏距離的 L逆矩陣是一個下三角,先在 x 和 y 方向進行縮放,再在 y 方向進行錯切(想象矩形變平行四邊形),總體來說是一個沒有旋轉的仿射變換。
3. 向量内積
向量内積是線性代數裡最為常見的計算,實際上它還是一種有效并且直覺的相似性測量手段。向量内積的定義如下:
直覺的解釋是:如果 x 高的地方 y 也比較高, x 低的地方 y 也比較低,那麼整體的内積是偏大的,也就是說 x 和 y 是相似的。舉個例子,在一段長的序列信号 A 中尋找哪一段與短序列信号 a 最比對,隻需要将 a 從 A 信号開頭逐個向後平移,每次平移做一次内積,内積最大的相似度最大。信号進行中 DFT 和 DCT 也是基于這種内積運算計算出不同頻域内的信号組分(DFT 和 DCT 是正交标準基,也可以看做投影)。向量和信号都是離散值,如果是連續的函數值,比如求區間
[-1, 1]
兩個函數之間的相似度,同樣也可以得到(系數)組分,這種方法可以應用于多項式逼近連續函數,也可以用到連續函數逼近離散樣本點(最小二乘問題,OLS coefficients)中,扯得有點遠了- -!。
向量内積的結果是沒有界限的,一種解決辦法是除以長度之後再求内積,這就是應用十分廣泛的餘弦相似度(Cosine similarity):
餘弦相似度與向量的幅值無關,隻與向量的方向相關,在文檔相似度(TF-IDF)和圖檔相似性(histogram)計算上都有它的身影。需要注意一點的是,餘弦相似度受到向量的平移影響,上式如果将 x 平移到 x+1, 餘弦值就會改變。怎樣才能實作平移不變性?這就是下面要說的皮爾遜相關系數(Pearson correlation),有時候也直接叫相關系數:
皮爾遜相關系數具有平移不變性和尺度不變性,計算出了兩個向量(次元)的相關性。不過,一般我們在談論相關系數的時候,将 x 與 y 對應位置的兩個數值看作一個樣本點,皮爾遜系數用來表示這些樣本點分布的相關性。
由于皮爾遜系數具有的良好性質,在各個領域都應用廣泛,例如,在推薦系統根據為某一使用者查找喜好相似的使用者,進而提供推薦,優點是可以不受每個使用者評分标準不同和觀看影片數量不一樣的影響。
4. 分類資料點間的距離
漢明距離(Hamming distance)是指,兩個等長字元串s1與s2之間的漢明距離定義為将其中一個變為另外一個所需要作的最小替換次數。舉個維基百科上的例子:
還可以用簡單的比對系數來表示兩點之間的相似度——比對字元數/總字元數。
在一些情況下,某些特定的值相等并不能代表什麼。舉個例子,用 1 表示使用者看過該電影,用 0 表示使用者沒有看過,那麼使用者看電影的的資訊就可用 0,1 表示成一個序列。考慮到電影基數非常龐大,使用者看過的電影隻占其中非常小的一部分,如果兩個使用者都沒有看過某一部電影(兩個都是 0),并不能說明兩者相似。反而言之,如果兩個使用者都看過某一部電影(序列中都是 1),則說明使用者有很大的相似度。在這個例子中,序列中等于 1 所占的權重應該遠遠大于 0 的權重,這就引出下面要說的傑卡德相似系數(Jaccard similarity)。
在上面的例子中,用 M11 表示兩個使用者都看過的電影數目,M10 表示使用者 A 看過,使用者 B 沒看過的電影數目,M01 表示使用者 A 沒看過,使用者 B 看過的電影數目,M00 表示兩個使用者都沒有看過的電影數目。Jaccard 相似性系數可以表示為:
Jaccard similarity 還可以用集合的公式來表達,這裡就不多說了。
如果分類數值點是用樹形結構來表示的,它們的相似性可以用相同路徑的長度來表示,比如,“/product/spot/ballgame/basketball” 離“product/spot/ballgame/soccer/shoes” 的距離小于到 "/product/luxury/handbags" 的距離,以為前者相同父節點路徑更長。
5. 序列之間的距離
上一小節我們知道,漢明距離可以度量兩個長度相同的字元串之間的相似度,如果要比較兩個不同長度的字元串,不僅要進行替換,而且要進行插入與删除的運算,在這種場合下,通常使用更加複雜的編輯距離(Edit distance, Levenshtein distance)等算法。編輯距離是指兩個字串之間,由一個轉成另一個所需的最少編輯操作次數。許可的編輯操作包括将一個字元替換成另一個字元,插入一個字元,删除一個字元。編輯距離求的是最少編輯次數,這是一個動态規劃的問題,有興趣的同學可以自己研究研究。
時間序列是序列之間距離的另外一個例子。DTW 距離(Dynamic Time Warp)是序列信号在時間或者速度上不比對的時候一種衡量相似度的方法。神馬意思?舉個例子,兩份原本一樣聲音樣本A、B都說了“你好”,A在時間上發生了扭曲,“你”這個音延長了幾秒。最後A:“你~~~好”,B:“你好”。DTW正是這樣一種可以用來比對A、B之間的最短距離的算法。
DTW 距離在保持信号先後順序的限制下對時間信号進行“膨脹”或者“收縮”,找到最優的比對,與編輯距離相似,這其實也是一個動态規劃的問題:
實作代碼(轉自 McKelvin's Blog ):
[java] view plain copy
- <span style="background-color: rgb(255, 255, 255);">#!/usr/bin/python2
- # -*- coding:UTF-8 -*-
- # code related at: http://blog.mckelv.in/articles/1453.html
- import sys
- distance = lambda a,b : 0 if a==b else 1
- def dtw(sa,sb):
- '''
- >>>dtw(u"幹啦今今今今今天天氣氣氣氣氣好好好好啊啊啊", u"今天天氣好好啊")
- 2
- '''
- MAX_COST = 1<<32
- #初始化一個len(sb) 行(i),len(sa)列(j)的二維矩陣
- len_sa = len(sa)
- len_sb = len(sb)
- # BUG:這樣是錯誤的(淺拷貝): dtw_array = [[MAX_COST]*len(sa)]*len(sb)
- dtw_array = [[MAX_COST for i in range(len_sa)] for j in range(len_sb)]
- dtw_array[0][0] = distance(sa[0],sb[0])
- for i in xrange(0, len_sb):
- for j in xrange(0, len_sa):
- if i+j==0:
- continue
- nb = []
- if i > 0: nb.append(dtw_array[i-1][j])
- if j > 0: nb.append(dtw_array[i][j-1])
- if i > 0 and j > 0: nb.append(dtw_array[i-1][j-1])
- min_route = min(nb)
- cost = distance(sa[j],sb[i])
- dtw_array[i][j] = cost + min_route
- return dtw_array[len_sb-1][len_sa-1]
- def main(argv):
- s1 = u'幹啦今今今今今天天氣氣氣氣氣好好好好啊啊啊'
- s2 = u'今天天氣好好啊'
- d = dtw(s1, s2)
- print d
- return 0
- if __name__ == '__main__':
- sys.exit(main(sys.argv))</span>
6. 機率分布之間的距離
前面我們談論的都是兩個數值點之間的距離,實際上兩個機率分布之間的距離是可以測量的。在統計學裡面經常需要測量兩組樣本分布之間的距離,進而判斷出它們是否出自同一個 population,常見的方法有卡方檢驗(Chi-Square)和 KL 散度( KL-Divergence),下面說一說 KL 散度吧。
先從資訊熵說起,假設一篇文章的标題叫做“黑洞到底吃什麼”,包含詞語分别是 {黑洞, 到底, 吃什麼}, 我們現在要根據一個詞語推測這篇文章的類别。哪個詞語給予我們的資訊最多?很容易就知道是“黑洞”,因為“黑洞”這個詞語在所有的文檔中出現的機率太低啦,一旦出現,就表明這篇文章很可能是在講科普知識。而其他兩個詞語“到底”和“吃什麼”出現的機率很高,給予我們的資訊反而越少。如何用一個函數 h(x) 表示詞語給予的資訊量呢?第一,肯定是與 p(x) 相關,并且是負相關。第二,假設 x 和 y 是獨立的(黑洞和宇宙不互相獨立,談到黑洞必然會說宇宙),即 p(x,y) = p(x)p(y), 那麼獲得的資訊也是疊加的,即 h(x, y) = h(x) + h(y)。滿足這兩個條件的函數肯定是負對數形式:
對假設一個發送者要将随機變量 X 産生的一長串随機值傳送給接收者, 接受者獲得的平均資訊量就是求它的數學期望:
這就是熵的概念。另外一個重要特點是,熵的大小與字元平均最短編碼長度是一樣的(shannon)。設有一個未知的分布 p(x), 而 q(x) 是我們所獲得的一個對 p(x) 的近似,按照 q(x) 對該随機變量的各個值進行編碼,平均長度比按照真實分布的 p(x) 進行編碼要額外長一些,多出來的長度這就是 KL 散度(之是以不說距離,是因為不滿足對稱性和三角形法則),即:
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 疊代算法等。
參考資料:
- 距離和相似性度量
- Machine Learning: Measuring Similarity and Distance
- What is Mahalanobis distance?
- Cosine similarity, Pearson correlation, and OLS coefficients
- 機器學習中的相似性度量
- 動态時間歸整 | DTW | Dynamic Time Warping
作者:daniel-D 出處:http://www.cnblogs.com/daniel-D/ 歡迎轉載或分享,但請務必聲明文章出處。