徐曉霖
摘要:
為了解決TextRank算法的初始值賦權(quán)問題,提高關(guān)鍵詞抽取準(zhǔn)確率,引入LogLikelihood算法。通過與參考語料庫詞頻進(jìn)行對比,為詞條的初始權(quán)重賦值,將不需要外部語料的TextRank和需要外部語料的LogLikelihood進(jìn)行融合、計(jì)算。實(shí)驗(yàn)結(jié)果表明,融合后的TextRankLL算法優(yōu)于TextRank算法。
關(guān)鍵詞:
關(guān)鍵詞抽??;TextRank算法;LogLikelihood算法;TextRankLL算法;圖模型
DOIDOI:10.11907/rjdk.172527
中圖分類號:TP312
文獻(xiàn)標(biāo)識碼:A文章編號文章編號:16727800(2018)003008703
英文摘要Abstract:In order to solve the initial value of TextRank algorithm, we can improve the accuracy of keyword extraction. The LogLikelihood algorithm is introduced to compute the initial weight of the term by comparing with the observed word frequency of the corpus. The TextRank without external corpus and the LogLikelihood which requires external corpus are merged and calculated. Experimental results show that the fusion TextRankLL algorithm is superior to the TextRank algorithm.
英文關(guān)鍵詞Key Words:keyword extraction;TextRank;LogLikelihood;TextRankLL;graph model
0引言
文本關(guān)鍵詞抽取是指從文本中快速提取出使用者認(rèn)為具有重要意義的短語或詞組。文本關(guān)鍵詞抽取是文本分析的前沿工作,對于后續(xù)文本相似度對比、文本語義理解等都具有十分重要的作用。所以,只有關(guān)鍵詞的抽取更加快速、準(zhǔn)確,才能提高文本分析等工作效率。文本關(guān)鍵詞抽取之前已進(jìn)行了大量研究,對不同的數(shù)學(xué)模型進(jìn)行組合可提高抽取準(zhǔn)確度[12]。目前對關(guān)鍵詞的抽取主要有兩類方法:有監(jiān)督和無監(jiān)督。
TFIDF算法是最經(jīng)典的關(guān)鍵詞抽取算法,簡單、快速,且適用范圍廣。TFIDF即將TF與IDF相乘計(jì)算。TF詞頻指詞條在該文檔中出現(xiàn)的頻率,IDF逆向文件頻率指詞條在其它文檔中出現(xiàn)頻率的倒數(shù)。但TFIDF算法只能根據(jù)頻率劃分重要性,而未考慮詞條位置、詞條長度、詞條上下文等。針對TFIDF算法的改進(jìn),學(xué)者們進(jìn)行了大量研究。如鄧丹君[3]提出特殊符號后權(quán)值加強(qiáng)的改進(jìn),對于特殊符號如@后表示提到的重點(diǎn)人,權(quán)值加重。該方法對于微博等文本提取算法提升較顯著,但不適用于所有文本。
TextRank[4]算法是無監(jiān)督關(guān)鍵詞抽取的經(jīng)典算法,是基于PageRank的文本關(guān)鍵詞抽取算法。PageRank將整個網(wǎng)絡(luò)假想成一張有向圖譜,各個網(wǎng)站A、B等是圖中的點(diǎn),如果存在A到B的鏈接,則在圖譜上畫一條A到B的有向線。而TextRank算法將PageRank中對網(wǎng)頁的計(jì)算改為對詞條的計(jì)算,但是TextRank算法有一個十分明顯的不足:詞語的初始權(quán)重設(shè)置為1,從而使每個詞條的重要性相同,但在每個句子中,不同詞條有著不同的重要程度。針對TextRank的不足,很多學(xué)者都提出改進(jìn)算法。夏天[5]提出了根據(jù)詞語位置不同、頻率不同等構(gòu)建影響率轉(zhuǎn)移矩陣與TextranK進(jìn)行融合;顧益軍[6]提出將LDA模型和Textrank算法進(jìn)行有效融合,當(dāng)數(shù)據(jù)集呈現(xiàn)較強(qiáng)的主題分布時,可以顯著改善關(guān)鍵詞抽取效果。
因此,為了提高文本關(guān)鍵詞抽取效果,本文將Loglikelihood算法與TextRank算法相結(jié)合,對TextRank算法加以改進(jìn)。
1算法介紹
1.1LogLikelihood算法
對數(shù)似然比(LogLikelihood)是一種頻率差異檢測方法,是語料庫語言學(xué)研究中比較常用的統(tǒng)計(jì)檢測方法之一[78]。同一詞條在不同文章中出現(xiàn)頻率相同,也不能說明該詞條對于兩篇文章的重要程度相同。對數(shù)似然比是指某詞條在文本總量為m1的文檔中出現(xiàn)頻率為k1,在文本總量為m2的文檔中出現(xiàn)頻率為k2,則兩個文本的分布不同(相同)。計(jì)算公式為:
LL=logL(p1,k1,m1)L(p2,k2,m2)L(p1,k1,m1)L(p2,k2,m2)(1)
pi=kimi,p=(k1+k2)(m1+m2),L(p,k,n)=pk(1-p)m-k(2)
對數(shù)似然比在語言學(xué)中有著很多應(yīng)用,設(shè)置觀察語料庫和參照語料庫。在關(guān)鍵詞抽取問題上具體如下:觀察語料庫為想要抽取的關(guān)鍵詞文本,而參考語料庫則是一個足夠大的、與想要抽取的關(guān)鍵詞文本同一類型的文本。只有參考語料庫足夠大,語料庫里的詞條頻率在與觀察語料文本進(jìn)行對比時才會更加真實(shí)。當(dāng)觀察語料庫中的詞條頻率大于同類型參考語料庫中的該詞條頻率時,說明該詞條在該篇文章中相對于同類文章更加重要。
由于LL算法需要與外部語料庫進(jìn)行對比,因此可以和TextRank不需要外部語料庫的優(yōu)勢進(jìn)行互補(bǔ),從而更有效地提升現(xiàn)有算法的應(yīng)用效果。
1.2TextRank算法
TextRank一般模型可以表示為一個有向有權(quán)圖G=(V, E), 由點(diǎn)集合V和邊集合E組成,E是V×V的子集。圖中任兩點(diǎn)Vi、Vj之間邊的權(quán)重為wji,對于一個給定的點(diǎn)Vi,In(Vi)為指向該點(diǎn)的點(diǎn)集合,Out(Vi)為點(diǎn)Vi指向的點(diǎn)集合。點(diǎn)Vi的得分定義如下:
S(Vi)=(1-d)+d×∑j∈In(Vj)1|Out(Vj)|S(Vj)(3)
其中,d為阻尼系數(shù),取值范圍為0~1,代表從圖中某一特定點(diǎn)指向其它任意點(diǎn)的概率,一般取值為0.85。上述公式表示當(dāng)前節(jié)點(diǎn)Vi的值為:所有指向Vi的節(jié)點(diǎn)Vj給予的值的和。使用TextRank算法計(jì)算圖中各點(diǎn)得分時,需要給圖中的點(diǎn)指定任意初值,并遞歸計(jì)算直到收斂,即圖中任意一點(diǎn)的誤差率小于給定的極限值時即可達(dá)到收斂,一般該極限值取0.000 1。
2算法描述
Textrank的初始權(quán)值都為1,如圖1所示。由節(jié)點(diǎn)A到達(dá)其它節(jié)點(diǎn)的轉(zhuǎn)移概率相同,但是其它節(jié)點(diǎn)在文章中的重要性不同,所以轉(zhuǎn)移概率也應(yīng)該不同,所以對兩點(diǎn)轉(zhuǎn)移概率即兩點(diǎn)間的有向?qū)嵕€進(jìn)行權(quán)值設(shè)置。
其中w代表轉(zhuǎn)移概率,兩個詞條之間的權(quán)重即代表跳轉(zhuǎn)概率,在這里通過似然對數(shù)比對詞條之間進(jìn)行權(quán)重賦值。如果LL值很高,說明該詞條在本文出現(xiàn)的頻率遠(yuǎn)高于同類文本中該詞條出現(xiàn)的頻率,則該詞條越重要。參考張莉婧[9]和夏天[10]的賦值方法,用Loglikelihood進(jìn)行權(quán)值計(jì)算如下:
Wi=LLiLLmax(4)
將權(quán)值公式(4)帶入公式(3)后,新的計(jì)算公式為:
S(Vi)=(1-d)*LLiLLmax+d*LLiLLmax∑Vi∈Out(Vj)
Wij∑Vi∈Out(Vj)WjkS(Vi)(5)
算法具體實(shí)現(xiàn)如下:
(1)設(shè)置參考語料庫。參考語料庫最好是能夠與測試文本類型相同的大量語料,以計(jì)算出詞頻表。在這里使用兩種語料庫進(jìn)行對比,一種為《現(xiàn)代漢語語料庫分詞類詞頻表》,另一種為自己爬蟲的1 000篇相同類型的文獻(xiàn),進(jìn)行詞頻表計(jì)算。
(2)文本處理。使用jieba分詞工具對文本進(jìn)行處理,去除停止詞等不需要的詞匯,將文本分為詞條組,并統(tǒng)計(jì)每種詞條的頻率,以便于進(jìn)行LogLikelihood計(jì)算[11]。
(3)獲得參考語料庫詞頻以及觀察語料庫詞頻后通過公式(1)、(4)進(jìn)行計(jì)算,獲得權(quán)重。
(4)構(gòu)建加權(quán)的TextRank圖模型,通過公式(5)計(jì)算至收斂后進(jìn)行排序,獲得關(guān)鍵詞。
3實(shí)驗(yàn)分析
3.1實(shí)驗(yàn)數(shù)據(jù)來源
本實(shí)驗(yàn)選擇的實(shí)驗(yàn)數(shù)據(jù)為:①以搜狐新聞為目標(biāo),爬取1 000篇社會欄目新聞,并且包含關(guān)鍵詞,保存為xml格式。以此為參考語料庫進(jìn)行詞頻統(tǒng)計(jì),生成詞頻表。以相同欄目的100篇文章為測試語料庫;②參考語料庫為《現(xiàn)代漢語語料庫分詞類詞頻表》。將兩種不同語料庫進(jìn)行對比,更能體現(xiàn)出語料庫的作用以及對TextRank算法的提升。
3.2實(shí)驗(yàn)環(huán)境
融合LogLikelihood和TextRank算法的關(guān)鍵詞抽取算法使用Python2.7實(shí)現(xiàn),分詞以及頻率的統(tǒng)計(jì)采用jieba分詞工具,利用Python2.7實(shí)現(xiàn)。jieba分詞工具準(zhǔn)確率高、速度快。使用Macbook pro機(jī)器,內(nèi)存16G,系統(tǒng)為OS。
3.3實(shí)驗(yàn)結(jié)果
實(shí)驗(yàn)主要是測試改進(jìn)后的算法對于TextRank算法是否有所提升。將從搜狐新聞爬取的1 000篇社會類新聞進(jìn)行語料庫生成,計(jì)算出頻率詞條集,用時30min。所爬取的文本所帶關(guān)鍵詞大多為3個,即將關(guān)鍵詞的個數(shù)設(shè)置為3,選擇窗口大小為5。
目前關(guān)鍵詞抽取算法效果評判標(biāo)準(zhǔn)有準(zhǔn)確率P、召回率R以及F值,計(jì)算公式如下:
P=抽取結(jié)果中與文本自帶關(guān)鍵詞相同的個數(shù)文本自帶關(guān)鍵詞總數(shù)
R=抽取結(jié)果中與文本自帶關(guān)鍵詞相同的個數(shù)抽取關(guān)鍵詞總數(shù)
Fmeasure=2PR(P+R)
通過對100篇測試語料文本進(jìn)行抽取實(shí)驗(yàn),算法對比如圖3所示,對其進(jìn)行深入分析并得出如下結(jié)論:
TextRankLL算法對于TextRank算法有一定程度的改進(jìn),關(guān)鍵詞抽取準(zhǔn)確率得到提升。
以現(xiàn)代漢語分詞頻率表為參考預(yù)料庫的提升遠(yuǎn)小于以同類文本為基礎(chǔ)生成的文本詞頻表的提升,所以參考語料庫對于該改進(jìn)算法有一定影響,越是與測試語料庫同類的文本庫生成的詞頻表,對于TextRank的提升越多。
融合了LogLikelihood和TextRank算法的關(guān)鍵詞抽取即TextRankLL算法,便于Loglikelihood的參考語料庫與測試語料庫的詞頻對比,提升了抽取準(zhǔn)確率,但也存在一些不足,因此本文提出如下改進(jìn):①使用大量訓(xùn)練文檔進(jìn)行訓(xùn)練,從而使參考語料庫的詞條頻率表更加準(zhǔn)確;②訓(xùn)練文檔的選取能夠和測試文檔相關(guān),最好為同類,詞條頻率才會更加穩(wěn)定和準(zhǔn)確;③通過Hadoop集群計(jì)算提高速度。
綜上所述,融合了LogLikelihood算法和TextRank算法的文本關(guān)鍵詞抽取算法的主要優(yōu)勢是結(jié)合了前者需要和外部文檔進(jìn)行比較以及后者的獨(dú)立性,使其在準(zhǔn)確率、召回率、Fmeasure值上都有一定程度提高,但是提高不是很明顯,比較適合有大量同類型文本作參考語料庫時的文本關(guān)鍵詞抽取。同時,其對于時間的消耗也有所上升。本文的結(jié)果以及算法對關(guān)鍵詞抽取技術(shù)的研究有一定借鑒意義,但仍有很大提升空間。
4結(jié)語
本文基于LogLikelihood算法進(jìn)行參考文本與觀察文本之間的詞頻關(guān)系計(jì)算,以改進(jìn)TextRank算法的詞條初始權(quán)重問題。實(shí)驗(yàn)結(jié)果表明,參考語料庫文本的數(shù)量和類型對于準(zhǔn)確率等有一定影響,在提高抽取準(zhǔn)確率的同時也造成了時間消耗增加。所以,下一步的研究方向是如何確定更加合理的參考語料庫以及如何縮短時間。
參考文獻(xiàn)參考文獻(xiàn):
[1]MIHALCEA R, TARAU P. TextRank: bringing order into texts[C].Conference on Empirical Methods in Natural Language Processing, EMNLP, 2004:404411.
[2]FRANK E, PAYNTER G W, WITTEN I H, et al. Domainspecific keyphrase extraction[C]. ACM CIKM International Conference on Information and Knowledge Management, Bremen, Germany,1999:283284.
[3]鄧丹君,姚莉.基于改進(jìn)TFIDF的微博短文本特征詞提取算法[J].軟件導(dǎo)刊,2016,15(6):4850.
[4]MIHALCEA R, TARAU P. TextRank: bringing order into texts[J]. Unt Scholarly Works, 2004:404411.
[5]夏天.詞語位置加權(quán)TextRank的關(guān)鍵詞抽取研究[J].現(xiàn)代圖書情報(bào)技術(shù),2013,29(9):3034.
[6]顧益軍.融合LDA與TextRank的關(guān)鍵詞抽取研究[J].現(xiàn)代圖書情報(bào)技術(shù),2014,30(7):4147.
[7]姬弘飛.基于TextRank與LogLikelihood的Chrome瀏覽器中文詞云插件的設(shè)計(jì)與開發(fā)[D].北京:北京外國語大學(xué),2015.
[8]李國臣.文本分類中基于對數(shù)似然比測試的特征詞選擇方法[J].中文信息學(xué)報(bào),1999,13(4):1722.
[9]張莉婧,李業(yè)麗,曾慶濤,等.基于改進(jìn)TextRank的關(guān)鍵詞抽取算法[J].北京印刷學(xué)院學(xué)報(bào),2016,24(4):5155.
[10]夏天.詞向量聚類加權(quán)TextRank的關(guān)鍵詞抽取[J].數(shù)據(jù)分析與知識發(fā)現(xiàn),2017(2):2834.
[11]MIKOLOV T, CHEN K, CORRADO G, et al. Efficient estimation of word representations in vector space[J]. Computer Science, 2013.
責(zé)任編輯(責(zé)任編輯:黃?。?