Distance Classification
Distance
歐氏距離(Euclidean Distance)
闵可夫斯基距離（Minkowski distance）
曼哈頓距離(Manhattan distance)
切比雪夫距離 ( Chebyshev distance )
标準化歐氏距離(Standardized Euclidean distance )
馬氏距離(Mahalanobis Distance)
漢明距離(Hamming distance)
餘弦相似度（Cosine Similarity）
傑卡德相似系數(Jaccardsimilarity coefficient)
Reference
由于最近在做故障診斷相關研究，不斷學習各種算法，發現在很多算法裡面都用到了Distance來定義各種變量之間的關系，确定之間的相關類名額。且在運用算法做分類時需要估不同樣本之間的相似性度量(Similarity Measurement，SM)，這時通常采用的方法就是計算樣本間的“距離”(Distance)。在下面一 一道來！
這可太有意思了，不經讓我去尋找，究竟有多少種Distance可以運用在不同的算法裡面呢？在不同算法裡的計算方式是否有所不同？在計算效率上哪種Distance更優？哪種Distance在算法中運作速度更快，效果更好呢？什麼Distance能夠使得你的分類或聚類效果更加優秀呢？…
針對太多了疑問和不解，那麼現在開始做做Distance的相關解讀吧！
首先，了解一下距離計算（聚類分析）
對于函數Dist( ; )，倘若它是一個“距離度量”（distance measure），則需要滿足一些基本性質：
相信歐氏距離(EuclideanDistance)是很多人都知道且用到的一個距離計算方法，且簡單高效。
在我們做聚類分析中常用的基于歐幾裡得距離的相似矩陣作為一種可行的方法。
歐幾裡得
簡而言之，就是歐式空間中，兩點之間的距離公式。
在數學中，歐幾裡得距離或歐幾裡得度量是歐幾裡得空間中兩點間“普通”（即直線）距離。使用這個距離，歐氏空間成為度量空間。相關聯的範數稱為歐幾裡得範數。較早的文獻稱之為畢達哥拉斯度量。
歐幾裡得度量（euclidean metric）（也稱歐氏距離）是一個通常采用的距離定義，指在m維空間中兩個點之間的真實距離，或者向量的自然長度（即該點到原點的距離）。在二維和三維空間中的歐氏距離就是兩點之間的實際距離。
—來源于網絡
原理公式
下面簡述下計算公式：
二維空間的公式
其中，
簡單的說，就是求其二維平面上兩點之間的模長。—>本人心得
三維空間的公式
和二維空間一樣，隻不過多加了一個坐标系的值
再簡單的說，同理就是求其三維平面上兩點之間的模長。—>本人心得
n維空間的公式
将每個次元的求其模長。 及其不标準描述，别說我說的
拓展内容：
所謂歐氏距離變換，是指對于一張二值圖像（在此我們假定白色為前景色，黑色為背景色），将前景中的像素的值轉化為該點到達最近的背景點的距離。
歐氏距離變換在數字圖像進行中的應用範圍很廣泛，尤其對于圖像的骨架提取，是一個很好的參照。
應用層面
歐氏距離看作信号的相似程度。 距離越近就越相似，就越容易互相幹擾，誤碼率就越高。
最近看了一篇 Paper，大佬級别的，引用率很高。講的是關于歐幾裡得距離（歐氏距離）作為主成分分析（PCA）的相似性度量。理論性很強，本人菜雞一個，目前讀的有些老火，上傳了網盤，論文可在這裡下載下傳【提取碼：fvj2】。
《Euclidean Distance as a Similarity Metric for Principal Component Analysis》–KIMBERLY L. ELMORE
cite：[1] Elmore K L , Richman M B . Euclidean Distance as a Similarity Metric for Principal Component Analysis[J]. Monthly Weather Review, 2010, 129(3):540-549.
闵氏距離不是一種距離，而是一組距離的定義。是歐氏空間中的一種測度，被看做是歐氏距離的一種推廣，歐氏距離是闵可夫斯基距離的一種特殊情況。
闵氏空間指狹義相對論中由一個時間維和三個空間維組成的時空，為俄裔德國數學家闵可夫斯基(H.Minkowski,1864-1909)最先表述。他的平坦空間（即假設沒有重力，曲率為零的空間）的概念以及表示為特殊距離量的幾何學是與狹義相對論的要求相一緻的。闵可夫斯基空間不同于牛頓力學的平坦空間。
闵可夫斯基
一個小故事：
阿爾伯特·愛因斯坦在瑞士蘇黎世聯邦科技大學(Eidgen?ssische Technische Hochschule, ETH; Swiss Federal Institute of Technology)時期的數學老師赫爾曼·闵可夫斯基在愛因斯坦提出狹義相對論之後，于1907年将愛因斯坦與亨德裡克·洛侖茲的理論結果重新表述成(3+1)維的時空，其中光速在各個慣性參考系皆為定值，這樣的時空即以其為名，稱為闵可夫斯基時空，或稱闵可夫斯基空間。
官方原理：
闵氏距離有時也指時空間隔，關于時空間隔的内容可跳轉看詞條解釋。
設n維空間中有兩點坐标x, y，v為常數，闵式距離定義為
（1）闵氏距離與特征參數的量綱有關，有不同量綱的特征參數的闵氏距離常常是無意義的。
（2）闵氏距離沒有考慮特征參數間的相關性，而馬哈拉諾比斯距離解決了這個問題。
當v = 1
可得到絕對值距離，也叫曼哈頓距離（Manhattan distance）、出租汽車距離或街區距離（city block distance）。在二維空間中可以看出，這種距離是計算兩點之間的直角邊距離，相當于城市中出租汽車沿城市街道拐直角前進而不能走兩點連接配接間的最短距離。絕對值距離的特點是各特征參數以等權參與進來，是以也稱等混合距離。
當v → ∞
得到切比雪夫距離，下面再做介紹。
我們常常将屬性劃分為“連續屬性”（continuous attribute）和“離散屬性”（categorical attribute），前者在定義域上有無窮多個可能的取值，後者在定義域上式有限個取值。然而，在讨論距離計算的時候，屬性上是否定義“序”關系更為重要。例如，定義域在{1，2，3}的離散屬性和連續屬性的性質更為接近一些，能直接在屬性值上計算距離：“1”和“2”比較接近、與“3”比較遠，這樣的屬性稱為“有序屬性”（ordinal attribute）；而定義為{火車、飛機、船}這樣的離散屬性則不能直接在屬性值上計算距離，稱為“無序屬性”（non-ordinal attribute）。在這裡，闵可夫斯基距離可用于有序距離，
連續屬性亦成為“數值屬性”（numerical attribute）
離散屬性亦成為“列名屬性”（nominal attribute）
簡單總結：闵可夫斯基距離在面對離散資料集的時候則不适用，而對于有序數列資料集可用。
—來自菜雞解釋，不對可忽略。
由上可知，在闵可夫斯基距離中，當v = 1時，可得到絕對值距離，也叫曼哈頓距離（Manhattan distance）、出租汽車距離或街區距離（city block distance）。
同樣也是由上面那位圖檔上的大佬建立的，這裡就不放Photo了
計程車幾何或曼哈頓距離（Manhattan Distance）是由十九世紀的赫爾曼·闵可夫斯基所創詞彙 ，是種使用在幾何度量空間的幾何學用語，用以标明兩個點在标準坐标系上的絕對軸距總和。
官方解釋很好了解（附上了）
曼哈頓距離
上圖中紅線代表曼哈頓距離，綠色代表歐氏距離，也就是直線距離，而藍色和黃色代表等價的曼哈頓距離。曼哈頓距離——兩點在南北方向上的距離加上在東西方向上的距離，即
對于一個具有正南正北、正東正西方向規則布局的城鎮街道，從一點到達另一點的距離正是在南北方向上旅行的距離加上在東西方向上旅行的距離，是以，曼哈頓距離又稱為計程車距離。曼哈頓距離不是距離不變量，當坐标軸變動時，點間的距離就會不同。曼哈頓距離示意圖在早期的計算機圖形學中，螢幕是由像素構成，是整數，點的坐标也一般是整數，原因是浮點運算很昂貴，很慢而且有誤差，如果直接使用AB的歐氏距離（歐幾裡德距離：在二維和三維空間中的歐氏距離的就是兩點之間的距離），則必須要進行浮點運算，如果使用AC和CB，則隻要計算加減法即可，這就大大提高了運算速度，而且不管累計運算多少次，都不會有誤差。
菜雞了解：曼哈頓距離在處理大規模運算的時候，将一些需要用到浮點運算的地方（歐氏距離運算）換成加減運算，在處理器較強的現在，（不懂算法提速的我），或許還會提高運算速度(雖然沒有試過，大膽假設一波，再去補補Paper)。在二維三維平面上本來走直線的，現在通過走曲折的“直線”減小計算難度，但增加了計算過程，最終的結果是使得運算速度提速了！！！很神奇
煮個栗子吧
現在請出靈魂畫師
此時的曼哈頓距離
關于曼哈頓距離的應用，搜羅了大部分Paper，發現都是在計算機領域的應用較多，比如提高改進GPU運算性能、算法層面的性能提升、CV等等…太多了
這裡有幾篇引用率且水準較高的Paper可讀一讀。
本菜在不斷摸索當中
[1] Chang D J , Desoky A H , Ming O , et al. Compute Pairwise Manhattan Distance and Pearson Correlation Coefficient of Data Points with GPU[C]// 10th ACIS International Conference on Software Engineering, Artificial Intelligences, Networking and Parallel/Distributed Computing, SNPD 2009, in conjunction with 3rd International Workshop on e-Activity, IWEA 2009, 1st International Workshop on Enterprise Architecture Challenges and Responses, WEACR 2009, Catholic University of Daegu, Daegu, Korea, 27-29 May 2009. IEEE, 2009.
[2] Mattausch H J , Omori N , Fukae S , et al. Fully-parallel pattern-matching engine with dynamic adaptability to Hamming or Manhattan distance[C]// VLSI Circuits Digest of Technical Papers, 2002. Symposium on. IEEE, 2002.
[3] Oike Y , Ikeda M , Asada K . A high-speed and low-voltage associative co-processor with exact Hamming/Manhattan-distance estimation using word-parallel and hierarchical search architecture[J]. IEEE Journal of Solid-State Circuits, 2004, 39(8):1383-1387.
深入了解後再細挖（待更新）。
在數學中，切比雪夫距離（Chebyshev distance）或是L ∞
度量，是向量空間中的一種度量，二個點之間的距離定義是其各坐标數值差絕對值的最大值。以數學的觀點來看，切比雪夫距離是由一緻範數（uniform norm）（或稱為上确界範數）所衍生的度量，也是超凸度量（injective metric space）的一種。(—來自網絡)
最形象的一個比如應該當屬“國際象棋”，相信有大部分人像本弱雞一樣不會下國際象棋，下面直接講原理。
國際象棋棋盤上二個位置間的切比雪夫距離是指王要從一個位子移至另一個位子需要走的步數。由于王可以往斜前或斜後方向移動一格，是以可以較有效率的到達目的的格子。下圖是棋盤上所有位置距f6位置的切比雪夫距離。
一維空間中，所有的Lp度量都是一樣的------------（即為二坐标差的絕對值）。
也即是，求其兩點之間橫縱坐标x ， y對應差的絕對值，在選出最大的一個作為它們之間的切比雪夫距離。
炒個栗子吧
此時又得拿出靈魂畫師的水準
此時，
（圖檔來自
網絡）
是以平面的切比雪夫距離可以視為平面曼哈頓距離旋轉再放大後的結果。
關于切比雪夫距離，在聚類上有所用到，在圖象識别領域，改進的切比雪夫相似性度量來替代聚類分析中現有的度量（如歐幾裡得和标準切比雪夫），通過改進的算法應用到醫學的圖像識别上，效果很好。所提出的措施産生最小的目标函數值，并在疊代次數最少時收斂。這裡推薦一篇Paper.
Mousa A , Yusof Y . An improved Chebyshev distance metric for clustering medical images[C]// American Institute of Physics Conference Series. AIP Publishing LLC, 2015:040020.
标準歐氏距離的定義:
标準化歐氏距離是針對簡單歐氏距離的缺點而作的一種改進方案。
本菜了解：針對多元變量，将輸入樣本X XX進行标準化的歐式距離計算操作。
首先，将各個分量都“标準化”到均值、方差相等。
菜雞了解：
在這裡的分量标準差s k ，言簡意赅的了解就是，比如二維平面上兩個點A（2,5）,B（5,1），按照曼哈頓距離的方式看（當然是我類比），組成一個長方體（下圖隻花了一個三角形），黃色的線計算為歐氏距離的方式。
但在這裡我們要得到s k ，那麼計算或許如下：
在機器學習中，聚類用的标準化歐氏距離比較多，在面對求解長方形區域聚類的時候，普通的距離無法滿足相似性度量，這是就得采用标準化歐氏距離來度量。
這裡推薦一本書。
Chikodili N B , MD Abdulmalik, Abisoye O A , et al. Outlier Detection in Multivariate Time Series Data Using a Fusion of K-Medoid, Standardized Euclidean Distance and Z-Score[M]. 2021.
馬氏距離(Mahalanobis distance)是由印度統計學家馬哈拉諾比斯(P. C. Mahalanobis)提出的，表示點與一個分布之間的距離。它是一種有效的計算兩個未知樣本集的相似度的方法。與歐氏距離不同的是，它考慮到各種特性之間的聯系（例如：一條關于身高的資訊會帶來一條關于體重的資訊，因為兩者是有關聯的），并且是尺度無關的(scale-invariant)，即獨立于測量尺度。(百科也很詳細)
生來清貧，沒有頭像，隻留下一本書
馬氏距離(Mahalanobis
Distance)是度量學習中一種常用的距離名額，同歐氏距離、曼哈頓距離、漢明距離等一樣被用作評定資料之間的相似度名額。但卻可以應對高維線性分布的資料中各次元間非獨立同分布的問題。(來自知乎大佬)
什麼是馬氏距離？
簡單來說就是，作為一種距離的度量，可以看作是歐氏距離的一種修正，修正了歐式距離中各個次元尺度不一緻且相關的問題。
單個資料點的馬氏距離
資料點x , y之間的馬氏距離
其中Σ是多元随機變量的協方差矩陣，μ為樣本均值，如果協方差矩陣是機關向量，也就是各次元獨立同分布，馬氏距離就變成了歐氏距離。
馬氏距離實際意義:
那麼馬氏距離就能能幹什麼？它比歐氏距離好在哪裡？再炒幾個栗子
歐式距離近就一定相似？
先舉個比較常用的例子，身高和體重，這兩個變量擁有不同的機關标準，也就是有不同的scale。比如身高用毫米計算，而體重用千克計算，顯然差10mm的身高與差10kg的體重是完全不同的。但在普通的歐氏距離中，這将會算作相同的差距。
歸一化後歐氏距離近就一定相似？
當然我們可以先做歸一化來消除這種次元間scale不同的問題，但是樣本分布也會影響分類
舉個一維的栗子，現在有兩個類别，統一機關，第一個類别均值為0，方差為0.1，第二個類别均值為5，方差為5。那麼一個值為2的點屬于第一類的機率大還是第二類的機率大？距離上說應該是第一類，但是直覺上顯然是第二類，因為第一類不太可能到達2這個位置。
是以，在一個方差較小的次元下很小的差别就有可能成為離群點。就像下圖一樣，A與B相對于原點的距離是相同的。但是由于樣本總體沿着橫軸分布，是以B點更有可能是這個樣本中的點，而A則更有可能是離群點。
算上次元的方差就夠了？
還有一個問題——如果次元間不獨立同分布，樣本點一定與歐氏距離近的樣本點同類的機率更大嗎？
可以看到樣本基本服從f(x) = x的線性分布，A與B相對于原點的距離依舊相等，顯然A更像是一個離群點
即使資料已經經過了标準化，也不會改變AB與原點間距離大小的互相關系。是以要本質上解決這個問題，就要針對主成分分析（PCA）中的主成分來進行标準化。
馬氏距離的幾何意義
上面搞懂了，馬氏距離就好了解了，隻需要将變量按照主成分進行旋轉，讓次元間互相獨立，然後進行标準化，讓次元同分布就OK了。
由主成分分析可知，由于主成分就是特征向量方向，每個方向的方差就是對應的特征值，是以隻需要按照特征向量的方向旋轉，然後縮放特征值倍就可以了，可以得到以下的結果：
離群點就被成功分離，這時候的歐式距離就是馬氏距離。（很妙啊！）
馬氏距離的問題
1.協方差矩陣必須滿秩
裡面有求逆矩陣的過程，不滿秩不行，要求資料要有原次元個特征值，如果沒有可以考慮先進行PCA，這種情況下PCA不會損失資訊
2.不能處理非線性流形(manifold)上的問題
隻對線性空間有效，如果要處理流形，隻能在局部定義，可以用來建立KNN圖
不能處理非線性流形(manifold)上的問題
漢明距離是使用在資料傳輸差錯控制編碼裡面的，漢明距離是一個概念，它表示兩個（相同長度）字對應位不同的數量，我們以d （ x , y ）表示兩個字x , y之間的漢明距離。對兩個字元串進行異或運算，并統計結果為1 11的個數，那麼這個數就是漢明距離。
理查德·衛斯裡·漢明
原理
在資訊論中，兩個等長字元串之間的漢明距離是兩個字元串對應位置的不同字元的個數。換句話說，它就是将一個字元串變換成另外一個字元串所需要替換的字元個數。例如：
1011101 與 1001001 之間的漢明距離是 2
2143896 與 2233796 之間的漢明距離是 3
“toned” 與 “roses” 之間的漢明距離是 3
可視化的煮個栗子吧
漢明距離多用于編碼等資訊論方面的計算，對于為什麼上面的漢明距離結果為此，簡單來看，拿出我靈魂畫手工筆
這樣來看是不是更好了解一點呢。隻需要從字元串中尋找出不同的項，不同項的數量就為之間的漢明距離。
這裡寫了一個小的求漢明距離的Python封裝代碼（直接調用即可）：
def HammingDistance(x, y):
"""傳回等長序列之間的漢明距離"""
if len(x) != len(y):
raise ValueError("對于長度不等的序列未定義")
return sum(t1 != t2 for t1, t2 in zip(x, y)) 最小漢明距離
例如：(00)與(01)的距離是1，(110)和(101)的距離是2。在一個碼組集合中，任意兩個編碼之間漢明距離的最小值稱為這個碼組的最小漢明距離。最小漢明距離越大，碼組越具有抗幹擾能力。
漢明距離更多的用于信号處理，表明一個信号變成另一個信号需要的最小操作（替換位），實際中就是比較兩個比特串有多少個位不一樣，簡潔的操作時就是兩個比特串進行異或之後包含1的個數。漢明距在圖像處理領域也有這廣泛的應用，是比較二進制圖像非常有效的手段。計算一個數字的比特位包含1的個數有個小技巧：value &= value - 1這個運算的結果就是把value最後一個1去掉，循環進行運算直到value等于0（所有的1都被去掉）就可以知道vaule擁有多少個1了。其在包括資訊論、編碼理論、密碼學等領域都有應用。但是，如果要比較兩個不同長度的字元串，不僅要進行替換，而且要進行插入與删除的運算，在這種場合下，通常使用更加複雜的編輯距離等算法。（源自百科）
在信号處理方面，本菜就不班門弄斧了
據說，在機器學習領域中，漢明距離也常常被用于作為一種距離的度量方式。在LSH算法漢明距離也有重要的應用。具體還有待研究（待進一步深挖後 更新）
為什麼在這裡會提到餘弦？等等，這不是在學幾何三角！
雖然幾何中夾角餘弦可用來衡量兩個向量方向的差異，但是我們在機器學習中借用這一概念來可以衡量樣本向量之間的差異，從此進行相似性度量。
在二維空間中向量A ( x 1 , y 1 )與向量B ( x 2 , y 2 ) 的夾角餘弦公式：
來自網絡
或許可以了解為：求空間中兩點的餘弦值，值越大表示兩個向量的夾角越小，值越小表示兩向量的夾角越大。從上圖中可以看出，夾角越小代表兩個向量點越相似，夾角越大代表兩個向量的相似度越小。
當兩個向量的方向重合時夾角餘弦取最大值1，當兩個向量的方向完全相反夾角餘弦取最小值-1。
歐氏距離和餘弦相似度的差別
從上圖可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐标（即個體特征次元的數值）直接相關；而餘弦相似度衡量的是空間向量的夾角，更加的是展現在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐标軸原點，那麼這個時候餘弦相似度cosθ是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發生改變，這就是歐氏距離和餘弦相似度的不同之處。
餘弦相似度用向量空間中兩個向量夾角的餘弦值作為衡量兩個個體間差異的大小。相比距離度量，餘弦相似度更加注重兩個向量在方向上的差異，而非距離或長度上。(見此大佬轉載更好的解釋)
關于對餘弦相似度的應用，有以下見解：
正如上所述，相比歐氏距離，餘弦相似度計算更加注重的是在方向範圍上的應用，對絕對數值是相當的不夠敏感，在機器學習中，做聚類或分類的時候，針對多元不同特征，在數值上的聯系是相當重要的，故本菜自認為可應用性不大。在對多層次元進行分析展現不同特征之間的差異時，歐式距離或标準化歐氏距離會更占優勢。
餘弦在方向上區分不同特征的差異占優勢，可對一些用于使用使用者對内容評分來區分使用者興趣的相似度和差異，同時修正了使用者間可能存在的度量标準不統一的問題。（這條我抄的别說了）
吳軍. 數學之美 系列 12 -餘弦定理和新聞的分類.(一個比較好的栗子)
http://www.google.com.hk/ggblog/googlechinablog/2006/07/12_4010.htmlJaccard index , 又稱為Jaccard相似系數（Jaccard similarity coefficient）用于比較有限樣本集之間的相似性與差異性。Jaccard系數值越大，樣本相似度越高。
官方定義：
給定兩個集合A,B，Jaccard 系數定義為A與B交集的大小與A與B并集的大小的比值，定義如下：
當集合A，B都為空時，J(A,B)定義為1。
與Jaccard 系數相關的名額叫做Jaccard 距離，用于描述集合之間的不相似度。Jaccard 距離越大，樣本相似度越低。公式定義如下：
其中對參差（symmetric difference）:
非對稱二進制屬性的相似性
在資料挖掘領域，常常需要比較兩個具有布爾值屬性的對象之間的距離，Jaccard距離就是常用的一種方法。
給定兩個比較對象A，B。
A，B 均有n個二進制屬性，即每個屬性取值為{0，1}。
定義如下4個統計量：
Jaccard 系數：
Jaccard距離：
主要應用場景：
1.比較文本相似度，用于文本查重與去重；
2.計算對象間距離，用于資料聚類等。
Python有相應的庫包scipy.spatial.distance ，包含有傑卡德距離計算，可直接調用
# scipy距離公式
from numpy import *
import scipy.spatial.distance as dist
matV = mat([[1,1,0,1,0,1,0,0,1], [0,1,1,0,0,0,1,1,1]])
print ("dist.jaccard:", dist.pdist(matV,'jaccard')) 項目相似性度量是協同過濾系統的核心。 相關研究中，基于物品協同過濾系統的相似性度量方法普遍使用餘弦相似性。 然而，在許多實際應用中,評價資料稀疏度過高，物品之間通過餘弦相似度計算會産生誤導性結果。 将傑卡德相似性度量應用到基于物品的協同過濾系統中，并建立起相應的評價分析方法。 與傳統相似性度量方法相比，傑卡德方法完善了餘弦相似性隻考慮使用者評分而忽略了其他資訊量的弊端，特别适合于應用到稀疏度過高的資料。（引用自百科）