1 相似度文獻總結相似度有兩種基本類別：（1）客觀相似度，即對象之間的相似度是對象的多維特征之間的某種函數關系，比如對象之間的歐氏距離；（2）主觀相似度，即相似度是人對研究對象的認知關系，換句話說，相似度是主觀認知的結果，它取決于人及其所處的環境，主觀相似度符合人眼視覺需求，帶有一定的模糊性13。1.1 客觀相似度客觀相似度可分為距離測度、相似測度、匹配測度。它們都是衡量兩對象客觀上的相近程度?？陀^相似度滿足下面的公理，假設對象 A與B 的相似度判別為 ，有:(1) 自相似度是一個常量：所有對象的自相似度是一個常數，通常為 1，即(2) 極大性：所有對象的自相似度均大于它與其他對象間的相似度，即。(3) 對稱性：兩個對象間的相似度是對稱的，即。(4) 唯一性：，當且僅當 。1.1.1 距離測度這類測度以兩個矢量矢端的距離為基礎，因此距離測度值是兩矢量各相應分量之差的函數。設表示兩個矢量，計算二者之間距離測度的具體方式有多種，最常用的有： 歐氏距離：Euclidean Distance-based Similarity最初用于計算歐幾里德空間中兩個點的距離，假設 x，y 是 n 維空間的兩個點，它們之間的歐幾里德距離是： （1.1）當x，y是兩個直方圖時，該方法可稱為直方圖匹配法?？梢钥闯觯?n=2 時，歐幾里德距離就是平面上兩個點的距離。當用歐幾里德距離表示相似度，一般采用以下公式進行轉換：距離越小，相似度越大。 （1.2）范圍：0,1，值越大，說明d越小，也就是距離越近，則相似度越大。 說明：由于特征分量的量綱不一致，通常需要先對各分量進行標準化，使其與單位無關。歐氏距離能夠體現個體數值特征的絕對差異，所以更多的用于需要從維度的數值大小中體現差異的分析。優點：簡單，應用廣泛缺點：沒有考慮分量之間的相關性，體現單一特征的多個分量會干擾結果 曼哈頓距離，絕對值距離(街坊距離或 Manhattan 距離)：原理：曼哈頓距離來源于城市區塊距離，是將多個維度上的距離進行求和后的結果。同歐式距離相似，都是用于多維數據空間距離的測度 范圍：0,1，同歐式距離一致，值越小，說明距離值越大，相似度越大。 說明：比歐式距離計算量少，性能相對高。 （1.3） 切氏(Chebyshev)距離（棋盤距離/切比雪夫距離）：切比雪夫距離起源于國際象棋中國王的走法，我們知道國際象棋國王每次只能往周圍的8格中走一步，那么從棋盤中A格（x1，y1）走到B格（x2，y2）最少需要走幾步？ （1.3） 明氏(Minkowski)距離/閔可夫斯基距離： （1.4）可以看出，(1.1)、(1.2)、(1.3)式實際上是(1.4)式當的特殊情況。在實際中較多地使用歐氏距離。顯然，在觀測量的量綱取定的條件下，兩個矢量越相似，距離就越小，反之亦然。值得注意的是，在使用上述距離測度描述具體對象時，量綱選取不同會改變某特征的判斷依據，即改變該特征對判斷貢獻的大小，嚴重的可造成錯誤分類。這是因為改變特征矢量某分量的量綱，進行比較的兩個矢量的相應的兩個分量的數值也將改變。若變小，則其相應的特征在距離測度中“影響作用比重”將變小，即根據其判斷分類的作用變小，反之將增大，這樣便不能很好地反映事實。馬氏(Mahalanobis)距離是不受量綱影響的。 馬氏距離(Mahalanobis)：馬氏距離定義如下：設n維矢量和是矢量集中的兩個矢量，它們的馬氏距離 d 定義為 （1.5）式中，。V的含義是這個矢量集的協方差矩陣的統計量。適用場合：1） 度量兩個服從同一分布并且協方差矩陣為C的隨機變量的差異程度2） 度量與某一類的均值向量的差異程度，判別樣本的歸屬，此時為類均值向量。優點：1） 獨立于分量量綱2） 排除了樣本之間的相關性影響缺點：不同的特征不能差別對待，可能夸大弱特征 漢明距離（Hamming Distance）在信息論中，兩個等長字符串之間的漢明距離是兩個字符串對應位置的不同字符的個數。換句話說，它就是將一個字符串變換成另一個字符串所需要替換的字符個數。例如：1011101與1001001之間的漢明距離是2。2143896與2233796之間的漢明距離是3?！皌oned”與“roses” 之間的漢明距離是3。 巴氏距離（Bhattacharyya）巴氏距離常用于計算直方圖間相似度，定義如下： (1.6)其中，x、y為歸一化數據向量。Bhattacharyya系數取值在01之間，越靠近1，表示兩個模型之間相似度越高。如果，x、y向量未歸一化，則巴氏系數的計算定義為： （1.7） Hausdorff距離：Hausdorff距離(Hausdorff distance ,HD)是一種定義于兩個點集上的最大最小距離，是描述兩組點集之間的相似程度的一種量度，x、y之間的Hausdorff距離定義為： （1.8）式中，為x到y的有向Hausdorff距離；為y到x的有向Hausdorff距離；為某種定義在點集x、y上的距離范數。常用的是歐幾里得范數。如果定義(表示空間中的任意點)則Hausdorff距離可定義為,這里稱分別為點集y和點集x在空間中的變化距離。由于Hausdorff距離是度量兩個點集之間最不匹配點的距離，因此它對遠離中心的噪聲、漏檢點都非常敏感，而這一點，在提取圖像特征點集特征時使不可避免的。為了克服這個缺點，需要對Hausdorff距離的定義進行擴展。 改進的部分Hausdorff距離：為獲得準確的匹配結果，Sim提出了改進的部分Hausdorff距離（LTS-HD）,它是用距離序列的線性組合來定義的： （1.9）式中，p為x內點的個數，為一個屬于0,1的百分數。把點集x中的所有點到點集y的距離按由小到大的順序排列，將序號為1k的k個距離求和，再求平均。所以，該匹配方法不僅能消除遠離中心的錯誤匹配點的影響，而且對零均值高斯噪聲的消除能力明顯。因襲，采用LTS-HD用于圖像特征點集的匹配，力求在所有可能的變換空間中尋找圖像特征點集之間的最優變換，以便通過使LTS-HD最小化來獲得最優匹配結果。設g為變換空間T（通常由旋轉矩陣R、平移變換向量t、尺度c等變換組成）中的一個變換，則最優匹配變換g0滿足 (1.10)0 相關度距離常用于計算直方圖間相似度，定義如下： （1.8）1 卡方系數常用于計算直方圖間相似度，定義如下： （1.9）（備注：引自基于混合圖結構的圖像相似度的研究_莊小芳，2013年福建師范大學碩士學位論文第一章，2.2節）2 （未命名）常用于計算直方圖間相似度，定義如下： （1.11）其中,N表示圖像顏色樣點空間,比起前面幾個計算公式,該式在給出圖像相似度的計算中更為直接,操作也更加簡便。（備注：引自基于混合圖結構的圖像相似度的研究_莊小芳，2013年福建師范大學碩士學位論文第一章，2.2節）3 直方圖相交距離直方圖相交距離是常用于顏色特征相似性度量的一種方法，常用于計算直方圖間相似度。如果有兩幅圖像,則它們的相交距離定義式如下： （1.12）1.1.2 相似測度這類測度是以兩矢量的方向是否相近作為考慮的基礎，矢量長度并不重要，同樣設。 角度相似系數(夾角余弦) 原理：多維空間兩點與所設定的點形成夾角的余弦值。 范圍：-1,1，值越大，說明夾角越大，兩點相距就越遠，相似度就越小。 說明：在數學表達中，如果對兩個項的屬性進行了數據中心化，計算出來的余弦相似度和皮爾森相似度是一樣的，所以皮爾森相似度值也是數據中心化后的余弦相似度。定義：矢量之間的相似度可用它們的夾角余弦來度量。兩個矢量x和 y 的夾角余弦定義如下： （1.6）與歐幾里德距離類似，基于余弦相似度的計算方法也是把特征點作為n-維坐標系中的一個點，通過連接這個點與坐標系的原點構成一條直線（向量），兩個特征點之間的相似度值就是兩條直線（向量）間夾角的余弦值。因為連接代表特征點與原點的直線都會相交于原點，夾角越小代表兩個特征越相似，夾角越大代表兩個特征的相似度越小。同時在三角系數中，角的余弦值是在-1, 1之間的，0度角的余弦值是1，180角的余弦值是-1。借助三維坐標系來看下歐氏距離和余弦相似度的區別：從圖上可以看出距離度量衡量的是空間各點間的絕對距離，跟各個點所在的位置坐標（即個體特征維度的數值）直接相關；而余弦相似度衡量的是空間向量的夾角，更加的是體現在方向上的差異，而不是位置。如果保持A點的位置不變，B點朝原方向遠離坐標軸原點，那么這個時候余弦相似度cos是保持不變的，因為夾角不變，而A、B兩點的距離顯然在發生改變，這就是歐氏距離和余弦相似度的不同之處。應用：Cosine 相似度被廣泛應用于計算文檔數據的相似度及數據挖掘類工作：特點：余弦相似度用向量空間中兩個向量夾角的余弦值作為衡量兩個個體間差異的大小。相比距離度量，余弦相似度更加注重兩個向量在方向上的差異，而非距離或長度上。它對于坐標系的旋轉和尺度的縮放是不變的(因矢量的長度已規格化)，但對一般的線性變換和坐標系的平移不具有不變性。 調整余弦相似度 Adjusted Cosine Similarity在余弦相似度的介紹中說到：余弦相似度更多的是從方向上區分差異，而對絕對的數值不敏感。因此沒法衡量每個維數值的差異，會導致這樣一個情況：比如用戶對內容評分，5分制，X和Y兩個用戶對兩個內容的評分分別為(1,2)和(4,5)，使用余弦相似度得出的結果是0.98，兩者極為相似，但從評分上看X似乎不喜歡這兩個內容，而Y比較喜歡，余弦相似度對數值的不敏感導致了結果的誤差，需要修正這種不合理性，就出現了調整余弦相似度，即所有維度上的數值都減去一個均值，比如X和Y的評分均值都是3，那么調整后為(-2,-1)和(1,2)，再用余弦相似度計算，得到-0.8，相似度為負值并且差異不小，但顯然更加符合現實。應用：調整余弦相似度和弦相似度，皮爾遜相關系數在推薦系統中應用較多。在基于項目的推薦中GroupLens有篇論文結果表明調整余弦相似度性能要由于余弦相似度和皮爾遜相關系數。 相關系數 它實際上是數據中心化后的矢量夾角余弦。 （1.7）此處將 , 視作兩個數據集的樣本，和 分別是這兩個數據集的平均矢量。相關系數對于坐標系的平移、旋轉和尺度縮放是不變的。（備注：該節引自 項德良【SAR 圖像相似度評估技術研究】，2012年國防科大碩士論文1.2節。） 指數相似系數 指數相似系數定義如下： （1.8）式中， 為相應分量的方差，n為矢量維數。它不受量綱變化的影響。從函數的構造上看屬于距離方式(類似于馬氏距離)，但從測度值和相似關系看屬于相似測度。（備注：該節引自 項德良【SAR 圖像相似度評估技術研究】，2012年國防科大碩士論文1.2節。） 對數似然相似度Ted Dunning在1993年提出一種對數似然比的概念，主要應用于自然文本語言庫中兩個詞的搭配關系問題。它是基于這樣一種思想，即統計假設可以確定一個空間的很多子空間，而這個空間是被統計模型的位置參數所描述。似然比檢驗假設模型是已知的，但是模型的參數是未知的。二項分布的對數似然比對于二項分布的情況，似然函數為 （1.1）式中：的統計模型，試驗結果的參數。給定模型的參數。假設二項分布有相同的基本參數集合，那么對數似然比就是 （1.2）式中：當取得某值時，統計模型的最大值。當時，分母取得最大值。當時，分子取得最大值。所以對數似然比簡化為 （1.3）式中：二項分布，實驗重復的次數，某事發生的概率，該事件發生的次數，。兩邊取對數可以將對數似然比的公式變形為： （1.4）由于二項分布的對數似然比能夠合理的描述兩個事物的相似模型，所以常用對數似然比來計算兩個事物（用戶或物品）的相似度。對數似然相似度基于兩個用戶共同評估過的物品數目，但在給定物品總數和每個用戶評價的情況下，其最終結果衡量的是兩個用戶有這么多共同物品的“不可能性”，它是一種不考慮具體偏好值的方法。比如在用戶物品偏好的二維矩陣中，我們可以將一個用戶對所有物品的偏好作為一個向量來計算用戶之間的相似度，或者將所有用戶對某個物品的偏好作為一個向量來計算物品之間的相似度。備注：引自張明敏，張功萱對數似然相似度算法的MapReduce并行化實現計算機工程與設計2015,36卷，第5期。 Levenshtein 距離,又稱編輯距離兩個字符串（鏈）的相似度可以用Levenshtein距離（Levenshtein distance）表示，該距離定義為將一個串變為另一個串所需的最小操作步數，可能的操作有刪除、插入、替換Schlesinger and Hlavac ,2002。還可以給字符串元素變換賦一個變換代價，從而使計算得到的相似度（距離）更靈活，更敏感。同樣的原理也可以用在圖相似度的計算上。下定義可能的結點和弧的變換（刪除、插入、替換、重新標注）集合，再給每種變換賦一個變換代價。任一變換序列的代價用單個步驟代價的組合表示（類似代價步驟的和）。將一個圖變為另一個圖的所有變換集合中具有最小代價值的那個集合就定義了這兩幅圖間的距離Niemann,1990。用途：常用于字符串距離，類似可用于計算圖的距離備注：引用于圖像處理、分析與機器視覺（第三版）Milan Sonka ,Vaclav Hlavac, Roger Boyle著，艾海舟，蘇延超譯P298，9.5.2 圖的相似度 統計相關系數-皮爾遜相關系數（Pearson Correlation Coefficient）皮爾遜相關也稱積差相關（積矩相關），即相關分析中的相關系數，分別對基于自身總體標準化后計算余弦向量的標準夾角。是英國統計學家皮爾遜于20世紀提出的一種計算直線相關的方法。皮爾遜相關系數一般用來反映兩個變量線性相關程度，它的取值在 -1，+1 之間。相關系數的絕對值越大，相關性越強。假設有兩個變量，那么；兩個變量間的皮爾遜相關系數可以通過以下公式計算：公式一：公式二：公式三：公式四：以上列出四個公式等價，其中E是數學期望，cov表示方差，N表示變量取值的個數。適用范圍：當兩個變量對的標準差都不為0時，相關系數才有定義，皮爾遜系數適用于：（1） 兩個變量之間是線性關系，都是連續數據（2） 兩個變量的總體是正態分布，或接近正態的單峰分布（3） 兩個變量的觀測值是成對的，每對觀測值之間互相獨立特點：（1）當兩個變量的線性關系增強時，相關系數趨于1或-1；（2）當一個變量增大，另一個變量也增大時，表明它們之間是正相關的，相關系數大于0；（3）如果一個變量增大，另一個變量卻減小，表明它們之間是負相關的，相關系數小于0；（4）如果相關系數等于0，表明它們之間不存在線性相關關系。 統計相關系數-斯皮爾曼相關（Spearman秩相關）系數-Spearman Correlation（1） 簡介在統計學中，斯皮爾曼等級相關系數以Charles Spearman命名，并經常用希臘字母表示其值。斯皮爾曼等級相關系數用來估計兩個變量之間的相關性，其中變量間的相關性可以用單調函數來描述。如果兩個變量取值的兩個集合中均不存在相同的兩個元素，那么，當其中一個變量可以表示為另一個變量的很好的單調函數時（即兩個變量的變化趨勢相同），兩個變量之間的可以達到+1或-1。假設兩個隨機變量分別為（也可以看做是兩個集合），它們的元素個數均為N，兩個隨機變量取的第個值分別用表示。對進行排序（同為升序或降序），得到兩個元素排行集合，其中元素分別為在中的排行以及在中的排行。將集合中的元素對應相減得到一個排行差分集合d,其中，。隨機變量之間的斯皮爾曼等級相關系數可由或d計算得到，其計算方式如下：公式一：由排行差分集合d計算而得（）：公式二：由排行集合計算而得（斯皮爾曼等級相關系數同時也被認為是經過排行的兩個隨機變量的皮爾遜相關系數，以下實際是計算的皮爾遜相關系數）：以下是一個計算集合中元素排行的例子（僅適用于斯皮爾曼等級相關系數的計算）變量元素的位置（依降序排列）變量的排行（）1540.2451.33（2+3）/2=2.51.32（2+3）/2=2.51011這里需要注意：當變量的兩個值相同時，它們的排行是通過對它們的位置進行平均得到的。（2） 適用范圍斯皮爾曼等級相關系數對數據條件的要求沒有皮爾遜相關系數嚴格，只要兩個變量的觀測值是成對的等級評定資料，或者是由連續變量觀測資料轉化得到的等級資料，不論兩個變量的整體分布形態、樣本容量的大小如何，都可以用斯皮爾曼等級相關系數來進行研究。原理：Spearman秩相關系數通常被認為是排列后的變量之間的Pearson線性相關系數。 （3）取值范圍：-1.0,1.0，當一致時為1.0，不一致時為-1.0。 （4）說明：計算非常慢，有大量排序。針對推薦系統中的數據集來講，用Spearman秩相關系數作為相似度量是不合適的。一般用于學術研究或者是小規模的計算。（5）Spearman相關系數的特點：Spearman相關是根據等級資料研究兩個變量間相關關系的方法。它是依據兩列成對等級的各對等級數之差來進行計算的，所以又稱為“等級差數法”1， Spearman相關系數對原始變量的分布不做要求，屬于非參數統計方法。因此它的適用范圍比Pearson相關系數要廣的多。即使原始數據是等級資料也可以計算Spearman相關系數。對于服從Pearson相關系數的數據也可以計算Spearman相關系數，2， 統計效能比Pearson相關系數要低一些（不容易檢測出兩者事實上存在的相關關系）。3， spearman只要兩個變量的觀測值是成對的等級評定資料，或者是由連續變量觀測資料轉化得到的等級資料，不論兩個變量的總體分布形態、樣本容量的大小如何，都可以用斯皮爾曼等級相關來進行研究。注：spearman與pearson：1. 連續數據，正態分布，線性關系，用pearson相關系數是最恰當，當然用spearman相關系數也可以，就是效率沒有pearson相關系數高。2. 上述任一條件不滿足，就用spearman相關系數，不能用pearson相關系數。3. 兩個定序測量數據之間也用spearman相關系數，不能用pearson相關系數。 4 .只要在X和Y具有單調的函數關系的關系，那么X和Y就是完全Spearman相關的，這與Pearson相關性不同，后者只有在變量之間具有線性關系時才是完全相關的。 統計相關系數-Kendall Rank(肯德爾等級)相關系數（1） 簡介在統計學中，肯德爾相關系數是以Maurice Kendall命名的，并經常用希臘字母（tau）表示其值?？系聽栂嚓P系數是一個用來測量兩個隨機變量相關性的統計值。一個肯德爾檢驗是一個無參假設檢驗，它使用計算而得的相關系數去檢驗兩個隨機變量的統計依賴性?？系聽栂嚓P系數的取值范圍在-1到1之間，當為1時，表示兩個隨機變量擁有一致的等級相關性，當為-1時，表示兩個隨機變量擁有完全相反的等級相關性，當為0時，表示兩個隨機變量是相互獨立的。假設兩個隨機變量分別為（也可以看做是兩個集合），它們的元素個數均為N，兩個隨機變量取的第個值分別用表示。中的對應元素組成一個元素對集合,其包含的元素為。當集合中任意兩個元素與的排行相同時（也就是說當出現情況1或2時；情況1: ,情況2：），這兩個元素就被認為是一致的。當出現情況3或4時（情況3: ,情況4：），這兩個元素就被認為是不一致的。當出現情況5或6時（情況5: ,情況6：），這兩個元素既不是一致也不是不一致的。這里有三個公式計算肯德爾相關系數的值：公式一：其中C表示XY中擁有一致性的元素對數（兩個元素為一對），D表示XY中擁有不一致性的元素對數。注意：這一公式僅適用于集合X與Y中不存在相同元素的情況（集合中各個元素唯一）公式二：注意：這一公式適用于集合X或Y中存在相同元素的情況（當然，如果X或Y中均不存在相同的元素時，公式二便等同于公式一）。其中C、D與公式一相同；N1、N2分別是針對集合X、Y計算的，現在以計算N1為例，給出N1的由來（N2的計算可以類推）：將X中的相同元素分別組合成小集合，s表示集合X中擁有的小集合數（例如X包含元素：1 2 3 4 3 3 2，那么這里得到的s則為2，因為只有2、3有相同的元素），表示第i個小集合所包含的元素數。N2在集合Y的基礎上計算而得。公式三：注意：這一公式中沒有再考慮集合、或者中存在相同元素給最后的統計值帶來的影響。公式三的這一計算形式僅適用于用表格表示的隨機變量X、Y之間相關系數的計算（下面會介紹），參數M稍后會做介紹。以上都是圍繞用集合表示的隨機變量而計算肯德爾相關系數的，下面所講的則是圍繞用表格表示的隨機變量而計算肯德爾相關系數的。通常人們會將兩個隨機變量的取值制作成一個表格，例如有10個樣本，對每個樣本進行兩項指標些事（指標的取值均為1到3）。根據樣本的指標取值，得到以下二維表格（表1）：表1123Sum112032121430123sum25310由表1 可以得到的可以以集合的形式表示為：得到的集合形式后就可以使用以上的公式一或公式二計算的肯德爾相關系數了（注意公式一、公式二的適用條件）當然如果給定的集合形式，那么也是很容易得到它們的表格形式的。這里需要注意的是：公式二也可以用來計算表格形式表示的二維變量的肯德爾相關系是，不過它一般用來計算由正方形表格表示的二維變量的肯德爾相關系數，公式三則只是用來計算由長方形表格表示的二維變量的Kendall相關系數。這里給出公式三種字母的含義，表示長方形表格中行數與列數中較小的一個。表1的行數及列數均為三。（2） 適用范圍肯德爾相關系數與斯皮爾曼相關系數對數據的條件要求相同。0 Tanimoto 系數（Tanimoto Coefficient）Tanimoto 系數也稱為 廣義Jaccard 系數，是 Cosine 相似度的擴展，通常應用于、為布爾向量，即各分量只取0或1的時候，此時表示的是、的公共特征占、具有的所有特征的比例。其實質就是集合交集與并集的比。也多用于計算文檔數據的相似度，或兩個集合之間的相似程度。范圍：0,1，越接近1說明越相似。 1 Jaccard 系數Jaccard 系數主要用于計算符號度量或布爾值度量的個體間的相似度，因為個體的特征屬性都是由符號度量或者布爾值標識，因此無法衡量差異具體值的大小，只能獲得“是否相同”這個結果，所以Jaccard 系數只關心個體間共同具有的特征是否一致這個問題。如果比較的Jaccard 相似系數，只比較中相同的個數，公式如下：也就是關聯的交集除以關聯的并集。范圍：其值介于0, 1之間，如果兩個個體間的特征完全相同，交集等于并集，值為1；如果沒有任何關聯，交集為空，值為0。1.1.3 匹配測度 （備注：該節引自 項德良【SAR 圖像相似度評估技術研究】，2012年國防科大碩士論文1.2節。）這種測度常用于醫學和生物的分類中。在有些情況下，特征只有兩個狀態，對象或具有此特征或不具有此特征。此時，若對象具有此特征，則相應分量定義為 1，而相應分量為 0 表示對象無此特征，這就是所謂的二值特征。對于給定的二值特征矢量x和 y 中的某兩個相應分量和，若和，則稱和是（1-1）匹配，若和，則稱和是（1-0）匹配；若和，則稱和是（0-1）匹配；若，則稱和是（0-0）匹配，令 （1.9）則a等于兩矢量 x 和 y 的(1-1)匹配的特征的數目，b 等于 x 和 y 的(0-1)匹配的特征的數目，c等于x和 y 的(1-0)匹配的特征的數目，e等于x和 y 的(0-0)匹配的特征的數目。對于二值n維特征矢量可定義如下相似性測度： Tanimoto 測度 （1.10）可以看出， s ( x , y )等于x 和 y 都具有的特征的數目與 x和 y 分別具有的特征種類總數之比。這里只考慮(1-1)匹配而不考慮(0-0)匹配。 Rao 測度 （1.11）上式等于(1-1)匹配特征數目和所選用的特征數目之比。 簡單匹配系數 （1.12）上式表明，這時匹配系數分子為(1-1)匹配特征數目與(0-0)匹配特征數目之和，分母為所選用的特征數目。 Dice 系數 （1.13）分子、分母無(0-0)匹配，對(1-1)匹配加權。 Kulzinsky 系數 （1.14）上式分子為(1-1)匹配特征數目，分母為(1-0)和(0-0)匹配特征數目之和。1.2 主觀相似度1.2.1 結構相似度（SSIM,structural similarity (SSIM) index measurement）（備注：該節引自 項德良【SAR 圖像相似度評估技術研究】，2012年國防科大碩士論文1.2節。）結構相似性理論認為，自然圖像信號是高度結構化的，即像素間有很強的相關性，特別是空域中最接近的像素，這種相關性蘊含著視覺 場景中物體結構的重要信息；HVS的主要功能是從視野中提取結構信息，可以用對結構信息的度量作為圖像感知質量的近似。結構相似性理論是一種不同于以往模 擬HVS低階的組成結構的全新思想，與基于HVS特性的方法相比，最大的區別是自頂向下與自底向上的區別。這一新思想的關鍵是從對感知誤差度量到對感知結 構失真度量的轉變。它沒有試圖通過累加與心理物理學簡單認知模式有關的誤差來估計圖像質量，而是直接估計兩個復雜結構信號的結構改變，從而在某種程度上繞 開了自然圖像內容復雜性及多通道去相關的問題.作為結構相似性理論的實現，結構相似度指數從圖像組成的角度將結構信息定義為獨立于亮度、對比度的，反映場景中物體結構的屬性，并將失真建模為亮度、對比度和結構三個不同因素的組合。用均值作為亮度的估計，標準差作為對比度的估計，協方差作為結構相似程度的度量。(from Internet)Zhou Wang 在 2004 年提出一種結構相似度準則 SSIM(Structural Similarity Index Measurement)來衡量光學圖像相似度。該準則分析了人眼視覺特性和圖像結構之間的關系，從圖像空間、人眼視覺和圖像結構等方面對SSIM進行了研究，在光學圖像的配準、目標識和圖像質量評估方面得到了有效驗證16。SSIM準則側重人眼的主觀感受，它是從圖像的客觀信息出發，通過建立模型從而得到的符合人眼視覺的準則。結構相似度定義如下： （1.2.1）為亮度相似度函數，其中，為當、為零時定義的常量。對比度相似度函數定義如下： （1.16）其中，。也為一個常量。結構相似度函數定義如下： （1.17）其中。綜上，結構相似度指數(SSIM)定義如下： （1.18）其中均大于 0，為控制三個分量相似度權重的參數。 SSIM ( x , y )越接近于 1，則表明x與 y 越相似，否則越不相似。近年來基于語義測度的主觀相似度準則得到越來越多學者的關注。該方法一般在圖像分割的基礎上，通過構建圖像區域子塊與語義元數據之間的統計映射關系，實現圖像內容的統計語義描述，建立圖像之間、圖像與語義類別、語義類別之間的分層語義相似測度23-26。該方法充分考慮人眼視覺的語義層面，在圖像檢索等應用中得到有效驗證。1.3 基于像素差值編碼的相似度1.3.1 像素差值編碼規則 給定一幅 SAR 圖像，J 和K 為圖像高度和寬度。 G ( x , y )為圖像在( x , y )處灰度值。 B 是對應的編碼圖像，其大小也為， B ( x , y )為 ( x , y )處編碼值，定義如下 （2.1）式(2.1)中SAR圖像像素值比較是按從左到右、從上到下的順序。圖 2.1所示為SAR圖像編碼圖示。1.3.2 相似性測度及其概率密度函數 和 為待比較的兩幅SAR圖像， 和 分別為對應的編碼圖像，基于像素差值編碼的相似性測度(Intensity increment code-IIC)定義如下所示： （2.2）式(2.2)中，分別為編碼圖像和 在 ( x , y )處編碼值。衡量了兩幅編碼圖像的相似性，也即反映了兩幅SAR圖像灰度變化是否一致，評價：該方法對圖像噪聲、部分遮擋和一定程度模糊有一定魯棒性。然而該方法著重統計全局圖像灰度信息，較少考慮圖像局部細節，因此對細節豐富的 SAR 圖像并不太適用。1.4 基于 KL 距離準則的相似度比較灰度直方圖相似性的方法很多，本文采用一種對稱KL準則SKLD(Symmetry Kullback-Leibler Divergence)64。對兩個局部梯度比率直方圖H 和Q，定義SKLD如下： （3.1）其中，和 分別為 H 和 Q 的MLGRPH特征矢量，N 為特征矢量的維數。由于相似度范圍為0,1，即完全相似時，相似度為1，此時SKLD 為0，當完全不相似時，相似度為0，SKLD 為，因此這里需要將SKLD 變換為范圍在0,1之間的相似度。我們采用最簡單的高斯隸屬度函數，如下所示： (3.2)其中，為控制高斯函數寬度的參數，可通過來控制距離與相似度變化關系。1.5 基于hash方法的相似度計算基于hash的相似度計算方法，是一種基于概率的高維度數據的維度削減的方法，主要用于大規模數據的壓縮與實時或者快速的計算場景下，基于hash方法的相似度計算經常用于高維度大數據量的情況下，將利用原始信息不可存儲與計算的問題轉化為映射空間的可存儲計算問題，在海量文本重復性判斷方面，近似文本查詢方面有比較多的應用，google的網頁去重1，google news的協同過濾2,3等都是采用hash方法進行近似相似度的計算，比較常見的應用場景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算法族里的一個常用方法，基本的思想是，對于每一個對象的itemlist，將輸入的item進行hash，這樣相似的item具有很高的相似度被映射到相同的buckets里面，這樣盡量保證了hash之后兩個對象之間的相似程度和原來是高相似的，而buckets的數量是遠遠小于輸入的item的，因此又達到降低復雜度的目的。 minhash方法用Jaccard進行相似度的計算方法，則對于兩個集合 和 ， 和 的相似性的計算方法為： （1.6.1）當兩個集合越相似，則該值越接近1，否則越接近0。用minhash方法，將一個集合映射到0-R-1之間的值，以相同的概率隨機的抽取一個0-R-1的一個排列，依次排列查找第一次出現1的行。設隨機排列為43201(edcab)，對于C1列，第一次出現1的行是R4，所以h(C1) = 3，同理有h(C2)=2, h(C3)=4, h(C4)=3。通過多次抽取隨機排列得到n個minhash函數h1,h2,hn，依此對每一列都計算n個minhash值。對于兩個集合，看看n個值里面對應相等的比例，即可估計出兩集合的Jaccard相似度?？梢园衙總€集合的n個minhash值列為一列，得到一個n行C列的簽名矩陣。因為n可遠小于R，這樣在壓縮了數據規模的同時，并且仍能近似計算出相似度。1.5.2 simhash方法介紹simhash方法是在大文本重復識別常用的一個方法，該方法主要是通過將對象的原始特征集合映射為一個固定長度的簽名，將對象之間的相似度的度量轉化為簽名的漢明距離，通過這樣的方式，極大限度地進行了降低了計算和存儲的消耗。1.5.3 簽名計算過程該方法通過對輸入特征集合的計算步驟可以描述如下：1， 將一個f維的向量V初始化為0；f位的二進制數S初始化為0；2， 對每一個特征：用傳統的hash算法對該特征產生一個f位的簽名b。對i=1到f：如果b的第i位為1，則V的第i個元素加上該特征的權重；否則，V的第i個元素減去該特征的權重。 1， 如果V的第i個元素大于0，則S的第i位為1，否則為0；2， 輸出S作為簽名。通過上述步驟將輸入的表示對象的特征集合轉化為該對象的一個簽名，在完成簽名之后，度量兩個對象的相似度的差異即變成了對量二者的指紋的K位的差異情況。1.5.4 漢明距離查找優化對于如何快速查找出某一個簽名是否與其存在最大差異不超過K個bit的指紋，Detecting Near-Duplicates for Web Crawling這篇論文中進行了介紹。該查找方法的基本思想是利用空間換時間的方法，該方法的依據是需要查找的兩個指紋的差異很小，這樣可以通過將原始指紋進行分塊索引，如果兩個指紋的差異很小，則合理的分塊后，根據鴿籠原理，其中存在一定數量的塊是一致的，通過利用相同的塊進行相似的指紋的召回，只需要比對召回的塊中有差異的塊的bit差異，這樣減少了需要比對的數量，節省了比對的時間開銷。1.5.5 小結hash方法的相似度計算的主要應用場景，一般是針對大規模數據進行壓縮，在保證效果損失可接受的情況下，節省存儲空間，加快運算速度，針對該方法的應用，在目前的大規模的互聯網處理中，很多相似度的計算都是基于這種近似性的計算，并取得了比較好的效果。設隨機排列為43201(edcab)，對于C1列，第一次出現1的行是R4，所以h(C1) = 3，同理有h(C2)=2, h(C3)=4, h(C4)=3。通過多次抽取隨機排列得到n個minhash函數h1,h2,hn，依此對每一列都計算n個minhash值。對于兩個集合，看看n個值里面對應相等的比例，即可估計出兩集合的Jaccard相似度?？梢园衙總€集合的n個minhash值列為一列，得到一個n行C列的簽名矩陣。因為n可遠小于R，這樣在壓縮了數據規模的同時，并且仍能近似計算出相似度。1.6 基于主題的相似度計算Bag-of-Words 模型是NLP和IR領域中的一個基本假設。在這個模型中，一個文檔(document)被表示為一組單詞(word/term)的無序組合，而忽略了語法或者詞序的部分。BOW在傳統NLP領域取得了巨大的成功，在計算機視覺領域(Computer Vision)也開始嶄露頭角，但在實際應用過程中，它卻有一些不可避免的缺陷，比如：l 稀疏性(Sparseness): 對于大詞典，尤其是包括了生僻字的詞典，文檔稀疏性不可避免；l 多義詞(Polysem): 一詞多義在文檔中是常見的現象，BOW模型只統計單詞出現的次數，而忽略了他們之間的區別；l 同義詞(Synonym): 同樣的，在不同的文檔中，或者在相同的文檔中，可以有多個單詞表示同一個意思；從同義詞和多義詞問題我們可以看到，單詞也許不是文檔的最基本組成元素，在單詞與文檔之間還有一層隱含的關系，我們稱之為主題(Topic)。我們在寫文章時，首先想到的是文章的主題，然后才根據主題選擇合適的單詞來表達自己的觀點。主題的概念的引入，主要是在原有的基本特征粒度的基礎上，引入了更為豐富的隱含層特征，提高了相似性計算的效果，常用的主題分析方法包括Latent Semantic Analysis (LSA) 、 Probabilitistic Latent Semantic Analysis (PLSA)、Latent Dirichlet Allocation ( LDA)。這些方法在分類，聚類、檢索、推薦等領域都有著很多的應用，并取得了比較好的效果。下面就LSA及PLSA方法進行簡要介紹。1.6.1 LSA（Latent Semantic Analysis）簡介LSA的基本思想就是，將document從稀疏的高維Vocabulary空間映射到一個低維的向量空間，我們稱之為隱含語義空間(Latent Semantic Space).LSA最初是用在語義檢索上，為了解決一詞多義和一義多詞的問題： 1.一詞多義： 美女和PPMM表示相同的含義，但是單純依靠檢索詞“美女”來檢索文檔，很可能喪失掉那些包含“PPMM”的文檔。 2.一義多詞：如果輸入檢索詞是多個檢索詞組成的一個小document，例如“清澈 孩子”，那我們就知道這段文字主要想表達concept是和道德相關的，不應該將“春天到了，小河多么的清澈”這樣的文本包含在內。 為了能夠解決這個問題，需要將詞語（term）中的concept提取出來，建立一個詞語和概念的關聯關系（t-c relationship），這樣一個文檔就能表示成為概念的向量。這樣輸入一段檢索詞之后，就可以先將檢索詞轉換為概念，再通過概念去匹配文檔。LSA6,7模型認為特征之間存在某種潛在的關聯結構，通過特征-對象矩陣進行統計計算，將高維空間映射到低維的潛在語義結構上，構建出LSA空間模型，從而提取出潛在的語義結構，并用該結構表示特征和對象，消除了詞匯之間的相關性影響，并降低了數據維度。增強了特征的魯棒性LSA利用SVD分解的數學手段來進行計算，數學過程可以表述如下：對于的矩陣A，其中m為特征數，n為樣本數。令 ，經過奇異值分解，矩陣A可分解成3個矩陣的乘積：其中，U、V是 和 的正交矩陣，分別稱為矩陣A的奇異值對應的左、右奇異向量，是包含所有奇異值的 的對角矩陣，稱為A的奇異標準形，其對角元素為矩陣A的奇異值。奇異值按照遞減的排列構成對角矩陣 ，取 中前k個最大奇異值構成的，取U和V最前面的k列構成的Uk和的Vk，構建A的k-秩矩陣。（LSA降維的方式就是只取最大的K個奇異值，而其他置為0，于是得到了共生矩陣的近似。） 其中，Uk和Vk 中的行向量分別作為特征向量和對象向量，k是降維后的維數。下圖形象的展示了LSA的過程：LSA的優點l 低維空間表示可以刻畫同義詞，同義詞會對應著相同或相似的主題；l 降維可去除部分噪聲，是特征更魯棒；l 充分利用冗余數據；l 無監督/完全自動化；l 與語言無關；LSA的不足l 沒有刻畫term出現次數的概率模型；l 無法解決多義詞的問題；l SVD的優化目標基于L-2 norm 或者是 Frobenius Norm的，這相當于隱含了對數據的高斯噪聲假設。而term出現的次數是非負的，這明顯不符合Gaussian假設，而更接近Multi-nomial分布；l 對于count vectors 而言，歐式距離表達是不合適的（重建時會產生負數）；l 特征向量的方向沒有對應的物理解釋；l SVD的計算復雜度很高，而且當有新的文檔來到時，若要更新模型需重新訓練；l 維數的選擇是ad-hoc的；1.6.2 plas介紹 PLSA和LSA基礎思想是相同的，都是希望能從term中抽象出概念，但是具體實現的方法不相同。PLSA使用了概率模型，并且使用EM算法來估計P（t|c）和P（c|d）矩陣。 PLSA8,9模型是由Hofmann提出的用于文本檢索的概率生成模型，與相比較于LSA，PLSA是基于概率模型的，并直接引入了潛在class變量 zZ=Z1Zk