基于DOM樹與模板的自適應(yīng)網(wǎng)絡(luò)信息抽取方法

柏志安 廖 健 曾劍平

(上海交通大學(xué)醫(yī)學(xué)院附屬瑞金醫(yī)院信息中心 上海 200025)2(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 200433)

0 引 言

基于HTML Web頁(yè)面的網(wǎng)絡(luò)信息表示方法是當(dāng)前的主流，在微博、論壇、傳統(tǒng)網(wǎng)站、公眾號(hào)等不同類型應(yīng)用中廣泛使用。由于Web頁(yè)面中通常包含大量與真正內(nèi)容無(wú)關(guān)的其他信息，因此，從中抽取有用信息一直是研究和應(yīng)用的重要基礎(chǔ)。Web信息抽取主要用于從網(wǎng)頁(yè)中提取符合要求的信息內(nèi)容，這些信息通常是以一定的HTML標(biāo)簽標(biāo)注的，對(duì)提取出來(lái)的信息內(nèi)容可以以一定的方式進(jìn)行組織和存儲(chǔ)，方便后續(xù)的分析或利用。

論壇型網(wǎng)站頁(yè)面結(jié)構(gòu)復(fù)雜，包含了主帖列表、回帖列表、帖子中的各種用戶信息和帖子內(nèi)容等眾多信息。針對(duì)這些信息的抽取，目前還是傾向于使用基于模版的信息抽取技術(shù)為特定的頁(yè)面結(jié)構(gòu)生成特定抽取規(guī)則。然而這種類型頁(yè)面經(jīng)常進(jìn)行改版，包括結(jié)構(gòu)組織和頁(yè)面內(nèi)容的調(diào)整等，這就導(dǎo)致抽取規(guī)則需要重新設(shè)計(jì)。其原因在于，目前信息抽取技術(shù)缺乏對(duì)網(wǎng)頁(yè)本身特性的利用，整體自動(dòng)化水平不高。因此，對(duì)于Web頁(yè)面信息抽取而言，具有很大的挑戰(zhàn)性，研究具有普適性且能夠應(yīng)對(duì)網(wǎng)頁(yè)結(jié)構(gòu)變化的自適應(yīng)信息抽取算法是非常有必要的。

1 相關(guān)工作

Web信息抽取的技術(shù)根據(jù)不同的歸類方法有不同的分類。從自動(dòng)化的程度來(lái)說(shuō)，可以分為非自動(dòng)化、半自動(dòng)化和全自動(dòng)化三類。從技術(shù)方法分類，可以分為基于視覺特征的方法、基于本體的方法、基于機(jī)器學(xué)習(xí)的方法、基于DOM樹結(jié)構(gòu)的方法和基于模版的方法[1]。

基于視覺特征的算法利用視覺上的距離進(jìn)行分塊來(lái)區(qū)分不同主題的數(shù)據(jù)，所使用的視覺特征有字體的大小和顏色、頁(yè)面背景顏色、間隔距離等。孫璐等[2]提出了一種基于視覺特征的Deep Web信息抽取方法,利用經(jīng)典的VIPS算法對(duì)頁(yè)面結(jié)構(gòu)進(jìn)行語(yǔ)義分塊,基于基準(zhǔn)視覺塊進(jìn)行信息抽取。

基于本體的信息抽取方法通常先對(duì)Web頁(yè)面進(jìn)行預(yù)處理，包括網(wǎng)頁(yè)分塊。然后對(duì)網(wǎng)頁(yè)文本進(jìn)行詞性和語(yǔ)法分析，需要設(shè)計(jì)合理完善的知識(shí)庫(kù)并構(gòu)建領(lǐng)域本體，最后解析文本生成抽取規(guī)則。文獻(xiàn)[3-4]提出了利用本體的方法抽取信息，或通過(guò)建立完整的本體得到抽取規(guī)則或是在Web信息抽取中利用領(lǐng)域本體知識(shí)。劉麗娟等[5]采用向量空間模型結(jié)合特征詞權(quán)值,利用本體思想分析并計(jì)算主題相關(guān)度,從而達(dá)到提高特定主題網(wǎng)頁(yè)信息抽取質(zhì)量的目的。

基于機(jī)器學(xué)習(xí)的抽取方法中，一類是利用實(shí)現(xiàn)觀察或分析結(jié)果定義若干能夠反映預(yù)期信息與噪聲信息差別的統(tǒng)計(jì)量，然后再進(jìn)行信息抽取。吳共慶等[6]結(jié)合標(biāo)簽路徑特征和文本塊密度的統(tǒng)計(jì)特征，提出了Web新聞信息抽取模型CEDP。李志義等[7]基于一類具有重復(fù)模式的頁(yè)面，提出了新的信息提取新方法，該方法利用聚類算法發(fā)現(xiàn)重復(fù)模式。另一類機(jī)器學(xué)習(xí)方法則引入一定的數(shù)學(xué)模型來(lái)描述抽取對(duì)象，劉志強(qiáng)等[8]將待抽取信息項(xiàng)視作為狀態(tài),將詞匯作為待抽取觀測(cè)項(xiàng)，從而提出基于改進(jìn)的隱馬爾可夫模型的網(wǎng)頁(yè)信息抽取方法，對(duì)新聞報(bào)道中的關(guān)鍵信息進(jìn)行抽取。深度學(xué)習(xí)方法也開始被用于Web信息抽取，趙朗[9]構(gòu)建了一種基于雙層循環(huán)神經(jīng)網(wǎng)絡(luò)的模型用于Web頁(yè)面信息的抽取。

節(jié)點(diǎn)及其子節(jié)點(diǎn)進(jìn)行篩選，只保留文字類型的子節(jié)點(diǎn)，最后形成獨(dú)立而完整的段落，并將其組成分段的網(wǎng)頁(yè)文本內(nèi)容。

基于模版的信息抽取針對(duì)的是通過(guò)讀取數(shù)據(jù)庫(kù)數(shù)據(jù)填充到統(tǒng)一模版生成的網(wǎng)頁(yè)。李寶密[15]提出了自動(dòng)生成模板的Web信息抽取方法，并將模板轉(zhuǎn)換成為結(jié)構(gòu)化形式。張方[16]提出了一種基于數(shù)據(jù)分塊的Web數(shù)據(jù)抽取規(guī)則生成算法,自動(dòng)生成基于Xpath和正則表達(dá)式的抽取規(guī)則模板。顧韻華等[17]結(jié)合DIV塊模板和表格模板，在領(lǐng)域本體指導(dǎo)下訓(xùn)練決策樹模型構(gòu)建DIV塊模板定位數(shù)據(jù)塊。

綜上所述，這五類Web頁(yè)面信息抽取方法在各自不同的角度上提出了抽取技術(shù)，基于視覺特征的抽取方法并無(wú)法區(qū)分信息塊中的有用信息，例如發(fā)帖人昵稱、發(fā)帖時(shí)間等。基于本體的方法則存在構(gòu)造本體的復(fù)雜問(wèn)題，并且抽取質(zhì)量與本體完整性有密切關(guān)系。基于模板的方法更偏向于人工分析的基礎(chǔ)上定義模板，在面對(duì)頁(yè)面改版時(shí)也會(huì)遇到很大問(wèn)題?；跈C(jī)器學(xué)習(xí)的方法試圖解決自適應(yīng)的問(wèn)題，但引入了閾值這類難以確定的參數(shù)或需要大量的標(biāo)注樣本。基于DOM樹具有直觀的方式，是HTML頁(yè)面表示的合適方法。

本文充分利用了DOM樹和模板的優(yōu)勢(shì)，提出新的方法解決頁(yè)面抽取的自適應(yīng)問(wèn)題。相對(duì)于現(xiàn)有Web信息抽取技術(shù),本文的創(chuàng)新點(diǎn)主要是：

(1) 針對(duì)論壇型網(wǎng)頁(yè)信息抽取，提出一種基于DOM樹與模板的自適應(yīng)信息抽取算法。算法以擁有共同父節(jié)點(diǎn)的鄰近結(jié)構(gòu)進(jìn)行子樹定位，通過(guò)文本長(zhǎng)度、鏈接文本長(zhǎng)度等特征對(duì)子樹內(nèi)各個(gè)節(jié)點(diǎn)進(jìn)行進(jìn)一步的細(xì)分，從而生成信息抽取規(guī)則。盡管DOM樹、模板是Web信息抽取的常用方法，但是當(dāng)前的方法不能充分利用這兩者的優(yōu)勢(shì)，導(dǎo)致Web頁(yè)面信息抽取時(shí)，難以解決頁(yè)面改版帶來(lái)的程序重寫問(wèn)題。

(2) 算法能夠自動(dòng)適應(yīng)實(shí)際應(yīng)用中的多種典型頁(yè)面改版操作，包括HTML標(biāo)簽類型、屬性和屬性值的增刪和修改，以及整個(gè)頁(yè)面中信息單元的位置移動(dòng)。本文方法能夠很好地針對(duì)這些改版自動(dòng)生成抽取規(guī)則并獲得比現(xiàn)有方法更好的抽取性能。

2 論壇型網(wǎng)頁(yè)特性

不同類型的網(wǎng)站由于功能與內(nèi)容偏重不同，頁(yè)面的布局往往相差很大。典型的新聞博客類網(wǎng)頁(yè)的布局通常是標(biāo)題位于上方，正文緊隨其后，這能很清楚地引導(dǎo)用戶關(guān)注標(biāo)題及正文的內(nèi)容。企業(yè)、學(xué)校等組織的官方網(wǎng)站則有導(dǎo)航和網(wǎng)站主體內(nèi)容分成兩個(gè)部分的頁(yè)面布局。本文算法針對(duì)的目標(biāo)是論壇型網(wǎng)頁(yè)，不同論壇板塊頁(yè)或稱目錄頁(yè)的布局大同小異，通常來(lái)說(shuō)就是一個(gè)以帖子標(biāo)題為主要元素的列表，而帖子內(nèi)的布局可以分為主帖+回復(fù)樓層和只有回復(fù)樓層兩種，如圖1和圖2所示。

圖1 主帖+回復(fù)樓層的帖內(nèi)頁(yè)面結(jié)構(gòu)

圖2 只有回復(fù)樓層的帖內(nèi)頁(yè)面結(jié)構(gòu)

對(duì)于圖1，不管從外觀還是從DOM樹的角度看，其主帖和下方的評(píng)論樓層都分屬不同的部分，可以容易地與評(píng)論樓層所在的區(qū)域區(qū)分開，因此，重點(diǎn)在于定位評(píng)論樓層所在的位置。

2.1 多變性

現(xiàn)代網(wǎng)頁(yè)多使用CSS文件來(lái)控制頁(yè)面布局外觀，實(shí)現(xiàn)了與html的分離。在設(shè)計(jì)得當(dāng)?shù)那闆r下，只要修改幾個(gè)CSS文件就可以同時(shí)對(duì)多個(gè)網(wǎng)頁(yè)進(jìn)行改版，在對(duì)應(yīng)的html標(biāo)簽的class屬性內(nèi)表明其歸屬類即可。也正是這種易修改性，使得網(wǎng)站設(shè)計(jì)人員進(jìn)行頁(yè)面改版變得更加容易。

此外，部分網(wǎng)站由于反爬蟲的需要，也會(huì)頻繁對(duì)節(jié)點(diǎn)屬性、節(jié)點(diǎn)標(biāo)簽，甚至是頁(yè)面結(jié)構(gòu)進(jìn)行改動(dòng)。對(duì)于通過(guò)xpath、css選擇器等方式定位節(jié)點(diǎn)再抓取信息的爬蟲采集方式，這種變動(dòng)會(huì)導(dǎo)致抽取規(guī)則在改版后完全失效，需要根據(jù)變化情況對(duì)規(guī)則進(jìn)行人工調(diào)整，耗時(shí)耗力。另外，通過(guò)嵌入html的JavaScript腳本，可以輕易增加、刪除DOM樹上的節(jié)點(diǎn)，修改已有節(jié)點(diǎn)的屬性、文本等。

因此，考慮到上述多種原因產(chǎn)生的頁(yè)面多變性，本文不關(guān)注特定節(jié)點(diǎn)本身，而是從DOM樹整體結(jié)構(gòu)入手。根據(jù)論壇型網(wǎng)頁(yè)的特性，比較DOM樹子樹之間的相似性，自動(dòng)化地分析并獲取能夠定位到所需節(jié)點(diǎn)的抽取模板。

2.2 子樹結(jié)構(gòu)的相似性

現(xiàn)代Web網(wǎng)頁(yè)基本上都是采用div+css布局或table布局，前者因?yàn)閾碛懈玫目删S護(hù)性和更佳的性能在近幾年使用更多。然而不管使用什么格式的布局，正常的網(wǎng)頁(yè)設(shè)計(jì)者為了保證網(wǎng)頁(yè)的功能和后續(xù)可維護(hù)，對(duì)頁(yè)面做出改版時(shí)都會(huì)遵循相似的原則。

網(wǎng)頁(yè)中每個(gè)樓層內(nèi)的元素和其排列順序基本一致，主要變化在于用戶ID、用戶評(píng)論、評(píng)論時(shí)間對(duì)應(yīng)節(jié)點(diǎn)的文本。查看網(wǎng)頁(yè)的源代碼，能夠發(fā)現(xiàn)在帖內(nèi)的不同樓層分別屬于擁有相同class屬性的獨(dú)立的div容器，且都聚集在上一層的div容器內(nèi)，樓層內(nèi)含有各個(gè)標(biāo)簽在div容器內(nèi)也是以同樣的順序排列。其下出現(xiàn)的標(biāo)簽、標(biāo)簽出現(xiàn)的次序、標(biāo)簽對(duì)應(yīng)的內(nèi)容，都是同樣的。因此從DOM樹的角度看，它們可以被視為掛在同一個(gè)父節(jié)點(diǎn)下的多棵結(jié)構(gòu)極度相似的子樹。

不管各個(gè)節(jié)點(diǎn)的文本內(nèi)容或者DOM樹整體結(jié)構(gòu)發(fā)生什么樣的改變，為了保證網(wǎng)頁(yè)符合用戶的使用習(xí)慣，用戶評(píng)論或回復(fù)樓層在視覺上必然集中在一個(gè)區(qū)域內(nèi)。為了實(shí)現(xiàn)這種設(shè)計(jì)，在DOM樹上它們也必然是掛在同一個(gè)上層節(jié)點(diǎn)下。這也就是說(shuō)，本文算法中定位有效信息所在子樹的核心思想是：在DOM樹上論壇帖內(nèi)各樓層回帖，表現(xiàn)為擁有共同父節(jié)點(diǎn)的鄰近的結(jié)構(gòu)極度相似的子樹。因此，可以認(rèn)為對(duì)于論壇型網(wǎng)頁(yè)來(lái)說(shuō)，通過(guò)識(shí)別相鄰的擁有相似結(jié)構(gòu)的子樹來(lái)選擇有效信息子樹，即使修改樓層的一些節(jié)點(diǎn)，只要它們多次重復(fù)出現(xiàn)且集中在相近區(qū)域內(nèi)，就能正確識(shí)別。只要識(shí)別出這些代表樓層的有效信息子樹的位置，就可以進(jìn)一步地通過(guò)文本長(zhǎng)度、鏈接文本長(zhǎng)度等特征對(duì)子樹內(nèi)各個(gè)節(jié)點(diǎn)進(jìn)行進(jìn)一步的細(xì)分，判別它們各自的信息類別。

3 算法流程

本文算法重點(diǎn)在于定位有效內(nèi)容對(duì)應(yīng)的標(biāo)簽，生成抽取規(guī)則并提取文本，這需要遍歷DOM樹上所有節(jié)點(diǎn)。算法整體流程如圖3所示，在遍歷過(guò)程中，根據(jù)class屬性對(duì)節(jié)點(diǎn)進(jìn)行第一步的粗篩選生成候選集。因?yàn)閔tml標(biāo)簽的class屬性可以有多個(gè)值，為了方便操作，將其屬性值拼合成以“.”連接的字符串的形式，并將這個(gè)字符串為稱為節(jié)點(diǎn)的class屬性串。接下來(lái)，獲取候選集內(nèi)所有class屬性串對(duì)應(yīng)節(jié)點(diǎn)的公共父節(jié)點(diǎn)，隨后再根據(jù)候選集內(nèi)的情況做下一步的細(xì)分。下面分階段說(shuō)明算法執(zhí)行過(guò)程和原理。

圖3 算法的整體結(jié)構(gòu)

3.1 生成候選集

要利用DOM樹進(jìn)行信息抽取，需要將HTML文檔轉(zhuǎn)換為對(duì)應(yīng)的DOM樹，之后，所需的回復(fù)樓層部分的信息變成了多棵結(jié)構(gòu)相似的子樹，且這些子樹的父節(jié)點(diǎn)擁有相同的標(biāo)簽和屬性。如果能得到這些子樹在DOM樹的位置，我們的問(wèn)題就可以轉(zhuǎn)換為對(duì)這些有效信息子樹的直接處理。

在根據(jù)html構(gòu)建DOM樹前需要過(guò)濾掉不存儲(chǔ)有效信息的html標(biāo)簽及其內(nèi)部?jī)?nèi)容，這些標(biāo)簽包括: