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

彭艷兵，謝馨庭

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

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

彭艷兵1，2，謝馨庭1

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

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

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

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

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

1 基于單DOM樹特征預分類

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

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

1.1 DOM樹與樹路徑

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

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

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

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

其中：

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

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

pni和pnj分別表示Pi和Pj所在DOM樹的葉節(jié)點總數(shù)。

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

例：圖2是一個簡單的網(wǎng)頁表示成DOM樹結(jié)構(gòu)：

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

圖2 網(wǎng)頁的DOM樹結(jié)構(gòu)

1.2 特征提取

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

1.2.1 超鏈接特征

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

1.2.2 文本特征

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

1.2.3 結(jié)構(gòu)特征

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

1.3 分類算法

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

2 同源頁面信息抽取

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

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

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

3 實驗與結(jié)果

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

表1 訓練數(shù)據(jù)集站點

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

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

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

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

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

表3 頁面信息抽取結(jié)果

4 結(jié) 論

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

[1]王元卓,靳小龍,程學旗等.網(wǎng)絡大數(shù)據(jù):現(xiàn)狀與展望[J].計算機學報， 2013，36（6）:1126-1138.

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

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

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

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

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

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

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

[9]高慶寧，吳鵬，張晶晶.基于文檔對象模型與行塊分布算法的網(wǎng)頁信息抽取[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和小波神經(jīng)網(wǎng)絡混合模型的Web信息抽取[J].微計算機信息，2012（5）:136-138.

[14]許世明，武波，馬翠，等.一種基于預分類的高效SVM中文網(wǎng)頁分類器 [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—），男，湖北洪湖人，博士，高級工程師。研究方向：海量數(shù)據(jù)分析，網(wǎng)絡行為分析。