網(wǎng)絡(luò)爬蟲性能研究＊

漆志輝，楊天奇

(暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院 計(jì)算機(jī)系，廣東 廣州 510632)

隨著因特網(wǎng)技術(shù)的發(fā)展，傳統(tǒng)的通用搜索爬蟲正面臨著巨大的挑戰(zhàn)，已經(jīng)不能滿足人們對個(gè)性化信息檢索服務(wù)日益增長的需要。專業(yè)搜索引擎搜索的內(nèi)容只限于特定主題或?qū)ｉT領(lǐng)域，因而在搜索過程中無須對整個(gè)Web進(jìn)行遍歷，只需選擇與主題頁面相關(guān)的頁面進(jìn)行訪問。

主題爬蟲的搜索策略常見的有5種：(1)基于內(nèi)容評價(jià)的搜索策略。這類網(wǎng)絡(luò)蜘蛛在距離相關(guān)頁面集較近的地方搜索時(shí)表現(xiàn)出良好的性能。但由于頁面中的文本信息缺乏“全局性”，很難反映 Web的整體情況，普遍存在“近視”的缺點(diǎn)。(2)基于鏈接結(jié)構(gòu)評價(jià)的搜索策略。這種策略利用頁面之間的引用關(guān)系確定鏈接的重要性。這類搜索策略優(yōu)點(diǎn)是考慮了鏈接的結(jié)構(gòu)特征，缺點(diǎn)是忽略了頁面與主題的相關(guān)性，在某些情況下會(huì)出現(xiàn)搜索偏離主題的“主題漂移”問題。此外，其在搜索過程中需要重復(fù)計(jì)算PageRank值或Authority及Hub權(quán)重，計(jì)算復(fù)雜度隨訪問的頁面和鏈接數(shù)量的增長呈指數(shù)級增長。(3)基于未來回報(bào)價(jià)值評價(jià)的搜索策略。這種策略本質(zhì)上是通過訓(xùn)練發(fā)掘出鏈接文本中“隱含”的結(jié)構(gòu)信息，這些結(jié)構(gòu)信息反映了距離搜索目標(biāo)的遠(yuǎn)近，因而在搜索遠(yuǎn)期回報(bào)方面具有一定優(yōu)勢。然而，這類搜索策略也存在一些不足：一是預(yù)測未來回報(bào)能力有限；二是這種“離線”的訓(xùn)練方式需要選擇典型站點(diǎn)或種子集，加重了用戶的負(fù)擔(dān)。(4)基于“綜合價(jià)值”評價(jià)的搜索策略。采用單一的評價(jià)方法不能有效預(yù)測鏈接的真實(shí)價(jià)值。這類搜索可以有效提高搜索效率。(5)基于動(dòng)態(tài)價(jià)值評價(jià)的搜索策略。根據(jù)環(huán)境的變化動(dòng)態(tài)調(diào)整價(jià)值評價(jià)機(jī)制，表現(xiàn)出極大的靈活性。

根據(jù)搜索策略的不同可以把主題爬蟲歸為下面幾類：

(1)傳統(tǒng)主題爬蟲[1]將描述主題的用戶查詢語句作為其輸入，這是一些種子網(wǎng)頁URL集，并且它會(huì)把查找導(dǎo)向感興趣的網(wǎng)頁。這種爬蟲的文本相似度是用信息相似度模型來計(jì)算的，這些模型有布爾型模型和向量空間模型(VSM)[2]。

(2)語義型爬蟲[3]是傳統(tǒng)主題爬蟲的變種。根據(jù)語義相似度標(biāo)準(zhǔn)，把下載權(quán)重分配給頁面，這樣就可以計(jì)算出頁面內(nèi)容和主題的相關(guān)度：如果頁面和主題都有概念上(沒必要是詞語上的)相似的短語，那頁面和主題具有相關(guān)性。短語之間的概念相似度是使用本體論[4]來定義的。

(3)學(xué)習(xí)型爬蟲[5]采用訓(xùn)練過程來給網(wǎng)頁指派訪問權(quán)重和引導(dǎo)抓取過程。這類爬蟲的特點(diǎn)是爬蟲學(xué)習(xí)了網(wǎng)頁相關(guān)方式或者通過網(wǎng)頁鏈接來到達(dá)相關(guān)頁面的路徑。

將學(xué)習(xí)型爬蟲的思想和傳統(tǒng)主題爬蟲的思想進(jìn)行合理結(jié)合，這樣改造出來的新型爬蟲就同時(shí)具有學(xué)習(xí)型爬蟲和傳統(tǒng)主題爬蟲的優(yōu)點(diǎn)。受到HMM爬蟲的啟發(fā)，學(xué)習(xí)型爬蟲結(jié)合采用網(wǎng)頁內(nèi)容和鏈接信息來估計(jì)網(wǎng)頁對給定主題的相關(guān)性，這樣就可以得到新型的爬蟲變種。

1 爬蟲設(shè)計(jì)與實(shí)現(xiàn)

爬蟲的設(shè)計(jì)與實(shí)現(xiàn)：(1)輸入。爬蟲的輸入包括一定數(shù)量的初始種子URL和主題描述詞。主題描述詞可以是關(guān)鍵詞的列表。(2)下載網(wǎng)頁。抽取網(wǎng)頁中的活躍鏈接，并將其置于隊(duì)列中。主題爬蟲的隊(duì)列排序和傳統(tǒng)爬蟲不一樣，需要根據(jù)一定的標(biāo)準(zhǔn)重新排序。(3)處理網(wǎng)頁內(nèi)容。對網(wǎng)頁進(jìn)行分詞處理，分解成詞語向量，采用向量空間模型(VSM)來計(jì)算文本相似度。(4)權(quán)重分配。從網(wǎng)頁中抽取到的活躍鏈接放在一個(gè)權(quán)重隊(duì)列中，權(quán)重隊(duì)列中的權(quán)重分配是由爬蟲的類型和用戶的喜好決定的。(5)重復(fù)步驟(1)～(4)。選擇 URL進(jìn)行進(jìn)一步的爬行，重復(fù)步驟(1)～(4)直到滿足一些停止爬行的條件，或者系統(tǒng)資源耗盡。

HMM爬蟲[6]的工作是建立網(wǎng)頁內(nèi)容與導(dǎo)向相關(guān)頁面路徑之間的關(guān)系。首先用戶瀏覽一個(gè)特定的主題頁面，并且對網(wǎng)頁進(jìn)行標(biāo)記相關(guān)或者不相關(guān)，保存這些頁面以建立頁面訓(xùn)練種子集。相關(guān)頁面組成簇(D0)。不相關(guān)的頁面采用K-Means[7](K由用戶定義)分簇，它們形成簇D1～Dk。HMM模型建立的分簇基礎(chǔ)是：每個(gè)頁面有兩個(gè)狀態(tài)特征：(1)顯狀態(tài)。根據(jù)網(wǎng)頁的內(nèi)容來確定頁面屬于哪個(gè)簇；(2)隱狀態(tài)。頁面和目標(biāo)頁面的距離。假定頁面屬于這個(gè)簇，那這個(gè)簇的權(quán)重是它能導(dǎo)向目標(biāo)頁面的概率。

圖1中展現(xiàn)了HMM爬蟲訓(xùn)練集。L0表示目標(biāo)或0級網(wǎng)頁，L1是 1級頁面 (與目標(biāo)頁面相距 1個(gè)鏈接)，L2是2級頁面(與目標(biāo)頁面相距2個(gè)鏈接)，L3是與目標(biāo)頁面相距 3個(gè)或更多鏈接。D0、D1和 D2標(biāo)簽分別對應(yīng)簇0、1、2。有相同簇的頁面可能屬于不同頁面級，在同一頁面級的頁面可能屬于不同的簇。

圖1 HMM訓(xùn)練集

HMM爬蟲用到的參數(shù)和記號：網(wǎng)頁的等級或隱狀態(tài)特征Li(i是等級)，顯狀態(tài)用它們歸屬的簇Dj來表示。頁面集隱狀態(tài)和顯狀態(tài)可以用HMM模型來建模。

(1)初始概率矩陣：Ф={P(L0，…，Ls-1)}，其中 s是隱狀態(tài)的數(shù)目，P(Li)表示在時(shí)間 1，處于隱狀態(tài) i的概率。這個(gè)概率的計(jì)算方法是：分配給每個(gè)頁面一個(gè)值，這個(gè)值等于在訓(xùn)練集中有相同隱狀態(tài)的頁面的比例。

(2)過渡概率矩陣：A=[pij]0≤i＜s，0≤ij＜s， 如果在狀態(tài)Li時(shí)間t，pij則表示在狀態(tài) Lj時(shí)間 t+1時(shí)的概率。這個(gè)概率假定和t獨(dú)立，且通過計(jì)算從在訓(xùn)練集中狀態(tài)Li到Lj的過渡矩陣個(gè)數(shù)和通過把來自狀態(tài)Li的全部過渡矩陣歸一化，即可以得到這個(gè)概率。

(3)發(fā)射概率矩陣：B=[bij]0≤i＜s，0≤j＜c， 其中bij代表指定狀態(tài)Li在簇Dj中的概率，c是簇的個(gè)數(shù)。這個(gè)概率的計(jì)算方法是：先計(jì)算在簇中有隱狀態(tài)Li的個(gè)數(shù)，然后把在隱狀態(tài)Li的網(wǎng)頁總數(shù)歸一化。

在基于訓(xùn)練集的抓取開始之前，Ф、A、B已經(jīng)計(jì)算出來了。爬蟲下載頁面后，抽取它們的向量表示(根據(jù)VSM)，并且用K-Nearest Neighbors算法給每個(gè)網(wǎng)頁分簇。頁面的簇確定后，這個(gè)頁面能抓取到目標(biāo)頁面的概率可以用HMM模型參數(shù)來計(jì)算。這個(gè)概率與包含在那個(gè)頁面中的鏈接訪問權(quán)重一致。若要考慮頁面的次序，采用HMM模型來預(yù)測在下一個(gè)時(shí)間步驟里的狀態(tài)。為了計(jì)算預(yù)測值，每個(gè)訪問過的頁面與值 p(Lj，t)，j=0，1，…，s相關(guān)聯(lián)。值 p(Lj，t)是爬蟲在時(shí)間 t時(shí)刻下載具有隱狀態(tài) Lj頁面的概率。 指定父頁面值 p(Lj，t-1)，值 p(Lj，t)采用下面遞歸公式計(jì)算：

其中，pij是在矩陣A中從狀態(tài)Li到Lj的過渡概率，bjct是來自矩陣B中隱狀態(tài)的簇ct的發(fā)射概率。在最后遞歸步驟中，值 p(Lj，0)取自初始化概率矩陣Ф。指定值 p(Lj，t)，即在下一個(gè)時(shí)間步所選頁面將會(huì)處于狀態(tài)Lj的概率的計(jì)算公式：

在下一個(gè)步驟處于狀態(tài)L0的概率是HMM爬蟲分配給網(wǎng)頁的權(quán)重。如果兩個(gè)簇產(chǎn)生相同的概率(例如它們的概率差值低于預(yù)定義的閾值ε)，那么更高的權(quán)重分配給那些具有可以在兩步內(nèi)(同樣用式(1)和(2)計(jì)算)導(dǎo)向目標(biāo)頁面概率更高的簇。在導(dǎo)向它們的路徑中，與相同簇次序相關(guān)聯(lián)的頁面分配相同的權(quán)重。改進(jìn)后的爬蟲，頁面權(quán)重分?jǐn)?shù)規(guī)定為用HMM爬蟲和計(jì)算的權(quán)重及代表頁面的由短語向量表示相關(guān)的分類(質(zhì)心)向量的相似度的平均數(shù)。新型的HMM爬蟲變種只采用頁面內(nèi)容，或同時(shí)采用頁面內(nèi)容和鏈接文本。

圖2 新型爬蟲的操作步驟

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

2.1 實(shí)驗(yàn)設(shè)置

所有的爬蟲都用C++實(shí)現(xiàn)。要下載的頁面必須是text/html格式，其內(nèi)容大小不超過300 KB。由于性能的因素，鏈接超時(shí)和下載時(shí)間同樣也要考慮。所有已實(shí)現(xiàn)的爬蟲都有這些限制。抓取過程一直重復(fù)，當(dāng)抽取到預(yù)定頁面數(shù)量(1 000)時(shí)，則結(jié)束。實(shí)現(xiàn)且評估前面提到的所有爬蟲，讓它們抓取的主題相同。

爬蟲的性能，由下載到的頁面中和主題相關(guān)的頁面比例決定(如相似度大于預(yù)定的閾值的頁面，本文中閾值取0.75)。這項(xiàng)措施稱為“收獲率”。收獲率可以用來調(diào)整測量爬蟲下載和主題高度相關(guān)頁面的能力。

初始的種子頁面由人工完成。把相關(guān)的頁面組成主題的種子頁面，每個(gè)主題的種子頁面集大小為100。對于每個(gè)主題，把爬蟲抓取到的結(jié)果和種子頁面作比較，因?yàn)閷ε老x返回的每個(gè)頁面，采用VSM方法計(jì)算它們的文檔相似度，如果它們的相似度值的最大值比用戶定義的閾值要大，那么這個(gè)頁面就標(biāo)記為正結(jié)果。爬蟲的正結(jié)果越多，這個(gè)爬蟲就越成功，即爬蟲抓取到和主題相似的結(jié)果的概率就更高。爬蟲的性能是所有主題的正結(jié)果數(shù)的平均數(shù)。

2.2 爬蟲評估

本文對以下三種爬蟲進(jìn)行了評估：(1)原始的HMM爬蟲；(2)HMM爬蟲采用頁面內(nèi)容相似度，相似度具有相關(guān)頁面簇質(zhì)心；(3)HMM采用頁面內(nèi)容和鏈接文本相似度，相似度具有相關(guān)頁面簇質(zhì)心。

三種爬蟲的結(jié)果比較如圖3所示。

圖3 三種爬蟲結(jié)果比較

從圖3可以看到，改進(jìn)后爬蟲的所有實(shí)現(xiàn)勝過傳統(tǒng)的HMM爬蟲，當(dāng)允許它們根據(jù)頁面的內(nèi)容分配給頁面不同的優(yōu)先權(quán)時(shí)，這些頁面在導(dǎo)向它們的路徑中有相同的簇次序(即使在一個(gè)頁面中的鏈接，在使用鏈接文本的時(shí)候)。表1是三種爬蟲的平均運(yùn)行時(shí)間和頁面相關(guān)率統(tǒng)計(jì)表。

表1 運(yùn)行時(shí)間和相關(guān)率統(tǒng)計(jì)表

從表1可以看到，傳統(tǒng)的爬蟲運(yùn)行時(shí)間是最短的，但它抓取到的網(wǎng)頁頁面相關(guān)率只有4.11%。兩種改進(jìn)后的爬蟲——HMM爬蟲(2)和HMM爬蟲(3)，其運(yùn)行的時(shí)間相對較長，但其頁面相關(guān)率均達(dá)到13%以上，與傳統(tǒng)爬蟲相比，頁面相關(guān)率提高了9%以上。

本文實(shí)現(xiàn)了兩個(gè)主題爬蟲變種，并且根據(jù)收獲率標(biāo)準(zhǔn)評價(jià)了三種主題爬蟲的性能。尤其要強(qiáng)調(diào)的是HMM學(xué)習(xí)型爬蟲，不僅學(xué)習(xí)目標(biāo)頁面的內(nèi)容，而且還學(xué)習(xí)了導(dǎo)向目標(biāo)頁面的路徑。從本質(zhì)上說，網(wǎng)絡(luò)蜘蛛的搜索問題是一個(gè)“多目標(biāo)”規(guī)劃問題。在合理的時(shí)間限度內(nèi)，以較少的網(wǎng)絡(luò)資源、存儲資源和計(jì)算資源的消耗獲得更多的主題相關(guān)頁面是主題爬蟲追求的最終目標(biāo)。隨著人們對“個(gè)性化”信息服務(wù)需要的日益增長，專業(yè)搜索引擎的發(fā)展將成為搜索引擎發(fā)展的主要趨勢之一。

[1]Zuo Xiaojun，Zhang Kaituo.An improved search algorithm of focused crawler in vertical search engine[C].Asia-Pacific Youth Conference On Communication Technology2010(APYCCT 2010)， 2010： 509-513.

[2]Ju Xiaolin， Chen Jihong， Shao Haoran.Hierarchical Web page classification method based on vector space model[C].JournalofNantong University (NaturalScience Edition)，2010.

[3]Yang Shengyuan.A focused crawler with ontology-supported website models for information agents[C].Advances in Grid and Pervasive Computing， 2010：522-532.

[4]LI Jun， FURUSE K， YAMAGUCHI K.Focused crawling by exploiting anchor text using decision tree[C].Proceedings of the 14th International World Wide Web Conference， 2005：1190-1191.

[5]CHEN Y.A novel hybrid focused crawling algorithm to build domain-specific collections[D].Ph.D.Thesis，Virginia Polytechnic Institute and State University，2007.

[6]STEINBACH M，KARYPIS G，KUMAR V.A comparison of document clustering techniques[C].Sixth ACM SIGKDD，World Text Mining Conference， Boston， MA， 2000.

[7]UDDIN M Z， LEE J J， KIM T S.Independent shape component-based human activity recognition via Hidden Markov Model[J].Applied Intelligence， 2010，33(2)：193-206.