簡介

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

余弦相似度

原理

        余弦定理：

圖-1 余弦定理圖示

         性質(zhì)：

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

向量空間模型

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

        概念：

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

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

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

        權(quán)重：

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

        向量對齊：

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

        Text1: 我/是/中國人/

        Text2: 我們/是/中國人/

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

        Vector1 = (1, 1, 1, 0)

        Vector2 = (0, 1, 1, 1)

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

文本特例

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

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

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

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

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

        2）文本中存在同義表述

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

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

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

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

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

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

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

　　余弦相似度算法源程序：

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

SimHash

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

過程

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

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

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

        3.  針對f-bit指紋，按位進(jìn)行疊加運(yùn)算；

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

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

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

圖-2 SimHash處理過程

漢明距離

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

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

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

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

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

　　SimHash算法源程序： 

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