閱讀原文

相似性度量與距離

分類時(shí)常需要估算不同樣本之間的 相似性度量 (Similarity Measurement)，這時(shí)通常采用的方法就是計(jì)算樣本間的 “距離” (Distance)。采用什么方法計(jì)算距離很講究，甚至關(guān)系到分類的正確與否。

1. 歐幾里得距離 Euclidean Distance

兩點(diǎn)形成的 直線的距離

歐氏距離

X = [0, 0; 1, 0; 0, 2]; % A,B,C 三點(diǎn)距離比較順序 (A,B) (A,C) (B,C) 
D = pdist(X, 'euclidean'); % 1.0000    2.0000    2.2361

2. 曼哈頓距離 Manhattan/Cityblock Distance

兩點(diǎn)所形成的線段 對(duì)軸產(chǎn)生的投影的距離總和。

城市街區(qū)距離。

坐標(biāo)（x₁, y₁）的點(diǎn) P₁ 與坐標(biāo)（x₂, y₂）的點(diǎn) P₂ 的曼哈頓距離為：

曼哈頓距離

X = [0, 0; 1, 0; 0, 2]; % A,B,C 三點(diǎn)距離比較順序 (A,B) (A,C) (B,C) 
D = pdist(X, 'cityblock'); % 1     2     3

3. 切比雪夫距離 Chebyshev Distance

兩點(diǎn)的 各坐標(biāo)數(shù)值差的最大值。

maximum coordinate difference 最大的坐標(biāo)軸差異。

(x₁,y₁) 和 (x₂,y₂) 的切比雪夫距離為 max(|x₂-x₁|,|y₂-y₁|)。

切比雪夫距離

X = [0, 0; 1, 0; 0, 2]; % A,B,C 三點(diǎn)距離比較順序 (A,B) (A,C) (B,C) 
D = pdist(X, 'chebychev'); % 1     2     2

4. 閔可夫斯基距離 Minkowski Distance

閔氏距離不是一種距離，而是一組距離的定義。

歐式距離和曼哈頓距離的推廣，p 是可變參數(shù)。

閔氏距離

其中 p 是可變參數(shù)。

• 當(dāng) p = 1 時(shí)，曼哈頓距離
• 當(dāng) p = 2 時(shí)，歐氏距離
• 當(dāng) p→∞ 時(shí)，切比雪夫距離

X = [0, 0; 1, 0; 0, 2]; % A,B,C 三點(diǎn)距離比較順序 (A,B) (A,C) (B,C) 
D = pdist(X, 'minkowski');       % 默認(rèn)p=2，為歐式距離
D1 = pdist(X, 'minkowski', 1);   % p=1，曼哈頓距離
D2 = pdist(X, 'minkowski', 2);   % p=2，歐式距離
D3 = pdist(X, 'minkowski', 3);   % p=3，閔3距離
D99 = pdist(X, 'minkowski', 99); % p=99，閔99距離
disp(D);                         % 1.0000    2.0000    2.2361
disp(D1);                        % 1         2         3
disp(D2);                        % 1.0000    2.0000    2.2361
disp(D3);                        % 1.0000    2.0000    2.0801
disp(D99);                       % 1         2         2  (接近切比雪夫)

5. 標(biāo)準(zhǔn)化歐氏距離 Standardized Euclidean distance

標(biāo)準(zhǔn)化歐氏距離先將 各個(gè)分量 都 “標(biāo)準(zhǔn)化” 到均值、方差相等。
因?yàn)闅W式距離中不同分量可能是不同的量綱，不能“相同看待”（閔式距離的缺點(diǎn)）

解決 各分量的 數(shù)據(jù)量綱差別大的問(wèn)題，類比過(guò)擬合。

分量標(biāo)準(zhǔn)化，m 均值，s 標(biāo)準(zhǔn)差

標(biāo)準(zhǔn)化公式

兩個(gè) n 維向量：a(x₁₁, x₁₂, … , x_1n) 與 b(x₂₁, x₂₂, … , x_2n)

標(biāo)準(zhǔn)化歐氏距離

公式解釋：
k = 1，x₁₁, x₂₁ 這組分量求出 m₁, s₁，然后用標(biāo)準(zhǔn)化公式得到 第1維 的標(biāo)準(zhǔn)化向量；
k = 2，x₁₂, x₂₂ 這組分量求出 m₂, s₂，然后用標(biāo)準(zhǔn)化公式得到 第2維 的標(biāo)準(zhǔn)化向量；
相當(dāng)于，把各個(gè)分量的值都限制在 [-1, 1]。

標(biāo)準(zhǔn)化后，各分量的期望和方差都相同，m = 0，s = 1。

X = [0, 0; 1, 0; 0, 2]; % A,B,C 三點(diǎn)距離比較順序 (A,B) (A,C) (B,C) 
D = pdist(X, 'seuclidean');                % 默認(rèn)采用 實(shí)際標(biāo)準(zhǔn)差
D1 = pdist(X, 'seuclidean', [0.5, 1]);     % 自定義標(biāo)準(zhǔn)差
D2 = pdist(X, 'seuclidean', std(X, 0, 1)); % 使自定義標(biāo)準(zhǔn)差 = 實(shí)際標(biāo)準(zhǔn)差
disp(D)  % 1.7321    1.7321    2.4495
disp(D1) % 2.0000    2.0000    2.8284
disp(D2) % 1.7321    1.7321    2.4495

6. 馬哈拉諾比斯距離 Mahalanobis Distance

馬氏距離 表示數(shù)據(jù)的 協(xié)方差距離，其考慮到各種特性之間的聯(lián)系。

協(xié)方差，排除變量之間的相關(guān)性干擾。

設(shè) M 個(gè)樣本向量 X₁ ~ X_m，協(xié)方差矩陣記為 S，均值記為向量 μ。
則其中樣本向量 X 到 μ 的馬氏距離為：

X 到 μ 的馬氏距離

其中向量 X_i 與 X_j 間的馬氏距離為：

Xi 與 Xj 間的馬氏距離

若協(xié)方差矩陣是單位矩陣（各個(gè)樣本向量之間獨(dú)立同分布）,則公式就成了：

S = 1

即為歐氏距離。

若協(xié)方差矩陣是 對(duì)角矩陣，公式變成了標(biāo)準(zhǔn)化歐氏距離。

X = [1 2; 1 3; 2 2; 3 1]; % A,B,C,D四點(diǎn)，(A,B)(A,C)(A,D)(B,C)(B,D)(C,D)
D = pdist(X,'mahalanobis'); % 2.3452    2.0000    2.3452    1.2247    2.4495    1.2247

7. 夾角余弦

幾何中夾角余弦可用來(lái)衡量 兩個(gè)向量方向的差異，
機(jī)器學(xué)習(xí)中借用這一概念來(lái)衡量樣本向量之間的差異。

向量方向差異：[-1, 1]

① 二維空間中向量 A(x₁,y₁) 與向量 B(x₂,y₂) 的夾角余弦公式：

二維夾角

② n 維樣本點(diǎn) a(x₁₁,x₁₂,…,x_1n) 和 b(x₂₁,x₂₂,…,x_2n)：

n 維夾角

X = [1 0; 1 1.732; -1 0]; % A,B,C三點(diǎn) (A,B)(A,C)(B,C)
D = pdist(X, 'cosine'); % matlab中該函數(shù)求得結(jié)果其實(shí)是 1 - cos(θ)
disp(D);   % 0.5000    2.0000    1.5000
disp(1-D); % 0.5000   -1.0000   -0.5000 得到cos(θ)

8. 漢明距離

① 兩個(gè)等長(zhǎng)字符串 s₁ 與 s₂ 之間的 漢明距離 定義為 將其中一個(gè)變?yōu)榱硗庖粋€(gè)所需要作的最小替換次數(shù)。例如字符串“1111”與“1001”之間的漢明距離為2。

一個(gè)字符串 s₁ 變化為另一個(gè)字符串 s₂ 需要的最小替換次數(shù)。

應(yīng)用：信息編碼（為了增強(qiáng)容錯(cuò)性，應(yīng)使得編碼間的最小漢明距離盡可能大）

② Matlab Hamming distance, percentage of coordinates that differ

X = [1 0; 1 1.732; -1 0]; % A,B,C三點(diǎn) (A,B)(A,C)(B,C)
D = pdist(X, 'hamming'); % 0.5000    0.5000    1.0000

9. 杰卡德距離/杰卡德相似系數(shù) Jaccard similarity coefficient

① 杰卡德相似系數(shù)：兩個(gè)集合 A 和 B 的交集元素在 A，B 的并集中所占的比例，稱為兩個(gè)集合的杰卡德相似系數(shù)，用符號(hào) J(A,B) 表示。

杰卡德相似系數(shù)

杰卡德相似系數(shù)是 衡量?jī)蓚€(gè)集合相似度 的一種指標(biāo)。

杰卡德相似系數(shù)：集合 ∩ / ∪

② 杰卡德距離與杰卡德相似系數(shù)相反：

杰卡德距離

杰卡德相似系數(shù)：1 - 集合 ∩ / ∪

用兩個(gè)集合中不同元素占所有元素的比例 來(lái) 衡量?jī)蓚€(gè)集合的區(qū)分度。

③ Matlab Jaccard Distance, percentage of nonzero coordinates that differ

非零的坐標(biāo)軸 數(shù)值不同 所占的比例。

X = [1 1 0; 1 -1 0; -1 1 0]; % (A,B)1/2 (A,C)1/2 (B,C)2/2
D = pdist(X, 'jaccard'); % 0.5000    0.5000    1.0000

X = [1 1 1; 1 2 1; 1 2 2]; % (A,B)1/3 (A,C)2/3 (B,C)1/3
D = pdist(X, 'jaccard'); % 0.3333    0.6667    0.3333

10. 相關(guān)系數(shù)/相關(guān)距離 Correlation Coefficient / Distance

① 相關(guān)系數(shù)的定義：

相關(guān)系數(shù)

相關(guān)系數(shù)是 衡量隨機(jī)變量 X 與 Y 相關(guān)程度 的一種方法，相關(guān)系數(shù)的取值范圍是[-1,1]。

相關(guān)系數(shù)的絕對(duì)值越大，則表明 X 與 Y 相關(guān)度越高。
當(dāng) X 與 Y 線性相關(guān)時(shí)，相關(guān)系數(shù)取值為 1（正線性相關(guān)）或 -1（負(fù)線性相關(guān)）

② 相關(guān)距離的定義：

相關(guān)距離

X = [1 2 3 4 ; 3 8 7 6];
C = corrcoef(X'); % 返回相關(guān)系數(shù)矩陣
% 1.0000    0.4781
% 0.4781    1.0000

D = pdist(X, 'correlation'); % 0.5219

% 0.4781就是相關(guān)系數(shù)，0.5219是相關(guān)距離