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

機器學(xué)習(xí)中的相似性度量在做分類時常常需要估算不同樣本之間的相似性度量(SimilarityMeasurement)，這時通常采用的方法就是計算樣本間的''距離”(Distance)。采用什么樣的方法計算距離是很講究，甚至關(guān)系到分類的正確與否。本文的目的就是對常用的相似性度量作一個總結(jié)。本文目錄：歐氏距離曼哈頓距離切比雪夫距離閔可夫斯基距離標準化歐氏距離馬氏距離夾角余弦漢明距離杰卡德距離&杰卡德相似系數(shù)相關(guān)系數(shù)&相關(guān)距離信息熵hausdorff距離Bhattacharyya距離歐氏距離(EuclideanDistance)歐氏距離是最易于理解的一種距離計算方法，源自歐氏空間中兩點間的距離公式。二維平面上兩點a(x1,y1)與b(x2,y2)間的歐氏距離：必=7(^1- +<71-Yz)1三維空間兩點a(x1,y1,z1)與b(x2,y2,z2)間的歐氏距離：他=/(”一如)'+S—W+(宥一知)兩個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=[00;10;02]D=pdist(X,'euclidean')結(jié)果：D=1.0000 2.0000 2.2361曼哈頓距離(ManhattanDistance)從名字就可以猜出這種距離的計算方法了。想象你在曼哈頓要從一個十字路口開車到另外一個十字路口，駕駛距離是兩點間的直線距離嗎？顯然不是，除非你能穿越大樓。實際駕駛距離就是這個''曼哈頓距離〃。而這也是曼哈頓距離名稱的來源，曼哈頓距離也稱為城市街區(qū)距離(CityBlockdistance)。(1)二維平面兩點a(x1,y1)與b(x2,y2)間的曼哈頓距離^12=依二一圣1+Iti-y2l(2)兩個n維向量a(x11,x12,...,x1n)與b(x21,x22,...,x2n)間的曼哈頓距離k=l(3)Matlab計算曼哈頓距離例子:計算向量(0,0)、(1,0)、(0,2)兩兩間的曼哈頓距離X=[00;10;02]D=pdist(X,'cityblock')結(jié)果：D=12 3切比雪夫距離(ChebyshevDistance)國際象棋玩過么？國王走一步能夠移動到相鄰的8個方格中的任意一個。那么國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？自己走走試試。你會發(fā)現(xiàn)最少步數(shù)總是max(|x2-x1|,|y2-y1|)步。有一種類似的一種距離度量方法叫切比雪夫距離。二維平面兩點a(x1,y1)與b(x2,y2)間的切比雪夫距離』說=方一知|」憲-ya|)兩個n維向量a(x11,x12,...,x1n)與b(x21,x22,...,x2n)間的切比雪夫距離這個公式的另一種等價形式是看不出兩個公式是等價的？提示一下:試試用放縮法和夾逼法則來證明。(3)Matlab計算切比雪夫距離例子:計算向量(0,0)、(1,0)、(0,2)兩兩間的切比雪夫距離X=[00;10;02]D=pdist(X,'chebychev')12 2閔可夫斯基距離(MinkowskiDistance)閔氏距離不是一種距離，而是一組距離的定義。(1)閔氏距離的定義兩個n維變量a(x11,x12,...,x1n)與b(x21,x22,...,x2n)間的閔可夫斯基距離定義為：其中p是一個變參數(shù)。當p=1時，就是曼哈頓距離當p=2時，就是歐氏距離當p-8時，就是切比雪夫距離根據(jù)變參數(shù)的不同，閔氏距離可以表示一類的距離。閔氏距離的缺點閔氏距離，包括曼哈頓距離、歐氏距離和切比雪夫距離都存在明顯的缺點。舉個例子:二維樣本(身高，體重)，其中身高范圍是150~190，體重范圍是50~60，有三個樣本:a(180,50)，b(190,50)，c(180,60)。那么a與b之間的閔氏距離(無論是曼哈頓距離、歐氏距離或切比雪夫距離)等于a與c之間的閔氏距離，但是身高的10cm真的等價于體重的10kg么？因此用閔氏距離來衡量這些樣本間的相似度很有問題。簡單說來，閔氏距離的缺點主要有兩個：(1)將各個分量的量綱(scale)，也就是''單位〃當作相同的看待了。(2)沒有考慮各個分量的分布(期望，方差等)可能是不同的。Matlab計算閔氏距離例子:計算向量(0,0)、(1,0)、(0,2)兩兩間的閔氏距離(以變參數(shù)為2的歐氏距離為例)X=[00;10;02]D=pdist(X,'minkowski',2)結(jié)果：D=1.0000 2.0000 2.2361標準化歐氏距離(StandardizedEuclideandistance)(1)標準歐氏距離的定義標準化歐氏距離是針對簡單歐氏距離的缺點而作的一種改進方案。標準歐氏距離的思路:既然數(shù)據(jù)各維分量的分布不一樣，好吧！那我先將各個分量都''標準化〃到均值、方差相等吧。均值和方差標準化到多少呢？這里先復(fù)習(xí)點統(tǒng)計學(xué)知識吧，假設(shè)樣本集X的均值(mean)為m，標準差(standarddeviation)為s，那么X的''標準化變量〃表示為：而且標準化變量的數(shù)學(xué)期望為0，方差為1。因此樣本集的標準化過程(standardization)用公式描述就是：X—m標準化后的值=(標準化前的值一分量的均值)/分量的標準差經(jīng)過簡單的推導(dǎo)就可以得到兩個n維向量a(x11,x12,...,x1n)與b(x21,x22,...,x2n)間的標準化歐氏距離的公式：如果將方差的倒數(shù)看成是一個權(quán)重，這個公式可以看成是一種加權(quán)歐氏距離(WeightedEuclideandistance)o(2)Matlab計算標準化歐氏距離例子:計算向量(0,0)、(1,0)、(0,2)兩兩間的標準化歐氏距離(假設(shè)兩個分量的標準差分別為0.5和1)X=[00;10;02]D=pdist(X,'seuclidean',[0.5,1])結(jié)果：D=2.0000 2.0000 2.8284馬氏距離(MahalanobisDistance)馬氏距離定義有M個樣本向量X1~Xm,協(xié)方差矩陣記為S,均值記為向量四則其中樣本向量X到u的馬氏距離表示為：D(X)=而其中向量Xi與Xj之間的馬氏距離定義為：D(W)=」(*-""**一知若協(xié)方差矩陣是單位矩陣(各個樣本向量之間獨立同分布),則公式就成了：D(乩另)=告)T(E-旨)也就是歐氏距離了。若協(xié)方差矩陣是對角矩陣，公式變成了標準化歐氏距離。馬氏距離的優(yōu)缺點:量綱無關(guān)，排除變量之間的相關(guān)性的干擾。Matlab計算(12)，(13)，(22)，(31)兩兩之間的馬氏距離X=[12;13;22;31]=pdist(X,'mahalanobis')結(jié)果：=2.3452 2.0000 2.3452 1.2247 2.4495 1.2247夾角余弦(Cosine)有沒有搞錯，又不是學(xué)幾何，怎么扯到夾角余弦了？各位看官稍安勿躁。幾何中夾角余弦可用來衡量兩個向量方向的差異，機器學(xué)習(xí)中借用這一概念來衡量樣本向量之間的差異。在二維空間中向量A(x1,y1)與向量B(x2,y2)的夾角余弦公式：COS0=COS0=+y1y2+ /與拱+y孩兩個n維樣本點a(x11,x12,...,x1n)和b(x21,x22,...,x2n)的夾角余弦類似的，對于兩個n維樣本點a(x11,x12,...,x1n)和b(x21,x22,...,x2n)，可以使用類似于夾角余弦的概念來衡量它們間的相似程度。即:夾角余弦取值范圍為［-1,1］。夾角余弦越大表示兩個向量的夾角越小，夾角余弦越小表示兩向量的夾角越大。當兩個向量的方向重合時夾角余弦取最大值1，當兩個向量的方向完全相反夾角余弦取最小值-1。夾角余弦的具體應(yīng)用可以參閱參考文獻［1］。(3)Matlab計算夾角余弦例子:計算(1,0)、(1,1.732)、(-1,0)兩兩間的夾角余弦X=［10;11.732;-10］D=1-pdist(X,'cosine')%Matlab中的pdist(X,'cosine')得到的是1減夾角余弦的值結(jié)果：D=0.5000-1.0000-0.5000漢明距離(Hammingdistance)(1)漢明距離的定義兩個等長字符串S1與s2之間的漢明距離定義為將其中一個變?yōu)榱硗庖粋€所需要作的最小替換次數(shù)。例如字符串“1111'與''1001〃之間的漢明距離為2。應(yīng)用:信息編碼(為了增強容錯性，應(yīng)使得編碼間的最小漢明距離盡可能大)。(2)Matlab計算漢明距離Matlab中2個向量之間的漢明距離的定義為2個向量不同的分量所占的百分比。例子:計算向量(0,0)、(1,0)、(0,2)兩兩間的漢明距離X=[00;10;02];D=PDIST(X,'hamming')結(jié)果：D=0.5000 0.5000 1.0000杰卡德相似系數(shù)(Jaccardsimilaritycoefficient)杰卡德相似系數(shù)兩個集合A和B的交集元素在A，B的并集中所占的比例，稱為兩個集合的杰卡德相似系數(shù)，用符號J(A,B)表示。SB)=杰卡德相似系數(shù)是衡量兩個集合的相似度一種指標。杰卡德距離與杰卡德相似系數(shù)相反的概念是杰卡德距離(Jaccarddistance)。杰卡德距離可用如下公式表示：Jd(A,E)=l-；(A^=一疝茂一杰卡德距離用兩個集合中不同元素占所有元素的比例來衡量兩個集合的區(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的并集的元素個數(shù)，而p是A與B的交集的元素個數(shù)。而樣本A與B的杰卡德距離表示為：p+q+亍(4)Matlab計算杰卡德距離Matlab的pdist函數(shù)定義的杰卡德距離跟我這里的定義有一些差別，Matlab中將其定義為不同的維度的個數(shù)占''非全零維度〃的比例。例子:計算(1,1,0)、(1,-1,0)、(-1,1,0)兩兩之間的杰卡德距離X=[110;1-10;-110]D=pdist(X,'jaccard')結(jié)果D=0.5000 0.5000 1.0000相關(guān)系數(shù)(Correlationcoefficient)與相關(guān)距離(Correlationdistance)(1)相關(guān)系數(shù)的定義_^ovpf.Y)_旺(X—EX)(F—Erj)相關(guān)系數(shù)是衡量隨機變量X與Y相關(guān)程度的一種方法，相關(guān)系數(shù)的取值范圍是[-1,1]。相關(guān)系數(shù)的絕對值越大，則表明X與Y相關(guān)度越高。當X與Y線性相關(guān)時,相關(guān)系數(shù)取值為1（正線性相關(guān)）或-1（負線性相關(guān)）。（2）相關(guān)距離的定義=1■—PXYMatlab計算(1,2,3,4)與(3,8,7,6)之間的相關(guān)系數(shù)與相關(guān)距離X=[1234;3876]C=corrcoef(X')%將返回相關(guān)系數(shù)矩陣D=pdist(X,'correlation')結(jié)果:C=1.0000 0.47810.4781 1.00000.5219其中0.4781就是相關(guān)系數(shù)，0.5219是相關(guān)距離。信息熵（InformationEntropy）信息嫡并不屬于一種相似性度量。那為什么放在這篇文章中?。窟@個。。。我也不知道。（JV）L信息嫡是衡量分布的混亂程度或分散程度的一種度量。分布越分散（或者說分布越平均），信息嫡就越大。分布越有序（或者說分布越集中），信息嫡就越小。計算給定的樣本集X的信息嫡的公式：Entropy(X)=￡一孔M吸pt=l參數(shù)的含義：n：樣本集X的分類數(shù)pi:X中第i類元素出現(xiàn)的概率信息熵越大表明樣本集S分類越分散，信息熵越小則表明樣本集X分類越集中。。當S中n個分類出現(xiàn)的概率一樣大時(都是1/n),信息熵取最大值log2(n)。當X只有一個分類時，信息熵取最小值012hausdorff距離微分動力系統(tǒng)原理這本書里有介紹Hausdorff距離是描述兩組點集之間相似程度的一種量度，它是兩個點集之間距離的一種定義形式:假設(shè)有兩組集合A={a1,…,ap},B={b1,…,bq}，則這兩個點集合之間的Hausdorff距離定義為H(A,B)=max(h(A,B),h(B,A))(1)其中，h(A,B)=max(a^A)min(b^B)IIa-bII(2)h(B,A)=max(b^B)min(a^A)||b-aII(3)II.II是點集A和B點集間的距離范式(如:L2或Euclidean距離).這里式⑴稱為雙向Hausdorff距離是Hausdorff距離的最基本形式；式⑵中的h(A,B)和h(B,A)分別稱為從A集合到B集合和從B集合到A集合的單向Hausdorff距離.即h(A,B)實際上首先對點集A中的每個點ai到距離此點ai最近的B集合中點bj之間的距離Iai-bjI進行排序，然后取該距離中的最大值作為h(A,B)的值.h(B,A)同理可得.由式⑴知雙向Hausdorff距離H(A,B)是單向距離h(A,B)和h(B,A)兩者中的較大者，它度量了兩個點集間的最大不匹配程度.13Bhattacharyya距離在統(tǒng)計學(xué)中，Bhattacharyya距離(以下稱巴氏距離)測量的是兩個離散或連續(xù)概率分布的相似性。計算方式和Bhattacharyya系數(shù)關(guān)系很密切。兩種計算方式都以A.Bhattacharyya名字命名，Bhattacharyya是一位30年代在印度統(tǒng)計研究所工作的統(tǒng)計學(xué)家。巴氏系數(shù)可用來對兩組樣本的相關(guān)性進行測量。這一方法常用來作分類器算法。[1]數(shù)學(xué)定義-離散概率分布對于在X數(shù)域上的兩個離散概率分布p和q,巴氏距離定義為[2]:DB(p,q)=-ln(BC(p,q))其中BC(p,q)=Z<p(x)q(x)BC被稱作Bhattacharyya系數(shù)(巴氏系數(shù))0<BC<1q且0<DB<^-連續(xù)概率分布在連續(xù)情形中，Bhattacharyya系數(shù)如下定義：BC(p,q)=Np(x)q(x)dx0<BC<1q且0<DB<8兩種情形中，巴氏距離DB均不滿足三角不等式Bhattacharyya系數(shù)Bhattacharyya系數(shù)[3](BhattacharyyaCoefficient,巴氏系數(shù))是對兩個統(tǒng)計樣本的重疊量的近似計算。巴氏系數(shù)可用來對兩組樣本的相關(guān)性進行測量。計算巴氏系數(shù)涉及到對該兩個樣本的重疊部分進行基本形式的積分。兩個樣本值的積分被分成指定數(shù)目的部分。而每一個樣本的每一個部分的成員數(shù)被用于下式中：Bhattacharyya=￡{i=1|n}W￡ai?￡bi)其中，a,b為兩個樣本，n是分塊數(shù)，ai,bi分別是在a,b中第i部分的成員數(shù)。這樣一來，這個式子就