周麗杰，于偉海，郭 成

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

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

基于改進(jìn)的TF－IDF方法的文本相似度算法研究

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

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

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

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

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

1 TF－IDF方法

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

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

2 改進(jìn)的文本相似度算法

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

2.1 關(guān)鍵詞權(quán)值計(jì)算

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

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

2.2 語義相似度

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

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

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

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

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

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

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

在公式4中，WtiT表示運(yùn)用改進(jìn)的TF－IDF方法獲得的關(guān)鍵詞tiT的權(quán)值.

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

2.3 文本總體相似度

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

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

3 實(shí)驗(yàn)與討論

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

［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］.計(jì)算機(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)計(jì)相結(jié)合的中文文本相似度量方法研究［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(3):833－837.

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

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

［7］李秦.文本聚類中改進(jìn)特征權(quán)重算法［J］.工程數(shù)學(xué)學(xué)報(bào)，2012，29(4):523－529.

［8］李侃，周世斌，劉玉樹.統(tǒng)計(jì)流形擴(kuò)散核的文本分類方法［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)運(yùn)用于許多的自然語言處理應(yīng)用當(dāng)中［1］，傳統(tǒng)的文本相似度算法采用關(guān)鍵詞頻率表示關(guān)鍵詞在文檔中的重要程度，關(guān)鍵詞在多個(gè)文本中頻率的波動(dòng)導(dǎo)致關(guān)鍵詞的權(quán)值產(chǎn)生不穩(wěn)定性，同時(shí)也增大了TF－IDF(term frequency－inverse document frequency)方法進(jìn)行特征抽取時(shí)的開銷;采用向量空間模型［2］來表示文本，割裂了文本中關(guān)鍵詞之間的關(guān)聯(lián).因此，得到的文本之間的相似度不夠準(zhǔn)確.研究并發(fā)現(xiàn)一種文本的有效處理策略、提取出文本潛在的語義信息資源非常必要.

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

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

2015－03－23

國家自然科學(xué)基金資助項(xiàng)目(61401060;61272173);山東省高等學(xué)?？萍加?jì)劃基金資助項(xiàng)目(J12LN73)

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