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

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

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

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

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

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

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

1 引言

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

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

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

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

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

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

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

4.1 查詢接口處理

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

4.1.1 查詢接口建模

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

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

4.1.2 查詢接口選擇

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

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

(3)

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

(4)

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

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

4.2 查詢實(shí)例生成

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

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

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

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

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

(5)

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

5 實(shí)驗(yàn)和評(píng)價(jià)

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

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

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

5.2 實(shí)驗(yàn)結(jié)果與分析

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

(1) 查詢提交效率

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

圖1 查詢提交效率實(shí)驗(yàn)

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

(2) 資源覆蓋率

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

圖2 資源覆蓋率實(shí)驗(yàn)

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

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

6 總結(jié)

在本文中，我們提出了一種面向特定領(lǐng)域/應(yīng)用的深網(wǎng)采集方法，該方法利用在線目錄服務(wù)實(shí)現(xiàn)特定采集任務(wù)的知識(shí)抽樣，基于知識(shí)抽樣自動(dòng)實(shí)現(xiàn)深網(wǎng)資源的采集。實(shí)驗(yàn)表明該方法能夠有效解決隱藏在Form表單后端的深網(wǎng)資源的采集問(wèn)題。目前，本文所采用的領(lǐng)域知識(shí)的抽樣方法依賴人工分析獲取的領(lǐng)域?qū)傩院统闃诱军c(diǎn)信息，下一步我們將研究利用深網(wǎng)站點(diǎn)自身提供的數(shù)據(jù)自動(dòng)生成查詢實(shí)例，實(shí)現(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ù)庫(kù)采樣方法[J]. 軟件學(xué)報(bào), 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)域?yàn)閿?shù)據(jù)挖掘、知識(shí)圖譜。E?mail：linlunnian@software．ict．a(chǎn)c．cn熊錦華(1972-)，博士，副研究員，主要研究領(lǐng)域?yàn)榇笠?guī)模數(shù)據(jù)處理、搜索引擎等。E?mail：xjh@ict．a(chǎn)c．cn王博(1982-)，博士，高級(jí)工程師，主要研究領(lǐng)域?yàn)榫W(wǎng)絡(luò)與信息安全、社會(huì)計(jì)算。E?mail：wbxyz@163．com

1003-0077(2016)02-0175-07

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

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

TP391

A