面向垂直搜索引擎的主題爬行技術研究.pdf

1、主題爬行是獲取World Wide Web中特定領域(主題)的網頁的關鍵技術。隨著Web的快速增長，以及網絡帶寬和各種資源的有限性，從中獲取全面、準確和高質量的信息變的越發(fā)困難。傳統(tǒng)(通用)搜索引擎技術呈現(xiàn)出了嚴重的局限性。(1)對某一查詢返回的結果太多且相關性、質量不高。(2)不能滿足不同背景、不同目的和不同時期的用戶的需求。(3)在索引的全面性、更新的及時性上存在著很大的不足。垂直搜索引擎(Vertical Search Engin

2、e)被作為解決通用搜索引擎局限性的一種潛在方案，有著智能化、個性化、領域化的特點，從而成為當前學術界和產業(yè)界研究的熱點。它利用主題爬行(Focused Crawling or Topical Crawling)技術來搜集面向領域(主題)的Web網頁，并提供面向主題的檢索服務。無疑，主題爬行技術作為垂直搜索引擎的基礎與核心，它的性能對垂直搜索引擎的性能至關重要。此外，主題爬行技術還可用于Web的實時檢索、個性化檢索、數(shù)字圖書館等領域。因此

3、，對主題爬行技術的研究具有重要的學術意義和廣闊的應用前景。 主題爬行基于這樣一個重要的假設：與同一主題相關的網頁趨向于互相鏈接，被稱為Web上的主題局部性。主題爬蟲每次從待爬行URLs隊列中選擇最有希望的鏈接進行爬行，其目標是保持在主題相關的網頁的周圍，而不偏離主題。因此，主題爬行在很大程度上能節(jié)省硬件和網絡資源，提高檢索結果的查準率和質量，保證爬行的時新性。但由于Web是一個高度開放、異構、分布式的信息空間，網頁雜亂地散布在全

4、球各個站點上，而且每天以極快的速度更新。相對于巨大、無序的Web信息空間，與某個主題相關的網頁是非常有限的，僅僅是整個信息空間的一小部分。而一個理想的主題爬蟲需要最大限度的爬行與預定主題最相關的網頁，并最小限度的爬行不相關的網頁。因此，主題爬行又是一個極富挑戰(zhàn)性的研究課題。 主題爬行的關鍵技術有：主題(用戶需求)描述、面向主題爬行的網頁分塊、待爬行URLs優(yōu)先級計算、主題爬行算法。研究主題爬行技術的目標是提供建立垂直搜索引擎的一

5、般技術和通用算法，通過提高網頁搜集的效率和質量來提高垂直搜索引擎的性能，降低垂直搜索引擎的構造和運行代價。本文以“山東省科技攻關計劃項目—垂直檢索系統(tǒng)的研究與開發(fā)”為依托，針對上述關鍵技術展開研究，主要貢獻和創(chuàng)新點包括如下幾點： (1)提出了一種基于分類法的上下文主題描述(CTD-T，Contextual　Topic Description based on Taxonomy)方法。 CTD-T方法基于ODP(Open

6、Directory Project)來表示主題(用戶需求)。對于ODP中的任一主題結點，給出其“上下文主題關鍵詞集合(CTKW，Contextual Topic Key Words)”和“主題描述(TD，Topic Description)”的定義及表示方法。針對直接從ODP中獲取CTKW會引入很多噪音結點的問題，提出了一種基于逆路徑頻率(IPF，Inverse Path Frequency)對CTKW進行去噪的方法。另外，在對CTKW

7、進行向量表示時，提出了一種基于主題結點在ODP中的相對層次位置來計算其權重的方法。利用CTKW來計算已知信息(網頁，錨文本等)與給定主題及其上下文主題的相關度，用來在線指導主題爬蟲的爬行。利用TD來計算已爬行網頁與給定主題的相關度，用來離線評價主題爬蟲的性能。 (2)提出了一種面向主題爬行的在線網頁分塊(OPS4FC，Online Page Segmentation for Focused Crawling)方法。 指出

8、一個網頁中影響主題爬行算法性能的塊主要有兩種：文本塊和鏈接塊。鏈接塊可以進一步被細分為相關鏈接塊，導航鏈接塊和噪音鏈接塊。OPS4FC的主要目標是識別出網頁中的主題文本和相關鏈接塊。首先，將一個已爬行的網頁解析成DOM(DocumentObjectModel)樹。其次，提出一種基于多特征的概率統(tǒng)計方法來識別出該網頁中的所有文本塊和鏈接塊。然后，根據(jù)文本塊之間的語義相關性關系來識別出整個網頁的主題文本。最后，根據(jù)鏈接塊中所有鏈接的錨文本集

9、合與主題文本的語義相關性關系識別出該網頁所有的相關鏈接塊。實驗從Web信息檢索和主題爬行兩個角度證明了OPS4FC方法具有很好的通用性。適用于對海量的，不同版面格式的網頁的處理，能夠有效的提取網頁的主題文本內容和相關鏈接塊，有效的去除網頁中的噪音文本和噪音鏈接，從而能顯著的提高Web檢索和主題爬蟲的性能。 (3)提出一種多粒度的TCURLs優(yōu)先級計算(PUMG，Prioritizing URLs in Multi-Granula

10、rities)方法。 主題爬行的基本思想就是計算爬行隊列中的待爬行URLs(TCURLs，To Crawl URLs)的訪問優(yōu)先級，并每次選最有希望者進行爬行。因此，主題爬行的核心計算問題是：計算每個TCURL的訪問優(yōu)先級。PUMG以CTD-T和OPS4FC為基礎，利用站點、網頁內容、相關鏈接塊、錨文本、URL地址和鏈接類型六種特征，從站點級、網頁級、塊級和鏈接級四種不同的粒度來計算一個TCURL的優(yōu)先級。在PUMG中的子創(chuàng)新點

11、如下： a)提出了以站點為粒度來計算該站點中的TCURLs優(yōu)先級的方法。如果站點S1的相關網頁數(shù)(相關度)大于站點S2的相關網頁數(shù)(相關度)，那么在動態(tài)的爬行過程中，S1中已爬行的相關網頁總數(shù)(相關度總和)的增速比S2的快。因此，一個站點到目前為止已爬行的相關網頁數(shù)(相關度總和)的增速可以用來衡量該站點的TCURLs的優(yōu)先級。 b)在基于網頁粒度的TCURLs的優(yōu)先級計算中，不是利用整個網頁的內容，而是基于分塊后的該網頁

12、的主題文本和所有相關鏈接塊的錨文本集合。因為使用的是經過分塊后的網頁，有效的去除了其中的噪音，提高了優(yōu)先級計算的準確性。 c)針對當前網頁中鏈接較多，且相關鏈接易于聚集成塊的特點，提出了以鏈接塊為粒度來計算該塊中的TCURLs優(yōu)先級的方法。在計算時，只利用網頁的相關鏈接塊，因此有效的過濾掉大量的噪音鏈接。此外，有些相關鏈接的錨文本較短，單純依靠錨文本不能有效的發(fā)現(xiàn)它們，而以塊為粒度很好的解決了這個問題。 d)指出大部分網

13、頁的URLs地址包含了與網頁內容相關聯(lián)的一些語義標記(Token)，并提出了基于一個TCURL地址的語義標記來計算其優(yōu)先級的方法。首先，把中文URLs中的語義標記主要分成四種形式：完整英文、英文縮寫、完整拼音和拼音的第一個字母。然后，經過半自動的統(tǒng)計分析，創(chuàng)建了一個主題-標記映射表(TTMT，Topic-Token Mapping Table)。對于一個給定主題，從TTMT中找到對應的四種形式的標記；對于一個給定URL，根據(jù)分隔符“/”

14、和“.”將其分割成多個標記；然后通過兩者標記的匹配情況，確定該URL的優(yōu)先級。 e)提出了基于鏈接類型來計算一個TCURL的優(yōu)先級的方法。一個網頁的出鏈指向的網頁繼承了該網頁與主題的相關性。首先，利用一個TCURL與其父網頁在Web站點中的相對位置將鏈接分成五種類型。然后，給出了五種啟發(fā)式規(guī)則根據(jù)鏈接類型來推斷該TCURL指向的網頁與其父網頁的主題間的關系，并確定一個合理的繼承因子。利用父網頁與指定主題的相關度乘以繼承因子作為預

15、測的該TCURL指向的網頁與指定主題的相關度，從而作為該TCURL的優(yōu)先級。 (4)提出了一種基于多粒度優(yōu)先級計算的自適應主題爬行(AFC-PUMG，Adaptive Focused Crawling based on PUMG)算法。 AFC-PUMG從一些與預定主題相關的種子出發(fā)，利用OPS4FC對已爬行的網頁進行分塊，并抽取出網頁中的待爬行URLs，然后利用PUMG計算每個URL的優(yōu)先級，并按照其優(yōu)先級順序進行訪問

16、。AFC-PUMG給出了一個可變長度的路徑探測深度(PED，Path Exploring Depth)函數(shù)，使TCURLs的PED隨著其所在網頁與給定主題的相關度的變化而變化。從而使AFC-PUMG可以更加靈活的控制探測的方向和深度，獲取更多更相關的網頁。此外，根據(jù)不同粒度的優(yōu)先級計算之間的依賴關系，定義了它們計算的先后順序，并用來改進AFC-PUMG算法的優(yōu)先級計算過程，降低了算法的運行時間復雜度。 (5)基于上述技術實現(xiàn)了一

17、個主題爬行原型系統(tǒng)，從多個角度對本文的方法進行了實驗分析。 給出了原型系統(tǒng)的體系結構和具體的設計方案。我們在該原型系統(tǒng)中同時實現(xiàn)了寬度優(yōu)先(Bread-First)，最佳優(yōu)先(Best-First)，Shark-Search和本文的AFC-PUMG。進行了一系列的實驗，實驗針對多個不同的主題，在真實的Web環(huán)境上，從多個角度證明了本文提出的CTD-T、OPS4FC、PUMG和AFC-PUMG的有效性。在整體性能方面，將本文的AF