徐曉霖
摘要:
為了解決TextRank算法的初始值賦權(quán)問(wèn)題,提高關(guān)鍵詞抽取準(zhǔn)確率,引入LogLikelihood算法。通過(guò)與參考語(yǔ)料庫(kù)詞頻進(jìn)行對(duì)比,為詞條的初始權(quán)重賦值,將不需要外部語(yǔ)料的TextRank和需要外部語(yǔ)料的LogLikelihood進(jìn)行融合、計(jì)算。實(shí)驗(yàn)結(jié)果表明,融合后的TextRankLL算法優(yōu)于TextRank算法。
關(guān)鍵詞:
關(guān)鍵詞抽??;TextRank算法;LogLikelihood算法;TextRankLL算法;圖模型
DOIDOI:10.11907/rjdk.172527
中圖分類號(hào):TP312
文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào)文章編號(hào):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)為具有重要意義的短語(yǔ)或詞組。文本關(guān)鍵詞抽取是文本分析的前沿工作,對(duì)于后續(xù)文本相似度對(duì)比、文本語(yǔ)義理解等都具有十分重要的作用。所以,只有關(guān)鍵詞的抽取更加快速、準(zhǔn)確,才能提高文本分析等工作效率。文本關(guān)鍵詞抽取之前已進(jìn)行了大量研究,對(duì)不同的數(shù)學(xué)模型進(jìn)行組合可提高抽取準(zhǔn)確度[12]。目前對(duì)關(guān)鍵詞的抽取主要有兩類方法:有監(jiān)督和無(wú)監(jiān)督。
TFIDF算法是最經(jīng)典的關(guān)鍵詞抽取算法,簡(jiǎn)單、快速,且適用范圍廣。TFIDF即將TF與IDF相乘計(jì)算。TF詞頻指詞條在該文檔中出現(xiàn)的頻率,IDF逆向文件頻率指詞條在其它文檔中出現(xiàn)頻率的倒數(shù)。但TFIDF算法只能根據(jù)頻率劃分重要性,而未考慮詞條位置、詞條長(zhǎng)度、詞條上下文等。針對(duì)TFIDF算法的改進(jìn),學(xué)者們進(jìn)行了大量研究。如鄧丹君[3]提出特殊符號(hào)后權(quán)值加強(qiáng)的改進(jìn),對(duì)于特殊符號(hào)如@后表示提到的重點(diǎn)人,權(quán)值加重。該方法對(duì)于微博等文本提取算法提升較顯著,但不適用于所有文本。
TextRank[4]算法是無(wú)監(jiān)督關(guān)鍵詞抽取的經(jīng)典算法,是基于PageRank的文本關(guān)鍵詞抽取算法。PageRank將整個(gè)網(wǎng)絡(luò)假想成一張有向圖譜,各個(gè)網(wǎng)站A、B等是圖中的點(diǎn),如果存在A到B的鏈接,則在圖譜上畫一條A到B的有向線。而TextRank算法將PageRank中對(duì)網(wǎng)頁(yè)的計(jì)算改為對(duì)詞條的計(jì)算,但是TextRank算法有一個(gè)十分明顯的不足:詞語(yǔ)的初始權(quán)重設(shè)置為1,從而使每個(gè)詞條的重要性相同,但在每個(gè)句子中,不同詞條有著不同的重要程度。針對(duì)TextRank的不足,很多學(xué)者都提出改進(jìn)算法。夏天[5]提出了根據(jù)詞語(yǔ)位置不同、頻率不同等構(gòu)建影響率轉(zhuǎn)移矩陣與TextranK進(jìn)行融合;顧益軍[6]提出將LDA模型和Textrank算法進(jìn)行有效融合,當(dāng)數(shù)據(jù)集呈現(xiàn)較強(qiáng)的主題分布時(shí),可以顯著改善關(guān)鍵詞抽取效果。
因此,為了提高文本關(guān)鍵詞抽取效果,本文將Loglikelihood算法與TextRank算法相結(jié)合,對(duì)TextRank算法加以改進(jìn)。
1算法介紹
1.1LogLikelihood算法
對(duì)數(shù)似然比(LogLikelihood)是一種頻率差異檢測(cè)方法,是語(yǔ)料庫(kù)語(yǔ)言學(xué)研究中比較常用的統(tǒng)計(jì)檢測(cè)方法之一[78]。同一詞條在不同文章中出現(xiàn)頻率相同,也不能說(shuō)明該詞條對(duì)于兩篇文章的重要程度相同。對(duì)數(shù)似然比是指某詞條在文本總量為m1的文檔中出現(xiàn)頻率為k1,在文本總量為m2的文檔中出現(xiàn)頻率為k2,則兩個(gè)文本的分布不同(相同)。計(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)
對(duì)數(shù)似然比在語(yǔ)言學(xué)中有著很多應(yīng)用,設(shè)置觀察語(yǔ)料庫(kù)和參照語(yǔ)料庫(kù)。在關(guān)鍵詞抽取問(wèn)題上具體如下:觀察語(yǔ)料庫(kù)為想要抽取的關(guān)鍵詞文本,而參考語(yǔ)料庫(kù)則是一個(gè)足夠大的、與想要抽取的關(guān)鍵詞文本同一類型的文本。只有參考語(yǔ)料庫(kù)足夠大,語(yǔ)料庫(kù)里的詞條頻率在與觀察語(yǔ)料文本進(jìn)行對(duì)比時(shí)才會(huì)更加真實(shí)。當(dāng)觀察語(yǔ)料庫(kù)中的詞條頻率大于同類型參考語(yǔ)料庫(kù)中的該詞條頻率時(shí),說(shuō)明該詞條在該篇文章中相對(duì)于同類文章更加重要。
由于LL算法需要與外部語(yǔ)料庫(kù)進(jìn)行對(duì)比,因此可以和TextRank不需要外部語(yǔ)料庫(kù)的優(yōu)勢(shì)進(jìn)行互補(bǔ),從而更有效地提升現(xiàn)有算法的應(yīng)用效果。
1.2TextRank算法
TextRank一般模型可以表示為一個(gè)有向有權(quán)圖G=(V, E), 由點(diǎn)集合V和邊集合E組成,E是V×V的子集。圖中任兩點(diǎn)Vi、Vj之間邊的權(quán)重為wji,對(duì)于一個(gè)給定的點(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)得分時(shí),需要給圖中的點(diǎn)指定任意初值,并遞歸計(jì)算直到收斂,即圖中任意一點(diǎn)的誤差率小于給定的極限值時(shí)即可達(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)該不同,所以對(duì)兩點(diǎn)轉(zhuǎn)移概率即兩點(diǎn)間的有向?qū)嵕€進(jìn)行權(quán)值設(shè)置。
其中w代表轉(zhuǎn)移概率,兩個(gè)詞條之間的權(quán)重即代表跳轉(zhuǎn)概率,在這里通過(guò)似然對(duì)數(shù)比對(duì)詞條之間進(jìn)行權(quán)重賦值。如果LL值很高,說(shuō)明該詞條在本文出現(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è)置參考語(yǔ)料庫(kù)。參考語(yǔ)料庫(kù)最好是能夠與測(cè)試文本類型相同的大量語(yǔ)料,以計(jì)算出詞頻表。在這里使用兩種語(yǔ)料庫(kù)進(jìn)行對(duì)比,一種為《現(xiàn)代漢語(yǔ)語(yǔ)料庫(kù)分詞類詞頻表》,另一種為自己爬蟲的1 000篇相同類型的文獻(xiàn),進(jìn)行詞頻表計(jì)算。
(2)文本處理。使用jieba分詞工具對(duì)文本進(jìn)行處理,去除停止詞等不需要的詞匯,將文本分為詞條組,并統(tǒng)計(jì)每種詞條的頻率,以便于進(jìn)行LogLikelihood計(jì)算[11]。
(3)獲得參考語(yǔ)料庫(kù)詞頻以及觀察語(yǔ)料庫(kù)詞頻后通過(guò)公式(1)、(4)進(jìn)行計(jì)算,獲得權(quán)重。
(4)構(gòu)建加權(quán)的TextRank圖模型,通過(guò)公式(5)計(jì)算至收斂后進(jìn)行排序,獲得關(guān)鍵詞。
3實(shí)驗(yàn)分析
3.1實(shí)驗(yàn)數(shù)據(jù)來(lái)源
本實(shí)驗(yàn)選擇的實(shí)驗(yàn)數(shù)據(jù)為:①以搜狐新聞為目標(biāo),爬取1 000篇社會(huì)欄目新聞,并且包含關(guān)鍵詞,保存為xml格式。以此為參考語(yǔ)料庫(kù)進(jìn)行詞頻統(tǒng)計(jì),生成詞頻表。以相同欄目的100篇文章為測(cè)試語(yǔ)料庫(kù);②參考語(yǔ)料庫(kù)為《現(xiàn)代漢語(yǔ)語(yǔ)料庫(kù)分詞類詞頻表》。將兩種不同語(yǔ)料庫(kù)進(jìn)行對(duì)比,更能體現(xiàn)出語(yǔ)料庫(kù)的作用以及對(duì)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)主要是測(cè)試改進(jìn)后的算法對(duì)于TextRank算法是否有所提升。將從搜狐新聞爬取的1 000篇社會(huì)類新聞進(jìn)行語(yǔ)料庫(kù)生成,計(jì)算出頻率詞條集,用時(shí)30min。所爬取的文本所帶關(guān)鍵詞大多為3個(gè),即將關(guān)鍵詞的個(gè)數(shù)設(shè)置為3,選擇窗口大小為5。
目前關(guān)鍵詞抽取算法效果評(píng)判標(biāo)準(zhǔn)有準(zhǔn)確率P、召回率R以及F值,計(jì)算公式如下:
P=抽取結(jié)果中與文本自帶關(guān)鍵詞相同的個(gè)數(shù)文本自帶關(guān)鍵詞總數(shù)
R=抽取結(jié)果中與文本自帶關(guān)鍵詞相同的個(gè)數(shù)抽取關(guān)鍵詞總數(shù)
Fmeasure=2PR(P+R)
通過(guò)對(duì)100篇測(cè)試語(yǔ)料文本進(jìn)行抽取實(shí)驗(yàn),算法對(duì)比如圖3所示,對(duì)其進(jìn)行深入分析并得出如下結(jié)論:
TextRankLL算法對(duì)于TextRank算法有一定程度的改進(jìn),關(guān)鍵詞抽取準(zhǔn)確率得到提升。
以現(xiàn)代漢語(yǔ)分詞頻率表為參考預(yù)料庫(kù)的提升遠(yuǎn)小于以同類文本為基礎(chǔ)生成的文本詞頻表的提升,所以參考語(yǔ)料庫(kù)對(duì)于該改進(jìn)算法有一定影響,越是與測(cè)試語(yǔ)料庫(kù)同類的文本庫(kù)生成的詞頻表,對(duì)于TextRank的提升越多。
融合了LogLikelihood和TextRank算法的關(guān)鍵詞抽取即TextRankLL算法,便于Loglikelihood的參考語(yǔ)料庫(kù)與測(cè)試語(yǔ)料庫(kù)的詞頻對(duì)比,提升了抽取準(zhǔn)確率,但也存在一些不足,因此本文提出如下改進(jìn):①使用大量訓(xùn)練文檔進(jìn)行訓(xùn)練,從而使參考語(yǔ)料庫(kù)的詞條頻率表更加準(zhǔn)確;②訓(xùn)練文檔的選取能夠和測(cè)試文檔相關(guān),最好為同類,詞條頻率才會(huì)更加穩(wěn)定和準(zhǔn)確;③通過(guò)Hadoop集群計(jì)算提高速度。
綜上所述,融合了LogLikelihood算法和TextRank算法的文本關(guān)鍵詞抽取算法的主要優(yōu)勢(shì)是結(jié)合了前者需要和外部文檔進(jìn)行比較以及后者的獨(dú)立性,使其在準(zhǔn)確率、召回率、Fmeasure值上都有一定程度提高,但是提高不是很明顯,比較適合有大量同類型文本作參考語(yǔ)料庫(kù)時(shí)的文本關(guān)鍵詞抽取。同時(shí),其對(duì)于時(shí)間的消耗也有所上升。本文的結(jié)果以及算法對(duì)關(guān)鍵詞抽取技術(shù)的研究有一定借鑒意義,但仍有很大提升空間。
4結(jié)語(yǔ)
本文基于LogLikelihood算法進(jìn)行參考文本與觀察文本之間的詞頻關(guān)系計(jì)算,以改進(jìn)TextRank算法的詞條初始權(quán)重問(wèn)題。實(shí)驗(yàn)結(jié)果表明,參考語(yǔ)料庫(kù)文本的數(shù)量和類型對(duì)于準(zhǔn)確率等有一定影響,在提高抽取準(zhǔn)確率的同時(shí)也造成了時(shí)間消耗增加。所以,下一步的研究方向是如何確定更加合理的參考語(yǔ)料庫(kù)以及如何縮短時(shí)間。
參考文獻(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]夏天.詞語(yǔ)位置加權(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].北京:北京外國(guó)語(yǔ)大學(xué),2015.
[8]李國(guó)臣.文本分類中基于對(duì)數(shù)似然比測(cè)試的特征詞選擇方法[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ù)分析與知識(shí)發(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é)任編輯:黃?。?