機器學(xué)習(xí)中的相似性度量

1、在做分類時常常需要估算不同樣本之間的相似性度量(Similarity Measurement),這時通常采用的方法就是計算樣本間的距離”(Distance)。 采用什么樣的方法計算距離是很講究，甚至關(guān)系到分類的正確與否。本文的目的就是對常用的相似性度量作一個總結(jié)。本文目錄：歐氏距離曼哈頓距離切比雪夫距離閔可夫斯基距離標(biāo)準(zhǔn)化歐氏距離馬氏距離夾角余弦漢明距離杰卡德距離&杰卡德相似系數(shù)相關(guān)系數(shù)&相關(guān)距離信息熵歐氏距離(Euclidean Distance)歐氏距離是最易于理解的一種距離計算方法，源自歐氏空間中兩點間的距 離公式。(1)二維平面上兩點a(x1,y1)與b(x2,y2)間的歐氏距離：(2

2、)三維空間兩點a(x1,y1,z1)與b(x2,y2,z2)間的歐氏距離:兩個 n 維向量 a(x11,x12,.,x1n)與 b(x21,x22,.,x2n)間的歐氏距離:也可以用表示成向量運算的形式：(4)Matlab計算歐氏距離Matlab計算距離主要使用pdist函數(shù)。若X是一個MxN的矩陣，則pdist(X) 將X矩陣M行的每一行作為一個N維向量，然后計算這M個向量兩兩間的距 離。例子：計算向量(0,0)、(1,0)、(0,2)兩兩間的歐式距離X = 0 0 ; 1 0 ; 0 2D = pdist(X,euclidean)結(jié)果：D =1.00002.00002.2361曼哈頓距離(

3、Manhattan Distance)從名字就可以猜出這種距離的計算方法了。想象你在曼哈頓要從一個十字 路口開車到另外一個十字路口，駕駛距離是兩點間的直線距離嗎？顯然不是，除 非你能穿越大樓。實際駕駛距離就是這個曼哈頓距離。而這也是曼哈頓距離名 稱的來源，曼哈頓距離也稱為城市街區(qū)距離(City Block distance) o二維平面兩點a(x1,y1)與b(x2,y2)間的曼哈頓距離12 =+ lyi -y2l兩個 n 維向量 a(x11,x12,.,x1n)與 b(x21,x22,.,x2n)間的曼哈頓距離k=l(3) Matlab計算曼哈頓距離例子：計算向量(0,0)、(1,0)、(0

4、,2)兩兩間的曼哈頓距離X = 0 0 ; 1 0 ; 0 2D = pdist(X, cityblock)結(jié)果：D =123國際象棋玩過么？國王走一步能夠移動到相鄰的8個方格中的任意一個。 那么國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？自己走走試試。你 會發(fā)現(xiàn)最少步數(shù)總是max( | x2-x1 | , | y2-y1 | )步。有一種類似的一種距 離度量方法叫切比雪夫距離。二維平面兩點a(x1,y1)與b(x2,y2)間的切比雪夫距離d12 = maxfbi-yal)兩個 n 維向量 a(x11,x12,.,x1n)與 b(x21,x22,.,x2n)間的切比雪夫距 離

5、說=-工招)這個公式的另一種等價形式是看不出兩個公式是等價的？提示一下：試試用放縮法和夾逼法則來證明。(3)Matlab計算切比雪夫距離例子：計算向量(0,0)、(1,0)、(0,2)兩兩間的切比雪夫距離X = 0 0 ; 1 0 ; 0 2D = pdist(X, chebychev)結(jié)果：D =122閔可夫斯基距離(Minkowski Distance)閔氏距離不是一種距離，而是一組距離的定義。閔氏距離的定義兩個 n 維變量 a(x11,x12,.,x1n)與 b(x21,x22,.,x2n)間的閔可夫斯基距離定義為：其中p是一個變參數(shù)。當(dāng)p=1時，就是曼哈頓距離當(dāng)p=2時，就是歐氏距離當(dāng)

6、p8時，就是切比雪夫距離根據(jù)變參數(shù)的不同，閔氏距離可以表示一類的距離。閔氏距離的缺點閔氏距離，包括曼哈頓距離、歐氏距離和切比雪夫距離都存在明顯的缺點。舉個例子：二維樣本(身高，體重)，其中身高范圍是150190，體重范圍 是 5060，有三個樣本：a(180,50)，b(190,50)，c(180,60)。那么 a 與 b 之間的閔氏距離(無論是曼哈頓距離、歐氏距離或切比雪夫距離)等于a與c 之間的閔氏距離，但是身高的10cm真的等價于體重的10kg么？因此用閔氏 距離來衡量這些樣本間的相似度很有問題。簡單說來，閔氏距離的缺點主要有兩個：(1)將各個分量的量綱(scale)， 也就是單位當(dāng)作相

7、同的看待了。(2)沒有考慮各個分量的分布(期望，方差等) 可能是不同的。Matlab計算閔氏距離例子：計算向量(0,0)、(1,0)、(0,2)兩兩間的閔氏距離(以變參數(shù)為2的歐氏 距離為例)X = 0 0 ; 1 0 ; 0 2D = pdist(X,minkowski,2)結(jié)果：D =1.00002.00002.2361標(biāo)準(zhǔn)化歐氏距離(Standardized Euclidean distance )(1)標(biāo)準(zhǔn)歐氏距離的定義標(biāo)準(zhǔn)化歐氏距離是針對簡單歐氏距離的缺點而作的一種改進(jìn)方案。標(biāo)準(zhǔn)歐氏 距離的思路：既然數(shù)據(jù)各維分量的分布不一樣，好吧！那我先將各個分量都標(biāo) 準(zhǔn)化到均值、方差相等吧。均值和

8、方差標(biāo)準(zhǔn)化到多少呢？這里先復(fù)習(xí)點統(tǒng)計學(xué) 知識吧，假設(shè)樣本集X的均值(mean)為m，標(biāo)準(zhǔn)差(standard deviation)為 s，那么X的標(biāo)準(zhǔn)化變量表示為：而且標(biāo)準(zhǔn)化變量的數(shù)學(xué)期望為0，方差為1。因此樣本集的標(biāo)準(zhǔn)化過程 (standardization)用公式描述就是：IX mK =標(biāo)準(zhǔn)化后的值=(標(biāo)準(zhǔn)化前的值一分量的均值)/分量的標(biāo)準(zhǔn)差經(jīng)過簡單的推導(dǎo)就可以得到兩個n維向量a(x11,x12,.,x1n)與 b(x21,x22,.,x2n)間的標(biāo)準(zhǔn)化歐氏距離的公式：如果將方差的倒數(shù)看成是一個權(quán)重，這個公式可以看成是一種加權(quán)歐氏距離(Weighted Euclidean distance

9、) o(2)Matlab計算標(biāo)準(zhǔn)化歐氏距離例子：計算向量(0,0)、(1,0)、(0,2)兩兩間的標(biāo)準(zhǔn)化歐氏距離(假設(shè)兩個分量 的標(biāo)準(zhǔn)差分別為0.5和1)X = 0 0 ; 1 0 ; 0 2D = pdist(X, seuclidean,0.5,1)結(jié)果：D =2.00002.00002.8284馬氏距離(Mahalanobis Distance)(1)馬氏距離定義有M個樣本向量X1Xm，協(xié)方差矩陣記為S，均值記為向量，則其中 樣本向量X到u的馬氏距離表示為：而其中向量Xi與Xj之間的馬氏距離定義為:若協(xié)方差矩陣是單位矩陣(各個樣本向量之間獨立同分布)，則公式就成了:功=J(蘋-電丁叫-電也

10、就是歐氏距離了。若協(xié)方差矩陣是對角矩陣，公式變成了標(biāo)準(zhǔn)化歐氏距離。馬氏距離的優(yōu)缺點：量綱無關(guān)，排除變量之間的相關(guān)性的干擾。Matlab計算(1 2)，( 1 3)，( 2 2)，( 3 1)兩兩之間的馬氏距離X = 1 2; 1 3; 2 2; 3 1Y = pdist(X,mahalanobis)結(jié)果:Y =2.34522.00002.34521.22472.44951.22477.夾角余弦(Cosine)有沒有搞錯，又不是學(xué)幾何，怎么扯到夾角余弦了？各位看官稍安勿躁。 幾何中夾角余弦可用來衡量兩個向量方向的差異，機器學(xué)習(xí)中借用這一概念來衡 量樣本向量之間的差異。(1)在二維空間中向量A(x

11、1,y1)與向量B(x2,y2)的夾角余弦公式：(2)兩個 n 維樣本點 a(x11,x12,.,x1n)和 b(x21,x22,.,x2n)的夾角余弦 類似的，對于兩個 n 維樣本點 a(x11,x12,.,x1n)和 b(x21,x22,.,x2n)，可以使用類似于夾角余弦的概念來衡量它們間的相似程度。cos(幻=7-nT7cc |h|即：夾角余弦取值范圍為-1,1。夾角余弦越大表示兩個向量的夾角越小，夾 角余弦越小表示兩向量的夾角越大。當(dāng)兩個向量的方向重合時夾角余弦取最大值 1，當(dāng)兩個向量的方向完全相反夾角余弦取最小值-1。夾角余弦的具體應(yīng)用可以參閱參考文獻(xiàn)1。(3)Matlab計算夾角

12、余弦例子：計算(1,0)、( 1,1.732)、( -1,0)兩兩間的夾角余弦X = 1 0 ; 1 1.732 ; -1 0D = 1- pdist(X, cosine) % Matlab 中的 pdist(X, cosine)得到的是 1 減 夾角余弦的值結(jié)果：D =0.5000 -1.0000 -0.5000漢明距離(Hamming distance)漢明距離的定義兩個等長字符串si與s2之間的漢明距離定義為將其中一個變?yōu)榱硗庖粋€ 所需要作的最小替換次數(shù)。例如字符串“1111與“1001之間的漢明距離為2。應(yīng)用：信息編碼(為了增強容錯性，應(yīng)使得編碼間的最小漢明距離盡可能 大)。Matla

13、b計算漢明距離Matlab中2個向量之間的漢明距離的定義為2個向量不同的分量所占的百 分比。例子：計算向量(0,0)、(1,0)、(0,2)兩兩間的漢明距離X = 0 0 ; 1 0 ; 0 2;D = PDIST(X, hamming)結(jié)果：D =0.50000.50001.0000杰卡德相似系數(shù)(Jaccard similarity coefficient)(1)杰卡德相似系數(shù)兩個集合A和B的交集元素在A，B的并集中所占的比例，稱為兩個集合 的杰卡德相似系數(shù)，用符號J(A,B)表示。杰卡德相似系數(shù)是衡量兩個集合的相似度一種指標(biāo)。(2)杰卡德距離與杰卡德相似系數(shù)相反的概念是杰卡德距離(Jac

14、card distance)。杰卡德距離可用如下公式表示：杰卡德距離用兩個集合中不同元素占所有元素的比例來衡量兩個集合的區(qū) 分度。杰卡德相似系數(shù)與杰卡德距離的應(yīng)用可將杰卡德相似系數(shù)用在衡量樣本的相似度上。樣本A與樣本B是兩個n維向量，而且所有維度的取值都是0或1。例如： A(0111)和B(1011)。我們將樣本看成是一個集合，1表示集合包含該元素，0 表示集合不包含該元素。p :樣本A與B都是1的維度的個數(shù)q ：樣本A是1,樣本B是0的維度的個數(shù)r ：樣本A是0,樣本B是1的維度的個數(shù)s :樣本A與B都是0的維度的個數(shù)那么樣本A與B的杰卡德相似系數(shù)可以表示為：這里p+q + r可理解為A與B

15、的并集的元素個數(shù)，而p是A與B的交集的元素 個數(shù)。而樣本A與B的杰卡德距離表示為：+母+ T(4)Matlab計算杰卡德距離Matlab的pdist函數(shù)定義的杰卡德距離跟我這里的定義有一些差別，Matlab 中將其定義為不同的維度的個數(shù)占非全零維度的比例。例子：計算(1,1,0)、(1,-1,0)、(-1,1,0)兩兩之間的杰卡德距離X = 1 1 0; 1 -1 0; -1 1 0D = pdist( X , jaccard)結(jié)果D =0.50000.50001.0000相關(guān)系數(shù)(Correlation coefficient )與相關(guān)距離(Correlation distance)(1)相

16、關(guān)系數(shù)的定義|_ Cov(XrY) _ F(X- EX)(7-Fr)相關(guān)系數(shù)是衡量隨機變量X與Y相關(guān)程度的一種方法，相關(guān)系數(shù)的取值范圍是 -1,1。相關(guān)系數(shù)的絕對值越大，則表明X與Y相關(guān)度越高。當(dāng)X與Y線性相 關(guān)時，相關(guān)系數(shù)取值為1 (正線性相關(guān))或-1 (負(fù)線性相關(guān))。(2)相關(guān)距離的定義(3)Matlab計算(1, 2 ,3 ,4 )與(3 ,8 ,7 ,6 )之間的相關(guān)系數(shù)與相關(guān)距離X = 1 2 3 4 ; 3 8 7 6C = corrcoef( X ) %將返回相關(guān)系數(shù)矩陣D = pdist( X , correlation)結(jié)果：C =1.00000.47810.47811.00

17、00D =0.5219其中0.4781就是相關(guān)系數(shù)，0.5219是相關(guān)距離。信息熵(Information Entropy)信息嫡并不屬于一種相似性度量。那為什么放在這篇文章中??？這個。 我也不知道。(Jv)信息嫡是衡量分布的混亂程度或分散程度的一種度量。分布越分散(或者說分布 越平均)，信息嫡就越大。分布越有序(或者說分布越集中)，信息嫡就越小。計算給定的樣本集X的信息嫡的公式：Eiitropy(X) = -p-蜘gt=l參數(shù)的含義：n：樣本集X的分類數(shù)pi： X中第i類元素出現(xiàn)的概率信息嫡越大表明樣本集S分類越分散，信息嫡越小則表明樣本集X分類越 集中。當(dāng)S中n個分類出現(xiàn)的概率一樣大時(都

18、是1/n)，信息嫡取最大值 log2(n)。當(dāng)X只有一個分類時，信息嫡取最小值0參考資料：吳軍.數(shù)學(xué)之美系列12 -余弦定理和新聞的分類. HYPERLINK .hk/ggblog/googlechinablog/2006/07/12_40 .hk/ggblog/googlechinablog/2006/07/12_40 10.htmlWikipedia. Jaccard index. HYPERLINK /wiki/Jaccard_index /wiki/Jaccard_indexWikipedia. Hamming distance HYPERLINK /wiki/Hamming_distance /wik