1 前言
在資料挖掘中，我們經常需要計算樣本之間的相似度(Similarity ),我們通常的做法是計算樣本之間的距離,本文對
距離計算方法做以下總結。
2 距離計算方法
A 歐式距離EuclideanDistance
歐式距離：兩點之間的直線距離。
(1)二維平面上兩點a(x1,y1)，b(x2,y2)之間的歐式距離公式：
(2) n維空間上兩點a(x1,x2……..xn)，b(y1,y2……..yn)的歐式距離公式：
B 曼哈頓距離(ManhattanDistance)
曼哈頓距離也叫”曼哈頓街區距離”。想象你在曼哈頓街道上，從一個十字路口開車到另一個十字路口，駕駛距離就
是這個“曼哈頓距離”。
(1)二維平面上兩點a(x1,y1)，b(x2,y2)之間的曼哈頓距離公式：
(2) n維空間上兩點a(x1,x2……..xn)，b(y1,y2……..yn)的曼哈頓距離公式：
C 夾角餘弦
機器學習中可以把兩點看成是空間中的兩個向量，通過衡量兩向量之間的相似性來衡量樣本之間的相似性。
(1)二維平面上兩向量a(x1,y1)，b(x2,y2)之間的夾角餘弦公式：
也可直接通過向量運算：
(2) n維空間上兩點a(x1,x2……..xn)，b(y1,y2……..yn)的夾角餘弦公式：
D 切比雪夫距離（Chebyshevdistance）
切比雪夫距離:各對應坐标數值差的最大值。國王從格子(x1,y1)走到格子(x2,y2)最少需要多少步？你會發現最少步
數總是max( | x2-x1 | , | y2-y1 | )步。
(1)二維平面上兩點a(x1,y1)，b(x2,y2)之間的切比雪夫距離公式：
(2) n維空間上兩點a(x1,x2……..xn)，b(y1,y2……..yn)的切比雪夫距離公式：
E 漢明距離
兩個等長字元串之間的漢明距離是兩個字元串對應位置的不同字元的個數。
1011101與 1001001 之間的漢明距離是2
2143896與 2233796 之間的漢明距離是3
irie與 rise之間的漢明距離是 3
轉自：http://blog.csdn.net/wangpei1949/article/details/52926651
當兩條新聞向量夾角餘弦等于1時，這兩條新聞完全重複（用這個辦法可以删除爬蟲所收集網頁中的重複網頁）；當夾角的餘弦值接近于1時，兩條新聞相似（可以用作文本分類）；夾角的餘弦越小，兩條新聞越不相關。
相似度（距離計算）彙總1 前言2 距離計算方法 2、餘弦距離和歐氏距離的對比
從上圖可以看出，餘弦距離使用兩個向量夾角的餘弦值作為衡量兩個個體間差異的大小。相比歐氏距離，餘弦距離更加注重兩個向量在方向上的差異。
借助三維坐标系來看下歐氏距離和餘弦距離的差別：
從上圖可以看出，歐氏距離衡量的是空間各點的絕對距離，跟各個點所在的位置坐标直接相關；而餘弦距離衡量的是空間向量的夾角，更加展現在方向上的差異，而不是位置。如果保持A點位置不變，B點朝原方向遠離坐标軸原點，那麼這個時候餘弦距離相似度（距離計算）彙總1 前言2 距離計算方法 相似度（距離計算）彙總1 前言2 距離計算方法 是保持不變的（因為夾角沒有發生變化），而A、B兩點的距離顯然在發生改變，這就是歐氏距離和餘弦距離之間的不同之處。
歐氏距離和餘弦距離各自有不同的計算方式和衡量特征，是以它們适用于不同的資料分析模型：
歐氏距離能夠展現個體數值特征的絕對差異，是以更多的用于需要從次元的數值大小中展現差異的分析，如使用使用者行為名額分析使用者價值的相似度或差異。
餘弦距離更多的是從方向上區分差異，而對絕對的數值不敏感，更多的用于使用使用者對内容評分來區分興趣的相似度和差異，同時修正了使用者間可能存在的度量标準不統一的問題（因為餘弦距離對絕對數值不敏感）。
3、傑卡德相似性度量
（1）傑卡德相似系數
兩個集合A和B交集元素的個數在A、B并集中所占的比例，稱為這兩個集合的傑卡德系數，用符号 J(A,B) 表示。傑卡德相似系數是衡量兩個集合相似度的一種名額（餘弦距離也可以用來衡量兩個集合的相似度）。相似度（距離計算）彙總1 前言2 距離計算方法 （2）傑卡德距離
與傑卡德相似系數相反的概念是傑卡德距離（Jaccard Distance），可以用如下公式來表示：傑卡德距離用兩個兩個集合中不同元素占所有元素的比例來衡量兩個集合的區分度。相似度（距離計算）彙總1 前言2 距離計算方法 （3）傑卡德相似系數的應用
假設樣本A和樣本B是兩個n維向量，而且所有次元的取值都是0或1。例如，A（0,1,1,0）和B（1,0,1,1）。我們将樣本看成一個集合，1表示集合包含該元素，0表示集合不包含該元素。
p：樣本A與B都是1的次元的個數
q：樣本A是1而B是0的次元的個數
r：樣本A是0而B是1的次元的個數
s：樣本A與B都是0的次元的個數
那麼樣本A與B的傑卡德相似系數可以表示為：
相似度（距離計算）彙總1 前言2 距離計算方法 此處分母之是以不加s的原因在于：
對于傑卡德相似系數或傑卡德距離來說，它處理的都是非對稱二進制變量。非對稱的意思是指狀态的兩個輸出不是同等重要的，例如，疾病檢查的陽性和陰性結果。
按照慣例，我們将比較重要的輸出結果，通常也是出現幾率較小的結果編碼為1（例如HIV陽性），而将另一種結果編碼為0（例如HIV陰性）。給定兩個非對稱二進制變量，兩個都取1的情況（正比對）認為比兩個都取0的情況（負比對）更有意義。負比對的數量s認為是不重要的，是以在計算時忽略。
（4）傑卡德相似度算法分析
傑卡德相似度算法沒有考慮向量中潛在數值的大小，而是簡單的處理為0和1，不過，做了這樣的處理之後，傑卡德方法的計算效率肯定是比較高的，畢竟隻需要做集合操作。4、調整餘弦相似度算法（Adjusted Cosine Similarity）
餘弦相似度更多的是從方向上區分差異，而對絕對的數值不敏感，是以沒法衡量每個次元上數值的差異，會導緻這樣一種情況：
使用者對内容評分，按5分制，X和Y兩個使用者對兩個内容的評分分别為（1,2）和（4,5），使用餘弦相似度得到的結果是0.98，兩者極為相似。但從評分上看X似乎不喜歡2這個 内容，而Y則比較喜歡，餘弦相似度對數值的不敏感導緻了結果的誤差，需要修正這種不合理性就出現了調整餘弦相似度，即所有次元上的數值都減去一個均值，比如X和Y的評分均值都是3，那麼調整後為（-2，-1）和（1,2），再用餘弦相似度計算，得到-0.8，相似度為負值并且差異不小，但顯然更加符合現實。
那麼是否可以在（使用者-商品-行為數值）矩陣的基礎上使用調整餘弦相似度計算呢？從算法原理分析，複雜度雖然增加了，但是應該比普通餘弦夾角算法要強。
轉自：http://www.cnblogs.com/chaosimple/archive/2013/06/28/3160839.html
總結：一、說明
相似性度量用以描述兩個向量之間的相似性，是一個值域為一維的二進制函數。一般情況，相似性度量本質上指距離度量，隻不過數值訓示剛好相反，如果是距離的話，數值越小，距離越近，而相似度越大；如果是相似度的話，數值越小，相似度越小，而距離越大。 相似性度量在機器學習中是一個非常基礎的概念，尤其在聚類、推薦系統等算法中。 在工程應用中，也會使用一些不完全滿足距離度量基本性質的“非距離度量”[1]。二、距離度量的基本性質：
非負性：dist(x,y) >= 0 同一性：dist(x,x) = 0 對稱性：dist(x,y) = dist(y,x) 三角不等式：dist(x,z)+dist(y,z) >= dist(x,y)三、常用相似性度量
1、闵可夫斯基距離(Minkowski Distance)
相似度（距離計算）彙總1 前言2 距離計算方法 2、曼哈頓距離(Manhattan Distance)
p=1時，闵可夫斯基距離就是曼哈頓距離又稱城市街區距離，在方正的北京大街打車，行車距離就是曼哈頓距離，如果在山城重慶就不是了。相似度（距離計算）彙總1 前言2 距離計算方法 3、歐氏距離(Euclidean Distance)
p=2時，闵可夫斯基距離就是歐氏距離。在平面幾何或者立體幾何中的距離，通常就是歐氏距離，是以歐氏距離也最容易了解。相似度（距離計算）彙總1 前言2 距離計算方法 4、切比雪夫距離(Chebyshev Distance)
p等于無窮大時，闵可夫斯基距離就是切比雪夫距離。若将國際象棋棋盤放在二維直角坐标系中，格子的邊長定義為1，座标的x軸及y軸和棋盤方格平行，原點恰落在某一格的中心點，則王從一個位置走到其他位置需要的最少步數恰為二個位置的切比雪夫距離，是以切比雪夫距離也稱為棋盤距離。[2]相似度（距離計算）彙總1 前言2 距離計算方法 5、"權重(weighted)"闵可夫斯基距離
當樣本中不同屬性的重要性不同時，可使用"權重距離"(weighted distance)[1]。相似度（距離計算）彙總1 前言2 距離計算方法 6、餘弦相似度(Cosine Similarity)
餘弦相似性取值[-1,1]，值越趨于1，表示兩個向量的相似度越高。餘弦相似度與向量的幅值無關，隻與向量的方向相關，在文檔相似度(TF-IDF)和圖檔相似性(histogram)計算上都有它的身影[3]。相似度（距離計算）彙總1 前言2 距離計算方法 7、皮爾遜相關系數(Pearson Correlation)
餘弦相似度會受到向量的平移影響，怎樣才能實作平移不變性？在餘弦相似度的基礎上，每個向量減去這個向量均值組成的向量，也就是皮爾遜相關系數，有時候也直接叫相關系數。當兩個向量均值都為0時，皮爾遜相對系數等于餘弦相似性。相似度（距離計算）彙總1 前言2 距離計算方法 8、馬氏距離(Mahalanobis Distance)
一個向量的不同次元如果是不同的量綱，更有甚者，次元之間是相關的，比如身高和體重組成的向量，在闵可夫斯基距離中等同對待，有時，這樣是不恰當的。馬氏距離利用 Cholesky transformation 消除了不同次元之間的相關性和尺度不同[3]。其中，S為樣本的協方差矩陣。當S是機關陣的時候，馬氏距離就是歐式距離；當S是對角陣的時候，馬氏距離是權重歐式距離。 很多時候，一個事物的有點也可能會構成它的缺點。這裡馬氏距離可以消除不同次元之間的不同尺度，就可能放大了變化細微次元的作用[4]。 我們可以按照連續性将屬性分為“連續屬性”和“離散屬性”；也可以按照有序性将屬性分為“有序屬性”和“無序屬性”[1]。上面的相似性度量都是關于“連續”并“有序”屬性的，下面給出幾個關于“離散屬性”和“無序屬性”的相似性度量。相似度（距離計算）彙總1 前言2 距離計算方法 9、漢明距離(Hamming Distance)
兩個等長字元串s1與s2之間的漢明距離定義為将其中一個變為另外一個所需要作的最小替換次數。 例如:字元串“11110011”與“10010010”之間的漢明距離為3。 漢明距離可以在通信中累計定長二進制字中發生翻轉的錯誤資料位，是以它也被稱為信号距離。漢明重量分析在包括資訊論、編碼理論、密碼學等領域都有應用。[5] 如果要比較兩個不同長度的字元串，不僅要進行替換，而且要進行插入與删除的運算，在這種場合下，通常使用更加複雜的編輯距離等算法。[5]10、傑卡德相似系數(Jaccard Similarity)
傑卡德相似系數是衡量兩個集合的相似度一種名額傑卡德相似系數是從相似性度量的角度來表述的，從距離度量的角度，則有傑卡德距離(Jaccard Distance)相似度（距離計算）彙總1 前言2 距離計算方法 傑卡德相似系數和傑卡德距離本質上是一樣的，隻是表述角度不同。 在聚類中，傑卡德相似系數可以作為聚類的性能度量[1]。在推薦系統中，傑卡德相似系數可以度量兩個購買若幹商品的使用者之間的相似性[3]。相似度（距離計算）彙總1 前言2 距離計算方法 11、KL散度(Kullback-Leibler Divergence)
又叫相對熵，表示兩個随機分布之間的相似性可以證明，KL散度大于等于0，當p=q時等于0；KL散度不滿足對稱性。相似度（距離計算）彙總1 前言2 距離計算方法 12、Hellinger距離(Hellinger Distance)
在七月算法的課程裡，還講了一個與KL散度類似的距離，表示随機分布之間的相似性的Hellinger距離當α=0時相似度（距離計算）彙總1 前言2 距離計算方法 這時，Hellinger距離就是兩個随機分布取平方根之後的歐式距離，符合距離度量的四個性質，是嚴格的距離度量。 轉自：http://www.jianshu.com/p/9b7166997a3e相似度（距離計算）彙總1 前言2 距離計算方法
- 如果資料存在“分數膨脹“問題，就使用皮爾遜相關系數
- 如果資料比較密集，變量之間基本都存在共有值，且這些距離資料都是非常重要的，那就使用歐幾裡得或者曼哈頓距離
- 如果資料是稀疏的，就使用餘弦相似度