鮮學(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é)計(jì)算機(jī)工程學(xué)院，江蘇蘇州 215104）

針對(duì)數(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)圖模型相比，具有更強(qiáng)的適應(yīng)性和確定性，可適用于僅僅包含簡(jiǎn)單查詢接口的deep Web數(shù)據(jù)源。在此模型的基礎(chǔ)上，發(fā)現(xiàn)增長(zhǎng)節(jié)點(diǎn)并預(yù)測(cè)其新數(shù)據(jù)發(fā)現(xiàn)能力；利用互信息計(jì)算節(jié)點(diǎn)之間的依賴關(guān)系，查詢選擇時(shí)盡可能地降低查詢依賴帶來的負(fù)面影響。該策略提高了新數(shù)據(jù)爬取的效率，實(shí)驗(yàn)結(jié)果表明，在相同資源約束前提下，該策略能使本地?cái)?shù)據(jù)和遠(yuǎn)程數(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無需付費(fèi)注冊(cè)就可以公開訪問的。deep Web的信息一般存儲(chǔ)在服務(wù)端Web數(shù)據(jù)庫中，與靜態(tài)頁面相比通常信息量更大、主題更專一、信息質(zhì)量和結(jié)構(gòu)更好。為了方便用戶快捷高效地使用deep Web信息，國(guó)內(nèi)外學(xué)者對(duì)deep Web數(shù)據(jù)集成進(jìn)行了廣泛的研究。目前，deep Web信息集成主要有2種實(shí)現(xiàn)方案。一種方案是基于元搜索的方法，針對(duì)某個(gè)領(lǐng)域提供統(tǒng)一的查詢接口，將用戶查詢經(jīng)過語義映射轉(zhuǎn)發(fā)到各個(gè)deep Web數(shù)據(jù)源上，返回的結(jié)果經(jīng)過抽取、語義標(biāo)注、去重合并呈現(xiàn)給用戶。該方案不需維護(hù)本地?cái)?shù)據(jù)庫，但存在如下不足：用戶的查詢響應(yīng)慢，響應(yīng)時(shí)間不可控，由遠(yuǎn)程數(shù)據(jù)源的服務(wù)質(zhì)量決定；建立和維護(hù)統(tǒng)一查詢接口模式與各個(gè)數(shù)據(jù)源接口模式的語義映射代價(jià)高。另一種方案是deep Web數(shù)據(jù)本地化集成方案[1~4]，該方案將deep Web數(shù)據(jù)庫中內(nèi)容爬取出來，經(jīng)過數(shù)據(jù)抽取、語義標(biāo)注、實(shí)體識(shí)別和去重等處理后，使其以結(jié)構(gòu)化的形式存儲(chǔ)于本地?cái)?shù)據(jù)庫，它能在最短時(shí)間內(nèi)響應(yīng)用戶的查詢要求。Madhavan等[1]提出了一種新的基于DataSpace的數(shù)據(jù)集成框架PayGo，該集成框架具有Pay-As-You-Go和演化特性，具有構(gòu)建成本低、領(lǐng)域獨(dú)立、演化等特點(diǎn)。目前，第2種方案正受到越來越多國(guó)內(nèi)外研究學(xué)者的關(guān)注，將成為deep Web數(shù)據(jù)集成研究的主流。該方案中的關(guān)鍵問題是如何讓本地?cái)?shù)據(jù)和遠(yuǎn)程數(shù)據(jù)源中數(shù)據(jù)保持同步。本文將致力于該關(guān)鍵問題的研究，在相同更新資源條件下，使本地?cái)?shù)據(jù)和遠(yuǎn)程數(shù)據(jù)保持最大化同步。

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

2 相關(guān)研究

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

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

本文提出了一種基于屬性值序列圖模型的deep Web新數(shù)據(jù)發(fā)現(xiàn)策略，該策略首先將deep Web數(shù)據(jù)源的本地?cái)?shù)據(jù)表示為數(shù)據(jù)記錄屬性值序列圖，然后根據(jù)歷史數(shù)據(jù)產(chǎn)生增長(zhǎng)節(jié)點(diǎn)，并設(shè)計(jì)了增長(zhǎng)節(jié)點(diǎn)的新數(shù)據(jù)發(fā)現(xiàn)能力計(jì)算方法，最后基于增長(zhǎng)節(jié)點(diǎn)的新數(shù)據(jù)發(fā)現(xiàn)效率進(jìn)行選擇查詢節(jié)點(diǎn)以爬取新數(shù)據(jù)記錄。實(shí)驗(yàn)結(jié)果表明基于屬性值序列圖模型的deep Web新數(shù)據(jù)發(fā)現(xiàn)策略在相同資源約束前提下，提高了新數(shù)據(jù)的發(fā)現(xiàn)效率，使本地?cái)?shù)據(jù)和遠(yuǎn)程數(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}，每條記錄包含個(gè)屬性{1,2,…,a}，WDB中所有不相同的屬性值組成的集合為。在Deep Web數(shù)據(jù)增量爬取中，對(duì)于一個(gè)給定WDB，它的屬性值序列圖模型可定義為一種帶權(quán)的有向連通圖，表示為（，，，），其中是節(jié)點(diǎn)的集合，每一個(gè)節(jié)點(diǎn)v∈都與WDB中的屬性值av∈一一對(duì)應(yīng)。(v)表示節(jié)點(diǎn)v∈的入度，(v)表示節(jié)點(diǎn)v∈的出度。每個(gè)節(jié)點(diǎn)附帶一個(gè)權(quán)值表示該節(jié)點(diǎn)對(duì)應(yīng)屬性值在WDB的數(shù)據(jù)記錄集合出現(xiàn)的次數(shù)，如果不考慮同一個(gè)屬性值在一個(gè)數(shù)據(jù)記錄中出現(xiàn)多次的情況，則節(jié)點(diǎn)v∈的權(quán)值(v)為在WDB中出現(xiàn)屬性值av∈的數(shù)據(jù)記錄數(shù)。、分別為出現(xiàn)在單條數(shù)據(jù)記錄中的起點(diǎn)屬性值和終點(diǎn)屬性值的集合，為有向邊的集合，中的元素表示數(shù)據(jù)記錄中屬性值的接續(xù)關(guān)系，一個(gè)有向邊(v,v)∈當(dāng)且僅當(dāng)av和av接續(xù)出現(xiàn)在一個(gè)數(shù)據(jù)記錄r∈中（如圖1所示）。每條邊也附帶一個(gè)權(quán)值表示該邊所關(guān)聯(lián)的節(jié)點(diǎn)間的關(guān)聯(lián)度，邊(v,v)∈的權(quán)值(v,v)為包含有向邊(v,v)∈的數(shù)據(jù)記錄數(shù)。

屬性值序列圖模型具有如下特點(diǎn)。

2) 對(duì)于屬性值序列圖任意一個(gè)節(jié)點(diǎn)，有()(v)≥1。

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

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

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

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

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

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

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

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

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

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

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

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

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

1) begin

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

3)=((t?L),(t?(L?1)),…,(t?1)) //增長(zhǎng)節(jié)點(diǎn)選擇

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

5) whiledo //停止條件

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

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

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

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

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

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

( )：從結(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) 對(duì)于數(shù)據(jù)源WDB，如果()最近連續(xù)選擇的個(gè)節(jié)點(diǎn)（查詢關(guān)鍵詞）發(fā)現(xiàn)新數(shù)據(jù)記錄的效率低于閾值。

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

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

4.2 增長(zhǎng)節(jié)點(diǎn)選擇

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

其中，D?i()為圖(t?i)中節(jié)點(diǎn)的入度（出度），即在(t?i)中與節(jié)點(diǎn)對(duì)應(yīng)關(guān)鍵詞相匹配的數(shù)據(jù)記錄數(shù)；表示節(jié)點(diǎn)的增長(zhǎng)度的權(quán)重，與當(dāng)前版本越接近的版本之間的增長(zhǎng)度越重要；表示(t?i)與(t?(i+1))2個(gè)版本之間的增長(zhǎng)度；D?i()?D(?i+1)()為在(t?i)中與節(jié)點(diǎn)相匹配的新記錄數(shù)；對(duì)于，用一個(gè)例子說明，假定(t?i)中2個(gè)節(jié)點(diǎn)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，因?yàn)樵赿eep Web數(shù)據(jù)源上提交2對(duì)應(yīng)的關(guān)鍵詞能獲得比提交1對(duì)應(yīng)的關(guān)鍵詞更多的新記錄，使(2)(1)，同時(shí)避免當(dāng)?(t?i)，D?i()0時(shí)，公式除以0的情況。節(jié)點(diǎn)的增長(zhǎng)度如果大于增長(zhǎng)閾值，則認(rèn)為節(jié)點(diǎn)為增長(zhǎng)節(jié)點(diǎn)。增長(zhǎng)節(jié)點(diǎn)產(chǎn)生算法的具體描述如下。

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

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

輸出：//為增長(zhǎng)節(jié)點(diǎn)集合

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

1) begin

2) for each vertexin(t?1)do

3) Compute()；

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

5)∪添加節(jié)點(diǎn)到增長(zhǎng)節(jié)點(diǎn)集合

6) end if

7) end for

8) return

end

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3.2 增長(zhǎng)節(jié)點(diǎn)預(yù)提交的方法

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

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

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

4.4 查詢節(jié)點(diǎn)選擇

通過預(yù)測(cè)或預(yù)提交得到中每個(gè)節(jié)點(diǎn)在(t)中可能的入度（出度）后，可以通過D()?D?1()得到每個(gè)增長(zhǎng)節(jié)點(diǎn)的新數(shù)據(jù)發(fā)現(xiàn)能力，即時(shí)刻t，在(t)上提交節(jié)點(diǎn)能獲得新數(shù)據(jù)記錄數(shù)量。根據(jù)deep Web新數(shù)據(jù)發(fā)現(xiàn)策略的爬取代價(jià)，查詢節(jié)點(diǎn)（關(guān)鍵詞）選擇的目標(biāo)為：每次在中選擇具有最高新數(shù)據(jù)發(fā)現(xiàn)效率的節(jié)點(diǎn)，節(jié)點(diǎn)的新數(shù)據(jù)發(fā)現(xiàn)效率為爬取最少的總數(shù)據(jù)記錄，獲得最多的新數(shù)據(jù)記錄，即對(duì)于(t?i)中2個(gè)節(jié)點(diǎn)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é)點(diǎn)的新數(shù)據(jù)發(fā)現(xiàn)效率定義為

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

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

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

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

其中，IncrementV為中還沒有被選擇提交的增長(zhǎng)節(jié)點(diǎn)集合，IncrementV[1,2,…,m]為所有已提交的個(gè)查詢節(jié)點(diǎn)集合，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)中同時(shí)出現(xiàn)在一個(gè)有序圈（一條數(shù)據(jù)記錄）中的概率。IncrementV中所有節(jié)點(diǎn)的依賴度都基于(t?1)計(jì)算得到。

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

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

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

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

5 實(shí)驗(yàn)

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

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

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

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

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

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

=(5)

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

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

=(6)

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

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

5.3 實(shí)驗(yàn)結(jié)果

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

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種方法通過各自策略選擇下一個(gè)最可能發(fā)現(xiàn)新數(shù)據(jù)的關(guān)鍵詞，以發(fā)現(xiàn)新數(shù)據(jù)，反復(fù)執(zhí)行該過程，直到滿足停止條件。該實(shí)驗(yàn)的停止條件為實(shí)驗(yàn)deep Web數(shù)據(jù)源的新數(shù)據(jù)覆蓋率達(dá)到95%，為了便于比較當(dāng)某一種爬取方法的新數(shù)據(jù)覆蓋率達(dá)到停止條件時(shí)，同時(shí)已結(jié)束其他2種增量爬取方法的爬取。為了避免AVM滿足停止條件而過早停止，保證實(shí)驗(yàn)在相同的停止條件下進(jìn)行比較，在實(shí)驗(yàn)中值設(shè)置為10，閾值設(shè)置為1%，重計(jì)算節(jié)點(diǎn)值的步長(zhǎng)值設(shè)置為12。

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

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

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

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

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

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

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

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

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

(t)(7)

其中，|(t)為在時(shí)刻t，的數(shù)據(jù)記錄總數(shù)；|(t)∩WDB(t)|為在時(shí)刻t，本地?cái)?shù)據(jù)與遠(yuǎn)程數(shù)據(jù)相同數(shù)據(jù)記錄總數(shù)。

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

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

6 結(jié)束語

由于deep Web是自治的、獨(dú)立更新的，其數(shù)據(jù)經(jīng)常處于頻繁更新的狀態(tài)（不斷有新數(shù)據(jù)記錄產(chǎn)生），同時(shí)也有一些數(shù)據(jù)記錄消失或改變，而用戶總是希望能夠得到當(dāng)前deep Web數(shù)據(jù)源中最新的內(nèi)容。因此需要定期地爬取遠(yuǎn)程數(shù)據(jù)源的數(shù)據(jù)，更新本地?cái)?shù)據(jù)拷貝，以保持本地?cái)?shù)據(jù)與遠(yuǎn)程數(shù)據(jù)同步。deep Web數(shù)據(jù)增量爬取需要處理新產(chǎn)生的、消失的和改變的3類數(shù)據(jù)記錄。本文以屬性值序列圖模型為基礎(chǔ)，針對(duì)新產(chǎn)生記錄的爬取，提出了一種新數(shù)據(jù)發(fā)現(xiàn)策略，實(shí)驗(yàn)表明在相同資源約束前提下，可有效提高本地?cái)?shù)據(jù)的時(shí)新性和新數(shù)據(jù)的發(fā)現(xiàn)效率，使本地?cái)?shù)據(jù)和遠(yuǎn)程數(shù)據(jù)保持最大化同步。同時(shí)本文提出的屬性值序列圖模型僅與數(shù)據(jù)相關(guān)，可適用于僅僅包含簡(jiǎ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].濟(jì)南：山東大學(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] 徐國(guó)強(qiáng). 統(tǒng)計(jì)預(yù)測(cè)和決策[M]. 上海；上海財(cái)經(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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61440053, No.61472268, No.41201338）；江蘇省自然科學(xué)基金資助項(xiàng)目（No.BK2012164）；蘇州市科技計(jì)劃基金資助項(xiàng)目（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é)副教授，主要研究方向?yàn)閃eb數(shù)據(jù)管理、數(shù)據(jù)挖掘和智能信息處理。

崔志明（1961-），男，上海人，蘇州大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)橹悄苄畔⑻幚砗陀?jì)算機(jī)網(wǎng)絡(luò)。

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

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

楊元峰（1973-），男，江蘇鹽城人，蘇州市職業(yè)大學(xué)副教授，主要研究方向?yàn)橹悄苄畔⑻幚怼?/p>

顧才東（1963-），男，寧夏吳忠人，蘇州市職業(yè)大學(xué)教授，主要研究方向?yàn)橹悄苄畔⑻幚砗臀锫?lián)網(wǎng)。