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