搜索研發(fā)部官方博客 ? Blog Archive ? 相似度計算常用方法綜述

相似度計算常用方法綜述 ???? (2012-7-05 09:07:59)

標(biāo)簽： 主題相似度 , 向量空間模型 , 相似度計算 ????分類： 數(shù)據(jù)挖掘

?引言

?????? 相似度計算用于衡量對象之間的相似程度，在數(shù)據(jù)挖掘、自然語言處理中是一個基礎(chǔ)性計算。其中的關(guān)鍵技術(shù)主要是兩個部分，對象的特征表示，特征集合之間的相似關(guān)系。在信息檢索、網(wǎng)頁判重、推薦系統(tǒng)等，都涉及到對象之間或者對象和對象集合的相似性的計算。而針對不同的應(yīng)用場景，受限于數(shù)據(jù)規(guī)模、時空開銷等的限制，相似度計算方法的選擇又會有所區(qū)別和不同。下面章節(jié)會針對不同特點的應(yīng)用，進行一些常用的相似度計算方法進行介紹。

?

2向量空間模型

向量空間模型（Vector space model）是應(yīng)用最廣泛的一個基礎(chǔ)相似度計算模型，在該模型中，每個對象映射為一個特征向量:

?

作為一個應(yīng)用廣泛的模型，向量空間模型在現(xiàn)有的很多應(yīng)用中仍然起著至關(guān)重要的作用，也是很多擴展方法的基礎(chǔ)。

3 基于hash方法的相似計算

?????? 基于hash的相似度計算方法，是一種基于概率的高維度數(shù)據(jù)的維度削減的方法，主要用于大規(guī)模數(shù)據(jù)的壓縮與實時或者快速的計算場景下，基于hash方法的相似度計算經(jīng)常用于高維度大數(shù)據(jù)量的情況下，將利用原始信息不可存儲與計算的問題轉(zhuǎn)化為映射空間的可存儲計算問題，在海量文本重復(fù)性判斷方面，近似文本查詢方面有比較多的應(yīng)用，google的網(wǎng)頁去重 ^[1] ，google news的協(xié)同過濾 ^[2,3] 等都是采用hash方法進行近似相似度的計算，比較常見的應(yīng)用場景Near-duplicate detection、Image similarity identification、nearest neighbor search，常用的一些方法包括I-match，Shingling、Locality-Sensitive Hashing族等方法，下面針對幾種常見的hash方法進行介紹。

3.1 minhash方法介紹

?????? Minhash方法是Locality-sensitive hashing ^[4,5] 算法族里的一個常用方法，基本的思想是，對于每一個對象的itemlist，將輸入的item進行hash，這樣相似的item具有很高的相似度被映射到相同的buckets里面，這樣盡量保證了hash之后兩個對象之間的相似程度和原來是高相似的，而buckets的數(shù)量是遠(yuǎn)遠(yuǎn)小于輸入的item的，因此又達(dá)到降低復(fù)雜度的目的。

?????? minhash方法用Jaccard進行相似度的計算方法，則對于兩個集合 和 ?， 和 的相似性的計算方法為：

當(dāng)兩個集合越相似，則該值越接近1，否則越接近0。用minhash方法，將一個集合映射到[0-R-1]之間的值，以相同的概率隨機的抽取一個[0-R-1[的一個排列，依次排列查找第一次出現(xiàn)1的行。

設(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個minhash值列為一列，得到一個n行C列的簽名矩陣。因為n可遠(yuǎn)小于R，這樣在壓縮了數(shù)據(jù)規(guī)模的同時，并且仍能近似計算出相似度。

3.2 simhash方法介紹

simhash方法是在大文本重復(fù)識別常用的一個方法，該方法主要是通過將對象的原始特征集合映射為一個固定長度的簽名，將對象之間的相似度的度量轉(zhuǎn)化為簽名的漢明距離，通過這樣的方式，極大限度地進行了降低了計算和存儲的消耗。

3.2.1 簽名計算過程

?????? 該方法通過對輸入特征集合的計算步驟可以描述如下：

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)化為該對象的一個簽名，在完成簽名之后，度量兩個對象的相似度的差異即變成了對量二者的指紋的K位的差異情況。

3.2.2 漢明距離查找優(yōu)化

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

3.3 小結(jié)

?????? hash方法的相似度計算的主要應(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 個 minhash 值列為一列，得到一個 n 行 C 列的簽名矩陣。因為 n 可遠(yuǎn)小于 R ，這樣在壓縮了數(shù)據(jù)規(guī)模的同時，并且仍能近似計算出相似度。

4 基于主題的相似度計算

?????? 傳統(tǒng)的BOW（bag-of_words）模型，一般都會建立在特征獨立假設(shè)的基礎(chǔ)上，按照特征向量的匹配情況來度量對象之間的相似度，但是在實際的應(yīng)用中，很多時候特征之間存在著很多的關(guān)聯(lián)關(guān)系，二者在傳統(tǒng)的BOW模型中無法解決，在這個基礎(chǔ)上，引入了主題的概念，通過主題的思想，建立起基本特征與對象的中間層的關(guān)聯(lián)關(guān)系，主題的概念的引入，主要是在原有的基本特征粒度的基礎(chǔ)上，引入了更為豐富的隱含層特征，提高了相似性計算的效果，常用的主題分析方法包括Latent Semantic Analysis (LSA) 、 Probabilitistic Latent Semantic Analysis (PLSA)、Latent Dirichlet Allocation ( LDA)。這些方法在分類，聚類、檢索、推薦等領(lǐng)域都有著很多的應(yīng)用，并取得了比較好的效果。下面就LSA及PLSA方法進行簡要介紹。

4.1 LSA簡介

?????? LSA ^[6,7] 模型認(rèn)為特征之間存在某種潛在的關(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利用奇異值分解來進行計算，數(shù)學(xué)過程可以表述如下：

?????? 對于 的矩陣A，其中m為特征數(shù)，n為樣本數(shù)。令? ?，經(jīng)過奇異值分解，矩陣A可分解成3個矩陣的乘積：

其中，U、V是 ?和 ?的正交矩陣，分別稱為矩陣A的奇異值對應(yīng)的左、右奇異向量， 是 ?的對角矩陣，稱為A的奇異標(biāo)準(zhǔn)形，其對角元素為矩陣A的奇異值。奇異值按照遞減的排列構(gòu)成對角矩陣 ，取 中前k個最大奇異值構(gòu)成 ?的，取U和V最前面的k列構(gòu)成 ?的U _k 和 ?的V _k ，構(gòu)建A的k-秩矩陣

????????????????????????????????????????????????????? (6)

其中，U _k 和V _k 中的行向量分別作為特征向量和對象向量，k是降維后的維數(shù)。

4.2 plas介紹

?????? PLSA ^[8,9] 模型是由Hofmann提出的用于文本檢索的概率生成模型，與相比較于LSA，PLSA是基于概率模型的，并直接引入了潛在class變量 ，下面的用文本處理語言來描述該模型。

選定一篇文檔的概率p(d)，每篇文檔以概率 屬于一個主題，而給定一個主題，每一個詞以概率 產(chǎn)生。將這個過程形成聯(lián)合的概率模型表達(dá)式：

???????????????????? ?????????????????????????? (7)

?????? ????????????? ???????????? ??????????(8)

則：

????????????????? ???????????????????? (9)

在PLSA實際的使用過程中，存在著overfit的風(fēng)險，一般訓(xùn)練過程是通過EM算法，進行模型參數(shù)訓(xùn)練，獲得p(z|d)、p(w|z)概率。

?????? PLSA和其相關(guān)的變形，在分類、聚類、檢索等方面，特征相關(guān)性計算等方面，獲得了廣泛的應(yīng)用，并取得了比較好的效果。

4.2 plas 介紹

?????? PLSA ^[8,9] 模型是由 Hofmann 提出的用于文本檢索的概率生成模型，與相比較于 LSA ， PLSA 是基于概率模型的，并直接引入了潛在 class 變量 z∈Z=｛Z _1… Z _k ?｝ ，下面的用文本處理語言來描述該模型。

選定一篇文檔的概率p(d)，每篇文檔以概率p(z|d)屬于一個主題，而給定一個主題，每一個詞以概率p(w|z) 產(chǎn)生。將這個過程形成聯(lián)合的概率模型表達(dá)式：

在PLSA實際的使用過程中，存在著overfit的風(fēng)險，一般訓(xùn)練過程是通過EM算法，進行模型參數(shù)訓(xùn)練，獲得p(z|d)、p(w|z)概率。

?????? PLSA和其相關(guān)的變形，在分類、聚類、檢索等方面，特征相關(guān)性計算等方面，獲得了廣泛的應(yīng)用，并取得了比較好的效果。

.3 小結(jié)

?????? 主題方法的引入，在一定程度上彌補了BOW的假設(shè)的獨立性，在工業(yè)中，主題的方法也越來越多的應(yīng)用到實際的機器學(xué)習(xí)中，包括在圖像處理領(lǐng)域、傳統(tǒng)的分類、聚類、檢索等方面，都取得了比較好的效果。

總結(jié)

?????? 相似度的計算在數(shù)據(jù)挖掘方面有著廣泛的應(yīng)用，根據(jù)不同的應(yīng)用場景，各種方法各有其優(yōu)劣特點，對于相似度效果的影響，除了方法本身之外，合理有效的特征的選擇和使用也是至關(guān)重要的，同時，根據(jù)應(yīng)用場景的不同，選擇合理的方法，對于解決問題，有著重要的作用。

參考文獻： ?

1. G.S. Manku, A. Jain, A.D. Sarma. Detecting Near-Duplicates for Web Crawling. WWW2007, 2007

2. A. Das, M. Datar, A.Garg. Google News Personalization: Scalable Online Collaborative Filtering. WWW2007, 2007

3. http://en.wikipedia.org/wiki/MinHash

4. M. S. Charikar. Similarity estimation techniques from rounding algorithms. STOC’02. 2002

5. http://en.wikipedia.org/wiki/Locality-sensitive_hashing

6. K. Dave, S. Lawrence, and D. Pennock. Mining the peanut gallery: opinion extraction and semantic classification of product reviews. In Proceedings of the 22th International World Wide Web Conference, Budapest, Hungary, 2003

7. http://en.wikipedia.org/wiki/Latent_semantic_analysis

8. T. Hofmann. Probabilistic Latent Semantic Analysis. In Proceedings of the 15th Conference on Uncertainty in AI(1999).

9. Y. M kim, J. F. Pressiot M. R.Amini etc. An Extension of PLSA for Document Clustering. CIKM’08

by chenqingxuan

搜索研發(fā)部官方博客 ? Blog Archive ? 相似度計算常用方法綜述