基于領(lǐng)域知識抽樣的深網(wǎng)資源采集方法

林海倫，熊錦華，王 博，程學(xué)旗

(1. 中國科學(xué)院 計算技術(shù)研究所，北京 100190; 2. 中國科學(xué)院大學(xué)，北京 100049； 3. 國家計算機網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029)

基于領(lǐng)域知識抽樣的深網(wǎng)資源采集方法

林海倫1,2，熊錦華1，王 博3，程學(xué)旗1

(1. 中國科學(xué)院 計算技術(shù)研究所，北京 100190; 2. 中國科學(xué)院大學(xué)，北京 100049； 3. 國家計算機網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029)

深網(wǎng)資源是指隱藏在HTML表單后端的Web數(shù)據(jù)庫資源，這些資源主要通過表單查詢的方式訪問。然而，目前的網(wǎng)頁采集技術(shù)由于采用頁面超鏈接的方式采集資源，所以無法有效覆蓋這些資源，為此，該文提出了一種基于領(lǐng)域知識抽樣的深網(wǎng)資源采集方法，該方法首先利用開源目錄服務(wù)創(chuàng)建領(lǐng)域?qū)傩约?，接著基于置信度函?shù)對屬性進行賦值，然后利用領(lǐng)域?qū)傩约线x擇查詢接口并生成查詢接口賦值集合，最后基于貪心選擇策略選擇置信度最高的查詢接口賦值生成查詢實例進行深網(wǎng)采集。實驗表明，該方法能夠有效地實現(xiàn)深網(wǎng)資源的采集。

深網(wǎng)；置信度；抽樣；領(lǐng)域知識

1 引言

深網(wǎng)(Deep Web)是指網(wǎng)絡(luò)爬蟲通過頁面之間的鏈接關(guān)系難以采集到的資源，這些資源通常隱藏在HTML表單后端的Web數(shù)據(jù)庫中，主要通過表單查詢的方式動態(tài)訪問。深網(wǎng)資源具有以下主要特點： 一是深網(wǎng)資源比搜索引擎可索引的資源(淺網(wǎng)[1])在規(guī)模上更大，并且增長速度非?？欤?2000年BrightPlanet發(fā)布的對深網(wǎng)資源進行統(tǒng)計分析的白皮書中指出深網(wǎng)資源是互聯(lián)網(wǎng)上淺網(wǎng)資源的五百倍[1]，而且從2000年到2004年，深網(wǎng)資源增長了 3～7倍[2]，并且仍在不斷增長[3]；二是深網(wǎng)資源領(lǐng)域覆蓋面廣，數(shù)據(jù)結(jié)構(gòu)化程度高，為用戶提供的信息質(zhì)量更高： 深網(wǎng)資源覆蓋各種不同的領(lǐng)域，如教育、電子商務(wù)、房地產(chǎn)、娛樂等[3]，而且主要以結(jié)構(gòu)化的數(shù)據(jù)的形式存儲在Web數(shù)據(jù)庫中[4]。

由此可見，與淺網(wǎng)相比，深網(wǎng)具有數(shù)據(jù)量更大、內(nèi)容覆蓋面更廣、結(jié)構(gòu)化更好等優(yōu)點，這使得深網(wǎng)資源對數(shù)據(jù)分析類的應(yīng)用(如市場分析、比價購物)和知識庫的構(gòu)建來說價值更高。目前獲取深網(wǎng)資源方法的研究主要集中在利用爬蟲技術(shù)主動查詢深網(wǎng)數(shù)據(jù)庫，迭代地“發(fā)現(xiàn)”深網(wǎng)數(shù)據(jù)庫中的內(nèi)容，這種方法與傳統(tǒng)的淺網(wǎng)采集方法不同： 需要爬蟲能夠自動發(fā)現(xiàn)深網(wǎng)資源的查詢接口，并且為查詢接口中的查詢輸入項選擇合適的取值生成查詢，從查詢的響應(yīng)結(jié)果頁中提取數(shù)據(jù)記錄從而實現(xiàn)深網(wǎng)資源的采集。利用這種方法進行深網(wǎng)采集是一個充滿挑戰(zhàn)的問題，原因在于： 深網(wǎng)的數(shù)據(jù)規(guī)模比淺網(wǎng)規(guī)模更大，嘗試覆蓋所有的深網(wǎng)資源是不可行的；而且訪問深網(wǎng)資源只能通過為用戶設(shè)計的限制搜索的查詢接口，訓(xùn)練一個爬蟲使用這個限制搜索的查詢接口提取相關(guān)的內(nèi)容是非常困難的。同時，對應(yīng)用來說，采集所有深網(wǎng)資源的價值可能并不比采集特定的深網(wǎng)資源的價值高。

為此，本文提出了一種面向特定領(lǐng)域(應(yīng)用)的基于知識抽樣的深網(wǎng)采集方法，該方法采用人工輔助的方式，利用人工定義的資源采集需求描述自動實現(xiàn)深網(wǎng)資源采集。具體地說，本文目標(biāo)是基于特定領(lǐng)域或應(yīng)用的需求，有針對性地采集深網(wǎng)資源： 該方法首先根據(jù)領(lǐng)域或應(yīng)用需求描述，實現(xiàn)領(lǐng)域知識抽樣(采集任務(wù)抽樣)，然后根據(jù)領(lǐng)域知識樣本實現(xiàn)指定站點的深網(wǎng)資源采集，人工輔助的方式能夠支持爬蟲對應(yīng)用或任務(wù)相關(guān)的深網(wǎng)資源提交查詢。該方法的創(chuàng)新之處在于：

? 提出了根據(jù)領(lǐng)域或應(yīng)用需求描述，自動實現(xiàn)領(lǐng)域知識抽樣的算法；

? 提供并實現(xiàn)了基于領(lǐng)域知識抽樣處理深網(wǎng)資源采集的新方法，包括領(lǐng)域(任務(wù))相關(guān)的深網(wǎng)資源選擇和查詢實例生成技術(shù)。

本文的組織結(jié)構(gòu)如下： 第二節(jié)介紹相關(guān)工作；第三節(jié)介紹領(lǐng)域知識抽樣的原理；第四節(jié)介紹基于領(lǐng)域知識抽樣的深網(wǎng)資源采集過程，包括查詢接口處理和查詢實例生成；第五節(jié)是實驗和評價；最后總結(jié)全文。

2 相關(guān)工作

為了提高深網(wǎng)資源覆蓋率，充分挖掘深網(wǎng)資源的價值，使深網(wǎng)資源能夠服務(wù)最終用戶，近年來，深網(wǎng)資源采集技術(shù)得到了廣泛研究，已經(jīng)出現(xiàn)很多支持深網(wǎng)資源采集的工具和方法。Raghavan等人[5]設(shè)計了一種深網(wǎng)資源采集的框架HiWE，HiWE采用面向特定領(lǐng)域的方式： 需要人工提供領(lǐng)域?qū)傩约皩傩匀≈导?，并利用領(lǐng)域?qū)傩院蛯傩匀≈?，生成查詢集合，然后利用爬蟲技術(shù)進行資源采集。HiWE還利用深網(wǎng)資源查詢接口中選擇輸入項的取值更新屬性取值，但是沒有考慮利用爬蟲的采集結(jié)果自動更新領(lǐng)域?qū)傩匀≈档姆绞健?/p>

不同于HiWE，Wu[6]提出一種基于屬性值圖的深網(wǎng)資源采集方法，該方法將基于查詢的深網(wǎng)采集建模為圖的遍歷問題。該工作得出結(jié)論認為結(jié)構(gòu)化的數(shù)據(jù)庫屬性值圖中結(jié)點的度分布與冪律分布(power law)相似，并以此為依據(jù)采用貪心選擇策略選擇度大的結(jié)點生成表單查詢。但是該方法需要將每一次的查詢結(jié)果增加到已有的屬性值圖中，然后生成下一個新的待提交的查詢詞，更新屬性值圖的代價較高。

DeepBot[7-8]是一個基于瀏覽器內(nèi)核開發(fā)的深網(wǎng)采集的方法，它基于瀏覽器內(nèi)核設(shè)計深網(wǎng)資源爬蟲，解決網(wǎng)頁客戶端瀏覽器腳本解析問題，DeepBot與HiWE類似，都采用面向特定領(lǐng)域的方式，接受一組領(lǐng)域定義集合作為輸入，指導(dǎo)深網(wǎng)資源的采集。但是該方法完全依賴人工提供的領(lǐng)域定義集合，沒有考慮領(lǐng)域定義集合的更新問題。

為此，Madhavan[9]提出了一種基于查詢模板的深網(wǎng)資源自動采集方法，該方法自動判斷查詢接口中輸入元素接受的數(shù)據(jù)類型，選擇查詢接口中的輸入項的一個子集作為約束項構(gòu)造查詢模板，該方法通過表單查詢返回結(jié)果驗證查詢模板的有效性。雖然該方法能夠自動實現(xiàn)深網(wǎng)查詢請求的生成，但是對于包含多個輸入項的查詢接口來說，其對應(yīng)文本輸入項取值集合的確定、查詢模板有效性的驗證過程復(fù)雜，導(dǎo)致深網(wǎng)資源采集的效率較低。

西安交通大學(xué)的Jiang和Wu等人[10-12]提出了基于增強學(xué)習(xí)(Reinforcement Learning,RL)的深網(wǎng)資源采集方法，該方法在選擇查詢時除了利用統(tǒng)計信息之外，還利用語言特征以及HTML本身的特征[10]。RL方法允許爬蟲根據(jù)從已執(zhí)行的查詢中獲取的經(jīng)驗自動學(xué)習(xí)查詢選擇策略，從而為每一輪查詢選擇收益最大的查詢關(guān)鍵詞進行資源采集。但是相比有人工方式參與的深網(wǎng)資源采集方法，該方法的學(xué)習(xí)過程相對復(fù)雜。

上述工作都從不同角度對深網(wǎng)資源采集方法進行研究，通過分析我們發(fā)現(xiàn)完全人工和完全自動的深網(wǎng)采集方法都存在局限性，為此，我們需要一種在它們之間折中的深網(wǎng)資源采集方法來克服這種局限性。

3 領(lǐng)域知識抽樣

深網(wǎng)數(shù)據(jù)庫的資源通常是屬于某個特定領(lǐng)域的，而同一領(lǐng)域的數(shù)據(jù)庫的屬性值和屬性值的分布相似。因此，考慮同一領(lǐng)域各個數(shù)據(jù)庫之間的相似性，利用同一領(lǐng)域的數(shù)據(jù)樣本，爬蟲則可以獲得該領(lǐng)域查詢接口的屬性取值生成查詢，實現(xiàn)深網(wǎng)資源的采集。問題的關(guān)鍵在于如何能有效地獲取領(lǐng)域知識，并整合到深網(wǎng)資源采集框架中。在本節(jié)，我們提出了一種面向領(lǐng)域的知識抽樣方法，在介紹抽樣方法之前，我們首先討論領(lǐng)域知識的表示。

3.1 領(lǐng)域知識表示

定義1 領(lǐng)域知識： 關(guān)于領(lǐng)域DM的領(lǐng)域知識DK是對領(lǐng)域及領(lǐng)域數(shù)據(jù)的描述，領(lǐng)域知識由一組領(lǐng)域?qū)傩院蛯嵗M成：DK=，其中： 1)A表示領(lǐng)域DM的屬性集合，A={a1,a2,…,am}。其中，屬性ai為領(lǐng)域的屬性信息：ai=，name為屬性名稱，aliases為屬性別名集合：aliases={aliasi1,aliasi2,…,aliasin}，aliasij表示屬性ai的第j個同義名稱，affinity表示屬性ai與領(lǐng)域DM的相關(guān)度，0≤affinity≤1，affinity取值越大說明包含屬性ai的數(shù)據(jù)源與領(lǐng)域DM的相關(guān)性越大；2)I表示屬性的取值實例集合，I={Ia1,Ia2,…,Iam}，其中，Iai為屬性ai的實例集合：Iai={ci1,ci2,…,cil}，cik表示屬性ai的第k個實例：cik=，其中，name=ai.name表示屬性名，value表示屬性取值。

文獻[3]對不同領(lǐng)域的深網(wǎng)查詢接口中出現(xiàn)的屬性詞匯進行統(tǒng)計分析發(fā)現(xiàn)： 同一領(lǐng)域的查詢接口中出現(xiàn)的屬性詞匯數(shù)量趨于收斂在一個相對小的規(guī)模，而且，同一領(lǐng)域深網(wǎng)查詢接口中的屬性呈現(xiàn)Zipf分布。這就說明通過人工分析方式獲取領(lǐng)域?qū)傩訟的可行性，因此通過分析同一個領(lǐng)域中的幾個數(shù)據(jù)源通常就足以發(fā)現(xiàn)領(lǐng)域中重要的屬性并獲得屬性的別名信息。

在深網(wǎng)資源采集中，可以用領(lǐng)域知識定義數(shù)據(jù)采集任務(wù)，領(lǐng)域?qū)傩詀則表示出現(xiàn)在與采集任務(wù)相關(guān)的深網(wǎng)查詢接口中的查詢輸入項，屬性a的別名aliases則用于標(biāo)識屬性a在查詢接口中出現(xiàn)的替代標(biāo)簽，如針對圖書采集的領(lǐng)域知識中，屬性“作者”可能的別名有“著作者”、“譯著者”等，屬性a的affinity則用于標(biāo)識如果查詢接口包含該屬性時，該深網(wǎng)資源與領(lǐng)域相關(guān)的可能性，例如，在針對圖書資源采集時，屬性“ISBN”的affinity的取值會很高(如0.95)，因為，如果查詢接口允許對ISBN屬性進行查詢則幾乎可以肯定是對圖書進行查詢，而“價格”的affinity的取值則會比較低(如0.05)。其中屬性的affinity取值并不是固定的，可以因人而異。實例I則表示深網(wǎng)查詢接口中的查詢輸入項可用的取值。

3.2 領(lǐng)域知識抽樣算法

領(lǐng)域?qū)傩訟獲取之后，關(guān)鍵問題是如何獲得這些屬性的取值，即領(lǐng)域的實例集合I?？梢酝ㄟ^人工的方式為每個屬性選擇取值信息，獲得實例集合，但是這種方法明顯需要大量的時間和人力，難以擴展到大規(guī)模的深網(wǎng)采集任務(wù)上。為此，本文提出了基于領(lǐng)域?qū)傩缘某闃铀惴?，其主要思想是基于領(lǐng)域?qū)傩缘男畔ⅲ瑥脑诰€目錄服務(wù)(如ODP)、維基百科(Wikipedia)中選擇一些Web站點作為數(shù)據(jù)源自動實現(xiàn)屬性實例的獲取。本文使用OXPath[13]作為數(shù)據(jù)提取工具對Web頁面P進行內(nèi)容抽取，結(jié)果記為Results(P)，每條數(shù)據(jù)記錄用鍵-值對(key-value)的形式表示，即Results(P)={R1,R2, …,Rm}，其中，Ri={f1,f2, …,fn}，fj表示數(shù)據(jù)的字段信息：fj=，key表示數(shù)據(jù)的屬性，value表示屬性的取值。

然而，與通過人工方式提供的屬性實例相比，通過抽樣方式自動獲取的屬性實例的置信度無法保證與人工提供的相同，為此，我們引入屬性實例置信度函數(shù)F(c,a)，在抽樣過程中利用F(c,a)為屬性a的抽樣實例c分配一個權(quán)重wc(0≤wc≤1)，用于表示該抽樣實例的置信度。屬性實例置信度函數(shù)F(c,a)的定義和抽樣實例的構(gòu)造如下：

1) 如果在抽樣站點的Web頁面中，成功抽取到屬性a，則F(c,a)=1： 即在Ri中存在一個字段fj，其對應(yīng)的key與屬性a的名稱(a.name)或別名(a.aliases)中的某一個值相等，則構(gòu)造抽樣實例c=并加入到Ia中：wc=1，Ia=Ia∪{c}；

2) 如果在抽樣站點的Web頁面中，沒有抽取到屬性a，但是在Results(P)的數(shù)據(jù)記錄中字段fj對應(yīng)的取值有kj(0并加入到Ia中：wc=F(c,a)，Ia=Ia∪{c}；

3) 如果在抽樣站點的Web頁面中，沒有抽取到屬性a，在Results(P)的數(shù)據(jù)記錄中字段fj對應(yīng)的取值出現(xiàn)在屬性a的實例集合Ia中的次數(shù)為0時，則F(c,a)的定義如式(1)所示。

(1)

其中，B=a.aliases∪{a.name}，sim(keyj,bi)表示字段fj與bi的相似度：

(2)

其中，ed(fj.key,bi)為字段fj的key與bi的編輯距離[14]；|·|表示詞的長度。在此，選擇Results(P)與屬性a相似度最大的字段fj的取值構(gòu)造抽樣實例c=并加入到Ia中：wc=F(c,a)，Ia=Ia∪{c}。

通過上述方式得到針對屬性a的抽樣實例集合Ia，并得到該實例集合的置信度WIa：WIa={wc|c∈Ia}。下面將詳細介紹基于領(lǐng)域知識抽樣的深網(wǎng)資源采集方法。

4 深網(wǎng)資源采集

在引言中已分析指出，對深網(wǎng)進行采集時，需要解析頁面包含的查詢接口，并為查詢接口中的輸入項選擇合適的取值，不斷地向查詢接口主動提交查詢迭代地“發(fā)現(xiàn)”深網(wǎng)內(nèi)容。接下來我們介紹如何利用抽樣得到的領(lǐng)域知識，自動實現(xiàn)用戶指定的深網(wǎng)資源的采集。

4.1 查詢接口處理

查詢接口在網(wǎng)頁中是以HTML的Form元素表示的表單形式存在的，但是并不是所有的表單都是深網(wǎng)資源的查詢接口。因此，為了獲得Web站點中與采集任務(wù)相關(guān)的查詢接口，首先需要提取頁面包含的表單；然后過濾表單，獲得與采集任務(wù)相關(guān)的深網(wǎng)資源的查詢?nèi)肟?。目前，已有很多表單提取工具，如LabelEx[15]、HMME[16]、VisQIExt[17]、ExQ[18]和OPAL[19]等，Khare等人[20]對表單提取的相關(guān)工作進行了詳細的研究分析，我們使用OPAL[19]工具對頁面包含的表單進行提?。?OPAL 是典型的基于規(guī)則的表單提取工具，它利用表單的視覺信息生成提取規(guī)則，通過制定規(guī)則匹配常見的Web頁面設(shè)計方式。下面分別介紹表單提取過程中的查詢接口模型以及基于領(lǐng)域知識的查詢接口選擇算法。

4.1.1 查詢接口建模

查詢接口(QI, Query Interface)被表示成四元組：QI=，其中： 1)name表示查詢接口名稱；2)action用于標(biāo)識響應(yīng)查詢請求的服務(wù)器；3)method為向服務(wù)器發(fā)送查詢請求的HTTP請求方式，method={GET,POST}；4)elements為查詢接口包含的元素集合：elements={e1,e2,…,en}，其中ei=，label為用戶通過網(wǎng)頁可查看的元素名稱；name為元素的名稱，用于提交查詢，包含在HTTP請求中；type為元素的類型，type={text,textarea,radio,checkbox,select,button,submit,reset,image,file,hidden}；domains為元素的值域，表示元素可用的取值集合。在查詢接口中，一些元素的值域是有限集，其對應(yīng)的取值已經(jīng)嵌在Web頁面中，比如radio、checkbox、select類型的元素。而其它一些元素的值域則是無限集，如text類型的元素。

提取頁面包含的表單之后，則需要從這些表單中選擇與采集任務(wù)相關(guān)的查詢接口。

4.1.2 查詢接口選擇

如第三節(jié)所述，如果一個深網(wǎng)資源屬于定義的采集任務(wù)(記為T)，則該深網(wǎng)資源的查詢接口元素的label信息與領(lǐng)域知識DK中某個屬性a相關(guān)的概率會很高，因此，我們將查詢接口選擇問題轉(zhuǎn)換為計算查詢接口元素與領(lǐng)域?qū)傩缘南嗨贫扔嬎銌栴}，即查詢接口與采集任務(wù)的相關(guān)度R(QI,T)可以轉(zhuǎn)換為查詢接口與領(lǐng)域知識DK的相關(guān)度計算R(QI,DK)。R(QI,DK)可通過式(3)計算。

R(QI，T)=R(QI，DK)

(3)

其中，E表示查詢接口QI包含的元素集合：E=QI.elements；A為領(lǐng)域知識DK包含的屬性集合：A=DK.A；a.affinity表示屬性a與領(lǐng)域的相關(guān)度(見3.1節(jié))；S(e,a)表示查詢接口的元素e與領(lǐng)域?qū)傩詀的相似度：S(e,a)定義為：

(4)

其中，B={a.name}∪a.aliases；sim(e.label,b)計算方法如式(2)所示(見3.2節(jié))。

查詢接口選擇算法的基本思想是： 基于抽樣獲取的領(lǐng)域知識DK和提取的查詢接口模式信息，實現(xiàn)查詢接口與采集任務(wù)相關(guān)度R(QI,T)的計算，并根據(jù)設(shè)定的相關(guān)度閾值μ判斷查詢接口是否屬于定義的采集任務(wù)。獲得與采集任務(wù)相關(guān)的深網(wǎng)資源的查詢?nèi)肟诤?，接下來則需要為查詢接口選擇合適的輸入值進行填充，從而生成有效的表單查詢請求，實現(xiàn)深網(wǎng)資源的采集。下面我們介紹查詢接口的查詢請求生成算法。

4.2 查詢實例生成

在4.1節(jié)，在對查詢接口QI進行采集任務(wù)相關(guān)性判斷時，是通過計算查詢接口元素e與領(lǐng)域?qū)傩詀的文本相似度S(e,a)實現(xiàn)的。為此，我們也通過查詢接口元素e與領(lǐng)域?qū)傩詀的文本匹配對元素e進行賦值。具體地說，對于QI的每個元素ei，我們采用以下方式為其取值生成一個賦值集合Vi，并用pvik表示為元素ei選取第k個值的置信度，PVi={pvik|vik∈Vi}表示該賦值行為的置信度：

? 如果ei是選擇輸入項(radio、checkbox、select類型的元素)，則Vi=ei.domains，并且PVi=1；

? 如果ei是文本輸入項，則選擇屬性aj=argmaxaj∈DK.A{S(ei,aj)}的實例集合Iaj對元素ei進行賦值：Vi={ck.value|ck∈Iaj}，pvik=wck，PVi=WIa，其中，aj∈DK.A；

? 如果通過上述兩種情況無法獲得元素ei的取值，則Vi=?，并且令PVi=1。

對QI的每個元素ei按照上述方式賦值之后，基于領(lǐng)域知識抽樣DK為查詢接口QI生成的所有的賦值集合為Q(QI,DK)={|vi∈ei.V}。通過3.2節(jié)可知，在進行知識抽樣時每個屬性實例c的權(quán)重wc可能不同，也就是說利用抽樣獲得的領(lǐng)域知識DK為QI的元素賦值時，該賦值的置信度不同。因此，在每次深網(wǎng)查詢提交時，我們需要從查詢接口的賦值集合Q(QI,DK)中選擇“最好”的賦值生成查詢實例。這里，“最好”的賦值是基于對Q(QI,DK)中所有賦值的排序(ranking)，排序的依據(jù)是按照Q(QI,DK)中每個賦值組成部分的最小置信度pv的值進行排序，排序函數(shù)φr定義如式(5)所示。

(5)

利用貪心選擇策略，從Q(QI,DK)中選擇φr最大的賦值生成查詢實例，并對查詢實例的響應(yīng)結(jié)果利用抽樣算法為查詢接口生成新的賦值。通過上述過程，迭代地為查詢接口QI自動生成查詢實例，實現(xiàn)查詢接口QI后端深網(wǎng)資源的采集。

5 實驗和評價

深網(wǎng)資源采集一般選用查詢提交效率(submission efficient，SE)和資源覆蓋率(coverage rate，CR)作為方法評價指標(biāo)[5]。查詢提交效率的定義如下：SE=Nsuccess/Ntotal，其中，Ntotal表示在采集過程中對查詢接口QI生成的查詢實例的總數(shù)；用Nsuccess表示在查詢實例對應(yīng)的響應(yīng)結(jié)果頁中能夠獲得一個或多個搜索結(jié)果的查詢實例的數(shù)目；資源覆蓋率的定義如下：CR=Rretrieval/RDB，其中，RDB表示該深網(wǎng)數(shù)據(jù)庫的資源總數(shù)，Rretrieval表示通過查詢提交采集到的資源數(shù)目。查詢提交效率用于評估在給定時間內(nèi)，深網(wǎng)采集方法完成采集任務(wù)的有效率，查詢提交效率越高，將會獲取更多有用的深網(wǎng)資源的可能性越大；資源覆蓋率用于評價采集深網(wǎng)資源的能力，資源覆蓋率越高，采集到的深網(wǎng)資源的數(shù)據(jù)量越大。本文也采用它們作為我們工作的評價指標(biāo)。本文利用基于隨機策略的查詢實例生成方法[6](記為Random)和基于Zipf策略的查詢實例生成方法[11](記為Zipf)與基于領(lǐng)域知識抽樣的查詢實例生成方法(記為DKS)進行對比測試。

5.1 數(shù)據(jù)集

我們選擇了一個論文數(shù)據(jù)庫： DBLP數(shù)據(jù)庫，記為DBLP，該數(shù)據(jù)庫可以免費從Web下載，我們選擇的DBLP包含一百萬條記錄，將其部署在遠程服務(wù)器上，用于模擬深網(wǎng)資源的抓取，我們設(shè)定DBLP數(shù)據(jù)庫的每個查詢結(jié)果列表頁最多包含20條記錄。另外，我們又選用了兩個在線圖書數(shù)據(jù)庫： 當(dāng)當(dāng)圖書和京東圖書，分別記為DBooks和JBooks，當(dāng)當(dāng)目前在庫圖書有60萬種，京東目前在庫圖書有40萬種。對于DBLP，我們選取論文題目、作者名、期刊/會議名稱、時間作為查詢實例生成屬性，對于當(dāng)當(dāng)圖書和京東圖書，選擇書名、作者名、出版社、類別作為查詢實例生成屬性。

5.2 實驗結(jié)果與分析

在上述三個數(shù)據(jù)庫上，分別利用領(lǐng)域知識抽樣方法(DSK)、隨機方法(Random)和Zipf方法(Zipf)對查詢提交的效率和資源覆蓋率進行比較。從ODP目錄劃分的“圖書”分類中選擇當(dāng)當(dāng)網(wǎng)和亞馬遜作為圖書領(lǐng)域知識抽樣站點，從“Conferences”分類中選擇DBLP和IEEE作為學(xué)術(shù)論文知識抽樣站點，生成初始候選查詢集合。Random方法每次隨機地從響應(yīng)結(jié)果頁中選擇一個新詞生成下一輪的查詢實例，Zipf方法則利用詞在頁面中出現(xiàn)的詞頻選擇出現(xiàn)頻率最大的新詞生成下一輪的查詢實例。

(1) 查詢提交效率

我們利用DSK、Random、Zipf在三個數(shù)據(jù)庫上分別生成查詢實例用于查詢提交效率的測試，圖1(a)(b)(c)分別表示不同數(shù)據(jù)庫上三種方法得到的查詢提交效率的比較。

圖1 查詢提交效率實驗

圖1中，橫坐標(biāo)表示查詢實例的個數(shù)，縱坐標(biāo)表示查詢提交的效率(SE)，由實驗結(jié)果可知，隨著提交的查詢實例數(shù)的增加，三種方法的查詢提交效率都在降低，但是DSK方法的查詢提交效率在所有測試用例中均優(yōu)于Random方法和Zipf方法，而且當(dāng)提交的查詢數(shù)量增加時，其優(yōu)勢越明顯。由此可見，在對深網(wǎng)資源進行采集時，人工參與可以提高深網(wǎng)采集方法獲取更多有用的深網(wǎng)資源的概率，使得在給定時間內(nèi)完成采集任務(wù)的效率越高。

(2) 資源覆蓋率

我們利用DSK、Random、Zipf分別對三個數(shù)據(jù)庫進行資源采集，在本實驗中，只要有一種方法爬取的資源覆蓋率大于80%就停止實驗。圖2(a)(b)(c)分別表示不同數(shù)據(jù)庫上三種方法得到的資源覆蓋率的比較。

圖2 資源覆蓋率實驗

圖2中，橫坐標(biāo)表示向數(shù)據(jù)庫提交查詢的次數(shù)，這里的查詢次數(shù)不是查詢實例提交的個數(shù)，而是查詢請求的次數(shù)(一個查詢實例返回的結(jié)果可能分多頁顯示，如果想獲取該查詢實例對應(yīng)的所有結(jié)果必須通過翻頁得到，每一次翻頁相當(dāng)于一次查詢請求)，縱坐標(biāo)表示數(shù)據(jù)庫資源的覆蓋率(CR)，由實驗結(jié)果可以，在三個數(shù)據(jù)庫上都是DKS方法最先達到80%以上的資源覆蓋率，由此可見，人工參與的基于領(lǐng)域知識抽樣的深網(wǎng)資源采集方法能夠以最小的代價獲取更多的深網(wǎng)資源。

實驗結(jié)果表明，本文提出的基于領(lǐng)域知識抽樣的深網(wǎng)資源采集方法比隨機方法和Zipf方法具有更優(yōu)異的性能表現(xiàn)，它的查詢提交效率和資源覆蓋率均優(yōu)于其它對比系統(tǒng)。

6 總結(jié)

在本文中，我們提出了一種面向特定領(lǐng)域/應(yīng)用的深網(wǎng)采集方法，該方法利用在線目錄服務(wù)實現(xiàn)特定采集任務(wù)的知識抽樣，基于知識抽樣自動實現(xiàn)深網(wǎng)資源的采集。實驗表明該方法能夠有效解決隱藏在Form表單后端的深網(wǎng)資源的采集問題。目前，本文所采用的領(lǐng)域知識的抽樣方法依賴人工分析獲取的領(lǐng)域?qū)傩院统闃诱军c信息，下一步我們將研究利用深網(wǎng)站點自身提供的數(shù)據(jù)自動生成查詢實例，實現(xiàn)深網(wǎng)采集。

[1] M K Bergman, The Deep Web: Surfacing Hidden Value[J]. Journal of Electronic Publishing, 2001，7(1)[DB/OL]DOI:http://dx.doi.org110.399813336451.0007.104

[2] K C C Chang, B He, C Li, et al. Structured databases on the web: Observations and implications[R]. ACM SIGMOD Record, 2004，33(3): 61-70.

[3] B He, M Patel, et al., Accessing the deep web:A Survey[C]//Proceedings of the Communications of the ACM, 2007， 50(5): 94-101.

[4] 劉偉, 孟小峰, 凌妍妍, 一種基于圖模型的 Web 數(shù)據(jù)庫采樣方法[J]. 軟件學(xué)報, 2008， 19(2): 179-193.

[5] S Raghavan, H Garcia-Molina. Crawling the Hidden Web[C]//Proceedings of 27th VLDB. 2001:129-138.

[6] P Wu, J R Wen, H Liu, et al. Query selection techniques for efficient crawling of structured web sources[C]//Proceedings of the 22nd International Conference on Data Engineering. 2006: 47-56.

[7] M A lvarez, J Raposo, F Cacheda, et al., A Task-specific approach for crawling the deep web[J]. Journal Engineering Letters. Special Issue: Advances in Information Engineering, 2006， 13(2): 204-215.

[8] M A Lvarez, J Raposo, A Pan, et al. DeepBot: a focused crawler for accessing hidden web content[C]//Proceedings of the ACM Conference on Electronic Commerce. 2007:18-25.

[9] J Madhavan, D Ko, L Kot, et al. Google’s deep web crawl[J]. VLDB Endowment, 2008,1(2): 1241-1252.

[10] L Jiang, Z Wu, Q Zheng, et al. Learning deep web crawling with diverse features[C]//Proceedings of the IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technologies. 2009: 572-575.

[11] L Jiang, Z Wu, Q Feng, et al., Efficient deep web crawling using reinforcement learning[J]. Advances in Knowledge Discovery and Data Mining, 2010: 428-439.

[12] Q Zheng, Z Wu, X Cheng, et al., Learning to Crawl Deep Web[R]. Information Systems, 2013,38(6):801-819.

[13] T Furche, G Gottlob, G Grasso, et al., OXPATH: A Language for Scalable Data Extraction, Automation, and Crawling on the Deep Web[J]. The VLDB Journal, 2012，22(1): 47-72.

[14] V I Levenshtein. Binary codes capable of correcting deletions[J], insertions and reversals. 1966，10(8)： 707-710.

[15] H Nguyen, T Nguyen, J Freire, Learning to extract form labels[R]. VLDB Endowment, 2008，1(1): 684-694.

[16] R Khare. An empirical study on using hidden markov model for search interface segmentation[C]//Proceedings of the 18th ACM Conference on Information and Knowledge Management, 2009: 17-26.

[17] E C Dragut, T Kabisch, C Yu, et al., A hierarchical approach to model web query interfaces for web source integration[C]//Proceedings of the VLDB Endowment, 2009，2(1): 325-336.

[18] W Wu, A H Doan, C Yu, et al., Modeling and extracting deep-web query interfaces[J]. Advances in Information and Intelligent Systems, 2009: 65-90.

[19] T Furche, G Gottlob, G Grasso, et al. OPAL: automated form understanding for the deep web[C]//Proceedings of the 21st International Conference on World Wide Web. 2012: 829-838.

[20] R Khare, Y An, I Y Song, Understanding deep web search interfaces: a survey[R]. SIGMOD record, 2010，39(1): 33-40.

An Approach to Crawling the Deep Web Based on Domain Knowledge Sampling

LIN Hailun1,2, XIONG Jinhua1, WANG Bo3, CHENG Xueqi1

(1. Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China; 2. University of Chinese Academy of Sciences, Beijing 100049, China; 3. CNCERT/CC, Beijing 100029, China)

The Deep Web refers to the Web databases content hidden behind HTML forms, which can only be accessed by performing form submissions. The current web page collection technologies can not cover these resources effectively by employing only hyperlinks. For this purpose, this paper proposes an approach to crawling the deep web based on domain knowledge sampling. Firstly, it creates a domain attributes set using open source directory services and assigns the attributes based on a confidence function; Secondly, it uses the domain attributes set to select query interface and generate assignments, and finally, it selects the assignment with the highest confidence as a query instance for deep web crawling based on greedy algorithm. Experiments show that our approach can effectively collect the deep web resources.

deep web; confidence; sampling; domain knowledge

林海倫(1987-)，通信作者，博士，助理研究員，主要研究領(lǐng)域為數(shù)據(jù)挖掘、知識圖譜。E?mail：linlunnian@software．ict．a(chǎn)c．cn熊錦華(1972-)，博士，副研究員，主要研究領(lǐng)域為大規(guī)模數(shù)據(jù)處理、搜索引擎等。E?mail：xjh@ict．a(chǎn)c．cn王博(1982-)，博士，高級工程師，主要研究領(lǐng)域為網(wǎng)絡(luò)與信息安全、社會計算。E?mail：wbxyz@163．com

1003-0077(2016)02-0175-07

2013-06-08 定稿日期： 2013-12-09

國家科技支撐計劃課題(2011BAH11B02,2012BAH46B04)；國家242專項(2013G129)；國家自然科學(xué)基金(61300206)

TP391

A