搜索引擎信息覆蓋率評測模型研究報告

1、-PAGE . z搜索引擎的信息覆蓋率評測模型研究孟濤 李曉明 閆宏飛大學計算機科學技術系 ，100871摘 要本文從有向圖構造出發(fā)，總結分析了搜索引擎搜集子系統(tǒng)網(wǎng)頁搜集不完全性的假設干因素，指出信息覆蓋率這一概念的研究意義，由此提出了三類比擬重要的信息覆蓋率概念。在對信息覆蓋率建立量化研究模型之后，本文以北大天網(wǎng)WebInfomall平臺為考察對象，以不同的方式對中國Web進展取樣，用PageRank和HITS這兩類典型的權值算法計算出其中的重要網(wǎng)頁作為樣本，從量和質的角度上考察webinfomall的信息覆蓋率，得到合理的數(shù)量覆蓋率和質量覆蓋率實驗數(shù)據(jù)，從而驗證了WebInfomall信息

2、覆蓋率結論的合理性和信息覆蓋率評測模型的可靠性。關鍵詞搜索引擎，信息覆蓋率，取樣，權值計算，驗證，數(shù)量覆蓋率，質量覆蓋率研究背景World Wide Web自1989年誕生并于次年開場運行以來,在迄今為止的十多年里開展迅猛，已逐漸成為人類社會信息資源中的一個重要組成局部。它以超文本和超媒體為核心技術，將文本、圖形、圖像、音頻和視頻等信息有機結合起來，給人們以豐富的信息表示空間。隨著Internet技術和應用的不斷開展，社會的信息化進程不斷加快，越來越多的社會信息資源開場選擇Web作為其載體。當前，上大約有8,745,000個，約2,500,000,000網(wǎng)頁，包含了至少19TB以上的數(shù)據(jù)，而且

3、這些網(wǎng)頁正以每天凈增7,500,000的速度膨脹1 2。而在中國，根據(jù)中國互聯(lián)網(wǎng)絡中心NIC于2002年1月進展的互聯(lián)網(wǎng)統(tǒng)計報告3，下注冊的域名數(shù)為127,319個，共有277,100個Web站點。到2002年為止，中國境內(nèi)的Web站點共有53,432,598個網(wǎng)頁，主要分布在約49,146個中4。面對浩瀚的互聯(lián)網(wǎng)絡資源，人們假設不借助其他工具很難快速的查找到自己所需要的信息，這帶來了搜索引擎的誕生。從1994年誕生的第一代搜索引擎Lycos和InfoSeek等開場，開展到當前流行的Google、Altavista等系統(tǒng)，它們已逐漸成為人們進展網(wǎng)際沖浪的重要工具之一。根據(jù)弗吉尼亞理工大學GVU

4、中心的調查報告5 ，全世界有84.8%的用戶通過搜索引擎獲得自己所需網(wǎng)頁，足見搜索引擎功用之一斑。我們將每一條獨立的信息稱為一個網(wǎng)頁，它有一個唯一的資源定位地址稱為URL(Uniform Resource Location)。搜索引擎便是利用URL之間的連接關系，搜集其對應的網(wǎng)頁信息，建立索引，供用戶查詢。因此，搜索引擎搜集的網(wǎng)頁集合便是用戶所能得到查詢結果的最大范圍；這個范圍越接近，搜索引擎越優(yōu)秀。事實上，沒有任何一個搜索引擎能搜集完的所有網(wǎng)頁。著名的搜索引擎Google系統(tǒng)和WiseNut系統(tǒng)，搜集到并提供應用戶查詢的網(wǎng)頁數(shù)量分別是2,073,418,204個6和1,571,413,207

5、7個，最多不過靜態(tài)網(wǎng)頁總數(shù)的80%。而根據(jù)Greg R.Notes在200.年3月發(fā)表的搜索引擎統(tǒng)計數(shù)據(jù)8.，這兩個系統(tǒng)的網(wǎng)頁數(shù)據(jù)量是最大的。網(wǎng)絡上的信息數(shù)量巨大而且種類繁多，任何一個實際運行的搜集系統(tǒng)都不可能將其全部搜盡。優(yōu)秀的搜索引擎總會搜集盡量多的網(wǎng)頁，更好的滿足用戶的查詢要求?？疾焖阉饕鎸π畔①Y源的搜集覆蓋程度，可作為不斷改良搜集系統(tǒng)的根據(jù)，對評價搜索引擎的性能好壞具有積極的作用。另一方面，隨著社會信息化程度的不斷提高，將是該階段人類社會信息資源在網(wǎng)絡上的投影，記錄著人類社會的歷史開展進程?；谒阉饕婕夹g開發(fā)的網(wǎng)絡信息博物館正以此為目的，力圖通過搜索引擎的網(wǎng)頁搜集系統(tǒng)不斷搜集上的所

6、有網(wǎng)頁，假設干年后能夠同時在時間和空間上展示的每一個角落。因此，研究搜索引擎的信息覆蓋率對驗證網(wǎng)絡信息博物館網(wǎng)頁資源的有效性也有著十分重大的意義。本文的研究工作基于上述目的，針對大學計算機系網(wǎng)絡與分布式系統(tǒng)實驗室開發(fā)的搜索引擎8及以此為根底開發(fā)的網(wǎng)上信息博物館WebInfomall9，采取多種方法從多個角度計算其信息覆蓋率，證明了該網(wǎng)頁搜集系統(tǒng)獲得的中國網(wǎng)絡信息資源是根本有效的。模型概述網(wǎng)頁搜集的不完全性如果把中的每一個網(wǎng)頁看作一個頂點，則這個頂點以URL作為它的唯一標記；又由于網(wǎng)頁中存在其它網(wǎng)頁的URL，可以把這種網(wǎng)頁間的看作連接頂點的邊，則整個構成了一張有向圖，如圖1示。相應的，每一個頂點

7、的入度和出度對應著鏈向該網(wǎng)頁的網(wǎng)頁數(shù)量和該網(wǎng)頁鏈向其他網(wǎng)頁的數(shù)量。顯然，這是一張不完全圖，因為里面存在很多入度或出度為0的頂點。當前的網(wǎng)頁搜集系統(tǒng)都是基于對這種構造的理解，依據(jù)網(wǎng)頁之間的關系，從*一個種子URL開場，不斷的從新搜到的網(wǎng)頁中提取出URL，從而到達其它的網(wǎng)頁。搜集過程中，通常需要對網(wǎng)頁重要性作初步的判斷，優(yōu)先搜集相對有價值的網(wǎng)頁。在這種搜集機制里面，存在著以下問題，導致無法遍歷所有的網(wǎng)頁。局部網(wǎng)頁的入度為0，即從任何一個網(wǎng)頁開場，都不存在到它的路徑，這類網(wǎng)頁的數(shù)量約占全體網(wǎng)頁數(shù)量的10%10 。選擇的種子URL集合中，任何一個網(wǎng)頁都不存在到該網(wǎng)頁的路徑。中的有向圖構造中，只有約21

8、.3%的頂點能被選取作為起始點去遍歷剩下的約90%的頂點10。由于在網(wǎng)頁搜集的過程中出現(xiàn)了優(yōu)先排序，搜集系統(tǒng)資源本身的限制磁盤容量和時間限量導致局部網(wǎng)頁直到搜集過程中止都沒有被搜集，出現(xiàn)Starve的情況11。本身處于不斷的膨脹過程之中，大量新出現(xiàn)的網(wǎng)頁來不及搜集。搜集系統(tǒng)自身一般都有搜集周期，而*些網(wǎng)頁如實時新聞網(wǎng)頁的更新頻率遠大于搜集頻率。從廣義的角度而言，但凡上的信息都應該被搜集，而現(xiàn)在的搜索引擎一般只搜集了局部格式的網(wǎng)頁信息。當前搜集的一般都是靜態(tài)網(wǎng)頁中類似于HTML文檔的信息資源，沒有考慮到包括動態(tài)網(wǎng)頁在內(nèi)的巨量深層網(wǎng)絡文檔。據(jù)估計，當前中的所有網(wǎng)頁包括深層網(wǎng)頁約有5500億之多，搜

9、索引擎所覆蓋的不到其百分之一12！因此，可以肯定任何一個實際運行的網(wǎng)頁搜集系統(tǒng)都不可能將當前中的所有網(wǎng)頁全部抓盡。這種搜集性能越優(yōu)異，意味著它所獲得網(wǎng)頁集合在數(shù)量和質量上越接近于實際的，網(wǎng)頁之間的關系也越逼近實際的有向圖構造。搜索引擎的信息覆蓋率正是對這種接近程度的衡量，它表達了一個網(wǎng)頁搜集系統(tǒng)所獲得的網(wǎng)頁集合及關系所占實際的比例。幾類重要的覆蓋率廣義的信息資源，應該定義為互聯(lián)網(wǎng)上的一切信息，即所有存在于上的文檔。這些文檔有些能通過瀏覽器瀏覽，有些則不能；有些存在于的數(shù)據(jù)庫中，經(jīng)過動態(tài)的請求方能生成，有些則是靜態(tài)存在的且被其它網(wǎng)頁到。搜索引擎當前所能搜集的絕大多數(shù)就是這種靜態(tài)的網(wǎng)頁，且在處理過

10、程中進一步過濾掉了*些不可瀏覽的局部如可執(zhí)行文件等。在這里，我們所研究的搜集系統(tǒng)覆蓋目標是上的所有靜態(tài)網(wǎng)頁，它們通?？赏ㄟ^瀏覽器顯示內(nèi)容，且其URL一般靜態(tài)存在于其它網(wǎng)頁中。我們可以從多個角度來考慮搜索引擎對信息資源的覆蓋程度。搜集系統(tǒng)應該力圖遍歷的所有網(wǎng)頁，在數(shù)量這一角度上到達完全覆蓋的程度。這提供一個衡量搜集系統(tǒng)覆蓋信息能力的全局標準。例如當前上的網(wǎng)頁估計約為2,500,000,000個2 ，Google系統(tǒng)的網(wǎng)頁搜集數(shù)量是2,073,418,204個6 ，因此可以估計其數(shù)量覆蓋率為百分之八十左右。如果系統(tǒng)的數(shù)量覆蓋率足夠高，我們就可以認為它根本上覆蓋了上的所有信息資源。高的數(shù)量覆蓋率應該

11、是任何一個搜集系統(tǒng)及以此為根底的網(wǎng)上信息博物館的首要目標。網(wǎng)上信息資源極為豐富，但也存在不少冗余，大量的廣告頁面和內(nèi)容重復頁面便是此例。即使去除這些冗余后，用戶感興趣的網(wǎng)頁通常也只是數(shù)以十億計的數(shù)量中的極少數(shù)。因此，考慮搜集系統(tǒng)在質量上對網(wǎng)頁的覆蓋程度顯得尤為重要。這一指標可以告訴我們，對那些用戶會感興趣的重要的網(wǎng)頁，系統(tǒng)覆蓋了其中的百分之幾。從更深的層次來說，如果搜集系統(tǒng)覆蓋了絕大多數(shù)的重要網(wǎng)頁，它也就覆蓋了當前社會信息在每一個重要主題上映射到上的局部，成為它的一個有效特征子集。類似于WebInfomall的系統(tǒng)如果將這些重要網(wǎng)頁全部記錄下來，以后就能通過歷史網(wǎng)頁回放來重現(xiàn)人類社會信息資源在

12、時間和空間兩維上的每一個角落。從信息的表現(xiàn)形式來看，搜集系統(tǒng)當前存儲的信息中相當一局部日后將是不可見的。這一方面是由于存儲系統(tǒng)的資源所限，未能搜集類似于圖片影音之類的大文檔；另一方面是因為搜集技術的不成熟，無法獲得類似于JavaScript、Applet等格式的網(wǎng)頁。因此，考察搜集系統(tǒng)對可視網(wǎng)上信息資源的覆蓋率，也有著積極的意義。它可以告訴我們當前所搜集到的網(wǎng)頁當中，多大比例的一局部能夠在假設干年后通過瀏覽器重新瀏覽。在本文的研究中，將對前面的兩種進展詳細的討論和量化分析。信息覆蓋率評測模型我們定義搜集系統(tǒng)的信息覆蓋率為它所收集的網(wǎng)頁集合在中所占的比例。考慮到的構造，將其視為一張有向圖G=V

13、，E，則搜集系統(tǒng)所獲得的網(wǎng)頁集合是G的強連通子圖.不一定是強連通圖G=V，E，每一個頂點都有唯一的標記URL。則信息覆蓋率的表達式為：C=需要加一句對公式的解釋。G的相關屬性在搜集過程中已得到，但是因為搜索引擎搜集網(wǎng)頁的不完全性，G的相關屬性卻只能去估計。為了得到準確的信息覆蓋率數(shù)據(jù)，我們采取對取樣的方法，即采取隨機的方式從中獲得一張子圖=V，E，考察V中的頂點落在V中所占V的比例C作為C的近似值。如果足夠大或是隨機性足夠好,則C非常接近于C。此時的C即搜集系統(tǒng)的數(shù)量覆蓋率。我們可以用類似的思想去計算搜集系統(tǒng)的質量覆蓋率?？紤]中的所有重要網(wǎng)頁構成的連通子圖G，我們可以用隨機的方法獲得*些重要網(wǎng)

14、頁組成的集合S作為樣本，來考察搜集系統(tǒng)覆蓋S中的子集S所占樣本容量的比例，作為近似的質量覆蓋率C,因此質量覆蓋率的表達式為：為什么用雙豎線.C=因此，我們需要通過對隨機取樣獲得網(wǎng)頁樣本；需要采取*些方法得到隨機的重要網(wǎng)頁集合，這通常要利用網(wǎng)頁之間的關系來對網(wǎng)頁進展權值估算；在得到網(wǎng)頁樣本之后，再檢查搜集系統(tǒng)的網(wǎng)頁覆蓋其中的比例，在檢查過程中，必須對網(wǎng)頁過濾，扔掉無法連接到的網(wǎng)頁?？傮w的工作流程大致如以下圖所示：數(shù)量覆蓋率我們可以從不同的角度來對來進展采樣。如果不考慮頂點之間的關系，僅從頂點的標記URL所對應的IP地址出發(fā)，可以采取隨機產(chǎn)生IP的方法來獲得一個網(wǎng)頁集合，從而得到樣本，這種考慮基于

15、全局的視點；如果考慮到頂點之間的關系，則可以模仿搜索引擎搜集系統(tǒng)的工作方式，采取絕對廣度優(yōu)先的方法，從*一個頂點種子URL出發(fā)，逐漸擴展遍歷，得到一個網(wǎng)頁集合作為樣本，這是一種從局部來進展取樣的方法。隨機IP法在Edward T.ONeil和和 Patrick D.M的工作13中，他們提出了通過隨機產(chǎn)生IP來對進展取樣的方法。首先獲得上已經(jīng)分配使用的所有IP地址，假設共有M個?？梢岳肐P的分段將它們一一映射到0到M-1之間的*個整數(shù)作為唯一標記。這樣，我們可以利用隨機算法產(chǎn)生小于M的整數(shù)，得到一個IP標記集合，再逆映射回到IP地址，即得到一組隨機IP樣本。如果搜集系統(tǒng)以域名標志地址，還需要將

16、其轉換為域名。這種取樣原理如圖3所示：3.1.1取樣我們在研究工作中獲得了中國國內(nèi)已分配的所有IP地址分段4322個，例如至55為其中一個分段，被分配給大學使用。如果統(tǒng)一用點分十進制表示所有網(wǎng)絡地址，則所有的IP分段可以表示如下A1.B1.C1.D1A2.B2.C2.D2An.Bn.DnAn.Bn.DnAt.Bt.Ct.Dt中的函數(shù)值為：F(a.b.c.d)=+a-At*+(b-Bt)*+ (c-Ct)*+ (d-Dt)于是我們將每一個IP都對應到一個整數(shù)，便可以用隨機算法在其中選取假設干，逆映射轉變?yōu)镮P地址，便得到一個IP地址集合。去掉此集合

17、中不提供效勞包括與網(wǎng)絡無連接的元素，就得到了一個樣本。由于大約93.6%14的通過80端口提供 效勞，我們可以順次掃描這些網(wǎng)絡地址上的80端口。得到的存在 效勞的IP地址集合經(jīng)反向域名解析便可得到樣本URL集合。通過對中國國內(nèi)的IP進展隨機取樣并進展掃描，我們得到了如下結果：編號12345678910隨機IP數(shù)100K200K300K400K500K600K700K800K900K1M存在 數(shù)95172252336418478570652717817表格中間線太粗，而且第三條應該是不可見的在上面的統(tǒng)計中，我們選取了多組不同數(shù)量的隨機IP，得到的存在 效勞的IP地址數(shù)量與隨機數(shù)大致成比例，說明選

18、出的IP地址具有很好的隨機性。3.1.2驗證由于搜集系統(tǒng)一般以包含域名的URL來記錄網(wǎng)頁，我們要檢驗這些網(wǎng)頁是否已被覆蓋，應該將其轉化為相應的域名。由于網(wǎng)絡中DNS效勞器提供的IP反向解析功能有限，而搜集系統(tǒng)在搜集過程中通常記錄了搜到的網(wǎng)頁域名與IP地址的對應關系，我們可以由此直接檢驗被覆蓋的IP地址數(shù)量。我們的目的是對所有的IP地址進展建模，接下來的問題應該是該用多少數(shù)據(jù)才能滿足要求使得樣本有效。盡管我們就這一問題無法給出準確的數(shù)量，但是可以從少量的數(shù)據(jù)開場，然后逐步增加數(shù)據(jù)量。如果我們這種通過隨機產(chǎn)生IP對取樣的方法是正確的，在原先樣本的根底上逐步增加數(shù)據(jù)集將不會影響信息覆蓋率的結果。因此

19、，我們可以對樣本容量從小到大的各組數(shù)據(jù)統(tǒng)計得到的覆蓋率進展分析，看是否滿足以上條件。下表是在各組隨機IP地址樣本中，被搜集系統(tǒng)覆蓋的IP地址所占比例。編號12345678910存在 數(shù)95172252336418478570652717817覆蓋IP數(shù)47913162128364347可以通過最小二乘法對結果進展線性擬合，得到以下的二維圖像。其中，橫軸代表隨機IP地址樣本容量，縱軸代表搜集系統(tǒng)覆蓋樣本的數(shù)量，直線的斜率則表示信息覆蓋率。從圖中可知，自變量和因變量之間存在很好的一次函數(shù)關系，覆蓋率根本保持在5.72%左右。由此可以推斷，當樣本擴展到所有的IP地址時，WebInfomall的覆蓋率

20、將會保持在這個數(shù)量左右。3.1.3模型修正和結果分析隨機IP法產(chǎn)生了大量的隨機IP地址，用這種方法可以很好的對上的所有提供 效勞的Web效勞器進展取樣；隨著樣本容量的增加，樣本的準確性也會增加。但是，這種采樣方法存在一些缺乏，導致信息覆蓋率具有較大偏差。首先，IP地址標記的是Web效勞器的網(wǎng)絡地址，在大多數(shù)情況下，它等同于該效勞器上運行的首頁。這使得我們最終得到的網(wǎng)頁集合實際上是上首頁的一個樣本。使用IP地址將使得我們對所有的一視*，忽略了的大小之別。一個只有三五個網(wǎng)頁的個人小如和一個有著上千網(wǎng)頁的大商業(yè)如/，為.sina./的IP地址是不等同的，然而這種區(qū)別在隨機IP地址取樣中無法表達。另外

21、，大量存在 效勞的效勞器并非是實際意義上的。大多數(shù)Windows系列操作系統(tǒng)自帶的IIS效勞器軟件，Linu*系統(tǒng)自帶安裝的Apache軟件，如此眾多，都會在缺省條件下提供Web效勞，而這些首頁是沒有實際意義的測試網(wǎng)頁。類似的，也有大量的在*個IP地址短暫出現(xiàn)的網(wǎng)頁例如臨時通過 效勞共享文件等等。在上述隨機IP取樣方法中，這些根本無效的網(wǎng)頁都被簡單的等同于重要首頁參加了樣本之中。因此，我們有必要對此模型作出修正。既要利用隨機IP方法具有的優(yōu)異的隨機性和全局性，又要保證通過隨機IP地址獲得的網(wǎng)頁的有效性。解決方法是利用網(wǎng)頁之間的關系，不再將各個網(wǎng)頁看作獨立的點，通過發(fā)現(xiàn)網(wǎng)頁中的URL而進展適當擴

22、展。我們在研究中將得到的所有隨機IP地址視為根本集合R ，通過 1.0協(xié)議取得這些IP地址上的網(wǎng)頁內(nèi)容，提取出其中的，參加R，作為網(wǎng)頁樣本，如以下圖所示：為了將無效網(wǎng)頁的影響降至最低，還可以對作多級擴展。經(jīng)過這種處理后，上述第一種情況可以得到修正，因為大的首頁通常存在較大的出度；第二種情況中默認網(wǎng)頁鏈出的網(wǎng)頁一般指向該軟件生產(chǎn)廠家的首頁，頁面一樣且數(shù)量少，且因其通常在國外故可在研究WebInfomall時過濾掉。我們從上述的隨機樣本中抽取了5組，經(jīng)過擴展以后的網(wǎng)頁樣本數(shù)量以及覆蓋數(shù)量如下：編號135710存在 數(shù)95252418570817擴展樣本容量10842584385954848094覆

23、蓋URL數(shù)17459684112041899在驗證的過程中，我們將用IP地址表示的URL轉化成域名URL，以便搜集系統(tǒng)的驗證。這種轉換經(jīng)過了兩級反向解析，第一步是通過網(wǎng)上DNS效勞器的解析，第二步是通過搜集系統(tǒng)保存的域名與IP對應數(shù)據(jù)。對得到的結果作線性擬合，得到的圖幾沒有標如下，從擬合結果可得到信息覆蓋率約為23.5%?？梢?，在對模型作修正之后，覆蓋率有很大的增幅；如果考慮到域名與IP之間的動態(tài)關系即大量域名的IP是可變的，DNS系統(tǒng)每隔幾分鐘更新一次，我們?nèi)コ魳颖局幸訧P表示的URL，數(shù)量覆蓋率數(shù)據(jù)將還會有小幅度的提高，這才是真正的數(shù)量覆蓋率大小。通過隨機IP法產(chǎn)生的網(wǎng)頁樣本很好的考察了

24、搜集系統(tǒng)對有向圖*些入度為0或是從出發(fā)頂點無法到達頂點的覆蓋情況。這啟示我們在搜集網(wǎng)頁過程中，選取適當數(shù)量的以隨機IP法產(chǎn)生的URL作為起始頂點集合的一局部，能提高搜集系統(tǒng)的數(shù)量信息覆蓋率和WebInfomall中網(wǎng)頁信息的有效性。廣度優(yōu)先法隨機IP法雖然具有較好的隨機性和全局性，但在使用過程中發(fā)現(xiàn)許多有待改良之處；為了使對的取樣在邏輯構造上與實際情況更加接近，考慮到對隨機IP法作修正時對邏輯關系的利用，我們提出了絕對廣度優(yōu)先搜集取樣的方法。這種方法實現(xiàn)的實際就是一個最原始的搜集系統(tǒng)的工作過程，只是在搜集過程中按照絕對廣度優(yōu)先的方式一級級的擴展開去。這種取樣是從局部的角度來進展的，原理如以下圖

25、所示。3.2.1取樣我們選取了五個URL作為起始點，采取上述絕對廣度優(yōu)先搜集網(wǎng)頁的方法分別獲得五組網(wǎng)頁樣本，樣本容量從幾萬到數(shù)十萬不等。算法如下：1選取*個網(wǎng)頁S作為起始URL；2創(chuàng)立隊列Q存儲未搜集的網(wǎng)頁，S入隊列；創(chuàng)立構造數(shù)組A存儲已經(jīng)搜集過的網(wǎng)頁，按照URL字符串排序；3取得隊列頭元素，通過 1.0協(xié)議獲取H的源文件，提取出其中包含的的全部URL，并記錄關系；4在A中用二分法尋找3中得到的URL是否已被搜集，如果沒有搜集，則使其進入隊列Q；5判斷A中的網(wǎng)頁數(shù)量是否已到達要求，假設沒有繼續(xù)3。得到的結果列表如下：樣本編組12345種子URL..sina.

26、擴展URL數(shù)668912116291543147238661740783.2.2驗證和分析得到網(wǎng)頁樣本之后，我們可以在WebInfomall的網(wǎng)頁數(shù)據(jù)庫中驗證被覆蓋的比例。為了快速的檢驗數(shù)據(jù)，到達磁盤性能的極限，我們啟動了數(shù)百個進程從URL列表中讀取并通過Hash算法從庫中查找。得到的覆蓋率數(shù)據(jù)如下表所示。對于這組離散的覆蓋率值，我們計算均值和方差分別為41.6%和0.0230，前者即為通過絕對廣度優(yōu)先法得到的數(shù)量覆蓋率。樣本編組12345擴展URL數(shù)66891211629154314723866174078覆蓋數(shù)量26732875626717827306674370數(shù)量覆蓋率40.0%41.

27、4%43.5%37.7%42.7%對于使用這種采樣方法得到的數(shù)量覆蓋率41.6%，較之采用隨機IP法具有較高的覆蓋率值是可以理解的。因為這兩批數(shù)據(jù)是從兩個不同的方面說明搜集系統(tǒng)的信息覆蓋情況：隨機IP法著眼于全局，而絕對廣度優(yōu)先法著眼于局部，更類似于搜索引擎的搜集過程。通常搜集系統(tǒng)是在中的最*通子圖內(nèi)遍歷，絕對廣度優(yōu)先法恰好反映了搜集系統(tǒng)對這一最*通子圖的覆蓋比例。由于這一最*通子圖占據(jù)了中90%10左右的網(wǎng)頁，而且我們選取的起始URL均落在這一子圖之內(nèi)，故絕對廣度優(yōu)先法得到的結論應該修正為乘以90%這一參數(shù)才能在全局角度上反映搜集系統(tǒng)的覆蓋率，因此準確的數(shù)量覆蓋率應該是37.4%。當樣本容量

28、越大,覆蓋率就應該約逼近此值,這從我們采用的大容量樣本(第4組)結果中已經(jīng)得到了驗證。隨機IP法反映的是搜集系統(tǒng)對中所有點的覆蓋情況，因此這種采樣更容易采集到入度為0或由于其他原因導致搜集系統(tǒng)無法遍歷到的網(wǎng)頁稱為不可到達網(wǎng)頁。由于不可到達網(wǎng)頁中大量的點是孤立點，在沒有很好的區(qū)分這些IP地址上所存在的網(wǎng)頁數(shù)據(jù)量的情況下，這種樣本需要經(jīng)過多級擴展才能全面的反映真實的。也就是說，如果對初始URL不斷作擴展，最后的數(shù)據(jù)會不斷接近37.4%，這在我們作第一級擴展之后已經(jīng)有了好的反映。我們可以預測到，如果將兩種采樣方法的優(yōu)點結合起來，通過隨機IP法產(chǎn)生URL集合作為絕對廣度優(yōu)先法取樣的種子集合再進展擴展，

29、在樣本容量足夠大之后，最后的數(shù)量覆蓋率數(shù)據(jù)應該與通過文獻10 的工作做的估計相符，在37.4%附近。質量覆蓋率考察搜集系統(tǒng)在質量上對的信息覆蓋率，需要通過有效的網(wǎng)頁重要性評測方法找到一組重要網(wǎng)頁樣本。盡管通?？梢酝ㄟ^用戶評選提交的方式得到他們在瀏覽網(wǎng)頁過程中發(fā)現(xiàn)的重要網(wǎng)頁集合作為樣本，但在本文研究中，為了保證樣本的隨機性和客觀性，我們采用兩類基于對構造的分析而對中重要網(wǎng)頁進展取樣的有效方法。這些方法的根本思想都是找到一組具有較強關系的網(wǎng)頁初始取樣，通過基于分析的網(wǎng)頁權值算法，求出其中所有網(wǎng)頁的相對重要性值，從而可以對網(wǎng)頁進展排序取出前假設干位作為重要網(wǎng)頁的樣本。這些經(jīng)典的權值算法包括斯坦福大學

30、開發(fā)Google系統(tǒng)提出的PageRank算法15和IBM研究院開發(fā)Clever系統(tǒng)提出的HITS算法16 Hyperlink-Induced Topic Search，它們都是基于對有向圖構造的理解提出的。網(wǎng)頁重要性評測方法上的信息資源數(shù)量如此之大，無論是搜集系統(tǒng)本身還是承受返回結果的查詢用戶，都要求有好的方法對網(wǎng)頁集合按照重要性進展排序，因為系統(tǒng)搜集的和用戶關心的一般都只是其中的*一子集。準確的區(qū)分出重要的網(wǎng)頁加以優(yōu)先搜集，準確的計算出重要的網(wǎng)頁返回給用戶優(yōu)先瀏覽，要做到這些，我們需要適宜的網(wǎng)頁重要性評定方法。這里，網(wǎng)頁的重要性用權值來衡量，權值越高表示網(wǎng)頁越重要。我們可以從三個角度來分析

31、網(wǎng)頁的權值，討論它的相關因素。從網(wǎng)頁本身的唯一屬性URL出發(fā)來考慮：網(wǎng)頁的權值可以從URL的屬性中得到反映。一般而言，URL所在的域名越短，所在上相對于根目錄的層次越淺，網(wǎng)頁的權值越大。例如，大學的首頁../ 一般被認為比大學計算機系首頁 .. 的權值要高；而../page1.htm比../dir1/dir2/page2.htm 的權值顯然也要高。這一原理可以在網(wǎng)頁搜集過程中加以利用。從網(wǎng)頁作為有向圖的一個節(jié)點來考慮：網(wǎng)頁的權值可以根據(jù)它的認可度來判斷，由于網(wǎng)頁間的通常代表著認可度的傳遞，我們可以統(tǒng)計網(wǎng)頁的入度來評判其重要性。如果網(wǎng)

32、頁A上存在網(wǎng)頁B的URL，排除掉純粹導航的因素，表示著網(wǎng)頁A的作者存在對網(wǎng)頁B的認可；而這種認可的增多則意味著網(wǎng)頁B權值的上升。因此，入度越大，權值通常越高。從網(wǎng)頁本身的內(nèi)容出發(fā)來考慮：在搜索引擎搜集網(wǎng)頁的過程中，通常都要保存網(wǎng)頁的關鍵詞或全文信息，以便建立索引。由于網(wǎng)頁的重要性一般又對應著用戶較高的關心程度，我們可以通過對用戶遞交給搜索引擎的查詢詞與網(wǎng)頁的內(nèi)容全文或關鍵詞進展匹配，匹配程度越高意味著網(wǎng)頁的權值越高。當然，這要求用戶遞交的查詢是希望得到大量相關網(wǎng)頁的寬主題查詢。該情況在Kleinberg的論文18中有詳細討論。當前大多數(shù)搜索引擎所采用的網(wǎng)頁權值計算方法正是上面提到的的PageR

33、ank算法和HITS算法兩種，它們分別利用了上述中的后兩種原理，而且對其間的網(wǎng)頁關系作了更深層次的挖掘。PageRank算法15是一種利用網(wǎng)頁間關系進展權值計算的典型方法，它是學術論文引用統(tǒng)計原理在上的推廣，它統(tǒng)計每個網(wǎng)頁被引用的次數(shù)，但每一次引用又因引用者權值的不同而不同；而HITS算法17 將網(wǎng)頁的權值分為目錄型權值和權威型權值分別進展計算，目錄型權值高表示它鏈向很多權威型權值高的網(wǎng)頁，而權威型權值高則表示它被很多目錄型權值高的網(wǎng)頁所到。目錄型、權威型沒有解釋基于這兩種權值算法，我們提出了下面的兩類質量覆蓋率確定方法。廣度優(yōu)先法4.2.1 取樣PageRank算法根據(jù)網(wǎng)頁間的關系來評判網(wǎng)頁

34、的重要性，因此我們選取的初始網(wǎng)頁集合必須和有著大致一樣的構造，保證初始樣本中每個網(wǎng)頁的入度與實際互聯(lián)網(wǎng)絡相差不大，或者網(wǎng)頁入度的相對大小變化不大。這樣才能使得初始樣本中的相對網(wǎng)頁權值保持不變。我們可以利用絕對廣度優(yōu)先的方法，從初始URL開場向外遍歷。隨著初始樣本容量的加大，每個樣本網(wǎng)頁的入度越來越接近于它在中的實際入度，樣本網(wǎng)頁的入度相對大小也越來越固定。我們以數(shù)量覆蓋率研究中的廣度優(yōu)先法所獲樣本作為初始樣本，它們的數(shù)量一般在數(shù)十萬，已能根本保證其中相當數(shù)量網(wǎng)頁的相對入度大小。用PageRank算法從中計算選出權值在前M位的網(wǎng)頁集合作為樣本。顯然，M值越小，樣本的有效性越容易得到保證。4.2.

35、2 PageRank算法假定網(wǎng)頁A在里面被網(wǎng)頁T1Tn所鏈到，C(A)表示從A鏈出去的網(wǎng)頁數(shù)量即出度，則A的權值可以表示如下：PR(A)=17這種根本思想可以從以下圖中表達：考慮到用戶從Ti出發(fā)只有d0d1的可能性繼續(xù)瀏覽網(wǎng)頁 ，則相應的權值也只有相應比例的一局部傳到 A ，因此 PR(A) 可以調整如下：PR(A)=1-d+ d15如果將所有的網(wǎng)頁依次編號為1至 N ，他們的權值可以看作矢量W， 則W的轉秩是這個秩嗎.為PR1，PR2，PRN；考慮矩陣R ，如果存在從網(wǎng)頁 i到網(wǎng)頁 j的，則Ri,j=1/C(i) ，否則Ri,j=0；則所有的網(wǎng)頁權值可以寫成如下式子：W=d*WR + E其間

36、，E為常數(shù)向量。我們可以用迭代的方法求W的值 , 反復計算Wi+1=d*W(i)R + E ，直到W經(jīng)判斷已經(jīng)收斂。事實上，這里的d已經(jīng)成了一個收斂因子，盡管其實際意義為繼續(xù)瀏覽網(wǎng)頁的概率。沒看懂4.2.3 算法實現(xiàn)和試驗結果根據(jù)以上算法的需求，我們在網(wǎng)頁搜集過程中記錄了所有搜集到的網(wǎng)頁間的關系，隨著這個樣本網(wǎng)頁群體的增大，它在關系上將與越來越接近。出于對系統(tǒng)內(nèi)存需求的考慮，所有的網(wǎng)頁都被以整數(shù)統(tǒng)一編號而代替其URL字符串；網(wǎng)頁之間的關系以二元組的形式存入關系數(shù)據(jù)庫。當網(wǎng)頁的數(shù)量足夠大時，所有的網(wǎng)頁及其屬性無法一次全部存入內(nèi)存中，故需要分塊對矩陣進展迭代。具體的實現(xiàn)算法如下：創(chuàng)立數(shù)據(jù)構造存儲網(wǎng)

37、頁的整數(shù)ID、權值、出度、入度以及所有鏈入網(wǎng)頁的ID，以此作為矢量W的單元；根據(jù)網(wǎng)頁的平均入度2估計系統(tǒng)內(nèi)存一次能存放的URL數(shù)量N，在我們的系統(tǒng)中，估計約為1MB ；從數(shù)據(jù)庫中導出N個URL到內(nèi)存，按ID排序；再將全部的關系導入，對于上述N中的每一個，填充進它的屬性；對于N中的每一個，用二分法找到它的鏈入URL的數(shù)組下標，如果不在當前內(nèi)存中則其權值以平均值計算，運用PageRank算法計算其權值；如果全部的URL都已經(jīng)導入計算過，則對該矢量進展處理使得所有URL的權值之和為1；否則繼續(xù)4；如果先后兩次計算的W距離足夠小，則對權值排序選取前M個輸出到文件；否則繼續(xù)3。將輸出文件中的所有URL

38、整數(shù)ID轉換為URL字符串。實驗在Red Hat 7.2 系統(tǒng)上運行，主要硬件指標是1GB 內(nèi)存 ，P = 3 * ROMAN III 550 CPU。我們以數(shù)量覆蓋率計算中得到的五組樣本作為初始樣本，如果選擇權值排序位于前面約5%左右的網(wǎng)頁作為重要網(wǎng)頁的標準，得到了如下結果：樣本編組12345種子URL..sina.初始擴展數(shù)量66891211629154314723866174078PageRank取數(shù)352384978702334368408占前百分之幾5.3%4.0%5.6%4.6%4.8%覆蓋URL數(shù)154240324754177173456質量覆

39、蓋率43.8%47.5%54.6%53.0%41.1%取前M個,為什么每組占前百分之幾不一樣。對五組樣本檢驗得到的質量覆蓋率計算均值和方差分別是48.0%和0.0579。為了保證所求樣本網(wǎng)頁的重要性有效，我們選取了上述樣本中的第2組和第4組，改變判斷重要性的標準，質量覆蓋率隨此而變化的情形如下表所示。對于第二組網(wǎng)頁樣本：重要網(wǎng)頁個數(shù)18113434511768088497占前百分之幾0.86%1.62%2.42%3.22%4.02%覆蓋網(wǎng)頁數(shù)11452068278833634032質量覆蓋率63.2%60.2%54.5%49.4%47.5%以下圖是隨著重要性標準的放松，質量覆蓋率的變化情況：對

40、于第四組網(wǎng)頁樣本：重要網(wǎng)頁個數(shù)1732133436491986445079155占前百分之幾2.39%4.62%6.80%8.90%10.9%覆蓋網(wǎng)頁數(shù)990317717247183112636780質量覆蓋率57.2%53.0%50.2%48.3%46.5%以下圖是隨著重要性標準的放松，質量覆蓋率的變化情況：從這兩張圖中可以看出，當重要標準很苛刻時重要網(wǎng)頁樣本容量很小，此時搜集系統(tǒng)的覆蓋率很高；但隨著重要標準的放松導致樣本容量的增大，搜集系統(tǒng)的質量覆蓋率會越來越低；當重要性的標準放至最低，即所有網(wǎng)頁的地位平等時，質量覆蓋率變?yōu)樽钚?，為?shù)量覆蓋率值。這兩張圖中都顯示，當重要標準降至約5%左右時

41、，曲線開場逐漸變得平緩，因此此點的覆蓋率數(shù)據(jù)48.0%無疑最適合作為我們所測的的搜集系統(tǒng)質量覆蓋率。主題查詢法網(wǎng)頁具有作為有向圖構造中一個頂點的相關邏輯屬性，它又可根據(jù)其內(nèi)容本身而屬于人類社會信息資源的*一主題類別。例如，網(wǎng)頁可以根據(jù)其內(nèi)容分為屬于社會、人文或休閑娛樂等類別以及它們的子類的網(wǎng)頁。基于這一點的考慮，我們的研究工作中采取了通過主題查詢獲得重要網(wǎng)頁樣本的方法。這類似于文獻19 的工作中HITS算法選擇的網(wǎng)頁集合所采用的方法。由于上同一主題的網(wǎng)頁之間具有較強的關系19，我們可用HITS算法對此網(wǎng)頁集合進展權值計算，進展排序后得到前假設干網(wǎng)頁作為在這一主題類別的重要網(wǎng)頁樣本。4.3.1

42、取樣假設我們希望得到關于主題T的重要網(wǎng)頁樣本，我們一般會通過遞交假設干與T相關的查詢詞Q提交給搜索引擎，它返回的網(wǎng)頁集合為R。對于通常的搜索引擎，R的網(wǎng)頁一般都具有和T較高的相關度，因為查詢中通常使用字符串匹配，使得返回的網(wǎng)頁中大多含有Q之類的字樣。但是，也有大量的重要網(wǎng)頁不適合這種情況，例如天網(wǎng)系統(tǒng)的主頁并沒有搜索引擎的字樣供匹配。出于對這種特殊現(xiàn)象的考慮，需要對R以適當?shù)臄U展，參加R網(wǎng)頁鏈出去的網(wǎng)頁和鏈向R元素的網(wǎng)頁得到初始樣本S ，如圖示：我們選擇了八個主題的查詢詞遞交給天網(wǎng)搜索引擎，在用以上的方式對返回結果進展擴展之后，得到了八組初始網(wǎng)頁樣本如下：樣本編組12345678查詢詞大學考研

43、股票Linu*教程聯(lián)想集團三個代表世界杯返回數(shù)量18021802180218021355180218021802擴展數(shù)量11667193791340311006265481549811608208234.3.2 HITS算法上圖中的S正是我們用HITS算法進展權值計算的對象。對于S中的任意一個元素P ，設H(P)表示其目錄型權值Hub Weight，A(P)表示其權威型權值Authority Weight，F(xiàn)1,F2,Fm是鏈到P的網(wǎng)頁，T1,T2,Tn是從P鏈出的網(wǎng)頁，則A(P)和H(P)可以從下面的式子計算：A(P)=H(P)=同PageRank算法類似，我們可以將所有的網(wǎng)頁的目錄型權值看

44、作矢量H，將所有網(wǎng)頁的權威型權值看作矢量A，設樣本中所有網(wǎng)頁及關系構成的有向圖的鄰接矩陣為M，考慮到兩個URL之間最多有一個使得假設存在網(wǎng)頁i到網(wǎng)頁j的則Mi,j=1否則Mi,j=0，則上面的式子可以寫成：A=MHH=MA由此兩式可得A= MMA，即實際上A是MM的特征向量；同理H是MM的特征向量，我們因此也可以用冪法或QR算法等來通過迭代來求得A和H的值。但考慮到系統(tǒng)內(nèi)存對初始樣本容量的限制，假設數(shù)量很大的時候需要分塊對兩個矩陣進展迭代。4.3.3 試驗結果在我們的研究工作中，我們沒有通過計算特征向量而采取了根據(jù)前一組公式直接進展迭代計算A和H值的方法，具體的實現(xiàn)算法如下：采集初始樣本時將所

45、有的URL編號存入數(shù)據(jù)庫，同時存入URL之間的關系；創(chuàng)立相關的數(shù)據(jù)構造存儲每個URL的Hub和Auth權值及關系，從數(shù)據(jù)庫中導出所有URL屬性并填充到數(shù)據(jù)構造中；給予H和A*個初始值，分別計算Ai+1=MHi和H(i+1)=MA(i)，直至A(i+1)和A(i)的距離足夠小為止；分別對Auth和Hub值進展冒泡排序，輸出前假設干個URL到文件中。在確定重要網(wǎng)頁的界限時，我們選取的是初始網(wǎng)頁樣本中權值排在前面約15%左右的局部，大致與搜索引擎響應查詢詞返回的網(wǎng)頁數(shù)量相當。即搜索引擎就此主題返回*個重要網(wǎng)頁，我們經(jīng)過計算后也給出*個真正重要的網(wǎng)頁，檢查搜集系統(tǒng)覆蓋其中的比例作為質量覆蓋率。對于具有

46、較高Hub權值的重要網(wǎng)頁，實驗的數(shù)據(jù)如下：樣本編組12345678查詢詞大學考研股票Linu*教程聯(lián)想集團三個代表世界杯初始數(shù)量1166719379134031100626548154981160820823Hub取數(shù)16711701153210401508142818591961覆蓋數(shù)量958956578312772514793651覆蓋率57.3%56.2%37.7%30%51.2%36.0%42.7%33.2%八組樣本所得的質量覆蓋率分別為表幾所示，它們的均值和方差分別為43.0%和0.106，前者即為搜集系統(tǒng)對Hub型重要網(wǎng)頁的覆蓋率。對于具有較高Auth權值的重要網(wǎng)頁，實驗的數(shù)據(jù)如下

47、：樣本編組12345678查詢詞大學考研股票Linu*教程聯(lián)想集團三個代表世界杯初始數(shù)量1166719379134031100626548154981160820823Auth取數(shù)1400157211249301197104715811985覆蓋數(shù)量9439303853016926319271052覆蓋率67.4%59.2%34.3%32.4%57.8%60.3%58.6%53.0%八組樣本所得的質量覆蓋率分別為，它們的均值為，表幾所示方差為52.9%和0.1269，前者即為搜集系統(tǒng)對Auth型重要網(wǎng)頁的質量覆蓋率。4.3.3 修正與分析在上述的HITS算法中，我們將所有的地位視為平等，而事實

48、上并非如此，我們可以從它的導向詞與查詢詞的匹配度的不同處著手，這在Soumen Chakrabarti和 Byron Dom的工作19中有論述。這里的導向詞指的是該出現(xiàn)在網(wǎng)頁源文件的地方前后約150個字符之內(nèi)的信息，它們一般含有該網(wǎng)頁內(nèi)容或屬性的說明。即，*個網(wǎng)頁中兩個url1和url2，如果url1的導向詞中出現(xiàn)大學10次，而url2的導向詞中未出現(xiàn)此字眼，在查詢的主題是大學時，url1的地位要高于url2。我們稱以此為根底的算法為擴展HITS算法。假定查詢詞是Q，存在網(wǎng)頁A到B的，提取出網(wǎng)頁A中B的導向詞，設F(A,B)為Q在導向詞中匹配的次數(shù)，則可以對HITS算法作如下修正：A(P)=H

49、(P)=我們用這種算法對上述的8組初始樣本進展計算，然后分別選取Hub權值和Auth權值在前假設干位的重要網(wǎng)頁作為重要網(wǎng)頁樣本，從Hub和Auth兩個角度求得的搜集系統(tǒng)信息質量覆蓋率均值分別為46.2%和50.3%。從實驗數(shù)據(jù)可以看出，廣度優(yōu)先法和主題查詢法所求得的質量覆蓋率數(shù)據(jù)能夠很好的符合，WebInfomall的搜集系統(tǒng)對普通的重要網(wǎng)頁覆蓋率在50%左右。如果對重要網(wǎng)頁的標準提高一些，則質量覆蓋率的數(shù)據(jù)還要更高。結論本文針對搜索引擎搜集子系統(tǒng)對的信息覆蓋能力，創(chuàng)立了信息覆蓋率的量化研究模型。在這個模型中，我們提出兩套取樣方法，采取了兩類典型的網(wǎng)頁權值算法，分別從量和質的角度上分析計算搜集

50、系統(tǒng)的信息覆蓋率。運用這個模型，我們針對中國Web進展樣本采集，從而對北大天網(wǎng)系統(tǒng)的WebInfomall平臺所存儲的中國國內(nèi)網(wǎng)頁數(shù)據(jù)的信息覆蓋率進展評估。得到的數(shù)據(jù)顯示，在數(shù)量上WebInfomall平臺覆蓋了中國國內(nèi)網(wǎng)頁總數(shù)的37%，而在質量上覆蓋了重要網(wǎng)頁總數(shù)的50%左右。這個數(shù)據(jù)也顯示天網(wǎng)的覆蓋率與國際上諸如Google的幾個大搜索引擎系統(tǒng)相當，尤其是在數(shù)量覆蓋率這一方面。對于同一類型的信息覆蓋率，采用不同取樣和權值計算方法所驗證得到的數(shù)據(jù)能夠很好的符合，證明了信息覆蓋率模型的正確性以及所獲得WebInfomall平臺信息覆蓋率的準確性。實驗結果肯定了天網(wǎng)搜集系統(tǒng)的較強搜集能力，并對進一步改良這種搜集能力及相關WebInfomall平臺的性能提供了重要的客觀依據(jù)。本文缺乏之處在于對網(wǎng)頁重要性的定性標準不夠嚴密，對于PageRank算法，我們選取了權值位于前5%的網(wǎng)頁作為重要網(wǎng)頁；而對于HITS算法計算的查詢所得擴展網(wǎng)頁集合，我們選取重要的標準是和初始返回結果相等的量，約占權值排序后前面的10%。如文中所述，在實驗中通過對其中兩組樣