基于密度及文本特征的新聞標題抽取算法

彭圳生,鞏青歌,高志強,段妍羽,曾子賢

(1. 武警工程大學 信息工程學院，陜西 西安 710086；2. 軍隊大數據與云計算重點實驗室，陜西 西安 710086)

0 引言

[1][2]。

相對于有著成熟研究的Web正文信息抽取技術[3-5]，新聞標題抽取技術的研究相對較少，其主要難點在于： 對于大量的復雜非規范網頁來說，無法根據某種統一的網頁結構或規則進行統一抽取，且新聞標題的特征不像正文一樣明顯[6]，在抽取的過程中，很容易被埋沒在正文中或者被遺漏，無法很好地與正文分開抽取。然而，只有從網頁中準確抽取出新聞標題，才能為后期信息檢索和文本挖掘提供準確依據。

1 相關工作

雖然新聞標題抽取是Web信息抽取中的一個重要課題，但這方面的研究目前還比較少[7]，尤其對于復雜不規范的網頁結構，尚未提出一種通用的新聞標題抽取方法。目前對新聞標題的抽取技術主要集中在： ①基于網頁規則[5,8-12]方法；②基于機器學習[1,7,13-17]方法;③基于相似度[18-21]方法。

針對基于網頁規則的新聞標題抽取技術研究，Zhang[9]等通過XPath規則自動抽取Web論壇內容，并通過統計和預測的方法自動生成抽取規則。Wang[10]等提出一種基于DOM樹的提取方法，將DOM樹轉化為STU-DOM樹，通過信息提取算法自動準確地從HTML文檔中提取有用的相關內容。

針對基于機器學習方法的新聞標題抽取技術研究，朱青[13]等將HTML格式及DOM樹結構等信息引入機器學習抽取過程中，實現對新聞標題的抽取。羅永蓮[7]等提出一種基于新聞特點與網頁標記信息的方法，將網頁標記和文本相似度作為機器學習的特征來提取新聞標題。

針對基于相似度的新聞標題抽取技術研究，李國華[18]等利用網頁標題和正文信息之間的關系，通過計算句子之間的相似度和對應權值確定新聞標題。Mohammadzadeh[21]等人將每個文本片段的內容與HTML文件中的標題進行比較，并實現了四種類型的相似性比較方法。

隨著網頁結構日趨復雜，網頁元素日趨多樣，網頁噪聲內容逐步增多，按照網頁結構和HTML標簽編寫規則并維護模板的統一抽取網頁信息的方法愈來愈不可行。一方面，隨著HTML和CSS的分離，樣式特征很難具有區分性質，重新標注網頁訓練集，而后再重新訓練機器學習，模型代價巨大，基于樣式特征的機器學習方法已經不再適用；另一方面，由于網頁編寫規則不統一，不同網站編寫的隨意性很大，基于網頁DOM結構和XPath的信息抽取方法很難保證抽取效果。因此基于網頁規則及基于機器學習的抽取方法的實用性和適用性極大降低。

本文將基于密度的正文抽取方法引入新聞標題的抽取方法中，過濾網頁中非文本信息(例如，鏈接、圖片、視頻等非文本網頁噪聲)的干擾，提出一種基于密度和文本特征的語料判定模型，通過判定模型將網頁劃分為語料區和標題候選區，利用Text Rank算法[22]從語料中計算key-value權重集合，結合改進的相似度計算方法從標題候選區域抽取出新聞標題。最后通過多源數據適應性實驗和傳統算法的對比實驗，驗證了算法的適用性和有效性。

2 抽取算法實現

基于密度及文本特征的新聞標題抽取算法(title extraction with density and text-features, TEDT)實現主要由三部分構成： 語料判定模型(corpus decision model, CDM)進行區域劃分；通過TextRank算法構建key-value權重集合，獲得詞(key)和詞對應的權重(value)；利用改進的相似度計算方法，從標題候選隊列中抽取新聞標題。

2.1 語料判定模型

對語料區和標題候選區進行劃分前，需要過濾Script、Style、Comment標簽，去除網頁特殊標記(包括空格)并只保留換行符“ ”，最后再過濾掉不包含中文文本信息的行，處理后的HTML網頁源代碼中由含有中文的文本行和換行符“ ”構成。新聞的正文區域和標題區域有如下特征。

(1) 正文一般在標題下方，兩者中間一般含有發布時間、新聞來源、編輯或者外部鏈接等信息。

(2) 新聞標題的文本特征表現為標題是對正文的概括，所以標題中關鍵詞多。此外，由于新聞標題的簡潔性，新聞標題含有的特殊符號少且一般沒有分句符。

(3) 正文具有連續性，即從正文開始到正文結束之間的內容一定為正文。正文部分(即使包含圖片、視頻和鏈接)文本行之間的間隔一般不超過10個換行符[5]；文本行之間如果沒有間隔，則必定屬于正文。

(4) 正文的文本行一般較長且含有分句符。

(5) 正文的頭部和尾部的文本特征表現為阿拉伯數字比較多，例如發布日期、發布時間和瀏覽次數等其它特殊標記。由于已經不屬于正文部分，所以分句符較少，且一些特殊的詞出現的頻率較高，如，“來源”、“編輯”、“收藏”、“分享”、“評論”、“閱讀”等。

根據以上關于網頁中新聞內容密度分布特性和新聞文本特征的分析，總結出以下特征變量：

(1) 純文本數(Pure Text Number, PTN): 一個文本行中包含中文字符的個數。

(2) 句數(Sentence Number, SN): 一個文本行中句子的個數，按照“，。；！？”的標點符號劃分。

(3) 數字數(Numerals Number, NN): 一個文本行中所包含的阿拉伯數字的個數。

(4) 特殊字符數(Special Characters Number, SCN): 一個文本行中“: - |《》”符號和其他不同于分隔句子的符號個數。

(5) 特殊中文字符(Special Chinese Characters, SCC): 在正文開始前與正文結束后出現頻率較高的詞語，如“來源、編輯、收藏、分享、評論、閱讀”等。

(6) 中心間隔(Center Distance,CD)： 當前文本行與上一個加入語料區文本行之間的換行符個數。

(7) 字符數(Characters Number, CN): 每個文本行中字符的個數，不管是漢字、英文還是符號都算作一個字符。

區域劃分的關鍵在于判別語料區和標題候選區，為保證所選取的語料都屬于正文，并在進入標題候選區之前語料選取判停，我們引入了風險因子，如式(1) 所示。

(1)

其中，α表示準備加入到語料區的文本行的權值，PTN表示該文本行的純文本數，∑leni*SCCi表示該文本行中所出現的第i個特殊中文字符數與該字符長度乘積的和，NN表示當前文本行中出現阿拉伯數字的個數，SCN表示當前文本行中出現的特殊字符的個數，SN表示當前文本行中分句符的個數。以上所有變量均有可能為0，因此ln中的分子、分母同時加上調節常量1。

風險因子ln部分的分母NN+SCN+∑leni*SCCi+1體現為： 加入語料庫中的文本行中，如果當前文本行中出現的阿拉伯數字、特殊字符數和特殊中文字符所占比重越大，則越有可能不屬于正文，ln部分的分子PTN-∑leni*SCCi+1體現為，加入語料庫中的文本行中，如果純文本數越多，特殊中文字符所占比重越小，則該行越有可能屬于正文。此外，當前文本行中分句符的個數SN體現為，如果加入語料區中的該行中含有的分句符越多，其越有可能屬于正文。

根據風險因子的計算公式，當α大于0時，將對應文本行加入語料區，當α小于0時可以認為選取的語料不屬于正文。結合正文連續性的特征，進一步得到語料判定模型(Corpus Decision Model, CDM)，如式(2)所示。

(2)

其中，CDMi是對加入語料庫的第i個文本行的判斷值，CDi表示當前加入語料區的文本行的中心間隔，即第i行與前一個加入語料區的文本行之間換行符“ ”的個數，CNi表示第i個文本行中字符的個數；當CDi為0且CNi不為0時，CDMi的判定值為1，表明在文本行與文本行之間沒有間隔且加入語料區的文本行不為空行的情況下，該文本行一定屬于語料區；當CDi≥10或CNi為0時，CDMi的判定值為0，表明當前文本行與其加于語料區中的上一文本行間隔距離大于10或者加入語料區的當前文本行為空行的情況下，該行一定不屬于語料區；當0

算法1CDM區域劃分算法偽代碼

程序輸入: HC(Html Code)

程序輸出: corpus, titleCandidateQueue

初始化變量

1： Corpus = []

2： titleCandidateQueue = []

3： HC←removeScript/Style/Label(HC)

初始語料選擇

4：Forall textLine in HC

5： PTN←chineseNumber(textLine)

6：EndFor

反向判定

8：FortextLine in HCstart

9： PTN←ChineseNumber (textLine)

10： SN←sentenceNumber (textLine)

11： NN←numeralsNumber (textLine)

12： SCN←specialCharactersNumber(textLine)

13： SCC←specialChineseCharacters (textLine)

14： CN←lenght(textLine)

15： CD←distance (textLine)

16：IfCD=0 and CN≠0

17： Corpus.append(textLine)

18：EndIf

19：IfCD≥10 or CN=0

20：Break(set textLine index as end)

21：EndIf

22：Ifα<0(αrefer to PTN,SN,NN,SCN,SCC)

23：Break(set textLine index as end)

24：Elsedo step 17

25：EndIf

26:EndFor

27： titleCandidateQueue.append(HC0～end)

正向判定

28：FortextLine in HCstart

29： do step 9～25

30：EndFor

為了展示網頁文本行區劃分的效果，以鳳凰資訊2017年12月26日新聞《技術創新領導未來： 小間距LED 2018年行業10大猜想》為例，經過算法1處理后，其網頁文本行被劃分成三個部分，其中第一個部分為新聞標題候選區(0～287行)，第二個部分為語料區(288～391行)，第三個部分(392～1 000行)直接舍棄，具體效果如圖1所示。

圖1 網頁文本行區域劃分效果圖

2.2 構建單詞權重集合

TextRank[22]是PageRank算法[23]的改進版，其算法核心如式(3)所示。

(3)

式(3)中，TextRank利用權重項ωji，表示兩個節點之間的邊連接的重要程度,其中d為阻尼系數，一般取值為0.85。對于一個給定的點Vi，ln(Vi)為指向Vi的點集合，Out(Vj)為Vj指向其他點的集合。利用TextRank構建單詞權重集合的具體算法如算法2所示。

算法2TextRank構建key-value權重集合算法偽代碼

2.3 計算標題候選隊列權重

在算法2輸出單詞權重集合的基礎上，根據改進的相似度公式計算標題候選隊列的相似度。在數據挖掘領域，通常采用Jaccard相似系數計算兩個含有布爾值度量對象之間的距離(相似度)，如式(5)所示。

(5)

(6)

(7)

在對β進行歸一化處理時，式(7)中的βi為標題候選隊列中選取的當前文本行的β值，βj(1≤j≤n)是標題候選隊列每個文本行的β值，n為標題候選隊列的長度值。

從新聞標題候選隊列中抽取新聞標題的算法偽代碼如算法3所示。

算法3改進Jaccard標題抽取算法偽代碼

在算法3中，首先利用改良的風險因子β過濾標題候選區中不具備新聞標題文本特性的候選項，而后通過改進Jaccard標題抽取算法抽取新聞標題。通過計算β

圖2 網頁文本行標題候選區密度分布

3 實驗與結果分析

為了驗證本文基于密度及文本特征新聞標題抽取算法(算法源代碼https://github.com/pzs741/TEDT)的有效性，設計兩組實驗:

(1) 針對主流新聞網站和復雜不規范新聞網站，測試算法的適用性。

(2) 與傳統的基于相似度和基于規則的新聞標題抽取算法進行對比，驗證算法的有效性。

3.1 測試樣本集

測試樣本主要來源于各大主流門戶網站和院校內部信息網，通過網絡爬蟲爬取了3 100個新聞網站并手工摘取并標注了新聞標題，其中主流門戶網2 050個，院校內部信息網1 050個，分為主流網站新聞標題和復雜不規則網站新聞標題兩個互不重疊數據集。

3.2 評價標準

抽取單一網頁新聞標題的準確率P，召回率R和F1值定義如式(8)所示。

(8)

其中，a是自動抽取的網頁新聞標題的字符序列，b是手工標注網頁新聞標題的字符序列，LCS(a,b)為a、b的最大公共子序列，.len是序列對應的長度。

為綜合評價TEDT算法對大量復雜不規范網頁的性能，采用平均準確率、平均召回率和平均F1的值作為評價指標，如式(9)所示。

(9)

其中，Pi,Ri,F1i分別是單個網頁的準確率、召回率和F1值，N為網頁集合的數量。抽取新聞標題的最終結果有四種情況，其主要受到TEDT算法中CDM區域劃分的影響。第一種抽取結果為準確的新聞標題，出現這種情況表示算法劃區是準確的；第二種抽取結果是含有雜質的新聞標題(一般為