基于改進的TF－IDF方法的文本相似度算法研究

周麗杰，于偉海，郭 成

(1.煙臺職業(yè)學院電教中心，山東煙臺 264670;2.煙臺市教育局，山東煙臺 264003;

3.大連理工大學軟件學院，遼寧大連 116620;4.煙臺職業(yè)學院成教處，山東煙臺 264670)

基于改進的TF－IDF方法的文本相似度算法研究

周麗杰1，于偉海2，4，郭 成3

(1.煙臺職業(yè)學院電教中心，山東煙臺 264670;2.煙臺市教育局，山東煙臺 264003;

3.大連理工大學軟件學院，遼寧大連 116620;4.煙臺職業(yè)學院成教處，山東煙臺 264670)

傳統(tǒng)的文本相似度算法采用關鍵詞頻率表示該關鍵詞在文檔中的重要程度，關鍵詞在類別內(nèi)不同文檔中的頻率波動使得關鍵詞的權值產(chǎn)生不穩(wěn)定性，導致文本之間的相似度運算不夠準確.本文提出一種基于詞語信息量的改進的TF－IDF算法計算關鍵詞的權值，將得到的權值運用于向量空間模型和馬爾可夫模型中，分別得到基于向量空間模型的基礎相似度和基于馬爾可夫模型的語義相似度，將語義相似度和基礎相似度相結(jié)合，得到文本之間總體相似度.將改進的文本相似度算法運用于文本分類，實驗結(jié)果表明，在搜狗文本分類語料庫基礎上，改進的算法相對于傳統(tǒng)的文本相似度算法使得文本分類的準確率有了較大地提高.

文本相似度算法;TF－IDF方法;詞語關聯(lián);馬爾可夫模型;文本分類

1 TF－IDF方法

當前，對文本中關鍵詞的權值計算主要采用TF－IDF方法［1］，TF表示關鍵詞在本文檔中出現(xiàn)的頻率，記為C;DF表示該文本在整個文檔集中出現(xiàn)的頻率，記為n;IDF表示的是反文檔頻率，記整個文檔集中文檔的數(shù)目是N，則IDF可表示為N/n.一般認為，關鍵詞在文檔中出現(xiàn)的次數(shù)越高，表明該關鍵詞在文檔中越重要;關鍵詞在文檔集出現(xiàn)的越頻繁，表明該關鍵詞對于文檔區(qū)分能力越小，對于關鍵詞i在文檔j中的權值計算方法如公式1所示.

公式1中，Ci表示關鍵詞i在文檔j中出現(xiàn)的次數(shù)，nj表示文檔j在文檔集中出現(xiàn)的次數(shù)，0.01是為了數(shù)據(jù)平滑.由TF－IDF的定義可知，類別內(nèi)不同文檔內(nèi)，關鍵詞的頻率不盡相同，會出現(xiàn)很大程度的波動現(xiàn)象，使得最終的關鍵詞權值缺乏穩(wěn)定性.

2 改進的文本相似度算法

對關鍵詞頻率波動進行改進，提出全局頻率的概念，對多個文本中的關鍵詞頻率進行平均化.將新的關鍵詞頻率運用于TF－IDF算法，通過余弦相似度法和馬爾可夫模型實現(xiàn)文本之間的相似度運算.

2.1 關鍵詞權值計算

由于TF－IDF方法中關鍵詞頻率的波動并隨之增大了文本特征選擇復雜性.基于此，文獻［5－6］提出對文檔中關鍵詞權值進行歸一化操作，依據(jù)文檔中所有關鍵詞的數(shù)量修正文檔中關鍵詞的權重，本文在此基礎上，綜合考慮各個文檔中關鍵詞的頻率以及文檔的長度信息，對頻率信息和長度信息進行平均化，提出一種詞語信息量的度量方法，得到改進的TF權重計算方法如公式2所示.

公式2中，C1表示該關鍵詞i在文檔r1中出現(xiàn)的次數(shù)，lr1表示該文檔r1的長度，t表示對應所屬類別中包含關鍵詞i的文檔數(shù)目，lr2表示文檔r2的長度，s表示該所屬類別中所包含文檔的數(shù)目.得到改進的關鍵詞權重計算公式如公式3所示.

2.2 語義相似度

根據(jù)馬爾可夫模型的理論基礎，將這一理論運用于文本表示當中，通過馬爾可夫鏈中各個狀態(tài)之間的狀態(tài)切換概率來表征文本中關鍵詞之間的跳轉(zhuǎn)概率，如圖1所示.

圖1中，S0→S12→S23→…→Sn4→SF表示的是一條馬爾可夫鏈，該鏈中各個狀態(tài)之間邊上的權值表示的是狀態(tài)之間的切換概率.文本相似度運算過程中，馬爾可夫鏈中各個狀態(tài)對應的是文本中各個關鍵詞，鏈中狀態(tài)之間的切換概率對應的是關鍵詞之間的跳轉(zhuǎn)概率.對于S0→S12→S23→…→Sn4→SF這條馬爾可夫鏈，S12→S23表示狀態(tài)S12所對應的關鍵詞后是S23，所對應的關鍵詞的概率是a13，計算方法為統(tǒng)計S23所對應的關鍵詞出現(xiàn)在S12所對應的關鍵詞之后的次數(shù).因此，馬爾可夫鏈中各個狀態(tài)之間的跳轉(zhuǎn)關系表示的是文本中關鍵詞的排列順序.

通過馬爾可夫模型中節(jié)點之間的跳轉(zhuǎn)概率以及模型中節(jié)點權值，得到文本之間語義相似度的計算方法如下所示.

圖1 文本中關鍵詞跳轉(zhuǎn)概率圖

Step1:基準文本采用馬爾可夫模型表示為Tb，表示為向量形式為Tb=(t1Tb，t2Tb，…，tnTb).

Step2:對于待測文本T=(t1T，t2T，…，tnT)，對任一關鍵詞tiT∈T，匹配是否在Tb中出現(xiàn)，如果匹配成功，得到匹配節(jié)點，匹配節(jié)點的權值為WtiT，如果匹配不成功，置節(jié)點權值為ε(ε為很小的數(shù))，如公式4所示.

Step3:通過匹配節(jié)點的權值和跳轉(zhuǎn)概率，得到文本之間語義相似度如公式5所示.

在公式4中，WtiT表示運用改進的TF－IDF方法獲得的關鍵詞tiT的權值.

在公式5中，WtiT表示關鍵詞tiT的權值，atiTti+1T表示關鍵詞tiT跳轉(zhuǎn)到關鍵詞t(i+1)T的概率，即關鍵詞t(i+1)T緊隨出現(xiàn)在關鍵詞tiT后的次數(shù).若沒有出現(xiàn)，則置為1.

2.3 文本總體相似度

通過改進的關鍵詞權重計算方法，對于待測文本T=(t1T，t2T，…，tnT)和基準文本Tb=(t1Tb，t2Tb，…，tnTb)，運用余弦向量法得到文本之間基礎相似度如公式6所示.

結(jié)合語義相似度和基礎相似度，得到文本之間總體相似度如公式7所示.

3 實驗與討論

將改進的文本相似度算法運用于文本分類，文本分類的語料庫采用搜狗中文文本分類語料庫，該語料庫中共有17910篇文檔，共分為9個類別，每個類別內(nèi)文檔數(shù)目為1990篇.采用中國科學院主持研發(fā)的ICTCLAS中文分詞工具，文本分類算法使用貝葉斯算法，(公式7)中參數(shù)α設置為0.4.

使用改進的TF－IDF算法計算關鍵詞權值，為每篇文本構建馬爾可夫模型，統(tǒng)計出各個關鍵詞之間的跳轉(zhuǎn)概率.分別從每個類別中選取70%的文本作為訓練數(shù)據(jù)，剩余30%文本作為測試數(shù)據(jù)［7－8］，文本經(jīng)過分詞之后，選取文本中70%關鍵詞用以表示文本，比較本文提出的算法與傳統(tǒng)的文本相似度算法在文本分類時不同的分類準確率，如圖2所示.

圖2 本文算法和傳統(tǒng)算法分類準確率比較圖

圖3 本文算法和傳統(tǒng)算法分類F1值比較圖

由圖2可知，相比于傳統(tǒng)文本相似度算法，本文算法使得文本分類的準確率有了較大提高，分類的準確率平均值保持在83.6%左右，而采用傳統(tǒng)算法在進行文本分類時，分類準確率平均值只有78.5%左右.

由圖3可知，相比于傳統(tǒng)文本相似度算法，本文算法使得文本分類的F1值有了較大提高，分類的F1平均值保持在82.5%左右，而采用傳統(tǒng)算法在進行文本分類時，分類F1值的平均值只有77.4%左右.

依次選取文本分詞之后文本中關鍵詞總數(shù)的50%，70%和85%，分別比較本文算法和傳統(tǒng)文本相似度算法在分類時的準確率，如圖4所示.

圖4 關鍵詞總數(shù)50%，70%和85%在分類時準確率

由圖4可知，當關鍵詞數(shù)目較少，為文本中關鍵詞總數(shù)50%時，傳統(tǒng)文本相似度算法在進行文本分類時的分類準確率平均值只有67%左右，而本文算法使得分類準確率平均值保持在76%附近;當選取文本中70%關鍵詞時，結(jié)果如圖2所示，選取關鍵詞數(shù)目從50%變成70%，傳統(tǒng)算法在分類的準確率提高了11%左右，本文算法分類時準確率提高了7%左右;當關鍵詞總數(shù)變成總數(shù)85%時，本文算法和傳統(tǒng)算法在進行分類時的準確率分別是85.6%和85.4%.

對實驗結(jié)果進行分析，當選取文本中關鍵詞總數(shù)較少(50%關鍵詞)時，傳統(tǒng)算法在進行文本分類時分類準確率較低，因為文本中特征項選取較少，對文本的表征能力不高，相比于本文算法，本文算法將文本中關鍵詞之間關聯(lián)性加以提取，待測試文本中與基準文本關鍵詞語義關聯(lián)相符合特征信息加以權值放大，在選取關鍵詞數(shù)目較少時，顯著地提高了分類的準確率，比傳統(tǒng)算法在分類時的準確率提高了9%左右;當選取關鍵詞的數(shù)目達到平衡狀態(tài)(70%關鍵詞)時，本文算法的優(yōu)越性顯得并非十分明顯，但是也使分類的準確率有了較大的提高，提高了5%左右;此時，接近飽和的關鍵詞數(shù)目已經(jīng)能夠比較全面的反映文本的特征信息，最后的實驗結(jié)果也說明了這一點，本文算法在分類時的準確率只比傳統(tǒng)算法提高了0.2%.因此，本文算法在特征項的數(shù)目選取較少時，能夠比較顯著的提高文本分類的準確率.

4 結(jié)束語

文本特征選擇有多種方式，TF－IDF方法是一種常用的方式，TF－IDF方法在計算關鍵詞權重時由于關鍵詞的頻率波動導致關鍵詞的權值出現(xiàn)不穩(wěn)定性，本文提出一種詞語信息量的方法，以全局頻率為依托，避免關鍵詞因在不同文檔的頻率不同而產(chǎn)生波動.將改進的關鍵詞權值計算方法運用于向量空間模型和馬爾可夫模型，有效地提高了文本相似度計算的準確率，從而提高了文本分類的準確率.下一步的工作應該是提高文本特征提取的效率、更準確的獲取關鍵詞之間的語義關聯(lián)，并對本文構建的馬爾可夫模型進行優(yōu)化，減小馬爾可夫模型的存儲空間，提高在關鍵詞匹配時的匹配效率.

［1］Yanhui Gu，Zhenglu Yang，Guandong Xu.Exploration on efficient similar sentences extraction［J］.World WideWeb，2014，17(4):595－626.

［2］許文杰，陳慶奎.基于余弦向量法的web數(shù)據(jù)并行抓取系統(tǒng)［J］.計算機工程，2009，35(7):64－68.

［3］Koby Crammer，Mark Dredze，F(xiàn)ernando Pereira.Confidence－Weighted Linear Classification for Text Categorization［J］.Journal of Machine Learning Research，2012(13):1891－1926.

［4］華秀麗，朱巧明，李培峰.語義分析與詞頻統(tǒng)計相結(jié)合的中文文本相似度量方法研究［J］.計算機應用研究，2012，29(3):833－837.

［5］廖一星，潘學增.面向不平衡文本的特征選擇方法［J］.電子科技大學學報，2012，41(4):592－596.

［6］褚蕾蕾，常文波，李秦.文本聚類中改進特征權重算法［J］.工程數(shù)學學報，2012，29(4):523－529.

［7］李秦.文本聚類中改進特征權重算法［J］.工程數(shù)學學報，2012，29(4):523－529.

［8］李侃，周世斌，劉玉樹.統(tǒng)計流形擴散核的文本分類方法［J］.模式識別與人工智能，2012，25(2):339－345.

Research on Text Sim ilarity Algorithm Based on Improved TF－IDF Strategy

ZHOU Li－jie1，YUWei－h(huán)ai2，4，GUO Cheng3
(1.Electronic Teaching Center，Yantai Vocational College，Yantai，264670; 2.Yantai Bureau of Education，Yantai，264003; 3.School of Software Technology，Dalian University of Technology，Dalian，116620; 4.Department of Adult Education，Yantai Vocational College，Yantai，264670，China)

Traditional text similarity algorithm uses term＇s frequency to show the importance of the term in a document，the continuously changing frequency of a term in different documentswhich has common category makes the term＇sweightunstable，causing a low precision rate of text similarity calculation.We propose an improved TF－IDF strategy based on term＇s information capacity to calculate the term＇sweight，the obtained term＇sweight is used in vector spacemodel and Markovmodel to acquire the fundamental similarity based on vector spacemodel and semantic similarity based on Markovmodel，combining similarity and semantic similarity，the overall similarity between texts is got by combining fundamental similarity and semantic similarity.The experimental results on an open benchmark datasets from Sogou show our proposed approach can improve the accuracy and F1 performance of classification compared to traditional approach.

text similarity algorithm;TF－IDF strategy;word－relation;Markovmodel;text categorization

TP391

A

1672－2590(2015)03－0018－05

文本相似度的研究已經(jīng)運用于許多的自然語言處理應用當中［1］，傳統(tǒng)的文本相似度算法采用關鍵詞頻率表示關鍵詞在文檔中的重要程度，關鍵詞在多個文本中頻率的波動導致關鍵詞的權值產(chǎn)生不穩(wěn)定性，同時也增大了TF－IDF(term frequency－inverse document frequency)方法進行特征抽取時的開銷;采用向量空間模型［2］來表示文本，割裂了文本中關鍵詞之間的關聯(lián).因此，得到的文本之間的相似度不夠準確.研究并發(fā)現(xiàn)一種文本的有效處理策略、提取出文本潛在的語義信息資源非常必要.

Koby Crammer等人將自然語言處理中的統(tǒng)計方法引入，提出一種置信度加權的學習策略，并利用高斯分布來更新文本向量中元素的權值因子，試圖讓向量空間模型能夠更加準確的反映文本，然而，文本中關鍵詞之間關聯(lián)性依然被忽略［3］;文獻［4］提出根據(jù)表征文本特征的關鍵詞的詞頻信息和語義特征來對文本之間的相似度進行度量，然而關鍵詞的詞頻波動信息并未考慮，語義特征中也未包含關鍵詞的詞序關系;文獻將文本中關鍵詞組織成圖的形式，通過文本之間共有關鍵詞，建立文本中其它關鍵詞之間的關聯(lián)，這種方式導致很多完全無關的關鍵詞通過共有關鍵詞建立了聯(lián)系.通過對大量文獻的研究，關鍵詞頻率波動會對文本的特征選擇產(chǎn)生較大影響，關鍵詞之間的詞序關系包含了文本中豐富的信息，對于進一步提高文本之間相似度運算的準確性至關重要.

本文提出一種改進的文本相似度計算方法，為了克服關鍵詞頻率的波動，提出一種全局關鍵詞頻率的方法，將類別內(nèi)多個文檔中的頻率值做平均化，將獲得的關鍵詞頻率值采用TF－IDF方法計算關鍵詞權值.將得到的關鍵詞權值分別作為向量空間模型中元素值和馬爾可夫模型中的節(jié)點權值，向量空間模型采用余弦相似度法得到文本之間基礎相似度，馬爾可夫模型可以體現(xiàn)文本中關鍵詞之間關聯(lián)性，得到文本之間的語義相似度，將基礎相似度和語義相似度相結(jié)合，得到文本之間總體相似度.

2015－03－23

國家自然科學基金資助項目(61401060;61272173);山東省高等學?？萍加媱澔鹳Y助項目(J12LN73)

周麗杰(1976－)，女，山東龍口人，煙臺職業(yè)學院電教中心實驗師.