張 巍， 鄒曉明， 談鳳真

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

?

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

張 巍， 鄒曉明， 談鳳真

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

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

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

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

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

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

1 概述

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

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

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

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

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

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

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

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

Area(node)/Area(body)>Tregion

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

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

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

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

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

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

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

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

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

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

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

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

4 對齊數(shù)據(jù)項

4.1 去噪

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

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

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

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

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

4.2 對齊數(shù)據(jù)項

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

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

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

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

(3)對齊算法。得到所有的數(shù)據(jù)項及其xpath后，需要將不同數(shù)據(jù)記錄中相應(yīng)數(shù)據(jù)項對齊。首先將每條數(shù)據(jù)記錄的數(shù)據(jù)項按照其在網(wǎng)頁中的位置從上至下、從左至右排列。為了便于對齊，設(shè)計了一個類似二維數(shù)組的數(shù)據(jù)結(jié)構(gòu)來保存數(shù)據(jù)項，如圖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ù)項的存儲結(jié)構(gòu)

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

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

5 模板

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

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

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

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

5.2 對齊數(shù)據(jù)項的模板

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

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

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

6 實驗

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

6.1 實驗數(shù)據(jù)

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

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

選用DEPTA算法作為對比，因為它是利用DOM樹抽取數(shù)據(jù)的典型算法。查準率是指抽取的數(shù)據(jù)記錄占抽取的所有記錄的比例，查全率是指抽取的數(shù)據(jù)記錄占網(wǎng)頁中所有數(shù)據(jù)記錄的比例。表1是對八個網(wǎng)站(見表2)進行抽取實驗后兩種算法的比較：

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

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

6.3 數(shù)據(jù)項的對齊實驗

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

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

表2 數(shù)據(jù)項對齊的準確率Table 2 Alignment accuracy of data item

7 結(jié)語

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

[1] 劉偉. Deep Web數(shù)據(jù)集成研究綜述 [J]. 計算機學報， 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.

責任編輯 陳呈超

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

山東省自然科學基金項目(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