鮮學(xué)豐，崔志明，趙朋朋，方立剛，楊元峰，顧才東

?

基于屬性值序列圖模型的deep Web新數(shù)據(jù)發(fā)現(xiàn)策略

鮮學(xué)豐1,2,3，崔志明1,2，趙朋朋2，方立剛1,3，楊元峰1,3，顧才東1,3

（1. 江蘇省現(xiàn)代企業(yè)信息化應(yīng)用支撐軟件工程技術(shù)研發(fā)中心，江蘇蘇州215104； 2. 蘇州大學(xué)智能信息處理及應(yīng)用研究所，江蘇蘇州215006；3. 蘇州市職業(yè)大學(xué)計算機工程學(xué)院，江蘇蘇州 215104）

針對數(shù)據(jù)源新產(chǎn)生數(shù)據(jù)記錄的增量爬取問題，提出了一種deep Web新數(shù)據(jù)發(fā)現(xiàn)策略，該策略采用一種新的屬性值序列圖模型表示deep Web數(shù)據(jù)源，將新數(shù)據(jù)發(fā)現(xiàn)問題轉(zhuǎn)化為屬性值序列圖的遍歷問題，該模型僅與數(shù)據(jù)相關(guān)，與現(xiàn)有查詢關(guān)聯(lián)圖模型相比，具有更強的適應(yīng)性和確定性，可適用于僅僅包含簡單查詢接口的deep Web數(shù)據(jù)源。在此模型的基礎(chǔ)上，發(fā)現(xiàn)增長節(jié)點并預(yù)測其新數(shù)據(jù)發(fā)現(xiàn)能力；利用互信息計算節(jié)點之間的依賴關(guān)系，查詢選擇時盡可能地降低查詢依賴帶來的負(fù)面影響。該策略提高了新數(shù)據(jù)爬取的效率，實驗結(jié)果表明，在相同資源約束前提下，該策略能使本地數(shù)據(jù)和遠程數(shù)據(jù)保持最大化同步。

deep Web；新數(shù)據(jù)發(fā)現(xiàn)；數(shù)據(jù)獲取

1 引言

目前，主流搜索引擎還只能搜索Internet表面可索引的信息，在Internet深處還隱含著大量通過主流搜索引擎無法涉及的海量信息，這些信息稱之為深層網(wǎng)頁(deep Web，又稱為invisible Web 或hidden Web)。根據(jù)Bright Planet研究表明，deep Web信息量非常龐大，是可索引Web信息的500倍，并且這些deep Web內(nèi)容95%都是可以通過Internet無需付費注冊就可以公開訪問的。deep Web的信息一般存儲在服務(wù)端Web數(shù)據(jù)庫中，與靜態(tài)頁面相比通常信息量更大、主題更專一、信息質(zhì)量和結(jié)構(gòu)更好。為了方便用戶快捷高效地使用deep Web信息，國內(nèi)外學(xué)者對deep Web數(shù)據(jù)集成進行了廣泛的研究。目前，deep Web信息集成主要有2種實現(xiàn)方案。一種方案是基于元搜索的方法，針對某個領(lǐng)域提供統(tǒng)一的查詢接口，將用戶查詢經(jīng)過語義映射轉(zhuǎn)發(fā)到各個deep Web數(shù)據(jù)源上，返回的結(jié)果經(jīng)過抽取、語義標(biāo)注、去重合并呈現(xiàn)給用戶。該方案不需維護本地數(shù)據(jù)庫，但存在如下不足：用戶的查詢響應(yīng)慢，響應(yīng)時間不可控，由遠程數(shù)據(jù)源的服務(wù)質(zhì)量決定；建立和維護統(tǒng)一查詢接口模式與各個數(shù)據(jù)源接口模式的語義映射代價高。另一種方案是deep Web數(shù)據(jù)本地化集成方案[1~4]，該方案將deep Web數(shù)據(jù)庫中內(nèi)容爬取出來，經(jīng)過數(shù)據(jù)抽取、語義標(biāo)注、實體識別和去重等處理后，使其以結(jié)構(gòu)化的形式存儲于本地數(shù)據(jù)庫，它能在最短時間內(nèi)響應(yīng)用戶的查詢要求。Madhavan等[1]提出了一種新的基于DataSpace的數(shù)據(jù)集成框架PayGo，該集成框架具有Pay-As-You-Go和演化特性，具有構(gòu)建成本低、領(lǐng)域獨立、演化等特點。目前，第2種方案正受到越來越多國內(nèi)外研究學(xué)者的關(guān)注，將成為deep Web數(shù)據(jù)集成研究的主流。該方案中的關(guān)鍵問題是如何讓本地數(shù)據(jù)和遠程數(shù)據(jù)源中數(shù)據(jù)保持同步。本文將致力于該關(guān)鍵問題的研究，在相同更新資源條件下，使本地數(shù)據(jù)和遠程數(shù)據(jù)保持最大化同步。

由于deep Web是自治的、獨立更新的，其數(shù)據(jù)經(jīng)常處于頻繁更新的狀態(tài)，而用戶總是希望能夠得到當(dāng)前Web數(shù)據(jù)庫中最新的內(nèi)容。因此需要定期地更新本地數(shù)據(jù)拷貝，以保持和遠程數(shù)據(jù)源同步。由于不同的deep Web數(shù)據(jù)源或同一個deep Web數(shù)據(jù)源中的數(shù)據(jù)記錄變化頻率是不一樣的，按統(tǒng)一頻率更新本地存儲的所有數(shù)據(jù)，這是非常耗費資源的(包括帶寬、遠程數(shù)據(jù)源服務(wù)器資源等)。deep Web處于快速動態(tài)更新的狀態(tài)，使增量維護變得更加復(fù)雜，因此亟需提出新的方法來自動增量更新本地deep Web數(shù)據(jù)，從而在相同資源約束前提下，提高本地數(shù)據(jù)的時新性和新數(shù)據(jù)的發(fā)現(xiàn)效率。deep Web數(shù)據(jù)增量爬取主要包含2部分內(nèi)容：系統(tǒng)已集成的本地數(shù)據(jù)（消失和改變的記錄）的增量更新和新數(shù)據(jù)發(fā)現(xiàn)。目前，新數(shù)據(jù)的增量發(fā)現(xiàn)問題還有待進一步研究，因此本文將針對該問題開展研究，在相同資源約束前提下，獲得盡可能多的新數(shù)據(jù)，使本地數(shù)據(jù)和遠程數(shù)據(jù)保持最大化同步。

2 相關(guān)研究

互聯(lián)網(wǎng)中信息量的快速增長使增量信息爬取技術(shù)成為網(wǎng)上信息獲取的一種有效手段，針對淺層網(wǎng)頁(surface Web)的網(wǎng)頁變化和增量爬取技術(shù)已得到廣泛的關(guān)注和研究[5~7]。然而surface Web和deep Web存在較大的差異，數(shù)據(jù)增量爬取的最大區(qū)別為：surface Web頁面有固定的URL，更新一個本地網(wǎng)頁只需根據(jù)這個URL重新訪問。然而deep Web數(shù)據(jù)記錄無固定的URL，更新無法根據(jù)固定的URL來訪問。對于一個deep Web數(shù)據(jù)記錄，只能通過在deep Web數(shù)據(jù)源的查詢接口上提交與該數(shù)據(jù)記錄相關(guān)的查詢，才能更新該數(shù)據(jù)記錄。因此，不能直接應(yīng)用surface Web的增量爬取技術(shù)來實現(xiàn)deep Web數(shù)據(jù)增量爬取，不得不研究新的方法解決deep Web數(shù)據(jù)增量爬取問題。

目前，國內(nèi)外學(xué)者對deep Web數(shù)據(jù)增量爬取也開展了一些探索性研究，文獻[8]提出一種基于查詢關(guān)聯(lián)圖模型的增量數(shù)據(jù)爬取方法，該方法首先建立數(shù)據(jù)源的查詢關(guān)聯(lián)圖模型，從而將增量爬取任務(wù)轉(zhuǎn)化為圖遍歷過程，然后通過分析deep Web數(shù)據(jù)源的歷史版本選擇查詢來增量爬取新記錄。該圖模型的復(fù)雜性由數(shù)據(jù)源的數(shù)據(jù)記錄數(shù)和查詢接口查詢能力決定。文獻[9]同樣基于查詢關(guān)聯(lián)圖模型，但與文獻[8]的查詢選擇依據(jù)不同，文獻[9]通過分析deep Web數(shù)據(jù)源的樣本選擇查詢爬取新記錄。該圖模型與deep Web數(shù)據(jù)源提供的查詢接口能力密切相關(guān)，對于2個具有相同內(nèi)容deep Web數(shù)據(jù)源，如果它們的查詢接口在查詢能力上不同，那么所產(chǎn)生的查詢關(guān)聯(lián)圖模型也不相同。因此，這種圖模型不能獨立表示deep Web數(shù)據(jù)源的內(nèi)容，具有一定的不確定性；同時該圖模型不適用于僅僅包含簡單查詢接口的deep Web數(shù)據(jù)源。文獻[10]把deep Web數(shù)據(jù)爬取表示為集合覆蓋問題，通過機器學(xué)習(xí)方法獲得增量回報模型，然后根據(jù)增量回報模型自動選擇查詢爬取增量記錄。還有一些針對直接集成deep Web網(wǎng)頁集成系統(tǒng)的增量爬取的研究[11~13]，文獻[11]提出一種基于URL分類的deep Web增量爬蟲，該爬蟲根據(jù)deep Web網(wǎng)頁的內(nèi)容將其分為列表頁面和葉子頁面，所有URL也被分為列表URL和葉子URL，該爬蟲根據(jù)列表頁面的更新頻率和葉子頁面的變化頻率爬取最新的deep Web頁面。這類研究的deep Web集成方式與本文不同，它屬于deep Web數(shù)據(jù)集成研究的另一個分支。雖然國內(nèi)外學(xué)者已對deep Web數(shù)據(jù)增量爬取問題進行了一定的研究，但這些研究的新數(shù)據(jù)發(fā)現(xiàn)效率還有待進一步提高。deep Web新數(shù)據(jù)發(fā)現(xiàn)問題研究目前仍處于探索階段，其中，許多問題仍需進一步深入研究。

本文提出了一種基于屬性值序列圖模型的deep Web新數(shù)據(jù)發(fā)現(xiàn)策略，該策略首先將deep Web數(shù)據(jù)源的本地數(shù)據(jù)表示為數(shù)據(jù)記錄屬性值序列圖，然后根據(jù)歷史數(shù)據(jù)產(chǎn)生增長節(jié)點，并設(shè)計了增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力計算方法，最后基于增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)效率進行選擇查詢節(jié)點以爬取新數(shù)據(jù)記錄。實驗結(jié)果表明基于屬性值序列圖模型的deep Web新數(shù)據(jù)發(fā)現(xiàn)策略在相同資源約束前提下，提高了新數(shù)據(jù)的發(fā)現(xiàn)效率，使本地數(shù)據(jù)和遠程數(shù)據(jù)保持最大化同步。

3 屬性值序列圖模型

3.1 屬性值序列圖模型定義

定義1 deep Web數(shù)據(jù)源的屬性值序列圖模型。結(jié)構(gòu)化的deep Web數(shù)據(jù)源（WDB）可看作一張關(guān)系數(shù)據(jù)表DB，DB包含的數(shù)據(jù)記錄為{1,2,…,r}，每條記錄包含個屬性{1,2,…,a}，WDB中所有不相同的屬性值組成的集合為。在Deep Web數(shù)據(jù)增量爬取中，對于一個給定WDB，它的屬性值序列圖模型可定義為一種帶權(quán)的有向連通圖，表示為（，，，），其中是節(jié)點的集合，每一個節(jié)點v∈都與WDB中的屬性值av∈一一對應(yīng)。(v)表示節(jié)點v∈的入度，(v)表示節(jié)點v∈的出度。每個節(jié)點附帶一個權(quán)值表示該節(jié)點對應(yīng)屬性值在WDB的數(shù)據(jù)記錄集合出現(xiàn)的次數(shù)，如果不考慮同一個屬性值在一個數(shù)據(jù)記錄中出現(xiàn)多次的情況，則節(jié)點v∈的權(quán)值(v)為在WDB中出現(xiàn)屬性值av∈的數(shù)據(jù)記錄數(shù)。、分別為出現(xiàn)在單條數(shù)據(jù)記錄中的起點屬性值和終點屬性值的集合，為有向邊的集合，中的元素表示數(shù)據(jù)記錄中屬性值的接續(xù)關(guān)系，一個有向邊(v,v)∈當(dāng)且僅當(dāng)av和av接續(xù)出現(xiàn)在一個數(shù)據(jù)記錄r∈中（如圖1所示）。每條邊也附帶一個權(quán)值表示該邊所關(guān)聯(lián)的節(jié)點間的關(guān)聯(lián)度，邊(v,v)∈的權(quán)值(v,v)為包含有向邊(v,v)∈的數(shù)據(jù)記錄數(shù)。

屬性值序列圖模型具有如下特點。

2) 對于屬性值序列圖任意一個節(jié)點，有()(v)≥1。

3) 每條數(shù)據(jù)記錄在屬性值序列圖中被表示為一個有序閉環(huán)。

4) 對于屬性值序列圖中的任意一個節(jié)點v，根據(jù)、、數(shù)據(jù)記錄的長度以及與v相關(guān)聯(lián)的有向邊，可以確定屬性值序列圖中包含節(jié)點v的所有數(shù)據(jù)記錄。

5) 邊(v,v)∈和(v,v)∈屬于不同的邊，(v,v)∈≠(v,v)∈。

3.2 圖模型的構(gòu)建

對一個給定的結(jié)構(gòu)化的deep Web數(shù)據(jù)源，假設(shè)在前期的數(shù)據(jù)爬取中已獲得了該WDB的全部數(shù)據(jù)記錄，獲得的數(shù)據(jù)記錄集為{1,2,…,r}。首先基于中一條數(shù)據(jù)記錄生成初始屬性值序列圖（如圖1所示），然后依次從中提取各數(shù)據(jù)記錄，不斷向中的添加節(jié)點和邊，同時也更新節(jié)點和邊的權(quán)值，直到中所有數(shù)據(jù)記錄都已添加到，最終得到WDB的屬性值序列圖。屬性值序列圖構(gòu)建示意如圖1和圖2所示。

圖1(a)為一個數(shù)據(jù)記錄r，包含4個屬性值。圖1(b)為圖1(a)數(shù)據(jù)記錄對應(yīng)的屬性值序列圖，1為起始節(jié)點1為終止節(jié)點。有向邊(v,v)∈當(dāng)且僅當(dāng)av和av接續(xù)出現(xiàn)于一個數(shù)據(jù)記錄r∈中，數(shù)據(jù)記錄r在屬性值序列圖中被表示為一個有序閉環(huán)。在圖1(b)中所有節(jié)點和邊的權(quán)重都為1。

圖2顯示了一個結(jié)構(gòu)化deep Web數(shù)據(jù)源（假定WDB包含4條記錄，每條記錄包含4個屬性值）和它所對應(yīng)的屬性值序列圖。圖2(b)中節(jié)點1的權(quán)重=3，節(jié)點2、2、1的權(quán)重=2，其他所有節(jié)點的權(quán)重=1；圖2（b）中邊(1、1)∈和(2,2)∈的權(quán)重=2，其他邊的權(quán)重都=1。屬性值序列圖的節(jié)點和邊的權(quán)重記錄了它們在已構(gòu)建的所有記錄中的統(tǒng)計信息，這些信息將便于deep Web數(shù)據(jù)的增量爬取。

對于一個給定的deep Web數(shù)據(jù)源，在第一次數(shù)據(jù)爬取結(jié)束后，通過上述圖模型的構(gòu)建方法可以得到該WDB的屬性值序列圖。隨著時間的推移deep Web數(shù)據(jù)源會產(chǎn)生大量的新數(shù)據(jù)記錄，需要進行增量爬取。因此，本文以屬性值序列圖模型為基礎(chǔ)，研究新的方法來自動增量爬取新數(shù)據(jù)（新數(shù)據(jù)發(fā)現(xiàn)），以盡可能小的代價增量爬取deep Web數(shù)據(jù)源中新產(chǎn)生的數(shù)據(jù)記錄。從而在相同資源約束前提下，使本地數(shù)據(jù)與遠程數(shù)據(jù)保持最大化同步。

4 deep Web新數(shù)據(jù)發(fā)現(xiàn)策略

4.1 deep Web新數(shù)據(jù)發(fā)現(xiàn)的總體思路

事物發(fā)展的趨勢可以分為3種：遞增、遞減和平穩(wěn)。趨勢的原因各式各樣，比如我國的人均收入、銀行的存款額每年隨著時間而增長，而我國貧困人口的數(shù)據(jù)趨勢逐年遞減，某地區(qū)的平均溫度以及平均降水量是基本平穩(wěn)的。值得注意的是，幾乎所有的事物在不同的發(fā)展階段都要經(jīng)過不同的趨勢，一般來說初期具有向上增長的趨勢，經(jīng)過一段時間的成長達到成熟期，成熟期呈現(xiàn)平穩(wěn)的趨勢，到了末期則有向下減少的趨勢。因此，可以通過分析事物過去的發(fā)展情況，來預(yù)測將來的發(fā)展趨勢。假定deep Web數(shù)據(jù)源中包含某個關(guān)鍵詞的數(shù)據(jù)記錄數(shù)的變化趨勢已符合事物發(fā)展的一般規(guī)律，基于這個假定本文提出一種deep Web新數(shù)據(jù)發(fā)現(xiàn)策略，該策略的基本思路為通過分析deep Web數(shù)據(jù)源在最近個歷史版本對應(yīng)的屬性值序列圖，估計當(dāng)前屬性值序列圖(t?1)中哪些節(jié)點（查詢關(guān)鍵詞）為增長節(jié)點，增長節(jié)點為目前在WDB中與該節(jié)點相匹配的數(shù)據(jù)記錄數(shù)處于遞增階段的節(jié)點，換句話說，WDB在時刻t?1到時刻t期間產(chǎn)生的新數(shù)據(jù)記錄較大可能包含的節(jié)點。然后，對增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力進行評估，最后選擇Top個具有最高新數(shù)據(jù)發(fā)現(xiàn)效率的增長節(jié)點作為查詢節(jié)點，通過提交查詢節(jié)點對應(yīng)的關(guān)鍵詞爬取新數(shù)據(jù)記錄。下面介紹基于屬性值序列圖模型的deep Web新數(shù)據(jù)發(fā)現(xiàn)策略。假定從本地數(shù)據(jù)庫獲得deep Web數(shù)據(jù)源的個歷史版本，deep Web新數(shù)據(jù)發(fā)現(xiàn)問題能被描述為：給定的(0),(1), …,(t1)，如何盡可能多地爬取在△=t?t?1時間區(qū)間內(nèi)產(chǎn)生的新數(shù)據(jù)記錄。新數(shù)據(jù)發(fā)現(xiàn)算法的具體描述如下。

算法1 基于屬性值序列圖模型的deep Web新數(shù)據(jù)發(fā)現(xiàn)算法

輸入：(t?L),(t?(L?1)), …,(t?1)//deep Web數(shù)據(jù)源最近個歷史版本

輸出：;//為爬取的新數(shù)據(jù)記錄的集合

Algorithm((t?L),(t?(L?1)),…,(t?1))

1) begin

2) 構(gòu)建(t?L),(t?(L?1)),…,(t1)對應(yīng)的屬性值序列圖(t)，(t?(L?1))，…，(t?1)

3)=((t?L),(t?(L?1)),…,(t?1)) //增長節(jié)點選擇

4)=() //增長節(jié)點新數(shù)據(jù)發(fā)現(xiàn)能力估計

5) whiledo //停止條件

6)q=() //查詢節(jié)點選擇

7)(,q)=(q,) //在上執(zhí)行查詢q

8)=((,q)) //抽取執(zhí)行查詢q獲得的數(shù)據(jù)記錄

9)=(t?1) //查詢q爬取的新記錄

11)()()(q,)

12) end while

13) return

end

算法1為deep Web新數(shù)據(jù)發(fā)現(xiàn)算法，算法首先構(gòu)建deep Web數(shù)據(jù)源最近個歷史版本的屬性值序列（2)行），然后根據(jù)這個歷史版本的信息從(t?1)中選擇增長節(jié)點并估計增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力（3)~4)行），最后根據(jù)增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)效率選擇查詢節(jié)點，并提交查詢節(jié)點對應(yīng)的關(guān)鍵詞爬取新數(shù)據(jù)記錄（3)~5)行）。一次查詢的新數(shù)據(jù)爬取流程為：首先采用( )從增長節(jié)點中選擇一個節(jié)點作為查詢節(jié)點，提交該查詢節(jié)點對應(yīng)的關(guān)鍵詞到當(dāng)前的deep Web數(shù)據(jù)源，獲得返回結(jié)果頁面（6)~7)行）。然后從結(jié)果頁面中抽取該次查詢獲得的所有數(shù)據(jù)記錄，并篩選出新的數(shù)據(jù)記錄加入到中（8)~9)行），最后把該次數(shù)據(jù)爬取的代價(q,)計入爬取WDB已耗費的總代價()。算法不斷重復(fù)該新數(shù)據(jù)爬取過程直到滿足停止條件，完成該次新數(shù)據(jù)發(fā)現(xiàn)。

該算法主要由4個主要部分組成：( )、e ( )、( )和( )。

( )：通過分析Deep Web數(shù)據(jù)源的最近個歷史版本的屬性值序列圖，預(yù)測當(dāng)前版本的屬性值圖(t?1)中節(jié)點的變化趨勢并選擇增長節(jié)點，增長節(jié)點為(t?1)中與WDB在時刻t?1到時刻t期間產(chǎn)生的新數(shù)據(jù)記錄具有最大可能性相匹配的節(jié)點。

e( )：估計增長節(jié)點可能產(chǎn)生新記錄的數(shù)量。

( )：從增長節(jié)點集合中選擇最高新數(shù)據(jù)發(fā)現(xiàn)效率的節(jié)點。

( )：從結(jié)果頁面中抽取數(shù)據(jù)記錄。

( )已經(jīng)被廣泛研究，目前提出了許多解決方法，將不再討論數(shù)據(jù)記錄抽取問題。本文主要討論deep Web新數(shù)據(jù)發(fā)現(xiàn)的( )、e ( )和( )這3部分。

新數(shù)據(jù)發(fā)現(xiàn)的停止條件如下。

1) 如果系統(tǒng)分配給WDB的新數(shù)據(jù)爬取資源耗盡，即()≥c，c為分配給WDB的總資源，則結(jié)束WDB的數(shù)據(jù)爬取。

2) 對于數(shù)據(jù)源WDB，如果()最近連續(xù)選擇的個節(jié)點（查詢關(guān)鍵詞）發(fā)現(xiàn)新數(shù)據(jù)記錄的效率低于閾值。

3) 查詢節(jié)點集合為空，沒有可以提交的查詢節(jié)點。

接下來將詳細(xì)介紹增長節(jié)點選擇、增長節(jié)點新數(shù)據(jù)發(fā)現(xiàn)能力估計和查詢節(jié)點選擇這3個關(guān)鍵問題。

4.2 增長節(jié)點選擇

deep Web數(shù)據(jù)源當(dāng)前本地版本(t?1)的屬性值圖為(t?1)，deep Web新數(shù)據(jù)發(fā)現(xiàn)的關(guān)鍵問題為：在時刻t，如何從圖(t?1)中選擇一個節(jié)點，在WDB上提交該節(jié)點對應(yīng)的查詢關(guān)鍵詞可以獲得盡可能多的新記錄。根據(jù)4.1節(jié)敘述的事物發(fā)展的趨勢的一般規(guī)律，(t?1)中的所有節(jié)點根據(jù)目前所處的發(fā)展階段可分為3種類：增長類、衰減類和平穩(wěn)類。對于(t?1)中屬于這3類的節(jié)點分別稱為：增長節(jié)點、衰減節(jié)點和平穩(wěn)節(jié)點。如果圖(t?1)中的一個節(jié)點的出度（入度）在deep Web數(shù)據(jù)源最近的個歷史版本中都非常穩(wěn)定，根據(jù)事物發(fā)展的一般規(guī)律，那么該節(jié)點在(t)中存在大量新記錄與之相匹配的機會將很小，換句話說在時刻t?1到時刻t期間WDB不可能產(chǎn)生大量與該節(jié)點相匹配的數(shù)據(jù)記錄，這類節(jié)點即為“平穩(wěn)節(jié)點”，如果節(jié)點的出度（入度）在deep Web數(shù)據(jù)源最近的個歷史版本中的度逐漸減小或節(jié)點在最近的個歷史版本中，度的平均值與第+1版本相比減小，則稱該類節(jié)點為“衰減節(jié)點”，如果節(jié)點的出度（入度）在deep Web數(shù)據(jù)源最近的個歷史版本中的度逐漸增加，或節(jié)點在最近的個歷史版本中度的平均值大于第+1版本，則稱該類節(jié)點為“增長節(jié)點”，顯然，在時刻t，WDB中與增長節(jié)點相匹配的數(shù)據(jù)記錄數(shù)最有可能增加，即(t?1)中的增長節(jié)點在WDB中更有可能與新產(chǎn)生的數(shù)據(jù)記錄相匹配。本文使用式（1）計算當(dāng)前版本(t?1)中節(jié)點從時刻t?L到時刻t?1區(qū)間的增長度

其中，D?i()為圖(t?i)中節(jié)點的入度（出度），即在(t?i)中與節(jié)點對應(yīng)關(guān)鍵詞相匹配的數(shù)據(jù)記錄數(shù)；表示節(jié)點的增長度的權(quán)重，與當(dāng)前版本越接近的版本之間的增長度越重要；表示(t?i)與(t?(i+1))2個版本之間的增長度；D?i()?D(?i+1)()為在(t?i)中與節(jié)點相匹配的新記錄數(shù)；對于，用一個例子說明，假定(t?i)中2個節(jié)點1和2，D?i(1)=6，D(?i+1)(1)=2，D?i(2)=12，D(?i+1)(2)=4，顯然應(yīng)該優(yōu)先選擇2，因為在deep Web數(shù)據(jù)源上提交2對應(yīng)的關(guān)鍵詞能獲得比提交1對應(yīng)的關(guān)鍵詞更多的新記錄，使(2)(1)，同時避免當(dāng)?(t?i)，D?i()0時，公式除以0的情況。節(jié)點的增長度如果大于增長閾值，則認(rèn)為節(jié)點為增長節(jié)點。增長節(jié)點產(chǎn)生算法的具體描述如下。

算法2 增長節(jié)點產(chǎn)生算法

輸入：(t?L),(t?(L?1)), …,(t?1),WDB的最近個歷史版本的屬性值圖

輸出：//為增長節(jié)點集合

Algorithm((t?L)，(t?(L?1)),…,(t?1))

1) begin

2) for each vertexin(t?1)do

3) Compute()；

4) if() ≥then //為增長節(jié)點的閾值，如果() ≥，則為增長節(jié)點

5)∪添加節(jié)點到增長節(jié)點集合

6) end if

7) end for

8) return

end

在算法2中，首先輸入deep Web數(shù)據(jù)源最近個歷史版本的屬性值序列圖(t?L),(t?(L?1)),…,(t?1)，計算deep Web 數(shù)據(jù)源當(dāng)前版本屬性值序列圖(t?1)中每個節(jié)點的增長度，如果節(jié)點的增長度大于等于增長閾值，則將節(jié)點加入到增長節(jié)點集合中。通過上述算法得到當(dāng)前版本屬性值序列圖(t?1)中與產(chǎn)生新記錄相匹配可能性較大的所有增長節(jié)點。通過增長度計算(t?1)中所有節(jié)點定性分為增長節(jié)點、衰減節(jié)點和穩(wěn)定節(jié)點3類，在下一節(jié)中將預(yù)測增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力，即在(t)中與增長節(jié)點相匹配的新數(shù)據(jù)記錄數(shù)量。

4.3 增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力估計

目前，人們對事物發(fā)展趨勢（如價格、宏觀經(jīng)濟等）的預(yù)測主要采用的預(yù)測模型有灰色系統(tǒng)預(yù)測模型、時間序列預(yù)測模型、回歸預(yù)測模型、神經(jīng)網(wǎng)絡(luò)模型等[14]。由于在實際應(yīng)用中常常存在序列相關(guān)性、異方差性、非線性等問題，不可避免地存在信息丟失。神經(jīng)網(wǎng)絡(luò)預(yù)測模型由大量的處理單元以適當(dāng)?shù)姆绞交ヂ?lián)構(gòu)成，能模擬人的大腦及其活動，具有非線性和自適應(yīng)性的特點。在實際應(yīng)用中神經(jīng)網(wǎng)絡(luò)預(yù)測模型與其他預(yù)測模型相比通常具有較好的擬合效果和精度。同時，神經(jīng)網(wǎng)絡(luò)預(yù)測模型具有如下優(yōu)點：1)神經(jīng)網(wǎng)絡(luò)預(yù)測模型預(yù)測精度較高，并可以實現(xiàn)并行計算；2) 神經(jīng)網(wǎng)絡(luò)預(yù)測模型相當(dāng)于一個黑盒，不要知道輸入和輸出變量之間的映射關(guān)系，只需對給定的訓(xùn)練數(shù)據(jù)進行訓(xùn)練，來自動建立輸入和輸出變量之間的映射關(guān)系，直到實際輸出值與期望值的誤差滿足所需的精度要求；3) 神經(jīng)網(wǎng)絡(luò)預(yù)測模型在建模的過程中只需要選取適當(dāng)?shù)妮斎胱兞亢洼敵鲎兞恳约跋鄳?yīng)的拓?fù)浣Y(jié)構(gòu)就能建立合適的模型，能減少人工干預(yù)，降低人為假設(shè)的可能。

由于deep Web數(shù)據(jù)變化的復(fù)雜性，本文采用BP神經(jīng)網(wǎng)絡(luò)模型來預(yù)測增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力。同時，針對那些結(jié)果頁面包含與查詢關(guān)鍵詞相匹配的數(shù)據(jù)記錄數(shù)的deep Web數(shù)據(jù)源，采用一種更簡潔的方法計算增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力，即增長節(jié)點預(yù)提交方法。接下來將分別介紹這2種增長節(jié)點新數(shù)據(jù)發(fā)現(xiàn)能力計算方法。

4.3.1 基于BP神經(jīng)網(wǎng)絡(luò)的增長節(jié)點新數(shù)據(jù)發(fā)現(xiàn)能力預(yù)測

對于中一個節(jié)點，預(yù)測其在(t)與之相關(guān)聯(lián)的數(shù)據(jù)記錄數(shù)，即在(t)中的度。假定節(jié)點在最近個歷史版本的屬性值圖中度為：{ D?L(), D?(L?1)(),…,D?1()}。使用BP神經(jīng)網(wǎng)絡(luò)預(yù)測D()的步驟如下。

1) 利用歷史數(shù)據(jù)創(chuàng)建訓(xùn)練樣本

用{ D?L(), D?(L?1)(),…,D()}作為建立BP神經(jīng)網(wǎng)絡(luò)預(yù)測模型的訓(xùn)練樣本，其中，將D?L()作為起始，每連續(xù)個度作為一個樣本的輸入向量，接下來的(≥1)個度作為相應(yīng)的期望輸出向量，這樣的輸入向量和期望輸出向量組成一個樣本，然后起始位置向后退(≥1)個，即從D?L+h()作為起始，再用上述方法建立第2個樣本，依次類推，最終創(chuàng)建出所有的訓(xùn)練樣本。

2) BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)確定

本文預(yù)測采用3層網(wǎng)絡(luò)結(jié)構(gòu)：分別為輸入層、隱含層和輸出層。

輸入層：輸入層有個節(jié)點，對應(yīng)訓(xùn)練樣本的輸入向量。

隱含層：采用經(jīng)驗式lb（為隱含節(jié)點數(shù)，為輸入層節(jié)點數(shù)）確定隱含層節(jié)點數(shù)。

輸出層：輸出層有個節(jié)點，對應(yīng)訓(xùn)練樣本的期望輸出向量。本文設(shè)置=1，僅僅預(yù)測D?L+h+1()的值，如果需要一次預(yù)測D?L+h+1()和D?L+h+2()的值，則可以設(shè)置2。

3) 訓(xùn)練相關(guān)參數(shù)選取與新數(shù)據(jù)發(fā)現(xiàn)能力預(yù)測

選取對數(shù)型函數(shù)作為激勵函數(shù)，選取梯度下降BP訓(xùn)練函數(shù)，最大迭代次數(shù)100，精度為0.000 1。由于BP神經(jīng)網(wǎng)絡(luò)選取的型函數(shù)作為激勵函數(shù)，而型激勵函數(shù)的值域為[0,1]，因此需要采用歸一法將樣本的輸入和輸出向量規(guī)范到[0,1]區(qū)間。然后利用處理好的樣本對神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練，得到訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)，再利用訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)進行預(yù)測，得出D?L+h+1()的預(yù)測值。在時刻t，對于IncrementV中的每一個增長節(jié)點，可以通過BP神經(jīng)網(wǎng)絡(luò)得到D()的預(yù)測值，因此，增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力為：D()?D?1()。

使用基于BP神經(jīng)網(wǎng)絡(luò)的增長節(jié)點新數(shù)據(jù)發(fā)現(xiàn)能力預(yù)測方法，需要對每一個增長節(jié)點訓(xùn)練神經(jīng)網(wǎng)絡(luò)，當(dāng)增長節(jié)點數(shù)量較大時，雖然BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練可以離線進行，但仍然將十分耗時。因此，針對那些結(jié)果頁面包含與查詢關(guān)鍵詞相匹配的數(shù)據(jù)記錄數(shù)的deep Web數(shù)據(jù)源，本文采用一種更簡潔的方法計算增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力，即增長節(jié)點預(yù)提交方法。

4.3.2 增長節(jié)點預(yù)提交的方法

對于一個deep Web數(shù)據(jù)源，當(dāng)查詢關(guān)鍵詞提交到WDB，WDB將返回與該查詢關(guān)鍵詞相匹配的數(shù)據(jù)記錄組成的結(jié)果頁面，據(jù)觀察，大多數(shù)結(jié)果頁除了包含與查詢關(guān)鍵詞相關(guān)的數(shù)據(jù)記錄外，還包含WDB中與該查詢關(guān)鍵詞相匹配的數(shù)據(jù)記錄總數(shù)。圖3為在互動出版網(wǎng)（www.china-pub.com）的查詢接口提交查詢關(guān)鍵詞“java”后，互動出版網(wǎng)返回的結(jié)果頁面（互動出版網(wǎng)是一個圖書類電子商務(wù)網(wǎng)站）。如圖3所示，在結(jié)果頁面中除了顯示部分?jǐn)?shù)據(jù)記錄外，還包含在互動出版網(wǎng)中與查詢關(guān)鍵詞“java”匹配的記錄總數(shù)（見粗線方框“使用java搜索，共有3 413種商品”）。通過統(tǒng)計分析發(fā)現(xiàn)，現(xiàn)實世界中大多數(shù)的deep Web數(shù)據(jù)源的結(jié)果頁面中包含與提交到它的查詢關(guān)鍵詞相匹配的數(shù)據(jù)記錄總數(shù)，記為。

為了進行高效的新數(shù)據(jù)發(fā)現(xiàn)，需要獲得在時刻t，(t)中與增長節(jié)點相匹配的數(shù)據(jù)記錄數(shù)，即在(t)中增長節(jié)點的度D()。因此，本文利用deep Web數(shù)據(jù)源的結(jié)果頁面中包含與提交到它的查詢關(guān)鍵詞相匹配的數(shù)據(jù)記錄總數(shù)的特點，在時刻t，對于IncrementV中的每一個增長節(jié)點，進行一次查詢提交，獲得該節(jié)點查詢提交的一個結(jié)果頁面，然后從結(jié)果頁面中抽取(t)中與增長節(jié)點相匹配的數(shù)據(jù)記錄數(shù)，等價于(t)中增長節(jié)點的度D()。因此，在時刻t，增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力為：- D?1()。

與基于BP神經(jīng)網(wǎng)絡(luò)的增長節(jié)點新數(shù)據(jù)發(fā)現(xiàn)能力預(yù)測方法相比較，增長節(jié)點預(yù)提交方法不需要通過歷史數(shù)據(jù)訓(xùn)練預(yù)測模型，只需要對所有增長節(jié)點進行一次查詢提交，爬取一個結(jié)果頁面即可獲得時刻t在WDB中與增長節(jié)點相匹配數(shù)據(jù)記錄的準(zhǔn)確數(shù)量。因此，增長節(jié)點預(yù)提交方法與基于BP神經(jīng)網(wǎng)絡(luò)的增長節(jié)點新數(shù)據(jù)發(fā)現(xiàn)能力預(yù)測方法相比較, 增長節(jié)點預(yù)提交方法使用更加簡單方便，同時代價較低。更重要的是基于預(yù)測的方法存在一定的誤差，而增長節(jié)點預(yù)提交方法則更為準(zhǔn)確。因此，對那些結(jié)果頁面包含與查詢關(guān)鍵詞相匹配的數(shù)據(jù)記錄數(shù)的deep Web數(shù)據(jù)源，本文使用增長節(jié)點預(yù)提交方法獲得增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力，否則，使用基于BP神經(jīng)網(wǎng)絡(luò)的方法預(yù)測增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力。

4.4 查詢節(jié)點選擇

通過預(yù)測或預(yù)提交得到中每個節(jié)點在(t)中可能的入度（出度）后，可以通過D()?D?1()得到每個增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)能力，即時刻t，在(t)上提交節(jié)點能獲得新數(shù)據(jù)記錄數(shù)量。根據(jù)deep Web新數(shù)據(jù)發(fā)現(xiàn)策略的爬取代價，查詢節(jié)點（關(guān)鍵詞）選擇的目標(biāo)為：每次在中選擇具有最高新數(shù)據(jù)發(fā)現(xiàn)效率的節(jié)點，節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)效率為爬取最少的總數(shù)據(jù)記錄，獲得最多的新數(shù)據(jù)記錄，即對于(t?i)中2個節(jié)點1和2，如果1和2爬取相同數(shù)量的新數(shù)據(jù)記錄，1爬取的總數(shù)據(jù)記錄數(shù)小于2，則認(rèn)為1的新數(shù)據(jù)發(fā)現(xiàn)效率高于2。顯然，應(yīng)該優(yōu)先選擇1。節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)效率定義為

其中，D?1()為在時刻t?1圖(t?1)中增長節(jié)點的入度（出度），D()為在時刻t在deep Web數(shù)據(jù)源上提交與增長節(jié)點相對應(yīng)的查詢關(guān)鍵詞所返回的總記錄數(shù)。D()可由4.3節(jié)得到。D()?D?1()為時刻t在(t)上提交節(jié)點能獲得新數(shù)據(jù)記錄數(shù)量。

在理論上，只需按照中每個增長節(jié)點的新數(shù)據(jù)發(fā)現(xiàn)效率從大到小選擇節(jié)點，在deep Web數(shù)據(jù)源上提交與該節(jié)點對應(yīng)的查詢關(guān)鍵詞，爬取新記錄。不斷重復(fù)該過程，直到滿足停止條件。然而，上述新數(shù)據(jù)爬取的查詢選擇方法在進行查詢選擇時沒有考慮選擇提交的下一個查詢節(jié)點（關(guān)鍵詞）與已經(jīng)選擇提交的查詢節(jié)點之間的依賴關(guān)系。根據(jù)文獻[15]，在實際應(yīng)用中，屬性值之間的依賴關(guān)系十分普遍，例如：許多作者通常一起發(fā)表論文，當(dāng)一個作者名字被提交查詢后，其他的作者名字即便是具有較高新數(shù)據(jù)爬取效率，也不是一個好的選擇。提交它們作為查詢不但不能爬取更多的新數(shù)據(jù)，反而需要系統(tǒng)處理大量重復(fù)數(shù)據(jù)。因此，在進行查詢節(jié)點選擇時，必須要考慮查詢節(jié)點與其他已提交查詢節(jié)點之間的依賴關(guān)系，降低查詢依賴帶來的負(fù)面影響。

本文使用Mutual Information計算2個查詢節(jié)點（關(guān)鍵詞）之間的依賴性，2個查詢節(jié)點1和2的依賴度可由它們共同出現(xiàn)在(t?1)中一個有序圈（一條數(shù)據(jù)記錄）中的概率決定。對于IncrementV中的每個節(jié)點v與所有已提交的節(jié)點之間的依賴關(guān)系(v,IncrementV[1,2,…,m])可由式(3)計算得到

(v,IncrementV[1, 2,…,m])

其中，IncrementV為中還沒有被選擇提交的增長節(jié)點集合，IncrementV[1,2,…,m]為所有已提交的個查詢節(jié)點集合，v∈(v,IncrementV[1,2,…,m])，(v|G(t?1))和(v|G(t?1))分別為v和v在（t?1）中出現(xiàn)的概率，(v,v,(t?1))為v和v在(t?1)中同時出現(xiàn)在一個有序圈（一條數(shù)據(jù)記錄）中的概率。IncrementV中所有節(jié)點的依賴度都基于(t?1)計算得到。

本文在進行查詢選擇時需要懲罰那些具有較強依賴關(guān)系的節(jié)點，因此，對于IncrementV中的每個節(jié)點賦予它一個優(yōu)先級分?jǐn)?shù)(,IncrementV[1,2,…,m])，IncrementV中的所有節(jié)點按照(,IncrementV[1,2,…,m])降序排列，deep Web數(shù)據(jù)增量爬蟲每次從IncrementV中選擇(,IncrementV[1,2,…,m])最大的節(jié)點作為查詢節(jié)點。(, IncrementV[1,2,…,m])的計算式為

(,IncrementV[1,2,…,m])

=()(1?(v,IncrementV[1,2,…,m])) (4)

該方法從IncrementV中每次選擇具有最大值的節(jié)點作為查詢節(jié)點提交后，需要重新計算IncrementV中所有節(jié)點的值，以便選擇下一個節(jié)點，這樣計算量將非常大，因此，在具體應(yīng)用中設(shè)置一個重計算節(jié)點值的步長，即提交次查詢節(jié)點后，再重新計算IncrementV中所有節(jié)點的值。該方法在適當(dāng)犧牲系統(tǒng)效率的情況下，大幅降低系統(tǒng)的計算代價。在新數(shù)據(jù)爬取過程中步長的值可以動態(tài)調(diào)整，以提高新數(shù)據(jù)爬取的效率。

5 實驗

為了對本文提出的基于屬性值序列圖模型的deep Web新數(shù)據(jù)發(fā)現(xiàn)策略的性能進行評估，主要從以下3個方面進行實驗測試：1）算法關(guān)鍵參數(shù)（和）分析；2）新數(shù)據(jù)發(fā)現(xiàn)策略的性能分析；3）AVM與HVMIHM算法的同步率比較。本節(jié)首先介紹實驗所使用的數(shù)據(jù)集，然后給出各項實驗以及實驗結(jié)果分析。

5.1 數(shù)據(jù)準(zhǔn)備

為了評估本文提出方法的性能，本文采用專利領(lǐng)域和鞋類電子商務(wù)領(lǐng)域的5個真實deep Web數(shù)據(jù)源的歷史版本數(shù)據(jù)，這些歷史版本數(shù)據(jù)來至搜鞋客（www.soxieke.com）和明智慧——生物醫(yī)藥科技信息服務(wù)平臺（www. Mingzh.com）2個數(shù)據(jù)集成系統(tǒng)。鞋類電子商務(wù)領(lǐng)域選擇的Deep Web數(shù)據(jù)源為：好樂買（www.okbuy.com）、樂淘（www.letao.com）和搜鞋客（系統(tǒng)已集成的鞋類數(shù)據(jù)約95萬余條數(shù)據(jù)）；專利領(lǐng)域選擇的deep Web數(shù)據(jù)源為：中國知識產(chǎn)權(quán)局專利數(shù)據(jù)源的生物醫(yī)藥類別（www.sipo.gov.cn/zljs）和明智慧（系統(tǒng)已集成的七國兩組織生物醫(yī)藥專利數(shù)據(jù)約369萬余條數(shù)據(jù)）。這些數(shù)據(jù)取于系統(tǒng)2013年5月1日往后的系統(tǒng)集成數(shù)據(jù)，對于專利領(lǐng)域，每間隔2個星期選擇一個時間點，獲得連續(xù)20個歷史版本數(shù)據(jù)；由于電子商務(wù)領(lǐng)域的數(shù)據(jù)變化快于專利領(lǐng)域，因此，對于鞋類電子商務(wù)領(lǐng)域，每間隔一個星期選擇一個時間點，獲得連續(xù)20個歷史版本數(shù)據(jù)。下面將基于以上數(shù)據(jù)集進行實驗，以驗證本文提出方法的有效性。

5.2 新數(shù)據(jù)發(fā)現(xiàn)的效率評估指標(biāo)

deep Web新數(shù)據(jù)發(fā)現(xiàn)的主要目標(biāo)為在盡可能小的代價下獲得盡可能多的新數(shù)據(jù)，為了評估新數(shù)據(jù)發(fā)現(xiàn)的效率，2個因素必須被考慮：覆蓋率和爬取代價。

新數(shù)據(jù)發(fā)現(xiàn)策略的覆蓋率為

=(5)

其中，N為增量爬蟲發(fā)現(xiàn)的新數(shù)據(jù)記錄數(shù)，N為時間到時間1期間實際產(chǎn)生的新數(shù)據(jù)記錄數(shù)。

新數(shù)據(jù)發(fā)現(xiàn)策略的爬取代價為

=(6)

其中，N為增量爬蟲發(fā)現(xiàn)的新數(shù)據(jù)記錄數(shù)，N為爬蟲發(fā)現(xiàn)N個新數(shù)據(jù)記錄總共爬取的數(shù)據(jù)記錄數(shù)。

顯然，如果給定一個值，越大，則爬蟲新數(shù)據(jù)發(fā)現(xiàn)的效率越高。

5.3 實驗結(jié)果

然后實驗分析不同值對覆蓋率的影響，如圖4所示，在相同值的情況下，值越小覆蓋率越高，其變化趨勢與值對覆蓋率的影響相似，當(dāng)值到達一個臨界值后繼續(xù)減小值，對覆蓋率的影響變的非常小，因此，對于一個數(shù)據(jù)源值也有一個臨界值。與值對代價影響一致，隨著值的增加，尤其是值大于臨界之后，值的增加會使代價顯著增加。在5個不同的數(shù)據(jù)源上的實驗結(jié)果得到了基本一致的結(jié)論，因此，在后續(xù)的新數(shù)據(jù)發(fā)現(xiàn)算法效率比較時，選擇和的臨界值作為最理想取值。

5.3.2 新數(shù)據(jù)發(fā)現(xiàn)策略的性能分析

1) 新數(shù)據(jù)發(fā)現(xiàn)算法的有效性分析

首先比較本文提出的基于屬性值序列圖模型的deep Web新數(shù)據(jù)發(fā)現(xiàn)策略（AVM）與現(xiàn)有2種deep Web數(shù)據(jù)增量爬取方法HVM(model history version)[8]，IHM(incremental harvest model)[10]的性能并分析其有效性。上述3種方法通過各自策略選擇下一個最可能發(fā)現(xiàn)新數(shù)據(jù)的關(guān)鍵詞，以發(fā)現(xiàn)新數(shù)據(jù)，反復(fù)執(zhí)行該過程，直到滿足停止條件。該實驗的停止條件為實驗deep Web數(shù)據(jù)源的新數(shù)據(jù)覆蓋率達到95%，為了便于比較當(dāng)某一種爬取方法的新數(shù)據(jù)覆蓋率達到停止條件時，同時已結(jié)束其他2種增量爬取方法的爬取。為了避免AVM滿足停止條件而過早停止，保證實驗在相同的停止條件下進行比較，在實驗中值設(shè)置為10，閾值設(shè)置為1%，重計算節(jié)點值的步長值設(shè)置為12。

圖5給出了3種方法在5個實驗數(shù)據(jù)源最近一個歷史版本上的實驗結(jié)果。從圖5可以得出基于屬性值序列圖模型的deep Web新數(shù)據(jù)發(fā)現(xiàn)策略在5個數(shù)據(jù)源上都最先獲得95%左右的新數(shù)據(jù)。在Sipo數(shù)據(jù)源上當(dāng)其Sipo的新覆蓋率達到95%時，HVM達到83%，IHM為85.5%，在其他數(shù)據(jù)源上，基于屬性值序列圖模型的deep Web新數(shù)據(jù)發(fā)現(xiàn)策略已取得了與IHM數(shù)據(jù)源類似的結(jié)果。與HVM和IHM相比AVM的具有更好有效性和效率。

從Sipo數(shù)據(jù)源的實驗中可以看出當(dāng)查詢提交900次左右時，Sipo的覆蓋率已達到90%以上，在這個查詢次數(shù)下取得這樣的新數(shù)據(jù)覆蓋率已經(jīng)是非常理想的結(jié)果，而其他2種算法此時取得覆蓋率與AVM相差甚遠，甚至提交成倍的查詢次數(shù)也很難取得相同的覆蓋率。在其他數(shù)據(jù)源上，AVM算法都在較少的提交次數(shù)下獲得了90%以上的覆蓋率。因此說明本文提出的AVM算法能在較少查詢提交次數(shù)下獲得較高的覆蓋率，具有較強的有效性。

2) 在多個歷史版本上驗證新數(shù)據(jù)發(fā)現(xiàn)策略的效率

在以下2個實驗中根據(jù)5.3.1節(jié)的實驗結(jié)論，設(shè)置新數(shù)據(jù)發(fā)現(xiàn)算法的值為6，值為5%，重計算節(jié)點值的步長值為12。

在上述5個數(shù)據(jù)源上，利用新數(shù)據(jù)發(fā)現(xiàn)效率評估指標(biāo)來評價本文提出的新數(shù)據(jù)發(fā)現(xiàn)策略的性能。該實驗使用(t?6)，(t?5)，(t?4)，(t?3)，(t?2)和(t?1)最近連續(xù)6個歷史版本數(shù)據(jù)作為統(tǒng)計信息來爬取(t)中新產(chǎn)生的數(shù)據(jù)記錄。在時刻7、10和15這3個時間點上進行實驗得到的結(jié)果如表1所示。本文提出的新數(shù)據(jù)發(fā)現(xiàn)策略在新數(shù)據(jù)發(fā)現(xiàn)策略的覆蓋率（NR_Coverage）和新數(shù)據(jù)發(fā)現(xiàn)策略的爬取代價（NR_Cost）2個方面都取得了非常高的效率。在這5個數(shù)據(jù)源上的所有實驗表明，本文提出新數(shù)據(jù)發(fā)現(xiàn)策略的覆蓋率NR_Coverage都超過了87%，最高為92.5%。新數(shù)據(jù)發(fā)現(xiàn)策略的爬取代價NR_Cost最高的僅為39.7%。

表1 新數(shù)據(jù)發(fā)現(xiàn)策略的性能

5.3.3 AVM與HVMIHM算法的同步率比較

在相同增量爬取資源約束下，分別在5個數(shù)據(jù)源上，比較本文提出AVM與現(xiàn)有2種deep Web數(shù)據(jù)增量爬取方法HVM和IHM的數(shù)據(jù)同步率。

定義2 本地數(shù)據(jù)與遠程數(shù)據(jù)的同步率。假定在時刻t，經(jīng)過增量爬取后得到的本地數(shù)據(jù)為(t)，而此時遠程數(shù)據(jù)源中的實際數(shù)據(jù)為(t)。則本地數(shù)據(jù)與遠程數(shù)據(jù)的同步率(t)可定義為

(t)(7)

其中，|(t)為在時刻t，的數(shù)據(jù)記錄總數(shù)；|(t)∩WDB(t)|為在時刻t，本地數(shù)據(jù)與遠程數(shù)據(jù)相同數(shù)據(jù)記錄總數(shù)。

在實驗中，對每個數(shù)據(jù)源設(shè)置增量更新資源為20萬條數(shù)據(jù)記錄，即在時刻t，增量爬蟲從(t)中爬取20萬條數(shù)據(jù)記錄更新(t?1)，增量爬取后得到本地數(shù)據(jù)為WDB(t)。然后比較本地數(shù)據(jù)WDB(t)與遠程數(shù)據(jù)(t)的同步率。在實驗中，從(t)中爬取20萬條數(shù)據(jù)記錄可通過分析WDB的第個歷史版本獲得，并不需要真實的爬取過程。在9時刻獲得的實驗結(jié)果如圖6所示。

從圖6中可以看出，本文提出的AVM方法，在5個數(shù)據(jù)源上都取得了非常高的數(shù)據(jù)同步率，并都優(yōu)于HVM和IHM。在Sipo數(shù)據(jù)源，AVM、HVM和IHM 3種增量爬取方法的同步率比較接近，AVM略優(yōu)于IHM和HVM。但在Letao數(shù)據(jù)源的實驗結(jié)果與在Sipo數(shù)據(jù)源上存在較大的差異，在Letao數(shù)據(jù)源，AVM和IHM明顯優(yōu)于HVM，在相同更新資源的約束下，HVM取得的數(shù)據(jù)同步率最低，僅為75.2%，AVM和IHM 分別為94.4%和82.7%。對于HVM方法，本文在這些數(shù)據(jù)源分別選擇不同的查詢接口進行實驗得到差異較大的實驗結(jié)果，究其原因HVM方法與查詢接口能力密切相關(guān)，不能獨立表示deep Web數(shù)據(jù)源的內(nèi)容，具有一定的不確定性。在Mingzh數(shù)據(jù)源，AVM明顯優(yōu)于HVM和IHM，但是與其他4個數(shù)據(jù)源比較，這3種方法的同步率都較低，究其原因為Mingzh的數(shù)據(jù)量遠遠大于其他數(shù)據(jù)源，在相同的更新資源下，取得的同步率應(yīng)該低于其他數(shù)據(jù)源。從在Mingzh數(shù)據(jù)源上的實驗結(jié)果中可以看出，當(dāng)數(shù)據(jù)量較大時，本文方法的效率優(yōu)勢更加明顯，能較好地適應(yīng)大數(shù)據(jù)量情況下的增量更新。在其他時間點上的實驗與在9時刻的實驗結(jié)果類似，本文將不再這里贅述。綜上所述，本文提出的新數(shù)據(jù)發(fā)現(xiàn)方法都取得了非常高的同步率。

6 結(jié)束語

由于deep Web是自治的、獨立更新的，其數(shù)據(jù)經(jīng)常處于頻繁更新的狀態(tài)（不斷有新數(shù)據(jù)記錄產(chǎn)生），同時也有一些數(shù)據(jù)記錄消失或改變，而用戶總是希望能夠得到當(dāng)前deep Web數(shù)據(jù)源中最新的內(nèi)容。因此需要定期地爬取遠程數(shù)據(jù)源的數(shù)據(jù)，更新本地數(shù)據(jù)拷貝，以保持本地數(shù)據(jù)與遠程數(shù)據(jù)同步。deep Web數(shù)據(jù)增量爬取需要處理新產(chǎn)生的、消失的和改變的3類數(shù)據(jù)記錄。本文以屬性值序列圖模型為基礎(chǔ)，針對新產(chǎn)生記錄的爬取，提出了一種新數(shù)據(jù)發(fā)現(xiàn)策略，實驗表明在相同資源約束前提下，可有效提高本地數(shù)據(jù)的時新性和新數(shù)據(jù)的發(fā)現(xiàn)效率，使本地數(shù)據(jù)和遠程數(shù)據(jù)保持最大化同步。同時本文提出的屬性值序列圖模型僅與數(shù)據(jù)相關(guān)，可適用于僅僅包含簡單查詢接口的deep Web數(shù)據(jù)源，拓展了新數(shù)據(jù)發(fā)現(xiàn)的應(yīng)用范圍。

[1] MADHAVAN J, COHEN S, DONG X L, et al . Web-scale data integration: you can afford to pay as you go[C]//The 3rd International Conference Innovative Data Systems Research. Asilomar, CA, c2007: 342-350.

[2] MADHAVAN J, KO D, KOT L, et al. Google's deep-Web crawl[C]//The 34th International Conference on Very Large Data Bases. Auckland, New Zealand, Springer, c2008: 1241-1252.

[3] PAVAI G, GEETHA T V. A unified architecture for surfacing the con-tents of deep Web databases[C]//International Conference on Advances in Communication. Network, and Computing, Chennai, India, c2013.

[4] ANDREA C, DAVIDE M, RICCARDO T. Keyword search in the deep Web[C]//AMW2015 Alberto Mendelzon International Workshop on Foundations of Data Management .Lima Peru, c2015: 205-208.

[5] EDWARDS J, MCCURLEY K, TOMLIN J. An adaptive model for optimizing performance of an incremental Web crawler[C]//The 10th Conference on World Wide Web. Hong Kong, China, c2001: 106-113.

[6] SINGHAL N, DIXIT A, SHARMA A K. Design of a priority based frequency regulated incremental crawler[J]. International Journal of Computer Applications, 2010, 1 (1): 42-47.

[7] JAGANATHAN P, KARTHIKEYAN T. Highly efficient architecture for scalable focused crawling using incremental parallel Web crawler[J]. Journal of Computer Science, 2015, 11 (1): 120-126.

[8] LIU W, XIAO J G, YANG J W. Incremental structured Web database crawling via history versions[C]//The 11th International Conference on Web Information Systems Engineering. c2010: 524-533.

[9] LIU W, XIAO J G, YANG J W. A sample-guided approach to incremental structured Web database crawling[C]//International Conference on Information and Automation ,Harbin, c2010: 890-895.

[10] HUANG Q Y, LI Q Z, LI H, et al. An approach to incremental deep Web crawling based on incremental harvest model[J]. Procedia Engineering, 2012, (29): 1081-1087.

[11] ZHANG Z X, DONG G Q, PENG Z H, et al. A framework for incremental deep Web crawler based on URL classification[J]. Lecture Notes in Computer Science, 2011, 6988: 302-310.

[12] 張志瀟.面向領(lǐng)域的Deep Web的增量爬取[D].濟南：山東大學(xué),2012.

ZHANG Z X. Domain-specific deep Web incremental crawler[D]. JiNan: Shandong University,2012.

[13] YOGESH K, MANOJ K R, JITENDRA D. Novel approach for data source integration system update strategy in hidden Web[J]. International Journal of Engineering Universe for Scientific Research and Management.2015,2(7):1-5.

[14] 徐國強. 統(tǒng)計預(yù)測和決策[M]. 上海；上海財經(jīng)大學(xué)出版社.2008.

XU G Q. Statistical forecasting and decision-making [M]. Shanghai: Shanghai University of Finance and Economics press, 2003.

[15] WU P, WEN J R, LIU H, et al. Query selection techniques for efficient crawling of structured Web sources[C]//The 22th International Conference on Data Engineering. Atlanta, GA, USA, c2006: 47-56.

Deep Web new data discovery strategy based on the graph model of data attribute value lists

XIAN Xue-feng1,2,3, CUI Zhi-ming1,2, ZHAO Peng-peng2, FANG Li-gang1,3, YANG Yuan-feng1,3, GU Cai-dong1,3

(1. Jiangsu Province Support Software Engineering R&D Center for Modern Information Technology Application in Enterprise, Suzhou 215104,China; 2. Institute of Intelligent Information Processing and Application, Soochow University, Suzhou 215006, China; 3. School of Computer Engineering, Suzhou Vocational University, Suzhou 215104, China)

A novel deep Web data discovery strategy was proposed for new generated data record in resources. In the approach, a new graph model of deep Web data attribute value lists was used to indicate the deep Web data source, an new data crawling task was transformed into a graph traversal process. This model was only related to the data, compared with the existing query-related graph model had better adaptability and certainty, applicable to contain only a simple query interface of deep Web data sources. Based on this model, which could discovery incremental nodes and predict new data mutual information was used to compute the dependencies between nodes. When the query selects, as much as possible to reduce the negative impact brought by the query-dependent. This strategy improves the data crawling efficiency. Experimental results show that this strategy could maximize the synchronization between local and remote data under the same restriction.

deep Web, new data discovery, data acquisition

TP392

A

10.11959/j.issn.1000-436x.2016049

2015-04-20；

2015-10-28

崔志明，CZM@jssvc.edu.cn

國家自然科學(xué)基金資助項目（No.61440053, No.61472268, No.41201338）；江蘇省自然科學(xué)基金資助項目（No.BK2012164）；蘇州市科技計劃基金資助項目（No.SYG201342, No.SYG201343, No.SS201344）

The National Natural Science Foundation of China (No.61440053, No.61472268, No.41201338), The Natural Science Foundation of Jiangsu Province (No.BK2012164), Suzhou Foundation for Development of Science and Technology (No.SYG201342, No.SYG201343, No.SS201344)

鮮學(xué)豐（1980-），男，四川南充人，博士，蘇州市職業(yè)大學(xué)副教授，主要研究方向為Web數(shù)據(jù)管理、數(shù)據(jù)挖掘和智能信息處理。

崔志明（1961-），男，上海人，蘇州大學(xué)教授、博士生導(dǎo)師，主要研究方向為智能信息處理和計算機網(wǎng)絡(luò)。

趙朋朋（1980-），男，江蘇南通人，博士，蘇州大學(xué)副教授，主要研究方向為deep Web和Web數(shù)據(jù)挖掘。

方立剛（1980-），男，安徽黃山人，博士，蘇州市職業(yè)大學(xué)副教授，主要研究方向為計算機網(wǎng)絡(luò)和Web GIS。

楊元峰（1973-），男，江蘇鹽城人，蘇州市職業(yè)大學(xué)副教授，主要研究方向為智能信息處理。

顧才東（1963-），男，寧夏吳忠人，蘇州市職業(yè)大學(xué)教授，主要研究方向為智能信息處理和物聯(lián)網(wǎng)。