張 巍， 鄒曉明， 談鳳真

(中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院，山東 青島 266100)

?

基于視覺(jué)信息和標(biāo)簽路徑的數(shù)據(jù)抽取*

張 巍， 鄒曉明， 談鳳真

(中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院，山東 青島 266100)

結(jié)合網(wǎng)頁(yè)的視覺(jué)信息和DOM樹(shù)結(jié)構(gòu)，研究從Deep Web查詢(xún)結(jié)果頁(yè)面中抽取半結(jié)構(gòu)化數(shù)據(jù)的問(wèn)題。通過(guò)視覺(jué)塊與整個(gè)網(wǎng)頁(yè)的面積比定位數(shù)據(jù)區(qū)域。根據(jù)數(shù)據(jù)記錄兩兩相鄰等視覺(jué)特征找到包含數(shù)據(jù)記錄的一組節(jié)點(diǎn)，并通過(guò)比較各節(jié)點(diǎn)的DOM樹(shù)結(jié)構(gòu)的相似度去除噪音節(jié)點(diǎn)。根據(jù)xpath屬性將各條數(shù)據(jù)記錄的數(shù)據(jù)項(xiàng)對(duì)齊。對(duì)整個(gè)抽取過(guò)程生成模板，可以使抽取效率得到很大提高。對(duì)8個(gè)Deep Web網(wǎng)站進(jìn)行了抽取數(shù)據(jù)實(shí)驗(yàn)，結(jié)果表明本文方法是有效的。

Deep Web； 數(shù)據(jù)抽??； 視覺(jué)信息； 標(biāo)簽路徑

隨著互聯(lián)網(wǎng)的飛速發(fā)展，其中蘊(yùn)含了海量的信息可供利用。與Surface Web 相比, Deep Web 蘊(yùn)含的信息量是它的400～500 倍，并且其信息質(zhì)量和增長(zhǎng)速度要遠(yuǎn)遠(yuǎn)高于Surface Web。Deep Web覆蓋了現(xiàn)實(shí)世界中的各個(gè)領(lǐng)域，比如商業(yè)、教育、政府等，并且95%的信息可以公開(kāi)訪問(wèn)，因此如何有效獲取Deep Web信息并加以利用備受人們關(guān)注[1]。

Deep Web網(wǎng)頁(yè)的數(shù)據(jù)抽取一般有3種方法。手工方法：由編程人員通過(guò)觀察網(wǎng)頁(yè)的HTML源碼找出能夠定位目標(biāo)數(shù)據(jù)的一些模式，并根據(jù)這些模式抽取數(shù)據(jù)，這種方法能夠準(zhǔn)確地抽取數(shù)據(jù)，但是需要花費(fèi)大量的人力，并且抽取數(shù)據(jù)所用的模式不能適應(yīng)網(wǎng)頁(yè)的變化，所以不適合用于網(wǎng)頁(yè)的自動(dòng)抽取。半自動(dòng)方法：首先人工標(biāo)注一些網(wǎng)頁(yè)，并利用機(jī)器學(xué)習(xí)的算法學(xué)習(xí)到一組抽取數(shù)據(jù)的規(guī)則，然后利用這些規(guī)則從具有類(lèi)似格式的網(wǎng)頁(yè)中抽取數(shù)據(jù)，文獻(xiàn)[2-3]分別基于決策樹(shù)、SVM和CRF對(duì)數(shù)據(jù)的自動(dòng)抽取進(jìn)行了研究，這類(lèi)方法在一定程度上可以適應(yīng)網(wǎng)頁(yè)的變化，但是要得到一個(gè)好的模型，通常需要大量的人工標(biāo)注。全自動(dòng)方法：根據(jù)Deep Web頁(yè)面的特點(diǎn)自動(dòng)從網(wǎng)頁(yè)中尋找數(shù)據(jù)記錄，并將數(shù)據(jù)項(xiàng)對(duì)齊輸出。這種方法不需要手工參與，適合大量站點(diǎn)的自動(dòng)抽取。RoadRunner[4]通過(guò)比較多個(gè)樣本頁(yè)面的HTML結(jié)構(gòu)來(lái)推測(cè)共同模式。但隨著樣本數(shù)量的增加，效率會(huì)急劇下降。IEPAD[5]首先把頁(yè)面解析成HTML標(biāo)簽串，然后提出一種通過(guò)PAT樹(shù)進(jìn)行字符串匹配的方法識(shí)別數(shù)據(jù)記錄并抽取數(shù)據(jù)項(xiàng)。MDR[6]實(shí)現(xiàn)了數(shù)據(jù)記錄的抽取，通過(guò)挖掘多個(gè)相似的廣義節(jié)點(diǎn)來(lái)識(shí)別數(shù)據(jù)區(qū)域，其中每一個(gè)廣義節(jié)點(diǎn)對(duì)應(yīng)一條數(shù)據(jù)記錄。DEPTA[7]在MDR的基礎(chǔ)上，通過(guò)簡(jiǎn)單樹(shù)匹配算法對(duì)齊DOM子樹(shù)實(shí)現(xiàn)了數(shù)據(jù)項(xiàng)的對(duì)齊和抽取。但這2種方法都需要遍歷大量的節(jié)點(diǎn)，效率較低，而且也沒(méi)有實(shí)現(xiàn)模板，從而使每一個(gè)頁(yè)面都需要重復(fù)執(zhí)行復(fù)雜的抽取過(guò)程。VIPS[8]通過(guò)比較網(wǎng)頁(yè)元素的字體、顏色、是否超鏈接等視覺(jué)特征將頁(yè)面劃分成不同的視覺(jué)塊。ViDE[9]基于VIPS提出一種基于視覺(jué)信息的數(shù)據(jù)抽取方法，該方法在一定程度上克服了現(xiàn)有方法對(duì)HTML源文件的依賴(lài)，但是每次抽取數(shù)據(jù)都需要先計(jì)算頁(yè)面的視覺(jué)信息，這需要花費(fèi)大量的時(shí)間。

本文結(jié)合網(wǎng)頁(yè)的視覺(jué)信息和DOM樹(shù)結(jié)構(gòu)，提出一種從Deep Web查詢(xún)結(jié)果頁(yè)面中抽取半結(jié)構(gòu)化數(shù)據(jù)的自動(dòng)化方法。首先根據(jù)網(wǎng)頁(yè)的視覺(jué)特征來(lái)定位數(shù)據(jù)區(qū)域和數(shù)據(jù)記錄，然后利用數(shù)據(jù)記錄DOM樹(shù)結(jié)構(gòu)的相似性去除噪音節(jié)點(diǎn)，再通過(guò)xpath屬性來(lái)對(duì)齊數(shù)據(jù)項(xiàng)。最后生成抽取數(shù)據(jù)模板，從而可以對(duì)Deep Web頁(yè)面進(jìn)行高效、準(zhǔn)確地?cái)?shù)據(jù)抽取。

1 概述

Deep Web網(wǎng)站最顯著的特征是用戶向服務(wù)器提交關(guān)鍵字查詢(xún)，服務(wù)器查詢(xún)Web數(shù)據(jù)庫(kù)，并將結(jié)果加上格式控制后以網(wǎng)頁(yè)的形式返回，瀏覽器通過(guò)渲染網(wǎng)頁(yè)把結(jié)果表現(xiàn)出來(lái)。其中Web數(shù)據(jù)庫(kù)存放的是結(jié)構(gòu)化數(shù)據(jù)，但是返回結(jié)果是網(wǎng)頁(yè)形式的半結(jié)構(gòu)化數(shù)據(jù)，這些數(shù)據(jù)有一定的結(jié)構(gòu)，但是不同記錄的相應(yīng)字段沒(méi)有明確的對(duì)應(yīng)關(guān)系，各記錄的字段數(shù)目也不一樣，所以它們無(wú)法直接被利用，需要將其結(jié)構(gòu)化，并用圖5所示的存儲(chǔ)結(jié)構(gòu)保存為結(jié)構(gòu)化數(shù)據(jù)。網(wǎng)頁(yè)中顯示查詢(xún)結(jié)果的部分稱(chēng)為數(shù)據(jù)區(qū)域，通常由標(biāo)題、查詢(xún)結(jié)果列表、導(dǎo)航信息等組成。其中查詢(xún)結(jié)果列表稱(chēng)為數(shù)據(jù)記錄，也就是所要抽取的半結(jié)構(gòu)化數(shù)據(jù)，其它的是數(shù)據(jù)區(qū)域中的噪音。數(shù)據(jù)記錄的抽取，通?？梢酝ㄟ^(guò)以下三步來(lái)完成：

首先，定位數(shù)據(jù)區(qū)域。由于查詢(xún)結(jié)果頁(yè)面最主要的目的是突出查詢(xún)結(jié)果以方便用戶查看，所以其數(shù)據(jù)區(qū)域一般會(huì)放在頁(yè)面的明顯位置，并且占據(jù)網(wǎng)頁(yè)的大部分區(qū)域。根據(jù)Deep Web頁(yè)面的這個(gè)特點(diǎn)，可以通過(guò)查找與整個(gè)網(wǎng)頁(yè)的面積比大于某一個(gè)閾值的區(qū)域來(lái)定位到數(shù)據(jù)區(qū)域，如果這樣的區(qū)域有多個(gè)，則選擇面積最小的[6]。

第二，定位數(shù)據(jù)記錄。數(shù)據(jù)記錄是數(shù)據(jù)區(qū)域中的列表部分，這些數(shù)據(jù)記錄有相似的格式控制，即具有相似的標(biāo)簽名和樣式。將每一條數(shù)據(jù)記錄看作一棵DOM子樹(shù)，那么這些子樹(shù)除了葉子節(jié)點(diǎn)(數(shù)據(jù)項(xiàng))的值不同，其DOM樹(shù)結(jié)構(gòu)十分相似。所以遍歷數(shù)據(jù)區(qū)域得到它所有的孩子節(jié)點(diǎn)，并按標(biāo)簽名分類(lèi)，則數(shù)據(jù)記錄節(jié)點(diǎn)會(huì)在同一個(gè)類(lèi)別中。從數(shù)據(jù)記錄的視覺(jué)信息來(lái)看，無(wú)論他們?cè)趺磁帕?，其位置總是相鄰的。所以再將按?biāo)簽名得到的分類(lèi)按是否相鄰分類(lèi)，得到的互相相鄰并且面積之和大于數(shù)據(jù)區(qū)域面積的1/2以上的一組節(jié)點(diǎn)就會(huì)包含數(shù)據(jù)記錄，但是這組節(jié)點(diǎn)里還可能包含噪音。由于數(shù)據(jù)記錄節(jié)點(diǎn)之間的DOM樹(shù)結(jié)構(gòu)十分相似，而與噪音節(jié)點(diǎn)相差較大，所以通過(guò)比較他們的DOM樹(shù)的相似度，可以把噪音節(jié)點(diǎn)去除掉。

第三，對(duì)齊數(shù)據(jù)項(xiàng)。數(shù)據(jù)記錄由語(yǔ)義各不相同的項(xiàng)組成，每一個(gè)具有單獨(dú)語(yǔ)義的項(xiàng)稱(chēng)為數(shù)據(jù)項(xiàng)。例如當(dāng)當(dāng)網(wǎng)中關(guān)于一本書(shū)的數(shù)據(jù)記錄是“C++程序設(shè)計(jì) 2010年 清華大學(xué)出版社 價(jià)格：￥20 折扣：9折 ...”。這樣一條記錄顯然無(wú)法在實(shí)際中直接使用。需要進(jìn)一步把數(shù)據(jù)記錄分成不同的語(yǔ)義單位，例如“C++程序設(shè)計(jì)”、“ 清華大學(xué)出版社”、“價(jià)格：￥20”，并且將不同數(shù)據(jù)記錄的相同語(yǔ)義的數(shù)據(jù)項(xiàng)對(duì)齊。

另外，由于同一個(gè)Deep Web網(wǎng)站的查詢(xún)結(jié)果頁(yè)面的結(jié)構(gòu)十分相似，因此可以將首次抽取的網(wǎng)頁(yè)的一些參數(shù)保留下來(lái)作為模板，在其它類(lèi)似頁(yè)面的抽取中直接用來(lái)定位和對(duì)齊數(shù)據(jù)，這樣就不需要每一頁(yè)都重復(fù)復(fù)雜的抽取過(guò)程，可以大幅提高抽取效率。

2 定位數(shù)據(jù)區(qū)域

對(duì)于Deep Web的查詢(xún)結(jié)果頁(yè)面，按照功能一般可以分為以下幾部分：查詢(xún)區(qū)域、查詢(xún)結(jié)果的分類(lèi)、查詢(xún)結(jié)果列表以及廣告等。查詢(xún)區(qū)域包括搜索文本框、高級(jí)搜索、以及熱門(mén)搜索關(guān)鍵詞等，一般位于網(wǎng)頁(yè)的頂部；查詢(xún)結(jié)果的分類(lèi)是指將查詢(xún)結(jié)果按照地區(qū)或價(jià)格等屬性進(jìn)行分類(lèi)，點(diǎn)擊分類(lèi)中可以得到更具體的查詢(xún)結(jié)果。例如當(dāng)查詢(xún)一個(gè)城市的餐飲時(shí)，可以把查詢(xún)結(jié)果再按價(jià)格或中西餐分類(lèi)，當(dāng)點(diǎn)擊分類(lèi)時(shí)，可以得到更精確的查詢(xún)結(jié)果。查詢(xún)結(jié)果列表是整個(gè)頁(yè)面中最主要的部分，也就是我們要找的數(shù)據(jù)區(qū)域。

數(shù)據(jù)區(qū)域具有明顯的視覺(jué)特征。為了突出查詢(xún)結(jié)果，數(shù)據(jù)區(qū)域一般是頁(yè)面中面積最大的部分，并且它不會(huì)只位于網(wǎng)頁(yè)中線的一側(cè)。本文通過(guò)如下方法找到包含數(shù)據(jù)區(qū)域的節(jié)點(diǎn)：遍歷DOM樹(shù)，找到滿足下面條件的節(jié)點(diǎn)：

Area(node)/Area(body)>Tregion

如果這樣的節(jié)點(diǎn)有多個(gè)，將面積比最小的作為數(shù)據(jù)區(qū)域的節(jié)點(diǎn)。采集50個(gè)Deep Web查詢(xún)結(jié)果頁(yè)面作為樣本，并訓(xùn)練得到通過(guò)視覺(jué)信息定位數(shù)據(jù)區(qū)域的決策樹(shù)，當(dāng)Tregion為0.4時(shí)，可以準(zhǔn)確地定位到數(shù)據(jù)區(qū)域。

3 定位數(shù)據(jù)記錄

數(shù)據(jù)區(qū)域通常包括標(biāo)題、查詢(xún)結(jié)果列表、導(dǎo)航信息等，其中的查詢(xún)結(jié)果列表就是要抽取的數(shù)據(jù)記錄，定位數(shù)據(jù)記錄需要從數(shù)據(jù)區(qū)域中找到數(shù)據(jù)記錄的節(jié)點(diǎn)。通常分為兩步：

(1)將數(shù)據(jù)區(qū)域的所有孩子節(jié)點(diǎn)中標(biāo)簽名相同的分為一類(lèi)。由于數(shù)據(jù)記錄是由Web數(shù)據(jù)庫(kù)中的結(jié)構(gòu)化數(shù)據(jù)加上統(tǒng)一的格式控制產(chǎn)生，所以他們的DOM樹(shù)除了葉子節(jié)點(diǎn)(數(shù)據(jù)記錄的具體描述)外，其結(jié)構(gòu)十分相似，并且其根節(jié)點(diǎn)具有相同的標(biāo)簽名。在數(shù)據(jù)區(qū)域的DOM樹(shù)中，數(shù)據(jù)記錄節(jié)點(diǎn)的位置不盡相同，可能在同一個(gè)父節(jié)點(diǎn)下，也可能有不同的父節(jié)點(diǎn)(見(jiàn)圖1)。但如果將數(shù)據(jù)區(qū)域的孩子節(jié)點(diǎn)按標(biāo)簽名分類(lèi)，那么所有數(shù)據(jù)記錄節(jié)點(diǎn)會(huì)分在同一類(lèi)別中；

圖1 數(shù)據(jù)記錄節(jié)點(diǎn)在DOM樹(shù)中的位置Fig.1 Position of data record nodes in the DOM tree

(2)通過(guò)分析數(shù)據(jù)記錄的視覺(jué)特征，從第一步的分類(lèi)結(jié)果中找到包含數(shù)據(jù)記錄的類(lèi)別。這些視覺(jué)特征有：

①數(shù)據(jù)記錄是相鄰的，常見(jiàn)的數(shù)據(jù)記錄的排列方式有兩種：垂直分布和均勻分布，也會(huì)有其他的不規(guī)則的排列，如圖2所示。雖然數(shù)據(jù)記錄在網(wǎng)頁(yè)中的分布排列越來(lái)越豐富，但是這些排列方式共有的特點(diǎn)是每一條數(shù)據(jù)記錄都至少可以找到另外一條數(shù)據(jù)記錄與其相鄰。所以把對(duì)按標(biāo)簽名得到分類(lèi)再按是否相鄰分類(lèi)，則數(shù)據(jù)記錄節(jié)點(diǎn)位于標(biāo)簽名相同并且互相相鄰的類(lèi)別中；

圖2 數(shù)據(jù)記錄的分布

②數(shù)據(jù)區(qū)域一般包含標(biāo)題、數(shù)據(jù)記錄、導(dǎo)航信息等，但是數(shù)據(jù)記錄占數(shù)據(jù)區(qū)域的大部分，因此對(duì)于第1步得到標(biāo)簽名相同并且相鄰的分類(lèi)，如果分類(lèi)內(nèi)節(jié)點(diǎn)的面積之和大于數(shù)據(jù)區(qū)域面積的50%，就可以確定數(shù)據(jù)記錄包含在這一組節(jié)點(diǎn)中，但是這些節(jié)點(diǎn)中還可能包含標(biāo)題等噪音數(shù)據(jù)。定位數(shù)據(jù)記錄具體算法(見(jiàn)圖3)。

圖3 定位數(shù)據(jù)記錄的算法

該算法首先深度遍歷數(shù)據(jù)區(qū)域節(jié)點(diǎn)，得到其所有孩子節(jié)點(diǎn)。將這些孩子節(jié)點(diǎn)按標(biāo)簽名分類(lèi)，得到{Ci|0≤i

另外，在按相鄰位置分類(lèi)時(shí)，不需要判斷每一個(gè)標(biāo)簽名的分類(lèi)。因?yàn)镠TML標(biāo)簽按照標(biāo)記內(nèi)容的不同可以分為塊級(jí)元素和內(nèi)聯(lián)元素。塊級(jí)元素顯示的為一塊內(nèi)容，通常用于布局，如div，table等。內(nèi)聯(lián)元素是語(yǔ)義級(jí)的元素，它只能容納文本或者其他內(nèi)聯(lián)元素，如a，font等。顯然，數(shù)據(jù)記錄是對(duì)實(shí)體的具體描述，通常會(huì)包含多個(gè)數(shù)據(jù)項(xiàng)，只可能是塊級(jí)元素，因此只需考察塊級(jí)元素的分類(lèi)。

4 對(duì)齊數(shù)據(jù)項(xiàng)

4.1 去噪

數(shù)據(jù)區(qū)域通常由標(biāo)題、查詢(xún)結(jié)果列表、導(dǎo)航信息等組成。例如，在當(dāng)當(dāng)網(wǎng)的查詢(xún)結(jié)果頁(yè)面中，標(biāo)題是對(duì)數(shù)據(jù)記錄列屬性的說(shuō)明，如書(shū)名、價(jià)格等。查詢(xún)結(jié)果列表是對(duì)各屬性的具體描述。導(dǎo)航信息指“上一頁(yè) 下一頁(yè)”等。其中查詢(xún)結(jié)果列表以外的部分稱(chēng)為數(shù)據(jù)區(qū)域中的噪音。由于數(shù)據(jù)記錄的產(chǎn)生有統(tǒng)一的格式規(guī)則，所以各條數(shù)據(jù)記錄的DOM樹(shù)結(jié)構(gòu)十分相似。通過(guò)比較數(shù)據(jù)記錄節(jié)點(diǎn)和噪音節(jié)點(diǎn)的DOM樹(shù)結(jié)構(gòu)相似度就可以把兩者區(qū)分開(kāi)來(lái)。

圖4 數(shù)據(jù)記錄的DOM樹(shù)

(1)將數(shù)據(jù)記錄表示成xpath的集合。一條xpath是指從DOM樹(shù)的根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的標(biāo)簽路徑。數(shù)據(jù)記錄的根節(jié)點(diǎn)到所有葉子節(jié)點(diǎn)的xpath的集合記為xpaths，可以用{xpathij|0≤j

(2)由于數(shù)據(jù)項(xiàng)中可選項(xiàng)的存在，兩條數(shù)據(jù)記錄的DOM樹(shù)結(jié)構(gòu)可能不會(huì)完全相同，因此只要xpaths1和xpaths2的相似度大于一個(gè)閾值，就可以認(rèn)為二者具有相似的DOM樹(shù)結(jié)構(gòu)。本文中采用的閾值為0.6。xpaths1和xpaths2的相似度計(jì)算公式是：

intersection是指xpaths1和xpaths2中相同的xpath的數(shù)目；union是指xpaths1和xpaths2形成的集合中xpath的數(shù)目。只有2條xpath完全一致時(shí)才認(rèn)為相等。

4.2 對(duì)齊數(shù)據(jù)項(xiàng)

在查詢(xún)結(jié)果頁(yè)面中，每一條數(shù)據(jù)記錄包含若干個(gè)數(shù)據(jù)項(xiàng)，由于可選項(xiàng)的存在，各條數(shù)據(jù)記錄中包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)不一定相同。例如當(dāng)當(dāng)網(wǎng)中，每一條數(shù)據(jù)記錄包含的數(shù)據(jù)項(xiàng)是：書(shū)名、出版時(shí)間、出版社、作者、價(jià)格、折扣等，其中折扣是可選項(xiàng)，某些數(shù)據(jù)記錄中可能不包含折扣信息；另外，有的網(wǎng)站中每本圖書(shū)會(huì)有一個(gè)標(biāo)簽，如“專(zhuān)業(yè) 最新 適合入門(mén)”，作為讀者對(duì)該書(shū)的評(píng)價(jià)，顯然所有的評(píng)價(jià)應(yīng)該作為一個(gè)數(shù)據(jù)項(xiàng)，但是每本書(shū)的評(píng)價(jià)關(guān)鍵詞的數(shù)量是不一定的，在數(shù)據(jù)項(xiàng)對(duì)齊之前先要確定將那幾個(gè)項(xiàng)作為一個(gè)數(shù)據(jù)項(xiàng)。所以可選項(xiàng)的存在和數(shù)據(jù)項(xiàng)的長(zhǎng)度(指一個(gè)語(yǔ)義完整的數(shù)據(jù)項(xiàng)包含的項(xiàng)的個(gè)數(shù))可變是數(shù)據(jù)項(xiàng)對(duì)齊的主要問(wèn)題。

(1)確定數(shù)據(jù)項(xiàng)的粒度，即一條數(shù)據(jù)記錄中那幾項(xiàng)可以作為一個(gè)數(shù)據(jù)項(xiàng)。將數(shù)據(jù)記錄中的每一個(gè)葉子節(jié)點(diǎn)看作一個(gè)項(xiàng)，它是數(shù)據(jù)記錄中的最小單位。其中某些項(xiàng)關(guān)系比較密切，應(yīng)該把它們做為一個(gè)數(shù)據(jù)項(xiàng)來(lái)看。理想的情況是將通常人所觀察到的語(yǔ)義單位作為一個(gè)數(shù)據(jù)項(xiàng)，這樣的一個(gè)數(shù)據(jù)項(xiàng)可能包含一個(gè)或多個(gè)項(xiàng)。例如數(shù)據(jù)項(xiàng)“標(biāo)簽：專(zhuān)業(yè) 最新 適合入門(mén)”，其中每個(gè)詞語(yǔ)為一個(gè)項(xiàng)，由于這幾個(gè)項(xiàng)之間語(yǔ)義聯(lián)系緊密，就作為一個(gè)數(shù)據(jù)項(xiàng)來(lái)看。從數(shù)據(jù)記錄的產(chǎn)生來(lái)看，數(shù)據(jù)項(xiàng)之間的區(qū)分主要是給不同的數(shù)據(jù)項(xiàng)加上不同的格式控制，使同一數(shù)據(jù)項(xiàng)的各個(gè)項(xiàng)之間的視覺(jué)特征相似，并且同一數(shù)據(jù)項(xiàng)的項(xiàng)的間隔較小，不同的數(shù)據(jù)項(xiàng)的間隔較大。但是視覺(jué)信息對(duì)數(shù)據(jù)項(xiàng)的區(qū)分只是起到輔助作用，更主要的是人對(duì)數(shù)據(jù)項(xiàng)的語(yǔ)義的理解。假如將“標(biāo)簽：專(zhuān)業(yè) 最新”換成“標(biāo)簽：專(zhuān)業(yè) 清華大學(xué)出版社”，雖然這個(gè)數(shù)據(jù)項(xiàng)的視覺(jué)特征沒(méi)有變，但是我們會(huì)把后面的理解成兩個(gè)數(shù)據(jù)項(xiàng)。由于語(yǔ)義的處理較為復(fù)雜，本文采用一種較簡(jiǎn)單的方法來(lái)確定數(shù)據(jù)項(xiàng)。

遍歷數(shù)據(jù)記錄的孩子節(jié)點(diǎn)，如果遇到文本節(jié)點(diǎn)，就將它的父節(jié)點(diǎn)的內(nèi)容作為一個(gè)數(shù)據(jù)項(xiàng)。這樣得到的數(shù)據(jù)項(xiàng)可能將理想的數(shù)據(jù)項(xiàng)分成多個(gè)，如將“標(biāo)簽：專(zhuān)業(yè) 最新”分成“標(biāo)簽：”“專(zhuān)業(yè)”“最新”。再將得到的數(shù)據(jù)項(xiàng)，按照其在網(wǎng)頁(yè)中的位置從上到下、從左到右排列。這樣雖然這三個(gè)數(shù)據(jù)項(xiàng)是分開(kāi)的，但他們?cè)跀?shù)據(jù)記錄中的位置仍然是相鄰的，可以再根據(jù)語(yǔ)義將它們合并，本文暫不做討論。

(2)得到數(shù)據(jù)項(xiàng)的xpath，并將它作為數(shù)據(jù)項(xiàng)的對(duì)齊屬性。數(shù)據(jù)項(xiàng)的xpath是指從數(shù)據(jù)記錄的根節(jié)點(diǎn)到數(shù)據(jù)項(xiàng)(葉子節(jié)點(diǎn))之間的標(biāo)簽路徑。在一條數(shù)據(jù)記錄的DOM樹(shù)中，對(duì)于兩個(gè)不同的葉子節(jié)點(diǎn)，從根節(jié)點(diǎn)到他們的標(biāo)簽路徑可能完全一樣，所以數(shù)據(jù)項(xiàng)的xpath有可能重復(fù)。在Deep Web頁(yè)面中，不同的數(shù)據(jù)項(xiàng)一般會(huì)通過(guò)元素的class屬性對(duì)其有不同的格式控制，因此對(duì)xpath上的每個(gè)元素取兩個(gè)值：標(biāo)簽名和節(jié)點(diǎn)的class屬性。這樣xpath就能很好的區(qū)分不同的數(shù)據(jù)項(xiàng)。

(3)對(duì)齊算法。得到所有的數(shù)據(jù)項(xiàng)及其xpath后，需要將不同數(shù)據(jù)記錄中相應(yīng)數(shù)據(jù)項(xiàng)對(duì)齊。首先將每條數(shù)據(jù)記錄的數(shù)據(jù)項(xiàng)按照其在網(wǎng)頁(yè)中的位置從上至下、從左至右排列。為了便于對(duì)齊，設(shè)計(jì)了一個(gè)類(lèi)似二維數(shù)組的數(shù)據(jù)結(jié)構(gòu)來(lái)保存數(shù)據(jù)項(xiàng)，如圖5，記為Record[m+1][n]，m表示數(shù)據(jù)記錄的條數(shù)，n表示數(shù)據(jù)記錄的xpath的條數(shù)。Record[0] [J]表示xpathj的屬性信息，并與Record[i] [J] (0

圖5 保存數(shù)據(jù)項(xiàng)的存儲(chǔ)結(jié)構(gòu)

圖6 對(duì)齊數(shù)據(jù)項(xiàng)的算法Fig.6 Algorithm of aligning data items

當(dāng)插入數(shù)據(jù)記錄DRi的第j個(gè)數(shù)據(jù)項(xiàng)時(shí)，首先查找xpath[n2]中是否存在該數(shù)據(jù)項(xiàng)對(duì)應(yīng)的xpath，如果存在，直接在Record2的相應(yīng)位置存入數(shù)據(jù)項(xiàng)的值；否則說(shuō)明此數(shù)據(jù)項(xiàng)是一個(gè)可選項(xiàng)，先在Record2中上次插入的位置之后新建一列，然后保存此數(shù)據(jù)項(xiàng)，并將其xpath也插入到xpath[n2]中。

5 模板

在Deep Web數(shù)據(jù)抽取中，由程序自動(dòng)定位數(shù)據(jù)區(qū)域和數(shù)據(jù)記錄以及對(duì)齊數(shù)據(jù)項(xiàng)，這個(gè)過(guò)程需要對(duì)各個(gè)節(jié)點(diǎn)進(jìn)行大量的遍歷和計(jì)算。由于Deep Web頁(yè)面是動(dòng)態(tài)生成的，所以數(shù)據(jù)記錄都有固定的模式。當(dāng)數(shù)據(jù)區(qū)和數(shù)據(jù)記錄定位后，可以把相關(guān)的屬性保存下來(lái)作為模板參數(shù)，利用模板抽取同一網(wǎng)站的其他頁(yè)面，可以使抽取的效率大幅提高。

5.1 數(shù)據(jù)區(qū)域和數(shù)據(jù)記錄的模板

Deep Web網(wǎng)頁(yè)最顯著的特點(diǎn)是它們是查詢(xún)Web數(shù)據(jù)庫(kù)后動(dòng)態(tài)生成的，有統(tǒng)一的格式控制，所以對(duì)于同一網(wǎng)站的不同頁(yè)面，數(shù)據(jù)區(qū)域部分的網(wǎng)頁(yè)格式是基本一樣的。當(dāng)數(shù)據(jù)區(qū)域定位以后，可以記錄數(shù)據(jù)區(qū)域的節(jié)點(diǎn)信息作為模板，如標(biāo)簽名、BODY節(jié)點(diǎn)到數(shù)據(jù)區(qū)域節(jié)點(diǎn)的標(biāo)簽路徑等。由于每個(gè)頁(yè)面的數(shù)據(jù)區(qū)域節(jié)點(diǎn)有相同的格式，因此可以根據(jù)模板信息直接定位數(shù)據(jù)區(qū)域，而不必遍歷所有的節(jié)點(diǎn)。

同樣，同一網(wǎng)站的數(shù)據(jù)記錄也有相同的格式控制，把數(shù)據(jù)記錄的節(jié)點(diǎn)信息作為它的模板，則定位數(shù)據(jù)記錄時(shí)只需要判斷符合模板信息的節(jié)點(diǎn)。

5.2 對(duì)齊數(shù)據(jù)項(xiàng)的模板

由于可選項(xiàng)的存在，不同數(shù)據(jù)記錄所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)不同，所以需要對(duì)齊。但是，數(shù)據(jù)記錄中的可選項(xiàng)只是少數(shù)，一般是1～2項(xiàng)，而且包含可選項(xiàng)的數(shù)據(jù)記錄可以認(rèn)為是信息比較豐富的，一般會(huì)放在查詢(xún)結(jié)果列表中比較靠前的位置。這樣通過(guò)第一頁(yè)的抽取，基本所有的可選項(xiàng)都會(huì)出現(xiàn)。

將第一頁(yè)的數(shù)據(jù)項(xiàng)對(duì)齊后所有數(shù)據(jù)項(xiàng)的xpath作為對(duì)齊數(shù)據(jù)項(xiàng)的模板，這個(gè)模板基本包含所有的可選項(xiàng)。當(dāng)利用該模板對(duì)齊其他頁(yè)面的數(shù)據(jù)時(shí)，若出現(xiàn)新的可選項(xiàng)，也將其xpath插入來(lái)更新模板。另外，利用模板來(lái)對(duì)齊數(shù)據(jù)的好處是可以對(duì)齊多頁(yè)數(shù)據(jù)。

總之，當(dāng)首次抽取某個(gè)Deep Web網(wǎng)站的數(shù)據(jù)時(shí)，首先定位數(shù)據(jù)區(qū)域和數(shù)據(jù)記錄，然后對(duì)齊和保存數(shù)據(jù)項(xiàng)，并保存相應(yīng)的模板。由于Deep Web網(wǎng)站的數(shù)據(jù)一般會(huì)分頁(yè)顯示，通常會(huì)有“下一頁(yè)”“Next”等關(guān)鍵字提示，可以利用啟發(fā)式規(guī)則自動(dòng)點(diǎn)擊翻頁(yè)。當(dāng)抽取后面的類(lèi)似結(jié)構(gòu)網(wǎng)頁(yè)時(shí)，就可以利用已經(jīng)保存的模板來(lái)抽取數(shù)據(jù)，使抽取效率得到很大提高。若由于網(wǎng)站改版等原因使網(wǎng)頁(yè)的結(jié)構(gòu)發(fā)生變化，已保存的模板不能抽取當(dāng)前頁(yè)面的內(nèi)容，則需要重新進(jìn)行定位數(shù)據(jù)區(qū)域等操作，并得到新的模板。

6 實(shí)驗(yàn)

為了驗(yàn)證基于視覺(jué)信息和標(biāo)簽路徑的數(shù)據(jù)抽取算法的準(zhǔn)確率，本文通過(guò)Webbrowser控件來(lái)渲染網(wǎng)頁(yè)，實(shí)現(xiàn)了原型系統(tǒng)。本節(jié)給出實(shí)驗(yàn)結(jié)果。

6.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)的數(shù)據(jù)來(lái)自購(gòu)物、招聘等8個(gè)Deep Web網(wǎng)站，通過(guò)對(duì)每個(gè)網(wǎng)站的查詢(xún)?nèi)肟谔峤魂P(guān)鍵詞獲得查詢(xún)結(jié)果頁(yè)面。通常情況下，若數(shù)據(jù)記錄中包含可選項(xiàng)，在前兩頁(yè)中都會(huì)出現(xiàn)，因此，對(duì)每個(gè)網(wǎng)站抽取前兩頁(yè)數(shù)據(jù)作測(cè)試。

6.2 數(shù)據(jù)記錄的實(shí)驗(yàn)結(jié)果

選用DEPTA算法作為對(duì)比，因?yàn)樗抢肈OM樹(shù)抽取數(shù)據(jù)的典型算法。查準(zhǔn)率是指抽取的數(shù)據(jù)記錄占抽取的所有記錄的比例，查全率是指抽取的數(shù)據(jù)記錄占網(wǎng)頁(yè)中所有數(shù)據(jù)記錄的比例。表1是對(duì)八個(gè)網(wǎng)站(見(jiàn)表2)進(jìn)行抽取實(shí)驗(yàn)后兩種算法的比較：

表1 本文算法和DEPTA的比較Table 1 Comparison of our method and DEPTA /%

從表中可以看出，本文的方法能夠準(zhǔn)確地定位數(shù)據(jù)區(qū)域和去除噪音，因而抽取的數(shù)據(jù)記錄有較高的準(zhǔn)確率，但是也有部分?jǐn)?shù)據(jù)記錄沒(méi)有找到。這是因?yàn)?，有個(gè)別網(wǎng)頁(yè)使用WebBrowser不能正確渲染，得不到相應(yīng)的DOM樹(shù)，無(wú)法抽取數(shù)據(jù)。

6.3 數(shù)據(jù)項(xiàng)的對(duì)齊實(shí)驗(yàn)

找到數(shù)據(jù)記錄后，遍歷其子節(jié)點(diǎn)就可以得到數(shù)據(jù)項(xiàng)，因此數(shù)據(jù)項(xiàng)的查準(zhǔn)率、查全率和數(shù)據(jù)記錄基本相同。但是對(duì)于數(shù)據(jù)項(xiàng)，更關(guān)注不同數(shù)據(jù)記錄的數(shù)據(jù)項(xiàng)是否對(duì)齊，因?yàn)榧词顾械臄?shù)據(jù)項(xiàng)都找到并且全部準(zhǔn)確，如果具有相同語(yǔ)義的項(xiàng)沒(méi)有對(duì)齊，這樣的數(shù)據(jù)也無(wú)法利用。表2列出了選取的8個(gè)網(wǎng)站的對(duì)齊結(jié)果，第二列是本文算法得到的數(shù)據(jù)項(xiàng)的列數(shù)，第三列是能夠?qū)R的列數(shù)。

從表中可以得到，對(duì)齊的平均準(zhǔn)確率只有84.5%。由于本文對(duì)齊的依據(jù)是數(shù)據(jù)項(xiàng)的xpath，但是xpath不是唯一的，不同的數(shù)據(jù)項(xiàng)可能有相同的標(biāo)簽名和class屬性，使不同的數(shù)據(jù)項(xiàng)放在同一列。而且同一列數(shù)據(jù)項(xiàng)的class屬性也可能不一樣，這樣會(huì)使相同的數(shù)據(jù)項(xiàng)放在不同列?？傊?，如何確定數(shù)據(jù)項(xiàng)的分割粒度以及對(duì)齊所依賴(lài)的屬性還有待進(jìn)一步的研究。

表2 數(shù)據(jù)項(xiàng)對(duì)齊的準(zhǔn)確率Table 2 Alignment accuracy of data item

7 結(jié)語(yǔ)

本文針對(duì)從Deep Web頁(yè)面中抽取半結(jié)構(gòu)化數(shù)據(jù)的問(wèn)題，提出了一種通過(guò)視覺(jué)信息和標(biāo)簽路徑進(jìn)行自動(dòng)抽取的方法。首先通過(guò)計(jì)算視覺(jué)塊與整個(gè)網(wǎng)頁(yè)的面積比定位數(shù)據(jù)區(qū)域。然后根據(jù)數(shù)據(jù)記錄兩兩相鄰等視覺(jué)特征找到包含數(shù)據(jù)記錄的一組節(jié)點(diǎn)，并通過(guò)比較各節(jié)點(diǎn)的DOM樹(shù)結(jié)構(gòu)的相似度去除噪音節(jié)點(diǎn)。再根據(jù)xpath屬性將各條數(shù)據(jù)記錄的數(shù)據(jù)項(xiàng)對(duì)齊，最后對(duì)抽取過(guò)程生成模板。實(shí)驗(yàn)表明，本文抽取的數(shù)據(jù)記錄達(dá)到了較高的準(zhǔn)確率。未來(lái)的工作將考慮通過(guò)數(shù)據(jù)項(xiàng)的語(yǔ)義來(lái)劃分?jǐn)?shù)據(jù)記錄，并提高數(shù)據(jù)項(xiàng)對(duì)齊的準(zhǔn)確率。

[1] 劉偉. Deep Web數(shù)據(jù)集成研究綜述 [J]. 計(jì)算機(jī)學(xué)報(bào)， 2007, 30(9)： 1475-1489.

[2] Wang Y, Hu J. A machine learning based approach for table detection on the Web [C].//Proc of the 11th Int Conf on World Wide Web. New York: ACM, 2002: 242-250.

[3] Pinto D, McCallum A, Wei X. Table extraction using conditional random fields [C].//Proc of the 26th Annual Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2003: 235-242.

[4] Crescenzi V, Mecca G, Merialdo P. Road-runner: Towards Automatic Data Extraction from Large Web Sites[C].//Proc of the 26th Int'l Conf. on Very Large Database Systems. Roma, Italy: [s.n.], 2001: 109-118.

[5] Chang Chia-Hui, Lui C. IEPAD: Information Extraction Based on Pattern Discovery[C].//Proceedings of the 10th International Conference on World Wide Web. Hong Kong: [s.n.], 2001: 681-688.

[6] Liu B, Grossman R L, Zhai Yanhong. Mining data records in Web pages [C].// Proc of the 9th Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2003: 601-606.

[7] Zhai Y, Liu B. Web data extraction based on partial tree alignment [C].// Proc of the 14th Int Conf on World Wide Web. New York: ACM, 2005: 76-85.

[8] Cai D, Yu S, Wen J R, et al. VIPS: a vision-based page segmentation algorithm [R]. Microsoft Technical Report, MSR-TR-2003-79, 2003.

[9] Liu W, Meng X, Meng W. Vision-based Web data records extraction [C].// Proc of the 9th Int Workshop in Web and Databases. New York: ACM, 2006: 20-25.

責(zé)任編輯 陳呈超

Data Extraction Based on Vision and Tag Path

ZHANG Wei, ZOU Xiao-Ming, TAN Feng-Zhen

(College of Information Science and Engineering, Ocean University of China, Qingdao 266100, China)

Semi-structured data extracted from Deep Web query results page is studied, based on the visual information and DOM tree structure of pages. The data region is determined by the ratio of visual block area to the entire page. A set of nodes with data records are identified according to visual features, such as adjacency. Noise nodes are eliminated by comparing the similarity of nodes’ DOM tree structure. According to xpath attributes, all data items are aligned. Template is generated for the process of extraction, which significantly improves the extraction efficiency. Experiments of data extraction were conducted with eight Deep Web websites, the results of which fully testify the effectiveness of our method.

Deep Web; data extraction; visual feature; tag path

山東省自然科學(xué)基金項(xiàng)目(ZR2012FM016)資助

2013-10-30；

2014-09-20

張 巍(1975-)，男，副教授。E-mail: ihcil@ouc.edu.cn

TV149.2

A

1672-5174(2015)05-114-06

10.16441/j.cnki.hdxb.20130395