結(jié)合拓?fù)鋭菖cTextRank算法的關(guān)鍵詞提取方法

羅婉麗 張 磊

1(四川旅游學(xué)院信息與工程學(xué)院 四川 成都 610199) 2(四川省農(nóng)村信用聯(lián)合社 四川 成都 610041)

0 引 言

網(wǎng)絡(luò)文本數(shù)據(jù)呈爆炸式增長，且呈現(xiàn)出隨機(jī)性、模糊性及網(wǎng)絡(luò)化的特點(diǎn)。關(guān)鍵詞作為表達(dá)文本核心意義的最小單位，以凝練簡潔的形式對文本主題進(jìn)行有效概括，能幫助人們快速地把握文檔主題及內(nèi)容[1]，對關(guān)鍵詞進(jìn)行提取在信息檢索、情感分析及輿情分析等領(lǐng)域發(fā)揮著重要作用?，F(xiàn)在主要的關(guān)鍵詞提取算法有TF-IDF、TextRank、LDA等，其中TextRank算法以思想簡單、語言弱相關(guān)、適用于單文本及多文本等優(yōu)點(diǎn)得到廣泛應(yīng)用，但也存在忽略詞語間影響力、句子位置、文檔整體結(jié)構(gòu)等諸多不足[2]。針對TextRank算法的不足改進(jìn)，大量學(xué)者做了相關(guān)研究。

國內(nèi)文獻(xiàn)對TextRank算法的研究多集中在特征整合、轉(zhuǎn)移概率矩陣改進(jìn)等方面。李航等[3]考慮詞語平均信息熵、詞性及詞語位置三大特征，通過神經(jīng)網(wǎng)絡(luò)訓(xùn)練優(yōu)化三個(gè)特征的權(quán)重分配以完成特征融合，使用融合的特征改進(jìn)TextRank算法的詞語初始權(quán)重及概率轉(zhuǎn)移矩陣，提高了提取準(zhǔn)確率；周錦章等[4]針對詞匯語義差異對TextRank算法的影響，利用FastText將文檔集進(jìn)行詞向量表示，以詞語間的角余弦位距為基礎(chǔ)構(gòu)建轉(zhuǎn)移概率矩陣后進(jìn)行迭代計(jì)算和關(guān)鍵詞抽取，取得較好的實(shí)驗(yàn)結(jié)果；劉竹辰等[5]使用詞語覆蓋范圍、詞語位置、詞頻綜合加權(quán)作為詞語位置分布權(quán)值，計(jì)算概率轉(zhuǎn)移矩陣并迭代得到候選關(guān)鍵詞評分，改進(jìn)的方法取得了不錯(cuò)的效果；余珊珊等[6]將句子與標(biāo)題相似度、特殊段落中句子位置、關(guān)鍵句子、特殊句子權(quán)重、句子長度等因素加入TextRank網(wǎng)絡(luò)圖構(gòu)造中，提出了iTextRank方法且實(shí)驗(yàn)證明該方法較經(jīng)典的TextRank算法有更高準(zhǔn)確率及更低召回率。

國外文獻(xiàn)關(guān)于TextRank算法的研究則以與其他方法結(jié)合提高準(zhǔn)確率和應(yīng)用創(chuàng)新為主線。Mallick[7]以句子為節(jié)點(diǎn)，句子間相似度作為句子間邊權(quán)值來構(gòu)造圖，使用修改后的逆句子頻率對句子中的詞賦權(quán)值，并基于一個(gè)簇內(nèi)的句子彼此相似、不同簇內(nèi)的句子各不相同的假設(shè)，對圖進(jìn)行稀疏處理并劃分為不同的簇以生成文本摘要；Ashari等[8]利用TextRank算法、語義網(wǎng)絡(luò)及語料庫統(tǒng)計(jì)構(gòu)建文檔匯總系統(tǒng)，其中使用TextRank提取文檔的主要短語并形成句子作為摘要的輸出，這一過程由標(biāo)記化語句、圖的建立、使用語義網(wǎng)絡(luò)和語料庫統(tǒng)計(jì)的連接邊值計(jì)算、頂點(diǎn)值計(jì)算、排序頂點(diǎn)值以及摘要的創(chuàng)建等子過程組成，使用ROUGE-N方法計(jì)算總結(jié)的召回率、準(zhǔn)確度和F-Score來測量系統(tǒng)輸出的質(zhì)量；Zhang等[9]從語料中選取與某種子詞集語義相關(guān)的詞語或與主題相關(guān)但在目標(biāo)語料中未明確表述出來的詞組成子集，使用改進(jìn)的TextRank構(gòu)建詞圖模型并計(jì)算語料分?jǐn)?shù)給每個(gè)詞，用這些分?jǐn)?shù)修改ATE計(jì)算出的分?jǐn)?shù)；Petasis等[10]以檢查摘要提取和觀點(diǎn)挖掘間是否有重疊以及摘要提取方法是否對觀點(diǎn)挖掘任務(wù)有積極影響為動(dòng)機(jī)，將無監(jiān)督摘要提取方法TextRank應(yīng)用于觀點(diǎn)組成識別任務(wù)，在兩個(gè)數(shù)據(jù)集上進(jìn)行驗(yàn)證得出基于圖的方法對觀點(diǎn)挖掘會(huì)產(chǎn)生積極的影響；Barrios等[11]針對自動(dòng)摘要提取時(shí)TextRank算法僅根據(jù)兩個(gè)句子共享的內(nèi)容來確定相似關(guān)系，提出一種新的相似度函數(shù)來計(jì)算邊的權(quán)值，再使用PageRank計(jì)算各頂點(diǎn)的重要性挑選出最重要的句子，按句子在文中出現(xiàn)的順序形成摘要。

針對上述問題，本文考慮詞語詞頻及分布情況作為詞語“全局”重要性，在句子范圍內(nèi)結(jié)合拓?fù)鋭堇碚摳倪M(jìn)轉(zhuǎn)移概率矩陣，提出結(jié)合拓?fù)鋭菖cTextRank的關(guān)鍵詞提取方法(Topology Potential Combined TextRank,TPC-TextRank)。實(shí)驗(yàn)表明該方法能有效提高關(guān)鍵詞提取準(zhǔn)確率和召回率。

1 TextRank算法

Mihalcea等[12]提出的TextRank算法主要應(yīng)用于提取關(guān)鍵詞和自動(dòng)摘要生成，其提取關(guān)鍵詞的基本思想為：利用詞在窗口范圍內(nèi)的共現(xiàn)關(guān)系構(gòu)造詞項(xiàng)連接圖，用鄰居詞向當(dāng)前詞的連接表達(dá)投票關(guān)系，連接條數(shù)反映邊的權(quán)重，再通過公式迭代計(jì)算詞語重要性直至收斂，最后將詞語按重要性逆序并選擇排名高的若干詞作為關(guān)鍵詞。假設(shè)有一篇文檔D，需經(jīng)過以下步驟來實(shí)現(xiàn)TextRank算法：

(1)句子劃分。將文檔按句子劃分并對句子編號，即：D={s1,s2,…，sm}。

(2)預(yù)處理。該過程包括兩個(gè)步驟：① 用分詞工具進(jìn)行分詞，即si={wi1,wi2,…,win}；② 詞性標(biāo)注并保留特定詞性的詞，如名詞、動(dòng)詞、形容詞。

(3)詞項(xiàng)圖構(gòu)建。選定窗口大小為N，設(shè)詞win在句子si中的位置表示為index(win)，若|index(wia)-index(wib)|≤N，則認(rèn)為詞wia和詞wib存在連接邊。Mihalcea指出：句子是按一定結(jié)構(gòu)組成的，沒有十分“自然”的指向關(guān)系來描述詞之間的連接關(guān)系。實(shí)驗(yàn)也表明無論詞之間的指向如何，有向圖的提取效果均低于無向圖的提取結(jié)果。因此TextRank算法提取關(guān)鍵詞時(shí)構(gòu)造的是無向圖。

(4)詞語重要性計(jì)算。Mihalcea提出的原始Text-Rank算法迭代公式為：

(1)

式中：WS(Vi)表示詞語Vi的權(quán)重值；d為阻尼系數(shù)，表示保證某一詞跳到相鄰詞的概率，(1-d)則表示跳到一個(gè)新詞的概率，常取d=0.85；In(Vi)表示指向Vi的詞語集合；Out(Vj)表示Vj所指向的詞語集合；wji表示兩個(gè)詞連接邊間的權(quán)重。但算法應(yīng)用于關(guān)鍵詞提取時(shí)構(gòu)造的是無權(quán)邊模型，公式變?yōu)椋?/p>

(2)

根據(jù)式(2)迭代計(jì)算詞語的重要性直至收斂，一般當(dāng)兩次迭代結(jié)果差別非常小時(shí)(如：兩次結(jié)果差值小于0.000 1)則認(rèn)為算法結(jié)束。

(5)將詞語按重要性逆序排列并選擇Top-K個(gè)詞作為文檔關(guān)鍵詞。

2 結(jié)合拓?fù)鋭菖cTextRank算法的關(guān)鍵詞提取方法

2.1 拓?fù)鋭?/h3>

網(wǎng)絡(luò)結(jié)構(gòu)中各節(jié)點(diǎn)都不是相互獨(dú)立而是存在某種聯(lián)系的。法拉第為描述粒子間非接觸相互作用而提出場的概念：處于場中的任意粒子都將受到其他粒子的聯(lián)合作用[13]。文獻(xiàn)[14]從數(shù)據(jù)場的思想出發(fā)提出拓?fù)鋭荩汗?jié)點(diǎn)在網(wǎng)絡(luò)結(jié)構(gòu)中的拓?fù)湮恢孟喈?dāng)于節(jié)點(diǎn)所處的位勢，反映影響相鄰節(jié)點(diǎn)的能力，稱為拓?fù)鋭荨?/p>

真實(shí)網(wǎng)絡(luò)的模塊化特征表明節(jié)點(diǎn)間的相互作用具有范圍特征且節(jié)點(diǎn)的影響力與距離呈反比例關(guān)系，這十分符合短程場的概念。因此采用具有短程場特性且數(shù)學(xué)性質(zhì)良好的高斯函數(shù)來描述節(jié)點(diǎn)間的相互作用，作用大小通過拓?fù)鋭葜祦肀硎?。給定網(wǎng)絡(luò)G=(V,E)和勢場，其中V={vi|i=1,2,…，n}表示節(jié)點(diǎn)集合，E={(vi,vj)|vi,vj∈V}表示邊的集合。對于任意節(jié)點(diǎn)的拓?fù)鋭葜涤?jì)算如式(3)所示。

(3)

式中：φ(Vi)表示節(jié)點(diǎn)Vi的拓?fù)鋭葜担籲為在節(jié)點(diǎn)Vi影響范圍內(nèi)鄰居節(jié)點(diǎn)的個(gè)數(shù)；mj表示節(jié)點(diǎn)Vj的固有屬性，在現(xiàn)實(shí)網(wǎng)絡(luò)中常設(shè)為1；dij表示兩互相連接節(jié)點(diǎn)的最短距離，常用跳數(shù)進(jìn)行度量；σ為影響因子，主要用于控制節(jié)點(diǎn)的影響范圍。

(4)

2.2 結(jié)合拓?fù)鋭莸腡extRank算法

TextRank算法在迭代過程中通過詞語在窗口內(nèi)的共現(xiàn)關(guān)系構(gòu)建詞項(xiàng)圖且連邊間權(quán)重均勻轉(zhuǎn)移，未考慮詞語的語義信息及句法結(jié)構(gòu)。本文綜合考慮詞語局部和全局重要性，提出了結(jié)合拓?fù)鋭菖cTextRank算法的關(guān)鍵詞提取方法TPC-TextRank。

1)局部重要性。句子常由詞語通過語法規(guī)則組合而成，若將句子抽象為以詞為頂點(diǎn)的網(wǎng)絡(luò)，頂點(diǎn)間由于句法結(jié)構(gòu)的原因存在相互影響。拓?fù)鋭葜当硎揪W(wǎng)絡(luò)中節(jié)點(diǎn)在影響范圍內(nèi)受其他節(jié)點(diǎn)聯(lián)合作用的大小，將其計(jì)算方式進(jìn)行修改后可得到兩個(gè)單獨(dú)節(jié)點(diǎn)間的影響作用，以此作為詞語間的轉(zhuǎn)移概率，計(jì)算如下：

(5)

式中：σ表示影響范圍，其最優(yōu)值常根據(jù)勢熵來確定，但TextRank算法根據(jù)窗口大小N來確定共現(xiàn)關(guān)系，則可以通過下式確定σ：

(6)

dij為兩個(gè)詞語間距離。設(shè)dij=|Index(vi)-Index(vj)|，當(dāng)dij>N時(shí)，dij=0；當(dāng)dij≤N時(shí)，dij=|Index(vi)-Index(vj)|。計(jì)算詞語間的拓?fù)鋭葑鰹檫B接邊的權(quán)重以改進(jìn)TextRank算法的轉(zhuǎn)移概率矩陣。

2)全局重要性。TextRank算法加入詞頻、詞語分布等語義信息可以消除高頻詞的影響，實(shí)現(xiàn)對節(jié)點(diǎn)固有屬性mj的表示，主要包括兩個(gè)部分：TF(vj)表示詞語在整個(gè)文檔中出現(xiàn)的次數(shù);DF(vj)表示詞語在句子中的分布情況。要注意的是，文章都是高度聚合的，若詞語在文中分布越廣則更有可能成為關(guān)鍵詞。TF(vj)和DF(vj)的計(jì)算如式(7)-式(8)所示：

(7)

(8)

詞語固有屬性mj表示為：

mj=TF(vj)×DF(vj)

(9)

將式(9)代入式(5)，則轉(zhuǎn)移概率計(jì)算公式為：

(10)

TPC-TextRank算法的基本流程如圖1所示。

圖1 TPC-TextRank算法流程

對TPC-TextRank算法流程進(jìn)行如下說明：

(1)輸入文檔D。

(2)按句子對文檔進(jìn)行劃分后按句子進(jìn)行分詞、停用詞去除、詞性標(biāo)注等預(yù)處理。

(3)根據(jù)式(9)計(jì)算詞語全局重要性。

(4)設(shè)定滑動(dòng)窗口大小為N，在窗口范圍內(nèi)通過詞在句子范圍內(nèi)的共現(xiàn)關(guān)系構(gòu)建詞項(xiàng)圖。

(5)結(jié)合詞語全局重要性及詞項(xiàng)圖使用式(10)計(jì)算詞語的拓?fù)鋭葜?，作為詞語的轉(zhuǎn)移概率。

(6)結(jié)合詞項(xiàng)圖及轉(zhuǎn)移概率構(gòu)造轉(zhuǎn)移概率矩陣。

(7)根據(jù)式(2)迭代計(jì)算詞語重要性直至收斂。

(8)詞語按重要性逆序排列并輸出關(guān)鍵詞集合。

3 實(shí)驗(yàn)仿真

3.1 實(shí)驗(yàn)數(shù)據(jù)及環(huán)境

實(shí)驗(yàn)數(shù)據(jù)選取清華大學(xué)劉知遠(yuǎn)團(tuán)隊(duì)提供的2010年6月12日至2010年12月29日網(wǎng)易新聞信息，共計(jì)13 702條。每一條新聞包括“content”“title”“tags”等14個(gè)字段。其中主要用到了表示新聞?wù)牡摹癱ontent”字段，人工標(biāo)注標(biāo)簽的“tags”字段。實(shí)驗(yàn)環(huán)境為Windows 10，開發(fā)語言為Python 3.7，選用自然語言處理包TextRank4ZH和Jieba輔助實(shí)驗(yàn)仿真。

3.2 評價(jià)指標(biāo)

實(shí)驗(yàn)效果通過準(zhǔn)確率(P)、召回率(R)及F值(F)進(jìn)行驗(yàn)證。設(shè)經(jīng)TPC-TextRank算法提取的關(guān)鍵詞集合為TPC，原始標(biāo)注的關(guān)鍵詞集合為TAG，則：

(11)

(12)

(13)

3.3 實(shí)驗(yàn)與分析

為驗(yàn)證TPC-TextRank算法的效果，共設(shè)計(jì)了兩組實(shí)驗(yàn)。第一組實(shí)驗(yàn)：因TextRank和TPC-TextRank都將受滑動(dòng)窗口大小及Top-K大小的影響，為驗(yàn)證TPC-TextRank算法引入詞語局部重要性對最終效果的影響，設(shè)計(jì)實(shí)驗(yàn)取不同Top-K時(shí)準(zhǔn)確率、召回率及F值隨滑動(dòng)窗口大小變化的情況，實(shí)驗(yàn)結(jié)果如圖2所示。其中T-precision、T-recall、T-Fvalue分別表示TextRank算法的準(zhǔn)確率、召回率、F值，TPC-precision、TPC-recall、TPC-Fvalue表示TPC-TextRank算法的準(zhǔn)確率、召回率、F值。第二組實(shí)驗(yàn)：TF-IDF算法、TextRank算法、TPC-TextRank算法三者在Top-K值不同的情況下所得到的結(jié)果是不同的，而TextRank和TPC-TextRank又受到滑動(dòng)窗口大小的影響，故設(shè)計(jì)實(shí)驗(yàn)考查三種算法在滑動(dòng)窗口一定的情況下準(zhǔn)確率、召回率及F值隨Top-K取值變化的情況，實(shí)驗(yàn)結(jié)果如圖3所示。

圖2 TextRank與TPC-TextRank算法不同Top-K值時(shí)對比圖

圖3 三種算法對比圖

從圖2(a)、(b)可以看出，在Top-K值較小時(shí)TPC-TextRank算法三項(xiàng)指標(biāo)均高于TextRank算法，且TextRank算法各項(xiàng)指標(biāo)隨著滑動(dòng)窗口的增大而呈平衡趨勢，而TPC-TextRank算法效果隨滑動(dòng)窗口的增大而呈上升趨勢，說明考慮詞語全局及局部重要性時(shí)窗口越大越利于挖掘詞語間的關(guān)聯(lián)關(guān)系。從圖2(c)、(d)可以看出，在Top-K值增大后，TPC-TextRank算法三項(xiàng)指標(biāo)的起點(diǎn)低于TextRank算法，說明TPC-TextRank算法在窗口較小時(shí)對詞語間的關(guān)聯(lián)關(guān)系挖掘能力較弱，但隨著滑動(dòng)窗口的增大其效果呈現(xiàn)上升趨勢，驗(yàn)證了考慮詞語局部及全局影響對關(guān)鍵詞提取效果的提升。

由圖3可以看出，TF-IDF算法隨著Top-K取值的增加，準(zhǔn)確率呈降低趨勢而召回率呈升高趨勢，說明候選項(xiàng)中提取準(zhǔn)確的項(xiàng)數(shù)增速與候選項(xiàng)的增速不匹配，即未能有效地準(zhǔn)確提取出關(guān)鍵字；但其余兩種算法隨著滑動(dòng)窗口的增大以及Top-K取值的增加，準(zhǔn)確率均呈現(xiàn)上升趨勢，說明滑動(dòng)窗口的變化在構(gòu)建詞項(xiàng)圖時(shí)更加利于發(fā)現(xiàn)詞語之間的關(guān)聯(lián)關(guān)系。再結(jié)合圖2的分析結(jié)果，TPC-TextRank算法可更深層次地挖掘詞語間的語義信息并應(yīng)用于TextRank算法，提取效果優(yōu)于傳統(tǒng)的TextRank算法。

由上述實(shí)驗(yàn)結(jié)果可見，TF-IDF思想簡單且未考慮詞語語義信息，在實(shí)際中無法展現(xiàn)出良好的提取準(zhǔn)確率。傳統(tǒng)的TextRank算法雖然不依賴于語料庫且是基于圖的提取方法，但其迭代過程中連接邊的權(quán)值均勻分配，同樣忽略了詞語的語義信息而使得算法效果不佳。本文提出的TPC-TextRank方法綜合考慮詞語的全局及局部重要性，使用拓?fù)鋭莸乃枷雽D(zhuǎn)移概率矩陣進(jìn)行改進(jìn)，再結(jié)合傳統(tǒng)的TextRank算法實(shí)現(xiàn)了提取準(zhǔn)確率及召回率的提升。

4 結(jié) 語

關(guān)鍵詞是指能反映文本主題或主要內(nèi)容的詞語。作為自然語言處理領(lǐng)域的一個(gè)重要子任務(wù)，關(guān)鍵詞提取在信息檢索、情感分析、對話系統(tǒng)、文本分類等領(lǐng)域發(fā)揮著重要作用。本文針對傳統(tǒng)的TextRank算法提取關(guān)鍵詞時(shí)未考慮詞語的語義信息、構(gòu)建詞項(xiàng)圖時(shí)僅以詞語統(tǒng)計(jì)信息作為連接邊權(quán)值的考量、權(quán)值以均分的形式向相鄰節(jié)點(diǎn)傳統(tǒng)這些不足，使用詞頻和詞語分布情況作為詞語全局重要性指標(biāo)，再結(jié)合拓?fù)鋭輬隼碚撓嘤?jì)算詞語的拓?fù)鋭葜底鳛榫植恐匾?，將局部重要性引入傳統(tǒng)TextRank算法實(shí)現(xiàn)轉(zhuǎn)移概率矩陣的構(gòu)建，實(shí)驗(yàn)結(jié)果表明該方法實(shí)現(xiàn)了關(guān)鍵詞提取準(zhǔn)確率和召回率的提升。

TPC-TextRank算法在考慮詞語的全局重要性的基礎(chǔ)上結(jié)合拓?fù)鋭菟枷胄纬闪嗽~語的局部重要性考慮，但與傳統(tǒng)TextRank算法相結(jié)合后仍需要進(jìn)行多次迭代計(jì)算，使得算法的時(shí)間復(fù)雜度較高。本研究的后續(xù)工作將探討使用預(yù)先聚類、局部游走等方法降低TPC-TextRank算法的時(shí)間復(fù)雜度。