摘 要： 受到學(xué)習(xí)模型爬蟲的啟發(fā)，主題爬蟲結(jié)合網(wǎng)頁內(nèi)容和鏈接信息來估計(jì)網(wǎng)頁對(duì)給定主題的相關(guān)性，得到兩個(gè)新型的爬蟲變種。新型爬蟲強(qiáng)調(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)不能滿足人們對(duì)個(gè)性化信息檢索服務(wù)日益增長的需要。專業(yè)搜索引擎搜索的內(nèi)容只限于特定主題或?qū)ｉT領(lǐng)域，因而在搜索過程中無須對(duì)整個(gè)Web進(jìn)行遍歷，只需選擇與主題頁面相關(guān)的頁面進(jìn)行訪問。
主題爬蟲的搜索策略常見的有5種：(1)基于內(nèi)容評(píng)價(jià)的搜索策略。這類網(wǎng)絡(luò)蜘蛛在距離相關(guān)頁面集較近的地方搜索時(shí)表現(xiàn)出良好的性能。但由于頁面中的文本信息缺乏“全局性”，很難反映Web的整體情況，普遍存在“近視”的缺點(diǎn)。(2)基于鏈接結(jié)構(gòu)評(píng)價(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ù)級(jí)增長。(3)基于未來回報(bào)價(jià)值評(píng)價(jià)的搜索策略。這種策略本質(zhì)上是通過訓(xùn)練發(fā)掘出鏈接文本中“隱含”的結(jié)構(gòu)信息，這些結(jié)構(gòu)信息反映了距離搜索目標(biāo)的遠(yuǎn)近，因而在搜索遠(yuǎn)期回報(bào)方面具有一定優(yōu)勢(shì)。然而，這類搜索策略也存在一些不足：一是預(yù)測未來回報(bào)能力有限；二是這種“離線”的訓(xùn)練方式需要選擇典型站點(diǎn)或種子集，加重了用戶的負(fù)擔(dān)。(4)基于“綜合價(jià)值”評(píng)價(jià)的搜索策略。采用單一的評(píng)價(jià)方法不能有效預(yù)測鏈接的真實(shí)價(jià)值。這類搜索可以有效提高搜索效率。(5)基于動(dòng)態(tài)價(jià)值評(píng)價(jià)的搜索策略。根據(jù)環(huán)境的變化動(dòng)態(tài)調(diào)整價(jià)值評(píng)價(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)頁對(duì)給定主題的相關(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)容。對(duì)網(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è)特定的主題頁面，并且對(duì)網(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級(jí)網(wǎng)頁，L1是1級(jí)頁面(與目標(biāo)頁面相距1個(gè)鏈接)，L2是2級(jí)頁面(與目標(biāo)頁面相距2個(gè)鏈接)，L3是與目標(biāo)頁面相距3個(gè)或更多鏈接。D0、D1和D2標(biāo)簽分別對(duì)應(yīng)簇0、1、2。有相同簇的頁面可能屬于不同頁面級(jí)，在同一頁面級(jí)的頁面可能屬于不同的簇。
HMM爬蟲用到的參數(shù)和記號(hào)：網(wǎng)頁的等級(jí)或隱狀態(tài)特征Li(i是等級(jí))，顯狀態(tài)用它們歸屬的簇Dj來表示。頁面集隱狀態(tài)和顯狀態(tài)可以用HMM模型來建模。
在下一個(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 實(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)且評(píng)估前面提到的所有爬蟲，讓它們抓取的主題相同。
爬蟲的性能，由下載到的頁面中和主題相關(guān)的頁面比例決定(如相似度大于預(yù)定的閾值的頁面，本文中閾值取0.75)。這項(xiàng)措施稱為“收獲率”。收獲率可以用來調(diào)整測量爬蟲下載和主題高度相關(guān)頁面的能力。
初始的種子頁面由人工完成。把相關(guān)的頁面組成主題的種子頁面，每個(gè)主題的種子頁面集大小為100。對(duì)于每個(gè)主題，把爬蟲抓取到的結(jié)果和種子頁面作比較，因?yàn)閷?duì)爬蟲返回的每個(gè)頁面，采用VSM方法計(jì)算它們的文檔相似度，如果它們的相似度值的最大值比用戶定義的閾值要大，那么這個(gè)頁面就標(biāo)記為正結(jié)果。爬蟲的正結(jié)果越多，這個(gè)爬蟲就越成功，即爬蟲抓取到和主題相似的結(jié)果的概率就更高。爬蟲的性能是所有主題的正結(jié)果數(shù)的平均數(shù)。
2.2 爬蟲評(píng)估
本文對(duì)以下三種爬蟲進(jìn)行了評(píng)估：(1)原始的HMM爬蟲；(2)HMM爬蟲采用頁面內(nèi)容相似度，相似度具有相關(guān)頁面簇質(zhì)心；(3)HMM采用頁面內(nèi)容和鏈接文本相似度，相似度具有相關(guān)頁面簇質(zhì)心。
三種爬蟲的結(jié)果比較如圖3所示。
從圖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可以看到，傳統(tǒng)的爬蟲運(yùn)行時(shí)間是最短的，但它抓取到的網(wǎng)頁頁面相關(guān)率只有4.11%。兩種改進(jìn)后的爬蟲——HMM爬蟲(2)和HMM爬蟲(3)，其運(yùn)行的時(shí)間相對(duì)較長，但其頁面相關(guān)率均達(dá)到13%以上，與傳統(tǒng)爬蟲相比，頁面相關(guān)率提高了9%以上。
本文實(shí)現(xiàn)了兩個(gè)主題爬蟲變種，并且根據(jù)收獲率標(biāo)準(zhǔn)評(píng)價(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ò)資源、存儲(chǔ)資源和計(jì)算資源的消耗獲得更多的主題相關(guān)頁面是主題爬蟲追求的最終目標(biāo)。隨著人們對(duì)“個(gè)性化”信息服務(wù)需要的日益增長，專業(yè)搜索引擎的發(fā)展將成為搜索引擎發(fā)展的主要趨勢(shì)之一。
參考文獻(xiàn)
[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.