語言信息處理-文本相似度相關研究

1、1 引言出于個人對語言信息處理相關內容的興趣，對兩段文本之間如何比較相似性也有很大的好奇，在之前的工作中也用到相關知識，于是在本次的報告中，根據(jù)自己的能力實現(xiàn)了一個可以比較兩段文本相似程度的小算法，算法原理簡單，只是從“詞”的角度進行分析，沒有加入語義的分析，但是如果在特定的領域也會有不錯的效果。報告中會主要介紹算法的原理、自己在原理上進行的處理以及成果的展示。2 算法思想本文所研究的算法是基于文本相似度匹配而實現(xiàn)的。首先將文本處理成為相對應的向量，根據(jù)空間里向量的相近程度來反映出兩個文本之間的相似度。由于文本數(shù)據(jù)具有無結構的特性，需要對其進行一定的預處理，這樣才能轉換成為數(shù)值計算。本文所采用

2、的思路是首先對文本進行中文分詞處理，然后對分詞之后的結果進行詞頻統(tǒng)計，統(tǒng)計時可以同時完成對數(shù)據(jù)的降維操作。將統(tǒng)計結果排列成為兩個向量，最后利用向量計算的相關公式進行相似度計算。其總體流程如圖1所示。圖1算法流程圖3 基于文本相似度匹配的文本匹配算法3.1文本分詞一整段的文本由多個詞語組成，我們要進行文本之間相似度匹配的檢測。第一步是對文本進行中文分詞，分成一些關鍵的詞語組，其中要剔除掉語意詞、助詞等等對文章大意沒有影響的詞匯。英文分詞是相對容易的，因為每兩個單詞之間會有空格進行區(qū)分，這就使得分詞工作變成了檢測文章中的空格，然后加以分割。但中文句子并沒有這樣的特征，一個詞匯是由多個漢字組成，而且

3、有可能出現(xiàn)一個字與前后兩個字都能組成詞語的情況，需要根據(jù)語境進行判定區(qū)分，所以中文的分詞技術相對來說要難很多。但目前中文分詞技術也日漸成熟，出現(xiàn)了很多強大的中文分詞工具，也提供了很多不能編程語言的接口。單字分詞、二分法和詞典分詞是目前分詞的主要方法。 單字分詞，顧名思義即在對中文文本進行分詞時，以字為單位進行切分。字索引很靈活，但是實現(xiàn)單字匹配算法卻很復雜，也往往需要大量的CPU運算進行支撐。二分法，即將每兩個字當作一個詞語進行切分，然后建立索引，使用二分法可以明顯地減少每個詞條后位置信息的長度。 在進行了對比分析之后，詞典分詞的方法最為適合本系統(tǒng)的需要。詞典分詞的基本思想是先構造出一個基本詞

4、匯的詞典，然后將遇到的文本同詞典比對分析進行分詞，這是當前相對準確的方法，也被廣泛使用。本文使用的時Ansj中文分詞，是一個基于google語義模型+條件隨機場模型的中文分詞的java實現(xiàn)，詞速度達到每秒鐘200萬字左右，準確率能達到96%以上,目前實現(xiàn)了中文分詞、中文姓名識別、用戶自定義詞典等功能,可以應用到自然語言處理等方面,適用于對分詞效果要求高的各種項目。在文本中匹配單詞時，正向最大匹配算法和逆向最大匹配法是詞典分詞法經(jīng)常用到的算法，從左側開始依次讀入數(shù)據(jù)，嘗試把幾個連續(xù)出現(xiàn)的字符與詞庫中存在的詞條進行匹配，如果成功，就可以分出一個詞條，這是正向，而逆向是從文本的末端開始，每次都取最末

5、端連續(xù)出現(xiàn)的幾個字符進行匹配，如果匹配失敗，那么加入該字段最前面的一個字，繼續(xù)進行匹配Error! Reference source not found.。當文本比較復雜，需要比較精確的分詞的時候，就要用多種方式對文本進行切分，對不同方式的切分結果進行比對，相同的切分結果得到的詞語就是真正需要的詞。3.2詞頻統(tǒng)計與數(shù)據(jù)降維 上文中我們提到了要用到每個詞條的出現(xiàn)的次數(shù)，那么就需要進行詞頻統(tǒng)計，也就是詞條頻率，用來評價一個詞對于一段文本的重要性。 在信息領域，基于匹配的詞頻統(tǒng)計算法和基于樹結構的詞頻統(tǒng)計算法是最為經(jīng)典也是最被認可的詞頻統(tǒng)計方法，被廣泛使用。 在單關鍵詞

6、匹配算法中，比較著名的有BF算法、KMP算法、BM算法等。 （1）BF算法 BF算法也被稱為是蠻力算法，它的基本思想是：首先，A1和B1比較，如果相等，再對A2和B2進行比較，一直到Bm為止；如果A1和B1不相等，則B右移一下，繼續(xù)進行比較。如果存在k，1kn，且Ak+1k+m=T1m，則匹配成功，否則失敗。 （2）KMP算法 KMP算法是由高德納（Donald Ervin Knuth）和 Vaughan Pratt 在1977年合作發(fā)明的。其基本思想為：如果在匹配的進程中，判斷Ai和Bj是否相等，如果相

7、等，那么繼續(xù)對Ai+1和Bj+1進行判斷；如果兩者不相等，討論一下兩種情況，若j=1，向右移動，判斷Ai+1和B1相等與否，若1<j<=m，則右移j-next(j)位，檢查Ai和Bnext(j)是否匹配，重復此過程直到j=m或i=n結束。 （3）BM算法 BM算法1977年由Bob Boyer 和J Strother Moore提出，是一個字符串匹配算法。其基本思想是：設定一個位置i，將主串i起由左至右的進行判斷，若發(fā)現(xiàn)不相等，則下次應從主串的i + distance(si)位置開始繼續(xù)進行接下去的判斷

8、，即跳過distance(si)個字符而無需進行比較。 （4）本文使用的算法基于匹配的詞頻統(tǒng)計方法，是在對待處理文本進行多次了掃描的基礎上進行的，需要付出大量的時間和空間代價，尤其在文本數(shù)據(jù)量較大時，則更難以實現(xiàn)。針對這個難點，提出了基于樹結構的算法來對詞條進行統(tǒng)計。其基本思想是：首先根據(jù)已有的關鍵詞集合構建一棵查找樹，然后利用這個查找樹對文檔進行掃描，從而進行關鍵詞的統(tǒng)計。利用樹形結構的好處是，在統(tǒng)計時，對文本進行一次掃描就可以完成一個詞與查找樹的比較，進而可統(tǒng)計出所有的詞條信息。利用樹形結構大大減少了不必要的匹配過程，提高了統(tǒng)計效率。本系統(tǒng)在借助HashMap的基礎上進行詞條的頻

9、率統(tǒng)計，這種方式相對更加簡單明了，易于理解和使用。其基本思想是：利用HashMap，把關鍵字設置成詞條，其value等于該詞條出現(xiàn)的次數(shù)。對已經(jīng)分詞完畢的文本逐個詞條地進行分析，先進行判斷，如果該詞條不存在于HashMap，那么就將該詞條加入其中，并將其value設置為1；如果詞條已經(jīng)存在于HashMap，就將該詞條的value加1，進行一個算法復雜度為O（n）的操作之后，就可以將整個文本的詞頻統(tǒng)計出來。具體算法如算法1所示。算法1 詞頻統(tǒng)計算法輸入： 文本分詞結果的list  HashMap hm=new HashMap()；/初始化一個HashMapwhile(list

10、中仍有未處理詞條)if（詞條有效）then if（本詞條不存在于hm） then 相應value=1；else if(本詞條存在于hm) then 相應value+1；elsecontinue；rerurn;利用HashMap進行詞頻統(tǒng)計雖然很有效，但是也有弊端，那就是它最終的結果是無序的，而且當對兩個文本進行利用HashMap的方法進行詞頻統(tǒng)計之后，很難保證兩個文本同一詞條在HashMap的位置是一樣的。如果同一詞條所對應的詞頻不能出現(xiàn)在最終兩個向量的同一個維度，那么接下去的計算必然是無效的。所以在第二個文本進行填充HashMap之后就要進行一定的操作處理，最終使得兩個向量相同的詞條的詞頻出

11、現(xiàn)在相同的維度。因此，設計了算法對此進行實現(xiàn)，其基本思想是：設置兩個數(shù)組和兩個迭代器，兩個數(shù)組用來最終存儲兩個向量的值，分別進行迭代操作判斷出現(xiàn)順序完成統(tǒng)計。首先，用第一個迭代器對第一個HashMap進行遍歷，將對應關鍵字的鍵值從數(shù)組第一個位置起往后存儲。與此同時，遍歷每一個關鍵字之后，對這個關鍵字在第二個HashMap中是否存在進行判斷：如果存在，這說明兩個文本中都存在這個詞條；如果不存在，這說明這個詞條只在第一個文本中出現(xiàn)。判斷可知該算法的時間復雜度為O(n)。接下來要對利用第二個迭代器遍歷第二個HashMap，這時候只需要對詞條只出現(xiàn)在第二個文本的情況進行統(tǒng)計。對應的條件就是判斷該關鍵字

12、的鍵值在第一個HashMap中是否為空，是的話那就說明這個詞條的頻率需要統(tǒng)計。由此一來，既可以將所有出現(xiàn)在兩個文本中的詞條進行統(tǒng)計并在最終的向量數(shù)組中存儲，又可以使得兩個向量保證以相同的詞條順序存儲，那么接下來的計算就是準確的。具體算法如算法2所示。算法2 向量生成算法輸入：存儲詞頻統(tǒng)計結果的HashMap，hm1和hm2。輸出：存儲向量的vector1，vector。Integer vector1;Integer vector2;/ 初始化兩個數(shù)組Iterator iterator1 = hm1.keySet().iterator();/初始化兩個iterator Iterator iter

13、ator2 = hm2.keySet().iterator();while(iterator1.hasNext()不為空)vector1i=hm1.get(iterator.next();if(該關鍵字不存在于hm2) then buff2i = 0;else buff2i = hm2.get(iterator.next();while(iterator1.hasNext()不為空)if(該關鍵字不存在于hm1)then buff2i= hm2.get(iterator.next();buff1i=0;else break;return;如果數(shù)據(jù)的維度過大，無疑會大大增加程序的運行時間，所以詞

14、頻統(tǒng)計中數(shù)據(jù)降維是一個重要因素，想要提高效率必須要進行合適的降維操作。當文本中的詞條的數(shù)量很多，又有很多的標點符號時，都會增加向量的維度，提高了計算的復雜程度。為了提高計算的效率，需要進行適當?shù)慕档拖蛄烤S度的操作，去除一些無關緊要的詞語、標點等，減少向量的維度。這樣既可以有效的提高效率，又可以提高算法的精度。 本系統(tǒng)在處理這個問題時，是在進行HashMap填充之前，利用分詞結果剔除一些標點、空格、一般常用語等對于相似度匹配來說的干擾項。這樣可以進行簡單地去除那些對文本相似度產(chǎn)生精確度影響的詞條，也就是說，在把詞條加入HashMap時，會先進行簡單地判斷該詞條是否為對相似度判斷無效的詞

15、條，只有有用詞條會被添加到HashMap中，否則就直接跳過，繼續(xù)判斷下一詞條。3.3相似度計算VSM模型（VSM：Vector Space Model）即向量空間模型，由索頓等人于20世紀70年代提出，并成功地應用于著名的SMART文本檢索系統(tǒng)Error! Reference source not found.。向量空間模型的基本思想是：用特征向量來表示原來的文本，這樣抽象的文本相似度計算問題就轉化成了可見的為空間向量之間的運算，由此大大降低了問題的復雜性，而其可行性也大為提升。它首先按照分詞技術得到的分詞結果，把原來的文本映射為一個n維的空間向量，文本的相似度就可以通過計算兩段文本對應的向量

16、的余弦值來確定，利用了空間里向量的相近程度解決了文本之間的的相似性問題，簡單易懂。對于計算機來說，模糊的文本數(shù)據(jù)在經(jīng)過向量空間模型的處理之后，轉換成了可被計算機識別處理的數(shù)據(jù)，在得出兩個向量之間的相似性程度之后，兩個文本之間的相似性問題也隨之得到解決。每一篇文本，都是由許許多多的詞條組成，文本和其中的詞條之間存在一定的關系，我們需要對這個關系進行一個研究。我們可以把一段文本看成一個向量D（value1,value2,valuen），其中value1，value2是對應于組成這個文本的某個詞條的一個值，在下文中會對這個值進行進一步的說明。這樣，假設有在文本1中出現(xiàn)了3個詞語a、b、c，在文本2中

17、出現(xiàn)了3個詞語a，c，d，我們要比較文本1和文本2的相似度，那么我們選擇兩者并集所包含的詞語數(shù)量作為兩個文本的向量的維度數(shù)，也就是4維，那么接下來就是對每一維的值進行確定，我們使用TFIDF作為這個值，它的理論思想是這樣的：一個在某個文本中多次出現(xiàn)而在其他文本中很少的詞條對不同文本的區(qū)分具有很強的意義，根據(jù)這樣的詞語對文本進行分類處理可以得到很可靠的效果。那么首先讓我們了解兩個概念：詞頻 (term frequency, TF) 指的是某一個給定的詞語在該文件中出現(xiàn)的次數(shù)Error! Reference source not found.。在下面的算式中 ni,j 

18、;是該詞條的使用次數(shù)，文本中全部詞條的出現(xiàn)次數(shù)的和作為分母。其計算如式（1）所示。 （1）逆向文件頻率（inverse document frequency，IDF）是一個詞語普遍重要性的度量。如果詞條t在所有文本中出現(xiàn)次數(shù)越少，基數(shù)就會越小，IDF的值就越大，這就意味著t可以對不同文本進行很明顯的區(qū)分。IDF可以由式（2）獲得，其中，|D|：所匹配的庫中的文本總數(shù)，：包含詞語ti的文本數(shù)。 （2）上文中提到了文本所對應的向量有很多個維數(shù)，我們現(xiàn)在要給每個維的值進行賦值，也就是最后我們得到的TFIDF如式（3）所示： （3） 假設上文中，idf均為1，文本1詞條a出現(xiàn)的頻率為0.4，b出現(xiàn)的頻

19、率為0.3，c出現(xiàn)的頻率為0.3，文本2詞條a出現(xiàn)的頻率為0.6，c出現(xiàn)的頻率為0.2，d出現(xiàn)的頻率為0.2，按照相同詞條的頻率出現(xiàn)在向量的相同維度，由此可以得,兩個文本向量為（0.4,0.3,0.3,0）和（0.6,0,0.2,0.2），再按照下文中的相似度計算方法計算相似度。首先把兩段文本處理成為對應的兩個向量，基于向量空間模型的理論，兩段文本之間的相似度就可以認為是該文本所對應的向量在空間上的接近程度，也就是向量之間的夾角，夾角越大那就越不接近反之就越接近。我們對兩個向量的余弦值進行計算，根據(jù)余弦值的大小來得出兩段文本的相似程度，按照式（4）就可以得出最終的sim值。 

20、9;åå= （4）其中，T1、T2代表待比較的兩個文本對應的向量，其中的i表示向量的第i維，n用來表示向量的維數(shù)。兩個向量的余弦值是一個大于等于0小于等于1的數(shù)，如果向量一致余弦值就是1，如果向量正交就是0，這一點也符合相似度必然屬于0到1這個區(qū)間的特性，0代表完全不同，1代表完全相同。由此我們就可以通過這個sim的值來對兩短文本的相似度進行判斷。4 算法測試與評估我們選取病歷這一特定文本進行測試，醫(yī)生在進行病理管理的過程中，需要進行相似病歷查找的時候，更為準確的方式是利用患者的主訴和初步診斷結果在病歷庫中進行搜索，查找出最為相近的病歷供醫(yī)生參考使用。為測試算法的實用性和準

21、確性，選取了以患者主訴和初步診斷為基本內容的測試文本作為實驗數(shù)據(jù)進行了實驗，并對實驗結果進行分析。Text作為實驗文本，Text1至Text5為測試文本分別與其進行相似度檢測。分詞前后結果分別如表4-1和表4-2所示。表4-1文本內容文本內容Text咳嗽已有半月多，加重時發(fā)熱伴有胸悶，呼吸困難，不能正常入睡，初步診斷為急性支氣管肺炎，若藥物治療效果不明顯建議盡快到醫(yī)院進行手術治療。Text1在檢查前2小時，我在行走時不慎被摩托車撞倒，局部皮膚青紫，皮膚無破損，明確外傷史致腰部、右大腿疼痛，初步診斷為腰骶部軟組織挫傷 右大腿軟組織挫傷。Text2畏寒、發(fā)熱伴咳嗽、咳痰多天，時常會呼吸困難，初步診

22、斷為右中、下肺肺炎，急性氣管-支氣管炎，建議盡快接受治療Text3我十余天前無誘因下出現(xiàn)左上腹部陣發(fā)性隱痛，進食后疼痛加劇，按壓后稍有緩解，初步診斷為胃癌伴幽門梗阻，建議盡快到醫(yī)院就診。Text4孩子由于受涼咳嗽三天，發(fā)熱兩天，有痰很難咳出，初步診斷為支氣管肺炎、佝僂病，建議盡快到醫(yī)院確診。Text5陣發(fā)性心前區(qū)疼痛，不適1年，加重3天，持續(xù)時間幾分鐘，伴有咳嗽，服藥后癥狀無緩解，初步診斷為冠心病。表4-2分詞結果分詞結果Text咳嗽/v, 、/w, 咳/e, 痰/n, 已/d, 有/v, 半月/m, 多/m, ，/w, 加重/v, 時/ng, 發(fā)熱/v, 伴/v, 有/v, 胸/ng, 悶/

23、v, ，/w, 呼吸/v, 困難/an, ，/w, 不能/v, 正常/a, 入睡/v, ，/w, 初步/d, 診斷/v, 為/p, 急性/b, 支氣管/n, 肺炎/n, ，/w, 若/c, 藥物/n, 治療/v, 效果/n, 不/d, 明顯/a, 建議/n, 盡快/d, 到/v, 醫(yī)院/n, 進行/v, 手術/v, 治療/v, 。/wText1在/p, 檢查/vn, 前/f, 2/m, 小時/n, ，/w, 我/r, 在/p, 行走/v, 時/ng, 不慎/d, 被/p, 摩托車/n, 撞/v, 倒/v, ，/w, 局部/n, 皮膚/n, 青/a, 紫/a, ，/w, 皮膚/n, 無/v, 破

24、損/v, ，/w, 明確/ad, 外傷/n, 史/ng, 致/v, 腰部/n, 、/w, 右/f, 大腿/n, 疼痛/an, ，/w, 初步/d, 診斷/v, 為/p, 腰/n, 骶, 部/q, 軟組織/n, 挫傷/v, /nr, 右/f, 大腿/n, 軟組織/n, 挫傷/v, 。/wText2畏/vg, 寒/ag, 、/w, 發(fā)熱/v, 伴/v, 咳嗽/v, 、/w, 咳/e, 痰/n, 多天/m, ，/w, 時常/d, 會/v, 呼吸/v, 困難/an, ，/w, 初步/d, 診斷/v, 為/p, 右/f, 中/f, 、/w, 下/f, 肺/n, 肺炎/n, ，/w, 急性/b, 氣管/n

25、, -, 支氣管炎/n, ，/w, 建議/n, 盡快/d, 接受/v, 治療/v, 。/wText3我/r, 十余天/m, 前/f, 無/v, 誘因/n, 下/f, 出現(xiàn)/v, 左上/f, 腹部/n, 陣/ng, 發(fā)/v, 性/ng, 隱痛/n, ，/w, 進食/v, 后/f, 疼痛/an, 加劇/v, ，/w, 按壓/v, 后/f, 稍/d, 有/v, 緩解/v, ，/w, 初步/d, 診斷/v, 為/p, 胃癌/n, 伴/v, 幽門/n, 梗阻/v, ，/w, 建議/n, 盡快/d, 到/v, 醫(yī)院/n, 就診/v, 。/wText4孩子/n, 由于/c, 受涼/v, 咳嗽/v, 三天/m

26、, ，/w, 發(fā)熱/v, 兩天/m, ，/w, 有/v, 痰/n, 很/d, 難/a, 咳/e, 出/v, ，/w, 初步/d, 診斷/v, 為/p, 支氣管/n, 肺炎/n, 、/w, 佝僂病/n, ，/w, 建議/n, 盡快/d, 到/v, 醫(yī)院/n, 確診/v, 。/wText5陣/ng, 發(fā)/v, 性/ng, 心/n, 前/f, 區(qū)/n, 疼痛/an, ，/w, 不適/a, 1年/m, ，/w, 加重/v, 3天/m, ，/w, 持續(xù)/vd, 時間/n, 幾分鐘/m, ，/w, 伴/v, 有/v, 咳嗽/v, ，/w, 服/v, 藥/n, 后/f, 癥狀/n, 無/v, 緩解/v, ，/w, 初步/d, 診斷/v, 為/p, 冠心病/n, 。/w由于不同文本之間詞條數(shù)量的差異，無法統(tǒng)一進行向量的生成，需要逐一地將測試文本同實驗文本進行相似度計算的處理。在進行數(shù)據(jù)降維，除去標點符號之后進