基于最優(yōu)查詢的多領(lǐng)域ｄｅｅｐ Ｗｅｂ爬蟲

摘 要:Deep Web信息通過在網(wǎng)頁搜索接口提交查詢詞獲得。通用搜索引擎使用超鏈接爬取網(wǎng)頁，無法索引deep Web數(shù)據(jù)。為解決此問題，介紹一種基于最優(yōu)查詢的deep Web爬蟲，通過從聚類網(wǎng)頁中生成最優(yōu)查詢，自動提交查詢，最后索引查詢結(jié)果。實(shí)驗(yàn)表明系統(tǒng)能自動、高效地完成多領(lǐng)域deep Web數(shù)據(jù)爬取。

關(guān)鍵詞:deep Web; deep Web爬蟲; 最優(yōu)查詢; 頁面聚類

中圖分類號:TP393文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2009)09-3375-03

doi:10.3969/j.issn.1001-3695.2009.09.049

Multi-domain deep Web crawler based on most efficient queries

FENG Ming-yuan， LIN Huai-zhong

(College of Computer Science Technology， Zhejiang University， Hangzhou 310027， China )

Abstract:Deep Web information can only be obtained through queries submitted to search forms in pages. While traditional hyperlinks based search engines were hard to index the deep Web data. To address this problem， proposed a most efficient queries based on deep Web crawler. It generated the most efficient queries through clustered Web pages， submitted the queries， and indexed the returned results. Experiment shows it can crawl data automatically and efficiently from multi-domain deep Web.

Key words:deep Web; deep Web crawler; most efficient queries; page cluster

0 引言

隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)中出現(xiàn)了越來越多的網(wǎng)絡(luò)數(shù)據(jù)庫。與傳統(tǒng)的非結(jié)構(gòu)化網(wǎng)頁信息相比，結(jié)構(gòu)化的網(wǎng)絡(luò)數(shù)據(jù)庫提供了更高質(zhì)量的數(shù)據(jù)，支持更豐富的網(wǎng)絡(luò)應(yīng)用。通常稱由網(wǎng)絡(luò)數(shù)據(jù)庫提供的信息為deep Web信息，以區(qū)別于那些通過網(wǎng)頁鏈接獲取的靜態(tài)網(wǎng)頁信息，即surface Web信息。

據(jù)文獻(xiàn)[1]顯示，截至2005年，互聯(lián)網(wǎng)上已經(jīng)有超過百萬個(gè)deep Web網(wǎng)站，deep Web信息量是surface Web信息量的500倍[2]，越來越多的研究者將目光投向了這一領(lǐng)域[2，3]。Deep Web數(shù)據(jù)往往隱藏在網(wǎng)頁搜索框之后，這使得基于超鏈接的通用搜索引擎無法索引到其中數(shù)據(jù)，用戶只有向具有查詢表單的網(wǎng)頁提交查詢，才能訪問其中的數(shù)據(jù)[1]。

對于deep Web數(shù)據(jù)的獲取，主要有兩種方式:a)通過deep Web數(shù)據(jù)庫的接口集成，提供統(tǒng)一的查詢接口，把各個(gè)網(wǎng)絡(luò)數(shù)據(jù)庫的返回結(jié)果通過模式變換匯集到全局模式下，典型應(yīng)用如文獻(xiàn)[3];b)數(shù)據(jù)倉庫法，即通過deep Web爬蟲提交查詢，從返回的結(jié)果中提取所需要的數(shù)據(jù)，存儲到統(tǒng)一的存儲中心。這樣的工作模式可以被描述為查詢—獲取—存儲模式，典型應(yīng)用如文獻(xiàn)[4]。

該系統(tǒng)采用提交查詢、提取并存儲信息的方式獲取deep Web數(shù)據(jù)。其主要?jiǎng)?chuàng)新點(diǎn)是通過聚類方式獲取數(shù)據(jù)庫查詢的最優(yōu)查詢詞，以較少次的數(shù)據(jù)庫查詢獲得盡可能高的數(shù)據(jù)覆蓋率。與傳統(tǒng)的deep Web爬蟲相比，它具有適用領(lǐng)域廣、爬取效率高、信息覆蓋率高等優(yōu)勢。

1 系統(tǒng)總體結(jié)構(gòu)

傳統(tǒng)的采用數(shù)據(jù)倉庫方式的數(shù)據(jù)集成系統(tǒng)中，將各數(shù)據(jù)源的所有數(shù)據(jù)集成到數(shù)據(jù)中心，提供盡可能完整的集成。在網(wǎng)絡(luò)環(huán)境下的deep Web數(shù)據(jù)集成出現(xiàn)了一些新情況[5]。由于網(wǎng)絡(luò)數(shù)據(jù)庫規(guī)模龐大，且各數(shù)據(jù)源的差異巨大，筆者認(rèn)為集成更多數(shù)據(jù)源以及更有價(jià)值的數(shù)據(jù)比窮盡單個(gè)數(shù)據(jù)源所有數(shù)據(jù)更有意義。在這樣的思想指導(dǎo)下，通過設(shè)計(jì)最優(yōu)查詢詞，高效地爬取deep Web數(shù)據(jù)庫中的數(shù)據(jù)。系統(tǒng)總體架構(gòu)如圖1所示。

系統(tǒng)主要由三個(gè)功能模塊組成:

a)頁面爬取及預(yù)處理模塊。鏈接容器內(nèi)存放待爬取的鏈接。內(nèi)部鏈接隊(duì)列采取一定的算法進(jìn)行排序[6，7]，爬取最有可能包含搜索表單的網(wǎng)頁。

過濾器濾掉非目標(biāo)網(wǎng)頁。網(wǎng)頁中的表單除了搜索性表單外，還包括用戶登錄表單、郵件列表表單等無用表單。采用的過濾算法主要有兩個(gè):

(a)非搜索性表單的過濾。采用[7~9]中的非搜索性表單過濾算法，通過表單的一些結(jié)構(gòu)特征來進(jìn)行過濾。選取的表單結(jié)構(gòu)特征包括check box個(gè)數(shù)、radio個(gè)數(shù)、file input個(gè)數(shù)、submit標(biāo)簽個(gè)數(shù)、password個(gè)數(shù)、textboxes個(gè)數(shù)、select控件內(nèi)的候選值個(gè)數(shù)，以及表單標(biāo)簽中是否有詞組查找。

(b)網(wǎng)頁深度過濾。網(wǎng)頁深度是指從一個(gè)網(wǎng)站的主頁，到達(dá)網(wǎng)站的某一網(wǎng)頁所需要的最短跳轉(zhuǎn)次數(shù)。根據(jù)文獻(xiàn)[2]中的研究，在隨機(jī)選取的一百萬個(gè)IP地址中，deep Web搜索表單網(wǎng)頁深度都小于5，且94%的小于3，即如圖2(橫軸為網(wǎng)頁深度，縱軸為所占比例)。

據(jù)此設(shè)定同一網(wǎng)站(site)的最大爬取深度為3，提高了蜘蛛的爬取效率。

b)頁面聚類模塊。該模塊主要負(fù)責(zé)對已爬取且經(jīng)過濾的網(wǎng)頁進(jìn)行自動聚類，為最優(yōu)查詢生成作前期準(zhǔn)備。聚類算法保證了系統(tǒng)能在多個(gè)領(lǐng)域進(jìn)行爬取，擺脫傳統(tǒng)的deep Web爬蟲的領(lǐng)域限制。

c)最優(yōu)查詢生產(chǎn)及查詢模塊。通過選取多個(gè)最優(yōu)的關(guān)鍵查詢詞，實(shí)現(xiàn)在有限的查詢代價(jià)下獲得最優(yōu)的deep Web數(shù)據(jù)覆蓋率。

2 最優(yōu)查詢生成

爬蟲必須在網(wǎng)絡(luò)爬取廣度與單站爬取深度之間作出折中選擇。本文的方法首先保證Web搜索的廣度，不局限于某一領(lǐng)域內(nèi)的站點(diǎn)同時(shí)對單個(gè)站點(diǎn)設(shè)計(jì)出最優(yōu)的搜索詞，在有限的查詢提交中，盡可能廣地覆蓋deep Web數(shù)據(jù)。

2.1 頁面聚類

在deep Web環(huán)境下，Web數(shù)據(jù)庫隱藏在網(wǎng)頁搜索接口之后。網(wǎng)頁搜索接口是了解數(shù)據(jù)庫的惟一途徑[10]。首先對搜索框及其所在頁面進(jìn)行基于內(nèi)容的聚類，將網(wǎng)頁劃分為屬于各種不同topic的集合。對于網(wǎng)頁的聚類分析，實(shí)質(zhì)是對后臺deep Web數(shù)據(jù)庫的聚類分析[11]。

1)表單頁面特征空間模型 記搜索框所在頁面為Pg，Pg由二元組表示(Pc，F(xiàn)c)。其中Pc表示HTML頁面的文本內(nèi)容，F(xiàn)c表示搜索表單內(nèi)的文本內(nèi)容。從本質(zhì)上講，HTML文檔類似于傳統(tǒng)的信息檢索領(lǐng)域中的文本文檔，因此，用信息檢索領(lǐng)域常用的SVM[12]模型來進(jìn)行建模。

將Pg劃分為兩個(gè)特征空間，分別為Pc特征空間及Fc特征空間。每個(gè)特征空間由詞集合及相應(yīng)的權(quán)重值組成。Pc與Fc的代碼范圍由圖3所示的Dom樹裁剪而得。

2)構(gòu)建頁面特征向量 首先對搜索框所在頁面的HTML代碼進(jìn)行清洗，去除掉無用的標(biāo)簽、鏈接、圖片等;然后使用在文本處理中常用的TF-IDF方法來為Pc和Fc中的詞匯計(jì)算權(quán)重值。

此外，詞在頁面中的字體、位置也是權(quán)重值計(jì)算考察的因素。例如出現(xiàn)在網(wǎng)頁標(biāo)題(如HTML的title標(biāo)簽)中的詞將會獲得額外的分值。第i個(gè)詞的具體分值計(jì)算為

weighti= Ki ×Tfi ×log(N/ni)(1)

其中:Ki表示該詞的字體、位置因素所帶來的系數(shù)，即如果該詞位于網(wǎng)頁的重要位置(如標(biāo)題)則系數(shù)大，否則系數(shù)值小。具有比較大的權(quán)重系數(shù)的特征如表1所示。

表1 重要頁面特征提取

特征介紹

字體文本字體類型，如黑體、斜體

相對位置文本處于頁面上部或下部

距離文本與控件的頁面距離較近

3)計(jì)算頁面相似度 文檔間的相似度計(jì)算已經(jīng)有了深入的研究，最為常用的包括cosine相似度，即將文檔Di表示成m維向量(wi1，…， wim)，則兩個(gè)文檔Di、Dj間的相似度計(jì)算可以表示為

sim(Di，Dj) = (∑mk=1Wik×Wjk)/(∑mk=1Wik2)(∑mk=1Wjk2)(2)

為綜合Pc和Fc兩個(gè)特征空間， Pg頁面的相似度計(jì)算公式為

sim(Pg1，Pg2)=(C1×cos(Pc1，Pc2)+C2×cos(Fc1，F(xiàn)c2))/(C1+C2)(3)

其中:C1、C2分別表示Pc和Fc相似度對總相似度的貢獻(xiàn)。

4)K-means聚類 使用K-means算法對文檔進(jìn)行聚類。算法描述如下:

算法1 K-means聚類

a)Input:Pg，k

b)centr=Seedsselect(Pg，k)//隨機(jī)選擇種子集

c)repeat

d)clusters=assignPoints(formPgaes，centr)

//將表單頁面添加到最相似的聚類中

e)centr=recomputeCentroids(clusters)

//重新計(jì)算聚類的中心

f)until stop criterion is reached

g)return clusters

算法以所有表單頁面及參數(shù)k作為輸入。k個(gè)簇的種子集初始值隨機(jī)從表單頁面中選取(算法步驟b)。每一個(gè)聚類C有一個(gè)中心向量centr，計(jì)算式為

C = (∑Pc∈CPc/C，∑Fc∈CFc/C)(4)

聚類間距離計(jì)算使用式(3)，C1與C2的取值通過實(shí)驗(yàn)不斷調(diào)整，在實(shí)驗(yàn)中取C1=1.2，C2=1。

計(jì)算k個(gè)初始種子集的中心向量后，剩余表單頁面被添加進(jìn)與它距離最近(相似度最高)的聚類(算法步驟d))。每加入一個(gè)新的表單頁面后，該聚類將重新計(jì)算中心向量(算法步驟e))。這樣的一個(gè)計(jì)算過程將不斷重復(fù)，直到所有的聚類趨于穩(wěn)定，即表單頁面在各個(gè)聚類之間的移動變得很少，如可以設(shè)定只有不到10%的表單頁面有過移動。

表單頁面經(jīng)上述聚類處理后，deep Web數(shù)據(jù)庫被劃分為各個(gè)領(lǐng)域，接下來就可以提取各領(lǐng)域比較典型的查詢詞來進(jìn)行預(yù)測查詢。

2.2 最優(yōu)查詢生成及提交

研究者們對于如何生成合適的查詢詞來查詢deep Web數(shù)據(jù)庫有一定的研究。一些系統(tǒng)[4]配備了一個(gè)與領(lǐng)域相關(guān)的知識庫(task-specific database)，初始庫中手動添加了與領(lǐng)域相關(guān)的知識，如對于軟件領(lǐng)域的垂直搜索，則在公司目錄中加入微軟、Google等詞條，在領(lǐng)域目錄中加入數(shù)據(jù)庫、網(wǎng)絡(luò)等詞條。在爬蟲爬行過程中，可以從表單下拉框、deep Web返回結(jié)果等地方不斷學(xué)習(xí)新的詞匯，豐富知識庫。

筆者分析認(rèn)為，原有的方法具有以下幾個(gè)缺點(diǎn):a)適用領(lǐng)域的限制，原有的方法只適用于小規(guī)模、固定領(lǐng)域爬取;b)語言限制，對于不同的語言，需要建立不同語言的知識庫，工作量巨大。在大規(guī)模網(wǎng)絡(luò)及多領(lǐng)域多語言的環(huán)境條件下，爬蟲必須具有高適應(yīng)性、高效、高自動化及應(yīng)用簡單的特性。

1)最優(yōu)查詢種子集生成 取已聚類的表單頁面集中任一聚類集C為例進(jìn)行說明。首先選取該聚類集中具有最高內(nèi)容相關(guān)度的k個(gè)詞作為查詢種子集，即使用式(1)選取聚類集C中具有最高權(quán)重值的前k個(gè)關(guān)鍵詞。

2)反復(fù)迭代查詢 記初始的k個(gè)查詢詞為Nfirst，以初始查詢詞開始，進(jìn)行多次的反復(fù)迭代。

算法2 最優(yōu)查詢詞迭代查詢

a)Input:one of the clusters C

b)Nfirst=GenerateSeeds(C)//生成種子集

c)begin

While criterion is not reached

d)Pi=querysubmit(P，candidateWordsi)

//生成查詢結(jié)果頁面

e)CandidateWordsi=Generatetopkwords(Pi)

f)CandidateWordsi+1=filter(CandidateWordsi)

//對候選最優(yōu)查詢詞進(jìn)行過濾

g)return all valid result pages

h)end

設(shè)系統(tǒng)目前處于第i輪的迭代，此時(shí)經(jīng)過關(guān)鍵詞提交查詢產(chǎn)生Pi個(gè)結(jié)果頁面，通過式(1)計(jì)算出Pi個(gè)頁面中具有最大權(quán)重值的詞CandidateWordsi;運(yùn)用一定的規(guī)則篩選這些詞，取剩下的最優(yōu)關(guān)鍵詞作為下一次提交查詢的查詢詞。重復(fù)這一計(jì)算過程直到一定的停止條件被滿足。

步驟f)的候選最優(yōu)查詢篩選規(guī)則如下:

a)若某個(gè)詞在第i輪的生成頁面Pi中出現(xiàn)頻率過高(如大于90%)，則這個(gè)詞可能是網(wǎng)頁模板中的詞，應(yīng)以篩除;

b)若某個(gè)詞在第i輪的生成頁面Pi中出現(xiàn)頻率過低(如小于5%)，則這個(gè)詞不可能是領(lǐng)域特征詞，應(yīng)以篩除。

算法可以通過控制初始集Nfirst及每次迭代篩選后的最優(yōu)查詢詞CandidateWordsi的數(shù)量來控制爬取數(shù)據(jù)的規(guī)模。

3 結(jié)果分析

在實(shí)驗(yàn)中，采取隨機(jī)爬取的策略，采用的種子網(wǎng)站分別為搜房網(wǎng)(www.soufun.com)、新浪網(wǎng)(www.sina.com)、和訊網(wǎng)(www.hexun.com)、當(dāng)當(dāng)網(wǎng)(www.dangdang.com)。在種子網(wǎng)站中，實(shí)驗(yàn)中特意選擇不同領(lǐng)域的門戶網(wǎng)站，以測試系統(tǒng)在不同領(lǐng)域的適應(yīng)性。實(shí)驗(yàn)中部分?jǐn)?shù)據(jù)如表2所示。

表2 實(shí)驗(yàn)中部分重要參數(shù)數(shù)據(jù)

重要參數(shù)取值重要參數(shù)取值

含表單的頁面527式(4)的參數(shù)C21.0

含查詢表單的頁面387聚類參數(shù)K9

式(4)的參數(shù)C11.2共生成結(jié)果頁面7 541

本文用提交效率來衡量爬蟲的整體表現(xiàn)。記總提交查詢次數(shù)為Ntotal，返回有效結(jié)果的頁面數(shù)量為Nvalid，則提交效率為Esubmit =Ntotal/Nvalid。任意選取五個(gè)聚類作實(shí)驗(yàn)，測試系統(tǒng)在五個(gè)聚類中的提交效率。

在五個(gè)聚類的實(shí)驗(yàn)中，設(shè)置查詢停止條件為:a)迭代提交次數(shù)超過五次;b)候選查詢詞數(shù)量少于五個(gè);c)只要任意一個(gè)條件滿足，就停止提交查詢。圖4顯示了實(shí)驗(yàn)結(jié)果。圖表對比了每一個(gè)聚類的總的提交次數(shù)及返回有效頁面的次數(shù)。本文所稱的有效頁面排除了返回錯(cuò)誤類型以及沒有結(jié)果的頁面。從實(shí)驗(yàn)結(jié)果可見，本文的平均提交效率能達(dá)到85%以上，最高的可達(dá)90%，且多個(gè)聚類提交效率分布均勻，沒有出現(xiàn)較大的波動，可見系統(tǒng)對于不同的領(lǐng)域具有較強(qiáng)的適應(yīng)性。通過實(shí)驗(yàn)顯示了本文通過聚類提取最優(yōu)查詢詞的方法是非常有效的。

4 結(jié)束語

本文研究了通過設(shè)計(jì)最優(yōu)的查詢詞來獲取deep Web數(shù)據(jù)庫的數(shù)據(jù)。該方法能夠在較少次的查詢提交中獲得較好的deep Web數(shù)據(jù)庫信息覆蓋率。同時(shí)使用基于聚類的最優(yōu)查詢生成算法具有自動化程度高、適用于多個(gè)領(lǐng)域等特點(diǎn)，大大改進(jìn)了傳統(tǒng)的deep Web數(shù)據(jù)集成系統(tǒng)需要人工參與、適用單個(gè)領(lǐng)域等缺點(diǎn)，使得deep Web數(shù)據(jù)集成得以在大規(guī)模的網(wǎng)絡(luò)環(huán)境下進(jìn)行。未來的研究內(nèi)容包括將單個(gè)查詢接口查詢擴(kuò)展到多個(gè)查詢接口的查詢。使用多個(gè)查詢接口可以對查詢條件作更多的限制，能夠更好地對deep Web數(shù)據(jù)庫進(jìn)行有目的的探測。同時(shí)如何選取多個(gè)查詢接口，如何解決多個(gè)查詢接口中的查詢條件相互制約等問題是要解決的難題。

參考文獻(xiàn):

[1]COPE J， CRASWELL N， HAWKING D. Automated discovery of search interfaces on the Web[C]// Proc of the 14th Australasian Database Conference. Adelaide: Australian Computer Society， 2003: 181-189.

[2]CHANG K C C， HE B， LI C， et al. Structured databases on the Web: observations and implications[C]//Proc of 2008 ACM SIGMOD International Conference on Management of Data. 2004:61-70.

[3]CHANG K C C， HE B， ZHANG Z. Toward large-scale integration:building a metaquerier over databases on the Web[C]//Proc of the 2nd Conference on Innovative Data Systems Research. Asilomar:[s.n.]， 2005: 44-55.

[4]RAGHAVAN S， MOLINA H G. Crawling the hidden Web[C]// Proc of the 27th International Conference on Very Large Data Bases. Roma:Morgan Kaufmann， 2001: 129-138.

[5]MADHAVAN J， COHEN S， DONG X， et al. Web-scale data integration:you can afford to pay as you go[C]//Proc of the 3rd Conference on Innovative Data Systems Research. Asilomar:[s.n.]， 2007:342-350.

[6]BARBOSA L， FREIRE J. Combining classifiers to identify online databases[C]//Proc of the 16th International Conference on World Wide Web. Alberta:[s.n.]，2007:431-440.

[7]BARBOSA L， FREIRE J. Searching for hidden-Web databases[C]//Proc of the 8th International Workshop on the Web Databa-ses. Baltimore:[s.n.]，2005: 1-6.

[8]RUSSELL S， NORVIG P. Artificial intelligence: a modern approach[M].北京:人民郵電出版社， 2002.

[9]MITCHELL T. Machine learning [M].New York: McGraw Hill， 1997.

[10]HE B， TAO T， CHANG K C C. Organizing structured Web sources by query schemas: a clustering approach[C] // Proc of ACM CIKM International Conference on Information and Knowledge Management. Washington DC:[s.n.]， 2004: 22-31.

[11]BARBOSA L， FREIRE J， DA SILVA A S. Organizing hidden-Web databases by clustering visible Web documents[C]// Proc of the IEEE 23rd International Conference on Data Engineering. Istanbul:[s.n.]，2007:326-335.

[12]BAEZA-YATES R A， RIBEIRO-NETO B A. Modern information retrieval[M]. New York: ACM Press/Addison-Wesley， 1999.