基于MapReduce虛擬機的Deep Web數(shù)據(jù)源發(fā)現(xiàn)方法

辛潔，崔志明，趙朋朋，張廣銘，鮮學(xué)豐

(蘇州大學(xué) 智能信息處理及應(yīng)用研究所，江蘇 蘇州 215006)

1 引言

網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，海量數(shù)據(jù)使Web迅速的“深化”，這些由后臺數(shù)據(jù)庫動態(tài)產(chǎn)生的，對用戶隱藏不可見的數(shù)據(jù)不能被傳統(tǒng)的搜索引擎索引，只能通過表單提交查詢來獲得。如何從Deep Web中迅速有效地抽取信息，對數(shù)據(jù)源進行大規(guī)模的集成成為研究熱點，其中包括數(shù)據(jù)源發(fā)現(xiàn)，查詢接口抽取，數(shù)據(jù)源分類，查詢轉(zhuǎn)換，結(jié)果合成等，而Deep Web 數(shù)據(jù)源發(fā)現(xiàn)是信息集成的第一步。

Deep Web數(shù)據(jù)源的搜索和發(fā)現(xiàn)實際上是Web表單查詢接口的判定過程。這些接口是嵌入于Web 頁面中以Form表單形式出現(xiàn)的,因此整個過程是對數(shù)據(jù)按規(guī)則進行篩選，剔除，分類的操作。由于Deep Web數(shù)據(jù)動態(tài)產(chǎn)生且數(shù)量巨大，提高Deep Web入口發(fā)現(xiàn)的效率和精度應(yīng)不局限于僅從爬蟲本身進行結(jié)構(gòu)策略的優(yōu)化，還可從大規(guī)模數(shù)據(jù)的分布式并行處理，改善外部工作環(huán)境等方面下手。

作為云計算的關(guān)鍵技術(shù)之一，MapReduce是Google開發(fā)的在超大集群下進行海量數(shù)據(jù)的分布式編程模式。它能夠?qū)﹂_發(fā)人員隱藏并行編程的具體工作方式，為編寫需要大規(guī)模并行處理的代碼提供了簡單的編程模式。在Google的集群上，每天都有 1 000多個 MapReduce程序在執(zhí)行，是Google最關(guān)鍵的技術(shù)之一[1]。MapReduce在Surface Web數(shù)據(jù)抓取方面取得了巨大的成功，對于信息量約 500倍于 Surface Web的 Deep Web來說[2]，MapReduce模型應(yīng)更適合Deep Web的海量數(shù)據(jù)抽取。

MapReduce計算往往在超大集群上并發(fā)執(zhí)行，虛擬化技術(shù)可實現(xiàn)虛擬集群的構(gòu)建以達到資源的最大利用。本文首先利用MapReduce架構(gòu)爬蟲框架結(jié)構(gòu)模型，通過對鏈接過濾分類，頁面過濾分類，表單過濾分類等3個MapReduce過程發(fā)現(xiàn)數(shù)據(jù)源接口，再利用服務(wù)器虛擬化技術(shù)創(chuàng)建由一臺服務(wù)器變成4臺相互隔離的虛擬服務(wù)器的集群進行并行測試。結(jié)果顯示本方法提高了爬蟲抓取 Deep Web數(shù)據(jù)源的能力，大幅度提高了服務(wù)器的資源利用率。

本文的結(jié)構(gòu)如下：第2節(jié)簡述Deep Web爬蟲，MapReduce及虛擬化的相關(guān)研究；第 3節(jié)介紹MapReduce架構(gòu)的Deep Web數(shù)據(jù)源發(fā)現(xiàn)模型；第4節(jié)創(chuàng)建虛擬平臺并對該模型進行了性能測試；第5節(jié)是結(jié)束語。

2 相關(guān)研究工作

2.1 Deep Web爬蟲的數(shù)據(jù)源發(fā)現(xiàn)

Deep Web數(shù)據(jù)源要通過查詢接口在線訪問站點后端的Web數(shù)據(jù)庫得到。數(shù)據(jù)源發(fā)現(xiàn)要求Deep Web爬蟲必須能跟蹤超鏈接，填寫表單，最后獲取和識別結(jié)果頁面[3]，如圖1所示。

圖1 Deep Web 爬蟲系統(tǒng)框架

諸多研究集中于爬蟲爬行策略的改進，如實現(xiàn)網(wǎng)頁表單自動填寫，優(yōu)化數(shù)據(jù)源選擇方式等。這些研究都在已經(jīng)獲取到表單接口的前提下進行的。在判斷是表單是否是Deep Web查詢接口方面，文獻[4]提出了一種針對主題相關(guān)性及鏈接重要性的Deep Web的聚焦爬蟲可有效的提高Deep Web數(shù)據(jù)源發(fā)現(xiàn)效率和精度。Cope等人[5]提出基于查詢接口的特征利用C4.5決策樹實現(xiàn)了對查詢接口的識別。 Juliano等人[6]提出了一種根據(jù)啟發(fā)式規(guī)則來判斷網(wǎng)頁表單是否為查詢接口的方法。然而，再優(yōu)秀的算法面對PB級的數(shù)據(jù)量也顯得很無力，分布式并行計算勢在必行。MapReduce簡化了編程模型，降低了開發(fā)并行應(yīng)用的入門門檻，且虛擬化為MapReduc的架構(gòu)創(chuàng)造了條件。

2.2 MapReduce和虛擬化

MapReduce 的關(guān)鍵特點是它能夠?qū)﹂_發(fā)人員隱藏并行編程的具體工作方式，無需關(guān)心并行計算，容錯，數(shù)據(jù)分布，負載均衡等復(fù)雜細節(jié)，只需設(shè)計自身的分布式計算任務(wù)表述。MapReduce實現(xiàn)了兩個功能。Map把一個函數(shù)應(yīng)用于集合中的所有成員，然后返回一個基于這個處理的結(jié)果集。而Reduce是把從2個或更多個Map中，通過多個線程，進程或者獨立系統(tǒng)并行執(zhí)行處理的結(jié)果集進行分類和歸納[1]。日前，Google宣布完成對1TB數(shù)據(jù)的排序處理只需要短短 68s，歸功于其最重要的技術(shù)MapReduce。其概念可以表達為：

MapReduce的應(yīng)用非常廣泛，如簡單計算任務(wù)，海量數(shù)據(jù)輸入，集群計算，文檔聚類，機器學(xué)習，基于統(tǒng)計的機器翻譯等[1]。但鮮有文章對Deep Web數(shù)據(jù)進行并行處理應(yīng)用。

MapReduce在大規(guī)模的集群上表現(xiàn)良好，虛擬化技術(shù)系統(tǒng)安全性和可靠性，良好的擴展性為大型集群的架構(gòu)創(chuàng)造了基礎(chǔ)。文獻[7]利用Hadoop在虛擬機上測試了MapReduce的性能，提出了這2種技術(shù)的結(jié)合不僅提高了處理大規(guī)模數(shù)據(jù)的速度，保證了資源的有效使用，更不必重復(fù)執(zhí)行相同任務(wù)，虛擬機的容錯性和動態(tài)遷移可提高系統(tǒng)的可靠性。文獻[8]在完全虛擬化的平臺上對 MapReduce進行檢查，對比了2、4、8、16個虛擬節(jié)點下的處理能力，證明每增加一臺MapReduce機器，其計算能力也相應(yīng)增加。這些研究都是基于單機虛擬，即一臺機器作為一個虛擬機，本文進一步將服務(wù)器虛擬化的概念引入，將一臺服務(wù)器虛擬為多臺相互隔離的集群，通過“資源池”共享，達到負載均衡，簡化管理和提高效率。

3 Deep Web數(shù)據(jù)源發(fā)現(xiàn)MapReduce模型

3.1 MapReduce過程框架

Deep Web數(shù)據(jù)源發(fā)現(xiàn)指在Web中發(fā)現(xiàn)可訪問的Web數(shù)據(jù)庫。一是找到數(shù)據(jù)庫所在的網(wǎng)站，二是從網(wǎng)站中發(fā)現(xiàn)能夠?qū)?shù)據(jù)庫查詢的接口。引入MapReduce算法模型的好處在于：第一，將要執(zhí)行的問題分解成映射(map)和化簡(reduce)的方式，不需要考慮如何將輸入數(shù)據(jù)分塊、分配和調(diào)度，只需要指定Map和Reduce的操作得到高效率的并行計算，提高抽取和分類的效率；第二，MapReduce程序的輸入、輸出、中間數(shù)據(jù)都是以key/value的值對的形式出現(xiàn)，方便對查詢接口進行定義和類別判定；第三，MapReduce構(gòu)架下的自動表單分類方法適用于大規(guī)模數(shù)據(jù)處理，因此對于Deep Web中大量表單分類時，在保證分類效果的情況下，可用獲得線性的加速比。借鑒文獻[4]的方法，利用鏈接MapReduce 分類, 頁面 MapReduce 分類及表單MapReduce 分類對網(wǎng)站進行挖掘過濾，具體過程描述如圖2所示。

3.1.1 鏈接分類MapReduce

該過程的目的是找到種子鏈接下的所有鏈接，通過對鏈接的分類過濾，剔除掉不含表單接口的鏈接如導(dǎo)航信息，廣告信息等。輸出結(jié)果應(yīng)滿足：1)鏈接深度小于等于 3(91.6%的查詢接口所在頁面深度小于等于 3[8])；2)含有特征文字（錨文本中含有類似“搜索”、“高級搜索”、“點擊這里搜索”等文字及鏈接中含有 search、finder、seek等文字均為Deep Web查詢接口的標志）；3）主題相關(guān)。Maper1接收待訪問 URL種子列表，提取特征包括錨文本及鏈接上下文文本、URL地址、鏈接中的圖片地址，對上述信息進行分詞并統(tǒng)計詞頻，得到特征向量X。中間結(jié)果輸出鏈接的深度，特征文字抽取，相關(guān)性測試值。其中相關(guān)性的判定通過采用樸素貝葉斯分類算法，對于特征向量為 X=[x1,x2,…,xd]T的測試樣本，它屬于第Ci類的概率如下所示：

圖2 Deep Web數(shù)據(jù)源發(fā)現(xiàn)MapReduce過程

其中，P(Ci|X)代表X屬于類Ci的概率。因此，只有當 P(Ci|X)的最大值所在的 Ci類即為該鏈接所屬的類別。Reduce1在滿足以上條件的中間結(jié)果中將key值相同的結(jié)果合并，得到＜＜url, linkstoVisit＞, html＞值對送入到頁面分類MapReduce過程。

3.1.2 頁面分類MapReduce

二次過濾，使用與鏈接過濾MapReduce相同的方法，目的是縮小數(shù)據(jù)處理的范圍，找到與主題相關(guān)的頁面進行下一步的表單搜索。比較成熟的分類算法有決策樹分類算法，SVM算法，KNN算法，C4.5算法等。這里還是采用樸素貝葉斯方法，套用式(1), 得到該網(wǎng)頁屬于某一主題的概率值 P(Ci|X),給定一個閾值 θ(本文測試時 θ值為 0.5)，只有當P(Ci|X)＞θ時，該網(wǎng)頁才會被繼續(xù)處理。Maper2接受鏈接MapReduce處理好的中間結(jié)果，進行去html標記，和分詞操作。Reduce2對頁面進行分類判定，分入一個最相關(guān)的類別，并將具有相同key的頁面進行合并，輸出結(jié)果＜＜linkstoVisit, formName＞,form＞送入表單分類MapReduce過程。

3.1.3 表單分類MapReduce

表單分類服務(wù)器的功能是通過表單抽取器抽取頁面中的表單接口，剔除那些不合要求的表單，篩選出本文要研究的表單并進行分類。Deep Web數(shù)據(jù)源查詢接口的分類問題涉及2方面的內(nèi)容：特征抽取和機器學(xué)習。在對表單進行分類時，本文采取了非提交查詢的方法，直接利用網(wǎng)頁表單的結(jié)構(gòu)信息進行特征提取進行分類。

首先，Internet中大多數(shù)的查詢接口以 HTML語言編寫的Form表單表示。由于表單的組成比較復(fù)雜，通常包含INPUT, SELECT, TEXTAREA 3類控件，其中 INPUT控件的類型元素有：文本框(textbox)、單選按鈕(radio)、復(fù)選框(checkbox)和下拉列表框(selection list)等。在表單中，每個控件都對應(yīng)一個標簽，并有一個或多個屬性值。因此，該控件和其對應(yīng)的屬性值在邏輯上形成關(guān)聯(lián)，對應(yīng)了Deep Web后臺數(shù)據(jù)庫的一個字段。一個查詢接口可以抽象的表示為：F= (N, {A1,A2,…,An}),其中，N為表單的名字，Ai為查詢接口的屬性序列，Ai=(Li,{E1,E2,…,EK})，其中，Li為屬性標簽，Ej為表單控件。以某圖書搜索表單為例進行解釋：數(shù)據(jù)接口 F=(search, {A1,A2,…,An})，其中，Ai=(author, {textbox,radio1, radio2, radio3})。

Maper3接收從頁面分類MapReduce的中間結(jié)果，提取如下表單特征：網(wǎng)頁表單＜FORM＞標簽中的name屬性值，action屬性值，出現(xiàn)的控件類型，INPUT控件的 name屬性值和 value屬性值，SELECT控件和TEXTAREA控件的name屬性值，存在于控件標簽之間的詞。

其次，在自動分類過程中加入一些啟發(fā)式的規(guī)則可以進一步提升Deep Web查詢接口判定的效率和準確性。文獻[9]中提及的語義抽取方法,可設(shè)定如下規(guī)則。

規(guī)則 1 給定一個閾值θ，具有n＜θ的表單將被忽略不予考慮，n表示W(wǎng)eb表單中需要填寫的字段個數(shù)。該規(guī)則用于去除那些超負載的表單，如站內(nèi)搜索表單等。

規(guī)則2 對于給定表單γ，如果γ含有字段元素對應(yīng)標簽名為用戶名、密碼等的HTML類型元素，γ表單將被忽略不予考慮。該規(guī)則用于去除那些保密的表單，如用戶注冊表單等。

規(guī)則3 對于只含有一個復(fù)選框(checkbox)或只含有一個可選列表(selectlist)的輸入限制表單應(yīng)該拋棄。目的是去除一些超鏈接的轉(zhuǎn)向非搜索表單。

最后，Reduce3將規(guī)則過濾后的中間記過向已知的接口手工分類訓(xùn)練集的特征進行機器學(xué)習，計算得到各類別先驗概率和各詞的特征權(quán)值，自行判斷接口是否屬于表單查詢接口。

樸素貝葉斯分類器基于一個簡單的假定：在給定實例目標值的情況下，觀察得到聯(lián)合的ai(i=1,…,n)概率等于每個單獨屬性的概率乘積：

樸素貝葉斯分類器輸出的目標值可以表示為

假設(shè)Vyes為待分類網(wǎng)頁表單M是查詢接口的概率，Vno為待分類網(wǎng)頁表單M非查詢接口的概率，如Vyes＞Vno，可就可以判定網(wǎng)頁表單M為查詢接口。Reduce3輸入的結(jié)果＜formName, formAttri＞即為Deep Web數(shù)據(jù)源的查詢接口。

3.2 服務(wù)器虛擬化下單機集群架構(gòu)

Hadoop是Google MapReduce框架的JAVA實現(xiàn)，本文中的實現(xiàn)部分就是基于這個開源框架實現(xiàn)的。對于Hadoop的集群來說，可以分成兩大類角色：Master和 Slave，前者主要配置NameNode和JobTracker的角色，負責總管分布式數(shù)據(jù)和分解任務(wù)的執(zhí)行，后者配置DataNode和TaskTracker的角色，負責分布式數(shù)據(jù)存儲以及任務(wù)的執(zhí)行。本文所架構(gòu)的集群即為1個Master加3個Slave的結(jié)構(gòu)。服務(wù)器虛擬化后，一臺服務(wù)器虛擬為4臺具有獨立IP地址，獨立操作系統(tǒng)等，可通過區(qū)分資源的優(yōu)先次序即時將服務(wù)器資源分配給最需要它們的工作來簡化管理和提高效率。虛擬化后的結(jié)構(gòu)如圖3所示。

圖3 服務(wù)器虛擬化單機集群結(jié)構(gòu)

當用戶調(diào)用MapReduce 函數(shù)時，執(zhí)行步驟如下。

1) 數(shù)據(jù)分片。

將待分配URL列表按需分成幾個數(shù)據(jù)組。

2) 主程序master分配任務(wù)給worker。

圖2中的3個MapReduce過程都是由master將一個 Map 任務(wù)或 Reduce 任務(wù)分配給某一空閑的worker。

3) worker執(zhí)行Map函數(shù)。

被分配了map 任務(wù)的worker程序讀取相關(guān)的輸入數(shù)據(jù)片段，解析出各個過程中的 key/value值對，根據(jù)3個過程中各自Map 函數(shù)的定義，計算并輸出的中間數(shù)據(jù)存入內(nèi)存。

4) 中間結(jié)果的處理。

經(jīng)過3個MapReduce，中間結(jié)果被周期性地寫入到本地磁盤。master獲取其值對的存儲位置，并將信息傳至Reduce worker。

5) Reduce worker讀取中間數(shù)據(jù)。

根據(jù)接收到的存儲位置信息，Reduce worker從Map worker 所在主機的磁盤上讀取數(shù)據(jù)。然后對key 進行排序后并合并具有相同key值的數(shù)據(jù)。

6) 執(zhí)行Reduce函數(shù)。

Reduce worker 將處理好的結(jié)果集合傳遞給用戶自定義的 Reduce 函數(shù)，各分類過濾后的結(jié)果被追加到所屬分區(qū)的輸出文件。

7) master 喚醒用戶程序。

4 性能測試與分析

4.1 系統(tǒng)配置

Deep Web爬蟲MapReduce系統(tǒng)實驗環(huán)境配置如下：一臺IBM system X3650 M2 (Xeon 5530 2.4GHz/2×2GB/1×146GB)服務(wù)器，基于 VMware ESX 2.0的虛擬化平臺，Hapood version 0.18.0搭建集群，校園網(wǎng)絡(luò)帶寬。

由于Deep Web的數(shù)據(jù)庫具有主題多樣性，本實驗對其中的3個領(lǐng)域（飛機票、圖書和工作）進行測試。所采用的數(shù)據(jù)源如表1所示。

表1 數(shù)據(jù)對象抽取的測試數(shù)據(jù)源

設(shè)置爬行停止的條件為當某站點已發(fā)現(xiàn)的不同的查詢接口數(shù)多于5或下載的頁面數(shù)大于100時，該站點中的鏈接就不再處理。

4.2 測試結(jié)果

本測試主要針對3個方面對MapReduce模型下的Deep Web爬蟲進行測試：1) 對DeepWeb大規(guī)模數(shù)據(jù)并行的處理能力，對數(shù)據(jù)源接口的發(fā)現(xiàn)效率；2) 利用虛擬化技術(shù)構(gòu)建的Hapood單機集群的可靠性；3) 物理硬件資源的使用率。

圖4為上述實驗環(huán)境中，深層網(wǎng)絡(luò)爬蟲，本地單機 MapReduce爬蟲(MR爬蟲)與虛擬機集群MapReduce爬蟲(虛擬MR爬蟲)分別從3個領(lǐng)域中聚焦爬蟲爬行到Deep Web數(shù)據(jù)源查詢接口數(shù)量的對比。從圖中可以看出，采取MapReduce框架后的本地單機爬蟲的表現(xiàn)平平，并沒有太多提高爬蟲的爬行能力,只有當數(shù)據(jù)量比較大時效果才體現(xiàn)出來。而經(jīng)過虛擬化改良構(gòu)建為單機集群的爬蟲可從每個領(lǐng)域中爬取到更多的查詢接口。爬蟲的數(shù)據(jù)源發(fā)現(xiàn)效率得到大幅度提升。

圖4 3種模式下爬取Deep Web查詢接口數(shù)量對比

圖 5為單位時間內(nèi)，3種模式下爬取到的總的下載頁面數(shù)的對比。由圖5所知，改進后的模型可在同樣時間內(nèi)下載到更多的頁面。結(jié)合圖4，可以得到以下結(jié)論：MapReduce虛擬集群的具有更高的 Deep Web數(shù)據(jù)源發(fā)現(xiàn)能力，爬行效率有所提高。

圖5 3種模式下爬取到的總的下載頁面數(shù)的對比

除了對MapReduce框架下的爬蟲進行效率分析，本文也對獲得的數(shù)據(jù)進行精度評估，利用手工分類的方法從抓取到的表單接口中隨機抽取200個樣本，比較3種方式下的查全率（Recall）及準確率（Precision）。查全率是系統(tǒng)正確判定查詢接口的結(jié)果占所可能正確結(jié)果的比率，考察了不同算法下找全分類結(jié)果的能力。準確率是系統(tǒng)正確判定查詢接口占所有查詢表單的比例，考察了不同算法下找準分類結(jié)果的能力。F度量(F-measure)是2種融合。圖6為3個領(lǐng)域下3種模式的F值對比。

其中，P為查全率，R為準確率。

由圖6可知，本文所述的方法召回率和準確率都很高，F(xiàn)值也相應(yīng)得到提高，雖然提高的幅度不大，但亦表明，利用虛擬化技術(shù)構(gòu)建的Hapood單機集群的具有一定的可靠性，結(jié)果相對來說比較滿意。

最后，表2為虛擬化前后服務(wù)器硬件使用率的對比。從表中可以看出，服務(wù)器進行虛擬化后，其CPU、內(nèi)存、存儲器及帶寬都得到相應(yīng)的提高。也就是說，通過WMware對服務(wù)器資源的規(guī)劃利用，服務(wù)器得到更為充分的使用。

表2 虛擬化前后服務(wù)器使用率對比

5 結(jié)束語

Deep Web具有主題專一，信息質(zhì)量高，信息結(jié)構(gòu)化好等優(yōu)點，除了其信息量大，更新速度快會對高效率的發(fā)現(xiàn)數(shù)據(jù)源產(chǎn)生制約外，服務(wù)器工作效率，網(wǎng)絡(luò)帶寬等外界因素也對其效率產(chǎn)生影響。本文的主要貢獻在于首先將Surface Web中貢獻巨大的MapReduce框架借鑒入Deep web中，實現(xiàn)了大規(guī)模數(shù)據(jù)的并行處理，其次利用了虛擬化技術(shù)架構(gòu)了MapReduce單機集群，驗證了這2種技術(shù)的結(jié)合可大幅度提高機器的工作效率。

虛擬化和MapReduce都是云計算的關(guān)鍵技術(shù)，因此，云計算是可以在Deep Web數(shù)據(jù)挖掘方面發(fā)揮巨大作用的。數(shù)據(jù)源發(fā)現(xiàn)僅為Deep Web數(shù)據(jù)集成的一部分，數(shù)據(jù)源的管理，聚類分析等方面都可與云計算的方法融合處理。

[1] DEAN J, GHEMAWAT S. Mapreduce: simplified data processing on large clusters[A]. Proceedings of the 6th Symposium on Operating System Design and Implementation[C]. San Francisco: USRNIX,2004. 137-150.

[2] THANAA M, GHANEM, WALID G A. Databases deepen the Web[J].IEEE Computer, 2004, 73(1):116-117.

[3] 鄭東東, 趙朋朋, 崔志明. Deep Web爬蟲研究與設(shè)計[J]. 清華大學(xué)學(xué)報(自然科學(xué)版), 2005,45(S1):1896-1902.ZHENG D D, ZHAO P P, CUI Z H. On the research and design of deep Web crawler[J]. Tsinghua Univ (Sci&Tech), 2005,45(S1):1896-1902.

[4] BARBOSA L, FREIRE J. Searching for hidden-Web databases[A].Proceedings of Eighth International Workshop on the Web and Databases[C]. Baltimore, 2005. 1-6.

[5] COPE J, CRASWELL N, HAWKING D. Automated discovery of search interfaces on the Web[A]. Proceedings of the 14th Australian Database Conference[C]. Adelaide, 2003.181-189.

[6] JULIANO P L, ALTIGRAN S, DA S, et al. Automatic generation of agents for collecting hidden Web pages for data extraction[J]. Data &Knowledge Engineering, 2004, 49(2):177-196.

[7] SHADI I, HAI J, LU L, et al. Evaluating mapreduce on virtual machines: the hadoop case[A]. Proceedings of Cloud Computing-first International Conference[C]. Beijing, China, 2009.519-528.

[8] CHANG K C C, HE B, LI C, et al. Structured databases on the Web: observations and implications[J].SIGMOD Record,2004,33(3): 61-70.

[9] WANG Y, PENG T. Schema extraction of DEEP Web query interface[A]. Proceedings of 2009 International Conference on Web Information Systems and Mining [C]. Shanghai, China, 2009. 391-395.