轉(zhuǎn)自：http://www.cnblogs.com/heaad/archive/2011/03/08/1977733.html
沒有仔細(xì)看烟央，先留著戳粒，有空在手機(jī)上再看
在做分類時常常需要估算不同樣本之間的相似性度量(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)三維空間兩點a(x1,y1,z1)與b(x2,y2,z2)間的歐氏距離：
(3)兩個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 = [0 0 ; 1 0 ; 0 2]
D = pdist(X,'euclidean')
結(jié)果：
D = 1.0000 2.0000 2.2361
曼哈頓距離(Manhattan Distance)
從名字就可以猜出這種距離的計算方法了沽甥。想象你在曼哈頓要從一個十字路口開車到另外一個十字路口声邦，駕駛距離是兩點間的直線距離嗎？顯然不是摆舟，除非你能穿越大樓亥曹。實際駕駛距離就是這個“曼哈頓距離”。而這也是曼哈頓距離名稱的來源恨诱， 曼哈頓距離也稱為城市街區(qū)距離(City Block distance)媳瞪。
(1)二維平面兩點a(x1,y1)與b(x2,y2)間的曼哈頓距離
(2)兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的曼哈頓距離
(3) Matlab計算曼哈頓距離
例子：計算向量(0,0)、(1,0)照宝、(0,2)兩兩間的曼哈頓距離
X = [0 0 ; 1 0 ; 0 2]
D = pdist(X, 'cityblock')
結(jié)果：
D = 1 2 3
切比雪夫距離 ( Chebyshev Distance )
國際象棋玩過么蛇受？國王走一步能夠移動到相鄰的8個方格中的任意一個。那么國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步厕鹃？自己走走試試兢仰。你會發(fā)現(xiàn)最少步數(shù)總是max( | x2-x1 | , | y2-y1 | ) 步 。有一種類似的一種距離度量方法叫切比雪夫距離剂碴。
(1)二維平面兩點a(x1,y1)與b(x2,y2)間的切比雪夫距離
(2)兩個n維向量a(x11,x12,…,x1n)與 b(x21,x22,…,x2n)間的切比雪夫距離
這個公式的另一種等價形式是
看不出兩個公式是等價的把将？提示一下：試試用放縮法和夾逼法則來證明。
(3)Matlab計算切比雪夫距離
例子：計算向量(0,0)忆矛、(1,0)察蹲、(0,2)兩兩間的切比雪夫距離
X = [0 0 ; 1 0 ; 0 2]
D = pdist(X, 'chebychev')
結(jié)果：
D = 1 2 2
閔可夫斯基距離(Minkowski Distance)
閔氏距離不是一種距離，而是一組距離的定義。
(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)閔氏距離的缺點
閔氏距離儿捧，包括曼哈頓距離荚坞、歐氏距離和切比雪夫距離都存在明顯的缺點。
舉個例子：二維樣本(身高,體重)菲盾，其中身高范圍是150190颓影，體重范圍是5060，有三個樣本：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 = [0 0 ; 1 0 ; 0 2]
D = pdist(X,'minkowski',2)
結(jié)果：
D = 1.0000 2.0000 2.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)化”到均值、方差相等吧仑濒。均值和方差標(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)用公式描述就是：
標(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)泵喘。
(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 2]
D = pdist(X, 'seuclidean',[0.5,1])
結(jié)果：
D = 2.0000 2.0000 2.8284
馬氏距離(Mahalanobis Distance)
（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計算(1 2)绒极，( 1 3)骏令，( 2 2)，( 3 1)兩兩之間的馬氏距離
X = [1 2; 1 3; 2 2; 3 1]
Y = pdist(X,'mahalanobis')
結(jié)果：
Y = 2.3452 2.0000 2.3452 1.2247 2.4495 1.2247
夾角余弦(Cosine)
有沒有搞錯垄提，又不是學(xué)幾何榔袋，怎么扯到夾角余弦了？各位看官稍安勿躁铡俐。幾何中夾角余弦可用來衡量兩個向量方向的差異凰兑，機(jī)器學(xué)習(xí)中借用這一概念來衡量樣本向量之間的差異。
(1)在二維空間中向量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。
夾角余弦的具體應(yīng)用可以參閱參考文獻(xiàn)[1]旅择。
(3)Matlab計算夾角余弦
例子：計算(1,0)惭笑、( 1,1.732)、( -1,0)兩兩間的夾角余弦
X = [1 0 ; 1 1.732 ; -1 0]
D = 1- pdist(X, 'cosine') % Matlab中的pdist(X, 'cosine')得到的是1減夾角余弦的值
結(jié)果：
D = 0.5000 -1.0000 -0.5000
漢明距離(Hamming distance)
(1)漢明距離的定義
兩個等長字符串s1與s2之間的漢明距離定義為將其中一個變?yōu)榱硗庖粋€所需要作的最小替換次數(shù)生真。例如字符串“1111”與“1001”之間的漢明距離為2沉噩。
應(yīng)用：信息編碼（為了增強(qiáng)容錯性，應(yīng)使得編碼間的最小漢明距離盡可能大）柱蟀。
(2)Matlab計算漢明距離
Matlab中2個向量之間的漢明距離的定義為2個向量不同的分量所占的百分比川蒙。
例子：計算向量(0,0)、(1,0)长已、(0,2)兩兩間的漢明距離
X = [0 0 ; 1 0 ; 0 2];
D = PDIST(X, 'hamming')
結(jié)果：
D = 0.5000 0.5000 1.0000
杰卡德相似系數(shù)(Jaccard similarity coefficient)
(1) 杰卡德相似系數(shù)
兩個集合A和B的交集元素在A畜眨，B的并集中所占的比例昼牛，稱為兩個集合的杰卡德相似系數(shù)，用符號J(A,B)表示康聂。
杰卡德相似系數(shù)是衡量兩個集合的相似度一種指標(biāo)贰健。
(2) 杰卡德距離
與杰卡德相似系數(shù)相反的概念是杰卡德距離(Jaccard distance)。杰卡德距離可用如下公式表示：
杰卡德距離用兩個集合中不同元素占所有元素的比例來衡量兩個集合的區(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 = [1 1 0; 1 -1 0; -1 1 0]
D = pdist( X , 'jaccard')
結(jié)果
D =0.5000 0.5000 1.0000
相關(guān)系數(shù) ( Correlation coefficient )與相關(guān)距離(Correlation distance)
(1) 相關(guān)系數(shù)的定義
相關(guān)系數(shù)是衡量隨機(jī)變量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 6]
C = corrcoef( X' ) %將返回相關(guān)系數(shù)矩陣
D = pdist( X , 'correlation')
結(jié)果：
C =
1.0000 0.4781
0.4781 1.0000
D =0.5219
其中0.4781就是相關(guān)系數(shù)娜膘，0.5219是相關(guān)距離。
信息熵(Information Entropy)
信息熵并不屬于一種相似性度量优质。那為什么放在這篇文章中翱⑻啊？這個巩螃。演怎。。我也不知道避乏。 (╯▽╰)
信息熵是衡量分布的混亂程度或分散程度的一種度量爷耀。分布越分散(或者說分布越平均)，信息熵就越大淑际。分布越有序（或者說分布越集中）畏纲，信息熵就越小扇住。
計算給定的樣本集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只有一個分類時女阀，信息熵取最小值0
參考資料：
[1]吳軍. 數(shù)學(xué)之美 系列 12 - 余弦定理和新聞的分類.
http://www.google.com.hk/ggblog/googlechinablog/2006/07/12_4010.html
[2] Wikipedia. Jaccard index.
http://en.wikipedia.org/wiki/Jaccard_index
[3] Wikipedia. Hamming distance
http://en.wikipedia.org/wiki/Hamming_distance
[4] 求馬氏距離（Mahalanobis distance ）matlab版
http://junjun0595.blog.163.com/blog/static/969561420100633351210/
[5] Pearson product-moment correlation coefficient
http://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient
