簡介

        針對文本相似判定，本文提供余弦相似度和SimHash兩種算法，并根據(jù)實際項目遇到的一些問題，給出相應(yīng)的解決方法。經(jīng)過實際測試表明：余弦相似度算法適合于短文本，而SimHash算法適合于長文本，并且能應(yīng)用于大數(shù)據(jù)環(huán)境中。

余弦相似度

原理

        余弦定理：

圖-1 余弦定理圖示

         性質(zhì)：

         余弦值的范圍在[-1,1]之間，值越趨近于1，代表兩個向量的方向越趨近于0°，他們的方向更加一致，相應(yīng)的相似度也越高。需要指出的是，在文本相似度判定中，因為文本特征向量定義的特殊性，其余弦值范圍為[0,1]，即向量夾角越趨向于90°，則兩向量越不相似。

向量空間模型

        VSM（Vector Space Model）把對文本內(nèi)容的處理簡化為向量空間中的向量運算。

        概念：

        1）文檔（D）：泛指文檔或文檔片段，一般表征一篇文檔。

        2）詞匯（T）：文本內(nèi)容特征的基本語言單位，包含字、詞、詞組或短語。

        3）權(quán)重（W）：表征詞匯T的權(quán)重，在文檔D中的重要程度。

        權(quán)重：

        目前表征一個字詞在一個文本集或者語料庫中某篇文本中的重要程度的統(tǒng)計方法為TF-IDF(term frequency–inverse document frequency)，詞匯的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時會隨著它在語料庫中出現(xiàn)的頻率成反比下降，詳細(xì)內(nèi)容在此不贅述。但是本文在實際項目中面臨的問題是，文本集是變動的，而且變化速率比較快，因此并不適用于采用TF-IDF方法。本文采用非常簡單直觀的方法，即以詞頻來表征該詞匯在文本中的重要程度（即權(quán)重）。

        向量對齊：

        由于在實際應(yīng)用中，表征文本特征的兩個向量的長度是不同的，因此必然需要對上述向量進行處理。目前存在兩種方法：1）剔除掉向量中不重要的詞匯，從而使得兩個向量長度保持一致，目前主要依靠經(jīng)驗設(shè)定一些關(guān)鍵詞來處理，但是其準(zhǔn)確率不可保證；2）歸并向量，并根據(jù)原向量是否在新向量（歸并后的向量）存在，若存在則以該詞匯的詞頻來表征，若不存在則該節(jié)點置為0，示例如下：

        Text1: 我/是/中國人/

        Text2: 我們/是/中國人/

        Vector: 我/是/中國人/我們/

        Vector1 = (1, 1, 1, 0)

        Vector2 = (0, 1, 1, 1)

        上述“/”為采用IK分詞，智能切分后的間隔符，則歸并后的向量如Vector所示，對齊后的向量分別為Vector1 和Vector2。之后則根據(jù)兩向量的余弦值確定相似度。

文本特例

        由于在實際項目中，本文發(fā)現(xiàn)了2個特例，并相應(yīng)給出了解決方案。

        1）長句包含短句（無需完全包含）：

        Text1：“貫徹強軍目標(biāo)出實招用實勁 努力開創(chuàng)部隊建設(shè)新局面”

        Text2：“在接見駐浙部隊領(lǐng)導(dǎo)干部時強調(diào) 貫徹強軍目標(biāo)出實招用實勁 努力開創(chuàng)部隊建設(shè)新局面”

        上述兩個文本為網(wǎng)絡(luò)上實際的網(wǎng)頁標(biāo)題，若簡單以余弦相似度來判定，其誤判率是比較高的。本文解決方案為：若長句長度（中文切分后以詞匯為單位表征，并非以字符為單位）為短句的1.5倍，則針對長句選定短句長度的文本內(nèi)容逐個與短句進行相似度判定，直至長句結(jié)束，若中間達(dá)到預(yù)設(shè)的閾值，則跳出該循環(huán)，否則判定文本不相似。

        2）文本中存在同義表述

        Text1：“臺灣居民明日起持臺胞證可通關(guān) 無需辦理簽注”

        Text2：“明起臺胞來京無需辦理簽注 電子臺胞證年內(nèi)實施”

        上述兩個文本中“臺胞”和“臺灣居民”，“明日起”和“明起”為同義表述，可以理解為近義詞，但不完全為近義詞范疇。本文解決方案為引入同義詞詞典，鑒于中文詞匯的豐富性，其能在一定程度上緩解，仍然不是根本解決之法。

應(yīng)用場景及優(yōu)缺點

        本文目前將該算法應(yīng)用于網(wǎng)頁標(biāo)題合并和標(biāo)題聚類中，目前仍在嘗試應(yīng)用于其它場景中。

        優(yōu)點：計算結(jié)果準(zhǔn)確，適合對短文本進行處理。

        缺點：需要逐個進行向量化，并進行余弦計算，比較消耗CPU處理時間，因此不適合長文本，如網(wǎng)頁正文、文檔等。

　　余弦相似度算法源程序：

　　備注：同義詞詞典“synonyms.dict”文件較大，完全可以自己構(gòu)建，在此就不贅述了。

SimHash

        SimHash為Google處理海量網(wǎng)頁的采用的文本相似判定方法。該方法的主要目的是降維，即將高維的特征向量映射成f-bit的指紋，通過比較兩篇文檔指紋的漢明距離來表征文檔重復(fù)或相似性。

過程

        該算法設(shè)計十分精巧，主要過程如下：

        1.  文檔特征量化為向量；

        2.  計算特征詞匯哈希值，并輔以權(quán)重進行量化；

        3.  針對f-bit指紋，按位進行疊加運算；

        4.  針對疊加后的指紋，若對應(yīng)位為正，則標(biāo)記為1，否則標(biāo)記為0。

　　備注：此處f-bit指紋，可以根據(jù)應(yīng)用需求，定制為16位、32位、64位或者其它位數(shù)等。

       如圖-2所示，為SimHash作者Charikar在論文中的圖示，本文結(jié)合實際項目解釋如下：Doc表征一篇文本，feature為該文本經(jīng)過中文分詞后的詞匯組合，按列向量組織，weight為對應(yīng)詞匯在文本中的詞頻，之后經(jīng)過某種哈希計算得出哈希值，見圖中1和0的組合，剩余部分不再贅述。需要指出，Charikar在論文中并未指定需要采用哪種哈希函數(shù)，本文作者認(rèn)為，只要哈希計算值能夠均衡化、分散化，哈希函數(shù)可以根據(jù)實際應(yīng)用場景進行設(shè)計，本文在實際的項目中自行設(shè)計哈希函數(shù)，雖未經(jīng)過完全驗證，但是測試結(jié)果表明，該函數(shù)當(dāng)前能夠滿足需求。

圖-2 SimHash處理過程

漢明距離

        漢明距離應(yīng)用于數(shù)據(jù)傳輸差錯控制編碼，它表示兩個（相同長度）字對應(yīng)位不同的數(shù)量。鑒于SimHash***計算出的指紋采用0和1進行組織，故而用其來衡量文檔相似性或者重復(fù)性，該部分詳細(xì)內(nèi)容在此不再贅述。

應(yīng)用場景與優(yōu)缺點

        本文目前將該算法應(yīng)用于話題發(fā)現(xiàn)和內(nèi)容聚合等場景中，同時也在嘗試其它應(yīng)用場景。

        優(yōu)點：文本處理速率快，計算后的指紋能夠存儲于數(shù)據(jù)庫，因此對海量文本相似判定非常適合。

        缺點：由于短文本的用于哈希計算的數(shù)據(jù)源較少，因此短文本相似度識別率低。

　　SimHash算法源程序： 

　　備注：源程序中“131313”只是作者挑選的一個較大的素數(shù)而已，不代表特別含義，該數(shù)字可以根據(jù)需求進行設(shè)定。