基于單DOM樹特征預(yù)分類的自適應(yīng)Web信息抽取方法

彭艷兵，謝馨庭

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

基于單DOM樹特征預(yù)分類的自適應(yīng)Web信息抽取方法

彭艷兵1，2，謝馨庭1

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

在傳統(tǒng)的輿情中多為基于模板采集模式，基于減少人工維護(hù)的目的，文中提出一種基于單DOM樹特征預(yù)分類的自適應(yīng)Web信息抽取方法，分為鏈接預(yù)分類與信息抽取兩個(gè)部分。鏈接預(yù)分類采用SVM分類算法，提取信息超鏈接在頁(yè)面中的特征進(jìn)行分類學(xué)習(xí)，再對(duì)分類結(jié)果進(jìn)行同源的Web信息提取。實(shí)驗(yàn)表明，此方法預(yù)分類結(jié)果準(zhǔn)確率可達(dá)94.48%，召回率為94.77%。

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

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

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

1 基于單DOM樹特征預(yù)分類

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

圖1 基于單DOM樹特征預(yù)分類流程圖

1.1 DOM樹與樹路徑

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

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

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

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

其中：

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

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

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

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

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

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

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

1.2 特征提取

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

1.2.1 超鏈接特征

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

1.2.2 文本特征

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

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

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

1.3 分類算法

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

2 同源頁(yè)面信息抽取

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

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

圖3 同源頁(yè)面信息抽流程圖

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

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

表1 訓(xùn)練數(shù)據(jù)集站點(diǎn)

實(shí)驗(yàn)預(yù)分類結(jié)果采用準(zhǔn)確率與召回率作為評(píng)價(jià)指標(biāo)，信息抽取采用準(zhǔn)確率與完整性作為評(píng)價(jià)指標(biāo)。

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

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

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

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

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

4 結(jié) 論

文中提出了一種基于單DOM樹特征預(yù)分類的自適應(yīng)Web信息抽取方法。針對(duì)同一頁(yè)面中的信息超鏈接，提取其超鏈接特征，文本特征及結(jié)構(gòu)特征，采用SVM分類算法對(duì)其進(jìn)行分類，再對(duì)分類結(jié)果進(jìn)行同源的Web信息提取。實(shí)驗(yàn)結(jié)果表明本文提出的方法具有較強(qiáng)的適用性，能有效地對(duì)新聞?wù)搲日军c(diǎn)進(jìn)行信息提取。目前的工作也存在一些不足，需要進(jìn)一步開(kāi)展相關(guān)的研究，如對(duì)于復(fù)雜的門戶型站點(diǎn)，具有較多的頁(yè)面樣式，在預(yù)分類模塊中丟失率較高；對(duì)于博客新聞?lì)愋晚?yè)面的評(píng)論回復(fù)無(wú)法準(zhǔn)確識(shí)別。下步計(jì)劃在預(yù)分類中增加頁(yè)面類型識(shí)別，以在信息抽取的過(guò)程中針對(duì)不同類型頁(yè)面采取不同抽取方式。

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

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

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

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

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

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

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

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

[9]高慶寧，吳鵬，張晶晶.基于文檔對(duì)象模型與行塊分布算法的網(wǎng)頁(yè)信息抽取[J].情報(bào)理論與實(shí)踐，2016，39（4）:133-137.

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

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

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

[13]李少天，肖基毅，虞樂(lè).基于HMM和小波神經(jīng)網(wǎng)絡(luò)混合模型的Web信息抽取[J].微計(jì)算機(jī)信息，2012（5）:136-138.

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

[15]岳國(guó)偉，呂楠，申玉三.基于領(lǐng)域本體的Web信息抽取模型研究[J].情報(bào)探索，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稿件編號(hào)201608050

彭艷兵（1974—），男，湖北洪湖人，博士，高級(jí)工程師。研究方向：海量數(shù)據(jù)分析，網(wǎng)絡(luò)行為分析。