摘  要： 受到學(xué)習(xí)模型爬蟲(chóng)的啟發(fā)，主題爬蟲(chóng)結(jié)合網(wǎng)頁(yè)內(nèi)容和鏈接信息來(lái)估計(jì)網(wǎng)頁(yè)對(duì)給定主題的相關(guān)性，得到兩個(gè)新型的爬蟲(chóng)變種。新型爬蟲(chóng)強(qiáng)調(diào)的不僅是有學(xué)習(xí)相關(guān)網(wǎng)頁(yè)內(nèi)容的能力，而且有引向相關(guān)網(wǎng)頁(yè)的能力，并且在查找特定主題方面的能力有質(zhì)的提高。
關(guān)鍵詞： 主題爬蟲(chóng)；學(xué)習(xí)型爬蟲(chóng)；學(xué)習(xí)型主題爬蟲(chóng)

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

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

2 實(shí)驗(yàn)結(jié)果
2.1 實(shí)驗(yàn)設(shè)置
　所有的爬蟲(chóng)都用C++實(shí)現(xiàn)。要下載的頁(yè)面必須是text/html格式，其內(nèi)容大小不超過(guò)300 KB。由于性能的因素，鏈接超時(shí)和下載時(shí)間同樣也要考慮。所有已實(shí)現(xiàn)的爬蟲(chóng)都有這些限制。抓取過(guò)程一直重復(fù)，當(dāng)抽取到預(yù)定頁(yè)面數(shù)量(1 000)時(shí)，則結(jié)束。實(shí)現(xiàn)且評(píng)估前面提到的所有爬蟲(chóng)，讓它們抓取的主題相同。
　爬蟲(chóng)的性能，由下載到的頁(yè)面中和主題相關(guān)的頁(yè)面比例決定(如相似度大于預(yù)定的閾值的頁(yè)面，本文中閾值取0.75)。這項(xiàng)措施稱為“收獲率”。收獲率可以用來(lái)調(diào)整測(cè)量爬蟲(chóng)下載和主題高度相關(guān)頁(yè)面的能力。
　初始的種子頁(yè)面由人工完成。把相關(guān)的頁(yè)面組成主題的種子頁(yè)面，每個(gè)主題的種子頁(yè)面集大小為100。對(duì)于每個(gè)主題，把爬蟲(chóng)抓取到的結(jié)果和種子頁(yè)面作比較，因?yàn)閷?duì)爬蟲(chóng)返回的每個(gè)頁(yè)面，采用VSM方法計(jì)算它們的文檔相似度，如果它們的相似度值的最大值比用戶定義的閾值要大，那么這個(gè)頁(yè)面就標(biāo)記為正結(jié)果。爬蟲(chóng)的正結(jié)果越多，這個(gè)爬蟲(chóng)就越成功，即爬蟲(chóng)抓取到和主題相似的結(jié)果的概率就更高。爬蟲(chóng)的性能是所有主題的正結(jié)果數(shù)的平均數(shù)。
2.2 爬蟲(chóng)評(píng)估
　本文對(duì)以下三種爬蟲(chóng)進(jìn)行了評(píng)估：(1)原始的HMM爬蟲(chóng)；(2)HMM爬蟲(chóng)采用頁(yè)面內(nèi)容相似度，相似度具有相關(guān)頁(yè)面簇質(zhì)心；(3)HMM采用頁(yè)面內(nèi)容和鏈接文本相似度，相似度具有相關(guān)頁(yè)面簇質(zhì)心。
三種爬蟲(chóng)的結(jié)果比較如圖3所示。

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

　從表1可以看到，傳統(tǒng)的爬蟲(chóng)運(yùn)行時(shí)間是最短的，但它抓取到的網(wǎng)頁(yè)頁(yè)面相關(guān)率只有4.11%。兩種改進(jìn)后的爬蟲(chóng)——HMM爬蟲(chóng)(2)和HMM爬蟲(chóng)(3)，其運(yùn)行的時(shí)間相對(duì)較長(zhǎng)，但其頁(yè)面相關(guān)率均達(dá)到13%以上，與傳統(tǒng)爬蟲(chóng)相比，頁(yè)面相關(guān)率提高了9%以上。
　本文實(shí)現(xiàn)了兩個(gè)主題爬蟲(chóng)變種，并且根據(jù)收獲率標(biāo)準(zhǔn)評(píng)價(jià)了三種主題爬蟲(chóng)的性能。尤其要強(qiáng)調(diào)的是HMM學(xué)習(xí)型爬蟲(chóng)，不僅學(xué)習(xí)目標(biāo)頁(yè)面的內(nèi)容，而且還學(xué)習(xí)了導(dǎo)向目標(biāo)頁(yè)面的路徑。從本質(zhì)上說(shuō)，網(wǎng)絡(luò)蜘蛛的搜索問(wèn)題是一個(gè)“多目標(biāo)”規(guī)劃問(wèn)題。在合理的時(shí)間限度內(nèi)，以較少的網(wǎng)絡(luò)資源、存儲(chǔ)資源和計(jì)算資源的消耗獲得更多的主題相關(guān)頁(yè)面是主題爬蟲(chóng)追求的最終目標(biāo)。隨著人們對(duì)“個(gè)性化”信息服務(wù)需要的日益增長(zhǎng)，專業(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.