基于PageRank的新聞關(guān)鍵詞提取算法

顧亦然，許夢馨

?

基于PageRank的新聞關(guān)鍵詞提取算法

顧亦然，許夢馨

(南京郵電大學(xué)自動化學(xué)院 南京 210023)

現(xiàn)有的基于復(fù)雜網(wǎng)絡(luò)的關(guān)鍵詞提取算法在構(gòu)建加權(quán)文本網(wǎng)絡(luò)時沒有考慮文本的自然語言特性，且在提取關(guān)鍵詞時較少涉及復(fù)雜網(wǎng)絡(luò)領(lǐng)域經(jīng)典算法。本文引入詞頻分享權(quán)重，利用詞頻特性為節(jié)點之間的連邊加權(quán)。在此基礎(chǔ)上，基于PageRank算法，并結(jié)合人類語言習(xí)慣特性定義位置權(quán)重系數(shù)，提出了一個新的新聞關(guān)鍵詞提取算法——LTWPR算法，綜合考慮了文本網(wǎng)絡(luò)的局部特征和全局特征。采用新浪新聞?wù)Z料進行了大量實驗，結(jié)果表明該算法能夠快速有效的覆蓋新聞作者標注的關(guān)鍵詞，且提取效果更佳。

復(fù)雜網(wǎng)絡(luò); 關(guān)鍵詞提取; 自然語言; PageRank; 詞頻分享權(quán)重

隨著信息時代的到來以及互聯(lián)網(wǎng)的蓬勃發(fā)展，關(guān)鍵詞成為用戶搜索信息必不可少的工具。關(guān)鍵詞以凝練簡潔的形式對文本主題進行有效概括，通過提取關(guān)鍵詞，可以結(jié)構(gòu)化地表示目標文本，提高人們的文獻管理與檢索效率。

關(guān)鍵詞在新聞領(lǐng)域有十分重要的作用。目前，網(wǎng)頁新聞如新浪新聞會在網(wǎng)頁源代碼中標注keywords或tags屬性的詞語，并在網(wǎng)頁新聞下端貼出標簽或文章關(guān)鍵詞，使得用戶在搜索相關(guān)新聞時能快速定位。由于個體語言的差異性，手動標注關(guān)鍵詞可能存在不規(guī)范或不準確的問題，且核對工作較繁瑣。因此，找到一種規(guī)范化、合理高效的文本關(guān)鍵詞自動提取方法具有十分重要的意義。

傳統(tǒng)的關(guān)鍵詞提取算法是基于TF-IDF[1-2]計算詞語的特征權(quán)重，利用詞頻TF發(fā)現(xiàn)高頻詞，再通過引入逆文本頻率指數(shù)IDF[3]來降低高頻卻不具代表性的詞語對文本的重要度，提高提取關(guān)鍵詞的準確率，算法思想十分簡單。但此方法計算復(fù)雜度較高，需將所有文本均考慮在內(nèi)才能計算詞語的逆文本頻率指數(shù)，因此，其提取關(guān)鍵詞準確度受文檔集合大小的影響較大。另一經(jīng)典算法是以TextRank[4]為典型代表的基于詞圖模型的關(guān)鍵詞抽取算法。受著名的Google網(wǎng)頁排名算法PageRank[5]的啟發(fā)，文獻[4]把詞看做網(wǎng)頁，將詞與詞之間的語義關(guān)系看作鏈接，開發(fā)了TextRank算法，因其不需要事先對多篇文本進行訓(xùn)練，僅利用單篇文檔本身就能實現(xiàn)關(guān)鍵詞提取，實現(xiàn)方法簡單高效并得到廣泛應(yīng)用。然而，該方法采用的是詞語節(jié)點影響力均分的無權(quán)圖模型，在進行關(guān)鍵詞抽取時僅考慮了詞語的詞性信息，未考慮詞語節(jié)點之間的相互影響力，導(dǎo)致非重要詞語吸收的貢獻值相對增加。

基于復(fù)雜網(wǎng)絡(luò)的關(guān)鍵詞提取方法是近年來隨著復(fù)雜網(wǎng)絡(luò)研究的興起而出現(xiàn)的一種新的關(guān)鍵詞提取算法。文本網(wǎng)絡(luò)已被證實具有小世界特性[6]，可以使用復(fù)雜網(wǎng)絡(luò)理論進行關(guān)鍵詞的提取。在一個文本網(wǎng)絡(luò)中，詞語被視為節(jié)點，詞語之間的聯(lián)系抽象為連邊。所有詞語和連邊即構(gòu)成一個文本復(fù)雜網(wǎng)絡(luò)。已被研究出的基于復(fù)雜網(wǎng)絡(luò)的關(guān)鍵詞提取方法大多基于詞語在同一句子中共現(xiàn)次數(shù)為連邊加權(quán)[7]，再應(yīng)用復(fù)雜網(wǎng)絡(luò)統(tǒng)計參數(shù)度、聚類系數(shù)、介數(shù)、接近中心性、最短路徑等[8]兩參數(shù)加權(quán)或三參數(shù)加權(quán)計算得到詞語節(jié)點的特征權(quán)重，進而得到一篇文章的關(guān)鍵詞。文獻[9]利用特征詞共現(xiàn)次數(shù)為連邊加權(quán)，通過節(jié)點的加權(quán)聚類系數(shù)和介數(shù)兩參數(shù)加權(quán)計算節(jié)點的綜合特征值。文獻[10]利用詞語共現(xiàn)次數(shù)為連邊加權(quán)，通過加權(quán)度及聚類系數(shù)兩參數(shù)加權(quán)計算節(jié)點的特征權(quán)重。文獻[11]利用兩個詞語在同一句話中共現(xiàn)次數(shù)的倒數(shù)為連邊加權(quán)，通過節(jié)點的加權(quán)中心度和介數(shù)兩參數(shù)加權(quán)計算節(jié)點的綜合特征值，從而提取文本關(guān)鍵詞。文獻[12]提出應(yīng)用語義加權(quán)網(wǎng)絡(luò)提取中文關(guān)鍵詞的方法，利用詞共現(xiàn)頻率和語義相似度構(gòu)造語義加權(quán)網(wǎng)絡(luò)，通過節(jié)點的介數(shù)、聚類系數(shù)變化值和平均最短路徑變化值三參數(shù)加權(quán)計算得到節(jié)點的綜合特征值。文獻[13]提出的基于復(fù)雜網(wǎng)絡(luò)的關(guān)鍵詞提取方法也通過詞語共現(xiàn)次數(shù)的倒數(shù)為連邊加權(quán)，利用偏向中心性和度中心性兩參數(shù)歸一再加權(quán)計算節(jié)點的綜合特征值。文獻[14]依據(jù)詞匯在文本中的共現(xiàn)關(guān)系構(gòu)造詞匯概念復(fù)雜網(wǎng)絡(luò)，提出了一種利用詞匯概念本身頻率以及其相鄰節(jié)點的數(shù)量及重要性指標為節(jié)點加權(quán)，計算出文本詞匯的重要性指標獲取候選關(guān)鍵詞集。

已有的基于復(fù)雜網(wǎng)絡(luò)的關(guān)鍵詞提取研究大部分只應(yīng)用了復(fù)雜網(wǎng)絡(luò)統(tǒng)計參數(shù)，較少應(yīng)用復(fù)雜網(wǎng)絡(luò)經(jīng)典方法計算詞語節(jié)點的權(quán)重，且忽略了可以利用自然語言詞頻特性對節(jié)點和節(jié)點之間的連邊賦予權(quán)重的方法。本文針對上述問題進行研究分析，在較好構(gòu)建文本復(fù)雜網(wǎng)絡(luò)的基礎(chǔ)上，基于PageRank算法提出一種新的新聞關(guān)鍵詞提取算法，實現(xiàn)對關(guān)鍵詞的有效提取。

1 基于PageRank的新聞關(guān)鍵詞排序算法LTWPR

本文算法思想可概括為以下3點：

1) 考慮到詞頻對新聞主題的重要性，引入詞頻分享權(quán)重概念，將目標節(jié)點的詞頻值根據(jù)鄰居節(jié)點對其的重要度來分配給相應(yīng)的連邊，實現(xiàn)對連邊加權(quán)；

2) 考慮鄰居節(jié)點對目標節(jié)點的重要度貢獻，即：與關(guān)鍵詞聯(lián)系越緊密的詞語其成為關(guān)鍵詞的可能性也越大，基于PageRank算法提出本文LTWPR (located and TF-weighted PageRank)算法；

3) 考慮詞語位置對詞語重要度的影響，增加位置權(quán)重系數(shù)。顯然，對新聞文本而言，出現(xiàn)在標題中的詞語能夠更好地反映主題，相比于出現(xiàn)在正文中，其重要性更高，因此對位于新聞標題的詞語賦予更高的權(quán)重系數(shù)。

本文算法摒棄了大部分研究使用的復(fù)雜網(wǎng)絡(luò)兩參數(shù)或三參數(shù)加權(quán)的方法，直接將最原始的詞頻指標與復(fù)雜網(wǎng)絡(luò)經(jīng)典方法PageRank相融合，并考慮了人類語言習(xí)慣而設(shè)計位置權(quán)重系數(shù)。在時間復(fù)雜度上，由于傳統(tǒng)的TF-IDF算法在計算每個詞語的IDF值時均需要遍歷整個新聞文本集合，時間復(fù)雜度可謂非常高。而本文算法在讀入新聞文本集合后，一次只需處理一篇，時間復(fù)雜度較TF-IDF算法更低。同時，與已有的基于復(fù)雜網(wǎng)絡(luò)的關(guān)鍵詞提取算法相比，本文算法省去了對兩參數(shù)或三參數(shù)的調(diào)節(jié)過程與時間，獲取結(jié)果更為直接。

1.1 基于連邊規(guī)則的文本網(wǎng)絡(luò)構(gòu)建

文本網(wǎng)絡(luò)構(gòu)建過程最重要的是分詞和連邊關(guān)系的創(chuàng)建。首先，分詞獲得所有詞語節(jié)點。目前，文獻[15]的NLPIR分詞軟件已經(jīng)相對成熟，故分詞步驟直接調(diào)用NLPIR軟件的接口來實現(xiàn)。

其次，根據(jù)一定規(guī)則創(chuàng)建詞語節(jié)點之間的連邊。經(jīng)過大量學(xué)者的研究發(fā)現(xiàn)，距離為1或2的詞語之間構(gòu)建一條連邊在文本復(fù)雜網(wǎng)絡(luò)中最為常見，且效果最佳[9]。因此，本文采用該方法構(gòu)建連邊規(guī)則，即同一個句子中，距離小于等于2的有效詞語之間產(chǎn)生一條連邊且連邊方向為當前詞語單向指向位于其后的詞語。其中，有效詞語指可能作為關(guān)鍵詞的詞語。同時，為了對該連邊規(guī)則進行精確定義，本文提出了標點符號識別策略，對“同一個句子”和“距離”定義如下：

1) 同一個句子定義為：以句號、嘆號、逗號、分號、省略號分隔。

2) 距離定義為：以括號、引號、頓號、冒號、破折號分隔，間距記為1；以百分號、千分號、單位符號分隔，間距記為0。因為分詞軟件會直接將此類標點與其修飾的數(shù)字分為同一個詞，如5.7%作為數(shù)詞詞性存在，故此3種標點無需考慮。

1.2 文本網(wǎng)絡(luò)構(gòu)建算法

文本網(wǎng)絡(luò)構(gòu)建算法流程圖如圖1所示。具體步驟描述如下。

輸入數(shù)據(jù)：新聞文本。

1) 分詞。讀入用戶詞典，利用NLPIR分詞軟件輸出“詞語+詞性”組合列表，存入List WordList，記錄詞語內(nèi)容strWord，詞性intType；

2) 分句。根據(jù)標點符號將目標文本分成句子，存入List Sentence；

3) 無效詞語過濾。若命中停用詞表和無用詞性表的詞語標記為Ignore；

4) 定位每個未被標記Ignore的詞語在句子中的位置。根據(jù)Sentence確定詞語位置intPositon，和所屬句子索引intLineNum，作為詞語獨一無二的位置ID；

5) 合并詞語。掃描詞語，對同義詞進行合并，將被兼并詞語標記為Merged，指向兼并它的詞語；

6) 構(gòu)建節(jié)點。將未被標記為Ignore的剩余詞語構(gòu)造為節(jié)點，存入List NodeList中；

7) 構(gòu)建網(wǎng)絡(luò)。根據(jù)1.1節(jié)定義的連邊規(guī)則，依據(jù)位置intPosition和所屬句子索引intLineNum對所有節(jié)點進行加邊，對于標記為Merged的兼并節(jié)點，將邊和鄰居節(jié)點加載到其宗主節(jié)點上，兩節(jié)點之間的相應(yīng)邊權(quán)不變。

輸出數(shù)據(jù)：新聞文本網(wǎng)絡(luò)。

1.3 新聞關(guān)鍵詞提取算法LTWPR

新聞關(guān)鍵詞提取算法LTWPR具體步驟描述如下。

1) 構(gòu)建文本網(wǎng)絡(luò)，如1.2節(jié)描述。

2 實驗及結(jié)果分析

本文爬取了新浪新聞(http://news.sina.com.cn/)下6個領(lǐng)域類別(財經(jīng)、國際、國內(nèi)、政務(wù)、軍事、社會)共2 536篇新聞作為實驗數(shù)據(jù)集，并與經(jīng)典的TF-IDF算法和TextRank算法進行對比。采集的新聞文本格式如圖2所示。

由于個體語言的差異性，新聞中作者標注的關(guān)鍵詞集難免存在不合理的情況，且對同一事件的報導(dǎo)不同新聞媒體的敘述方式不同標注的關(guān)鍵詞也不盡相同。然而，考慮到新浪新聞的權(quán)威性、正式性和凝練性，本文默認大部分新聞文本數(shù)據(jù)的關(guān)鍵詞標注是合理的。因此，在實驗數(shù)據(jù)的準備工作中，只對部分關(guān)鍵詞標注明顯不合理的新聞文本進行關(guān)鍵詞手動微調(diào)，去掉確實不合理或者有重復(fù)性質(zhì)的關(guān)鍵詞。

本文首先隨機選取單篇新聞進行對比實驗說明本文算法優(yōu)于TF-IDF算法和TextRank算法之處。進一步的，為了驗證基于復(fù)雜網(wǎng)絡(luò)的新聞關(guān)鍵詞排序算法的有效性，針對爬取的2 536篇新浪新聞?wù)Z料，首先將所有新聞?wù)Z料匯總，進行上述3種算法對比實驗，并分析設(shè)置提取關(guān)鍵詞個數(shù)的合理性，在此基礎(chǔ)上將新聞按領(lǐng)域分類，再進行綜合對比實驗并分析結(jié)果。

2.1 單篇新聞實驗

首先采用圖2所示的新聞“日媒：中國軍艦若無其事經(jīng)過日本領(lǐng)?？殖沙B(tài)”進行對比實驗。3種算法提取出的關(guān)鍵詞及相關(guān)指標如表1所示。

表1 3種算法提取結(jié)果對比

觀察表1，新聞作者標注的標準關(guān)鍵詞為“中國海軍”、“中國軍艦”、“日本領(lǐng)?！?個，實驗設(shè)置提取的關(guān)鍵詞個數(shù)為4。其中，TF-IDF方法提取出的關(guān)鍵詞為“中國海軍”、“無害通航”、“李杰”、“日本領(lǐng)?！?。觀察圖2中新聞文本，發(fā)現(xiàn)詞語“無害通航”在文中出現(xiàn)7次，“李杰”在文中出現(xiàn)6次，使得這兩個詞語成為關(guān)鍵詞的可能性大大提高，干擾了最終的提取結(jié)果。TextRank算法提取的出關(guān)鍵詞為“中國海軍”、“軍艦”、“無害通航”、“日本”，對標準關(guān)鍵詞集的覆蓋率較低。分析發(fā)現(xiàn)“中國軍艦”和“日本領(lǐng)?！苯M合詞詞頻較低，鄰居節(jié)點數(shù)量小，而“軍艦”和“日本”詞頻相對高一些，在文本網(wǎng)絡(luò)中擁有更多的鄰居節(jié)點為其貢獻重要度，因而排名靠前，導(dǎo)致最終各項提取指標值較低。而本文LTWPR算法提取出的關(guān)鍵詞為“中國海軍”、“日本領(lǐng)海”、“軍艦”和“中國軍艦”，基本覆蓋標準關(guān)鍵詞集。說明本文算法在一定程度上優(yōu)于TF-IDF算法和TextRank算法。

2.2 按關(guān)鍵詞提取個數(shù)對比實驗

通過觀察爬取的2 536篇新浪新聞?wù)Z料發(fā)現(xiàn)，作者標注的關(guān)鍵詞(以下稱標準關(guān)鍵詞)個數(shù)在1～5范圍之間。關(guān)鍵詞分布如圖3所示。

圖3 新聞標準關(guān)鍵詞分布

從圖3中可以看出，對于新聞這種簡潔明了的文本(500～800字最佳)，標準關(guān)鍵詞設(shè)置3個的最為普遍，設(shè)置4個和2個的次之。標準關(guān)鍵詞設(shè)置為1個時，新聞主題概括較不明確，在用戶輸入關(guān)鍵詞搜索新聞時，較難匹配到目標新聞，較大程度降低搜索的準確性。而標準關(guān)鍵詞設(shè)置為5個或更多時，新聞主題特征分散或不明顯，容易干擾搜索結(jié)果，導(dǎo)致搜索有效性的降低。

2.3 按新聞領(lǐng)域?qū)Ρ葘嶒?/h3>

圖6 提取關(guān)鍵詞+2時各項指標結(jié)果

3 結(jié)束語

1) 將新聞?wù)Z料按關(guān)鍵詞提取個數(shù)分類進行的實驗結(jié)果表明，不管提取的關(guān)鍵詞個數(shù)多或者少，本文LTWPR算法提取出的關(guān)鍵詞能夠更好地覆蓋新聞作者標注的關(guān)鍵詞，提取結(jié)果優(yōu)于TF-IDF算法和TextRank算法，具有較高的有效性；

2) 將新聞?wù)Z料按領(lǐng)域分類進行的實驗結(jié)果表明，在財經(jīng)、國際、國內(nèi)、政務(wù)、軍事、社會6個領(lǐng)域，本文LTWPR算法的關(guān)鍵詞提取有效性更高，應(yīng)用于新聞關(guān)鍵詞的提取時實用性更強，且對于國際領(lǐng)域新聞的提取效果最優(yōu)。

本文研究工作還存在一些不足。由于基于復(fù)雜網(wǎng)絡(luò)的關(guān)鍵詞提取方法仍依賴于分詞軟件進行分詞才能構(gòu)造文本網(wǎng)絡(luò)，而構(gòu)建文本網(wǎng)絡(luò)的優(yōu)劣將直接影響提取關(guān)鍵詞的各項指標。本文算法在提取關(guān)鍵詞時，提取結(jié)果也在一定程度上受分詞軟件分詞準確率的影響。因此，在分詞軟件分詞準確率受限的情況下，如何提高文本網(wǎng)絡(luò)構(gòu)建的完備性仍需進一步研究。

[1] SALTON G. Developments in automatic text retrieval[J]. Science, 1991, 253(5023): 974-979.

[2] 楊凱艷. 基于改進的TFIDF關(guān)鍵詞自動提取算法研究[D]. 湖南, 湘潭: 湘潭大學(xué), 2015.

YANG Kai-yan. Research on automatic keyword extraction algorithm based on improved TFIDF[D]. Xiangtan, Hunan: Xiangtan University, 2015.

[3] GUO A, YANG T. Research and improvement of feature words weight based on TFIDF algorithm[C]//Proceedings of the Information Technology, Networking, Electronic and Automation Control Conference(ITNEC 2016). Chongqing, China: IEEE, 2016: 415-419.

[4] MIHALCEA R, TARAU P. TextRank: Bringing order into texts[C]//Conference on Empirical Methods in Natural Language Processing, EMNLP 2004. Barcelona, Spain: [s.n.], 2004: 404-411.

[5] BRIN S, PAGE L. The anatomy of a large-scale hyper textual web search engine[C]//Proceedings of the 7th World Wide Web Conference (WWW7). Brisbane, Australia: [s.n.], 1998: 107-117.

[6] CANCHO R F I, SOLé R V. The small world of human language[J]. Proceedings Biological Sciences, 2001, 268(1482): 2261-2266.

[7] MATSUO Y, ISHIZUKA M. Keyword extraction from a single document using word co-occurrence statistical information[J]. Transactions of the Japanese Society for Artificial Intelligence, 2011, 13(17): 217-223.

[8] 任曉龍, 呂琳媛. 網(wǎng)絡(luò)重要節(jié)點排序方法綜述[J]. 科學(xué)通報, 2014, 59(13): 1175-1197.

REN Xiao-long, Lü Lin-yuan. Review of ranking nodes in complex networks[J]. Chin Sci Bull, 2014, 59(13): 1175-1197.

[9] 謝鳳宏, 張大為, 黃丹, 等. 基于加權(quán)復(fù)雜網(wǎng)絡(luò)的文本關(guān)鍵詞提取[J]. 系統(tǒng)科學(xué)與數(shù)學(xué), 2010, 30(11): 1592-1596.

XIE Feng-hong, ZHANG Da-wei, HUANG Dan, et al. Keywords extraction based on weighted complex network[J]. Journal of Systems Science and Mathematical Sciences, 2010, 30(11): 1592-1596.

[10] 唐俊. 復(fù)雜網(wǎng)絡(luò)在新聞網(wǎng)頁關(guān)鍵詞提取中的應(yīng)用[J]. 云南民族大學(xué)學(xué)報(自然科學(xué)版), 2012, 21(4): 305-308.

TANG Jun. Application of complex networks to keyword extraction of news web pages[J]. Journal of Yunnan Nationalities University: Natural Sciences Edition, 2012, 21(4): 305-308.

[11] 左曉飛. 基于復(fù)雜網(wǎng)絡(luò)的關(guān)鍵詞提取研究[D]. 西安: 西安電子科技大學(xué), 2013.

ZUO Xiao-fei. Research on keyword extraction based on complex network[D]. Xian: XiDian University, 2013.

[12] CHEN Q, JIANG Z, BIAN J. Chinese keyword extraction using semantically weighted network[C]//International Conference on Intelligent Human-Machine Systems & Cybernetics. [S.l.]: IEEE, 2014: 83-86.

[13] NAN J, XIAO B, LIN Z, et al. Keywords extraction from Chinese document based on complex network theory[C]// 2014 Seventh International Symposium on Computational Intelligence and Design (ISCID). [S.l.]: IEEE, 2015: 383-386.

[14] 劉通. 基于復(fù)雜網(wǎng)絡(luò)的文本關(guān)鍵詞提取算法研究[J]. 計算機應(yīng)用研究, 2016, 33(2): 365-369.

LIU Tong. Algorithm research of text key word extraction based on complex networks[J]. Application Research of Computers, 2016, 33(2): 365-369.

[15]張華平. ICTCLAS漢語分詞系統(tǒng)[EB/OL]. [2014-06-25]. http://ictclas.nlpir.org/.

ZHANG Hua-ping. ICTCLAS Chinese word segmentation system[EB/OL]. [2014-06-25]. http://ictclas.nlpir.org/.

編 輯 蔣 曉

Extraction from News Articles Based on PageRank Algorithm

GU Yi-ran and XU Meng-xin

(College of Automation, Nanjing University of Posts and Telecommunications Nanjing 210023)

Most of the existing methods of extracting keyword based on complex networks ignore the natural language characters when building the weighted text network. In the meantime, they involve less the classical algorithms in complex network field. Based on PageRank algorithm, we propose a keyword extraction method, named LTWPR (located and TF-weighted PageRank), which takes into consideration term-frequency character and human language characters. The algorithm creates a term-frequency-shared weight in order to share the node’s term-frequency value to its links, and defines a position weight coefficient to express different importance of words in different positions of news articles. LTWPR brings text networks’ local and global features into consideration, making the results more accurate. Comprehensive experiments are conducted based on news articles grabbed from Sina News. Experimental results show that LTWPR algorithm is more effective and can better cover the keywords tagged by authors.

complex networks; keyword extraction; natural language; PageRank; term-frequency- shared weight

TP311; TP391.1

A

10.3969/j.issn.1001-0548.2017.05.021

2016-09-16

2016-12-26

教育部人文社會科學(xué)研究規(guī)劃基金(15YJZH016)

顧亦然(1972-)，女，博士，教授，主要從事復(fù)雜網(wǎng)絡(luò)理論與應(yīng)用、嵌入式系統(tǒng)及通信網(wǎng)絡(luò)等方面的研究.