基于邏輯強化學習的Deep Web增量信息獲取方法

顧偉，傅德勝，蔡瑋

0 引言

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

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

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

近年來，國內研究機構，如蘇州大學[9]和中國人民大學[10]對Deep Web信息提取進行了深入的研究。然而，國內其他學者對Deep Web增量數(shù)據(jù)提取問題研究較少，在Surface Web增量數(shù)據(jù)提取方面作了一定的研究。

1 Deep Web簡介

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

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

2 基于邏輯強化學習的增量數(shù)據(jù)提取方法

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

2.1 強化學習的簡介

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

2.2 同步頻率確定

泊松過程[13]是一個常用于描寫隨機事件累計發(fā)生次數(shù)的基本數(shù)學模型，表面上看，只要隨機事件在不相交時間區(qū)間是重復獨立發(fā)生，而且在充分小的區(qū)間上最多只發(fā)生一次，它們的累計次數(shù)就是一個泊松過程。在很多應用場合都可以近似地歸結為泊松過程。文中采用泊松過程來描述對象信息的變化情況，使得本地數(shù)據(jù)庫可以更好地與遠程數(shù)據(jù)庫保持同步。

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

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

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

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

為了避免在數(shù)據(jù)獲取過程中搜索樹膨脹，采用將強化學習技術應用到數(shù)據(jù)獲取的可控網絡爬蟲方法中。該方法通過強化學習技術得到一些控制“經驗信息”，根據(jù)這些信息來預測較遠的回報，按照某一主題進行搜索，以使累積返回的回報值最大。

基于邏輯強化學習的爬蟲（LQ-Spider）的訓練抓取過程包括下列步驟。

步驟1.提供待查詢數(shù)據(jù)的主題，分別構建站點初始訓練隊列URL，然后提取隊首隊列URL，分析其頁面結構提取頁面中的鏈接地址 URL，并根據(jù)頁面關鍵信息計算鏈接地址的立即回報，結合經驗得出未來回報值，然后結合Value值詞庫中未來回報來計算該鏈接地址的綜合Q值。

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

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

3 實驗驗證

在這一節(jié)中，通過具體的實驗來評估所提出的方法的有效性和可行性。首先，需對其理論基礎進行分析驗證該新方法的可行性，然后，在此基礎上進一步驗證采用該方法的性能優(yōu)劣。

3.1 驗證變化規(guī)律

研究表明網頁的變化頻率可以用泊松過程來表達。實驗數(shù)據(jù)集采用加利福尼亞大學一科研小組采集的 Web對象信息。該數(shù)據(jù)集包括書籍、汽車、論壇和工作4個領域的對象信息。該數(shù)據(jù)集借助爬蟲程序收集了一年半。收集到的Web對象數(shù)據(jù)集如表1所示：

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

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

表2 平均變化頻率在各時段內的對象個數(shù)

接著，統(tǒng)計不同領域平均變化頻率相同的對象，各時間點t附近的對象變化概率如圖1所示：

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

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

3.2 驗證新方法的性能

目前評價聚焦爬蟲性能指標主要是通過計算抓取的相關頁面和不相關頁面的比率來衡量爬蟲優(yōu)劣。本文采用收獲率方法來進行評估不同爬蟲的性能。其中

實驗通過采用基于邏輯強化學習的Deep Web聚焦爬蟲（LQ-Spider）和常用 Deep Web爬蟲（如 Best-first和Breadth-first）對工作和論壇兩個領域的數(shù)據(jù)源進行抓取分析，來比較不同方法的爬蟲獲取信息的收獲率，實驗結果如圖2所示：

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

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

4 總結

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

[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]鮮學豐, 崔志明, 趙朋朋, 等.基于循環(huán)策略和動態(tài)知識的 Deep Web數(shù)據(jù)獲取方法[J].通信學報,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]劉全, 高陽, 陳蓄道, 等.一種基于啟發(fā)式輪廓表的邏輯強化學習方法[J].計算機研究與發(fā)展, 2008, 45(11):1824-1830.

[5]孟濤, 王繼民, 閆宏飛.網頁變化與增量搜集技術[J].軟件學報, 2006，17(5):1051-1067.

[6]趙朋朋.Deep Web信息集成若干關鍵技術研究[D].蘇州大學博士論文, 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].計算機學報, 2007,30(9):1475-1489.

[10]林超.面向Deep Web的對象檢索關鍵技術研究[D].蘇州大學碩士論文, 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.