摘  要： 受到學習模型爬蟲的啟發，主題爬蟲結合網頁內容和鏈接信息來估計網頁對給定主題的相關性，得到兩個新型的爬蟲變種。新型爬蟲強調的不僅是有學習相關網頁內容的能力，而且有引向相關網頁的能力，并且在查找特定主題方面的能力有質的提高。
關鍵詞： 主題爬蟲；學習型爬蟲；學習型主題爬蟲

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

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

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

　從圖3可以看到，改進后爬蟲的所有實現勝過傳統的HMM爬蟲，當允許它們根據頁面的內容分配給頁面不同的優先權時，這些頁面在導向它們的路徑中有相同的簇次序(即使在一個頁面中的鏈接，在使用鏈接文本的時候)。表1是三種爬蟲的平均運行時間和頁面相關率統計表。

　從表1可以看到，傳統的爬蟲運行時間是最短的，但它抓取到的網頁頁面相關率只有4.11%。兩種改進后的爬蟲——HMM爬蟲(2)和HMM爬蟲(3)，其運行的時間相對較長，但其頁面相關率均達到13%以上，與傳統爬蟲相比，頁面相關率提高了9%以上。
　本文實現了兩個主題爬蟲變種，并且根據收獲率標準評價了三種主題爬蟲的性能。尤其要強調的是HMM學習型爬蟲，不僅學習目標頁面的內容，而且還學習了導向目標頁面的路徑。從本質上說，網絡蜘蛛的搜索問題是一個“多目標”規劃問題。在合理的時間限度內，以較少的網絡資源、存儲資源和計算資源的消耗獲得更多的主題相關頁面是主題爬蟲追求的最終目標。隨著人們對“個性化”信息服務需要的日益增長，專業搜索引擎的發展將成為搜索引擎發展的主要趨勢之一。
參考文獻
[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.