常用距離計算匯總

1、常用距離計算匯總 在做分類時常常需要估算不同樣本之間的相似性度量(Similarity Measureme nt) ，這 時通常采用的方法就是計算樣本間的距離”(Distanee)。采用什么樣的方法計算距離是 很講究，甚至關(guān)系到分類的正確與否。 本文的目的就是對常用的相似性度量作一個總結(jié)。 本文目錄： 1. 歐氏距離 2. 曼哈頓距離 3. 切比雪夫距離 4閔可夫斯基距離 5. 標準化歐氏距離 6. 馬氏距離 7. 夾角余弦 8. 漢明距離 9. 杰卡德距離 1 0 ; 0 2 D = pdist(X,mi nkowski,2) 結(jié)果： D = 1.00002.00002.2361 5. 標準

2、化歐氏距離(Standardized Euclidean distanee ) (1) 標準歐氏距離的定義 標準化歐氏距離是針對簡單歐氏距離的缺點而作的一種改進方案。標準歐氏距離的 思路：既然數(shù)據(jù)各維分量的分布不一樣，好吧！那我先將各個分量都標準化”到均值、 方差相等吧。均值和方差標準化到多少呢？這里先復(fù)習(xí)點統(tǒng)計學(xué)知識吧，假設(shè)樣本集X 的均值(mean)為m，標準差(standard deviation) 為s，那么X的標準化變量表示 為： 而且標準化變量的數(shù)學(xué)期望為0，方差為1。因此樣本集的標準化過程 (sta ndardizatio n)用公式描述就是： 標準化后的值 =(標準化前的值-分

3、量的均值)/分量的標準差 經(jīng)過簡單的推導(dǎo)就可以得到兩個n維向量a(x11,x12,x1n) 與 b(x21,x22,x2n間的標準化歐氏距離的公式： 如果將方差的倒數(shù)看成是一個權(quán)重，這個公式可以看成是一種加權(quán)歐氏距離 (Weighted Euclidea n dista nee)。 (2) Matlab計算標準化歐氏距離 例子：計算向量(0,0)、(1,0)、(0,2)兩兩間的標準化歐氏距離(假設(shè)兩個分量的標準 差分別為0.5和1) X = 0 0 ; 1 0 ; 0 2 D = pdist(X, seuclidean,0.5,1) 結(jié)果： D = 2.00002.00002.8284 6.

4、馬氏距離(Mahalanobis Distanee) (1) 馬氏距離定義 有M個樣本向量X1Xm，協(xié)方差矩陣記為S，均值記為向量 口，則其中樣本向 量X到u的馬氏距離表示為： 而其中向量Xi與Xj之間的馬氏距離定義為： 畋巧)=廠即“7(禺-與 若協(xié)方差矩陣是單位矩陣(各個樣本向量之間獨立同分布)，則公式就成了： 也就是歐氏距離了。 若協(xié)方差矩陣是對角矩陣，公式變成了標準化歐氏距離。 (2) 馬氏距離的優(yōu)缺點：量綱無關(guān)，排除變量之間的相關(guān)性的干擾。 Matlab 計算(1 2) ，( 1 3) ，( 2 2) ，( 3 1)兩兩之間的馬氏距離 X = 1 2; 1 3; 2 2; 3 1 Y

5、 = pdist(X,mahala no bis) 結(jié)果： Y = 2.34522.00002.34521.22472.44951.2247 7. 夾角余弦(Cosine) 有沒有搞錯，又不是學(xué)幾何，怎么扯到夾角余弦了？各位看官稍安勿躁。幾何中 夾角余弦可用來衡量兩個向量方向的差異，機器學(xué)習(xí)中借用這一概念來衡量樣本向量之 間的差異。 (1) 在二維空間中向量 A(x1,y1)與向量B(x2,y2)的夾角余弦公式： COS0 = (2)兩個n維樣本點a(x11,x12,x1 n和b(x21,x22,，x2n的夾角余弦 類似的，對于兩個 n維樣本點a(x11,x12,x1 n和b(x21,x22,

6、 以使用類似于夾角余弦的概念來衡量它們間的相似程度。 CLb ,x2n),可 kl |6| 即： Xllr 夾角余弦取值范圍為-1,1。夾角余弦越大表示兩個向量的夾角越小，夾角余弦 越小表示兩向量的夾角越大。當(dāng)兩個向量的方向重合時夾角余弦取最大值1，當(dāng)兩個向 量的方向完全相反夾角余弦取最小值-1。 夾角余弦的具體應(yīng)用可以參閱參考文獻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, cosin

7、e)得到的是 1 減夾角余 弦的值 結(jié)果： D = 0.5000-1.0000-0.5000 8. 漢明距離(Hamming distanee) (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 = 0 0 ; 1 0

8、; 0 2; D = PDIST(X, hammi ng) 結(jié)果： D = 0.50000.50001.0000 9. 杰卡德相似系數(shù)(Jaccard similarity coefficient) (1)杰卡德相似系數(shù) 兩個集合A和B的交集元素在A , B的并集中所占的比例，稱為兩個集合的杰卡 德相似系數(shù)，用符號J(A,B)表示。 a n b |AU F| 杰卡德相似系數(shù)是衡量兩個集合的相似度一種指標。 (2) 杰卡德距離 與杰卡德相似系數(shù)相反的概念是杰卡德距離(Jaccard distanee)。杰卡德距離可 用如下公式表示： M u M n s AUB 杰卡德距離用兩個集合中不同元素占所

9、有元素的比例來衡量兩個集合的區(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的杰卡

10、德距離表示為: 卩+孕+ (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.50000.50001.0000 10. 相關(guān)系數(shù)(Correlation coefficient )與相關(guān)距離(Correlation dista nee) (1) 相關(guān)系數(shù)的定義 Cov(xr) _

11、 (x-Ex)(y-r) 相關(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)距離的定義 Dxy = 1 一 PxY (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 , correlati on) 結(jié)果： C = 1.00000.4781 0.478

12、11.0000 D = 0.5219 其中0.4781就是相關(guān)系數(shù)，0.5219是相關(guān)距離 11. 信息熵（In formation En tropy） 信息熵并不屬于一種相似性度量。那為什么放在這篇文章中??？這個。我也 不知道。（丿什 信息熵是衡量分布的混亂程度或分散程度的一種度量。分布越分散（或者說分布越平 均），信息熵就越大。分布越有序（或者說分布越集中），信息熵就越小。 計算給定的樣本集X的信息熵的公式： Entro 參數(shù)的含義： n :樣本集X的分類數(shù) pi: X中第i類元素出現(xiàn)的概率 信息熵越大表明樣本集 S分類越分散，信息熵越小則表明樣本集 X分類越集中。 當(dāng)S中n個分類出現(xiàn)的概率一樣大時（都是 1/n ），信息熵取最大值log 2（n）。當(dāng)X只 有一個分類時，信息熵取最小值