顧偉，傅德勝，蔡瑋

0 引言

隨著Web的飛速發(fā)展，Deep Web中蘊(yùn)藏著海量高質(zhì)量數(shù)據(jù)。使用傳統(tǒng)搜索引擎在Internet表面檢索到的信息只是其中的一小部，在Internet深處還存在海量信息無(wú)法被搜索到，這些信息被稱為Deep Web[1]。Deep Web數(shù)據(jù)量是非常巨大的，大約是可索引的web信息的500倍。目前Deep Web數(shù)據(jù)集成主要有兩種實(shí)現(xiàn)方式：一種是基于元搜索的方法，提供一個(gè)統(tǒng)一的查詢接口，將用戶查詢通過(guò)語(yǔ)義映射轉(zhuǎn)發(fā)到相應(yīng)的Deep Web數(shù)據(jù)源，返回的結(jié)果通過(guò)提取，語(yǔ)義標(biāo)注，去重合并后呈現(xiàn)給用戶。該方法不需要維護(hù)本地?cái)?shù)據(jù)庫(kù)，但查詢響應(yīng)時(shí)間由遠(yuǎn)程數(shù)據(jù)源的服務(wù)質(zhì)量決定。另一種方案就是將Deep Web中爬取出來(lái)的內(nèi)容存儲(chǔ)在本地動(dòng)態(tài)網(wǎng)頁(yè)拷貝庫(kù)中，并通過(guò)建立索引來(lái)縮短用戶查詢的響應(yīng)時(shí)間[2]。該方案的關(guān)鍵問(wèn)題是如何讓本地?cái)?shù)據(jù)與遠(yuǎn)程數(shù)據(jù)同步。本文在相同更新資源條件下，使本地和遠(yuǎn)程數(shù)據(jù)保持最大化同步。

由于Deep Web數(shù)據(jù)的動(dòng)態(tài)性，其數(shù)據(jù)往往處于頻繁更新的狀態(tài)，但用戶總是希望得到最新的內(nèi)容[3]。由于不同的Deep Web數(shù)據(jù)源中數(shù)據(jù)記錄的變化頻率是不一樣的，根據(jù)統(tǒng)一的頻率更新所有的本地?cái)?shù)據(jù)非常耗費(fèi)資源。由于 Deep Web數(shù)據(jù)處于快速動(dòng)態(tài)的更新?tīng)顟B(tài)，本文提出的方法可以有效地提高Deep Web數(shù)據(jù)集成服務(wù)質(zhì)量，實(shí)現(xiàn)Deep Web數(shù)據(jù)的自動(dòng)增量更新，從而使Deep Web數(shù)據(jù)可以更好地為科研、生產(chǎn)和決策服務(wù)。

自Deep Web概念提出以來(lái)，國(guó)內(nèi)外學(xué)者對(duì)如何有效利用Deep Web信息做了廣泛研究。針對(duì)Deep Web數(shù)據(jù)提取，Ntoulas Alexandros[4]對(duì)Deep Web查詢生成制定了有效的生成策略。Capi等[5]將強(qiáng)化學(xué)習(xí)用于主題相關(guān)評(píng)估計(jì)算中，控制了搜索的正確方向。為了解決典型強(qiáng)化學(xué)習(xí)存在的“維數(shù)災(zāi)難”問(wèn)題[6]，近年來(lái)出現(xiàn)了分層強(qiáng)化學(xué)習(xí)法[7]和搜索空間限定法[8]等方法，主要通過(guò)對(duì)問(wèn)題抽象來(lái)實(shí)現(xiàn)。搜索空間限定法通過(guò)在受限的策略空間中搜索最優(yōu)，容易引起局部最優(yōu)。分層強(qiáng)化學(xué)習(xí)法借助抽象方法將強(qiáng)化學(xué)習(xí)任務(wù)進(jìn)行分解，實(shí)現(xiàn)降維，從而各層學(xué)習(xí)任務(wù)在低維空間中就可完成，但針對(duì)增量數(shù)據(jù)爬取，很難進(jìn)行分層處理。為此，本文采用邏輯強(qiáng)化學(xué)習(xí)方法可以很好地解決這個(gè)問(wèn)題。

近年來(lái)，國(guó)內(nèi)研究機(jī)構(gòu)，如蘇州大學(xué)[9]和中國(guó)人民大學(xué)[10]對(duì)Deep Web信息提取進(jìn)行了深入的研究。然而，國(guó)內(nèi)其他學(xué)者對(duì)Deep Web增量數(shù)據(jù)提取問(wèn)題研究較少，在Surface Web增量數(shù)據(jù)提取方面作了一定的研究。

1 Deep Web簡(jiǎn)介

Internet已經(jīng)成為當(dāng)今社會(huì)人們獲取信息的主要來(lái)源，尤其是數(shù)據(jù)庫(kù)技術(shù)與網(wǎng)絡(luò)技術(shù)的結(jié)合，使Internet擁有了最為巨大的信息量，進(jìn)而衍生出深度網(wǎng)（Deep Web）。最初由Dr.Jill Ellsworth于l994年提出，指那些由普通搜索引擎難以發(fā)現(xiàn)其信息內(nèi)容的web頁(yè)面。2001年，Christ Sherman等定義Deep Web為：雖然通過(guò)互聯(lián)網(wǎng)可以獲取，但普通搜索引擎由于受技術(shù)限制而不能或不作索引的那些文本頁(yè)、文件或其它通常是高質(zhì)量、權(quán)威的信息。

據(jù)最近對(duì)Deep Web的調(diào)查得到了以下有意義的發(fā)現(xiàn)：當(dāng)前Deep Web的規(guī)模為307,000個(gè)站點(diǎn)，450,000個(gè)數(shù)據(jù)庫(kù)和1,258,000個(gè)查詢接口，在2000-2004年間增長(zhǎng)了3-7倍；Deep Web廣泛分布于幾乎所有的學(xué)科領(lǐng)域；Deep Web對(duì)于主流搜索引擎來(lái)說(shuō)并不是完全不可見(jiàn)，大約有1/3的數(shù)據(jù)已經(jīng)被覆蓋；Deep Web中的數(shù)據(jù)大多是結(jié)構(gòu)化的；盡管一些Deep Web的目錄服務(wù)已經(jīng)開(kāi)始索引Web上的數(shù)據(jù)庫(kù)，但是他們的覆蓋率很小約為0.2%到15.6%；Web數(shù)據(jù)庫(kù)往往位于站點(diǎn)的較淺層，94%的Web數(shù)據(jù)庫(kù)位于站點(diǎn)Web數(shù)據(jù)庫(kù)往往位于站點(diǎn)的較淺層，94%的Web數(shù)據(jù)庫(kù)位于站點(diǎn)前3層。

2 基于邏輯強(qiáng)化學(xué)習(xí)的增量數(shù)據(jù)提取方法

Deep Web檢索系統(tǒng)的數(shù)據(jù)庫(kù)復(fù)制了遠(yuǎn)程數(shù)據(jù)庫(kù)的對(duì)象信息，但當(dāng)遠(yuǎn)程數(shù)據(jù)庫(kù)的對(duì)象信息發(fā)生改變時(shí)，本地?cái)?shù)據(jù)庫(kù)無(wú)法知曉，必須周期性檢測(cè)遠(yuǎn)程數(shù)據(jù)庫(kù)的變化情況，因此需要根據(jù)遠(yuǎn)程數(shù)據(jù)庫(kù)的變化規(guī)律來(lái)確定兩者之間的同步頻率。

2.1 強(qiáng)化學(xué)習(xí)的簡(jiǎn)介

馬爾可夫決策程序(MDP)[11]的邏輯組成對(duì)應(yīng)于一個(gè)有窮的狀態(tài)機(jī)，由于狀態(tài)和活動(dòng)是非結(jié)構(gòu)的，因此這個(gè)自動(dòng)機(jī)必須是以命題表示。通過(guò)邏輯馬爾可夫決策程序可以通過(guò)邏輯符號(hào)來(lái)替代同類狀態(tài)和活動(dòng)，最大程度地減少狀態(tài)和活動(dòng)的數(shù)量。針對(duì)強(qiáng)化學(xué)習(xí)一直被“維數(shù)災(zāi)難”問(wèn)題所困擾的問(wèn)題，在關(guān)系強(qiáng)化學(xué)習(xí)的基礎(chǔ)上，將邏輯謂詞規(guī)則與強(qiáng)化學(xué)習(xí)相結(jié)合，形成一種新的邏輯強(qiáng)化學(xué)習(xí)方法，采用輪廓表表達(dá)的狀態(tài)和活動(dòng)[12]，可以準(zhǔn)確地表達(dá)。

2.2 同步頻率確定

泊松過(guò)程[13]是一個(gè)常用于描寫(xiě)隨機(jī)事件累計(jì)發(fā)生次數(shù)的基本數(shù)學(xué)模型，表面上看，只要隨機(jī)事件在不相交時(shí)間區(qū)間是重復(fù)獨(dú)立發(fā)生，而且在充分小的區(qū)間上最多只發(fā)生一次，它們的累計(jì)次數(shù)就是一個(gè)泊松過(guò)程。在很多應(yīng)用場(chǎng)合都可以近似地歸結(jié)為泊松過(guò)程。文中采用泊松過(guò)程來(lái)描述對(duì)象信息的變化情況，使得本地?cái)?shù)據(jù)庫(kù)可以更好地與遠(yuǎn)程數(shù)據(jù)庫(kù)保持同步。

2.3 Deep Web數(shù)據(jù)更新

根據(jù)Deep Web的特性，可根據(jù)有兩種不同的粒度制定Deep Web數(shù)據(jù)更新策略[14-15]，分別通過(guò)數(shù)據(jù)源的重要性權(quán)重和數(shù)據(jù)源的變化頻率、以及數(shù)據(jù)記錄的歷史變化頻率來(lái)確定更新頻率。

2.4 Deep Web新數(shù)據(jù)發(fā)現(xiàn)

基于邏輯強(qiáng)化學(xué)習(xí)算法，在Deep Web數(shù)據(jù)獲取的過(guò)程中進(jìn)行在線學(xué)習(xí)。根據(jù)關(guān)鍵詞或關(guān)鍵詞的組合所返回結(jié)果中新記錄數(shù)，設(shè)置相應(yīng)的獎(jiǎng)賞值。根據(jù)學(xué)習(xí)結(jié)果，對(duì)可能出現(xiàn)新數(shù)據(jù)的關(guān)鍵詞或關(guān)鍵詞的組合分配更多的資源。在相同資源約束前提下，可有效提高新數(shù)據(jù)的發(fā)現(xiàn)效率。

為了避免在數(shù)據(jù)獲取過(guò)程中搜索樹(shù)膨脹，采用將強(qiáng)化學(xué)習(xí)技術(shù)應(yīng)用到數(shù)據(jù)獲取的可控網(wǎng)絡(luò)爬蟲(chóng)方法中。該方法通過(guò)強(qiáng)化學(xué)習(xí)技術(shù)得到一些控制“經(jīng)驗(yàn)信息”，根據(jù)這些信息來(lái)預(yù)測(cè)較遠(yuǎn)的回報(bào)，按照某一主題進(jìn)行搜索，以使累積返回的回報(bào)值最大。

基于邏輯強(qiáng)化學(xué)習(xí)的爬蟲(chóng)（LQ-Spider）的訓(xùn)練抓取過(guò)程包括下列步驟。

步驟1.提供待查詢數(shù)據(jù)的主題，分別構(gòu)建站點(diǎn)初始訓(xùn)練隊(duì)列URL，然后提取隊(duì)首隊(duì)列URL，分析其頁(yè)面結(jié)構(gòu)提取頁(yè)面中的鏈接地址 URL，并根據(jù)頁(yè)面關(guān)鍵信息計(jì)算鏈接地址的立即回報(bào)，結(jié)合經(jīng)驗(yàn)得出未來(lái)回報(bào)值，然后結(jié)合Value值詞庫(kù)中未來(lái)回報(bào)來(lái)計(jì)算該鏈接地址的綜合Q值。

步驟2.權(quán)衡立即回報(bào)價(jià)值和未來(lái)回報(bào)價(jià)值的信任度，即現(xiàn)在是處理利用階段還是探索階段，控制信任度。根據(jù)URL 地址的深度因子是否大于5，如果深度因子大于5，則拋棄，不放入待提取 URL隊(duì)列。據(jù)調(diào)查，91%的深層網(wǎng)頁(yè)查詢接口所在頁(yè)面的深度都在5層之內(nèi)，因此當(dāng)URL鏈接的深度大于5時(shí)，就不處理該鏈接，可以在保證準(zhǔn)確度的前提下，有效減小處理量。

步驟3.當(dāng)?shù)玫缴疃纫蜃有∮?的 URL鏈接后，然后判斷其綜合Q值是否大于某個(gè)主題值，如果是則更新Value值詞庫(kù)中的原屬性值，并用新的Value值詞庫(kù)來(lái)計(jì)算未來(lái)回報(bào)，然后根據(jù)URL優(yōu)先權(quán)放入待提取URL隊(duì)列中，如此反復(fù)訓(xùn)練直到得到最終的待提取URL隊(duì)列，然后由爬蟲(chóng)程序有目的的抓取Deep Web中增量信息。如果綜合Q值小于某個(gè)主題值，則舍去該URL。返回步驟（1）繼續(xù)下一輪訓(xùn)練。

3 實(shí)驗(yàn)驗(yàn)證

在這一節(jié)中，通過(guò)具體的實(shí)驗(yàn)來(lái)評(píng)估所提出的方法的有效性和可行性。首先，需對(duì)其理論基礎(chǔ)進(jìn)行分析驗(yàn)證該新方法的可行性，然后，在此基礎(chǔ)上進(jìn)一步驗(yàn)證采用該方法的性能優(yōu)劣。

3.1 驗(yàn)證變化規(guī)律

研究表明網(wǎng)頁(yè)的變化頻率可以用泊松過(guò)程來(lái)表達(dá)。實(shí)驗(yàn)數(shù)據(jù)集采用加利福尼亞大學(xué)一科研小組采集的 Web對(duì)象信息。該數(shù)據(jù)集包括書(shū)籍、汽車、論壇和工作4個(gè)領(lǐng)域的對(duì)象信息。該數(shù)據(jù)集借助爬蟲(chóng)程序收集了一年半。收集到的Web對(duì)象數(shù)據(jù)集如表1所示：

表1 Web對(duì)象數(shù)據(jù)集

通過(guò) λ= X/ T計(jì)算對(duì)象的平均變化頻率，X表示時(shí)間段T內(nèi)的變化次數(shù)。上述數(shù)據(jù)集的平均變化頻率在各時(shí)段的對(duì)象個(gè)數(shù)如表2所示：

表2 平均變化頻率在各時(shí)段內(nèi)的對(duì)象個(gè)數(shù)

接著，統(tǒng)計(jì)不同領(lǐng)域平均變化頻率相同的對(duì)象，各時(shí)間點(diǎn)t附近的對(duì)象變化概率如圖1所示：

圖1 間隔為10天的對(duì)象信息變化規(guī)律

X軸表示對(duì)象相鄰變化的時(shí)間間隔，Y軸表示對(duì)象變化的比例。根據(jù)泊松過(guò)程曲線可以明顯看出對(duì)象變化規(guī)律符合泊松過(guò)程。

3.2 驗(yàn)證新方法的性能

目前評(píng)價(jià)聚焦爬蟲(chóng)性能指標(biāo)主要是通過(guò)計(jì)算抓取的相關(guān)頁(yè)面和不相關(guān)頁(yè)面的比率來(lái)衡量爬蟲(chóng)優(yōu)劣。本文采用收獲率方法來(lái)進(jìn)行評(píng)估不同爬蟲(chóng)的性能。其中

實(shí)驗(yàn)通過(guò)采用基于邏輯強(qiáng)化學(xué)習(xí)的Deep Web聚焦爬蟲(chóng)（LQ-Spider）和常用 Deep Web爬蟲(chóng)（如 Best-first和Breadth-first）對(duì)工作和論壇兩個(gè)領(lǐng)域的數(shù)據(jù)源進(jìn)行抓取分析，來(lái)比較不同方法的爬蟲(chóng)獲取信息的收獲率，實(shí)驗(yàn)結(jié)果如圖2所示：

圖2 兩種數(shù)據(jù)提取方法比較

為了檢驗(yàn)采用不同方法的Deep Web聚焦爬蟲(chóng)的爬行效果，本文選取工作和論壇兩個(gè)領(lǐng)域，分別采用 Best-first、Breadth-first策略和我們的爬行策略(LQ)進(jìn)行爬行，圖2所示比較了幾種爬蟲(chóng)的抓取性能，其中 X軸表示爬蟲(chóng)抓取的結(jié)果頁(yè)數(shù)量，y軸表示收獲率。另外每個(gè)結(jié)果頁(yè)面包括從后臺(tái)數(shù)據(jù)庫(kù)中取到至少十條數(shù)據(jù)記錄。實(shí)驗(yàn)結(jié)果表明，采用基于邏輯強(qiáng)化學(xué)習(xí)的爬蟲(chóng)能夠獲取更多的信息，本文提出的爬行策略取得了較好的應(yīng)用效果，大大提高了爬蟲(chóng)的收獲率。

4 總結(jié)

對(duì)于Deep Web增量數(shù)據(jù)提取問(wèn)題，主要存在數(shù)據(jù)更新和發(fā)現(xiàn)新數(shù)據(jù)兩大難點(diǎn)。而它們的關(guān)鍵是更新頻率和新數(shù)據(jù)的發(fā)現(xiàn)。由于在處理此類問(wèn)題時(shí)存在狀態(tài)爆炸和難以分層處理等問(wèn)題，這樣很難用傳統(tǒng)的強(qiáng)化學(xué)習(xí)方法加以解決。為此，本文在分析了Deep Web數(shù)據(jù)更新頻率基礎(chǔ)上，提出了一種強(qiáng)化學(xué)習(xí)的 Deep Web數(shù)據(jù)提取方法。結(jié)果表明，該新方法能提高數(shù)據(jù)的時(shí)新性和新數(shù)據(jù)的發(fā)現(xiàn)效率，可有效提高Deep Web信息集成服務(wù)質(zhì)量。下一步還需進(jìn)一步優(yōu)化爬蟲(chóng)算法和更新頻率提高獲取的準(zhǔn)確度。

[1]Luciano Barbosa, Juliana Freire.Siphoning Hidden-Web Data through Keyword-Based Interfaces[C].Proceedings of Brazilian Symposium on Databases, Brasília, DF, Brasil, 2004: 309-321.

[2]鮮學(xué)豐, 崔志明, 趙朋朋, 等.基于循環(huán)策略和動(dòng)態(tài)知識(shí)的 Deep Web數(shù)據(jù)獲取方法[J].通信學(xué)報(bào),2012,33(10):35-43.

[3]He B., Patel M., Zhang Z., et al.Accessing the Deep Web:A Survey[J].Communications of the ACM, 2007,50(5):94-101.

[4]劉全, 高陽(yáng), 陳蓄道, 等.一種基于啟發(fā)式輪廓表的邏輯強(qiáng)化學(xué)習(xí)方法[J].計(jì)算機(jī)研究與發(fā)展, 2008, 45(11):1824-1830.

[5]孟濤, 王繼民, 閆宏飛.網(wǎng)頁(yè)變化與增量搜集技術(shù)[J].軟件學(xué)報(bào), 2006，17(5):1051-1067.

[6]趙朋朋.Deep Web信息集成若干關(guān)鍵技術(shù)研究[D].蘇州大學(xué)博士論文, 2008.

[7]Cho J., Ntoulas A., Effective Change Detection Using Sampling[C].Proceedings of 28th International Conference on Very Large Data Bases, Hong Kong, China,Springer Berlin, 2002: 514-525.

[8]Wu Ping, Wen Ji-Rong, Liu Huan, et al.Query Selection Techniques for Efficient Crawling of Structured Web Sources[C].Proceedings of the 22th International Conference on Data Engineering.Atlanta,GA,USA.IEEE Computer Society, 2006:47-56.

[9]劉偉, 孟小峰, 孟衛(wèi)一.Deep Web數(shù)據(jù)集成研究綜述[J].計(jì)算機(jī)學(xué)報(bào), 2007,30(9):1475-1489.

[10]林超.面向Deep Web的對(duì)象檢索關(guān)鍵技術(shù)研究[D].蘇州大學(xué)碩士論文, 2008.

[11]Jayant Madhavan, David Ko, Lucja Kot, et al.Google's Deep-Web Crawl[C].Proceedings of 34th International Conference on Very Large Data Bases.Auckland, New Zealand, Springer Berlin,2008:1241-1252.

[12]Rodrigo B.Almeida, Barzan Mozafari, Junghoo Cho.On the Evolution of Wikipedia[C].Proceedings of the International Conference on Weblogs and Social Media 2007.Colorado, U.S.A, AAAI Press, March 2007.

[13]Ka Cheung Sia, Junghoo Cho, and Hyun-Kyu Cho.Efficient Monitoring Algorithm for Fast News Alerts[J].IEEE Transactions on Knowledge and Data Engineering,2007,19(7) :950-961.

[14]Olston C., Pandey S..Recrawl Scheduling Based on Information Longevity[C]Proceedings of the 17th International World Wide Web Conference, Beijing, China, ACM Press ,2008:437-446.

[15]Croonenborghs T, Ramon J, Blockeel H, Bruynooghe M.Online Learning and Exploiting Relational Models in Reinforcement Learning[C].Proceedings of 20th International Joint Conference on Artifical Intelligence, Hyderabad, India, AAAI Press, 2007: 726-731.