基于單DOM樹特征預分類的自適應Web信息抽取方法

彭艷兵，謝馨庭

（1.武漢郵電科學研究院 湖北 武漢 430074；2.南京烽火星空通信發展有限公司 江蘇 南京210019）

基于單DOM樹特征預分類的自適應Web信息抽取方法

彭艷兵1，2，謝馨庭1

（1.武漢郵電科學研究院 湖北 武漢 430074；2.南京烽火星空通信發展有限公司 江蘇 南京210019）

在傳統的輿情中多為基于模板采集模式，基于減少人工維護的目的，文中提出一種基于單DOM樹特征預分類的自適應Web信息抽取方法，分為鏈接預分類與信息抽取兩個部分。鏈接預分類采用SVM分類算法，提取信息超鏈接在頁面中的特征進行分類學習，再對分類結果進行同源的Web信息提取。實驗表明，此方法預分類結果準確率可達94.48%，召回率為94.77%。

DOM樹；標簽路徑；信息抽取；SVM

Abstract:In traditional public opinion，mostly based on the template in acquisition mode， based on the reduction of artificial maintenance purposes，we propose a method based on adaptive Web information extraction single DOM tree features pre-classification，divided into the pre-classification and information extraction link two parts.Links presorting using SVM classification algorithm to extract information about hyperlinks in the pages of features to classify learning，then the results of the classification homologous Web information extraction.Experimental results show that this method of preclassification accuracy rate of 94.48%，the recall rate was 94.77%.

Key words:DOM tree；tag path feature； information extraction；SVM

網絡輿情是指在一定社會空間內，通過網絡圍繞社會事件的發生，發展和變化，民眾對于公共問題和社會管理者產生和持有的社會政治態度，信念和價值觀，是國家相關部門了解民意的重要渠道，Web信息作為輿情系統進行輿情分析的信息輸入，采集是否準確，站點是否覆蓋全面覆蓋，直接影響了輿情系統的性能[1]。在傳統的輿情采集中，多采用的是基于模板的方法，對于各個站點進行模板化的定制，隨著站點覆蓋的越來越多，用于模板維護定制的人力也消耗的越來越大，為了快速準確地獲取輿情信息，輿情系統對Web信息抽取提出了越來越高的要求，因此如何讓計算機程序自動準確地從千變萬化的頁面中抽取出結構化的目標數據，一直是輿情系統待解決的問題。

目前比較流行的自動化信息抽取工具有MDR[2]、基于MDR的改進方法Depta[3]等，但這些方法對待抽取網頁中信息的結構化程度要求比較嚴格，但實際網絡中存在大量松散結構化信息的網頁。文獻[4]提出了一種基于文本內容相似度的網頁正文提取方法，但未考慮如何區分是否為同源頁面。文獻[5]提出了一種基于標簽路徑特征融合的在線Web新聞內容抽取方法，引入了頁面標簽路徑特征。

文中深入研究了網頁的超鏈接特征、文本特征和結構特征，構建了面向網絡輿情載體類型識別的特征集，在基于DOM自動生成模板的方法上引入機器學習中的分類算法對上層頁面中的信息超鏈接進行預分類，提出一種基于單DOM樹特征預分類的自適應Web信息抽取方法。

1 基于單DOM樹特征預分類

文中提出的基于單DOM樹預分類模塊如圖1所示。該模塊輸入的是各站點Web頁面，如首頁，各版塊列表等。將其預處理生成DOM樹后，提取其中所有超鏈接及其特征，進入分類器分類。而分類器是選取了20個站點頁面中所有鏈接訓練生成。

圖1 基于單DOM樹特征預分類流程圖

1.1 DOM樹與樹路徑

一個Web頁面可以用DOM樹表示，DOM即文檔對象模型，定義了HTML文檔和XML文檔的邏輯結構，給出了一種訪問和處理HTML文檔和XML文檔的方法，可以根據HTML文檔和XML文檔結構形成一棵對象節點樹，稱為DOM樹[6]。在一棵DOM樹中，各節點的位置可表示為從DOM樹的根節點到此節點所經過的所有節點標簽組成的序列，表示如下：

其中：m表示該路徑在DOM樹中出現的次數；（t1，t2，…，tn）表示該路徑所經歷的節點標簽組成的序列；（s1，s2，…，sm）表示該路徑出現的位置，DOM 樹所有的路徑的葉節點按遍歷排序，用順序號表示樹路徑的位置[7]。

樹路徑是一條從根節點到葉節點經過的所有標簽序列，傳統樹路徑匹配計算采用計算路徑序列的相似度，只考慮標簽序列，忽略了樹路徑標簽序列在頁面中出現的位置，計算出的相似度結果并不能真實有效地反應實際相似度，因此，本文采用了一種改進的基于樹路徑匹配的網頁結構相似度算法[8]。對于兩條樹路徑

它們之間的樹路徑相似度定義如下：

其中：

表示樹路徑的標簽序列相似度，clen（Pi，Pj）表示兩條路徑以根節點為開始的最長公共標簽序列長度[9]，len（Pi）表示路徑 Pi的標簽序列長度；

表示兩條樹路徑的位置相似度，md（sik）表示Pi路徑在位置sik處與Pj的最近距離：

pni和pnj分別表示Pi和Pj所在DOM樹的葉節點總數。

路徑相似度主要由 st（Pi，Pj）和 sp（Pi，Pj）兩部分組成，分別體現了路徑相似性中的標簽序列和位置信息，w為權重，取值0～1，改變w可調節這兩部分在路徑相似性中的重要性[10]。

例：圖2是一個簡單的網頁表示成DOM樹結構：

由于本文只考慮超鏈接特征，為簡化計算，忽略不包含＜a＞標簽路徑，故該頁面共有兩個樹路徑，第一條路徑P1出現了兩次，葉節點a由遍歷DOM樹得到的順序號為1和2，因此該路徑位置分別為1，2；第二條路徑P2出現了1次，位置為3。

圖2 網頁的DOM樹結構

1.2 特征提取

文中選擇支持向量機的分類算法，對頁面中抽取的超鏈接進行分類。在分類問題中，最重要的是樣本的特征選取，選取特征是否能夠反映分類問題的本質，這決定了分類模型的優劣。通過分析大量站點頁面，我們將每個頁面中的各超鏈接視為由超鏈接特征，文本特征及結構特征構成。

1.2.1 超鏈接特征

超鏈接既內容鏈接，是各網頁之間相互連接的有效路徑，我們用同一資源定位符（URL）表示，基本的URL包含協議，域名（或IP地址），路徑和文件名[11-12]。對于同一站點下的頁面，有效的信息帖子URL具有以下特征：與站點根域名相同，新聞帖子大多包含日期信息， 論壇 博客會 包 含 “bbs”，“thread”，“blog”，“club”等關鍵詞。我們將URL是否包含日期及關鍵詞作為特征，進入分類學習。

1.2.2 文本特征

超鏈接的文本特征，既該鏈接所對應的＜a＞標簽在DOM樹中所嵌套包含的文本內容。通過大量觀察，其文本內容大多為鏈接對應網頁的標題內容，標簽還會攜帶title屬性，且由于網頁排版限制，大多數帖子標題長度相似，而版塊鏈接文本多限制在2到4個字符，如新聞，社會，天涯雜談等。我們將＜a＞標簽所對應文本長度，及是否帶有title屬性作為特征，進入分類學習。

1.2.3 結構特征

根據本文第一節所述，每一個HTML頁面都可以由一棵DOM樹結構來描述，它可以將整個頁面內容抽象為不同的對象，用結點的方式來表示[13]。通過分析觀察，網頁中的超鏈接信息是較均勻的分布在頁面主體結構中。簡單的版塊列表頁面超鏈接都分布在同一區域結構內，而復雜的門戶型網頁，會存在多個信息超鏈接區域，單各個信息區域的分界是相似的，且XPATH結構路徑是相似的。其中每一個鏈接所在的最小結構體就是該鏈接所對應的＜a＞標簽在DOM樹中的XPATH路徑。基于以上特點，我們可將問題轉化為對于＜a＞標簽的路徑特征分析。首先，我們根據各鏈接的XPATH路徑進行分組，并用公式1表示各鏈接的樹路徑，相同的XPATH路徑歸為一組。對各組鏈接進行降序排列，選取鏈接數最大的組，應用公式計算其他超鏈接路徑與最大鏈接組路徑的相似度，而最大鏈接數組相似度計為1。將其作為結構特征。

1.3 分類算法

在本文的分類問題中，我們采用了支持向量機SVM算法，這是一個有監督的學習模型，它最終能將訓練樣本進行劃分，求得其最優超平面，它的優勢在于是基于系統風險最小化的原則，能夠根據有限的樣本對給予的任意樣本的識別能力和特定樣本的學習精度之間尋求到最佳的平衡，以達到最好的學習能力[14]。此算法在解決非線性小樣本及高維模式識別等問題中效果良好。應用于本文分類問題時，我們根據第二節所述提取特征，將其抽象表示，選取部分作為訓練數據集進行訓練學習，獲得學習模型。

2 同源頁面信息抽取

對于兩個同源Web信息頁面，他們具有相同的結構，頁面中不相同的部分即為我們所需抽取的信息內容。我們通過抽取算法比較兩個同源頁面之間的匹配與不匹配，以獲得一個此結構頁面的抽取模板。如下圖所示，首先我們將網頁預處理為DOM樹結構，選取同組的兩個同源頁面進行信息抽取計算，生成模板，再通過此模板抽取其他同組頁面的內容信息，將其結構化輸出。

在信息抽取計算中，其中心思想就是處理兩棵DOM樹之間的不匹配，我們將不匹配分為兩種情況，標簽不匹配與字符串不匹配，標簽不匹配又分為重復項與可選項兩種情況[15]。同源頁面中的字符串不匹配，很大程度是由于讀取數據庫內容的不同所造成的，即可認為，字符串不匹配的部分即為我們待抽取的信息內容。對于標簽不匹配中的重復項，我們需找到重復標簽結點組的最小重復結構，對此重復結構標記并按字符串不匹配處理，通過大量觀察可發現，頁面中出現的重復結構大多為論壇回貼，新聞評論及博客回復等，同為帶抽取的信息內容。而標簽不匹配中出現的可選項為信息缺省所導致，將其記錄標志，待其它頁面驗證。將所有不匹配節點標志記錄，并依據其結點屬性標簽內容等特征將其標準化輸出為抽取模板。其他同組頁面即可通過模板快速抽取信息，而無需進行再次計算。

圖3 同源頁面信息抽流程圖

3 實驗與結果

為了驗證自動化抽取模型的有效性，編程實現了相關功能算法，并對結果進行評價。在單DOM樹特征預分類模塊中，選取了21個站點頁面近一萬條頁面鏈接，包含門戶型綜合網站，主流論壇，政府官網等類型，其中16個站點頁面做為訓練集，其余5個站點頁面為測試集，同時也作為頁面信息抽取的測試集。

表1 訓練數據集站點

實驗預分類結果采用準確率與召回率作為評價指標，信息抽取采用準確率與完整性作為評價指標。

將訓練數據只提取超鏈接及文本特征與提取超鏈接，文本及結構特征兩種情況進行分類學習測試，對比加入結構特征后對整體分類的影響效果。

從表的實驗結果可以清楚看出，加入了頁面結構特征后對于結構單一型的站點頁面影響不大，但對于綜合門戶型網頁優化較大。最終總體準確率可達94.48%，召回率為94.77%。該特征提取可有效的滿足，在單頁面中提取其中的有效鏈接，節省了為各站點定制正則表達來匹配URL鏈接的人力時間。

我們選取了5個不同站點進行信息抽取驗證，與較流行的基于正文統計算法進行比較，對比結果如下表，可見在傳統的新聞站點，二者區別不大，而在含有大量圖片新聞的綜合門戶型網站及論壇等站點，本文提出的抽取方法具有較大優勢，且在基于鏈接預分類的基礎上，減少了大量的對比計算。

表2 基于單DOM樹特征預分類測試結果

表3 頁面信息抽取結果

4 結 論

文中提出了一種基于單DOM樹特征預分類的自適應Web信息抽取方法。針對同一頁面中的信息超鏈接，提取其超鏈接特征，文本特征及結構特征，采用SVM分類算法對其進行分類，再對分類結果進行同源的Web信息提取。實驗結果表明本文提出的方法具有較強的適用性，能有效地對新聞論壇等站點進行信息提取。目前的工作也存在一些不足，需要進一步開展相關的研究，如對于復雜的門戶型站點，具有較多的頁面樣式，在預分類模塊中丟失率較高；對于博客新聞類型頁面的評論回復無法準確識別。下步計劃在預分類中增加頁面類型識別，以在信息抽取的過程中針對不同類型頁面采取不同抽取方式。

[1]王元卓,靳小龍,程學旗等.網絡大數據:現狀與展望[J].計算機學報， 2013，36（6）:1126-1138.

[2]王志華，魏斌，李占波，等.基于本體的Web信息抽取系統[J].計算機工程與設計，2012，33（7）:2634-2639.

[3]陳釗，張冬梅.Web信息抽取技術綜述[J].計算機應用研究， 2010，27（12）:4401-4405.

[4]王利，劉宗田，王燕華，等.基于內容相似度的網頁正文提取[J].計算機工程，2010，36（6）:102-104.

[5]吳共慶，胡駿，李莉.基于標簽路徑特征融合的在線Web新聞內容抽取[J].軟件學報， 2016，27（3）:714-735.

[6]寇月，李冬，申德榮，等.D-EEM:一種基于DOM樹的Deep Web實體抽取機制 [J].計算機研究與發展，2010，47（5）:858-865.

[7]陳雪，梁永全，趙相彬.改進的基于本體的Web信息抽取[J].計算機應用與軟件，2013，30（7）:14-16.

[8]廖浩偉，楊燕，賈真，等.一種改進的基于樹路徑匹配的網頁結構相似度算法[J].吉林大學學報（理學版），2012，50（6）:1199-1203.

[9]高慶寧，吳鵬，張晶晶.基于文檔對象模型與行塊分布算法的網頁信息抽取[J].情報理論與實踐，2016，39（4）:133-137.

[10]岳國偉，呂楠，申玉三.基于領域本體的Web信息抽取模型研究[J].情報探索，2012（1）:105-107.

[11]史西兵，王浩鳴.隱馬爾可夫模型解決信息抽取問題的仿真研究 [J].計算機仿真，2010，27（5）:132-135.

[12]李偉男，李書琴，景旭，等.基于模擬退火算法和二階HMM的Web信息抽取 [J].計算機工程與設計， 2014，35（4）:1264-1268.

[13]李少天，肖基毅，虞樂.基于HMM和小波神經網絡混合模型的Web信息抽取[J].微計算機信息，2012（5）:136-138.

[14]許世明，武波，馬翠，等.一種基于預分類的高效SVM中文網頁分類器 [J].計算機工程與應用，2010，46（1）:125-128.

[15]岳國偉，呂楠，申玉三.基于領域本體的Web信息抽取模型研究[J].情報探索，2012（1）:105-107.

The adaptive Web information extraction based on single DOM tree characteristics and classification

PENG Yan-bing1，2， XIE Xin-ting1
（1.Wuhan Research Institute of Posts and Telecommunications，Wuhan 430074，China；2.Nanjing FiberhomeStarrysky CO.LTD.， Nanjing210019，China）

TN919.6

A

1674－6236（2017）19-0056-04

2016-08-06稿件編號201608050

彭艷兵（1974—），男，湖北洪湖人，博士，高級工程師。研究方向：海量數據分析，網絡行為分析。