簡介

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

余弦相似度

原理

        余弦定理：

圖-1 余弦定理圖示

         性質：

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

向量空間模型

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

        概念：

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

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

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

        權重：

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

        向量對齊：

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

        Text1: 我/是/中國人/

        Text2: 我們/是/中國人/

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

        Vector1 = (1, 1, 1, 0)

        Vector2 = (0, 1, 1, 1)

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

文本特例

        由于在實際項目中，本文發現了2個特例，并相應給出了解決方案。

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

        Text1：“貫徹強軍目標出實招用實勁 努力開創部隊建設新局面”

        Text2：“在接見駐浙部隊領導干部時強調 貫徹強軍目標出實招用實勁 努力開創部隊建設新局面”

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

        2）文本中存在同義表述

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

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

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

應用場景及優缺點

        本文目前將該算法應用于網頁標題合并和標題聚類中，目前仍在嘗試應用于其它場景中。

        優點：計算結果準確，適合對短文本進行處理。

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

　　余弦相似度算法源程序：

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

SimHash

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

過程

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

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

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

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

        4.  針對疊加后的指紋，若對應位為正，則標記為1，否則標記為0。

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

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

圖-2 SimHash處理過程

漢明距離

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

應用場景與優缺點

        本文目前將該算法應用于話題發現和內容聚合等場景中，同時也在嘗試其它應用場景。

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

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

　　SimHash算法源程序： 

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