摘 要： 受到學(xué)習(xí)模型爬蟲的啟發(fā)，主題爬蟲結(jié)合網(wǎng)頁內(nèi)容和鏈接信息來估計網(wǎng)頁對給定主題的相關(guān)性，得到兩個新型的爬蟲變種。新型爬蟲強調(diào)的不僅是有學(xué)習(xí)相關(guān)網(wǎng)頁內(nèi)容的能力，而且有引向相關(guān)網(wǎng)頁的能力，并且在查找特定主題方面的能力有質(zhì)的提高。
關(guān)鍵詞： 主題爬蟲；學(xué)習(xí)型爬蟲；學(xué)習(xí)型主題爬蟲
隨著因特網(wǎng)技術(shù)的發(fā)展，傳統(tǒng)的通用搜索爬蟲正面臨著巨大的挑戰(zhàn)，已經(jīng)不能滿足人們對個性化信息檢索服務(wù)日益增長的需要。專業(yè)搜索引擎搜索的內(nèi)容只限于特定主題或?qū)ｉT領(lǐng)域，因而在搜索過程中無須對整個Web進行遍歷，只需選擇與主題頁面相關(guān)的頁面進行訪問。
主題爬蟲的搜索策略常見的有5種：(1)基于內(nèi)容評價的搜索策略。這類網(wǎng)絡(luò)蜘蛛在距離相關(guān)頁面集較近的地方搜索時表現(xiàn)出良好的性能。但由于頁面中的文本信息缺乏“全局性”，很難反映Web的整體情況，普遍存在“近視”的缺點。(2)基于鏈接結(jié)構(gòu)評價的搜索策略。這種策略利用頁面之間的引用關(guān)系確定鏈接的重要性。這類搜索策略優(yōu)點是考慮了鏈接的結(jié)構(gòu)特征，缺點是忽略了頁面與主題的相關(guān)性，在某些情況下會出現(xiàn)搜索偏離主題的“主題漂移”問題。此外，其在搜索過程中需要重復(fù)計算PageRank值或Authority及Hub權(quán)重，計算復(fù)雜度隨訪問的頁面和鏈接數(shù)量的增長呈指數(shù)級增長。(3)基于未來回報價值評價的搜索策略。這種策略本質(zhì)上是通過訓(xùn)練發(fā)掘出鏈接文本中“隱含”的結(jié)構(gòu)信息，這些結(jié)構(gòu)信息反映了距離搜索目標(biāo)的遠近，因而在搜索遠期回報方面具有一定優(yōu)勢。然而，這類搜索策略也存在一些不足：一是預(yù)測未來回報能力有限；二是這種“離線”的訓(xùn)練方式需要選擇典型站點或種子集，加重了用戶的負擔(dān)。(4)基于“綜合價值”評價的搜索策略。采用單一的評價方法不能有效預(yù)測鏈接的真實價值。這類搜索可以有效提高搜索效率。(5)基于動態(tài)價值評價的搜索策略。根據(jù)環(huán)境的變化動態(tài)調(diào)整價值評價機制，表現(xiàn)出極大的靈活性。
根據(jù)搜索策略的不同可以把主題爬蟲歸為下面幾類：
(1)傳統(tǒng)主題爬蟲[1]將描述主題的用戶查詢語句作為其輸入，這是一些種子網(wǎng)頁URL集，并且它會把查找導(dǎo)向感興趣的網(wǎng)頁。這種爬蟲的文本相似度是用信息相似度模型來計算的，這些模型有布爾型模型和向量空間模型(VSM)[2]。
(2)語義型爬蟲[3]是傳統(tǒng)主題爬蟲的變種。根據(jù)語義相似度標(biāo)準(zhǔn)，把下載權(quán)重分配給頁面，這樣就可以計算出頁面內(nèi)容和主題的相關(guān)度：如果頁面和主題都有概念上(沒必要是詞語上的)相似的短語，那頁面和主題具有相關(guān)性。短語之間的概念相似度是使用本體論[4]來定義的。
(3)學(xué)習(xí)型爬蟲[5]采用訓(xùn)練過程來給網(wǎng)頁指派訪問權(quán)重和引導(dǎo)抓取過程。這類爬蟲的特點是爬蟲學(xué)習(xí)了網(wǎng)頁相關(guān)方式或者通過網(wǎng)頁鏈接來到達相關(guān)頁面的路徑。
將學(xué)習(xí)型爬蟲的思想和傳統(tǒng)主題爬蟲的思想進行合理結(jié)合，這樣改造出來的新型爬蟲就同時具有學(xué)習(xí)型爬蟲和傳統(tǒng)主題爬蟲的優(yōu)點。受到HMM爬蟲的啟發(fā)，學(xué)習(xí)型爬蟲結(jié)合采用網(wǎng)頁內(nèi)容和鏈接信息來估計網(wǎng)頁對給定主題的相關(guān)性，這樣就可以得到新型的爬蟲變種。
1 爬蟲設(shè)計與實現(xiàn)
爬蟲的設(shè)計與實現(xiàn)：(1)輸入。爬蟲的輸入包括一定數(shù)量的初始種子URL和主題描述詞。主題描述詞可以是關(guān)鍵詞的列表。(2)下載網(wǎng)頁。抽取網(wǎng)頁中的活躍鏈接，并將其置于隊列中。主題爬蟲的隊列排序和傳統(tǒng)爬蟲不一樣，需要根據(jù)一定的標(biāo)準(zhǔn)重新排序。(3)處理網(wǎng)頁內(nèi)容。對網(wǎng)頁進行分詞處理，分解成詞語向量，采用向量空間模型(VSM)來計算文本相似度。(4)權(quán)重分配。從網(wǎng)頁中抽取到的活躍鏈接放在一個權(quán)重隊列中，權(quán)重隊列中的權(quán)重分配是由爬蟲的類型和用戶的喜好決定的。(5)重復(fù)步驟(1)~(4)。選擇URL進行進一步的爬行，重復(fù)步驟(1)~(4)直到滿足一些停止爬行的條件，或者系統(tǒng)資源耗盡。
HMM爬蟲[6]的工作是建立網(wǎng)頁內(nèi)容與導(dǎo)向相關(guān)頁面路徑之間的關(guān)系。首先用戶瀏覽一個特定的主題頁面，并且對網(wǎng)頁進行標(biāo)記相關(guān)或者不相關(guān)，保存這些頁面以建立頁面訓(xùn)練種子集。相關(guān)頁面組成簇(D0)。不相關(guān)的頁面采用K-Means[7](K由用戶定義)分簇，它們形成簇D1~Dk。HMM模型建立的分簇基礎(chǔ)是：每個頁面有兩個狀態(tài)特征：(1)顯狀態(tài)。根據(jù)網(wǎng)頁的內(nèi)容來確定頁面屬于哪個簇；(2)隱狀態(tài)。頁面和目標(biāo)頁面的距離。假定頁面屬于這個簇，那這個簇的權(quán)重是它能導(dǎo)向目標(biāo)頁面的概率。
圖1中展現(xiàn)了HMM爬蟲訓(xùn)練集。L0表示目標(biāo)或0級網(wǎng)頁，L1是1級頁面(與目標(biāo)頁面相距1個鏈接)，L2是2級頁面(與目標(biāo)頁面相距2個鏈接)，L3是與目標(biāo)頁面相距3個或更多鏈接。D0、D1和D2標(biāo)簽分別對應(yīng)簇0、1、2。有相同簇的頁面可能屬于不同頁面級，在同一頁面級的頁面可能屬于不同的簇。
HMM爬蟲用到的參數(shù)和記號：網(wǎng)頁的等級或隱狀態(tài)特征Li(i是等級)，顯狀態(tài)用它們歸屬的簇Dj來表示。頁面集隱狀態(tài)和顯狀態(tài)可以用HMM模型來建模。
在下一個步驟處于狀態(tài)L0的概率是HMM爬蟲分配給網(wǎng)頁的權(quán)重。如果兩個簇產(chǎn)生相同的概率(例如它們的概率差值低于預(yù)定義的閾值ε)，那么更高的權(quán)重分配給那些具有可以在兩步內(nèi)(同樣用式(1)和(2)計算)導(dǎo)向目標(biāo)頁面概率更高的簇。在導(dǎo)向它們的路徑中，與相同簇次序相關(guān)聯(lián)的頁面分配相同的權(quán)重。改進后的爬蟲，頁面權(quán)重分?jǐn)?shù)規(guī)定為用HMM爬蟲和計算的權(quán)重及代表頁面的由短語向量表示相關(guān)的分類(質(zhì)心)向量的相似度的平均數(shù)。新型的HMM爬蟲變種只采用頁面內(nèi)容，或同時采用頁面內(nèi)容和鏈接文本。
2 實驗結(jié)果
2.1 實驗設(shè)置
所有的爬蟲都用C++實現(xiàn)。要下載的頁面必須是text/html格式，其內(nèi)容大小不超過300 KB。由于性能的因素，鏈接超時和下載時間同樣也要考慮。所有已實現(xiàn)的爬蟲都有這些限制。抓取過程一直重復(fù)，當(dāng)抽取到預(yù)定頁面數(shù)量(1 000)時，則結(jié)束。實現(xiàn)且評估前面提到的所有爬蟲，讓它們抓取的主題相同。
爬蟲的性能，由下載到的頁面中和主題相關(guān)的頁面比例決定(如相似度大于預(yù)定的閾值的頁面，本文中閾值取0.75)。這項措施稱為“收獲率”。收獲率可以用來調(diào)整測量爬蟲下載和主題高度相關(guān)頁面的能力。
初始的種子頁面由人工完成。把相關(guān)的頁面組成主題的種子頁面，每個主題的種子頁面集大小為100。對于每個主題，把爬蟲抓取到的結(jié)果和種子頁面作比較，因為對爬蟲返回的每個頁面，采用VSM方法計算它們的文檔相似度，如果它們的相似度值的最大值比用戶定義的閾值要大，那么這個頁面就標(biāo)記為正結(jié)果。爬蟲的正結(jié)果越多，這個爬蟲就越成功，即爬蟲抓取到和主題相似的結(jié)果的概率就更高。爬蟲的性能是所有主題的正結(jié)果數(shù)的平均數(shù)。
2.2 爬蟲評估
本文對以下三種爬蟲進行了評估：(1)原始的HMM爬蟲；(2)HMM爬蟲采用頁面內(nèi)容相似度，相似度具有相關(guān)頁面簇質(zhì)心；(3)HMM采用頁面內(nèi)容和鏈接文本相似度，相似度具有相關(guān)頁面簇質(zhì)心。
三種爬蟲的結(jié)果比較如圖3所示。
從圖3可以看到，改進后爬蟲的所有實現(xiàn)勝過傳統(tǒng)的HMM爬蟲，當(dāng)允許它們根據(jù)頁面的內(nèi)容分配給頁面不同的優(yōu)先權(quán)時，這些頁面在導(dǎo)向它們的路徑中有相同的簇次序(即使在一個頁面中的鏈接，在使用鏈接文本的時候)。表1是三種爬蟲的平均運行時間和頁面相關(guān)率統(tǒng)計表。
從表1可以看到，傳統(tǒng)的爬蟲運行時間是最短的，但它抓取到的網(wǎng)頁頁面相關(guān)率只有4.11%。兩種改進后的爬蟲——HMM爬蟲(2)和HMM爬蟲(3)，其運行的時間相對較長，但其頁面相關(guān)率均達到13%以上，與傳統(tǒng)爬蟲相比，頁面相關(guān)率提高了9%以上。
本文實現(xiàn)了兩個主題爬蟲變種，并且根據(jù)收獲率標(biāo)準(zhǔn)評價了三種主題爬蟲的性能。尤其要強調(diào)的是HMM學(xué)習(xí)型爬蟲，不僅學(xué)習(xí)目標(biāo)頁面的內(nèi)容，而且還學(xué)習(xí)了導(dǎo)向目標(biāo)頁面的路徑。從本質(zhì)上說，網(wǎng)絡(luò)蜘蛛的搜索問題是一個“多目標(biāo)”規(guī)劃問題。在合理的時間限度內(nèi)，以較少的網(wǎng)絡(luò)資源、存儲資源和計算資源的消耗獲得更多的主題相關(guān)頁面是主題爬蟲追求的最終目標(biāo)。隨著人們對“個性化”信息服務(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]. Journal of Nantong University(Natural Science 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.