距離和相似度度量方法

http://blog.csdn.net/pipisorry/article/details/45651315

在機器學習和資料挖掘中，我們經常需要知道個體間差異的大小，進而評價個體的相似性和類别。最常見的是資料分析中的相關分析，資料挖掘中的分類和聚類算法，如 K 最近鄰（KNN）和 K 均值（K-Means）等等。

不同距離度量的應用場景

根據資料特性的不同，可以采用不同的度量方法。which one to use depends on what type of data we have and what our notion of similar is.

各種“距離”的應用場景簡單概括為，空間：歐氏距離，路徑：曼哈頓距離，國際象棋國王：切比雪夫距離，以上三種的統一形式:闵可夫斯基距離，權重：标準化歐氏距離，排除量綱和依存：馬氏距離，向量差距：夾角餘弦，編碼差别：漢明距離，集合近似度：傑卡德類似系數與距離，相關：相關系數與相關距離。

距離度量公理Axioms of Distance Measures

一般而言，定義一個距離函數 d(x,y), 需要滿足下面幾個準則：(即距離度量需要滿足的性質)

1) d(x,y) = 0  iff x = y                  // 到自己的距離為0

2) d(x,y) >= 0                  // 距離非負

3) d(x,y) = d(y,x)                   // 對稱性: 如果 A 到 B 距離是 a，那麼 B 到 A 的距離也應該是 a

4) d(x,k)+ d(k,y) >= d(x,y)    // 三角形法則triangle inequality: (兩邊之和大于第三邊)

Note: iff =  if and only if

基礎知識：熵與互資訊

[熵與互資訊 ]

文本相似度量方法一覽

此處的“文本”一詞涵蓋以下兩個對象:

1. 字元串/序列
2. 包含較多文本内容的文檔

相關的度量方法可以分為兩大類，各類下面再有一些具體的分類，比較常用的方法如見下圖

Note: lz這裡LCS也可以認為就是編輯距離吧。

總的來說，文本相似度量方法可以分為兩大類:

1. String Based，即基于待比較的文本本身中的資訊，該類方法評估的是”詞法“上的相似性，或說樸素的相似性
2. Corpus Based，即基于一個較大的文本集合中的資訊，該類方法評估的是“語義”上的相似性

[文本相似度量方法(1): 概覽]

皮皮blog

歐氏距離度量

歐拉距離，來自于歐式幾何，在數學上也可以成為範數。

範數Norm

Lr範數就是x,y每個次元差距上取r次方加和後再開r次方根。Lr norm: what you get by taking the rth power of the differences, summing and taking the rth root.

給定向量x=（x1，x2，...xn）

L1範數：向量各個元素絕對值之和，Manhattan distance。

║x║1=│x1│+│x2│+…+│xn│

L2範數：向量各個元素的平方求和然後求平方根，也叫歐式範數、歐氏距離。

║x║2=（│x1│2+│x2│2+…+│xn│2）^1/2

Lp範數：向量各個元素絕對值的p次方求和然後求1/p次方。

L∞範數：向量各個元素求絕對值，最大那個元素的絕對值。也就是x，y在任意次元上差距最大的那個值。

║x║∞=max（│x1│，│x2│，…，│xn│）

小示例

Euclidean distance Vs. Non-Euclidean distance 歐氏距離對比非歐氏距離

dense: 給定兩個點，它們的均值也是這個空間的一個點。And there is no reasonable notion of the average of points in the space.歐氏距離可以計算average，但是非歐氏距離卻不一定。

皮皮blog

非歐氏距離度量

Jaccard相似度

一般用于兩個一進制unary向量(buy or not, click or not)相似性的度量，或者用于集合sets相似性形式定義。

Note: Jaccard distance = 1 - Jaccard similarity

分子是集合交集，分母是集合并集。即兩個集合間的Jaccard similarity就是它們交集的大小除以它們并集的大小。

Jaccard相似度沒有考慮評分的大小。

Dice's Coefficient

Dice（s1,s2）=2*comm(s1,s2)/(leng(s1)+leng(s2))。

其中，comm (s1,s2)是s1、s2 中相同字元的個數leng(s1)，leng(s2)是字元串s1、s2 的長度。

Dice 系數和 Jaccard 相似性起初被用于生态學上，作為一種判斷物種間相似性的方法。在生态學上，要比較兩個物種間相似程度時，通常會對該物種的特性進行采樣，最後得到各自的特性集合，而 Dice 系數和 Jaccard 相似性都是通過比較兩者之間的 共有特性 占比來度量相似性的，是以這兩種方法都不是很關心每個 "Term" 的具體量，隻是關心有沒有某個 "Term"。

廣義Jaccard相似度|Tanimoto系數

EJ(A,B)=(A*B)/(||A||^2+||B||^2-A*B)

其中A、B分别表示為兩個向量，集合中每個元素表示為向量中的一個次元，在每個次元上，取值通常是[0, 1]之間的值，A*B表示向量乘積，||A||^2表示向量的模，即 ||A||^2 = sqrt (a1^2 + a2^2 + a3^2 + ......)。

另一種擴充方法，用最大最小值函數來代替乘積和模計算，如下：

即用向量中每個分量的的最小值和最大值來參與計算。

個人了解，這個可以做如下解釋。當集合A中的元素a1出現C(a1)次的時候，我們可以認為集合中的元素是允許重複存在的，即集合A中有C(a1)個元素；集合B也是這樣，有C(b1)個相同的元素，則A和B在這個元素上的交集就是min(a1, b1) ，并集就是max(a1, b1) ，這樣上述公式就是利用狹義Jaccard相似度計算的結果。

Cosine餘弦相似度/向量内積

适合高次元向量vectors的相似度計算。

1. 兩個向量間的餘弦值可以很容易地通過使用歐幾裡得點積和量級公式推導

\mathbf{a}\cdot\mathbf{b}=\left\|\mathbf{a}\right\|\left\|\mathbf{b}\right\|\cos\theta 

鑒于兩個向量的屬性， A 和B的餘弦相似性θ用一個點積形式來表示其大小，如下所示：

\text{similarity} = \cos(\theta) = {A \cdot B \over \|A\| \|B\|} = \frac{ \sum\limits_{i=1}^{n}{A_i \times B_i} }{ \sqrt{\sum\limits_{i=1}^{n}{(A_i)^2}} \times \sqrt{\sum\limits_{i=1}^{n}{(B_i)^2}} }

也就是說兩個向量的cosin距離就是這兩個向量之間的夾角。

Note:  if you project P1 onto P2,the length of the projection is the dot product, divided by the length of P2.Then the cosine of the angle between them is the ratio of adjacent(the dot product divided by P2) over hypotenuse(斜邊, the length of P1).

産生的相似性範圍從-1到1：-1意味着兩個向量指向的方向正好截然相反，1表示它們的指向是完全相同的，0通常表示它們之間是獨立的，而在這之間的值則表示中度的相似性或相異性。

對于文本比對，屬性向量A 和B 通常是文檔中的詞頻向量。餘弦相似性，可以被看作是一個規範比較檔案長度的方法。 在資訊檢索的情況下，由于一個詞的頻率（TF-IDF權）不能為負數，是以這兩個文檔的餘弦相似性範圍從0到1。并且，兩個詞的頻率向量之間的角度不能大于90°。

[餘弦相似性]

2. 向量内積是線性代數裡最為常見的計算，實際上它還是一種有效并且直覺的相似性測量手段。向量内積的定義如下：

直覺的解釋是：如果 x 高的地方 y 也比較高， x 低的地方 y 也比較低，那麼整體的内積是偏大的，也就是說 x 和 y 是相似的。舉個例子，在一段長的序列信号 A 中尋找哪一段與短序列信号 a 最比對，隻需要将 a 從 A 信号開頭逐個向後平移，每次平移做一次内積，内積最大的相似度最大。信号進行中 DFT 和 DCT 也是基于這種内積運算計算出不同頻域内的信号組分（DFT 和 DCT 是正交标準基，也可以看做投影）。向量和信号都是離散值，如果是連續的函數值，比如求區間[-1, 1] 兩個函數之間的相似度，同樣也可以得到（系數）組分，這種方法可以應用于多項式逼近連續函數，也可以用到連續函數逼近離散樣本點（最小二乘問題，OLS coefficients）中，扯得有點遠了- -!。

向量内積的結果是沒有界限的，一種解決辦法是除以長度之後再求内積，這就是應用十分廣泛的餘弦相似度（Cosine similarity）：

餘弦相似度與向量的幅值無關，隻與向量的方向相關，在文檔相似度（TF-IDF）和圖檔相似性（histogram）計算上都有它的身影。

cosine similarity的一個擴充是

Tonimoto系數

T(A,B) = {A /cdot B /over /|A/|^2 +/|B/|^2 - A /cdot B}

其實也沒什麼大不了。T（A,B）的分母是大于等于 cos similarity的分母，但且僅僅但 A,B長度一樣是才相等。這就意味着，Tonimoto系數考慮了兩個向量的長度差異，長度差異越大相似性約小。

另外需要注意一點的是，餘弦相似度受到向量的平移影響，上式如果将 x 平移到 x+1, 餘弦值就會改變。怎樣才能實作平移不變性？

皮爾遜相關系數（Pearson correlation）

{也叫Centered Cosine，有時候也直接叫相關系數}

{數值型資料的相關性分析Correlation Analysis (Numerical Data)，從下面這個公式看出，它其實就是将資料歸一化（資料減去其對應均值）後進行cosine相似度計算，是以叫centered cosine}

另一種表示方式

皮爾遜相關系數具有平移不變性和尺度不變性，計算出了兩個向量（次元）的相關性。不過，一般我們在談論相關系數的時候，将 x 與 y 對應位置的兩個數值看作一個樣本點，皮爾遜系數用來表示這些樣本點分布的相關性。

相關關系度量

由于皮爾遜系數具有的良好性質，在各個領域都應用廣泛，例如，在推薦系統根據為某一使用者查找喜好相似的使用者,進而提供推薦，優點是可以不受每個使用者評分标準不同和觀看影片數量不一樣的影響。

相關系數多大才是顯著相關？

相關系數的強弱僅僅看系數的大小是不夠的。一般來說，取絕對值後，0-0.09為沒有相關性，0.3-弱，0.1-0.3為弱相關，0.3-0.5為中等相關，0.5-1.0為強相關。

但是，往往你還需要做顯著性差異檢驗，即t-test，來檢驗兩組資料是否顯著相關。

樣本書越是大，需要達到顯著性相關的相關系數就會越小。是以這關系到你的樣本大小，如果你的樣本很大，比如說超過300，往往分析出來的相關系數比較低，比如0.2，因為你樣本量的增大造成了差異的增大，但顯著性檢驗卻認為這是極其顯著的相關。

一般來說，我們判斷強弱主要看顯著性，而非相關系數本身。但你在撰寫論文時需要同時報告這兩個統計資料。

[怎樣對資料做相關性檢驗]

皮爾遜相關系數的适用範圍

當兩個變量的标準差都不為零時，相關系數才有定義，皮爾遜相關系數适用于：

1. 兩個變量之間是線性關系，都是連續資料。
2. 兩個變量的總體是正态分布，或接近正态的單峰分布。
3. 兩個變量的觀測值是成對的，每對觀測值之間互相獨立。

如何了解皮爾遜相關系數

rubyist：皮爾遜相關系數了解有兩個角度

其一, 按照高中數學水準來了解, 它很簡單, 可以看做将兩組資料首先做Z分數處理之後, 然後兩組資料的乘積和除以樣本數，Z分數一般代表正态分布中, 資料偏離中心點的距離.等于變量減掉平均數再除以标準差.(就是聯考的标準分類似的處理)

樣本标準差則等于變量減掉平均數的平方和，再除以樣本數，最後再開方，也就是說，方差開方即為标準差，樣本标準差計算公式為：

是以, 根據這個最樸素的了解,我們可以将公式依次精簡為:

其二, 按照大學的線性數學水準來了解, 它比較複雜一點,可以看做是兩組資料的向量夾角的餘弦。下面是關于此皮爾遜系數的幾何學的解釋，先來看一幅圖，如下所示：

 回歸直線： y=gx(x) [紅色] 和 x=gy(y) [藍色]

如上圖，對于沒有中心化的資料, 相關系數與兩條可能的回歸線y=gx(x) 和 x=gy(y) 夾角的餘弦值一緻。

對于沒有中心化的資料 (也就是說, 資料移動一個樣本平均值以使其均值為0), 相關系數也可以被視作由兩個随機變量 向量 夾角 的 餘弦值（見下方）。

舉個例子，例如，有5個國家的國民生產毛額分别為 10, 20, 30, 50 和 80 億美元。 假設這5個國家 (順序相同) 的貧困百分比分别為 11%, 12%, 13%, 15%, and 18% 。 令 x 和 y 分别為包含上述5個資料的向量: x = (1, 2, 3, 5, 8) 和 y = (0.11, 0.12, 0.13, 0.15, 0.18)。

利用通常的方法計算兩個向量之間的夾角  (參見 數量積), 未中心化 的相關系數是:

我們發現以上的資料特意標明為完全相關: y = 0.10 + 0.01 x。 于是，皮爾遜相關系數應該等于1。将資料中心化 (通過E(x) = 3.8移動 x 和通過 E(y) = 0.138 移動 y ) 得到 x = (−2.8, −1.8, −0.8, 1.2, 4.2) 和 y = (−0.028, −0.018, −0.008, 0.012, 0.042), 從中

(4)皮爾遜相關的限制條件

從以上解釋, 也可以了解皮爾遜相關的限制條件:

• 1 兩個變量間有線性關系
• 2 變量是連續變量
• 3 變量均符合正态分布,且二進制分布也符合正态分布
• 4 兩變量獨立

在實踐統計中,一般隻輸出兩個系數,一個是相關系數,也就是計算出來的相關系數大小,在-1到1之間;另一個是獨立樣本檢驗系數,用來檢驗樣本一緻性。

Note: lz文本很短，關鍵詞很少的時候，餘弦距離就很難計算出準确的相似度。這時候可以使用主題模型。

皮皮blog

漢明距離-分類資料點間的距離

漢明距離（Hamming distance）是指，兩個等長字元串(一般适用于bit  vectors)s1與s2之間的漢明距離定義為将其中一個變為另外一個所需要作的最小替換次數。

舉個維基百科上的例子：

還可以用簡單的比對系數來表示兩點之間的相似度——比對字元數/總字元數。

在一些情況下，某些特定的值相等并不能代表什麼。舉個例子，用 1 表示使用者看過該電影，用 0 表示使用者沒有看過，那麼使用者看電影的的資訊就可用 0,1 表示成一個序列。考慮到電影基數非常龐大，使用者看過的電影隻占其中非常小的一部分，如果兩個使用者都沒有看過某一部電影（兩個都是 0），并不能說明兩者相似。反而言之，如果兩個使用者都看過某一部電影（序列中都是 1），則說明使用者有很大的相似度。在這個例子中，序列中等于 1 所占的權重應該遠遠大于 0 的權重，這就引出下面要說的傑卡德相似系數（Jaccard similarity）。

在上面的例子中，用 M11 表示兩個使用者都看過的電影數目，M10 表示使用者 A 看過，使用者 B 沒看過的電影數目，M01 表示使用者 A 沒看過，使用者 B 看過的電影數目，M00 表示兩個使用者都沒有看過的電影數目。Jaccard 相似性系數可以表示為：

Jaccard similarity 還可以用集合的公式來表達，這裡就不多說了。

如果分類數值點是用樹形結構來表示的，它們的相似性可以用相同路徑的長度來表示，比如，“/product/spot/ballgame/basketball” 離“product/spot/ballgame/soccer/shoes” 的距離小于到 "/product/luxury/handbags" 的距離，以為前者相同父節點路徑更長。

編輯距離Edit distance-序列之間的距離

[編輯距離Edit distance] 

kl散度/相對熵/kl距離

1. 相對熵（relative entropy）又稱為KL散度（Kullback–Leibler divergence，簡稱KLD），資訊散度（information divergence），資訊增益（information gain）。

KL散度是兩個機率分布P和Q差别的非對稱性的度量（designed to measure the difference between probability distributions）。 KL散度是用來 度量使用基于Q的編碼來編碼來自P的樣本平均所需的額外的位元數。 典型情況下，P表示資料的真實分布，Q表示資料的理論分布，模型分布，或P的近似分布。

定義

對于離散随機變量，其機率分布P 和Q的KL散度可按下式定義為

D_{\mathrm{KL}}(P\|Q) = \sum_i P(i) \ln \frac{P(i)}{Q(i)}

即按機率P求得的P和Q的對數差的平均值。KL散度僅當機率P和Q各自總和均為1，且對于任何i皆滿足?及P(i)>0時，才有定義。式中出現0 \ln 0的情況，其值按0處理。

特性

1. 相對熵的值為非負數

D_{\mathrm{KL}}(P\|Q) \geq 0

由吉布斯不等式（en:Gibbs' inequality）可知，當且僅當P = Q時DKL(P||Q)為0

2. 盡管從直覺上KL散度是個度量或距離函數, 但是它實際上并不是一個真正的度量或距離。因為KL散度不具有對稱性：從分布P到Q的距離（或度量）通常并不等于從Q到P的距離（或度量）。

D_{\mathrm{KL}}(P\|Q) \neq D_{\mathrm{KL}}(Q\|P)

L散度是不對稱的，當然，如果希望把它變對稱，

Ds(p1, p2) = [D(p1, p2) + D(p2, p1)] / 2

[KL散度]

[相對熵]

2. 機率分布之間的距離

實際上兩個機率分布之間的距離是可以測量的。在統計學裡面經常需要測量兩組樣本分布之間的距離，進而判斷出它們是否出自同一個 population，常見的方法有卡方檢驗（Chi-Square）和 KL 散度（ KL-Divergence），下面說一說 KL 散度吧。

先了解一下前面的基礎知識[資訊熵-資訊熵的來源]，而KL 散度又叫相對熵（relative entropy）。了解機器學習的童鞋應該都知道，在 Softmax 回歸（或者 Logistic 回歸），最後的輸出節點上的值表示這個樣本分到該類的機率，這就是一個機率分布。對于一個帶有标簽的樣本，我們期望的機率分布是：分到标簽類的機率是 1， 其他類機率是 0。但是理想很豐滿，現實很骨感，我們不可能得到完美的機率輸出，能做的就是盡量減小總樣本的 KL 散度之和（目标函數）。這就是 Softmax 回歸或者 Logistic 回歸中 Cost function 的優化過程啦。（PS：因為機率和為 1，一般的 logistic 二分類的圖隻畫了一個輸出節點，隐藏了另外一個）

[KL散度(Kullback-Leibler_divergence)]

kl散度的python+scipy實作

{計算topic_word分布矩陣所有topic_word分布兩兩之間的相似度-kl散度}

1.

# 方法1（pdist隻能計算對稱kl散度）
topic_similar_mat = spatial.distance.pdist(tw_dist_ndaray,
                                           metric=lambda P, Q: ((sum(kl_div(P, Q)) + sum(kl_div(Q, P))) / 2))
           

2.

def kl(P, Q):
    '''
    計算兩個ndarray的kl散度
    KL散度僅當機率P和Q各自總和均為1，且對于任何i皆滿足Q(i)>0及P(i)>0時，才有定義
    '''
    return sum(P * log(P / Q)) if (P > 0).all() and (Q > 0).all() else None
    # return sum(where((P > 0).all() and (Q > 0).all(), P * log(P / Q), None), axis=0)

#方法2（對稱kl散度，自定義kl函數）
topic_similar_mat = spatial.distance.pdist(tw_dist_ndaray,
                                               metric=lambda P, Q: ((kl(P, Q) + kl(Q, P)) / 2))
           

Note: kl散度可以通過scipy包的stats.entropy計算[Scipy教程 - 統計函數庫scipy.stats ]

3.# 方法3（非對稱kl散度）

topic_similar_mat = zeros([len(tw_dist_ndaray), len(tw_dist_ndaray)])

for i_id, i in enumerate(tw_dist_ndaray):

    for j_id, j in enumerate(tw_dist_ndaray):

        if i_id != j_id:

            topic_similar_mat[i_id, j_id] = stats.entropy(tw_dist_ndaray[i_id], tw_dist_ndaray[j_id])

4.topic_similar_mat[i_id, j_id] = sum(kl_div(tw_dist_ndaray[i_id], tw_dist_ndaray[j_id]))

Note：

1. 計算出的結果自己和自己的kl散度為0，為了排序計算與别人的相似度應該将對角線中的元素改為max

topic_similar_mat = spatial.distance.squareform(topic_similar_mat)
max_dist = topic_similar_mat.max()
for i in range(len(topic_similar_mat)):
    topic_similar_mat[i, i] = max_dist+1
print(topic_similar_mat)
           

2. 非對稱kl散度不是對稱的，而用pdist計算出的topic_similar_mat一定是對稱的，因為pdist隻計算上三角，是以使用pdist必須要用對稱的kl散度

[Computation of Kullback-Leibler (KL) distance between text-documents using numpy]

[http://docs.scipy.org/doc/scipy-dev/reference/generated/scipy.stats.entropy.html]

闵可夫斯基距離

闵可夫斯基距離（Minkowski distance）是衡量數值點之間距離的一種非常常見的方法，假設數值點 P 和 Q 坐标如下：

那麼，闵可夫斯基距離定義為：

該距離最常用的 p 是 2 和 1, 前者是歐幾裡得距離（Euclidean distance），後者是曼哈頓距離（Manhattan distance）。假設在曼哈頓街區乘坐計程車從 P 點到 Q 點，白色表示高樓大廈，灰色表示街道：

綠色的斜線表示歐幾裡得距離，在現實中是不可能的。其他三條折線表示了曼哈頓距離，這三條折線的長度是相等的。

當 p 趨近于無窮大時，闵可夫斯基距離轉化成切比雪夫距離（Chebyshev distance）：

我們知道平面上到原點歐幾裡得距離（p = 2）為 1 的點所組成的形狀是一個圓，當 p 取其他數值的時候呢？

注意，當 p 

<

 1 時，闵可夫斯基距離不再符合三角形法則，舉個例子：當 p 

<

 1, (0,0) 到 (1,1) 的距離等于 (1+1)^{1/p} 

>

 2, 而 (0,1) 到這兩個點的距離都是 1。

闵可夫斯基距離比較直覺，但是它與資料的分布無關，具有一定的局限性，如果 x 方向的幅值遠遠大于 y 方向的值，這個距離公式就會過度放大 x 次元的作用。是以，在計算距離之前，我們可能還需要對資料進行 z-transform 處理，即減去均值，除以标準差：

 : 該次元上的均值

 : 該次元上的标準差

可以看到，上述處理開始展現資料的統計特性了。這種方法在假設資料各個次元不相關的情況下利用資料分布的特性計算出不同的距離。如果次元互相之間資料相關（例如：身高較高的資訊很有可能會帶來體重較重的資訊，因為兩者是有關聯的），這時候就要用到馬氏距離（Mahalanobis distance）了。

馬氏距離

馬氏距離實際上是利用 Cholesky transformation 來消除不同次元之間的相關性和尺度不同的性質。馬氏距離的變換和 PCA 分解的白化處理頗有異曲同工之妙，不同之處在于：就二維來看，PCA 是将資料主成分旋轉到 x 軸（正交矩陣的酉變換），再在尺度上縮放（對角矩陣），實作尺度相同。而馬氏距離的 L逆矩陣是一個下三角，先在 x 和 y 方向進行縮放，再在 y 方向進行錯切（想象矩形變平行四邊形），總體來說是一個沒有旋轉的仿射變換。

考慮下面這張圖，橢圓表示等高線，從歐幾裡得的距離來算，綠黑距離大于紅黑距離，但是從馬氏距離，結果恰好相反：

假設樣本點（列向量）之間的協方差對稱矩陣是 

 ， 通過 Cholesky Decomposition（實際上是對稱矩陣 LU 分解的一種特殊形式，可參考部落格）可以轉化為下三角矩陣和上三角矩陣的乘積： 

 。消除不同次元之間的相關性和尺度不同，隻需要對樣本點 x 做如下處理：

 。處理之後的歐幾裡得距離就是原樣本的馬氏距離（為了書寫友善，這裡求馬氏距離的平方）：

Note: 這個也正是多元高斯分布的指數項的二次型，即高斯對于x的依賴的二次型表達。當

為機關矩陣時，馬氏距離就變成了歐氏距離。

下圖藍色表示原樣本點的分布，兩顆紅星坐标分别是（3, 3），（2, -2）:

由于 x， y 方向的尺度不同，不能單純用歐幾裡得的方法測量它們到原點的距離。并且，由于 x 和 y 是相關的（大緻可以看出斜向右上），也不能簡單地在 x 和 y 方向上分别減去均值，除以标準差。最恰當的方法是對原始資料進行 Cholesky 變換，即求馬氏距離（可以看到，右邊的紅星離原點較近）：

将上面兩個圖的繪制代碼和求馬氏距離的代碼貼在這裡，以備以後查閱：

import numpy as np
import pylab as pl
import scipy.spatial.distance as dist
def plotSamples(x, y, z=None):
    stars = np.matrix([[3., -2., 0.], [3., 2., 0.]])
    if z is not None:
        x, y = z * np.matrix([x, y])
        stars = z * stars
    pl.scatter(x, y, s=10)    # 畫 gaussian 随機點
    pl.scatter(np.array(stars[0]), np.array(stars[1]), s=200, marker='*', color='r')  # 畫三個指定點
    pl.axhline(linewidth=2, color='g') # 畫 x 軸
    pl.axvline(linewidth=2, color='g')  # 畫 y 軸
    pl.axis('equal')
    pl.axis([-5, 5, -5, 5])
    pl.show()
# 産生高斯分布的随機點
mean = [0, 0]      # 平均值
cov = [[2, 1], [1, 2]]   # 協方差
x, y = np.random.multivariate_normal(mean, cov, 1000).T
plotSamples(x, y)
covMat = np.matrix(np.cov(x, y))    # 求 x 與 y 的協方差矩陣
Z = np.linalg.cholesky(covMat).I  # 仿射矩陣
plotSamples(x, y, Z)
# 求馬氏距離 
print '\n到原點的馬氏距離分别是：'
print dist.mahalanobis([0,0], [3,3], covMat.I), dist.mahalanobis([0,0], [-2,2], covMat.I)
# 求變換後的歐幾裡得距離
dots = (Z * np.matrix([[3, -2, 0], [3, 2, 0]])).T
print '\n變換後到原點的歐幾裡得距離分别是：'
print dist.minkowski([0, 0], np.array(dots[0]), 2), dist.minkowski([0, 0], np.array(dots[1]), 2)
           

皮皮blog

其它距離度量方法

卡方檢驗[機率論：假設檢驗-t檢驗、卡方檢驗和AD-Fuller test ]

mutual information

Spearman's rank coefficient

Earth Mover's Distance

SimRank 相似：SimRank 疊代算法

SimRank來自圖論，說兩個變量相似，因為他們連結了同一個或相似的節點。

[漫談：機器學習中距離和相似性度量方法]

大規模相似度計算方法

[大規模資料相似度計算時，解決資料傾斜的問題的思路之一（分塊思想）]

皮皮blog

 徑向基函數核

徑向基函數核（Radial Basis Function, RBF kernel），也被稱為高斯核（Gaussian kernel）或平方指數核（Squared Exponential., SE kernel） [1]

 ，是常見的核函數（kernel function）。

關于兩個樣本x和x'的RBF核可表示為某個輸入空間（input space）的特征向量，它的定義如下：

上面的分子部分 可以看做兩個特征向量之間的平方歐氏距離。sigma 是一個自由參數。

因為RBF核函數的值随距離減小，并介于0（極限）和1（當x=x'的時候）之間，是以它是一種現成的相似性度量表示法。

核的特征空間有無窮多的維數；例如sigma=1時，其展開式為： 

 [徑向基函數核]

為何要選用核函數？

擷取非線性的方式[核函數與徑向基函數詳解]

高斯距離示例

#根據高斯距離進行高斯坐标轉換

def guass_kernel_trans(x, centers):

    '''

    坐标映射：x中的每一行都轉換成centers坐标系，即x中的每一行與centers一一作guass_kernel轉換，從x的次元d轉換成centers次元nc。

    :param x: 2d array (nx,d)

    :param centers: 2d array (nc,d)

    :return: 2d array

    '''

    import numpy as np

    x = np.asarray(x)

    centers = np.asarray(centers)

    x_t_guass = np.exp(-(np.sum(x ** 2, 1, keepdims=True).repeat(centers.shape[0], axis=1) +

                         np.sum(centers ** 2, 1, keepdims=True).repeat(x.shape[0], axis=1).transpose() -

                         x.dot(centers.transpose()) * 2))

    # exp内部是負平方歐氏距離

    # print(x_t_guass)

    x_t_guass = x_t_guass / x_t_guass.sum(axis=1, keepdims=True)

    #np.asarray([i / sum(i) for i in x_t_guass])

    return x_t_guass

userEmb = [[0.84, 0.8, 0.11, 0.85, 0.76, 0.1, 0.61, 0.6]]

Xc = [[0.84, 0.8, 0.11, 0.85, 0.76, 0.1, 0.61, 0.6], [0.77, 0.77, 0.2, 0.74, 0.6, 0.21, 0.69, 0.48]]

# print(guass_kernel_trans(userEmb, Xc))

Xc_ = guass_kernel_trans(Xc, Xc)

# print(Xc_)

距離函數的等價性

文本語料上訓練出來的特征向量習慣采用餘弦距離，圖檔或視訊上提取的特征向量一般采用歐氏距離。此外，還有特殊場景下定制的各種距離函數，此處介紹一個在搜尋排序場景中使用的angular相似度度量函數，其可有效放大被召回的頭部樣本點之間的差異。

歸一化向量之間的餘弦距離可以跟歐氏距離進行直接轉換，即euclidean_distance^2 = 1 - 2 * cosine_distance。是以很多代碼在實作歐氏距離時先做歸一化再直接相乘。

Note: 歸一化向量之間的餘弦距離可以跟歐氏距離進行直接轉換是因為： 歸一化的x^2=y^2=1，則到|x-y|^2 = 2-2x*y；通過繪圖也可以看出。

ANN召回場景下：1）即使不做歸一化，也可以直接讓歐氏距離與餘弦距離建立等價關系；2）任意向量内積的結果可與歐氏距離建立等價關系。

ANN中按歐氏距離計算出的近似K近鄰點與按内積或餘弦距離計算出來的近似K近鄰點結果相同，所要做的僅僅是對所有待檢索的向量做預處理即可，找出最大的常數φ，然後構造一個次元+1的新向量。

論文Speeding Up the Xbox Recommender System Using a Euclidean Transformation for Inner-Product Spaces

[距離函數的等價性]

非歐氏距離及其滿足公理性質的證明

Jaccard Dist

Note: Proof中使用反證法：兩個都不成立，即都相等時，minhash(x)=minhash(y)了。

Cosine Dist餘弦距離

Note: vectors here are really directions, not magnitudes.So two vectors with the same direction and different magnitudes are really the same vector.Even to vector and its negation, the reverse of the vector,ought to be thought of as the same vector.

Edit distance編輯距離

Hamming distance漢明距離

from:距離和相似度度量方法_皮皮blog-CSDN部落格_相似度度量方法

ref: 如何計算兩個文檔的相似度

Machine Learning: Measuring Similarity and Distance

What is Mahalanobis distance?

Cosine similarity, Pearson correlation, and OLS coefficients

機器學習中的相似性度量