摘 要
隨著web上信息的迅速擴展，各項基於web的服務也逐漸繁榮起來。作為這些信息服務的基礎和重要組成部分，web信息採集正套用於搜尋引擎、站點結構分析、頁面有效性分析、web圖進化、用戶興趣挖掘以及個性化信息獲取等多種套用和研究中。然而，隨著人們對提供的各項信息服務要求越來越高，傳統的基於整個web的信息採集也越來越力不從心，它無法及時地採集到足夠的web信息，也不能滿足人們日益增長的個性化需求。為此，本文展開了對web上局部範圍內信息的有效採集研究，也就是基於主題的web信息採集研究。
根據我們在信息採集領域的長期積累以及國內外在基於主題的信息採集領域的發展，本文在綜述了基本情況後提出了一個基於主題的web信息採集結構模型，這包括主題與起始url選擇、spider採集、頁面分析、url與主題的相關性判定、以及頁面與主題的相關性判定等一系列步驟。我們分別給出了相關的處理算法和流程以及相應的數據結構，並針對研究過程中遇到的問題，提出了多個新的算法、判定規則和規律：
在hub特性、linkage/sibling locality特性、站點主題特性、tunnel特性的基礎上，總結出了主題頁面在web上的分布規律。
在定義主題和提出分類主題的基礎上，給出了主題選擇的方法。
採用client/server結構的spider系統，允許多機同時採集，實現了全面、高效並且靈活的信息蒐集。
在分析了html語法的基礎上，給出了對html頁面的主題、連結、標題的提取算法。
在url與主題的相關性判定中，在擴展元數據方法rw、rwb和連結分析方法pagerank的基礎上提出了ipagerank算法。
在頁面與主題的相關性判定中，套用在自然語言處理中比較成熟的基於關鍵字的向量空間模型計算頁面與主題的相似度。
試驗結果顯示，我們的工作是有效的，我們的系統有很強的實用價值，特別是url與主題的相關性判定中的ipagerank算法，有較大的突破。
關鍵字：web，信息採集，主題，受限，搜尋引擎，pagerank，ipagerank
目 錄
第一章 引言……………………………………………………………………………….1
1.1 背景... 1
1.2 本文安排... 2
第二章 web信息採集概述………………………………………………………………4
2.1 web信息採集系統的基本原理... 4
2.2 web信息採集系統的基本結構... 4
2.3 web信息採集面臨的主要困難和相應的技術手段: 6
2.4 採集系統實例... 8
第三章 web信息採集的研究現狀………………………………………………….. ...11
3.1 基於整個web的信息採集... 11
3.2 增量式web信息採集: 12
3.3 基於主題的web信息採集: 12
3.4 基於用戶個性化的web信息採集... 13
3.5 基於agent的信息採集... 14
3.6 遷移的信息採集... 15
3.7 基於元搜尋的信息採集: 15
3.8 小結... 15
第四章 基於主題的web 信息採集基本問題研究………………………………… ...17
4.1 基於主題的web信息採集的定義... 17
4.2 基於主題的web信息採集的優點... 17
4.3 基於主題的web信息採集的分類... 18
4.4 主題頁面在web上的分布特徵... 19
4.5 相關性判別算法研究... 21
第五章 基於主題的web 信息採集系統模型及我們的對策……………………… ...37
5.1 系統模型... 37
5.2 模型中的關鍵問題及我們的策略... 37
第六章 主題選擇………………………………………………………………………...41
6.1 主題的定義... 41
6.2 主題分類目錄... 41
6.3 web上的主題分類目錄的特點... 42
6.4 主題選擇策略... 42
第七章 spider採集……………………………………………………………………44
7.1 spider的系統模型... 44
7.2 採集算法及實現... 45
第八章 頁面分析……………………………………………………………………...…49
8.1 html語法分析... 49
8.2 頁面中正文的提取... 49
8.3 頁面中連結的提取... 50
8.4 頁面中標題的提取... 51
第九章 url、頁面與主題的相關性判定…………………………………………...…52
91 url與主題的相關性判定——ipagerank算法... 53
9.2 頁面與主題的相關性判定——向量空間模型算法... 56
第十章 系統的實現與總結…………………………………………………………...…58
10.1 系統實現情況... 58
10.2 系統測試結果... 58
103 進一步的工作... 62
10.4 結論... 62
1.1 背景
隨著internet/intranet的迅速發展，網路正深刻地改變著我們的生活。而在網上發展最為迅猛的www（world wide web）技術，以其直觀、方便的使用方式和豐富的表達能力，已逐漸成為internet上最重要的信息發布和傳輸方式。隨著資訊時代的到來和發展，web上的信息如雨後春筍般迅速增長起來。截止到2000年7月，internet上的網頁數量就已經超過21億，上網用戶超過3億，而且網頁還在以每天700萬的速度增加[徐澤平 2001]。這給人們的生活提供了豐富的資源。
然而，web信息的急速膨脹，在給人們提供豐富信息的同時，又使人們在對它們的有效使用方面面臨一個巨大的挑戰。一方面網上的信息多種多樣、豐富多彩，而另一方面用戶卻找不到他們所需要的信息。因而基於www的網上信息的採集、發布和相關的信息處理日益成為人們關注的焦點。
為此，人們發展了以web搜尋引擎為主的檢索服務。為了解決網上信息檢索的難題，人們在信息檢索領域進行了大量的研究，開發了各種搜尋引擎(如google、yahoo)。這些搜尋引擎通常使用一個或多個採集器從internet上收集各種數據(如www、ftp、email、news)，然後在本地伺服器上為這些數據建立索引，當用戶檢索時根據用戶提交的檢索條件從索引庫中迅速查找到所需的信息[bowman 1994]。作為這些搜尋引擎的基礎和組成部分，web信息採集正發揮著舉足輕重的作用，並且隨著套用的深化和技術的發展，它也越來越多的套用於站點結構分析、頁面有效性分析、web圖進化、內容安全檢測、用戶興趣挖掘以及個性化信息獲取等多種服務和研究中。簡單說，web信息採集是指通過web頁面之間的連結關係，從web上自動地獲取頁面信息,並且隨著連結不斷向所需要的web頁面擴展的過程。
傳統的web信息採集的目標就是儘可能多地採集信息頁面，甚至是整個web上的資源，而在這一過程中它並不太在意採集的順序和被採集頁面的相關主題。這樣做的一個極大好處是能夠集中精力在採集的速度和數量上，並且實現起來也相對簡單，例如google採集系統在並行4個採集器時的速度可以達到每秒100頁，從而它配合搜尋引擎給網路用戶帶來了很大的便利。但是，這種傳統的採集方法也存在著很多缺陷。
隨著www信息的爆炸性增長，信息採集的速度越來越不能滿足實際套用的需要。最近的試驗表明，即使大型的信息採集系統，它對web的覆蓋率也只有30-40%。解決這一問題的直接辦法是升級信息採集器的硬體，採用處理能力更強的計算機系統，然而這種方法的擴展性有限，性價比也不高。一個更好的解決方法是採用分散式方法來提高並行能力，但是並行不但增加了系統的開銷和設計的複雜性，並且並行換來的效益也隨著並行採集器數目的增加而顯著地減小。目前，一般的大型採集系統都採用了並行機制，但並行帶來的改善效果仍遠不能滿足人們的需要。人們需要從其它角度改善目前的困境。比如說對整個web分塊採集，並將不同塊的採集結果整合到一起，以提高整個web的採集覆蓋率。
internet信息的分散存儲、管理和動態變化也是困擾著信息採集的問題之一。由於信息源隨時可能處於變化之中，信息採集器必須時常地刷新數據，但仍無法避免採集到的頁面失效的情況。對於傳統的信息採集來說，待刷新頁面數量的巨大使得很多採集系統刷新一遍需要數周到一個月的時間[aggarwal et al. 2001][brin&page 1998]，這使得頁面的失效率非常地巨大。selberg和etzioni在1995年的調查發現，通過internet中最常用的一些搜尋引擎查詢到的結果url中，14.9%的目標頁面已經失效了[selberg&etzioni 1995]。一個顯然的緩解辦法就是減小採集頁面的數量，從而減小刷新一遍的時間，進而減小頁面已採集頁面的失效率。
傳統的基於整個web的信息採集需要採集的頁面數量十分浩大，這需要消耗非常大的系統資源和網路資源，而對這些資源的消耗並沒有換來採集到頁面的較高利用率，事實上，它們中有相當大的一部分利用率很低。這是因為，用戶往往只關心其中極少量的頁面，並且這些頁面往往集中在一個主題或幾個主題內，而採集器採集的大部分頁面對於他們來說是沒有用的。儘管許多用戶合起來的效果提高了整個採集到頁面的利用率，但仍然顯得利用率偏低，這顯然是對系統資源和網路資源的一個巨大浪費。為了有效的提高它們的利用效率，我們有必要另闢蹊徑。
對於用戶的一般信息查詢檢索要求，傳統信息採集器所組成的搜尋引擎能夠提供較好的服務，但對於用戶更多的具體要求，這種傳統的基於整個web的信息採集所提供的服務就難以令人滿意。對於每個用戶來說，儘管他們輸入同一個查詢詞，但他們渴望得到的查詢結果卻是不一樣的，而傳統的信息採集和搜尋引擎卻只能死板地返回相同的結果，這是不合理的，需要進一步提高。
這些問題主要都源於兩點：採集頁面的數量過於龐大和採集頁面內容的過於雜亂。對整個 web頁面進行分類，按類別採集，基於主題進行採集的思想應運而生。它有效的減少了採集頁面的數量，增加了採集頁面的規整程度，進而有效的緩解了上述問題。因此需要開展對基於主題的web信息採集研究。
1.2 本文安排
第二章概述了web信息採集的基本結構、所面臨的主要困難和相應的技術手段。在第三章里，討論了web信息採集的研究現狀和熱門的發展方向，並通過論述指出基於主題的web信息採集的迫切性和必要性。在第四章里，我們討論了基於主題的web信息採集的基本問題，重點是對主題頁面在web 上的分布和相關性判定算法的研究。第五章給出了我們設計的基於主題的web信息採集系統的結構模型，並就搭建一個這種採集系統所面臨的關鍵問題和相應對策做了簡單的描述。在接下來的四章中(從第六章到第九章)，我們按照結構模型中的主要部分主題選擇、spider採集、頁面分析、url和頁面與主題的相關性判定分別作了較為詳細的論述，並給出了我們的設計方案和算法。最後，在第十章里，我們給出了系統的實驗結果和進一步需要研究的問題。
第二章 web信息採集概述
在研究基於主題的web信息採集之前，讓我們先來看看web信息採集的基本情況，這包括web信息採集的基本原理、基本結構和主要難題。它們是從各類web信息採集系統中抽象出來的，因此代表了比較本質和共性的特徵，而對於每個實際的採集系統來說，又與它們有所差別。為了更好的了解采採集系統，我們在本章的最後列舉了兩個實例。
2.1 web信息採集系統的基本原理
web信息採集（web crawling），主要是指通過web頁面之間的連結關係，從web上自動的獲取頁面信息,並且隨著連結不斷向所需要的web頁面擴展的過程。實現這一過程主要是由web信息採集器（web crawler）來完成的。根據套用習慣的不同，web信息採集器也常稱作web spider、web robot和web worm。粗略的說，它主要是指這樣一個程式，從一個初始的url集出發，將這些url全部放入到一個有序的待採集佇列里。而採集器從這個佇列里按順序取出url,通過web上的協定，獲取url所指向的頁面，然後從這些已獲取的頁面中提取出新的url,並將他們繼續放入到待採集佇列里，然後重複上面的過程，直到採集器根據自己的策略停止採集。對於大多數採集器來說，到此就算完結，而對於有些採集器而言，它還要將採集到的頁面數據和相關處里結果存儲、索引並在此基礎上對內容進行語義分析。
2.2 web信息採集系統的基本結構
如圖2.1所示，web信息採集系統基本上可以劃分為七個部分:url處理器、協定處理器、重複內容檢測器、url提取器、meta信息獲取器、語義信息解析器和資料庫，它們協調起來從web上獲取信息。圖中的箭頭表示數據走向。
2.2.1 url處理器
這個部件主要給待採集的url排序，並根據一定的策略向協定處理器分配url。按照採集系統規模的不同，url可以是多個採集佇列，也可以是一個url server。比如，天羅web採集系統採用了多個採集佇列，而google採集系統則使用了url server，以達到更快的處理速度。url處理器主要有三個數據來源：1)初始的種子url集，如圖中的粗箭頭所示；2)從url提取器傳輸過來的url集,它們是從已經採集到的頁面中提取出來的；3)頁面的meta、主題以及摘要等信息，來自meta信息獲取器，它們主要用來顯示從url提取器中傳輸過來的url的重要性，為在這裡排序提供依據。另外，url處理器還有一個任務就是dns解析。
圖2.1 web信息採集系統基本結構
2.2.2 協定處理器
這個部件處於系統的底層，主要通過各種web協定來完成數據的採集。一般來說協定包括http、ftp、gopher以及bbs,也有些採集系統根據套用的需要採集web chat、icq等特殊信息。但從主流上看，仍以http為主。
2.2.3 重複內容檢測器
web上存在著大量的鏡像頁面和內容，最近的研究表明，將近30%的頁面是重複的。這極大的浪費了網路的頻寬和影響了系統的效率。所以，重複內容檢測變成了採集系統，特別是大型採集系統的重要組成部分。要採用的檢測方法，根據系統的需要，從簡單的段落匹配到複雜的相似度比較中選擇。
2.2.4 url提取器
對於採集到的頁面，經過重複內容檢測後，需要分析其中的連結，並對連結進行必要的轉換，這些任務由url提取器來完成。首先判別頁面類型，對類型為“text、html、shtml和htm”等的頁面進行分析連結。頁面的類型可由應答頭分析得出，有些www站點返回的應答信息格式不完整，此時須通過分析頁面url中的檔案擴展名來判別頁面類型。需要分析的標記包括<a href=……>、<area href=……>、<base href=……>、<frame src=……>、<img src=……>、<body background=……>和<applet code=……>等。頁面連結中給出的url可以是多種格式的，可能是完整的包括協定、站點和路徑的，也可能是省略了部分內容的，或者是一個相對路徑。為處理方便，一般先將其規格化成統一的格式。
2.2.5 meta信息獲取器
這裡所要獲取的內容包括已採集頁面的meta信息、anchor信息、頁面的標題、頁面的摘要等。獲取它們的主要目的是力圖在沒有對頁面內容語義信息進行理解的前提下，儘可能多的挖掘meta、結構等的語義信息，來為從這些頁面中提取出來的url的好壞，給出一個度量。度量的結果傳輸到url處理器，用於排序。
2.2.6 語義信息解析器
根據採集策略的不同,有些採集器還有語義信息解析器。這裡所說的語義信息解析就是指對文本內容建立簡單的索引。因為它在一定程度上挖掘了頁面內容的語義，所以叫做語義信息解析器。對於一些大型的信息採集器，比如alta vista，由於採集的信息量很大，對語義挖掘的深度要求較高，所以一般將頁面語義挖掘與信息採集獨立開來，而用專門的indexer等部件進行處理。對於一些輕量級的採集系統，比如基於用戶個性化的採集，因為採集的信息量不大（這樣語義信息解析就不太影響採集效率）和採集過程中更需要語義信息制導，所以它們也常用到語義信息解析器。
2.2.7 資料庫
經過重複內容檢測後的頁面數據、提取出來的meta信息、主題和摘要等都要存入資料庫，以備其他套用使用。比如，對於google這樣的搜尋引擎，這個資料庫中的內容將用於建立索引。如果系統有語義信息解析器，則解析出來的內容也存入資料庫。由於數據較多，所以在存入資料庫之前，數據一般要進行壓縮。
2.3 web信息採集面臨的主要困難和相應的技術手段:
粗看起來，採集的過程似乎比較簡單，但實際上，它卻存在著許多技術上和工程上的挑戰。在分析這些挑戰之前，先看一下web的特點。
2.3.1 web的特點
web與傳統的信息媒介相比，主要存在以下幾個特點：1)信息容量的巨大性，在1998年7月，web上的靜態文本大約有3億5千萬個，並且以每月600gb的速度增長[kahle 1997]；2)web的動態性，每天web中的內容和web的結構都在變化著；3)web的異構性，web中包含的檔案類型各式各樣，包括圖像、圖片、聲音、文本以及script等；4)web頁面的重複性，最近的研究表明，將近30%的頁面是重複的；5)高連結性，平均每個頁面有超過8個連結指向別的頁面；6)多語種性，現在web上的頁面語種超過了100個。這為web的有效採集，特別是為搜尋引擎的採集提出了巨大的難題。
2.3.2 web採集面臨的技術困難和相應手段
從技術角度看，挑戰主要有以下幾點：第一，web信息容量的巨大性使得採集器不可能採集到所有的web頁面，而且很多採集系統也沒有足夠大的空間來存放採集到的所有頁面。如何提高採集的效率，即在單位時間內採集到儘可能多的高質量頁面，是採集系統面臨的一個難題。目前，有五種頁面質量高低的計算方法：1).similarity(根據頁面和指導採集的問題之間的相似度)；2).backlink(根據這個頁面在web圖中的入度大小)；3).pagerank(根據指向它的所有頁的平均權值之和,一頁的平均權值定義為這頁的權值除以這頁的出度)；4).forwardlink(根據這個頁面在web這個圖中的出度的大小)，5).location(根據這個頁面的位置信息)。cho中對比了寬度優先方法、backlink方法和pagerank方法[cho, molina & page 1999]，並根據試驗比較得出pagerank方法最好。這是因為pagerank方法反映的是一種全局的頁面質量分布，它能夠較快的發現全局的高質量頁面。
第二，並行性問題。頁面的採集速度一直是影響採集器性能的重要原因。一方面，web中的頁面數量非常龐大，另一方面，網路中的連線速度又非常緩慢，這客觀上要求系統需要並行。然而，要並行又引入新的問題：1).重複性(overlap)，多個不同的採集器或採集執行緒在同時採集的時候增加了重複頁面；2).質量問題(quality)，單個系統能夠根據算法採集到全局最優的頁面。而如果並行，每個採集執行緒只能看到局部頁面，它能夠採集到的頁面質量有所下降；3).通信頻寬代價（communication bandwidth），為了並行，各個採集執行緒之間不可避免的要有一些通信。一般來說，採集系統採用兩種模式來並行：區域網路並行模式(所有的採集執行緒都運行在同一個區域網路內，它們之間通過高速的內連線進行通信)和分散式並行模式(採集系統被分布在地域上較遠的internet上，通過網路進行遠程通信)。在並行時，採集系統也可選用以下三種方式合作：1).獨立方式，各個採集器之間獨立的採集各自的頁面，互不通信；2).動態分配方式，有一個中央協調器，動態的協調分配url給各個採集器；3).靜態分配方式，將url按事先劃分分配給各個採集器。對於靜態分配方式，存在一種跨區連結(inter-link，指一個採集器在提取連結時遇到的不屬於自己採集範圍的連結)。難題在於跨區連結並不一定能被它所屬於的採集器發現，如果本採集器採集了則可能重複採集，如果不採集則可能漏采。近期的研究工作針對這種情況比較了三種模式: 1).防火牆模式,完全不採集inter-link頁面；2).交叉模式，採集遇到的inter-link頁面；3).交換模式(exchange mode)當採集到inter-link，就將這些連結保存起來，積累到一定數量後傳輸給相應的採集器進行採集。實驗結果和我們的直覺一樣:交換模式最好：交換模式最好[cho 2001]。
第三,刷新問題。為了保持採集到的頁面是最新的，採集系統不得不對已經採集過的頁面進行周期性的更新。而隨著web的爆炸性膨脹，這個問題幾乎變成了不可逾越的鴻溝。最近的一項報告顯示，甚至流行的web搜尋引擎，頁面刷新一次甚至持續數月[lawrence&giles 1999]。同時，這份報告也顯示，14%的搜尋引擎提供頁面是無效的。cho試圖用泊松過程(poisson process)來描述頁面變化率，並研究和對比了三種頁面刷新策略：固定順序的刷新，隨機刷新和純隨機刷新策略。直覺上，更多的刷新應該分配給更那些更新快的頁面。但研究表明，用較高的頻率刷新更新快的頁面並不一定是明智之舉，對各種頁面採用相同的刷新周期效果更好，而效率最佳的點在這兩種刷新策略中間。這是因為，過高頻率的刷新更新快的頁面，使得其它頁面有較少的刷新機會，反而造成總體刷新質量下降[cho 2001]。
2.3.3 web採集面臨的工程困難和相應手段
從工程角度看：第一，正如前面分析的，web中的信息是完全異構、混亂和無序的，檔案格式各式各樣，網路狀況也隨時間變化莫測。所有的這些不確定性因素，為系統實現帶來了極大的困難。這就要求採集系統有完善的異常處理和故障恢復機制，充分考慮到實際網路環境中可能出現的各種情況。
第二，多執行緒與並行機制使系統變得非常複雜。在這種複雜的環境下，系統的許多瓶頸變得異常突出，並需要採用多種設計技巧來解決。比如說，對一個網站的採集不能過分集中，以防止造成網站負擔過重，google中的頁面採集就是同時採集多個站點。在google中，系統為每一個採集器都配了一個dns快取伺服器，以加快dns解析的速度。
2.4 採集系統實例
下面就以兩個實際的採集系統為例來具體說明，它們即有一般採集器的共同特點，也有自己的特色。
2.4.1 mercator信息採集器的基本結構和工作過程
mercator信息採集器是一個由康柏研究中心研製的面向整個web的分散式多執行緒信息採集系統[heydon&najork 1999]。它的基本結構如下圖2.2所示，採集步驟是從1)到8)不斷循環。步驟1)就是從多個執行緒共享的url frontier中移出絕對路徑的url來。絕對路徑的url中指明了這個url採用什麼方式下載。具體和協定相關接口的實現在protocol modules中。並且，用戶可以通過設定檔案來告訴系統裝載哪些協定接口。
在步驟2)中,系統選擇了相應的協定,通過了dns解析並從web上下載了頁面，然後將頁面放入3)rewindinputstream（ris）中，ris相當於一個快取，能夠多次快速的讀內容。一旦檔案被放進ris,這個工作執行緒就啟動內容檢測模組看是否此頁面已經被採集過，這就是步驟4)。如果採集過，系統就拋棄此頁並跳至步驟1)。
如果此頁沒有採集過，就進入步驟5)processing modules,在這裡對頁面進行初步的分析，比如提取標題、摘要和連結。預設狀況下，頁面中的所有連結都被提取出來，並轉換成絕對url。然後進行步驟6),也就是根據用戶要求對url進行過濾(filtering)。如果url通過了過濾器，則檢查此url是否已經在url待採集庫中(步驟7)。如果此url沒有，則將它加入到url frontier中,等著被選中進入下一輪循環(步驟8)。
圖2.2 mercator信息採集器結構
2.4.2 天羅信息採集系統的基本結構和工作過程
天羅信息採集系統是在國家“863”計畫下由曙光公司開發的智慧型導航系統的子系統。本採集系統最初的目標是面向整個web的信息採集，隨著web服務向個性化主動服務等領域的拓展，本採集系統的後續版本在中科院計算所領域前沿青年基金資助下正在向基於主題的採集方向發展。
如圖2.3所示，天羅web信息採集系統從功能上看可分為兩個部分：採集器部分和控制部分，中間的豎立虛線將他們分開。採集器部分主要負責實際採集，它分為三個部分。1).站點採集。把整個web以站點為單位劃分成若干個連通子圖是合乎人們的瀏覽習慣的，並且也是利於存儲的。天羅web信息採集系統的設計就是根據這一點，對web上的頁面以站點為單位進行採集。2).頁面採集。儘管系統從粗粒度上看，採集是以站點為單位的，但是從細粒度上講，每次只採集一頁。這個部分考慮的重點就是對採集每頁相關的協定的處理和實時網上異常的處理。3).存儲庫，主要存儲採集到的數據、站點結構信息以及相關的有用信息。
圖2.3天羅信息採集系統結構
控制部分主要負責採集以外的協調、策略以及與套用的接口，它分為五個部分。1).採集系統設定，主要用於系統管理員對採集系統的控制，包括設定採集起點和採集策略。2).採集系統控制，這是採集系統最具有全局觀念的一個子系統，它主要負責總體控制和其他各子系統之間的協調和連線,另外它還集中式的控制多個採集器並行。3).存儲庫，主要負責存儲一致化處理後的各項數據以及在此基礎上進行索引等處理的數據。4).採集策略處理，負責處理採集系統在理論上最難的一個部分——如何有效的採集和動態的刷新。5).安全開關，在實際套用系統中，採集器往往直接和web相連，而同時又與內部的套用伺服器相連，如果不加安全處理，web對於套用伺服器是非常危險的。為此，本採集系統設計了低成本高效率的安全開關。當與套用系統交換數據時，採集系統與web斷開；當在web上採集數據時，採集系統與套用系統斷開。這也是本採集系統的特色之一。圖中的箭頭描述了數據流向。
為了提高採集的效率，天羅web採集系統採用伺服器(採集系統控制)/採集器的結構使採集系統具有很好的可擴展性。管理員可根據系統採集規模的變化動態地調整採集器的數量，在保證系統性能的前提下儘量減少系統開銷，達到最佳的性能/價格比。而且在規模動態變化的過程中，系統能維持一致的管理和數據輸出接口。
第三章 web信息採集的研究現狀
目前，web信息採集技術的發展正如火如荼，在傳統的web信息採集技術的基礎上，又出現了許多輕型的各具特色的採集技術。我們根據國內外流行的看法，結合我們在這方面長期積累的實際經驗，把web信息採集的發展方向分為以下幾種：基於整個web的信息採集(scalable web crawling)，增量式web信息採集(incremental web crawling)，基於主題的web信息採集(focused web crawling)，基於用戶個性化的web信息採集(customized web crawling)，基於agent的信息採集(agent based web crawling),遷移的信息採集(relocatable web crawling)，基於元搜尋的信息採集(metasearch web crawling)。實際系統往往是以上幾個採集技術的結合。下面分別予以介紹。
3.1 基於整個web的信息採集
這種信息採集在國外也常叫做scalable web crawling，是一種較傳統的採集思想。主要是指目標為從一些種子url擴充到整個web的信息採集。這種信息採集主要是作為門戶搜尋引擎和大型的web服務提供商的數據收集部分。對於這類信息採集來說，由於採集的範圍和數量都非常巨大，所以對採集速度和存儲空間要求很高；由於目標是採集整個web，所以對採集頁面的順序要求相對較低；由於待刷新的頁面太多，儘管並行很多的採集器，但仍需數周乃至數月的時間來刷新一次，而且，隨著並行採集器數量的增加，整個系統能力的提高越來越小，穩定性卻越來越低。但是，這類信息採集又不能沒有，人們不光有個性化需求和具體主題的需求，還有許多廣泛主題的需求，而由這類web信息採集器構建的搜尋引擎，恰恰適合搜尋廣泛的主題。事實上，這類信息採集仍有很強的套用需求，目前在實際套用中占較為主流的地位。下面通過簡要分析三個實例google[brin&page 1998][cho, molina &page 1999]、mercator[heydon&najork 1999]和internet archive[burner 1997]來進一步說明這類信息採集。
google crawler是一個分散式的基於整個web的採集器，主要在美國stanford大學用c/c++設計。它並沒有採用多執行緒技術，而是採用異步i/o管理事件來實現並行。它有一個專門的url server 來為並行的多個採集器維護url佇列。為了保持高速的獲取頁面，每個採集器一次同時打開大約300個連線。在使用4個採集器時，系統的峰值速度大約是每秒100頁，相當於每秒大約600k的數據。由於dns解析壓力很大，google為每個採集器分配一個dns cache，這樣不需要在每次採集頁面時都做一次dns解析。google還使用了許多算法對系統性能進行最佳化，最著名的就是pagerank算法。在權衡了時空代價後，google選用了zlib 壓縮格式壓縮採集到的數據。
康柏系統研究中心研究實現了mercator web crawler。與google不同，它主要使用java實現的，在並行機制上，則採用了多執行緒技術，一般情況下，每個採集器能夠啟動數百個執行緒。mercator也有一個單獨的url處理器，用於收集和合併從採集到的頁面中提取出來的url。它有一個ris部件，用於去除相同內容的頁面，因此有較低的檔案重複率8.5%。mercator的另一大特點就是可擴展性，例如擴展一種新的採集協定。設計者聲稱，在雙533mhz cpu、2g記憶體和118g硬碟環境下，mercato採集速度是每秒112個檔案。
internet archive 使用異步i/o技術來並行採集整個web，它的目標就是為整個web存檔。為此，每個採集器被分配64個站點，同時每個站點的所有頁面都被分配給同一個採集器。在提取連結時，如果提取出的連結仍屬於這個採集器，就將這個連結放入相應的待採集佇列里，否則將它存在log檔案中，積累一段時間後，再按所屬站點傳輸給相應的採集器。
3.2 增量式web信息採集:
這種信息採集在國外也常叫做incremental web crawling。傳統上，web採集器根據自己的需要採集足量的信息後停止採集，當一段時間後這些數據過時後，它會重新採集一遍來代替原有的採集信息，這種採集器稱作周期性web採集器(periodic web crawler)。而另外一種方法，對待舊的頁面採用增量式更新，也就是說，採集器只需要採集新產生的或者已經發生變化的頁面，而對於沒有變化的頁面不進行採集。理想狀況中，已採集到的信息應該和web中的信息是一致的，然而實際上web的動態性、異構性和複雜決定了採集到的信息在相當短的時間內就可能過時，那種理想是不實現的，我們能夠做的就是儘量逼近這種理想。和周期性信息採集相比，增量式信息採集能極大地減小數據採集量進而極大地減小採集時空開銷，因此它成為實際採集系統的首選。前面所說的google、mercator和internet archive都是增量式信息採集系統。但是，增量式信息採集在減小時空開銷的同時，卻增加了算法的複雜性和難度，同時又面臨新的難題，例如如何根據頁面的變化快慢分配系統的採集能力。在最近的一項實驗中[cho et al. 2000]，隨機選擇了270個站點(包括132個.com站點，78個.edu站點，30個站點和30個.gov站點)並下載了72000個頁面，發現超過40%的.com頁面每天變化，.net和.org變化適中，而.edu和.gov變化最為緩慢。ibm設計完成的信息採集器webfountain是一個典型的增量式系統[edwards et al. 2000]。它採用了一個最佳化模型來控制採集策略。這個模型沒有對web頁面變化的統計行為做任何假設，而是採用了一種適應性的方法，根據先前採集周期里採集到的結果的實際變化率進行調整。作者也提到為更新頻率較快的頁面提高刷新頻率。
3.3 基於主題的web信息採集:
這種信息採集器在國外叫做focused crawler，是指選擇性的搜尋那些與預先定義好的主題集相關頁面的採集器，對它的研究現在比較熱門。它也是本文所要討論的重點，我們將在以後的章節里詳細論述。在這裡，先看看國際上流行的此類信息採集系統。
印度理工大學(iit)和ibm研究中心的研究人員開發了一個典型的基於主題的web信息採集器[chakrabarti et al. 1999]。它的主題集是用樣本檔案來描述的。為了達到採集時主題制導的目的，設計者設計了兩個文本挖掘的部件來指導採集。一個是分類器(classifier),用於評價採集文本是否與主題相關。另一個是精煉器(distiller)，用於識別能夠在較少的連結內就連線到大量相關頁面的超文本節點。採集系統首先保存一個經典的主題分類（例如yahoo的主題分類），並且為每一個主題分類都保存若干個內容樣本，用於詳細的刻畫這一類主題。用戶在使用本採集器搜尋與主題相關的頁面時，必須在系統的主題分類樹中先選擇一個主題，用於指導採集。由於要選擇和剪枝，採集速度並不太快，在雙333mhz pii cpu，256m內從 scsi硬碟下，每個採集器的採集速度為每小時6000頁。
aggarwal則提出了一種針對兩個假設的基於主題的web信息採集方法[aggarwal et al. 2001]：1).linkage locality,即被相關於某一主題的頁面連結到的頁面趨向於擁有同一主題。 2).sibling locality,對於某個連結到某主題的頁面，它所連結到的其它頁面也趨向於擁有這個主題。這樣，在採集器接到一個主題採集請求命令後，它就從自己保存的關於這個主題的起點出發，按照兩個假設蔓延，並利用指向備選頁面中的url結構以及其他一些meta信息使用統計學習的方法進行修剪，使採集的頁面很快接近主題。
web上80%的內容是動態產生的，並且呈增長趨勢[steve lawrence 1998]，而這些內容卻幾乎沒有被採集下來。美國stanford大學的hidden web exposer project就是要建立一個採集這些動態頁面的採集器[raghavan& garcia-molina 2000]。因為很多隱式頁面要通過填寫表單等人工手段才能獲取，所以採集器在採集之前需要人工輔助來事先填好領域信息，然後進行基於主題的採集。儘管主題信息的填寫工作較繁瑣，但同一主題的信息結構較相似，只要用戶填寫一次基本上就可以實現自動採集了。
menczer則評價了三種關於基於主題採集的策略[menczer et al. 2001]：1).best first crawler(通過計算連結所在頁面與主題的相似度來得到採集優先權)；2).pagerank(通過每25頁計算一遍pagerank值來得到採集優先權，pagerank值計算方法前面已經說過)；3).infospiders（通過連結周圍的文字，利用神經網路和遺傳算法來得到採集優先權）。經過試驗作者發現，bestfirst最好，infospiders次之，pagerank最差。一向被給予高度評價的pagerank算法之所以表現不佳，作者認為是它選出的高質量頁面是基於廣泛主題的，而對於特定主題來說頁面的質量可能就不高了。
3.4 基於用戶個性化的web信息採集
不同的用戶對一個搜尋引擎提交同一個檢索詞，他們期望的返回結果是不同的，然而搜尋引擎卻只能返回相同的檢索結果，這顯然不能完全滿足用戶的需要。為此，採集系統的設計者把目光投向了基於用戶個性化的web信息採集(customized web crawling)。這是一種輕量級的採集系統，它的目標就是通過用戶興趣制導或與用戶互動等靈話手段來採集信息。系統根據實際需要可以直接把採集結果提供給用戶，也可以先存儲起來等到以後再提供。這種個性化信息一般有兩個來源，第一個是用戶手工在系統提供的個性化設定頁面里設定，這裡主要考慮的問題是如何全面靈活簡單的提供這種設定，使得用戶的各種喜好都能夠表達。第二個是系統自動獲取，通過跟蹤用戶的瀏覽習慣和興趣等。sphinx是一個java工具包組成的環境互動式信息採集器[miller&bharat 1998]。它是一個典型的此類採集系統，用戶的個性化設定嵌在工作檯里，並針對指定的站點進行個性化採集。[kamba 1995]中介紹了一種新聞的個性化採集，這是個性化和主題採集套用結合的一個實例。
3.5 基於agent的信息採集
隨著智慧型agent技術的發展，agent與信息採集相結合的技術也逐漸熱門起來，這種採集技術叫做agent based crawling。智慧型agent系統是指一種處於一定環境下包裝的計算機系統，為了實現設計目的，它能夠在該環境下靈活地自主地活動。它除了具有自治性(agent運行時不直接由人或其它東西控制，它對自己的行為和內部狀態有一定的控制權)、社會能力(多個agent體之間信息交換和協作)、反應能力(對環境的感知和影響)和自發行為(agent的行為是自主的)，還具有一般人類所有的知識、信念、意圖和承諾等心智狀態,這使得智慧型agent系統具有人類的社會智慧型。它的這些特點使得它在面臨諸如基於主題和用戶個性化的採集時，更加方便靈活和適應力強。比如說在基於用戶個性化的採集中，它能像人一樣感知用戶的興趣變化，自主地靈活地智慧型地調整採集策略。
美國的愛荷華大學進行的arachnid研究項目就是這方面的典型代表。它主要通過模擬一個生態系統的發展和演變來設計web信息採集器infospiders[menzcer 1999]和[menczer&belew 1998]。系統的目標是從用戶的角度在網上搜尋最有效的頁面。它的採集原理基本如下：以一個用戶的書籤作為採集起點，通過分析這些起點周圍的小區域和連結關係來發現新的要採集的頁面。它通過對採集到的頁面是否真的跟採集前的相關性預期相符，來增加和減少能量，當能量很高時，還可以生出新的子樹，而當能量過低時，它就死亡。它的一大好處是杜絕了過期頁面。但缺點也較明顯。因為它是臨時到網上去搜尋，而不是在已完成的索引上直接匹配，所以儘管搜尋精確度甚至更好，速度卻比較慢。因此，它的定位是作為門戶搜尋引擎的有效補充。
美國麻省理工學院的一個系統letizia是利用agent來輔助用戶瀏覽web頁面的輔助工具[lieberman 1995]。當用戶通過一個瀏覽器瀏覽頁面時，agent就自動跟蹤了用戶的瀏覽行為，用啟發式方法來估計用戶的興趣，並根據用戶當前位置，從網上採集滿足當前感興趣的頁面推薦給用戶。用戶可以遵從這些推薦，也可以按著自己的方式瀏覽，而同時agent則不停地根據新的變化採集和推薦，推薦的內容緊跟當前用戶的瀏覽頁面。
美國stanford大學研究了一種基於學習agent的主題信息採集系統[balabanovic&shoham 1995]。它使用向量空間模型vsm和tf*idf來給發現的文本評分排序，並使用機器學習策略和用戶反饋來修改啟發式搜尋。
3.6 遷移的信息採集
這種信息採集器也叫relocatable web crawler。在採集時，它並不像其他採集器在本地向web站點伺服器發頁面請求，而是將自己上載到它所要採集的伺服器中，在當地進行採集，並將採集結果壓縮後，回傳到本地。這樣做的一個明顯優點是大量的節省了web資源，大量的剪裁工作將在被採集對象的伺服器上完成。但明顯的一個不利是採集器可能並不被被採集對象所信任，因為這樣被採集站點會由於給訪問者許可權太大而易遭到病毒攻擊。解決的辦法是建立一種信任機制，採集器由權威的信任機構評估並授權。還有另一種方法，採集器先遷移到離被採集站點很近的地方實施採集，這種方法是遷移到被採集站點方法和不遷移方法的折衷。sphinx 信息採集器就是這種思路的嘗試[miller&bharat 1998]。
3.7 基於元搜尋的信息採集:
元搜尋引擎（metasearch）的研究一直是搜尋引擎研究的一個熱點。它是這樣一種搜尋引擎系統，對用戶提交的查詢請求通過多個領域或門戶搜尋引擎搜尋，並將結果整合後以統一的界面提交個用戶。一般元搜尋引擎並不保存web頁面的索引檔案，但對於一些複雜的元搜尋引擎,它要保存為它服務的每個搜尋引擎的信息特徵，以便能夠在用戶查詢到來後做出好的搜尋引擎選擇。作為搜尋引擎先頭部隊的信息採集器，在元搜尋引擎中有相當的退化，但仍為web採集的一個方向,叫做基於元搜尋的信息採集(metacrawler)。
美國binghamton大學的研究者圍繞一個元搜尋引擎技術的難點：資料庫選擇問題進行了研究[zonghuan wu 2001]，並提出了一個解決上述問題的新方法。因為要借用其它搜尋引擎的索引數據，所以叫做資料庫選擇。他們的方法是：就每個有代表性的問題對大量的領域搜尋引擎排序，這有點像建立索引時的倒排表。當一個檢索詞來了後，通過相似度比較選擇一個最接近的代表性問題，進而確定了要選用的搜尋引擎。
美國華盛頓大學在metasearch方面的研究在[selberg&etzioni 1997]有詳細的說明。作者認為，大多數搜尋引擎對於同一個查詢要求返回的結果很不相同，質量也參差不齊。試驗發現，使用單獨一個搜尋引擎錯過大約77%的相關頁面[selberg&etzioni 1995]。所以，他們力圖在提高查全率的同時，也力爭利用單個搜尋引擎在某一領域的優勢提高平均查準率。
3.8 小結
隨著人們對web服務的種類和質量要求越來越強烈，各種各樣的信息採集系統也應運而生，並朝前不斷發展。最初，人們希望能夠設計出既大而全又質量好的信息採集系統(即基於整個web的信息採集)，這顯然是一個非常困難的問題，因為兩方面都要求必然造成兩方面都不能做得很好。人們經過不斷的努力和探索，從最初的web worm到現在的google,從基於詞的語義信息理解到web連結結構信息挖掘，發展到了今天已經取得了令人矚目的進步，優秀的基於整個web的採集器以及相關的搜尋引擎，已經在很多方面為人們利用web信息提供了大量幫助。然而，隨著人們對web服務的種類和質量要求越來越高，基於整個web的信息採集也越來越顯得力不從心，一方面它們不得不為越來越龐大的數據提高採集速度、增加存儲空間、最佳化採集算法，而一方面又越來越不能滿足用戶對個性化數據的需求，人們需要尋找新的出路。目前採用的基於詞的語義信息理解顯然不能準確把握整個文章的語義，而要上升到對句子甚至段落信息的理解卻還有待於自然語言理解的大發展，現在這一方面困難重重；基於已有結構信息的挖掘(例如google的pagerank算法)也已基本達到飽和，很難有新的算法達到較大突破；而對於紛亂的web制定新的標準，減少不確定性以提高性能，這一方面的發展也不能寄予過高的期望；隨著web服務逐漸向基於主題以及用戶個性化的方向邁進、agent的技術發展、遷移式思想的出現，單純的為了檢索的信息採集技術必將向著基於主題以及個性化主動信息採集服務方向全方位拓展。因此，有必要開展基於主題的web信息採集技術的研究。
第四章 基於主題的web 信息採集基本問題研究
在本章里，我們主要圍繞基於主題的web信息採集基本問題展開了研究，這主要包括主題的web信息採集的定義、優點、分類，主題頁面在web上的分布特徵以及相關性判別算法，後兩者是本章的重點。它們為在下一章中提出我們設計的基於主題的web信息採集結構模型提供了必要的準備。
4.1 基於主題的web信息採集的定義
在web信息採集的大家庭中，有一類非常重要，它就是基於主題的web信息採集，在國外也叫做focused crawling。它主要是指選擇性的搜尋那些與預先定義好的主題集相關的頁面的採集行為。
4.2 基於主題的web信息採集的優點
和傳統的基於整個web的信息採集相比，基於主題的web信息採集是一個新興的領域，主要有以下幾個優點：第一，從很大程度上，它緩解了信息採集開放性難題刷新問題所帶來的弊端。整個web的實時性使得數據在採集到的同時就面臨著過時的風險，為了降低這種風險，信息採集器必須不停的對採集過的信息重新採集已達到對數據的刷新。刷新問題就是指在對頁面數據的刷新過程中，這種風險只能降低，不能消除。隨著web的急速膨脹，傳統的基於整個web的信息採集的刷新問題變得異常地尖銳。儘管人們不斷的提高單機的性能，通過分散式增加並行能力，通過算法最佳化刷新策略，但是刷新問題還遠不能令人滿意。許多門戶搜尋引擎查新一次需要數周甚至數月的時間。selberg和etzioni在1995年的調查發現，通過internet中最常用的一些搜尋引擎查詢到的結果url中，14.9%的目標頁面已經失效了[selberg &etzioni 1995]。而對於基於主題的信息採集，這個問題好處理的多。隨著採集頁面數量的極大降低，頁面的刷新周期極大的變短，因此數據過時的風險也就極大的減小了。
第二，它極大的節省了資源和提高了資源的利用率。整個web上的信息是十分浩大的，想對web整個採集或完全鏡像的採集器，先不說它們能否做到這一點，就其在採集過程中所使用的硬體資源和網路資源來說，花費是十分巨大的。事實上，許多採集到的頁面信息很少被使用，這是一個極大的浪費。而基於主題的web信息採集就是在採集過程中對url根據需要有所剪枝。這種採集剪枝，不僅使剪枝掉的url數目遠大於被採集的url數目，甚至差別是幾個量級的，還使得剪枝後採集到的頁面有較高的利用率。因此，這極大的節省了硬體和網路等資源以及提高了資源的利用率。
第三，它更靈活，更利於為用戶服務。採集的目的就是為了服務於用戶，對於每個用戶來說，他們根本不關心整個web上的數據，而只是其中很小的一部分。事實上，這部分數據往往集中在很小的幾個或者一個主題領域內。基於主題的web信息採集恰恰可以滿足這些用戶的需求，而且，由於採集的頁面數量少，頁面內容也更有針對性，所以能夠更好的針對需要為用戶提供服務。也正是由於採集的頁面數量少，系統更加靈活。
第四，通過各個基於主題的web信息採集器的協作和共同努力，它可以提高整個web的頁面採集覆蓋率。隨著www信息的爆炸性增長，信息採集的速度越來越不能滿足實際套用的需要。最近的試驗表明，即使大型的信息採集系統，它對web的覆蓋率也只有30-40%。解決這一問題的直接辦法是升級信息採集器的硬體，採用處理能力更強的計算機系統，然而這種方法的擴展性有限，性價比也不高。一個更好的解決放法是採用分散式方法來提高並行能力，但是並行不但增加了系統的開銷和設計的複雜性，並且並行換來的效益隨著並行採集器數目的增加而顯著的減小。而基於主題的採集，由於採集的頁面總數少，並且對於這個主題內的頁面挖掘能力更強，所以和傳統的基於整個web的信息採集器相比，它在這個主題內往往採集到更多更全面質量更好的頁面。當多個主題採集器按照主題分類目錄對主題頁面進行分類採集和協同工作後，他們的綜合採集頁面對web的覆蓋率也就更高了。
4.3 基於主題的web信息採集的分類
4.3.1 廣泛主題和具體主題的web信息採集
按照採集主題的範圍和規模，基於主題的web信息採集可分為廣泛主題的web信息採集和具體主題的web信息採集。
廣泛主題是指那些涵蓋面較寬，並且和其他主題相比有較強的獨立性的一類主題。廣泛主題的web信息採集也稱作領域web信息採集。用戶在採集這類主題時，往往並沒有太具體的要求。一般這類信息採集所需要採集的頁面數量較多，為了達到較高的召回率，在進行url過濾的時候所設定的閾值較低、限制較寬，因此它的頁面的內容相對於其它基於主題的web信息採集來說也相對較雜，採集頁面與主題的平均相關度也較低。
與之相對應，具體的主題涵蓋面較窄，因此意義也比較明確，採集頁面的規模也較小。這類採集一般可直接服務於用戶，為此，它在進行url過濾的時候所設定的閾值較高、限制較嚴。這類信息採集對用戶來說，更加靈活，對每個用戶有更強的針對性。在操作方式上，此類信息採集的設定有點像給搜尋引擎提交查詢詞。
如果按照主題分類目錄來劃分它們二者的話，廣泛主題往往集中在主題樹的根結點附近，而具主題則集中在主題樹的葉子節點附近。
4.3.2 固定主題和可變主題的web信息採集
按照採集時能否指定主題，基於主題的web信息採集分為固定主題的web信息採集和可變主題的web信息採集。
顧名思義，固定主題的web信息採集在採集前和採集的過程中都不能進行主題的變更。它一般是針對比較廣泛的主題，並且這類主題要有較強的代表性和採集價值。，這類採集一般服務於領域搜尋引擎，不直接服務於用戶。通過領域搜尋引擎的標引和加工，以類似於門戶搜尋引擎的服務方式提供給用戶。它的頁面內容比基於整個web信息採集的頁面內容有強得多的主題特性，因此領域搜尋引擎要比門戶搜尋引擎有更好的檢索效果。
可變主題的web信息採集是指用戶在採集前可設定採集主題、在採集過程中可改變主題的一種採集方式。這類採集往往設定的主題較具體，採集頁面的規模也較小，提供給用戶的操作方式比較靈活。另外，多個此類信息採集器進行合作，分別採集不同的主題，能夠完成一些更高級和複雜的服務。
4.4 主題頁面在web上的分布特徵
整個web上的頁面分布是雜亂無章的，但透過這個雜亂無章的表面，我們能否找到同一個主題在web上分布的一些規律呢？答案是肯定的。我們將這些分布規律總結為四個特性：hub特性、sibling/linkage locality特性、站點主題特性、tunnel特性。通過對它們的研究，我們希望能夠發現一些在基於主題的採集過程中對無關url和頁面過濾有用的規律。
4.4.1 hub特性
美國康奈爾大學的教授jon m. kleinberg發現web上存在大量的hub頁面，這種頁面不但含有許多outlink連結(指出連結)，並且這些連結趨向於相關同一個主題。也就是說，hub頁面是指向相關主題頁面的一個中心。另外，他還定義了權威頁面(authority)的概念,即其它許多頁面都認為相關於這一主題有價值的好頁面。好的hub頁面一般指向多個authority的頁面，並且所指向的authority頁面越權威hub頁面的質量也越好；反過來，hub頁面的質量越好，它所指向的每個頁面也趨向于越權威。根據這個思想，他還提出了hub/authority 算法，這個算法我們將在後面的章節中介紹。這個算法對於計算廣泛的和概念模糊的主題效果不錯，但由於算法會產生概念擴散現象，使得計算後的中心頁面和權威頁面不太適合具體主題。
4.4.2 sibling/linkage locality特性
在hub特性的基礎上，人們又提出了sibling/linkage locality特性[aggarwal et al. 2001]。1).linkage locality,即頁面趨向於擁有連結到它的頁面的頁面主題；2).sibling locality,對於連結到某主題頁面的頁面，它所連結到的其它頁面也趨向於擁有這個主題。這實際上是hub特性的變形，主要是從頁面的設計者設計的角度考慮的。一個頁面的設計者趨向於把本頁面指向於與本頁面相關的其他頁面。
4.4.3 站點主題特性
我們發現，一個站點趨向於說明一個或幾個主題，並且那些說明每個主題的頁面較緊密地在此站點內部連結成團，而各個主題團之間卻連結較少。我們認為，這主要與網站的設計者的設計思路有關。每個網站在設計時都有目標，而這種目標往往就集中在一個或幾個主題中。而網站的瀏覽者往往也有一定的目的性，這個目的性一般體現在用戶趨向於瀏覽同一主題的頁面。為了滿足瀏覽者的這一需求,網站設計者需要將相關內容緊密地連結在一起。
為了發現和研究站點內頁面的主題團特性，余智華對站點結構進行了分析[余智華 1999]，他通過基於關鍵字的向量空間模型算法為每個頁面分類，並在站點內部結構特徵的基礎上，對站點頁面樹按照自底向上進行主題聚類，這樣一個站點所要說明的一個主題或多個主題就確定了(如果聚為一個類，說明站點只有一個主題，如果聚為多個類，則說明站點有多個主題)。顯然，聚的每一個類就是站點內頁面的一個主題團。在聚類過程中，他要區別每個連結和頁面對頁面樹結構的貢獻，為此他為站點定義了兩種結構(物理結構合邏輯結構)，並且把站點內的連結分為六類(下行鏈、上行鏈、水平鏈、交叉鏈、外向鏈、框架鏈)，把站點內的頁面分為四類(主頁、索引頁面、內容頁面、參考頁面)，他為每一類連結和頁面在聚類過程中賦予不同的權重。我們的試驗也證明了站點中存在著許多主題頁面團，或者說許多中心頁面。
4.4.4 tunnel特性
在web中還有一類現象，就是儘管存在很多主題頁面團，但是在這些頁面團之間，往往需要經過較多的無關連結才能夠到達。這些無關連結就想一個長長的隧道一樣，連線著兩個主題團，因此我們也把這種現象叫做“隧道現象”。在基於主題的頁面採集過程中，tunnel的存在極大地影響著採集的質量。為了提高採集頁面的準確率，我們需要提高url與主題相關性判定以及頁面與主題相關性判定的閾值，而閾值的提高將過濾掉大量的tunnel，使得採集系統很可能丟失tunnel另一端的主題團，進而影響了查全率(或者說資源發現率)。反過來，為了提高查全率，就得大量發現tunnel,就得降低url與主題相關性判定以及頁面與主題相關性判定的閾值，但是閾值的降低使得在得到tunnel的同時，也混進了大量的其它無關頁面，從而大大降低了頁面的準確率。這是一個兩難問題，但關鍵還是不能有效地區別tunnel和其它大量無關頁面，事實上兩個主題團之間的隧道數也較少。為此，我們這樣設計算法：判斷某個連結和頁面與主題的相關性低於閾值時，給它一個機率p不被剪枝，為了提高tunnel的發現率，這個機率p值一般要大於tunnel出現的估計機率值；另一方面，我們對連結和頁面相關性判定的閾值進行動態的調整，當目前採集頁面的準確率較高時，將閾值變低，而當目前採集頁面的準確率較低時，將閾值變高，以使得能夠有效的在查全率和查準率之間有一個有效的折衷。詳細的算法在url與主題的性關性判定那一章里介紹。
4.4.5 四個特性的關係
web中的頁面對於主題來說是雜亂的，但也存在一些規律。hub特性說明了主題容易成團出現的現象，linkage/sibling locality特性進一步對成團的特徵有所擴展，站點主題特性說明了主題團所在的位置(即大部分分布於站點的內部)，而tunnel特徵說明了主題團在web 上的分布並不稠密，並且由較少的連結和tunnel連線。
4.5 相關性判別算法研究
基於主題的web採集系統最大的特點就是在採集的同時要對待採集的url進行剪枝、對已經採集的頁面進行過濾，而做這些事情的核心問題就是頁面、url與主題的相關性判別問題，為此，我們在這裡對於相關性判別算法進行了詳細的研究，它主要分為以下四個大類：1).根據元數據的判定；2).根據擴展元數據的判定；3)根據連結分析的判定；4).根據頁面內容語義判定。
4.5.1 根據元數據的判定(元數據演算)
4.5.1.1 元數據演算基本概念
元數據（metadata）是指關於數據的數據，關於信息的信息 [marchiori 1998]。人們在研究web信息檢索的早期就發現，利用元數據(metadata)來增加html的結構特徵對web信息檢索有幫助。因此，html 規範從2.0版本開始引入了<meta>這一tag [html30 1995][html32 1997]，用於為web頁面標註metadata，一般形式為：<meta name=“...” content=“...”>。
例如:
<html>
<head>
<title>my interests</title>
<meta name=”author” content=”li shengtao”>
< meta name =”description” content =”i love basketball game”>
< meta name =”keyword” content =”basketball,game”>
</head>
<body>
…
</body>
</html>
圖4.1 html中的元信息標註
圖4.1表示該頁面的作者為li shengtao，關鍵字是basketball和game,而對本頁面的描述是”i love basketball game”。這種元數據顯然對本頁面的主題有相當大的說明作用。
4.5.1.2 演算機制
元數據演算（又稱為meta演算）最初是海量信息、多媒體數據ir等中的技術, 今天日益成為web研究中的重要一支，並成為基於主題的web信息採集時剪枝的一個依據。meta演算的核心思想是構造一個比原始被標引數據結構化程度更好、更便於計算的中間層次（元信息層次），在此基礎上提供各種更加最佳化智慧型的服務。meta演算以web的異構性作為突破口，試圖藉助元信息引入結構性和有序性，從而提供更優質的檢索服務。它的機制主要是標引和演算，兩部分相互配合共同發揮作用。[馮國珍 2001]
4.5.1.3 標引
標引的目的是為演算提供比原始數據更加結構化的標引數據。標引工作的前提是制定一套標引標準，分為表現方式和標引工作方法兩部分。表現方式包括標引數據的格式、屬性、取值範圍、標準值、存放規範等；標引方法體現為對標引屬性和標準用值的含義解釋，取值規定，和具體流程等。
標引工作的進行過程是為被標引對象即原始數據確定適用的標引屬性並給出具體取值。這必須在理解的基礎上進行，是理解歸納的工作。在web這一套用環境中，標引的目的具體地包括消減自然語言的模糊性、歧意性，以及降維等，總之是在自然語言的基礎上改善規範化和形式化程度。
4.5.1.4 演算
metadata演算的目的是為了提供各種服務，因而隨著需求的不同具體計算方法千差萬別，但我們可以將metadata演算的基本模式抽象為：以結構化程度更高的標引數據為對象，結合用戶信息進行深度演算。metadata演算一般不是工程或科學計算，而是智慧型領域的服務，如主動推送信息，信息自動分類，信息檢索，主題制導採集等，強調對原始數據的歸納理解和人機互動的方式[馮國珍 2001]。
4.5.1.5 元數據的層次標準
標引的目的是構造比原始數據更加結構化、更加有序，便於計算的中間層，因此標引必須遵循一致標準。標準的制定是有關meta演算的國際組織的一項重要工作內容。meta標準可以分為以下三個層次：
l 元信息格式。即元信息書寫格式。html和xml都支持在頁面中直接標註元信息， xml對元信息的頁面標註支持方式結合rdf標註定義。[[rdf10 1999]]
l 元信息標準取值。這定義的是有哪些屬性的元信息，各屬性的標準命名；每個屬性有那些有效取值，每個取值用什麼標準符號表示。
l 演算模型。即基於元信息這一中間層次向上提供服務的計算模型。
為web頁面制定元信息標準是一項十分困難的任務，因為web所涉及的學科領域，語種，國家地域，文體都非常多，目前meta標準在第一層次基本取得成功，html和xml頁面中標註元信息的格式得到了各方的承認和執行。再向上，在第二層次，只就各種頁面都共有的最基本屬性的確定和命名制定了比較廣泛接受的標準，即doublin core(簡稱dc)[dc]，該標準定義了15個輔助web ir的標準屬性，如“author”, “abstract”, “date”等。進一步，雖然各學科專有屬性的確定以及各屬性有效範圍的確定存在不少提案，但沒有獲得普遍接受形式的標準。至於meta演算，由於套用於不同目的時相應採用不同的算法和技術，因此無法抽象出統一的演算模型[馮國珍 2001]。
4.5.1.6 基於主題的信息採集對metadata 演算的利用
通過以上分析我們發現，metadata演算的一套思路和方法，都是為了更加有效地支持web檢索而產生的，基於主題的信息採集的本質就是將搜尋引擎技術里原來放在採集數據之後的一些檢索技術套用到了採集數據的過程中，因此metadata演算對於基於主題的信息採集時的url過濾和頁面過濾是有用的。事實上，已經有一些系統嘗試使用meta數據來進行url預測。但是，元數據演算卻有一個致命的病源：這種減輕web上信息的弱結構性和異構性的方法，需要人們事先按照標準書寫html頁面，這增加了人們的頁面寫作代價，而人們在習慣了原來簡潔的方式後，很難遵從元數據標準。同時，對於不同的領域，ontology標準的制定也有所不同，實施起來也困難重重。因此，像許多搜尋引擎甚至領域搜尋引擎一樣，它在主題採集領域內套用並不多。因此，在我們的系統中，並沒有利用任何的元數據。當然，這並不說明此類方法沒有前途，隨著web的新一代語言xml的發展，meta演算也逐漸有了新的發展空間，但是，它需要人們對增加頁面結構信息的渴望付諸行動，也就是共同遵守metadata書寫協定，這需要時間。
4.5.2 根據擴展元數據的判定
4.5.2.1 基本概念
儘管目前元數據演算並不理想，人們卻發現利用其它html標記anchor等信息能夠有效的指導檢索和基於主題的信息採集。我們把這些標記信息統稱為html擴展元數據，相應的計算叫做擴展元數據演算。
4.5.2.2 html擴展元數據
在html頁面中，主要有4種超連結：1).anchor(<a>) tags；2).image(<img>) tags；3).map and area tags；4). frame and iframe tags。
archor標記是最常用的，主要包括name，title，alt，on-mouse-over和href等幾種屬性。而image標記則包括name，alt，src，dynsrc，lowsrc，onabort，onload和onerror等幾種屬性。對於map和area標記，它們的屬性與anchor標記基本相同。frame和iframe一般與frameset一起使用，共同對網頁進行分割。它們主要包括accesskey，align，application，bgcolor，frameborder，language，marginwidth，name，scrolling，src，style和title等屬性。
如果把頁面看作點，這些超連結看作邊，則web構成一個有向圖。直覺上，這些連結所含的信息對頁面的語義有重要的解釋作用。因此，我們對主要的連結屬性作了分析。
4.5.2.3 html擴展元數據類型在web中的分布
我們研究了一個超過10000頁的頁面集，目的是了解在web中，各個擴展元數據類型所占的比例。這個頁面集合是通過天羅信息採集系統按照隨機給定的種子頁面集採集的。所有的頁面共包含了超過90000個超連結，這些連結中即包含內部連結(此連結所指向的頁面仍然在這個頁面集中)又包含外部頁面(此連結所指向的頁面不在這個頁面集中)。
分布
類型
連結比例
頁面比例
href
86%
89%
anchor text
74%
78%
surrounding text
35%
52%
name
12%
19%
onmouseover
5.3%
9.6%
src
1.7%
4.2%
title
0.8%
2.3%
image text
0.5%
1.4%
map & area text
0.1%
0.3%
frame text
0
0
圖4.2 擴展元數據類型在web中的分布
在圖4.2中，列出了幾種有代表性的html擴展元數據類型，它既有超連結的屬性，也有超連結標記的文字。連結比例主要是指在所有的連結中，含某種html擴展元數據類型的比重(即用所有含此擴展元數據類型的連結數比上所有的連結數)，連結比例實際刻畫的是一個連結中含某種擴展元數據類型的可能性。頁面比例是指在所有的頁面中，含某種html擴展元數據類型的比重(即用所有含此擴展元數據類型的頁面數比上所有的頁面數)，頁面比例實際刻畫的是一個頁面中含某種擴展元數據類型的可能性。
因為一個連結或者一個頁面並不只含有一種html擴展元數據類型，所以，所有類型的連結比例和頁面比例分別加起來都超過了100% 。另外，由於一個頁面中通常包含多個連結，所以頁面比例一般都要比連結比例高。
試驗數據顯示，對於連結比例和頁面比例來說，類型都是按href，anchortext，surrounding text，name，onmouseover，src，title，image text，map & area text和frame text降序排列的。這個排列順序說明了整個web中的頁面和連結中html擴展元數據類型使用的比例。因此，我們在下面的算法中只要關注幾個比例較高的擴展元數據類型，就能夠把握整個擴展元數據對本這面中連結所指向的頁面主題的預測。
4.5.2.4 基於html擴展元數據類型的判定算法
這些算法是利用連結的擴展元數據來為每一個連結計算權值，在進行基於主題的信息採集時，優先採集權值高的連結，並對權值較低的連結進行剔除。整個擴展元數據類型可以分為3個大類：1).url（包括href，onmouseover，src等）；2).text(包括anchor text，image text，map&area text，frame text和surrounding text等)；3)title(包括title，name等)。根據這3個大類，我們設計了算法。這些算法包含url啟發式算法(url heuristics or uh)、text啟發式算法(text heuristics or teh)、title啟發式算法(title heuristics or tih)、擴展元數據啟發式算法(all metadata heuristics or amh)、相關性權重算法(relevance weighting or rw)和有提升的相關性權重算法(relevance weighting with boosting or rwb)[ysh 2000]。
4.5.2.4.1 url啟發式算法(url heuristics or uh)
在web中，如果一個url中包含某個主題詞，則這個url所指向的頁面很可能是跟這個主題詞密切相關的。比如這個url包含的內容就很可能是關於basketball的。因此我們定義計算公式：
公式4.1
直覺上，根據這個公式計算的值 如果為1，則這個連結所指向的頁面與主題相關的準確性很高，但算的值 如果為0，這個連結所指向的頁面與主題無關的準確性並不高。也就是說此算法給許多實際相關的頁面並沒有賦權值1。
4.5.2.4.2 text啟發式算法(text heuristics or teh)
在web中，如果anchor text，image text，map&area text，frame text或surrounding text等中包含某個主題詞，則這個url所指向的頁面很可能是跟這個主題詞密切相關的。比如<a href="content1.htm" >科研</a>包含的內容就很可能是關於“科研”。因此我們定義計算公式：
公式4.2
url的text指的就是此連結的anchor text，image text，map&area text，frame text或surrounding text，顯然，在一個連結中，這些text是不可能同時出現的。直覺上，同url啟發式算法類似，根據這個公式計算的值 如果為1，則這個連結所指向的頁面與主題相關的準確性很高，但算的值 如果為0，這個連結所指向的頁面與主題無關的準確性並不高。不過與url啟發式算法相比，它沒有賦權值1的相關與主題的頁面要少一些。
4.5.2.4.3 title啟發式算法(title heuristics or tih)
在web中，如果一個連結中的title包含某個主題詞，則這個url所指向的頁面很可能是跟這個主題詞密切相關的。比如<a href="; title="me scuba diving">me scuba diving last summer</a>這個url中，title包含的內容me scuba diving就很可能是關於這個url所指向的頁面的內容。因此我們定義計算公式：
公式4.3
4.5.2.4.4 擴展元數據啟發式算法(all metadata heuristics or amh)
將所有的擴展元數據綜合在一起，就得到擴展元數據啟發式算法公式：
公式4.4
其中a，b，c為3個大於等於零小於等於一的常數，用於控制每類擴展元數據在整體中的權重。顯然，0 1。
4.5.2.4.5 相關性權重算法(relevance weighting or rw)
另一種綜合所有的擴展元數據來計算權重的公式如下：
公式4.5
其中，m(url)指與此url相關的所有擴展元數據集合， 是指擴展元數據中的一個詞與主題的相關度。c為用戶設定的相關性閾值。此方法與amh算法最大的不同在於相關度的計算。amh方法是看擴展元數據中是否包含主題詞或者主題詞的同義詞，這樣會漏掉許多相關頁面；而rw方法則是看擴展元數據中詞與主題詞之間的相似度，同義詞之間的相似度100%，近義詞之間的相似度50%~100%,遠義詞之間的相似度0%~50%，這樣大大降低了漏判相關頁面的可能性，同時也增加了錯判相關頁面(不相關的頁面判斷為相關頁面)的可能性，它的相關與否是通過閾值來決定的(大於等於閾值為相關，小於閾值為不相關)。另外，rw算法需要增加一個詞語相關性詞庫。
4.5.2.4.6 有提升的相關性權重算法(rwb)
公式4.6
在web中，有時在某兩個相關於主題的頁面之間會有若干個不相關於主題的頁面存在，我們把這種現象稱為“隧道現象”。這樣在採集到前面一個相關於主題的頁面時，根據rw算法很容易將隧道及隧道後面的相關於主題的頁面拋棄掉。為了減少這種因為“隧道現象”而漏采相關於主題頁面的損失，對rw算法進行擴展，產生了有提升的相關性權重算法rwb公式4.6。其中t(url)表示包含這個url的文本，t指文本中的每個詞，c與前面一樣，為用戶設定的相關性閾值，d為用戶設定的提升閾值。p1，p2為隨機變數，它們在0和1之間變化。
它的原理就是當一個連結url的 值小於相關性閾值c時，隨機產生一個提升因子p1，當p1大於等於提升閾值d時，此url就獲得了一個重新評判相關性的機會，這次評判不只是用擴展元數據，而是用包含此url的整個頁面內容。當重新評判的值大於相關性閾值c時，則用此值，表明這個url連結到的頁面是相關的。如果重新評判的值仍然小於相關性閾值c，則給第三次機會，其值等於隨機產生的變數p2，由於p2可能大於相關性閾值c，所以此url連結到的頁面仍有可能被判斷為相關的。這兩次機會減少了rw算法的漏判(相關的頁面被判斷為不相關)和對“隧道現象”的錯判，但同時也增加了相關性頁面的誤判(不相關的頁面被判斷為相關)。rwb算法的另一大優點就是解決了“停滯現象”。它總能找到相關頁頁面，而不因為沒有相關頁面採集停滯。
4.5.3 根據頁面間連結分析的判斷
web是基於internet的超文本（hypertext）系統，超文本系統與普通文檔信息庫的最大區別就在於前者中存在著大量的超連結。研究表明，利用web中豐富的超連結（hyperlink）信息，可以挖掘出web中許多重要的信息，這些信息對進一步理解超文本語義以及提供給用戶更優質的服務有相當大的幫助。我們把這些研究超連結的工作稱為連結分析，或叫做結構分析（structure analysis）。
連結分析的研究思路基於這樣一個假設：即把超連結看作是對它所指向的頁面的讚許[chakrabarti 1999]。在這樣的假設之下，當頁面a通過超連結指向頁面b時說明兩點：1).頁面b與頁面a的主題是有關的；2).頁面b是質量較好值得關注的頁面。單個連結並不是完全可靠可價值判斷，因為超連結中也有純粹起導航作用的（如“主頁”，“下一頁”），或者是廣告連結，或表示不贊同（“我不同意這個觀點”），或者是為了某種目的的欺騙性連結。不過，從巨觀總體上來看，web上整個連結集合所反映的情況則是比較可靠和準確的，因為不良連結的整體效應遠沒有重要連結的整體效應強。當然，為了有效和準確的評估連結，在進行具體的算法分析之前需要識別和去除 “噪音”連結，這也是許多連結分析算法的共同特點。
如果將頁面看作頂點，連結看作有向邊，整個web就可以看作是一個有向圖，稱為web圖（web graph），可以用複雜網路理論來進行研究和分析。在上述背景下，通過連結對web的研究可以分為以下三種類型：1).對web巨觀性質的研究，比如說通過每個頁面的出度和入度數來研究web中團的直徑和web的巨觀結構。這類研究往往用生態學（ecology）和社會學（sociology）的規律來來揭示web的發展。2).對web中單個頁面的性質的研究。就像經濟社會一樣，有巨觀問題，也有微觀問題，web中的每個頁面的作用是不相同的，有些頁面非常重要和非常有權威，很多人都關注它，而有些頁面則是垃圾，除了浪費被騙人的時間外，幾乎沒有任何存在的意義。現在比較好的計算頁面重要程度的方法為pagerank算法和authorities/hubs算法，我們將在下面的章節中詳細介紹。事實上，對web中單個頁面的性質的研究非常使用，許多搜尋引擎都採用了pagerank算法和authorities/hubs算法，以提高檢索結果的準確性。3).對web隱藏信息的挖掘。現在，仍然有許多可用的web信息沒有被挖掘出來，比如說有關共同話題的頁面“社區”的問題[kumar (1) 1999] [kumar(2) 1999] [mendelzon 1995] [mendelzon 1997]，這些問題的解決有待於對web隱藏信息的進一步挖掘。
4.5.3.1 相關度和重要度
4.5.3.1.1 相關度
在搜尋引擎技術中，相關度是個重要的概念。它描述了檢索結果和檢索請求之間的相關程度。相關度的計算方法有很多，但每一種方法基本上都是定量地計算檢索請求與檢索結果之間的語義關聯程度，並且根據這種關聯程度的數值高低排列搜尋引擎返回給用戶的結果。與之類似，基於主題的web信息採集的相關度是指頁面或連結和主題之間在語義上的相互關聯程度。
事實上，搜尋引擎的這種排序後的返回結果並不令人滿意。原因除了由於相關度計算方法的誤差導致的排序錯誤外，還主要有一點：相關度不太高的頁面不一定質量不高，相關度很高的頁面不一定有高的質量。比如，一個文本對於一個主題來說，可能並太相關，但卻出自一個權威作家之手，它有相當高的有用信息量；而另一個文本對於這個主題可能是非常相關的，因為它討論的確實是這個主題，但是，這個文本由於出自一個初學者之手，只包含很少的有用信息量；更有甚者，一個質量較差的網頁的作者，由於了解搜尋引擎的工作方式，利用在網頁中大量重複重要關鍵字的做法，提高它在搜尋引擎檢索中的相關度。實際上，用戶需要的不只是語義上最相關的頁面，而且是用途上質量高的頁面，也就是說，是相關度和質量因素綜合較高的頁面。為此，信息檢索的研究者們提出了另一個重要的衡量指標——重要度。
與信息檢索情況類似，基於主題的web信息採集在進行主題相關性判定時也面臨兩個衡量指標。需要最先採集的連結，一方面，要在語義上與主題十分相關，另一方面，它要有較高的權威性和質量。這種權威性和質量往往能夠使得採集到頁面具有較大的有用性和較高的發現其它高相關度頁面群的能力。我們在評價基於主題的web信息採集系統url預測方法時，也提出了另一個衡量指標——重要度。
4.5.3.1.2 重要度的概念
在信息檢索中，重要度定義為：檢索結果中，某文本的相對重要程度[楊志峰 2001]。我們在此處對重要度進行擴展：在一個文本集合中，某文本的相對重要程度。重要度刻畫的是一篇文本實際的質量和有用性，相關度則刻畫一篇文本和一個主題或者查詢在語義方面的相聯程度。儘管從統計概念的角度說，它們之間有較強的相關性(也就是說，統計上頁面表現出來的規律是：重要度高的頁面很可能相關度也高，反之，相關度高的頁面很可能重要度也高)，但從實際意義上看它們並無太大聯繫，只是從兩個不同的角度對本頁面的評價。一個不太恰當的比喻是馬克思對商品的看法：商品是價值和使用價值的統一體。在這裡，我把相關度比作價值，重要度比作使用價值，二者相關，但也有很大的不同。
計算頁面相關性的方法絲毫不能評估頁面的重要性，那么我們如何得到對頁面重要性的評估呢？連結分析給我們指明了道路。事實上，整個web上的指向頁面的連結數恰恰反映了頁面的可用程度和質量，也就是頁面的重要度。如果一個頁面質量好或可用程度高，那么就會有很多頁面指向它，如果一個頁面不好或可用程度低，就只有很少的頁面指向它。這說明連結關係不僅僅反映了頁面的重要度，還因為排除了個別用戶或臨時行為的干擾而使得這種重要度有較強的可信度。
因此人們用連結分析算法來評估頁面的重要度，流行的算法有pagerank和authorities/hubs算法，在後文我們設計的基於主題的ipagerank算法，就利用了重要度的概念。
4.5.3.2 pagerank算法
pagerank是著名搜尋引擎google的一個重要檢索算法，它有效的幫助搜尋引擎識別那些重要的頁面並且將它們排在檢索結果的前列。google是美國史丹福大學計算機科學系研究開發的一個大型搜尋引擎。它的設計目標，是提供千萬頁面級的搜尋引擎，每天可以應付數以百萬計的查詢請求，並且，最重要的是提供了相對令人滿意的檢索結果。
4.5.3.2.1 pagerank函式定義
world wide web上的無數頁面互相連結，構成了一個巨大的連結有向圖。也許是受論文引用排名的啟發，google的設計者們發現這個有向圖中包含了非常有用的引用信息，而這種資源以前從未被人注意過。
設計者的思路是：被別人大量引用(也就是被連結)的網頁，一定是好網頁。從這個觀點出發，他們構造了以下的基本公式：
給定一個網頁a，假設指向它的網頁有t1，t2，…，tn。令c(a)為從a出發指向其它網頁的連結數目，pr(a)為a的pagerank，d為衰減因子(通常設成0.85)，則有
公式4.7
設計者聲稱，pr(a)可以用簡單的疊代算法進行計算；在一台中等規模的工作站上，2600萬個網頁的pr函式值可以在幾小時內完成。
4.5.3.2.2 pagerank的直觀解釋
假設web上有一個隨機的瀏覽者，從一個任意給定的頁面出發，從來不執行“back”操作，按照頁面上的連結前進，我們假設瀏覽者選擇本頁中任意一個連結前進的機率是相等的。在每一個頁面，瀏覽者都有可能不再對本頁面的連結感興趣，從而隨機選擇一個新的頁面開始新的瀏覽。這個離開的可能性設為d。這樣，pagerank(即函式pr(a))就是它訪問到本頁面a的機率。因為用戶是趨向於瀏覽重要頁面的，所以這個機率就反映了此頁面的重要程度。從直觀上看，如果有很多頁面指向一個頁面，那么這個頁面的pagerank就會比較高；如果有pagerank很高的頁面指向它，這個頁面的pagerank也會很高。這樣，從“隨機瀏覽者”模型出發的pagerank函式就在直觀上同web上的實際情形相對應了。
4.5.3.2.3 對pagerank公式的修正
從隨機瀏覽者解釋思路看，公式8.7的形式是不準確的。有人認為應該修正為以下形式[楊志峰 2001]：
公式4.8
公式中，(1-d)(pr(ti)/c(ti))代表隨機瀏覽者從頁面ti進入頁面a的機率，所有機率值相加得到隨機瀏覽者從某個連結進入頁面a的機率；d/(ctotal-1)代表隨機瀏覽者離開當前頁面，隨機開始一個新頁面，從而選中頁面a的機率。這兩個機率相加，即得到進入頁面a的總機率。
因為d/(ctotal-1)約等於0，所以我們認為公式4.7中的d並不表示隨機瀏覽者離開當前頁面的選擇一個新頁的機率，而只是起到調高pr(a)值以便計算的作用，實際公式中的d/(ctotal-1)由於為0已被省略了。
4.5.3.3 權威中心頁面算法(authorities/hubs)
4.5.3.3.1背景
該算法主要在ibm的almaden研究開發中心研製的clever系統中實踐和套用。他們認為，web頁面的數量正呈指數形增長，但人們可以接受的信息數量幾乎保持不變。因此，沒有必要把所有的頁面都進行索引、分類以供檢索。他們的目標是主題提取(topic distillation)：給定一個覆蓋面比較廣的主題，篩選出這個主題下面質量最高的一小部分web頁面。
clever系統把連結分析的深度又提高了一層。在這個系統中，首次提出了兩個重要的概念：hubs和authorities。從這兩個概念的名稱可以推想到，authorities是重要的頁面，hubs就是指向眾多重要頁面的中心點。
hubs和authorities之間是相互加強的關係。一個好的hub必然指向許多好的authorities，一個好的authorities必然被許多好的hub連結。當然，一個頁面可以同時是hub和authorities。
4.5.3.3.2 權威中心頁面算法(authorities/hubs)
下面是clever算法的示意性算法描述。
1. 用戶給定一個查詢以後，clever把它提交給一個通用的基於關鍵字查詢技術的搜尋引擎，例如altavista。從這個搜尋引擎返回的結果稱為基本集(initial set)。基本集不超過200頁。
2. 向基本集中增加頁面。被增加的頁面必須或者是基本集中的頁面所連結的頁面，或者是它們連結到基本集中的頁面。擴展後的頁面集合稱為根集(root set)。
3. 對根集中的每個頁面p，賦給兩個權值：a(p)，代表authority權值；h(p)，代表hub權值。它們初始值設為1。
4. 疊代計算每個頁面的權值。
a) 對於頁面p，令 ，其中qi為頁面p連結的頁面。
b) 對於頁面p，令 ，其中ri是連結到頁面p的頁面。
5. 重複執行若干次疊代，每次疊代後進行規格化。
最終，取a(p)最高的頁面為最好的authorities頁面，取h(p)最高的頁面為最好的hubs頁面，每個頁面的authority值就是這個頁面的重要度。從算法中我們可以得知：根據authorities/hubs算法得到的權威頁面是基於主題的，也就是說得到的權威頁面是這個主題的權威頁面。但由於根集中擴展進了許多主題相關性較低的頁面和算法初始化各個頁面的authorities值相同(都為1)，這個算法一般只適用於較廣泛的主題。
4.5.4 根據頁面語義信息的判定
最好的判斷url和頁面與主題的相關性方法還是要基於語義的理解，儘管這樣做往往要花費更高的時空代價。目前，判斷文本和主題相關性的方法仍然是基於關鍵字的，主要有以下幾種方法：全文本掃描，布爾模型，擴展布爾模型，向量空間模型，機率模型。它們都是ir領域裡經典方法。
4.5.4.1 全文本掃描
對於檢索來說，要檢查某個檢索串的位置，最簡單有效的辦法恐怕是全文檢索，也就是從頭到尾掃描手中掌握的文本，檢查這些串是否存在於其中。相應地，要判定是否頁面與主題相關，最簡單的方法也是全文掃描，在進行分詞、去除停用詞、詞根還原（stemming）等簡單的預處理之後，看看主題中的關鍵字是否都在本頁面中出現，如果出現則相關，否則不相關，出現的頻率越高，則相關度越大。
如果系統支持帶正則表達式的查詢，那么情況會複雜一些，需要判斷文本中的字元串是否符合指定的模式。一般來說，可以構造一個和正則表達式對應的有限自動機，用它檢測字元串是否滿足要求。
全文本掃描的優點，在於這種方法非常簡單，不需要預先對文本進行處理，不需要耗費空間存儲索引，自然也不需要花代價維護索引。它的缺點在於，這是一種非常低效的方法，任何字元串的查找都要遍歷所有的文本。不僅回響時間太長，而且極其耗費cpu時間和磁碟io時間。所以不適合大規模套用。但是，如果數據量不大，全文本掃描不失為一種有效的簡便方法。
4.5.4.2 布爾邏輯模型
該模型構成了幾乎所有信息檢索和資料庫系統的基礎，直到今天仍然如此。採用這種模型的檢索系統，用戶查詢詞用布爾操作符“與”（and）、“或”（or）、“非”（not）進行連線，系統則返回滿足上述詞項組合的文檔[cooper 1988]。對於判定頁面與主題的相關性來說，將主題表示成若干個關鍵字並用布爾操作符相連，然後與頁面進行相關性判定，一般可採用全文掃描的方法。
4.5.4.3 擴展布爾模型
圖4.3 p-norm模型
經典的布爾邏輯模型的最大缺點是只有0和1，沒有ranking。也就是說只要整個布爾表達式中只要有一處不符合，則不相關；都符合，則相關。這種判定方式顯然十分僵化：在or方式中，包含很多主題詞的頁面和包含少數詞的頁面在與主題的相關度上是等同的；在and方式中，即使缺少一個詞，結果也是false，等於一個詞也沒有。為此建立了擴展布爾模型，在各種擴展中，p-norm模型的運行結果是最符合實際的。
如圖4.3所示，當p=infinity時，p-norm模型等同於classical boolean模型，當p較低時（如在[2,5]內），and方式中一個權值低的詞會使總體值大大降低，or方式中一個權值高的值會使總體值大大提高。當p=1時，變成向量空間模型(vector space model)，and和or方式實際上相同，公式變為cosine similarity。當p-norm可以得到更大的靈活性。用戶可以指定某個子表達式的p值，例如一個較大的值表示對它要求比較嚴格。
4.5.4.4 向量空間模型
進行主題詞和頁面內容相關性的計算過程，實際上也是一個對頁面進行分類和聚類的過程。salton 等人於60年代末提出了向量空間模型 vsm (vector space model) 的概念，即使用向量表示文本或頁面。
向量空間模型的基本概念可以描述如下：1).文檔：泛指一般的文本或文本的片段（段落、句群或句子），一般指一篇文章。儘管文檔可以是多媒體對象，但在我們的討論中假設為文本對象，並且對文本和文檔不加以區別。
2).項（特徵項）：文本的內容由一些特徵項來表達，一般由文本所含有的基本語言單位（字、詞、詞組或短語等）來表示，即文本可以表示為 ，其中， 表示各個項。換句話說，由這些項張開了一個向量空間，每個項表示一個維度。
3).項的權重：在一個文本中，每個特徵項都被賦予一個權重 w，以表示這個特徵項在該文本中的重要程度。權重一般都是以特徵項的頻率為基礎進行計算的，比如採用 tf-idf 公式表示等等。這樣文本就表示為： ，簡記為 ，這時我們說項 的權重為 ，其中 。
4).向量空間模型（vsm）：給定一自然語言文本 ，由於 在文本中既可以重複出現又應該有先後次序的關係，分析起來仍有一定的難度。為了簡化分析，可以暫不考慮 在文本中的先後次序並要求 互異（即沒有重複）。這時可以把 看成一個 n 維的坐標系，而 為相應的坐標值，因此一個文本就表示為 n 維空間的一個向量，我們稱 為文本 d 的向量表示或向量空間模型。
5).相似度度量：兩個文本 和 之間的相關程度常常用它們的相似度 來度量。在向量空間模型下，我們可以藉助向量之間的某種距離來表示文本間的相似度。相似度常用向量之間的內積來計算：
公式4.9
或用夾角餘弦表示：
公式4.10
在向量空間模型的框架下有許多算法，例如，貝葉斯算法、k-近鄰算法、類中心向量最近距離判別法、支持向量機等等。
4.5.4.5 機率模型（probabilistic model）
文檔與查詢相關的機率這一概念很早便由maron和kuhns引入信息檢索領域[maron 1960]。其核心思想是將ir系統的主要功能看作是把集合中的文檔按與用戶信息需求的相關度機率降序排列。但是直到70年代中期，機率排序思想才逐漸進入實踐領域，並開始蓬勃發展起來[robertson 1977]。
前面介紹的幾種信息檢索模型中都是將文檔表示詞條視為相互獨立的特徵項，忽略了詞條間的關聯性，而機率模型則考慮到詞條、文檔間的內在聯繫，利用詞條和詞條間的機率相依性進行檢索。它使用機率推理網路進行文檔表示和檢索。機率推理網路模擬人腦的推理思維，將文檔內容與用戶查詢匹配的過程轉化為一個從文檔到查詢的推理過程。基本的文檔檢索推理網路包含文檔網路與用戶查詢網路兩個部分，如圖4.4所示。
圖4.4 機率推理網路
圖4.4中每個節點表示一個文檔、一個查詢或者一個概念，其中 為文檔節點， 為文檔表示節點， 為文檔概念節點， 為用戶查詢概念節點， 為用戶查詢節點，有向邊表示節點間的機率相依性。網路中文檔節點與查詢節點間的相關性可以表示為：給定文檔節點與查詢節點的條件機率就可以計算出查詢節點的後驗機率，如要估算用戶查詢 與文檔 間的機率相關性 ，先將文檔節點 置為true，然後依次計算 的相依節點的機率即可[徐澤平 2001]。
在判定主題與頁面的相關性過程中，只要把頁面看作文檔，把主題看作查詢，則可用機率推理網路進行計算。
第五章 基於主題的web 信息採集系統模型及我們的對策
5.1 系統模型
基於主題的web信息採集技術在套用需求的推動下，已經成為一個熱門的研究課題，為了更好的研究這個課題，我們設計了一個基於主題的web 信息採集系統模型，如圖5.1所示。為實現對基於主題的信息自動採集，我們將整個處理過程分成五大模組：主題選擇和初始url選擇、spider採集、頁面分析、url與主題的性關性判定(連結過濾/連結預測)、頁面與主題的性關性判定(頁面過濾)。下邊簡要地說明整個系統模型中的關鍵問題，在後續幾章里，我們將詳細討論各個模組的算法及實現。
5.2 模型中的關鍵問題及我們的策略
5.2.1主題的選擇
為了有效的進行剪枝和採集，基於主題的web 信息採集所要解決的一個重要問題就是主題選擇問題。針對隨便的主題詞可能較大地影響採集效果，系統一般提供給用戶一個主題分類目錄以供選擇。為了有效地確定用戶選定主題的含義，用戶要提供對主題的進一步描述，比如提供若干表達主題含義的文本，當然系統也會提供一些主題文本供用戶選擇。我們的系統就是按照中國圖書館的分類方法的第一級目錄和二級目錄對主題進行分類的，並在每個主題下配備了一些主題文本，以供用戶選擇。
5.2.2 採集起點的選擇
一般採集器是從一個種子url集出發，通過web協定向web上所需的頁面擴展的。基於主題的web信息採集也不例外，也有一個起始採集的種子url集。但是，基於主題的web信息採集的採集起點選擇卻必須十分慎重，因為這將影響著採集的效率，尤其是剛開始採集的準確率。
基於web上的linkage/sibling locality特性，一般採集系統需要選擇質量較高的主題url作為初始種子url集。為此，我們採用我們自己設計的小金手元搜尋引擎為每個主題搜尋頁面，搜尋排名前50的url作為每個主題目錄下的種子url。用戶在設定主題採集時可以在這50個url中進行選擇，也可以將自己知道的好的主題url輸入進來，以提高採集的效果。
而更高級的初始url的選擇方法是根據用戶興趣制導的，這需要有一個初始的用戶興趣檔案，這個檔案可以由用戶填寫的興趣和用戶瀏覽器中的書籤&收藏檔案產生。這部分的研究也屬於基於用戶興趣的採集。
圖5.1 系統模型
5.2.3 spider採集
這個部分處於系統的底層，也叫“網路蜘蛛”，是系統專門與具體的web打交道的部分。主要通過各種web協定來自動採集internet上www站點內有效的信息（包括文本、超連結文本、圖象、聲音、影像、壓縮檔等各類文檔）。這些web協定包括http、ftp以及bbs，還根據用戶的需要採集了web chat、icq等特殊信息。這個部分主要對應於在第二章中介紹的web信息採集系統的基本結構中的“協定處理器”部分。
5.2.4頁面分析
在頁面採集到以後，我們要從中提取出連結來，然後根據連結與主題的相關性判定來過濾與主題無關的連結，接受與主題相關的連結並進行下一步的採集；為了有效的進行連結與主題的相關性判定，我們也要分析出頁面連結中的擴展元數據(這個概念我們將在以後的章節中具體介紹)來；再者，為了進行頁面與主題的相似度判定，我們也必須提取出頁面中的正文和關鍵字來；為了其它操作的處理，我們也要進行對頁面內容標題、摘要等的提取。所有的這些就是頁面分析的內容：連結的提取、元數據的提取、正文的提取、關鍵字的提取、標題的提取、摘要的提取。它們的詳細提取算法我們將在後文的相應章節中介紹。
5.2.5 url與主題的相關性判定(連結過濾/連結預測))
為了有效的提高基於主題的web信息採集的準確率和效率，系統需要對“待採集url”進行url與主題的相關性判定，也可以叫做連結過濾或連結預測。按照高預測值優先採集、低預測值(小於設定閾值)被拋棄的原則進行剪枝處理。這樣可以大大減少採集頁面的數量，有效的提高主題信息搜尋的速度和效率。這個問題是本類採集系統的重要問題，也是本文論述的一個重點，我們將在下面相應的章節中通過大量的算法分析詳細剖析這個問題。
5.2.6 頁面與主題的相關性判定(頁面過濾)
為了進一步提高採集頁面的準確率，需要對已採集的頁面進行主題相關性評價，也就是頁面過濾。通過對評價結果較低的頁面(小於設定的閾值)剔除，來提高所採集主題頁面的準確率。這個問題是檢索領域內的一個經典問題，已經有許多成熟的基於關鍵字的相關性判定算法。我們採取的方法就是基於關鍵字的向量空間模型算法。
5.2.7 數據存儲
主要有三種資料庫需要存儲，它們是主題頁面庫、全局url佇列和中間信息記錄庫。主題頁面庫主要存放採集器採集過的並經過頁面過濾處理後的主題頁面。全局url佇列則是存放從採集到的頁面中提取出來的url的地方，這些url在進入url佇列前必須經過url預測處理，只有被預測為指向主題相關頁面的連結才能進入全局url佇列。在插入佇列時，也要根據url與主題的預測相關性的大小排序，相關性越高，排序越前。為了有效的進行url與主題的性關性判定和頁面與主題的相關性判定流程，顯然需要許多中間處理結果，比如使用ipagerank算法時每個頁面所擁有的ipagerank值，所有的這些中間數據，保存在中間信息記錄庫中。
第六章 主題選擇
在我們講基於主題的採集的時候，並沒有完全弄清楚一個問題——什麼是主題。針對可變主題的信息採集系統，就像用戶利用搜尋引擎為自己服務時必須正確地選擇查詢詞一樣，我們必須有效的進行主題選擇，這樣才能採集到我們真正需要的主題頁面。本章在對主題和主題分類目錄作了詳細的說明後，給出了我們的主題選擇策略。
6.1 主題的定義
一個主題就是一個“含義”，或者叫一個“概念”。它可以是一個詞，也可以是一個短語，甚至是一個段落，一篇文章。這個“概念”的範圍可大可小，大的時候可以非常廣泛，但此時它的意義也非常模糊；小的時候它可以非常狹義，而這時它的意義卻非常具體。因此，基於主題的採集系統採集的頁面數量根據主題概念的大小有很大的變化。
6.2 主題分類目錄
圖6.1 中國圖書館分類法
一般的搜尋引擎返回給用戶的結果不令用戶滿意的一個重要原因是系統獲得查詢關鍵字並不足以反映用戶的需求，這很大程度上是因為關鍵字選擇得不合適。基於主題的信息採集也面臨著主題選擇的困難。現實中的主題範圍太廣泛，雜亂無章，混亂無序，有些主題沒有實際用途上的意義(比如，“如果，和”)；而有些主題又幾乎不能引起人們的採集興趣(比如，“跑”)。為此，有必要對主題進行統一的分類。這不光有利於固定主題的信息採集系統選擇合適的主題範圍和主題角度進行採集，而且還為多個此類採集系統聯合採集更大範圍的主題頁面提供了有效的依據，還可以將主題分類推薦給可變主題採集系統前的用戶，使他們的選擇更加明智。
目前，很多基於主題的採集採用yahoo主題分類目錄，當然也可以是其它分類目錄，但所選擇的分類目錄應該分類比較合理，並具有一定的權威性。圖6.1給出了中國圖書館分類法的第一級目錄對整個主題進行的分類。
當然，這些基於主題的信息採集系統，在提供給用戶主題分類目錄的同時，仍然允許用戶自由輸入主題，以提高系統的靈活性。
6.3 web上的主題分類目錄的特點
web上有許多分類目錄（directory）站點，如yahoo!，yellow pages。一般有以下特點：
l 基本是樹形結構。每個節點（葉節點除外）有數量不等的若干子節點。少數節點有不只一個父節點，因此不構成嚴格的樹結構。節點依據知識本體論(knowledge ontology)劃分。分類目錄站點的主頁一般只顯示一、二級節點。
l 節點命名。每個節點有一個簡短的命名。非根節點的全名是從根到該節點的路徑上的所有節點的名稱的順序組合，如business_and_economy/companies/travel/ agents。
l 節點內容。每個節點收集有若干url，除了葉節點之外，每個節點有若干子節點。
l 維護。分類目錄的維護一般是人工進行的，由分類目錄站點僱傭專人分別負責各個子類，不斷跟蹤web上的信息，這是大多數站點的主流做法。另一類做法是由志願人員維護，個別站點可以有用戶自己定製子樹。
web上主題分類目錄的這些特點決定了系統提供給用戶的是一個可層層深入的樹狀主題結構圖。
6.4 主題選擇策略
在本節里我們討論的主題選擇主要是針對可變主題的信息採集系統。從前文我們已經知道，一個主題可以是一個詞語，一個句子，甚至一個段落。為了讓用戶能夠有效的表達主題採集要求，採集系統一般要提供給用戶一個主題分類目錄，用戶可以通過它選擇一個最適合的主題進行採集，這個主題可以是樹根、樹枝，也可以是樹葉。
為了增加相似度判定時候的有效性，系統還必須為每個主題提供一定數量的最能表達主題概念的樣本文本，通過提取這些文本的特徵，系統定量的掌握主題的含義。同時，為了體現對用戶的針對性，系統允許用戶對樣本檔案進行選擇。
為此，用戶可以在三個方面進行採集主題的選擇：首先，用戶在主體分類目錄中尋找自己所要表達的主題；其次，對系統提供的樣本檔案進行選擇，以使得它們能夠完整的準確的表達自己的主題需求；第三，如果系統提供的主題選擇文本不能全面完整的刻畫自己的主題需求，或者主題分類目錄中根本沒有自己所需要的主題，則用戶必須自己輸入主題詞和主題樣本檔案。這是和一般搜尋引擎的關鍵字輸入不同的。和關鍵字相比，主題詞用更加定量的方法來描述，一般刻畫的意義更準確、更全面，刻畫手段更靈活、更方便。
第七章 spider採集
信息採集系統的最前沿就是與internet相連的spider採集，也叫“網路蜘蛛”，是系統專門與具體的web協定打交道的部分。主要通過各種web協定來自動採集www站點內有效的信息（包括文本、超連結文本、圖象、聲音、影像、壓縮檔等各類文檔）。這些web協定包括http、ftp以及bbs，我們還根據用戶的需要，採集了web chat、icq等特殊信息。本章先就spider結構作了一個簡要說明，然後詳細論述了我們的相關算法。
7.1 spider的系統模型
如圖7.1所示，為了能夠高效地採集頁面數據，我們在spider系統中採用了client / server結構。 “網路蜘蛛”由一台或多台spider構成，它們通過內部通信，由信息伺服器統一管理並協同工作。由於spider的效率受採集平台、網路性能等諸多限制，為了達到比較理想的採集速度，我們採用了用多個spider同時並行採集的策略。具體並行的spider個數需要根據實際的採集速度要求和網路環境而定。
顯而易見，採用伺服器/採集器的結構使採集系統具有很好的可擴展性。管理員可根據系統採集規模的變化動態地調整採集器的數量，在保證系統性能的前提下儘量減少系統開銷，達到最佳的性能/價格比。而且在規模動態變化的過程中，系統能維持一致的管理和數據輸出接口。
我們這裡所說的信息伺服器主要負責對全局url佇列中的url進行分發、對採集到的頁面信息和檔案信息進行快取和壓縮以及在採集過程中的一些協調和控制。這一部分所要處理的一個中心問題就是url的分配策略，以便能夠快速的有效的利用多個spider共同高效採集。為了實現的簡單性，我們採用了輪轉法進行分配。並且當某個spider沒有待採集的url時，它也會主動向url分發器傳送url請求。
每個spider的任務就是將信息伺服器分配給它的url按照到來的先後順序插入到自己的url佇列中，然後不停的從隊首取出url進行採集，直到自己的url佇列為空。另一種url入隊的方法是根據url的主題相關性評分高低插入自己的url佇列(評分最高的放在隊首)，但插入佇列的時間代價和入隊時的互斥操作都會影響採集的效率，而此方法換來的好處“更加優先的採集評分更高的頁面”也並不太影響最終採集頁面的質量。因此， 我們選擇了前者這種簡單的方法。為了提高進一步的採集效率，在每個spider上我們採用了多執行緒方式。
7.2 採集算法及實現
7.2.1 url的調度策略
為了提高分散式採集的效率，一般常用兩種調度策略：靜態調度和動態調度。
靜態調度相對比較簡單，它並不看採集器當時的負載情況，而是按事先的決策進行頁面的分配。目前，主要有三種方法。1).輪轉法，即將待採集的頁面依次分配給n個採集器，直觀上看，每個採集器被分配了相同的採集頁面數，但是由於每個頁面的連線時間不同，頁面的大小也不同，尤其在複雜多變的網路環境下，分配不均衡幾乎是不可避免的。2)加權輪轉法，針對剛才提到的輪轉法的缺點，將導致分配不均的主要因素網路連線時間長短作為權值，來引導輪轉。一般來說，初始採集很難知道頁面連線的時間長短，所以此時不能用加權輪轉法，但由於網路中大部分網站在一段時間內的平均連線時間變化不大，因此在刷新的時候可以用加權輪轉法，試驗說明此時加權輪轉法好於輪轉法。3).隨機選擇法，假設每個頁面的採集時間滿足指數分布，每個採集器的處理能力為c1,c2, … ,cn ，則以機率 / k=1,2, … , n 為採集器k分配待採集頁面。當每個採集器的處理能力相同時，則對每個採集器按機率為1/n分配頁面。
實際的web是異構的、無序的和複雜的，檔案格式各式各樣，網路狀況也隨時間變化莫測。採用靜態調度策略，並不考慮web當前的負載情況這一重要信息，結果常常難以令人滿意。相應的，根據當前的負載情況進行調度的策略稱為動態調度，這是一種更加智慧型化的方法，但算法往往比較複雜，維持此方法的系統開銷也較大。主要有以下幾種方法：1). 最低負載法，即將頁面總是分配給當前負載最低的採集器。這個算法的問題在於：收集各個採集器的當前負載會導致額外的開銷，並且過時的信息可能導致誤判。2).pick-2方法，在這種複雜的環境中，與其增加大量的開銷以跟蹤負載，倒不如簡單的增加選擇的隨機性以模擬環境的隨機性。事實上，這樣反而會改善整個系統的性能。pick-2方法就是這樣一個例子，它是指隨機的選擇兩個採集器，並選擇負載較低的一個採集器分配頁面。同理，pick-k就是隨機的選擇k個採集器進行比較，當k=n時，pick-k方法就退化成最低負載法了，當k=1時，pick-k方法就變成了我們前邊說的隨機分配法。mitzenmacher對pick-k進行了實驗分析，他認為在大多數情況下，k=2是較好的選擇[馬曉星&呂建]。
對於我們的系統來說，首先這是一個試驗系統，試驗的重點並不是分散式，而主要是測試頁面和url的過濾算法和系統的整體工作運轉情況；其次，我們系統中所並行的各個spider的環境較相似(網路環境和機器性能)，所以我們選擇了較簡單的輪轉法。
7.2.2 每個spider的抓取流程
圖7.2 spider的抓取流程
抓取工作流程如圖7.2所示，大致步驟如下：
1) 如果採集數據達到300k(上傳數據閾值),則上傳數據到信息伺服器。
2) 從url佇列中取出一個url放入協定判斷器中。如果此時url佇列為空，則轉入7），否則轉入3)。
3) 根據url頭部的協定信息，協定判斷器對url所採用的協定進行判斷，如果是http協定，轉入4)，如果是ftp協定，轉入5)，如果是bbs協定，轉入6)。
4) 啟動採集http協定的執行緒httppagecontrol，對本頁通過httpconnection進行採集。採集完後保存此頁，轉入1)
5) 啟動採集ftp協定的執行緒ftppagecontrol，對本頁通過ftpconnection進行採集。採集完後保存此頁，轉入1)
6) 啟動採集bbs協定的執行緒bbspagecontrol，對本頁通過bbsconnection進行採集。採集完後保存此頁，轉入1)
7) 向信息伺服器傳送請求url指令，採集完畢。
7.2.3 抓取頁面時的處理
因為所抓取的主要頁面都是符合http協定的，所以我們以http協定為例，說明具體的頁面抓取時的處理。在頁面抓取過程中用socket實現了基本的http協定。採集器可以經由指定的代理伺服器（proxy）採集目標url，並且在目標url要求身份認證時能自動用事先設定好的用戶標識和口令應答。抓取頁面的主要實現算法如下：
1) 分析頁面url，抽出目標站點地址和連線埠號，若無連線埠號設為http默認連線埠80。判斷該站點的連線方式設定，若設為直接連線則與該地址和連線埠建立網路連線；若設為穿越proxy連線則與指定的proxy地址和連線埠建立網路連線。
2) 若建立網路連線失敗，說明該站點不可達，中止抓取該頁面並將其拋棄；否則繼續下一步驟獲取指定頁面。
3) 由頁面url組裝http請求頭，若該站點需要用戶標識和口令則將其填入請求頭中，傳送請求到目標站點。若超過一定時間未收到應答訊息則中止抓取該頁面並將其拋棄；否則繼續下一步驟分析應答訊息。
4) 分析應答頭，判斷返回的狀態碼：
若狀態碼為2xx，返回正確頁面，進入步驟5)；
若狀態碼為301或302，表示頁面被重定向，從應答頭中提取出新的目標url，轉入步驟3)；
若狀態碼為其它，說明頁面連線失敗，中止抓取該頁面並將其拋棄。
5) 從應答頭中提取出日期、長度、頁面類型等頁面信息。若設定了頁面抓取限制，進行必要的判斷和過濾，拋棄不符合要求的頁面。
6) 讀取頁面的內容。對於長度較大的頁面，採用分塊讀取再拼接的方法保證頁面內容的完整。至此該頁面的抓取完成。
7.2.4 採集數據的組織
採集的數據存儲主要有兩個資料庫：快取資料庫，頁面記錄資料庫。
快取庫保存採集到的站點源頁面，每個頁面存成單獨檔案。每個站點創建一獨立的目錄，並按照頁面url中體現的層次組建本地快取檔案的目錄。例如，頁面在快取庫中對應檔案即為目錄下的“file1”檔案，其中[cachebase]指快取庫的根目錄。由於url可能包含檔案名稱中不允許的特殊字元，在轉換成目錄和檔案名稱時要用系統規定的轉義字元替換。
所採集頁面的長度、更新日期、標題等數據存儲在頁面記錄資料庫中。每個頁面對應庫中的一條記錄，包含了頁面的簡要說明，在後續的某些處理過程中可以從中獲得必要的信息而不必再查看源頁面。
第八章 頁面分析
在本信息採集的url和頁面的過濾判定過程中，主要處理html頁面。因此，在頁面分析中我們所做的工作主要包括對html頁面進行語法分析，提取出正文、連結、連結的擴展元數據及其它相關內容；再把這些內容進行簡單的加工和一致性處理；最後將處理結果保存在中間信息記錄庫中以供url過濾處理和頁面過濾處理。
8.1 html語法分析
因為採集到頁面的語法分析基於html（hypertext markup language）協定[rfc 1866]。整個語法分析過程可以看作兩個層次，即sgml（標記文法）層和html標記層。文法層將頁面分解成正文、標記、注釋等不同的語法成分，再調用標記層處理正文和標記。同時標記層維護著當前正文的各種狀態，包括字型、字型等，這些狀態由特定標記產生或改變。
在系統中使用的標記文法分析器的基本原理是：由標記文法構造狀態轉換表，根據輸入流中的當前字元（無需向前看）切換狀態，當到達特定狀態時執行相應語義操作。這裡先介紹幾個概念，然後分別討論對主要語法成分的處理：
l 文本。文本是頁面的初始狀態，此狀態下的所有字元（除了導致切換到其它狀態的）都構成頁面正文的一部分交由標記層根據當前正文狀態處理和保存。
l 標記。標記是出現在正文中以字元“<”開始，字元“>”結尾的一個字元串。語法分析器在遇到“<”後就創建一個標記結構，並將後續的標記名稱、標記中的參數等一一填入該結構中，其中參數由多個參數名/值對組成。當遇到“>”表示標記結束，將分析出的標記結構傳遞給標記層。標記層在根據標記名和參數做相應動作，包括修改正文狀態等。若在“<”後緊跟著字元“/”，則表明此標記是個結束標記，分析器區分開始和結束標記，但兩者的配對由標記層實現。對標記的處理在後面討論標記層時會進一步論述。
l 注釋。分析器判斷“<!”打頭的標記並統計模式“--”的個數從而識別頁面中的注釋，注釋直接被忽略而不作任何處理。
l 轉義字元。文本中出現的形如“&#nnn”或“&xxx”（末尾可能有附加的字元“;”）的，分析器將其作為轉義字元處理，查找相應對照表後將對應字元添加入正文中。
8.2 頁面中正文的提取
儘管url已經被預測為和主題相關，但此url所指向的實際頁面卻可能與預測結果相差甚遠，這就導致了採集到的頁面有相當大一部份與主題無關，因此，我們需要對頁面進行主題相關性判斷，通過判斷結果過濾掉無關頁面，從而提高整個數據集中頁面與主題的平均相似度值，或者說提高基於主題的web信息採集的準確率。
為此，我們需要在頁面分析時提取出頁面中的正文。頁面的正文提取方法較簡單。正文和標記都作為獨立的語法成分傳遞給標記層，標記層根據標記區分出頁面標題和內容，並根據系統需要合併出頁面的正文。目前還未考慮不同字型或字型的正文的差別。也就是說，在讀取頁面時，找到標記<body>和</body>，將這兩個標記中間的內容去除其中的所有標記即可。
8.3 頁面中連結的提取
對抓取到的頁面需要分析其中的連結，並對連結中的url進行必要的轉換。首先判別頁面類型，顯然只有類型為“text/html”的頁面才有必要分析連結。頁面的類型可由應答頭分析得出，有些www站點返回的應答信息格式不完整，此時須通過分析頁面url中的檔案擴展名來判別頁面類型。遇到帶有連結的標記如<a>、<area>、<frame>等，就從標記結構的屬性中找出目標url，並從成對的該標記之間抽取出正文作為該連結的說明文字(擴展元數據)。這兩個數據就代表了該連結。
對一個頁面中的連結提取工作流程如下：
1) 從頁面檔案佇列中取出一個頁面檔案，如果應答頭中未說明檔案類型，根據url中的檔案擴展名補充完整。如果頁面檔案佇列為空，跳轉到7)。
2) 判斷頁面是否為text/html/htm/shtml檔案，如果不是，拋棄此檔案，轉入1)，否則轉入3)。
3) 從檔案頭按順序讀取檔案，遇到如下標記<a href=……> <area href=……> <base href=……> <frame src=……> <img src=……> <body background=……> <applet code=……>等，記錄其中的url連線。如果遇到檔案結束符，則跳轉到7)
4) 將提取出來的url連結按照預先定義的統一的格式補充完整。(頁面連結中給出的url可以是多種格式的，可能是完整的、包括協定、站點和路徑的，也可能是省略了部分內容的，或者是一個相對路徑)
5) 記錄下<a href=……> <area href=……> <base href=……> <frame src=……> <img src=……> <body background=……> <applet code=……>等後面對此連結的說明信息。在url與主題的相關性判定那一章中，我們要用到此信息，並把它定義為擴展元數據。
6) 存儲此url及其擴展元數據，跳轉到2)。
7) 頁面url提取完畢。
此算法中，不但提取了已採集頁面中的url，並且同時提取了每個url的擴展元數據信息，在下一章，我們將看到對擴展元數據的套用。
8.4 頁面中標題的提取
如圖8.1所示，頁面中標題的提取分為三步：1).判斷正文開始的位置，從文章開頭開始，逐段掃描，直到某一段長度不小於設定的正文最小長度，就假定這段為正文中的一段。2). 由正文位置向前搜尋可能是標題的一段，根據字型大小、是否居中、顏色變化等特徵找出最符合的一段文字作為標題。3). 由所給參數調整標題所在的段，使標題提取更準確。句法、語義、統計分析標題段sttitlepara的前後幾段，以準確確定標題段的真實位置；向前或向後調整幾段，追加前一段或後一段。
判斷正文開始的位置
由正文位置向前搜尋可能是標題的一段
由所給參數調整標題所在的段，使標題提取更準確
標題