目錄
- 1 距離公式的基本性質
- 2 常見的距離公式
- 2.1 歐式距離
- 2.2 曼哈頓距離
- 2.3 切比雪夫距離
- 2.4 闵可夫斯基距離
- 3 連續屬性和離散屬性的距離計算
- 4 小結
- 5 其他距離公式
- 5.1 标準化歐氏距離
- 5.2 餘弦距離
- 5.3 漢明距離
- 5.4 傑卡德距離
- 5.5 馬氏距離
1 距離公式的基本性質
在機器學習過程中，對于函數 dist()，若它是一"距離度量" (distance measure)，則需滿足一些基本性質:
直遞性常被直接稱為“三角不等式”。
2 常見的距離公式
2.1 歐式距離
歐氏距離(Euclidean Distance)是最容易直覺了解的距離度量方法，我們國小、國中和高中接觸到的兩個點在空間中的距離一般都是指歐氏距離。
舉例:
X=[[1,1],[2,2],[3,3],[4,4]];
經計算得:
d = 1.4142 2.8284 4.2426 1.4142 2.8284 1.4142 2.2 曼哈頓距離
在曼哈頓街區要從一個十字路口開車到另一個十字路口，駕駛距離顯然不是兩點間的直線距離。這個實際駕駛距離就是“曼哈頓距離(Manhattan Distance)”。曼哈頓距離也稱為“城市街區距離”(City Block distance)。
舉例:
X=[[1,1],[2,2],[3,3],[4,4]];
經計算得:
d = 2 4 6 2 4 2 2.3 切比雪夫距離
國際象棋中，國王可以直行、橫行、斜行，是以國王走一步可以移動到相鄰8個方格中的任意一個。國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？這個距離就叫切比雪夫距離(Chebyshev Distance)。
舉例:
X=[[1,1],[2,2],[3,3],[4,4]];
經計算得:
d = 1 2 3 1 2 1 2.4 闵可夫斯基距離
闵氏距離(Minkowski Distance)不是一種距離，而是一組距離的定義，是對多個距離度量公式的概括性的表述。
兩個n維變量a(x11,x12,…,x1n)與b(x21,x22,…,x2n)間的闵可夫斯基距離定義為：
其中p是一個變參數：
- 當p=1時，就是曼哈頓距離；
- 當p=2時，就是歐氏距離；
- 當p→∞時，就是切比雪夫距離。
根據p的不同，闵氏距離可以表示某一類/種的距離。
小結：
1 闵氏距離，包括曼哈頓距離、歐氏距離和切比雪夫距離，都存在明顯的缺點:
e.g. 二維樣本(身高[機關:cm],體重[機關:kg]),現有三個樣本：a(180,50)，b(190,50)，c(180,60)。
a與b的闵氏距離（無論是曼哈頓距離、歐氏距離或切比雪夫距離）等于a與c的闵氏距離。但實際上身高的10cm并不能和體重的10kg劃等号。
2 闵氏距離的缺點：
(1)将各個分量的量綱(scale)，也就是“機關”相同的看待了;
(2)未考慮各個分量的分布（期望，方差等）可能是不同的。
3 連續屬性和離散屬性的距離計算
我們常将屬性劃分為"連續屬性" (continuous attribute)和"離散屬性" (categorical attribute)，前者在定義域上有無窮多個可能的取值，後者在定義域上是有限個取值.
- 若屬性值之間存在序關系，則可以将其轉化為連續值，例如：身高屬性“高”“中等”“矮”，可轉化為{1, 0.5, 0}。
- 闵可夫斯基距離可以用于有序屬性。
- 若屬性值之間不存在序關系，則通常将其轉化為向量的形式，例如：性别屬性“男”“女”，可轉化為{（1,0），（0,1）}。
4 小結
- 1 距離公式的基本性質：非負性、統一性、對稱性、直遞性
- 2 常見距離公式
- 2.1 歐式距離(Euclidean Distance)：
- 通過距離平方值進行計算
- 2.曼哈頓距離(Manhattan Distance)：
- 通過距離的絕對值進行計算
- 3.切比雪夫距離 (Chebyshev Distance)：
- 次元的最大值進行計算
- 4.闵可夫斯基距離(Minkowski Distance)：
- 當p=1時，就是曼哈頓距離；
- 當p=2時，就是歐氏距離；
- 當p→∞時，就是切比雪夫距離。
- 3 屬性
- 連續屬性
- 離散屬性，
- 存在序關系，可以将其轉化為連續值
- 不存在序關系，通常将其轉化為向量的形式
5 其他距離公式
5.1 标準化歐氏距離
标準化歐氏距離(Standardized EuclideanDistance)是針對歐氏距離的缺點而作的一種改進。
思路：既然資料各維分量的分布不一樣，那先将各個分量都“标準化”到均值、方差相等。
tips: Sk表示各個次元的标準差
如果将方差的倒數看成一個權重，也可稱之為權重歐氏距離(Weighted Euclidean distance)。
舉例:
X=[[1,1],[2,2],[3,3],[4,4]];（假設兩個分量的标準差分别為0.5和1）
經計算得:
d = 2.2361 4.4721 6.7082 2.2361 4.4721 2.2361 5.2 餘弦距離
幾何中，夾角餘弦可用來衡量兩個向量方向的差異；機器學習中，借用這一概念來衡量樣本向量之間的差異，就是餘弦距離(Cosine Distance)。
- 二維空間中向量A(x1,y1)與向量B(x2,y2)的夾角餘弦公式：
- 兩個n維樣本點a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夾角餘弦為：
即：
夾角餘弦取值範圍為[-1,1]。餘弦越大表示兩個向量的夾角越小，餘弦越小表示兩向量的夾角越大。當兩個向量的方向重合時餘弦取最大值1，當兩個向量的方向完全相反餘弦取最小值-1。
舉例:
X=[[1,1],[1,2],[2,5],[1,-4]]
經計算得:
d = 0.9487 0.9191 -0.5145 0.9965 -0.7593 -0.8107 5.3 漢明距離
兩個等長字元串s1與s2的漢明距離(Hamming Distance)為：将其中一個變為另外一個所需要作的最小字元替換次數。
例如:
The Hamming distance between "1011101" and "1001001" is 2.
The Hamming distance between "2143896" and "2233796" is 3.
The Hamming distance between "toned" and "roses" is 3. 随堂練習：
求下列字元串的漢明距離：
1011101與 1001001
2143896與 2233796
irie與 rise 漢明重量：是字元串相對于同樣長度的零字元串的漢明距離，也就是說，它是字元串中非零的元素個數：對于二進制字元串來說，就是 1 的個數，是以 11101 的漢明重量是 4。是以，如果向量空間中的元素a和b之間的漢明距離等于它們漢明重量的差a-b。
應用：漢明重量分析在包括資訊論、編碼理論、密碼學等領域都有應用。比如在資訊編碼過程中，為了增強容錯性，應使得編碼間的最小漢明距離盡可能大。但是，如果要比較兩個不同長度的字元串，不僅要進行替換，而且要進行插入與删除的運算，在這種場合下，通常使用更加複雜的編輯距離等算法。
舉例:
X=[[0,1,1],[1,1,2],[1,5,2]]
注：以下計算方式中，把2個向量之間的漢明距離定義為2個向量不同的分量所占的百分比。
經計算得:
d = 0.6667 1.0000 0.3333 5.4 傑卡德距離
傑卡德相似系數(Jaccard similarity coefficient)：兩個集合A和B的交集元素在A，B的并集中所占的比例，稱為兩個集合的傑卡德相似系數，用符号J(A,B)表示：
傑卡德距離(Jaccard Distance)：與傑卡德相似系數相反，用兩個集合中不同元素占所有元素的比例來衡量兩個集合的區分度：
舉例:
X=[[1,1,0],[1,-1,0],[-1,1,0]]
注：以下計算中，把傑卡德距離定義為不同的次元的個數占“非全零次元”的比例
經計算得:
d = 0.5000 0.5000 1.0000 5.5 馬氏距離
下圖有兩個正态分布圖，它們的均值分别為a和b，但方差不一樣，則圖中的A點離哪個總體更近？或者說A有更大的機率屬于誰？顯然，A離左邊的更近，A屬于左邊總體的機率更大，盡管A與a的歐式距離遠一些。這就是馬氏距離的直覺解釋。
馬氏距離(Mahalanobis Distance)是基于樣本分布的一種距離。
馬氏距離是由印度統計學家馬哈拉諾比斯提出的，表示資料的協方差距離。它是一種有效的計算兩個位置樣本集的相似度的方法。
與歐式距離不同的是，它考慮到各種特性之間的聯系，即獨立于測量尺度。
**馬氏距離定義：**設總體G為m維總體（考察m個名額），均值向量為μ=（μ1，μ2，… …，μm，）`,協方差陣為∑=（σij）,
則樣本X=（X1，X2，… …，Xm，）`與總體G的馬氏距離定義為：
馬氏距離也可以定義為兩個服從同一分布并且其協方差矩陣為∑的随機變量的差異程度：如果協方差矩陣為機關矩陣，馬氏距離就簡化為歐式距離；如果協方差矩陣為對角矩陣，則其也可稱為正規化的歐式距離。
馬氏距離特性：
1.量綱無關，排除變量之間的相關性的幹擾；
2.馬氏距離的計算是建立在總體樣本的基礎上的，如果拿同樣的兩個樣本，放入兩個不同的總體中，最後計算得出的兩個樣本間的馬氏距離通常是不相同的，除非這兩個總體的協方差矩陣碰巧相同；
3 .計算馬氏距離過程中，要求總體樣本數大于樣本的維數，否則得到的總體樣本協方差矩陣逆矩陣不存在，這種情況下，用歐式距離計算即可。
4.還有一種情況，滿足了條件總體樣本數大于樣本的維數，但是協方差矩陣的逆矩陣仍然不存在，比如三個樣本點（3，4），（5，6），（7，8），這種情況是因為這三個樣本在其所處的二維空間平面内共線。這種情況下，也采用歐式距離計算。
歐式距離&馬氏距離：
舉例：
已知有兩個類G1和G2，比如G1是裝置A生産的産品，G2是裝置B生産的同類産品。裝置A的産品品質高（如考察名額為耐磨度X），其平均耐磨度μ1=80，反映裝置精度的方差σ2(1)=0.25;裝置B的産品品質稍差，其平均耐磨損度μ2=75，反映裝置精度的方差σ2(2)=4.
今有一産品G0，測的耐磨損度X0=78，試判斷該産品是哪一台裝置生産的？
直覺地看，X0與μ1（裝置A）的絕對距離近些，按距離最近的原則，是否應把該産品判斷裝置A生産的？
考慮一種相對于分散性的距離，記X0與G1，G2的相對距離為d1，d2,則：
因為d2=1.5 < d1=4，按這種距離準則，應判斷X0為裝置B生産的。
裝置B生産的産品品質較分散，出現X0為78的可能性較大；而裝置A生産的産品品質較集中，出現X0為78的可能性較小。