相似性度量完

在做分類時常常需要估算不同樣本之間的相似性度量(SimilarityMeasurement)，這時通常采用的方法就是計算樣本間的“距離”(Distance)。采用什么樣的方法計算距離是很講究，甚至關(guān)系到分類的正確與否。對常用的相似性度量作一個總結(jié)。1.歐氏距離2.曼哈頓距離3.切比雪夫距離4.閔可夫斯基距離5.標(biāo)準(zhǔn)化歐氏距離6.馬氏距離7.夾角余弦8.漢明距離9.杰卡德距離&杰卡德相似系數(shù)10.相關(guān)系數(shù)&相關(guān)距離11.信息熵12.蘭氏距離13.斜交空間距離14.最大-最小相似度15.指數(shù)相似度16.KL距離1.歐氏距離(EuclideanDistance)歐氏距離是最易于理解的一種距離計算方法，源自歐氏空間中兩點間的距離公式。二維平面上兩點a(x1,y1)與b(x2,y2)間的歐氏距離：三維空間兩點a(x1,y1,z1)與b(x2,y2,z2)間的歐氏距離：兩個n維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的歐氏距離：也可以用表示成向量運算的形式：(4)Matlab計算歐氏距離Matlab計算距離主要使用pdist函數(shù)。若X是一個M×N的矩陣，則pdist(X)將X矩陣M行的每一行作為一個N維向量，然后計算這M個向量兩兩間的距離。例子：計算向量(0,0)、(1,0)、(0,2)兩兩間的歐式距離X=[00;10;02]D=pdist(X,'euclidean')結(jié)果：D=1.00002.00002.23612.曼哈頓距離(ManhattanDistance)又稱絕對值距離從名字就可以猜出這種距離的計算方法了。想象你在曼哈頓要從一個十字路口開車到另外一個十字路口，駕駛距離是兩點間的直線距離嗎？顯然不是，除非你能穿越大樓。實際駕駛距離就是這個“曼哈頓距離”。而這也是曼哈頓距離名稱的來源，曼哈頓距離也稱為城市街區(qū)距離(CityBlockdistance)。二維平面兩點a(x1,y1)與b(x2,y2)間的曼哈頓距離兩個n維向量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的曼哈頓距離(3)Matlab計算曼哈頓距離例子：計算向量(0,0)、(1,0)、(0,2)兩兩間的曼哈頓距離X=[00;10;02]D=pdist(X,'cityblock')結(jié)果：D=1233.切比雪夫距離(ChebyshevDistance)國際象棋玩過么？國王走一步能夠移動到相鄰的8個方格中的任意一個。那么國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？自己走走試試。你會發(fā)現(xiàn)最少步數(shù)總是max(|x2-x1|,|y2-y1|)步。有一種類似的一種距離度量方法叫切比雪夫距離。二維平面兩點a(x1,y1)與b(x2,y2)間的切比雪夫距離兩個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')結(jié)果：D=1224.閔可夫斯基距離(MinkowskiDistance)閔氏距離不是一種距離，而是一組距離的定義。(1)閔氏距離的定義兩個n維變量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的閔可夫斯基距離定義為：其中p是一個變參數(shù)。當(dāng)p=1時，就是曼哈頓距離當(dāng)p=2時，就是歐氏距離當(dāng)p→∞時，就是切比雪夫距離根據(jù)變參數(shù)的不同，閔氏距離可以表示一類的距離。(2)閔氏距離的缺點閔氏距離，包括曼哈頓距離、歐氏距離和切比雪夫距離都存在明顯的缺點。舉個例子：二維樣本(身高,體重)，其中身高范圍是150~190，體重范圍是50~60，有三個樣本：a(180,50)，b(190,50)，c(180,60)。那么a與b之間的閔氏距離（無論是曼哈頓距離、歐氏距離或切比雪夫距離）等于a與c之間的閔氏距離，但是身高的10cm真的等價于體重的10kg么？因此用閔氏距離來衡量這些樣本間的相似度很有問題。簡單說來，閔氏距離的缺點主要有兩個：(1)將各個分量的量綱(scale)，也就是“單位”當(dāng)作相同的看待了。(2)沒有考慮各個分量的分布（期望，方差等)可能是不同的。(3)Matlab計算閔氏距離例子：計算向量(0,0)、(1,0)、(0,2)兩兩間的閔氏距離（以變參數(shù)為2的歐氏距離為例）X=[00;10;02]D=pdist(X,'minkowski',2)結(jié)果：D=1.00002.00002.23615.標(biāo)準(zhǔn)化歐氏距離(StandardizedEuclideandistance)(1)標(biāo)準(zhǔn)歐氏距離的定義標(biāo)準(zhǔn)化歐氏距離是針對簡單歐氏距離的缺點而作的一種改進方案。標(biāo)準(zhǔn)歐氏距離的思路：既然數(shù)據(jù)各維分量的分布不一樣，好吧！那我先將各個分量都“標(biāo)準(zhǔn)化”到均值、方差相等吧。均值和方差標(biāo)準(zhǔn)化到多少呢？這里先復(fù)習(xí)點統(tǒng)計學(xué)知識吧，假設(shè)樣本集X的均值(mean)為m，標(biāo)準(zhǔn)差(standarddeviation)為s，那么X的“標(biāo)準(zhǔn)化變量”表示為：而且標(biāo)準(zhǔn)化變量的數(shù)學(xué)期望為0，方差為1。因此樣本集的標(biāo)準(zhǔn)化過程(standardization)用公式描述就是：標(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)歐氏距離(WeightedEuclideandistance)。(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=[00;10;02]D=pdist(X,'seuclidean',[0.5,1])結(jié)果：D=2.00002.00002.82846.馬氏距離(MahalanobisDistance)（1）馬氏距離定義有M個樣本向量X1~Xm，協(xié)方差矩陣記為S，均值記為向量μ，則其中樣本向量X到u的馬氏距離表示為：而其中向量Xi與Xj之間的馬氏距離定義為：若協(xié)方差矩陣是單位矩陣（各個樣本向量之間獨立同分布）,則公式就成了：也就是歐氏距離了。若協(xié)方差矩陣是對角矩陣，公式變成了標(biāo)準(zhǔn)化歐氏距離。(2)馬氏距離的優(yōu)缺點：量綱無關(guān)，排除變量之間的相關(guān)性的干擾。(3)Matlab計算(12)，(13)，(22)，(31)兩兩之間的馬氏距離X=[12;13;22;31]Y=pdist(X,'mahalanobis')結(jié)果：Y=2.34522.00002.34521.22472.44951.22477.夾角余弦(Cosine)有沒有搞錯，又不是學(xué)幾何，怎么扯到夾角余弦了？各位看官稍安勿躁。幾何中夾角余弦可用來衡量兩個向量方向的差異，機器學(xué)習(xí)中借用這一概念來衡量樣本向量之間的差異。在二維空間中向量A(x1,y1)與向量B(x2,y2)的夾角余弦公式：(2)兩個n維樣本點a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夾角余弦類似的，對于兩個n維樣本點a(x11,x12,…,x1n)和b(x21,x22,…,x2n)，可以使用類似于夾角余弦的概念來衡量它們間的相似程度。即：夾角余弦取值范圍為[-1,1]。夾角余弦越大表示兩個向量的夾角越小，夾角余弦越小表示兩向量的夾角越大。當(dāng)兩個向量的方向重合時夾角余弦取最大值1，當(dāng)兩個向量的方向完全相反夾角余弦取最小值-1。從方向上區(qū)分差異，對絕對的數(shù)值并不敏感。(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.50008.漢明距離(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.50000.50001.00009.杰卡德相似系數(shù)(Jaccardsimilaritycoefficient)(1)杰卡德相似系數(shù)兩個集合A和B的交集元素在A，B的并集中所占的比例，稱為兩個集合的杰卡德相似系數(shù)，用符號J(A,B)表示。杰卡德相似系數(shù)是衡量兩個集合的相似度一種指標(biāo)。(2)杰卡德距離與杰卡德相似系數(shù)相反的概念是杰卡德距離(Jaccarddistance)。杰卡德距離可用如下公式表示：杰卡德距離用兩個集合中不同元素占所有元素的比例來衡量兩個集合的區(qū)分度。(3)杰卡德相似系數(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的杰卡德距離表示為：(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.50000.50001.000010.相關(guān)系數(shù)(Correlationcoefficient)與相關(guān)距離(Correlationdistance)(1)相關(guān)系數(shù)的定義相關(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（負線性相關(guān)）。(2)相關(guān)距離的定義(3)Matlab計算(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.00000.47810.47811.0000D=0.5219其中0.4781就是相關(guān)系數(shù)，0.5219是相關(guān)距離。11.信息熵(InformationEntropy)信息熵并不屬于一種相似性度量。信息熵是衡量分布的混亂程度或分散程度的一種度量。分布越分散(或者說分布越平均)，信息熵就越大。分布越有序（或者說分布越集中），信息熵就越小。計算給定的樣本集X的信息熵的公式：參數(shù)的含義：n：樣本集X的分類數(shù)pi：X中第i類元素出現(xiàn)的概率信息熵越大表明樣本集S分類越分散，信息熵越小則表明樣本集X分類越集中。。當(dāng)S中n個分類出現(xiàn)的概率一樣大時（都是1/n），信息熵取最大值log2(n)。當(dāng)X只有一個分類時，信息熵取最小值012.蘭氏距離(LanceandWilliamsdistance，或CanberraDistance)蘭氏距離定義為與馬氏距離一樣，蘭氏距離對數(shù)據(jù)的量綱不敏感。不過蘭氏距離假定變量之間相互獨立，沒有考慮變量之間的相關(guān)性。13.斜交空間距離在m維空間中，使大量具有相關(guān)性的變量的譜系結(jié)構(gòu)不發(fā)生變形，采用斜交空間距離,其公式為：其中，rij為變量i和變量j之間的相關(guān)系數(shù)。m為樣本數(shù)量，n為樣本特征數(shù)。14.最大-最小相似度（Max-MinSimilarity）這里，有三種度量方法：假定，則有15.指數(shù)相似度其中各種相似性度量是第i個值的方差。余弦相似度、Max-Min相似度以及指數(shù)相似度等度量方法的取值范圍都在[0,1]內(nèi)。16.KL距離（又稱為相對熵或者KLDivergence，即Kullback-Leiblerdivergence）KL距離不符合對稱性，即多數(shù)情況下各種相似性度量不成立，KL距離也不符合三角形不等式，即各種相似性度量也不一定成立。pdist函數(shù)

調(diào)用格式：Y=pdist(X,’metric’)

說明：用‘metric’指定的方法計算X數(shù)據(jù)矩陣中對象之間的距離。

X：一個m×n的矩陣，它是由m個對象組成的數(shù)據(jù)集，每個對象的大小為n。

'metric’取值如下：

‘euclidean’：歐氏距離（默認）；

‘seuclidean’：標(biāo)準(zhǔn)化歐氏距離；

‘mahalanobis’：馬氏距離；

‘cityblock’：布洛克距離；

‘minkowski’：明可夫斯基距離；

‘cosine’：余弦距離；

‘correlation’：相關(guān)距離；

‘hamming’：海明距離；

‘jaccard’：杰卡德距離；

‘chebychev’：切比雪夫距離。

詳解協(xié)方差與協(xié)方差矩陣協(xié)方差的定義對于一般的分布，直接代入E(X)之類的就可以計算出來了，但真給你一個具體數(shù)值的分布，要計算協(xié)方差矩陣，根據(jù)這個公式來計算，還真不容易反應(yīng)過來。記住，X、Y是一個列向量，它表示了每種情況下每個樣本可能出現(xiàn)的數(shù)。比如給定則X表示x軸可能出現(xiàn)的數(shù)，Y表示y軸可能出現(xiàn)的。注意這里是關(guān)鍵，給定了4個樣本，每個樣本都是二維的，所以只可能有X和Y兩種維度。所以用中文來描述，就是：協(xié)方差(i,j)=（第i列的所有元素-第i列的均值）*（第j列的所有元素-第j列的均值）這里只有X,Y兩列，所以得到的協(xié)方差矩陣是2x2的矩陣，下面分別求出每一個元素：所以，按照定義，給定的4個二維樣本的協(xié)方差矩陣為：用matlab計算這個例子z=[1,2;3,6;4,2;5,2]cov(z)ans=2.9167-0.3333-0.33334.0000可以看出，matlab計算協(xié)方差過程中還將元素統(tǒng)一縮小了3倍。所以，協(xié)方差的matlab計算公式為：協(xié)方差(i,j)=（第i列所有元素-第i列均值）*（第j列所有元素-第j列均值）/（樣本數(shù)-1）下面在給出一個4維3樣本的實例，注意4維樣本與符號X,Y就沒有關(guān)系了，X,Y表示兩維的，4維就直接套用計算公式，不用X,Y那么具有迷惑性的表達了。（3）與matlab計算驗證Z=[1234;3412;2314]cov(Z)ans=1.00001.0000-1.0000-1.00001.00001.0000-1.0000-1.0000-1.0000-1.00001.33330.6667-1.0000-1.00000.66671.3333可知該計算方法是正確的。我們還可以看出，協(xié)方差矩陣都是方陣，它的維度與樣本維度有關(guān)（相等）。理解協(xié)方差矩陣的關(guān)鍵就在于牢記它計算的是不同維度之間的協(xié)方差，而不是不同樣本之間，拿到一個樣本矩陣，我們最先要明確的就是一行是一個樣本還是一個維度，心中明確這個整個計算過程就會順流而下，這么一來就不會迷茫了~歐氏距離vs馬氏距離我們熟悉的歐氏距離雖然很有用，但也有明顯的缺點。它將樣品的不同屬性（即各指標(biāo)或各變量）之間的差別等同看待，這一點有時不能滿足實際要求。例如，在教育研究中，經(jīng)常遇到對人的分析和判別，個體的不同屬性對于區(qū)分個體有著不同的重要性。因此，有時需要采用不同的距離函數(shù)。

如果用dij表示第i個樣品和第j個樣品之間的距離，那么對一切i，j和k，dij應(yīng)該滿足如下四個條件：

①當(dāng)且僅當(dāng)i=j時，dij=0

②dij＞0

③dij＝dji（對稱性）

④dij≤dik＋dkj（三角不等式）

顯然，歐氏距離滿足以上四個條件。滿足以上條件的函數(shù)有多種，本節(jié)將要用到的馬氏距離也是其中的一種。

第i個樣品與第j個樣品的馬氏距離dij用下式計算