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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

25、變量的分布不做要求，屬于非參數(shù)統(tǒng)計(jì)方法。因此它的適用范圍比Pearson相關(guān)系數(shù)要廣的多。即使原始數(shù)據(jù)是等級(jí)資料也可以計(jì)算Spearman相關(guān)系數(shù)。對(duì)于服從Pearson相關(guān)系數(shù)的數(shù)據(jù)也可以計(jì)算Spearman相關(guān)系數(shù)，2， 統(tǒng)計(jì)效能比Pearson相關(guān)系數(shù)要低一些（不容易檢測(cè)出兩者事實(shí)上存在的相關(guān)關(guān)系）。3， spearman只要兩個(gè)變量的觀測(cè)值是成對(duì)的等級(jí)評(píng)定資料，或者是由連續(xù)變量觀測(cè)資料轉(zhuǎn)化得到的等級(jí)資料，不論兩個(gè)變量的總體分布形態(tài)、樣本容量的大小如何，都可以用斯皮爾曼等級(jí)相關(guān)來進(jì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. 兩個(gè)定序測(cè)量數(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)系時(shí)才是完全相關(guān)的。 統(tǒng)計(jì)相關(guān)系數(shù)-Kendall Rank(肯德爾等級(jí))相關(guān)系數(shù)（1） 簡(jiǎn)介在統(tǒng)計(jì)學(xué)中，肯德爾相關(guān)系數(shù)是以Maurice Kendall命名的，并經(jīng)常用希臘字母（ta

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

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

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

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

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

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

33、。在有些情況下，特征只有兩個(gè)狀態(tài)，對(duì)象或具有此特征或不具有此特征。此時(shí)，若對(duì)象具有此特征，則相應(yīng)分量定義為 1，而相應(yīng)分量為 0 表示對(duì)象無此特征，這就是所謂的二值特征。對(duì)于給定的二值特征矢量x和 y 中的某兩個(gè)相應(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ù)目。對(duì)于二值n維特征矢量可定義如下相似性測(cè)度：

34、 Tanimoto 測(cè)度 （1.10）可以看出， s ( x , y )等于x 和 y 都具有的特征的數(shù)目與 x和 y 分別具有的特征種類總數(shù)之比。這里只考慮(1-1)匹配而不考慮(0-0)匹配。 Rao 測(cè)度 （1.11）上式等于(1-1)匹配特征數(shù)目和所選用的特征數(shù)目之比。 簡(jiǎn)單匹配系數(shù) （1.12）上式表明，這時(shí)匹配系數(shù)分子為(1-1)匹配特征數(shù)目與(0-0)匹配特征數(shù)目之和，分母為所選用的特征數(shù)目。 Dice 系數(shù) （1.13）分子、分母無(0-0)匹配，對(duì)(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é)引自 項(xiàng)德良【SAR 圖像相似度評(píng)估技術(shù)研究】，2012年國(guó)防科大碩士論文1.2節(jié)。）結(jié)構(gòu)相似性理論認(rèn)為，自然圖像信號(hào)是高度結(jié)構(gòu)化的，即像素間有很強(qiáng)的相關(guān)性，特別是空域中最接近的像素，這種相關(guān)性蘊(yùn)含著視覺 場(chǎng)景中物體結(jié)構(gòu)的重要信息；HVS的主要功能是從視野中提取結(jié)構(gòu)信息，可以用對(duì)結(jié)構(gòu)信息的度量作為圖像感知質(zhì)量的近似。結(jié)構(gòu)相似性理論是一種不同于以往模 擬HVS低

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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