一種改進(jìn)的TextRank關(guān)鍵詞提取算法

李志強(qiáng)，潘蘇含，戴 娟，胡佳佳

(揚(yáng)州大學(xué) 信息工程學(xué)院，江蘇 揚(yáng)州 225000)

0 引 言

隨著信息化的快速普及，網(wǎng)頁中的信息數(shù)據(jù)日益增多。面對(duì)海量的文本信息，如何準(zhǔn)確、高效地對(duì)文章內(nèi)容進(jìn)行檢索，成為目前的研究熱點(diǎn)。對(duì)于文本的分析，一般會(huì)先從關(guān)鍵詞入手，一篇文章的關(guān)鍵詞不但可以概括文章的主題，還能反映整篇文章所表達(dá)的主要內(nèi)容與情感傾向。因此，高效、準(zhǔn)確地獲取關(guān)鍵詞，對(duì)于文本分類、自動(dòng)摘要和文本檢索至關(guān)重要。

近年來，國(guó)內(nèi)外研究人員在關(guān)鍵詞提取技術(shù)領(lǐng)域展開了大量的研究工作，同時(shí)也提出了很多關(guān)鍵詞提取算法。其中主要算法有基于隱含主題模型的關(guān)鍵詞抽取(LDA)[1]、基于TF-IDF詞頻統(tǒng)計(jì)的關(guān)鍵詞抽取[2]和基于詞圖模型的關(guān)鍵詞抽取(TextRank)[3]。上述三種算法因其簡(jiǎn)單易行而應(yīng)用廣泛。

其中，基于隱含主題模型的關(guān)鍵詞抽取算法是根據(jù)文檔和單詞的主題分布相似度來計(jì)算單詞的重要性，由于該方法一般依賴對(duì)語料庫內(nèi)容進(jìn)行訓(xùn)練得到所需信息，因此，這種方法獲取到的關(guān)鍵詞的質(zhì)量與訓(xùn)練語料庫主題分布密切相關(guān)?；赥F-IDF算法的詞頻統(tǒng)計(jì)關(guān)鍵詞提取(term frequency-inverse document frequency)主要通過對(duì)詞語出現(xiàn)的頻次來判斷詞語對(duì)文章的重要性，是一種成熟的基于統(tǒng)計(jì)的提取方法。該方法在關(guān)鍵詞提取的過程中過度依賴詞頻特征，忽略了語義、上下文環(huán)境等其他特征。為此，往往會(huì)引入其他特征因子進(jìn)行計(jì)算以此減少對(duì)詞頻的依賴。TextRank算法是基于圖的排序算法，利用共現(xiàn)窗口實(shí)現(xiàn)部分詞語之間的關(guān)系構(gòu)建，對(duì)后續(xù)關(guān)鍵詞進(jìn)行排序，直接從文本本身中提取關(guān)鍵詞。但是該方法沒有分析詞語重要性的不同是否會(huì)影響相鄰節(jié)點(diǎn)權(quán)值轉(zhuǎn)移的問題，并且沒有利用文檔語料庫的整體信息，詞語的權(quán)重信息并沒有實(shí)際意義，不能區(qū)分連接上的強(qiáng)弱。

為了進(jìn)一步提高關(guān)鍵詞提取的效果與質(zhì)量，許多學(xué)者對(duì)上述算法進(jìn)行改進(jìn)。郎冬冬等人[4]提出一種基于LDA和TextRank的文本關(guān)鍵短語抽取方法。顧益軍等人[5]結(jié)合LDA與TextRank，使候選節(jié)點(diǎn)詞語的重要性按文檔集主題分布進(jìn)行了非均勻轉(zhuǎn)移。但是結(jié)果受訓(xùn)練語料庫主題分布影響較大。張瑾等人[6]、謝晉等人[7]考慮了結(jié)合詞語位置和詞跨度的方法對(duì)TF-IDF權(quán)重進(jìn)行改進(jìn)，或者利用語義的連貫性，結(jié)合詞頻和詞語位置特征進(jìn)行加權(quán)分析[8]。另外也有部分學(xué)者引入信息熵[9]的方法。但這些方法在應(yīng)用過程中都存在一定的問題，比如計(jì)算復(fù)雜度較高，或者在文章類型和語料規(guī)模上需要相當(dāng)?shù)囊?guī)模。還有一些學(xué)者結(jié)合文章綜合信息和引用新聞?lì)悇e因子的方法[10-12]，結(jié)合了其他特征信息進(jìn)行加權(quán)，在一定程度上能夠解決詞頻依賴問題。但這些方法未考慮關(guān)鍵詞的詞性以及關(guān)鍵詞覆蓋度不同所帶來的影響。Biswas S K等人[13]、Yan Ying等人[14]提出了基于圖的關(guān)鍵詞提取方法，方法中分別考慮了詞語的上下文環(huán)境，詞語的位置，詞語的中心性，詞性等特征，修改詞語的初始權(quán)重等，得到了不錯(cuò)的提取效果。

針對(duì)上述問題，基于文獻(xiàn)[13-14]的啟發(fā)，文中綜合考慮詞語對(duì)于單個(gè)文檔與文檔集的重要性來進(jìn)行關(guān)鍵詞抽取。選用TF-IDF與平均信息熵綜合計(jì)算詞語對(duì)于單文檔與文檔集的重要性，然后計(jì)算出詞語的綜合權(quán)重來改進(jìn)TextRank詞匯節(jié)點(diǎn)的初始權(quán)重以及概率轉(zhuǎn)移矩陣。通過多組實(shí)驗(yàn)對(duì)比分析，經(jīng)過改進(jìn)后的方法能夠更高效、準(zhǔn)確地獲取關(guān)鍵詞信息。

1 相關(guān)技術(shù)

對(duì)在關(guān)鍵詞提取過程中需要用到的相關(guān)算法進(jìn)行介紹，主要有TF-IDF算法與平均信息熵算法。這兩種算法主要用于詞語對(duì)單個(gè)文檔和文檔集的重要性計(jì)算。

1.1 TF-IDF算法

TF-IDF算法的基本思想是：利用詞語頻次(term frequency，TF)和逆文檔頻率(inverse document frequency，IDF)相乘得到詞語的權(quán)重值[15]。根據(jù)TF-IDF算法，詞語權(quán)重WTF-IDF(i)的計(jì)算公式如下：

WTF-IDF(i)=TFi*IDFi

(1)

IDFi=log(N/DFi)

(2)

其中，TFi表示詞語i在文檔內(nèi)容中出現(xiàn)的次數(shù)/文檔內(nèi)容的總詞數(shù)，即詞語i在文檔中出現(xiàn)的頻率，N表示語料庫中文檔總數(shù)，DFi表示包含詞語i的文檔數(shù)，IDFi表示詞語i的主題表現(xiàn)能力。

根據(jù)上述公式可知，如果詞語在某一篇文檔中出現(xiàn)頻率較高，但是在語料庫中包含該詞的文檔數(shù)較低，則該詞根據(jù)TF-IDF算法得到的權(quán)重值WTF-IDF(i)就越高，也就是說該詞語可以在一定程度上表示文章的主題內(nèi)容。反之，則說明該詞語不是重要詞語，不能表現(xiàn)文章的主要內(nèi)容。

1.2 平均信息熵算法

平均信息熵的基本思想是：根據(jù)詞頻在不同文檔中出現(xiàn)的頻數(shù)，結(jié)合整體語料庫計(jì)算所有詞語對(duì)于單個(gè)文檔和文檔集的重要性，通過平均信息熵可以衡量詞語在整個(gè)文檔集中分布的均衡度。根據(jù)平均信息熵算法，詞語權(quán)重WEntropy(i)的計(jì)算公式如下：

(3)

其中，fwk表示詞w在文檔k中出現(xiàn)的頻次，nw表示詞w在整個(gè)文檔集中出現(xiàn)的頻次，N表示語料庫中文檔的總數(shù)。

如果詞i在各類別文檔中出現(xiàn)頻率相當(dāng)，則其WEntropy(i)的值接近于最小值0，表示其并不能很好地表示文檔的主題內(nèi)容。反之，如果詞語i在各類文檔中出現(xiàn)頻率差別很大，其WEntropy(i)的值接近于最大值1，表示其對(duì)文檔主題有很好的表現(xiàn)力。

2 關(guān)鍵詞提取算法

2.1 算法描述

傳統(tǒng)的TextRank算法是將一篇文檔轉(zhuǎn)換成一張有向帶權(quán)的詞圖模型，是將文本進(jìn)行分割，分割成基本單元，即詞語，每個(gè)基本單元看作是一個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)之間的邊由詞節(jié)點(diǎn)之間的共現(xiàn)關(guān)系決定，而節(jié)點(diǎn)的重要性又由相鄰節(jié)點(diǎn)指向數(shù)量決定。TextRank算法的計(jì)算方式如下所示。

(4)

構(gòu)建TextRank關(guān)鍵詞圖G=(V,E)，其中V為節(jié)點(diǎn)集合，E為節(jié)點(diǎn)之間的邊集合；In(Vi)是節(jié)點(diǎn)Vi的入度點(diǎn)的集合，即指向節(jié)點(diǎn)Vi的節(jié)點(diǎn)集合；Out(Vj)是節(jié)點(diǎn)Vj的出度點(diǎn)集合，即節(jié)點(diǎn)Vj指向的所有節(jié)點(diǎn)的集合；Wji是節(jié)點(diǎn)Vj與節(jié)點(diǎn)Vi之間邊的權(quán)重；d是阻尼系數(shù)，一般取值為0.85，其作用是表示當(dāng)前節(jié)點(diǎn)向其他任意節(jié)點(diǎn)跳轉(zhuǎn)的概率，同時(shí)能夠保證讓權(quán)重能夠穩(wěn)定的傳遞至收斂，最終計(jì)算每個(gè)詞語的權(quán)重并進(jìn)行排序，選取topN作為N個(gè)關(guān)鍵詞并輸出。

傳統(tǒng)TextRank算法中，每個(gè)節(jié)點(diǎn)初始權(quán)重為1或1/N，即節(jié)點(diǎn)的初始權(quán)重相同，且節(jié)點(diǎn)權(quán)值均勻轉(zhuǎn)移。但是通過研究發(fā)現(xiàn)，基于詞語重要性加權(quán)詞語轉(zhuǎn)移概率的方法可以有效改進(jìn)關(guān)鍵詞提取的效果[16-17]。因此，文中選用TF-IDF和平均信息熵兩個(gè)特征來計(jì)算詞語的權(quán)重，用計(jì)算得到的綜合特征信息來改進(jìn)TextRank詞匯節(jié)點(diǎn)的初始權(quán)重大小以及概率轉(zhuǎn)移矩陣。

選取任意一個(gè)詞i，定義詞i的綜合權(quán)重計(jì)算方式如下：

(5)

其中，WTF-IDF(i)是詞語通過TF-IDF計(jì)算得到的權(quán)重值，WEntropy(i)是詞語的平均信息熵權(quán)值。

根據(jù)TextRank算法，節(jié)點(diǎn)間的轉(zhuǎn)移概率計(jì)算公式為：

(6)

根據(jù)式(6)可知，節(jié)點(diǎn)的權(quán)重迭代公式如下：

(7)

其中，W(Vj,Vi)表示節(jié)點(diǎn)Vj到節(jié)點(diǎn)Vi邊的轉(zhuǎn)移概率，即通過式(6)計(jì)算所得，WWeight(Vi)表示由式(5)得到的綜合權(quán)重值。

2.2 關(guān)鍵詞提取

基于改進(jìn)的TextRank關(guān)鍵詞提取算法的提取流程如圖1所示。

圖1 基于改進(jìn)的TextRank關(guān)鍵詞提取算法的提取流程

輸入需要提取關(guān)鍵詞信息的文本內(nèi)容，關(guān)鍵詞提取步驟如下：

第一步：文本預(yù)處理。對(duì)文本中的內(nèi)容進(jìn)行分詞，詞性標(biāo)注，只保留名詞、專有名詞、動(dòng)詞、形容詞和副詞，并刪除文本中的停用詞。

第二步：權(quán)重計(jì)算。計(jì)算得到文本中每個(gè)詞語的WTF-IDF，WEntropy，并計(jì)算綜合權(quán)重WWeight。

第三步：關(guān)鍵詞提取。構(gòu)建基于詞語綜合權(quán)重的加權(quán)節(jié)點(diǎn)初始值及節(jié)點(diǎn)概率轉(zhuǎn)移矩陣改進(jìn)的TextRank模型，最終計(jì)算選擇前N個(gè)權(quán)重比較大的詞語作為關(guān)鍵詞并輸出。

3 實(shí)驗(yàn)結(jié)果及分析

文中的實(shí)驗(yàn)數(shù)據(jù)是在各大門戶網(wǎng)站中隨機(jī)抽取的包含多種主題的新聞數(shù)據(jù)、新聞內(nèi)容字?jǐn)?shù)、主題等信息。將每一篇新聞保存為一個(gè)文檔，共500個(gè)文檔組成語料庫。對(duì)于數(shù)據(jù)集，采用多人人工交叉標(biāo)注的形式提取關(guān)鍵詞，每一個(gè)文檔分別提取5，7，10個(gè)關(guān)鍵詞。

對(duì)于相同的數(shù)據(jù)集，提取不同數(shù)量的關(guān)鍵詞，實(shí)驗(yàn)中分別采用傳統(tǒng)的TF-IDF算法、TextRank算法和改進(jìn)的TextRank算法(共現(xiàn)窗口大小一個(gè)為5，一個(gè)為7)進(jìn)行交叉對(duì)比。采用精度P(Precision)、召回率R(Recall)和F1值(F1-Measure)作為評(píng)價(jià)關(guān)鍵詞提取的性能指標(biāo)，指標(biāo)計(jì)算公式如下：

(8)

(9)

(10)

3.1 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果如表1所示。根據(jù)表1的實(shí)驗(yàn)結(jié)果分析可以發(fā)現(xiàn)，文中提出的方法在關(guān)鍵詞提取方面優(yōu)于傳統(tǒng)的TF-IDF和TextRank算法。

表1 實(shí)驗(yàn)結(jié)果對(duì)比 %

3.2 實(shí)驗(yàn)分析

實(shí)驗(yàn)結(jié)果交叉對(duì)比如圖2所示。

圖2 實(shí)驗(yàn)結(jié)果交叉對(duì)比

觀察對(duì)比圖可以發(fā)現(xiàn)，隨著提取的關(guān)鍵詞數(shù)量的增加，傳統(tǒng)的TF-IDF算法與TextRank算法的準(zhǔn)確率呈現(xiàn)下降的趨勢(shì)；而文中提出的改進(jìn)的TextRank算法，隨著關(guān)鍵詞提取的數(shù)量變化，準(zhǔn)確率相對(duì)穩(wěn)定。因?yàn)楦鶕?jù)詞語的綜合權(quán)重進(jìn)行計(jì)算，關(guān)鍵詞相對(duì)較為集中突出，權(quán)重相對(duì)較大。

此外，可以發(fā)現(xiàn)，傳統(tǒng)的TextRank算法的共現(xiàn)窗口大小對(duì)準(zhǔn)確率也有影響。因?yàn)楣铂F(xiàn)窗口的大小決定可權(quán)重轉(zhuǎn)移概率矩陣的稠密，從而影響關(guān)鍵詞的提取結(jié)果。當(dāng)共現(xiàn)窗口為7的時(shí)候，提取的關(guān)鍵詞準(zhǔn)確度要比共現(xiàn)窗口為5時(shí)高一些。

總之，文中提出的改進(jìn)方法，在精度P(Precision)和F1值(F1-Measure)方面均高于傳統(tǒng)方法，召回率(Recall)基本相當(dāng)。這個(gè)基本可以證明，該方法在關(guān)鍵詞信息獲取方面較傳統(tǒng)的TF-IDF和TextRank算法更加高效、準(zhǔn)確。

4 結(jié)束語

一篇文章的關(guān)鍵詞不但可以概括文章的主題，還能反映整篇文章所表達(dá)的主要內(nèi)容與情感傾向，所以對(duì)于提取的關(guān)鍵詞信息的準(zhǔn)確率有較高的要求，這樣才能夠相對(duì)準(zhǔn)確地表達(dá)文本的主題內(nèi)容。因此，高效、準(zhǔn)確地提取關(guān)鍵詞信息，對(duì)于文本分類、自動(dòng)摘要和文本檢索至關(guān)重要。

提出了一種基于TextRank的改進(jìn)算法。針對(duì)傳統(tǒng)TextRank算法沒有考慮詞語本身的重要性，以及文檔整體信息等不足之處，該算法選用TF-IDF算法與平均信息熵算法計(jì)算詞語的重要性，通過計(jì)算詞語的重要性對(duì)不同詞語賦予不同的權(quán)重，根據(jù)計(jì)算得到的詞語權(quán)重改進(jìn)TextRank算法詞匯節(jié)點(diǎn)的初始權(quán)重以及概率轉(zhuǎn)移矩陣。該算法提高了關(guān)鍵詞提取的準(zhǔn)確度，并且操作簡(jiǎn)單，無須進(jìn)行訓(xùn)練和人工干預(yù)，具有較強(qiáng)的通用性，能夠滿足對(duì)于一般文章的關(guān)鍵詞提取需求。同時(shí)，可以結(jié)合更多的詞語特征、詞語上下文的語義環(huán)境等對(duì)該算法進(jìn)行完善，這也是接下來研究的主要方向。