相似度測度總結(jié)匯總

1、1 相似度文獻總結(jié)相似度有兩種基本類別：（1）客觀相似度，即對象之間的相似度是對象的多維特征之間的某種函數(shù)關(guān)系，比如對象之間的歐氏距離；（2）主觀相似度，即相似度是人對研究對象的認知關(guān)系，換句話說，相似度是主觀認知的結(jié)果，它取決于人及其所處的環(huán)境，主觀相似度符合人眼視覺需求，帶有一定的模糊性13。1.1 客觀相似度客觀相似度可分為距離測度、相似測度、匹配測度。它們都是衡量兩對象客觀上的相近程度?？陀^相似度滿足下面的公理，假設(shè)對象 A與B 的相似度判別為 ，有:(1) 自相似度是一個常量：所有對象的自相似度是一個常數(shù)，通常為 1，即(2) 極大性：所有對象的自相似度均大于它與其他對象間的相似度，

2、即。(3) 對稱性：兩個對象間的相似度是對稱的，即。(4) 唯一性：，當(dāng)且僅當(dāng) 。1.1.1 距離測度這類測度以兩個矢量矢端的距離為基礎(chǔ)，因此距離測度值是兩矢量各相應(yīng)分量之差的函數(shù)。設(shè)表示兩個矢量，計算二者之間距離測度的具體方式有多種，最常用的有： 歐氏距離：Euclidean Distance-based Similarity最初用于計算歐幾里德空間中兩個點的距離，假設(shè) x，y 是 n 維空間的兩個點，它們之間的歐幾里德距離是： （1.1）當(dāng)x，y是兩個直方圖時，該方法可稱為直方圖匹配法?？梢钥闯?，當(dāng) n=2 時，歐幾里德距離就是平面上兩個點的距離。當(dāng)用歐幾里德距離表示相似度，

3、一般采用以下公式進行轉(zhuǎn)換：距離越小，相似度越大。 （1.2）范圍：0,1，值越大，說明d越小，也就是距離越近，則相似度越大。 說明：由于特征分量的量綱不一致，通常需要先對各分量進行標(biāo)準化，使其與單位無關(guān)。歐氏距離能夠體現(xiàn)個體數(shù)值特征的絕對差異，所以更多的用于需要從維度的數(shù)值大小中體現(xiàn)差異的分析。優(yōu)點：簡單，應(yīng)用廣泛缺點：沒有考慮分量之間的相關(guān)性，體現(xiàn)單一特征的多個分量會干擾結(jié)果 曼哈頓距離，絕對值距離(街坊距離或 Manhattan 距離)：原理：曼哈頓距離來源于城市區(qū)塊距離，是將多個維度上的距離進行求和后的結(jié)果。同歐式距離相似，都是用于多維數(shù)據(jù)空間距離的測度 范圍：0,1，同歐

4、式距離一致，值越小，說明距離值越大，相似度越大。 說明：比歐式距離計算量少，性能相對高。 （1.3） 切氏(Chebyshev)距離（棋盤距離/切比雪夫距離）：切比雪夫距離起源于國際象棋中國王的走法，我們知道國際象棋國王每次只能往周圍的8格中走一步，那么從棋盤中A格（x1，y1）走到B格（x2，y2）最少需要走幾步？ （1.3） 明氏(Minkowski)距離/閔可夫斯基距離： （1.4）可以看出，(1.1)、(1.2)、(1.3)式實際上是(1.4)式當(dāng)?shù)奶厥馇闆r。在實際中較多地使用歐氏距離。顯然，在觀測量的量綱取定的條件下，兩個矢量越相似，距離就越小，反之亦然。

5、值得注意的是，在使用上述距離測度描述具體對象時，量綱選取不同會改變某特征的判斷依據(jù)，即改變該特征對判斷貢獻的大小，嚴重的可造成錯誤分類。這是因為改變特征矢量某分量的量綱，進行比較的兩個矢量的相應(yīng)的兩個分量的數(shù)值也將改變。若變小，則其相應(yīng)的特征在距離測度中“影響作用比重”將變小，即根據(jù)其判斷分類的作用變小，反之將增大，這樣便不能很好地反映事實。馬氏(Mahalanobis)距離是不受量綱影響的。 馬氏距離(Mahalanobis)：馬氏距離定義如下：設(shè)n維矢量和是矢量集中的兩個矢量，它們的馬氏距離 d 定義為 （1.5）式中，。V的含義是這個矢量集的協(xié)方差矩陣的統(tǒng)計量。適用場合：1

6、） 度量兩個服從同一分布并且協(xié)方差矩陣為C的隨機變量的差異程度2） 度量與某一類的均值向量的差異程度，判別樣本的歸屬，此時為類均值向量。優(yōu)點：1） 獨立于分量量綱2） 排除了樣本之間的相關(guān)性影響缺點：不同的特征不能差別對待，可能夸大弱特征 漢明距離（Hamming Distance）在信息論中，兩個等長字符串之間的漢明距離是兩個字符串對應(yīng)位置的不同字符的個數(shù)。換句話說，它就是將一個字符串變換成另一個字符串所需要替換的字符個數(shù)。例如：1011101與1001001之間的漢明距離是2。2143896與2233796之間的漢明距離是3?！皌oned”與“roses” 之間的漢明距離是3

7、。 巴氏距離（Bhattacharyya）巴氏距離常用于計算直方圖間相似度，定義如下： (1.6)其中，x、y為歸一化數(shù)據(jù)向量。Bhattacharyya系數(shù)取值在01之間，越靠近1，表示兩個模型之間相似度越高。如果，x、y向量未歸一化，則巴氏系數(shù)的計算定義為： （1.7） Hausdorff距離：Hausdorff距離(Hausdorff distance ,HD)是一種定義于兩個點集上的最大最小距離，是描述兩組點集之間的相似程度的一種量度，x、y之間的Hausdorff距離定義為： （1.8）式中，為x到y(tǒng)的有向Hausdorff距離；為y到x的有向Hausdo

8、rff距離；為某種定義在點集x、y上的距離范數(shù)。常用的是歐幾里得范數(shù)。如果定義(表示空間中的任意點)則Hausdorff距離可定義為,這里稱分別為點集y和點集x在空間中的變化距離。由于Hausdorff距離是度量兩個點集之間最不匹配點的距離，因此它對遠離中心的噪聲、漏檢點都非常敏感，而這一點，在提取圖像特征點集特征時使不可避免的。為了克服這個缺點，需要對Hausdorff距離的定義進行擴展。 改進的部分Hausdorff距離：為獲得準確的匹配結(jié)果，Sim提出了改進的部分Hausdorff距離（LTS-HD）,它是用距離序列的線性組合來定義的： （1.9）式中，p為x內(nèi)點的個數(shù)，為

9、一個屬于0,1的百分數(shù)。把點集x中的所有點到點集y的距離按由小到大的順序排列，將序號為1k的k個距離求和，再求平均。所以，該匹配方法不僅能消除遠離中心的錯誤匹配點的影響，而且對零均值高斯噪聲的消除能力明顯。因襲，采用LTS-HD用于圖像特征點集的匹配，力求在所有可能的變換空間中尋找圖像特征點集之間的最優(yōu)變換，以便通過使LTS-HD最小化來獲得最優(yōu)匹配結(jié)果。設(shè)g為變換空間T（通常由旋轉(zhuǎn)矩陣R、平移變換向量t、尺度c等變換組成）中的一個變換，則最優(yōu)匹配變換g0滿足 (1.10)0 相關(guān)度距離常用于計算直方圖間相似度，定義如下： （1.8）1 卡方系數(shù)常用于計算直方圖間相

10、似度，定義如下： （1.9）（備注：引自基于混合圖結(jié)構(gòu)的圖像相似度的研究_莊小芳，2013年福建師范大學(xué)碩士學(xué)位論文第一章，2.2節(jié)）2 （未命名）常用于計算直方圖間相似度，定義如下： （1.11）其中,N表示圖像顏色樣點空間,比起前面幾個計算公式,該式在給出圖像相似度的計算中更為直接,操作也更加簡便。（備注：引自基于混合圖結(jié)構(gòu)的圖像相似度的研究_莊小芳，2013年福建師范大學(xué)碩士學(xué)位論文第一章，2.2節(jié)）3 直方圖相交距離直方圖相交距離是常用于顏色特征相似性度量的一種方法，常用于計算直方圖間相似度。如果有兩幅圖像,則它們的相交距離定義式如下： （1.12）1.1.

11、2 相似測度這類測度是以兩矢量的方向是否相近作為考慮的基礎(chǔ)，矢量長度并不重要，同樣設(shè)。 角度相似系數(shù)(夾角余弦) 原理：多維空間兩點與所設(shè)定的點形成夾角的余弦值。 范圍：-1,1，值越大，說明夾角越大，兩點相距就越遠，相似度就越小。 說明：在數(shù)學(xué)表達中，如果對兩個項的屬性進行了數(shù)據(jù)中心化，計算出來的余弦相似度和皮爾森相似度是一樣的，所以皮爾森相似度值也是數(shù)據(jù)中心化后的余弦相似度。定義：矢量之間的相似度可用它們的夾角余弦來度量。兩個矢量x和 y 的夾角余弦定義如下： （1.6）與歐幾里德距離類似，基于余弦相似度的計算方法也是把特征點作為n-維坐標(biāo)系中的一個點，通過連接這個點與坐標(biāo)系

12、的原點構(gòu)成一條直線（向量），兩個特征點之間的相似度值就是兩條直線（向量）間夾角的余弦值。因為連接代表特征點與原點的直線都會相交于原點，夾角越小代表兩個特征越相似，夾角越大代表兩個特征的相似度越小。同時在三角系數(shù)中，角的余弦值是在-1, 1之間的，0度角的余弦值是1，180角的余弦值是-1。借助三維坐標(biāo)系來看下歐氏距離和余弦相似度的區(qū)別：從圖上可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐標(biāo)（即個體特征維度的數(shù)值）直接相關(guān)；而余弦相似度衡量的是空間向量的夾角，更加的是體現(xiàn)在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐標(biāo)軸原點，那么這個時候余弦相似度co

13、s是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發(fā)生改變，這就是歐氏距離和余弦相似度的不同之處。應(yīng)用：Cosine 相似度被廣泛應(yīng)用于計算文檔數(shù)據(jù)的相似度及數(shù)據(jù)挖掘類工作：特點：余弦相似度用向量空間中兩個向量夾角的余弦值作為衡量兩個個體間差異的大小。相比距離度量，余弦相似度更加注重兩個向量在方向上的差異，而非距離或長度上。它對于坐標(biāo)系的旋轉(zhuǎn)和尺度的縮放是不變的(因矢量的長度已規(guī)格化)，但對一般的線性變換和坐標(biāo)系的平移不具有不變性。 調(diào)整余弦相似度 Adjusted Cosine Similarity在余弦相似度的介紹中說到：余弦相似度更多的是從方向上區(qū)分差異，而對絕對的數(shù)值

14、不敏感。因此沒法衡量每個維數(shù)值的差異，會導(dǎo)致這樣一個情況：比如用戶對內(nèi)容評分，5分制，X和Y兩個用戶對兩個內(nèi)容的評分分別為(1,2)和(4,5)，使用余弦相似度得出的結(jié)果是0.98，兩者極為相似，但從評分上看X似乎不喜歡這兩個內(nèi)容，而Y比較喜歡，余弦相似度對數(shù)值的不敏感導(dǎo)致了結(jié)果的誤差，需要修正這種不合理性，就出現(xiàn)了調(diào)整余弦相似度，即所有維度上的數(shù)值都減去一個均值，比如X和Y的評分均值都是3，那么調(diào)整后為(-2,-1)和(1,2)，再用余弦相似度計算，得到-0.8，相似度為負值并且差異不小，但顯然更加符合現(xiàn)實。應(yīng)用：調(diào)整余弦相似度和弦相似度，皮爾遜相關(guān)系數(shù)在推薦系統(tǒng)中應(yīng)用較多。在基于項目的推薦

15、中GroupLens有篇論文結(jié)果表明調(diào)整余弦相似度性能要由于余弦相似度和皮爾遜相關(guān)系數(shù)。 相關(guān)系數(shù) 它實際上是數(shù)據(jù)中心化后的矢量夾角余弦。 （1.7）此處將 , 視作兩個數(shù)據(jù)集的樣本，和 分別是這兩個數(shù)據(jù)集的平均矢量。相關(guān)系數(shù)對于坐標(biāo)系的平移、旋轉(zhuǎn)和尺度縮放是不變的。（備注：該節(jié)引自 項德良【SAR 圖像相似度評估技術(shù)研究】，2012年國防科大碩士論文1.2節(jié)。） 指數(shù)相似系數(shù) 指數(shù)相似系數(shù)定義如下： （1.8）式中， 為相應(yīng)分量的方差，n為矢量維數(shù)。它不受量綱變化的影響。從函數(shù)的構(gòu)造上看屬于距離方式(類似于馬氏距離)，但從測度值和相似關(guān)系看屬于相似測度。（備注：該

16、節(jié)引自 項德良【SAR 圖像相似度評估技術(shù)研究】，2012年國防科大碩士論文1.2節(jié)。） 對數(shù)似然相似度Ted Dunning在1993年提出一種對數(shù)似然比的概念，主要應(yīng)用于自然文本語言庫中兩個詞的搭配關(guān)系問題。它是基于這樣一種思想，即統(tǒng)計假設(shè)可以確定一個空間的很多子空間，而這個空間是被統(tǒng)計模型的位置參數(shù)所描述。似然比檢驗假設(shè)模型是已知的，但是模型的參數(shù)是未知的。二項分布的對數(shù)似然比對于二項分布的情況，似然函數(shù)為 （1.1）式中：的統(tǒng)計模型，試驗結(jié)果的參數(shù)。給定模型的參數(shù)。假設(shè)二項分布有相同的基本參數(shù)集合，那么對數(shù)似然比就是 （1.2）式中：當(dāng)取得某值時，統(tǒng)計模型的最大值。當(dāng)時，

17、分母取得最大值。當(dāng)時，分子取得最大值。所以對數(shù)似然比簡化為 （1.3）式中：二項分布，實驗重復(fù)的次數(shù)，某事發(fā)生的概率，該事件發(fā)生的次數(shù)，。兩邊取對數(shù)可以將對數(shù)似然比的公式變形為： （1.4）由于二項分布的對數(shù)似然比能夠合理的描述兩個事物的相似模型，所以常用對數(shù)似然比來計算兩個事物（用戶或物品）的相似度。對數(shù)似然相似度基于兩個用戶共同評估過的物品數(shù)目，但在給定物品總數(shù)和每個用戶評價的情況下，其最終結(jié)果衡量的是兩個用戶有這么多共同物品的“不可能性”，它是一種不考慮具體偏好值的方法。比如在用戶物品偏好的二維矩陣中，我們可以將一個用戶對所有物品的偏好作為一個向量來計算用戶之間的相似度，或者將所有用戶對

18、某個物品的偏好作為一個向量來計算物品之間的相似度。備注：引自張明敏，張功萱對數(shù)似然相似度算法的MapReduce并行化實現(xiàn)計算機工程與設(shè)計2015,36卷，第5期。 Levenshtein 距離,又稱編輯距離兩個字符串（鏈）的相似度可以用Levenshtein距離（Levenshtein distance）表示，該距離定義為將一個串變?yōu)榱硪粋€串所需的最小操作步數(shù)，可能的操作有刪除、插入、替換Schlesinger and Hlavac ,2002。還可以給字符串元素變換賦一個變換代價，從而使計算得到的相似度（距離）更靈活，更敏感。同樣的原理也可以用在圖相似度的計算上。下定義可能的

19、結(jié)點和弧的變換（刪除、插入、替換、重新標(biāo)注）集合，再給每種變換賦一個變換代價。任一變換序列的代價用單個步驟代價的組合表示（類似代價步驟的和）。將一個圖變?yōu)榱硪粋€圖的所有變換集合中具有最小代價值的那個集合就定義了這兩幅圖間的距離Niemann,1990。用途：常用于字符串距離，類似可用于計算圖的距離備注：引用于圖像處理、分析與機器視覺（第三版）Milan Sonka ,Vaclav Hlavac, Roger Boyle著，艾海舟，蘇延超譯P298，9.5.2 圖的相似度 統(tǒng)計相關(guān)系數(shù)-皮爾遜相關(guān)系數(shù)（Pearson Correlation Coefficient）皮爾遜相關(guān)也稱積

20、差相關(guān)（積矩相關(guān)），即相關(guān)分析中的相關(guān)系數(shù)，分別對基于自身總體標(biāo)準化后計算余弦向量的標(biāo)準夾角。是英國統(tǒng)計學(xué)家皮爾遜于20世紀提出的一種計算直線相關(guān)的方法。皮爾遜相關(guān)系數(shù)一般用來反映兩個變量線性相關(guān)程度，它的取值在 -1，+1 之間。相關(guān)系數(shù)的絕對值越大，相關(guān)性越強。假設(shè)有兩個變量，那么；兩個變量間的皮爾遜相關(guān)系數(shù)可以通過以下公式計算：公式一：公式二：公式三：公式四：以上列出四個公式等價，其中E是數(shù)學(xué)期望，cov表示方差，N表示變量取值的個數(shù)。適用范圍：當(dāng)兩個變量對的標(biāo)準差都不為0時，相關(guān)系數(shù)才有定義，皮爾遜系數(shù)適用于：（1） 兩個變量之間是線性關(guān)系，都是連續(xù)數(shù)據(jù)（2） 兩個變量的總體是正態(tài)分布

21、，或接近正態(tài)的單峰分布（3） 兩個變量的觀測值是成對的，每對觀測值之間互相獨立特點：（1）當(dāng)兩個變量的線性關(guān)系增強時，相關(guān)系數(shù)趨于1或-1；（2）當(dāng)一個變量增大，另一個變量也增大時，表明它們之間是正相關(guān)的，相關(guān)系數(shù)大于0；（3）如果一個變量增大，另一個變量卻減小，表明它們之間是負相關(guān)的，相關(guān)系數(shù)小于0；（4）如果相關(guān)系數(shù)等于0，表明它們之間不存在線性相關(guān)關(guān)系。 統(tǒng)計相關(guān)系數(shù)-斯皮爾曼相關(guān)（Spearman秩相關(guān)）系數(shù)-Spearman Correlation（1） 簡介在統(tǒng)計學(xué)中，斯皮爾曼等級相關(guān)系數(shù)以Charles Spearman命名，并經(jīng)常用希臘字母表示其值。斯皮爾曼等級相

22、關(guān)系數(shù)用來估計兩個變量之間的相關(guān)性，其中變量間的相關(guān)性可以用單調(diào)函數(shù)來描述。如果兩個變量取值的兩個集合中均不存在相同的兩個元素，那么，當(dāng)其中一個變量可以表示為另一個變量的很好的單調(diào)函數(shù)時（即兩個變量的變化趨勢相同），兩個變量之間的可以達到+1或-1。假設(shè)兩個隨機變量分別為（也可以看做是兩個集合），它們的元素個數(shù)均為N，兩個隨機變量取的第個值分別用表示。對進行排序（同為升序或降序），得到兩個元素排行集合，其中元素分別為在中的排行以及在中的排行。將集合中的元素對應(yīng)相減得到一個排行差分集合d,其中，。隨機變量之間的斯皮爾曼等級相關(guān)系數(shù)可由或d計算得到，其計算方式如下：公式一：由排行差分集合d計算而得

23、（）：公式二：由排行集合計算而得（斯皮爾曼等級相關(guān)系數(shù)同時也被認為是經(jīng)過排行的兩個隨機變量的皮爾遜相關(guān)系數(shù)，以下實際是計算的皮爾遜相關(guān)系數(shù)）：以下是一個計算集合中元素排行的例子（僅適用于斯皮爾曼等級相關(guān)系數(shù)的計算）變量元素的位置（依降序排列）變量的排行（）1540.2451.33（2+3）/2=2.51.32（2+3）/2=2.51011這里需要注意：當(dāng)變量的兩個值相同時，它們的排行是通過對它們的位置進行平均得到的。（2） 適用范圍斯皮爾曼等級相關(guān)系數(shù)對數(shù)據(jù)條件的要求沒有皮爾遜相關(guān)系數(shù)嚴格，只要兩個變量的觀測值是成對的等級評定資料，或者是由連續(xù)變量觀測資料轉(zhuǎn)化得到的等級資料，不論兩個變量的整體

24、分布形態(tài)、樣本容量的大小如何，都可以用斯皮爾曼等級相關(guān)系數(shù)來進行研究。原理：Spearman秩相關(guān)系數(shù)通常被認為是排列后的變量之間的Pearson線性相關(guān)系數(shù)。 （3）取值范圍：-1.0,1.0，當(dāng)一致時為1.0，不一致時為-1.0。 （4）說明：計算非常慢，有大量排序。針對推薦系統(tǒng)中的數(shù)據(jù)集來講，用Spearman秩相關(guān)系數(shù)作為相似度量是不合適的。一般用于學(xué)術(shù)研究或者是小規(guī)模的計算。（5）Spearman相關(guān)系數(shù)的特點：Spearman相關(guān)是根據(jù)等級資料研究兩個變量間相關(guān)關(guān)系的方法。它是依據(jù)兩列成對等級的各對等級數(shù)之差來進行計算的，所以又稱為“等級差數(shù)法”1， Spearman相關(guān)系數(shù)對原始

25、變量的分布不做要求，屬于非參數(shù)統(tǒng)計方法。因此它的適用范圍比Pearson相關(guān)系數(shù)要廣的多。即使原始數(shù)據(jù)是等級資料也可以計算Spearman相關(guān)系數(shù)。對于服從Pearson相關(guān)系數(shù)的數(shù)據(jù)也可以計算Spearman相關(guān)系數(shù)，2， 統(tǒng)計效能比Pearson相關(guān)系數(shù)要低一些（不容易檢測出兩者事實上存在的相關(guān)關(guān)系）。3， spearman只要兩個變量的觀測值是成對的等級評定資料，或者是由連續(xù)變量觀測資料轉(zhuǎn)化得到的等級資料，不論兩個變量的總體分布形態(tài)、樣本容量的大小如何，都可以用斯皮爾曼等級相關(guān)來進行研究。注：spearman與pearson：1. 連續(xù)數(shù)據(jù)，正態(tài)分布，線性關(guān)系，用pearson相關(guān)系數(shù)是

26、最恰當(dāng)，當(dāng)然用spearman相關(guān)系數(shù)也可以，就是效率沒有pearson相關(guān)系數(shù)高。2. 上述任一條件不滿足，就用spearman相關(guān)系數(shù)，不能用pearson相關(guān)系數(shù)。3. 兩個定序測量數(shù)據(jù)之間也用spearman相關(guān)系數(shù)，不能用pearson相關(guān)系數(shù)。 4 .只要在X和Y具有單調(diào)的函數(shù)關(guān)系的關(guān)系，那么X和Y就是完全Spearman相關(guān)的，這與Pearson相關(guān)性不同，后者只有在變量之間具有線性關(guān)系時才是完全相關(guān)的。 統(tǒng)計相關(guān)系數(shù)-Kendall Rank(肯德爾等級)相關(guān)系數(shù)（1） 簡介在統(tǒng)計學(xué)中，肯德爾相關(guān)系數(shù)是以Maurice Kendall命名的，并經(jīng)常用希臘字母（ta

27、u）表示其值?？系聽栂嚓P(guān)系數(shù)是一個用來測量兩個隨機變量相關(guān)性的統(tǒng)計值。一個肯德爾檢驗是一個無參假設(shè)檢驗，它使用計算而得的相關(guān)系數(shù)去檢驗兩個隨機變量的統(tǒng)計依賴性?？系聽栂嚓P(guān)系數(shù)的取值范圍在-1到1之間，當(dāng)為1時，表示兩個隨機變量擁有一致的等級相關(guān)性，當(dāng)為-1時，表示兩個隨機變量擁有完全相反的等級相關(guān)性，當(dāng)為0時，表示兩個隨機變量是相互獨立的。假設(shè)兩個隨機變量分別為（也可以看做是兩個集合），它們的元素個數(shù)均為N，兩個隨機變量取的第個值分別用表示。中的對應(yīng)元素組成一個元素對集合,其包含的元素為。當(dāng)集合中任意兩個元素與的排行相同時（也就是說當(dāng)出現(xiàn)情況1或2時；情況1: ,情況2：），這兩個元素就被認為

28、是一致的。當(dāng)出現(xiàn)情況3或4時（情況3: ,情況4：），這兩個元素就被認為是不一致的。當(dāng)出現(xiàn)情況5或6時（情況5: ,情況6：），這兩個元素既不是一致也不是不一致的。這里有三個公式計算肯德爾相關(guān)系數(shù)的值：公式一：其中C表示XY中擁有一致性的元素對數(shù)（兩個元素為一對），D表示XY中擁有不一致性的元素對數(shù)。注意：這一公式僅適用于集合X與Y中不存在相同元素的情況（集合中各個元素唯一）公式二：注意：這一公式適用于集合X或Y中存在相同元素的情況（當(dāng)然，如果X或Y中均不存在相同的元素時，公式二便等同于公式一）。其中C、D與公式一相同；N1、N2分別是針對集合X、Y計算的，現(xiàn)在以計算N1為例，給出N1的由來（

29、N2的計算可以類推）：將X中的相同元素分別組合成小集合，s表示集合X中擁有的小集合數(shù)（例如X包含元素：1 2 3 4 3 3 2，那么這里得到的s則為2，因為只有2、3有相同的元素），表示第i個小集合所包含的元素數(shù)。N2在集合Y的基礎(chǔ)上計算而得。公式三：注意：這一公式中沒有再考慮集合、或者中存在相同元素給最后的統(tǒng)計值帶來的影響。公式三的這一計算形式僅適用于用表格表示的隨機變量X、Y之間相關(guān)系數(shù)的計算（下面會介紹），參數(shù)M稍后會做介紹。以上都是圍繞用集合表示的隨機變量而計算肯德爾相關(guān)系數(shù)的，下面所講的則是圍繞用表格表示的隨機變量而計算肯德爾相關(guān)系數(shù)的。通常人們會將兩個隨機變量的取值制作成一個表格

30、，例如有10個樣本，對每個樣本進行兩項指標(biāo)些事（指標(biāo)的取值均為1到3）。根據(jù)樣本的指標(biāo)取值，得到以下二維表格（表1）：表1123Sum112032121430123sum25310由表1 可以得到的可以以集合的形式表示為：得到的集合形式后就可以使用以上的公式一或公式二計算的肯德爾相關(guān)系數(shù)了（注意公式一、公式二的適用條件）當(dāng)然如果給定的集合形式，那么也是很容易得到它們的表格形式的。這里需要注意的是：公式二也可以用來計算表格形式表示的二維變量的肯德爾相關(guān)系是，不過它一般用來計算由正方形表格表示的二維變量的肯德爾相關(guān)系數(shù)，公式三則只是用來計算由長方形表格表示的二維變量的Kendall相關(guān)系數(shù)。這里給

31、出公式三種字母的含義，表示長方形表格中行數(shù)與列數(shù)中較小的一個。表1的行數(shù)及列數(shù)均為三。（2） 適用范圍肯德爾相關(guān)系數(shù)與斯皮爾曼相關(guān)系數(shù)對數(shù)據(jù)的條件要求相同。0 Tanimoto 系數(shù)（Tanimoto Coefficient）Tanimoto 系數(shù)也稱為 廣義Jaccard 系數(shù)，是 Cosine 相似度的擴展，通常應(yīng)用于、為布爾向量，即各分量只取0或1的時候，此時表示的是、的公共特征占、具有的所有特征的比例。其實質(zhì)就是集合交集與并集的比。也多用于計算文檔數(shù)據(jù)的相似度，或兩個集合之間的相似程度。范圍：0,1，越接近1說明越相似。 1 Jaccard 系數(shù)Jaccar

32、d 系數(shù)主要用于計算符號度量或布爾值度量的個體間的相似度，因為個體的特征屬性都是由符號度量或者布爾值標(biāo)識，因此無法衡量差異具體值的大小，只能獲得“是否相同”這個結(jié)果，所以Jaccard 系數(shù)只關(guān)心個體間共同具有的特征是否一致這個問題。如果比較的Jaccard 相似系數(shù)，只比較中相同的個數(shù)，公式如下：也就是關(guān)聯(lián)的交集除以關(guān)聯(lián)的并集。范圍：其值介于0, 1之間，如果兩個個體間的特征完全相同，交集等于并集，值為1；如果沒有任何關(guān)聯(lián)，交集為空，值為0。1.1.3 匹配測度 （備注：該節(jié)引自 項德良【SAR 圖像相似度評估技術(shù)研究】，2012年國防科大碩士論文1.2節(jié)。）這種測度常用于醫(yī)學(xué)和生物的分類中

33、。在有些情況下，特征只有兩個狀態(tài)，對象或具有此特征或不具有此特征。此時，若對象具有此特征，則相應(yīng)分量定義為 1，而相應(yīng)分量為 0 表示對象無此特征，這就是所謂的二值特征。對于給定的二值特征矢量x和 y 中的某兩個相應(yīng)分量和，若和，則稱和是（1-1）匹配，若和，則稱和是（1-0）匹配；若和，則稱和是（0-1）匹配；若，則稱和是（0-0）匹配，令 （1.9）則a等于兩矢量 x 和 y 的(1-1)匹配的特征的數(shù)目，b 等于 x 和 y 的(0-1)匹配的特征的數(shù)目，c等于x和 y 的(1-0)匹配的特征的數(shù)目，e等于x和 y 的(0-0)匹配的特征的數(shù)目。對于二值n維特征矢量可定義如下相似性測度：

34、 Tanimoto 測度 （1.10）可以看出， s ( x , y )等于x 和 y 都具有的特征的數(shù)目與 x和 y 分別具有的特征種類總數(shù)之比。這里只考慮(1-1)匹配而不考慮(0-0)匹配。 Rao 測度 （1.11）上式等于(1-1)匹配特征數(shù)目和所選用的特征數(shù)目之比。 簡單匹配系數(shù) （1.12）上式表明，這時匹配系數(shù)分子為(1-1)匹配特征數(shù)目與(0-0)匹配特征數(shù)目之和，分母為所選用的特征數(shù)目。 Dice 系數(shù) （1.13）分子、分母無(0-0)匹配，對(1-1)匹配加權(quán)。 Kulzinsky 系數(shù) （1.14）

35、上式分子為(1-1)匹配特征數(shù)目，分母為(1-0)和(0-0)匹配特征數(shù)目之和。1.2 主觀相似度1.2.1 結(jié)構(gòu)相似度（SSIM,structural similarity (SSIM) index measurement）（備注：該節(jié)引自 項德良【SAR 圖像相似度評估技術(shù)研究】，2012年國防科大碩士論文1.2節(jié)。）結(jié)構(gòu)相似性理論認為，自然圖像信號是高度結(jié)構(gòu)化的，即像素間有很強的相關(guān)性，特別是空域中最接近的像素，這種相關(guān)性蘊含著視覺 場景中物體結(jié)構(gòu)的重要信息；HVS的主要功能是從視野中提取結(jié)構(gòu)信息，可以用對結(jié)構(gòu)信息的度量作為圖像感知質(zhì)量的近似。結(jié)構(gòu)相似性理論是一種不同于以往模 擬HVS低

36、階的組成結(jié)構(gòu)的全新思想，與基于HVS特性的方法相比，最大的區(qū)別是自頂向下與自底向上的區(qū)別。這一新思想的關(guān)鍵是從對感知誤差度量到對感知結(jié) 構(gòu)失真度量的轉(zhuǎn)變。它沒有試圖通過累加與心理物理學(xué)簡單認知模式有關(guān)的誤差來估計圖像質(zhì)量，而是直接估計兩個復(fù)雜結(jié)構(gòu)信號的結(jié)構(gòu)改變，從而在某種程度上繞 開了自然圖像內(nèi)容復(fù)雜性及多通道去相關(guān)的問題.作為結(jié)構(gòu)相似性理論的實現(xiàn)，結(jié)構(gòu)相似度指數(shù)從圖像組成的角度將結(jié)構(gòu)信息定義為獨立于亮度、對比度的，反映場景中物體結(jié)構(gòu)的屬性，并將失真建模為亮度、對比度和結(jié)構(gòu)三個不同因素的組合。用均值作為亮度的估計，標(biāo)準差作為對比度的估計，協(xié)方差作為結(jié)構(gòu)相似程度的度量。(from Interne

37、t)Zhou Wang 在 2004 年提出一種結(jié)構(gòu)相似度準則 SSIM(Structural Similarity Index Measurement)來衡量光學(xué)圖像相似度。該準則分析了人眼視覺特性和圖像結(jié)構(gòu)之間的關(guān)系，從圖像空間、人眼視覺和圖像結(jié)構(gòu)等方面對SSIM進行了研究，在光學(xué)圖像的配準、目標(biāo)識和圖像質(zhì)量評估方面得到了有效驗證16。SSIM準則側(cè)重人眼的主觀感受，它是從圖像的客觀信息出發(fā)，通過建立模型從而得到的符合人眼視覺的準則。結(jié)構(gòu)相似度定義如下： （1.2.1）為亮度相似度函數(shù)，其中，為當(dāng)、為零時定義的常量。對比度相似度函數(shù)定義如下： （1.16）其中，。也為一個常量。結(jié)構(gòu)相似度函

38、數(shù)定義如下： （1.17）其中。綜上，結(jié)構(gòu)相似度指數(shù)(SSIM)定義如下： （1.18）其中均大于 0，為控制三個分量相似度權(quán)重的參數(shù)。 SSIM ( x , y )越接近于 1，則表明x與 y 越相似，否則越不相似。近年來基于語義測度的主觀相似度準則得到越來越多學(xué)者的關(guān)注。該方法一般在圖像分割的基礎(chǔ)上，通過構(gòu)建圖像區(qū)域子塊與語義元數(shù)據(jù)之間的統(tǒng)計映射關(guān)系，實現(xiàn)圖像內(nèi)容的統(tǒng)計語義描述，建立圖像之間、圖像與語義類別、語義類別之間的分層語義相似測度23-26。該方法充分考慮人眼視覺的語義層面，在圖像檢索等應(yīng)用中得到有效驗證。1.3 基于像素差值編碼的相似度1.3.1 像素差值編碼規(guī)則 給定一幅 SA

39、R 圖像，J 和K 為圖像高度和寬度。 G ( x , y )為圖像在( x , y )處灰度值。 B 是對應(yīng)的編碼圖像，其大小也為， B ( x , y )為 ( x , y )處編碼值，定義如下 （2.1）式(2.1)中SAR圖像像素值比較是按從左到右、從上到下的順序。圖 2.1所示為SAR圖像編碼圖示。1.3.2 相似性測度及其概率密度函數(shù) 和 為待比較的兩幅SAR圖像， 和 分別為對應(yīng)的編碼圖像，基于像素差值編碼的相似性測度(Intensity increment code-IIC)定義如下所示： （2.2）式(2.2)中，分別為編碼圖像和 在 ( x , y )處編碼值。衡量了兩幅編

40、碼圖像的相似性，也即反映了兩幅SAR圖像灰度變化是否一致，評價：該方法對圖像噪聲、部分遮擋和一定程度模糊有一定魯棒性。然而該方法著重統(tǒng)計全局圖像灰度信息，較少考慮圖像局部細節(jié)，因此對細節(jié)豐富的 SAR 圖像并不太適用。1.4 基于 KL 距離準則的相似度比較灰度直方圖相似性的方法很多，本文采用一種對稱KL準則SKLD(Symmetry Kullback-Leibler Divergence)64。對兩個局部梯度比率直方圖H 和Q，定義SKLD如下： （3.1）其中，和 分別為 H 和 Q 的MLGRPH特征矢量，N 為特征矢量的維數(shù)。由于相似度范圍為0,1，即完全相似時，相似度為1，此時SKL

41、D 為0，當(dāng)完全不相似時，相似度為0，SKLD 為，因此這里需要將SKLD 變換為范圍在0,1之間的相似度。我們采用最簡單的高斯隸屬度函數(shù)，如下所示： (3.2)其中，為控制高斯函數(shù)寬度的參數(shù)，可通過來控制距離與相似度變化關(guān)系。1.5 基于hash方法的相似度計算基于hash的相似度計算方法，是一種基于概率的高維度數(shù)據(jù)的維度削減的方法，主要用于大規(guī)模數(shù)據(jù)的壓縮與實時或者快速的計算場景下，基于hash方法的相似度計算經(jīng)常用于高維度大數(shù)據(jù)量的情況下，將利用原始信息不可存儲與計算的問題轉(zhuǎn)化為映射空間的可存儲計算問題，在海量文本重復(fù)性判斷方面，近似文本查詢方面有比較多的應(yīng)用，google的網(wǎng)頁去重1，

42、google news的協(xié)同過濾2,3等都是采用hash方法進行近似相似度的計算，比較常見的應(yīng)用場景Near-duplicate detection、Image similarity identification、nearest neighbor search，常用的一些方法包括I-match，Shingling、Locality-Sensitive Hashing族等方法，下面針對幾種常見的hash方法進行介紹。1.5.1 minhash方法介紹 Minhash方法是Locality-sensitive hashing4,5算法族里的一個常用方法，基本的思想是，對于每一個對象的itemlis

43、t，將輸入的item進行hash，這樣相似的item具有很高的相似度被映射到相同的buckets里面，這樣盡量保證了hash之后兩個對象之間的相似程度和原來是高相似的，而buckets的數(shù)量是遠遠小于輸入的item的，因此又達到降低復(fù)雜度的目的。 minhash方法用Jaccard進行相似度的計算方法，則對于兩個集合 和 ， 和 的相似性的計算方法為： （1.6.1）當(dāng)兩個集合越相似，則該值越接近1，否則越接近0。用minhash方法，將一個集合映射到0-R-1之間的值，以相同的概率隨機的抽取一個0-R-1的一個排列，依次排列查找第一次出現(xiàn)1的行。設(shè)隨機排列為43201(edcab)，對于C1

44、列，第一次出現(xiàn)1的行是R4，所以h(C1) = 3，同理有h(C2)=2, h(C3)=4, h(C4)=3。通過多次抽取隨機排列得到n個minhash函數(shù)h1,h2,hn，依此對每一列都計算n個minhash值。對于兩個集合，看看n個值里面對應(yīng)相等的比例，即可估計出兩集合的Jaccard相似度?？梢园衙總€集合的n個minhash值列為一列，得到一個n行C列的簽名矩陣。因為n可遠小于R，這樣在壓縮了數(shù)據(jù)規(guī)模的同時，并且仍能近似計算出相似度。1.5.2 simhash方法介紹simhash方法是在大文本重復(fù)識別常用的一個方法，該方法主要是通過將對象的原始特征集合映射為一個固定長度的簽名，將對象之

45、間的相似度的度量轉(zhuǎn)化為簽名的漢明距離，通過這樣的方式，極大限度地進行了降低了計算和存儲的消耗。1.5.3 簽名計算過程該方法通過對輸入特征集合的計算步驟可以描述如下：1， 將一個f維的向量V初始化為0；f位的二進制數(shù)S初始化為0；2， 對每一個特征：用傳統(tǒng)的hash算法對該特征產(chǎn)生一個f位的簽名b。對i=1到f：如果b的第i位為1，則V的第i個元素加上該特征的權(quán)重；否則，V的第i個元素減去該特征的權(quán)重。 1， 如果V的第i個元素大于0，則S的第i位為1，否則為0；2， 輸出S作為簽名。通過上述步驟將輸入的表示對象的特征集合轉(zhuǎn)化為該對象的一個簽名，在完成簽名之后，度量兩個對象的相似度的差異即變成

46、了對量二者的指紋的K位的差異情況。1.5.4 漢明距離查找優(yōu)化對于如何快速查找出某一個簽名是否與其存在最大差異不超過K個bit的指紋，Detecting Near-Duplicates for Web Crawling這篇論文中進行了介紹。該查找方法的基本思想是利用空間換時間的方法，該方法的依據(jù)是需要查找的兩個指紋的差異很小，這樣可以通過將原始指紋進行分塊索引，如果兩個指紋的差異很小，則合理的分塊后，根據(jù)鴿籠原理，其中存在一定數(shù)量的塊是一致的，通過利用相同的塊進行相似的指紋的召回，只需要比對召回的塊中有差異的塊的bit差異，這樣減少了需要比對的數(shù)量，節(jié)省了比對的時間開銷。1.5.5 小結(jié)has

47、h方法的相似度計算的主要應(yīng)用場景，一般是針對大規(guī)模數(shù)據(jù)進行壓縮，在保證效果損失可接受的情況下，節(jié)省存儲空間，加快運算速度，針對該方法的應(yīng)用，在目前的大規(guī)模的互聯(lián)網(wǎng)處理中，很多相似度的計算都是基于這種近似性的計算，并取得了比較好的效果。設(shè)隨機排列為43201(edcab)，對于C1列，第一次出現(xiàn)1的行是R4，所以h(C1) = 3，同理有h(C2)=2, h(C3)=4, h(C4)=3。通過多次抽取隨機排列得到n個minhash函數(shù)h1,h2,hn，依此對每一列都計算n個minhash值。對于兩個集合，看看n個值里面對應(yīng)相等的比例，即可估計出兩集合的Jaccard相似度?？梢园衙總€集合的n個m

48、inhash值列為一列，得到一個n行C列的簽名矩陣。因為n可遠小于R，這樣在壓縮了數(shù)據(jù)規(guī)模的同時，并且仍能近似計算出相似度。1.6 基于主題的相似度計算Bag-of-Words 模型是NLP和IR領(lǐng)域中的一個基本假設(shè)。在這個模型中，一個文檔(document)被表示為一組單詞(word/term)的無序組合，而忽略了語法或者詞序的部分。BOW在傳統(tǒng)NLP領(lǐng)域取得了巨大的成功，在計算機視覺領(lǐng)域(Computer Vision)也開始嶄露頭角，但在實際應(yīng)用過程中，它卻有一些不可避免的缺陷，比如：l 稀疏性(Sparseness): 對于大詞典，尤其是包括了生僻字的詞典，文檔稀疏性不可避免；l 多義

49、詞(Polysem): 一詞多義在文檔中是常見的現(xiàn)象，BOW模型只統(tǒng)計單詞出現(xiàn)的次數(shù)，而忽略了他們之間的區(qū)別；l 同義詞(Synonym): 同樣的，在不同的文檔中，或者在相同的文檔中，可以有多個單詞表示同一個意思；從同義詞和多義詞問題我們可以看到，單詞也許不是文檔的最基本組成元素，在單詞與文檔之間還有一層隱含的關(guān)系，我們稱之為主題(Topic)。我們在寫文章時，首先想到的是文章的主題，然后才根據(jù)主題選擇合適的單詞來表達自己的觀點。主題的概念的引入，主要是在原有的基本特征粒度的基礎(chǔ)上，引入了更為豐富的隱含層特征，提高了相似性計算的效果，常用的主題分析方法包括Latent Semantic An

50、alysis (LSA) 、 Probabilitistic Latent Semantic Analysis (PLSA)、Latent Dirichlet Allocation ( LDA)。這些方法在分類，聚類、檢索、推薦等領(lǐng)域都有著很多的應(yīng)用，并取得了比較好的效果。下面就LSA及PLSA方法進行簡要介紹。1.6.1 LSA（Latent Semantic Analysis）簡介LSA的基本思想就是，將document從稀疏的高維Vocabulary空間映射到一個低維的向量空間，我們稱之為隱含語義空間(Latent Semantic Space).LSA最初是用在語義檢索上，為了解決一詞

51、多義和一義多詞的問題： 1.一詞多義： 美女和PPMM表示相同的含義，但是單純依靠檢索詞“美女”來檢索文檔，很可能喪失掉那些包含“PPMM”的文檔。 2.一義多詞：如果輸入檢索詞是多個檢索詞組成的一個小document，例如“清澈 孩子”，那我們就知道這段文字主要想表達concept是和道德相關(guān)的，不應(yīng)該將“春天到了，小河多么的清澈”這樣的文本包含在內(nèi)。 為了能夠解決這個問題，需要將詞語（term）中的concept提取出來，建立一個詞語和概念的關(guān)聯(lián)關(guān)系（t-c relationship），這樣一個文檔就能表示成為概念的向量。這樣輸入一段檢索詞之后，就可以先將檢索詞轉(zhuǎn)換為概念，再通過概念去匹配

52、文檔。LSA6,7模型認為特征之間存在某種潛在的關(guān)聯(lián)結(jié)構(gòu)，通過特征-對象矩陣進行統(tǒng)計計算，將高維空間映射到低維的潛在語義結(jié)構(gòu)上，構(gòu)建出LSA空間模型，從而提取出潛在的語義結(jié)構(gòu)，并用該結(jié)構(gòu)表示特征和對象，消除了詞匯之間的相關(guān)性影響，并降低了數(shù)據(jù)維度。增強了特征的魯棒性LSA利用SVD分解的數(shù)學(xué)手段來進行計算，數(shù)學(xué)過程可以表述如下：對于的矩陣A，其中m為特征數(shù)，n為樣本數(shù)。令 ，經(jīng)過奇異值分解，矩陣A可分解成3個矩陣的乘積：其中，U、V是 和 的正交矩陣，分別稱為矩陣A的奇異值對應(yīng)的左、右奇異向量，是包含所有奇異值的 的對角矩陣，稱為A的奇異標(biāo)準形，其對角元素為矩陣A的奇異值。奇異值按照遞減的排列

53、構(gòu)成對角矩陣 ，取 中前k個最大奇異值構(gòu)成的，取U和V最前面的k列構(gòu)成的Uk和的Vk，構(gòu)建A的k-秩矩陣。（LSA降維的方式就是只取最大的K個奇異值，而其他置為0，于是得到了共生矩陣的近似。） 其中，Uk和Vk 中的行向量分別作為特征向量和對象向量，k是降維后的維數(shù)。下圖形象的展示了LSA的過程：LSA的優(yōu)點l 低維空間表示可以刻畫同義詞，同義詞會對應(yīng)著相同或相似的主題；l 降維可去除部分噪聲，是特征更魯棒；l 充分利用冗余數(shù)據(jù)；l 無監(jiān)督/完全自動化；l 與語言無關(guān)；LSA的不足l 沒有刻畫term出現(xiàn)次數(shù)的概率模型；l 無法解決多義詞的問題；l SVD的優(yōu)化目標(biāo)基于L-2 norm 或者是

54、 Frobenius Norm的，這相當(dāng)于隱含了對數(shù)據(jù)的高斯噪聲假設(shè)。而term出現(xiàn)的次數(shù)是非負的，這明顯不符合Gaussian假設(shè)，而更接近Multi-nomial分布；l 對于count vectors 而言，歐式距離表達是不合適的（重建時會產(chǎn)生負數(shù)）；l 特征向量的方向沒有對應(yīng)的物理解釋；l SVD的計算復(fù)雜度很高，而且當(dāng)有新的文檔來到時，若要更新模型需重新訓(xùn)練；l 維數(shù)的選擇是ad-hoc的；1.6.2 plas介紹 PLSA和LSA基礎(chǔ)思想是相同的，都是希望能從term中抽象出概念，但是具體實現(xiàn)的方法不相同。PLSA使用了概率模型，并且使用EM算法來估計P（t|c）和P（c|d）矩陣。 PLSA8,9模型是由Hofmann提出的用于文本檢索的概率生成模型，與相比較于LSA，PLSA是基于概率模型的，并直接引入了潛在class變量 zZ=Z1Zk