文本相似度算法

1、1.信息檢索中的重要發(fā)明TF-IDF1.1TFTerm frequency即關(guān)鍵詞詞頻，是指一篇文章中關(guān)鍵詞出現(xiàn)的頻率，比如在一篇M個詞的文章中有N個該關(guān)鍵詞，則（公式1.1-1）為該關(guān)鍵詞在這篇文章中的詞頻。1.2IDFInverse document frequency指逆向文本頻率，是用于衡量關(guān)鍵詞權(quán)重的指數(shù)，由公式（公式1.2-1）計算而得，其中D為文章總數(shù)，Dw為關(guān)鍵詞出現(xiàn)過的文章數(shù)。2.基于空間向量的余弦算法2.1算法步驟預(yù)處理文本特征項選擇加權(quán)生成向量空間模型后計算余弦。2.2步驟簡介2.2.1預(yù)處理預(yù)處理主要是進行中文分詞和去停用詞，分詞的開源代碼有：ICTCLAS。然后按照停

2、用詞表中的詞語將語料中對文本內(nèi)容識別意義不大但出現(xiàn)頻率很高的詞、符號、標點及亂碼等去掉。如“這，的，和，會，為”等詞幾乎出現(xiàn)在任何一篇中文文本中，但是它們對這個文本所表達的意思幾乎沒有任何貢獻。使用停用詞列表來剔除停用詞的過程很簡單，就是一個查詢過程：對每一個詞條，看其是否位于停用詞列表中，如果是則將其從詞條串中刪除。圖2.2.1-1中文文本相似度算法預(yù)處理流程2.2.2文本特征項選擇與加權(quán)過濾掉常用副詞、助詞等頻度高的詞之后，根據(jù)剩下詞的頻度確定若干關(guān)鍵詞。頻度計算參照TF公式。加權(quán)是針對每個關(guān)鍵詞對文本特征的體現(xiàn)效果大小不同而設(shè)置的機制，權(quán)值計算參照IDF公式。2.2.3向量空間模型VSM

3、及余弦計算向量空間模型的基本思想是把文檔簡化為以特征項（關(guān)鍵詞）的權(quán)重為分量的N維向量表示。這個模型假設(shè)詞與詞間不相關(guān)（這個前提造成這個模型無法進行語義相關(guān)的判斷，向量空間模型的缺點在于關(guān)鍵詞之間的線性無關(guān)的假說前提），用向量來表示文本，從而簡化了文本中的關(guān)鍵詞之間的復(fù)雜關(guān)系，文檔用十分簡單的向量表示，使得模型具備了可計算性。在向量空間模型中，文本泛指各種機器可讀的記錄。用D（Document）表示文本，特征項（Term，用t表示）指出現(xiàn)在文檔D中且能夠代表該文檔內(nèi)容的基本語言單位，主要是由詞或者短語構(gòu)成，文本可以用特征項集表示為D（T1，T2，Tn），其中Tk是特征項，要求滿足1<=k

4、<=N。下面是向量空間模型（特指權(quán)值向量空間）的解釋。假設(shè)一篇文檔中有a、b、c、d四個特征項，那么這篇文檔就可以表示為D（a，b，c，d）對于其它要與之比較的文本，也將遵從這個特征項順序。對含有n個特征項的文本而言，通常會給每個特征項賦予一定的權(quán)重表示其重要程度，即DD（T1，W1；T2，W2；，Tn，Wn）簡記為DD（W1，W2，Wn）我們把它叫做文本D的權(quán)值向量表示，其中Wk是Tk的權(quán)重，1<=k<=N。在上面那個例子中，假設(shè)a、b、c、d的權(quán)重分別為30，20，20，10，那么該文本的向量表示為D（30，20，20，10）在向量空間模型中，兩個文本D1和D2之間的內(nèi)容

5、相關(guān)度Sim（D1，D2）常用向量之間夾角的余弦值表示，公式為：其中，W1k、W2k分別表示文本D1和D2第K個特征項的權(quán)值，1<=k<=N。下面是利用模型進行余弦計算的示例。在自動歸類中，我們可以利用類似的方法來計算待歸類文檔和某類目的相關(guān)度。假設(shè)文本D1的特征項為a，b，c，d，權(quán)值分別為30，20，20，10，類目C1的特征項為a，c，d，e，權(quán)值分別為40，30，20，10，則D1的向量表示為D1（30，20，20，10，0）C1的向量表示為C1（40，0，30，20，10）則根據(jù)上式計算出來的文本D1與類目C1相關(guān)度是0.86。那么0.86具體是怎么推導(dǎo)出來的呢？在數(shù)學(xué)當

6、中，n維向量是Vv1，v2，v3，.，vn模為|v|=sqrt（v1*v1+v2*v2+vn*vn）兩個向量的點積m*n=n1*m1+n2*m2+.+nn*mn相似度sim（m*n）/（|m|*|n|）它的物理意義就是兩個向量的空間夾角的余弦數(shù)值。下面是代入公式的過程：d1*c1=30*40+20*0+20*30+10*20+0*10=2000|d1|=sqrt（30*30+20*20+20*20+10*10+0*0）=sqrt（1800）|c1|=sqrt（40*40+0*0+30*30+20*20+10*10）=sqrt（3000）sim=d1*c1/（|d1|*|c1|）=2000/sq

7、rt（1800*3000）=0.86066完畢。2.3算法實現(xiàn)開源代碼：Text-Similarity-0.08簡介：PERL腳本、自定義去停用詞表、無語義識別功能、不適于中文。局限：僅適用于英文、無語義相似判別功能編譯安裝：（1）進入代碼主目錄里的/bin修改text_similarity.pl將第一行改為#!/usr/bin/perl（2）退回代碼主目錄，分別執(zhí)行perl Makefile.PLmakemake testmake install（3）重新進入主目錄/bin進行測試圖2.3-1代碼效果可以看見語句“.this is one”與“?this is two”的匹配度是0.66；“

8、.this is one”與“.this is two”的匹配度仍然是0.66；“.this is one”與“.this is one”的匹配度是1；“.this is one”與“.（）（）this is one”的匹配度是1。說明匹配的算法去停用字功能存在。2.4缺陷這類算法沒有很好地解決文本數(shù)據(jù)中存在的自然語言問題，即同義詞和多義詞。這樣對于搜索的精度產(chǎn)生很大的影響。2.5算法變體圖2.5-1算法變體（紅）3.改進算法3.1隱形語義引標隱性語義標引（LSI）利用矩陣理論中的“奇異值分解（SVD）”技術(shù)，將詞頻矩陣轉(zhuǎn)化為奇異矩陣：首先從全部的文檔集中生成一個文檔矩陣，該矩陣的每個分量為整

9、數(shù)值，代表某個特定的文檔矩陣出現(xiàn)在某個特定文檔中次數(shù)。然后將該矩陣進行奇異值分解，較小的奇異值被剔除。結(jié)果奇異向量以及奇異值矩陣用于將文檔向量和查詢向量映射到一個子空間中，在該空間中，來自文檔矩陣的語義關(guān)系被保留。最后，可以通過標準化的內(nèi)積計算來計算向量之間的夾角余弦相似度，進而根據(jù)計算結(jié)果比較文本間的相似度。LSI引入的唯一變化就是剔除小的奇異值，因為與小的奇異值相關(guān)聯(lián)的特征實際上在計算相似度時并不相關(guān)，將它們包括進來將降低相關(guān)性判斷的精確度。保留下來的特征是那些對文檔向量在m維空間中的位置大有影響的特征。剔除小的奇異值將文檔特征空間變?yōu)槲臋n概念空間。概念向量之問使用內(nèi)積的夾角余弦相似度計算

10、比原來基于原文本向量的相似度計算更可靠，這也是使用LSI方法的主要原因所在。LSI的缺點在于它的效果依賴于上下文信息，過于稀疏的語料不能很好的體現(xiàn)其潛在的語義。3.2基于語義相似度的文本相似度算法用向量空間模型（VSM）來表示文本在該領(lǐng)域內(nèi)普遍受到認可，是因為其在知識表示方法上的巨大優(yōu)勢。在該模型中，文本內(nèi)容被形式化為多維空間中的一個點，通過向量的形式給出，把對文本內(nèi)容的處理簡化為向量空間中向量的運算，使問題的復(fù)雜性大為降低。但是它很大的不足之處在于只考慮了詞在上下文中的統(tǒng)計特性，假定關(guān)鍵詞之間線性無關(guān)，而沒有考慮詞本身的語義信息，因此具有一定的局限性。結(jié)合語義相似度計算后的算法流程如下所示：

11、圖3.2-1基于向量空間的語義相似度算法流程圖其中，語義相關(guān)度計算獲得相似度矩陣的方向有兩個：基于知網(wǎng)HowNet或者基于WordNet。4.其它算法涉及的相似度衡量方式4.1基于拼音相似度的漢語模糊搜索算法不同于傳統(tǒng)的以關(guān)鍵詞匹配為核心的匹配技術(shù)，這里提出基于拼音相似度的編輯距離來衡量漢字字符串之間的相似度。論文提出三種編輯距離：基于漢字的編輯距離、基于拼音的編輯距離，以及基于拼音改良的編輯距離。4.2最長公共子序列（1）將兩個字符串分別以行和列組成矩陣。（2）計算每個節(jié)點行列字符是否相同，如相同則為1。（3）通過找出值為1的最長對角線即可得到最長公共子串。為進一步提升該算法，我們可以將字符相同節(jié)點的值加上左上角（di-1，j-1）的值，這樣即可獲得最大公共子串的長度。如此一來只需以行號和最大值為條件即可截取最大子串。4.3最小編輯距離算法（1）狹義編輯距離設(shè)A、B為兩個字符串，狹義的編輯距離定義為把A轉(zhuǎn)換成B需要的最少刪除（刪除A中一個字符）、插入（在A中插入一個字符）和替換（把A中的某個字符替換成另一個字符）的次數(shù)，用ED（A，B）來表示。直觀來說，兩個串互相轉(zhuǎn)換需要經(jīng)過的步驟越多，差異越大。（2）步驟1.對兩部分文本進行處理，將所有的非文本字符替換為分段標記“#”2.較長文