搜索引擎的信息覆蓋率評測模型研究報(bào)告

.z搜索引擎的信息覆蓋率評測模型研究孟濤李曉明閆宏飛大學(xué)計(jì)算機(jī)科學(xué)技術(shù)系，100871摘要 本文從有向圖構(gòu)造出發(fā)，總結(jié)分析了搜索引擎搜集子系統(tǒng)網(wǎng)頁搜集不完全性的假設(shè)干因素，指出信息覆蓋率這一概念的研究意義，由此提出了三類比擬重要的信息覆蓋率概念。在對信息覆蓋率建立量化研究模型之后，本文以北大天網(wǎng)WebInfomall平臺(tái)為考察對象，以不同的方式對中國Web進(jìn)展取樣，用PageRank和HITS這兩類典型的權(quán)值算法計(jì)算出其中的重要網(wǎng)頁作為樣本，從量和質(zhì)的角度上考察webinfomall的信息覆蓋率，得到合理的數(shù)量覆蓋率和質(zhì)量覆蓋率實(shí)驗(yàn)數(shù)據(jù)，從而驗(yàn)證了WebInfomall信息覆蓋率結(jié)論的合理性和信息覆蓋率評測模型的可靠性。關(guān)鍵詞 搜索引擎，信息覆蓋率，取樣，權(quán)值計(jì)算，驗(yàn)證，數(shù)量覆蓋率，質(zhì)量覆蓋率研究背景〔WorldWideWeb〕自1989年誕生并于次年開場運(yùn)行以來,在迄今為止的十多年里開展迅猛，已逐漸成為人類社會(huì)信息資源中的一個(gè)重要組成局部。它以超文本和超媒體為核心技術(shù)，將文本、圖形、圖像、音頻和視頻等信息有機(jī)結(jié)合起來，給人們以豐富的信息表示空間。隨著Internet技術(shù)和應(yīng)用的不斷開展，社會(huì)的信息化進(jìn)程不斷加快，越來越多的社會(huì)信息資源開場選擇Web作為其載體。當(dāng)前，上大約有8,745,000個(gè)，約2,500,000,000網(wǎng)頁，包含了至少19TB以上的數(shù)據(jù)，而且這些網(wǎng)頁正以每天凈增7,500,000的速度膨脹[1][2]。而在中國，根據(jù)中國互聯(lián)網(wǎng)絡(luò)中心〔NIC〕于2002年1月進(jìn)展的互聯(lián)網(wǎng)統(tǒng)計(jì)報(bào)告[3]，下注冊的域名數(shù)為127,319個(gè)，共有277,100個(gè)Web站點(diǎn)。到2002年為止，中國境內(nèi)的Web站點(diǎn)共有53,432,598個(gè)網(wǎng)頁，主要分布在約49,146個(gè)中[4]。面對浩瀚的互聯(lián)網(wǎng)絡(luò)資源，人們假設(shè)不借助其他工具很難快速的查找到自己所需要的信息，這帶來了搜索引擎的誕生。從1994年誕生的第一代搜索引擎Lycos和InfoSeek等開場，開展到當(dāng)前流行的Google、Altavista等系統(tǒng)，它們已逐漸成為人們進(jìn)展網(wǎng)際沖浪的重要工具之一。根據(jù)弗吉尼亞理工大學(xué)GVU中心的調(diào)查報(bào)告[5]，全世界有84.8%的用戶通過搜索引擎獲得自己所需網(wǎng)頁，足見搜索引擎功用之一斑。我們將每一條獨(dú)立的信息稱為一個(gè)網(wǎng)頁，它有一個(gè)唯一的資源定位地址稱為URL(UniformResourceLocation)。搜索引擎便是利用URL之間的連接關(guān)系，搜集其對應(yīng)的網(wǎng)頁信息，建立索引，供用戶查詢。因此，搜索引擎搜集的網(wǎng)頁集合便是用戶所能得到查詢結(jié)果的最大*圍；這個(gè)*圍越接近，搜索引擎越優(yōu)秀。事實(shí)上，沒有任何一個(gè)搜索引擎能搜集完的所有網(wǎng)頁。著名的搜索引擎Google系統(tǒng)和WiseNut系統(tǒng)，搜集到并提供應(yīng)用戶查詢的網(wǎng)頁數(shù)量分別是2,073,418,204個(gè)[6]和1,571,413,207[7]個(gè)，最多不過靜態(tài)網(wǎng)頁總數(shù)的80%。而根據(jù)GregR.Notes在200.年3月發(fā)表的搜索引擎統(tǒng)計(jì)數(shù)據(jù)[8]..，這兩個(gè)系統(tǒng)的網(wǎng)頁數(shù)據(jù)量是最大的。網(wǎng)絡(luò)上的信息數(shù)量巨大而且種類繁多，任何一個(gè)實(shí)際運(yùn)行的搜集系統(tǒng)都不可能將其全部搜盡。優(yōu)秀的搜索引擎總會(huì)搜集盡量多的網(wǎng)頁，更好的滿足用戶的查詢要求?？疾焖阉饕鎸π畔①Y源的搜集覆蓋程度，可作為不斷改良搜集系統(tǒng)的根據(jù)，對評價(jià)搜索引擎的性能好壞具有積極的作用。另一方面，隨著社會(huì)信息化程度的不斷提高，將是該階段人類社會(huì)信息資源在網(wǎng)絡(luò)上的投影，記錄著人類社會(huì)的歷史開展進(jìn)程?；谒阉饕婕夹g(shù)開發(fā)的網(wǎng)絡(luò)信息博物館正以此為目的，力圖通過搜索引擎的網(wǎng)頁搜集系統(tǒng)不斷搜集上的所有網(wǎng)頁，假設(shè)干年后能夠同時(shí)在時(shí)間和空間上展示的每一個(gè)角落。因此，研究搜索引擎的信息覆蓋率對驗(yàn)證網(wǎng)絡(luò)信息博物館網(wǎng)頁資源的有效性也有著十分重大的意義。本文的研究工作基于上述目的，針對大學(xué)計(jì)算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)實(shí)驗(yàn)室開發(fā)的搜索引擎[8]及以此為根底開發(fā)的網(wǎng)上信息博物館WebInfomall[9]，采取多種方法從多個(gè)角度計(jì)算其信息覆蓋率，證明了該網(wǎng)頁搜集系統(tǒng)獲得的中國網(wǎng)絡(luò)信息資源是根本有效的。模型概述網(wǎng)頁搜集的不完全性如果把中的每一個(gè)網(wǎng)頁看作一個(gè)頂點(diǎn)，則這個(gè)頂點(diǎn)以URL作為它的唯一標(biāo)記；又由于網(wǎng)頁中存在其它網(wǎng)頁的URL，可以把這種網(wǎng)頁間的看作連接頂點(diǎn)的邊，則整個(gè)構(gòu)成了一*有向圖，如圖1示。相應(yīng)的，每一個(gè)頂點(diǎn)的入度和出度對應(yīng)著鏈向該網(wǎng)頁的網(wǎng)頁數(shù)量和該網(wǎng)頁鏈向其他網(wǎng)頁的數(shù)量。顯然，這是一*不完全圖，因?yàn)槔锩娲嬖诤芏嗳攵然虺龆葹?的頂點(diǎn)。當(dāng)前的網(wǎng)頁搜集系統(tǒng)都是基于對這種構(gòu)造的理解，依據(jù)網(wǎng)頁之間的關(guān)系，從*一個(gè)種子URL開場，不斷的從新搜到的網(wǎng)頁中提取出URL，從而到達(dá)其它的網(wǎng)頁。搜集過程中，通常需要對網(wǎng)頁重要性作初步的判斷，優(yōu)先搜集相對有價(jià)值的網(wǎng)頁。在這種搜集機(jī)制里面，存在著以下問題，導(dǎo)致無法遍歷所有的網(wǎng)頁。局部網(wǎng)頁的入度為0，即從任何一個(gè)網(wǎng)頁開場，都不存在到它的路徑，這類網(wǎng)頁的數(shù)量約占全體網(wǎng)頁數(shù)量的10%[10]。選擇的種子URL集合中，任何一個(gè)網(wǎng)頁都不存在到該網(wǎng)頁的路徑。中的有向圖構(gòu)造中，只有約21.3%的頂點(diǎn)能被選取作為起始點(diǎn)去遍歷剩下的約90%的頂點(diǎn)[10]。由于在網(wǎng)頁搜集的過程中出現(xiàn)了優(yōu)先排序，搜集系統(tǒng)資源本身的限制〔磁盤容量和時(shí)間限量〕導(dǎo)致局部網(wǎng)頁直到搜集過程中止都沒有被搜集，出現(xiàn)Starve的情況[11]。本身處于不斷的膨脹過程之中，大量新出現(xiàn)的網(wǎng)頁來不及搜集。搜集系統(tǒng)自身一般都有搜集周期，而*些網(wǎng)頁〔如實(shí)時(shí)新聞網(wǎng)頁〕的更新頻率遠(yuǎn)大于搜集頻率。從廣義的角度而言，但凡上的信息都應(yīng)該被搜集，而現(xiàn)在的搜索引擎一般只搜集了局部格式的網(wǎng)頁信息。當(dāng)前搜集的一般都是靜態(tài)網(wǎng)頁中類似于HTML文檔的信息資源，沒有考慮到包括動(dòng)態(tài)網(wǎng)頁在內(nèi)的巨量深層網(wǎng)絡(luò)文檔。據(jù)估計(jì)，當(dāng)前中的所有網(wǎng)頁〔包括深層網(wǎng)頁〕約有5500億之多，搜索引擎所覆蓋的不到其百分之一[12]！因此，可以肯定任何一個(gè)實(shí)際運(yùn)行的網(wǎng)頁搜集系統(tǒng)都不可能將當(dāng)前中的所有網(wǎng)頁全部抓盡。這種搜集性能越優(yōu)異，意味著它所獲得網(wǎng)頁集合在數(shù)量和質(zhì)量上越接近于實(shí)際的，網(wǎng)頁之間的關(guān)系也越逼近實(shí)際的有向圖構(gòu)造。搜索引擎的信息覆蓋率正是對這種接近程度的衡量，它表達(dá)了一個(gè)網(wǎng)頁搜集系統(tǒng)所獲得的網(wǎng)頁集合及關(guān)系所占實(shí)際的比例。幾類重要的覆蓋率廣義的信息資源，應(yīng)該定義為互聯(lián)網(wǎng)上的一切信息，即所有存在于上的文檔。這些文檔有些能通過瀏覽器瀏覽，有些則不能；有些存在于的數(shù)據(jù)庫中，經(jīng)過動(dòng)態(tài)的請求方能生成，有些則是靜態(tài)存在的且被其它網(wǎng)頁到。搜索引擎當(dāng)前所能搜集的絕大多數(shù)就是這種靜態(tài)的網(wǎng)頁，且在處理過程中進(jìn)一步過濾掉了*些不可瀏覽的局部如可執(zhí)行文件等。在這里，我們所研究的搜集系統(tǒng)覆蓋目標(biāo)是上的所有靜態(tài)網(wǎng)頁，它們通?？赏ㄟ^瀏覽器顯示內(nèi)容，且其URL一般靜態(tài)存在于其它網(wǎng)頁中。我們可以從多個(gè)角度來考慮搜索引擎對信息資源的覆蓋程度。搜集系統(tǒng)應(yīng)該力圖遍歷的所有網(wǎng)頁，在數(shù)量這一角度上到達(dá)完全覆蓋的程度。這提供一個(gè)衡量搜集系統(tǒng)覆蓋信息能力的全局標(biāo)準(zhǔn)。例如當(dāng)前上的網(wǎng)頁估計(jì)約為2,500,000,000個(gè)[2]，Google系統(tǒng)的網(wǎng)頁搜集數(shù)量是2,073,418,204個(gè)[6]，因此可以估計(jì)其數(shù)量覆蓋率為百分之八十左右。如果系統(tǒng)的數(shù)量覆蓋率足夠高，我們就可以認(rèn)為它根本上覆蓋了上的所有信息資源。高的數(shù)量覆蓋率應(yīng)該是任何一個(gè)搜集系統(tǒng)及以此為根底的網(wǎng)上信息博物館的首要目標(biāo)。網(wǎng)上信息資源極為豐富，但也存在不少冗余，大量的廣告頁面和內(nèi)容重復(fù)頁面便是此例。即使去除這些冗余后，用戶感興趣的網(wǎng)頁通常也只是數(shù)以十億計(jì)的數(shù)量中的極少數(shù)。因此，考慮搜集系統(tǒng)在質(zhì)量上對網(wǎng)頁的覆蓋程度顯得尤為重要。這一指標(biāo)可以告訴我們，對那些用戶會(huì)感興趣的重要的網(wǎng)頁，系統(tǒng)覆蓋了其中的百分之幾。從更深的層次來說，如果搜集系統(tǒng)覆蓋了絕大多數(shù)的“重要〞網(wǎng)頁，它也就覆蓋了當(dāng)前社會(huì)信息在每一個(gè)重要主題上映射到上的局部，成為它的一個(gè)有效特征子集。類似于WebInfomall的系統(tǒng)如果將這些重要網(wǎng)頁全部記錄下來，以后就能通過歷史網(wǎng)頁回放來重現(xiàn)人類社會(huì)信息資源在時(shí)間和空間兩維上的每一個(gè)角落。從信息的表現(xiàn)形式來看，搜集系統(tǒng)當(dāng)前存儲(chǔ)的信息中相當(dāng)一局部日后將是不可見的。這一方面是由于存儲(chǔ)系統(tǒng)的資源所限，未能搜集類似于圖片影音之類的大文檔；另一方面是因?yàn)樗鸭夹g(shù)的不成熟，無法獲得類似于JavaScript、Applet等格式的網(wǎng)頁。因此，考察搜集系統(tǒng)對可視網(wǎng)上信息資源的覆蓋率，也有著積極的意義。它可以告訴我們當(dāng)前所搜集到的網(wǎng)頁當(dāng)中，多大比例的一局部能夠在假設(shè)干年后通過瀏覽器重新瀏覽。在本文的研究中，將對前面的兩種進(jìn)展詳細(xì)的討論和量化分析。信息覆蓋率評測模型我們定義搜集系統(tǒng)的信息覆蓋率為它所收集的網(wǎng)頁集合在中所占的比例?？紤]到的構(gòu)造，將其視為一*有向圖G=〔V，E〕，則搜集系統(tǒng)所獲得的網(wǎng)頁集合是G的強(qiáng)連通子圖...〔不一定是強(qiáng)連通圖〕G’=〔V’，E’〕，每一個(gè)頂點(diǎn)都有唯一的標(biāo)記URL。則信息覆蓋率的表達(dá)式為：C=需要加一句對公式的解釋。G’的相關(guān)屬性在搜集過程中已得到，但是因?yàn)樗阉饕嫠鸭W(wǎng)頁的不完全性，G的相關(guān)屬性卻只能去估計(jì)。為了得到準(zhǔn)確的信息覆蓋率數(shù)據(jù)，我們采取對取樣的方法，即采取隨機(jī)的方式從中獲得一*子圖=〔V，E〕，考察V’中的頂點(diǎn)落在V中所占V的比例C作為C的近似值。如果足夠大或是隨機(jī)性足夠好,則C非常接近于C。此時(shí)的C即搜集系統(tǒng)的數(shù)量覆蓋率。我們可以用類似的思想去計(jì)算搜集系統(tǒng)的質(zhì)量覆蓋率?？紤]中的所有重要網(wǎng)頁構(gòu)成的連通子圖G，我們可以用隨機(jī)的方法獲得*些重要網(wǎng)頁組成的集合S作為樣本，來考察搜集系統(tǒng)覆蓋S中的子集S所占樣本容量的比例，作為近似的質(zhì)量覆蓋率C,因此質(zhì)量覆蓋率的表達(dá)式為：〔為什么用雙豎線.〕C=因此，我們需要通過對隨機(jī)取樣獲得網(wǎng)頁樣本；需要采取*些方法得到隨機(jī)的重要網(wǎng)頁集合，這通常要利用網(wǎng)頁之間的關(guān)系來對網(wǎng)頁進(jìn)展權(quán)值估算；在得到網(wǎng)頁樣本之后，再檢查搜集系統(tǒng)的網(wǎng)頁覆蓋其中的比例，在檢查過程中，必須對網(wǎng)頁過濾，扔掉無法連接到的網(wǎng)頁?？傮w的工作流程大致如以下圖所示：數(shù)量覆蓋率我們可以從不同的角度來對來進(jìn)展采樣。如果不考慮頂點(diǎn)之間的關(guān)系，僅從頂點(diǎn)的標(biāo)記URL所對應(yīng)的IP地址出發(fā)，可以采取隨機(jī)產(chǎn)生IP的方法來獲得一個(gè)網(wǎng)頁集合，從而得到樣本，這種考慮基于全局的視點(diǎn)；如果考慮到頂點(diǎn)之間的關(guān)系，則可以模仿搜索引擎搜集系統(tǒng)的工作方式，采取絕對廣度優(yōu)先的方法，從*一個(gè)頂點(diǎn)〔種子URL〕出發(fā)，逐漸擴(kuò)展遍歷，得到一個(gè)網(wǎng)頁集合作為樣本，這是一種從局部來進(jìn)展取樣的方法。隨機(jī)IP法在EdwardT.O’Neil和和PatrickD.M的工作[13]中，他們提出了通過隨機(jī)產(chǎn)生IP來對進(jìn)展取樣的方法。首先獲得上已經(jīng)分配使用的所有IP地址，假設(shè)共有M個(gè)?？梢岳肐P的分段將它們一一映射到0到M-1之間的*個(gè)整數(shù)作為唯一標(biāo)記。這樣，我們可以利用隨機(jī)算法產(chǎn)生小于M的整數(shù)，得到一個(gè)IP標(biāo)記集合，再逆映射回到IP地址，即得到一組隨機(jī)IP樣本。如果搜集系統(tǒng)以域名標(biāo)志地址，還需要將其轉(zhuǎn)換為域名。這種取樣原理如圖3所示：3.1.1取樣我們在研究工作中獲得了中國國內(nèi)已分配的所有IP地址分段4322個(gè)，例如至55為其中一個(gè)分段，被分配給大學(xué)使用。如果統(tǒng)一用點(diǎn)分十進(jìn)制表示所有網(wǎng)絡(luò)地址，則所有的IP分段可以表示如下A1’.B1’.C1’.D1’A2.B2.C2.D2A2’.B2’.C2’.D2’……An.Bn..DnAn’.Bn’.’.Dn’At’.Bt’.Ct’.Dt’中〕的函數(shù)值為：F(a.b.c.d)=+〔a-At〕*+(b-Bt)*+(c-Ct)*+(d-Dt)于是我們將每一個(gè)IP都對應(yīng)到一個(gè)整數(shù)，便可以用隨機(jī)算法在其中選取假設(shè)干，逆映射轉(zhuǎn)變?yōu)镮P地址，便得到一個(gè)IP地址集合。去掉此集合中不提供效勞〔包括與網(wǎng)絡(luò)無連接〕的元素，就得到了一個(gè)樣本。由于大約93.6%[14]的通過80端口提供效勞，我們可以順次掃描這些網(wǎng)絡(luò)地址上的80端口。得到的存在效勞的IP地址集合經(jīng)反向域名解析便可得到樣本URL集合。通過對中國國內(nèi)的IP進(jìn)展隨機(jī)取樣并進(jìn)展掃描，我們得到了如下結(jié)果：編號(hào)12345678910隨機(jī)IP數(shù)100K200K300K400K500K600K700K800K900K1M存在數(shù)95172252336418478570652717817表格中間線太粗，而且第三條應(yīng)該是不可見的在上面的統(tǒng)計(jì)中，我們選取了多組不同數(shù)量的隨機(jī)IP，得到的存在效勞的IP地址數(shù)量與隨機(jī)數(shù)大致成比例，說明選出的IP地址具有很好的隨機(jī)性。3.1.2驗(yàn)證由于搜集系統(tǒng)一般以包含域名的URL來記錄網(wǎng)頁，我們要檢驗(yàn)這些網(wǎng)頁是否已被覆蓋，應(yīng)該將其轉(zhuǎn)化為相應(yīng)的域名。由于網(wǎng)絡(luò)中DNS效勞器提供的IP反向解析功能有限，而搜集系統(tǒng)在搜集過程中通常記錄了搜到的網(wǎng)頁域名與IP地址的對應(yīng)關(guān)系，我們可以由此直接檢驗(yàn)被覆蓋的IP地址數(shù)量。我們的目的是對所有的IP地址進(jìn)展建模，接下來的問題應(yīng)該是該用多少數(shù)據(jù)才能滿足要求使得樣本有效。盡管我們就這一問題無法給出準(zhǔn)確的數(shù)量，但是可以從少量的數(shù)據(jù)開場，然后逐步增加數(shù)據(jù)量。如果我們這種通過隨機(jī)產(chǎn)生IP對取樣的方法是正確的，在原先樣本的根底上逐步增加數(shù)據(jù)集將不會(huì)影響信息覆蓋率的結(jié)果。因此，我們可以對樣本容量從小到大的各組數(shù)據(jù)統(tǒng)計(jì)得到的覆蓋率進(jìn)展分析，看是否滿足以上條件。下表是在各組隨機(jī)IP地址樣本中，被搜集系統(tǒng)覆蓋的IP地址所占比例。編號(hào)12345678910存在數(shù)95172252336418478570652717817覆蓋IP數(shù)47913162128364347可以通過最小二乘法對結(jié)果進(jìn)展線性擬合，得到以下的二維圖像。其中，橫軸代表隨機(jī)IP地址樣本容量，縱軸代表搜集系統(tǒng)覆蓋樣本的數(shù)量，直線的斜率則表示信息覆蓋率。從圖中可知，自變量和因變量之間存在很好的一次函數(shù)關(guān)系，覆蓋率根本保持在5.72%左右。由此可以推斷，當(dāng)樣本擴(kuò)展到所有的IP地址時(shí)，WebInfomall的覆蓋率將會(huì)保持在這個(gè)數(shù)量左右。3.1.3模型修正和結(jié)果分析隨機(jī)IP法產(chǎn)生了大量的隨機(jī)IP地址，用這種方法可以很好的對上的所有提供效勞的Web效勞器進(jìn)展取樣；隨著樣本容量的增加，樣本的準(zhǔn)確性也會(huì)增加。但是，這種采樣方法存在一些缺乏，導(dǎo)致信息覆蓋率具有較大偏差。首先，IP地址標(biāo)記的是Web效勞器的網(wǎng)絡(luò)地址，在大多數(shù)情況下，它等同于該效勞器上運(yùn)行的首頁。這使得我們最終得到的網(wǎng)頁集合實(shí)際上是上首頁的一個(gè)樣本。使用IP地址將使得我們對所有的一視**，忽略了的大小之別。一個(gè)只有三五個(gè)網(wǎng)頁的個(gè)人小〔如〕和一個(gè)有著上千網(wǎng)頁的大商業(yè)〔如/，為.sina../的IP地址〕是不等同的，然而這種區(qū)別在隨機(jī)IP地址取樣中無法表達(dá)。另外，大量存在效勞的效勞器并非是實(shí)際意義上的。大多數(shù)Windows系列操作系統(tǒng)自帶的IIS效勞器軟件，Linu*系統(tǒng)自帶安裝的Apache軟件，如此眾多，都會(huì)在缺省條件下提供Web效勞，而這些“首頁〞是沒有實(shí)際意義的測試網(wǎng)頁。類似的，也有大量的在*個(gè)IP地址短暫出現(xiàn)的網(wǎng)頁〔例如臨時(shí)通過效勞共享文件等等〕。在上述隨機(jī)IP取樣方法中，這些根本無效的網(wǎng)頁都被簡單的等同于重要首頁參加了樣本之中。因此，我們有必要對此模型作出修正。既要利用隨機(jī)IP方法具有的優(yōu)異的隨機(jī)性和全局性，又要保證通過隨機(jī)IP地址獲得的網(wǎng)頁的有效性。解決方法是利用網(wǎng)頁之間的關(guān)系，不再將各個(gè)網(wǎng)頁看作獨(dú)立的點(diǎn)，通過發(fā)現(xiàn)網(wǎng)頁中的URL而進(jìn)展適當(dāng)擴(kuò)展。我們在研究中將得到的所有隨機(jī)IP地址視為根本集合R，通過1.0協(xié)議取得這些IP地址上的網(wǎng)頁內(nèi)容，提取出其中的，參加R，作為網(wǎng)頁樣本，如以下圖所示：為了將無效網(wǎng)頁的影響降至最低，還可以對作多級擴(kuò)展。經(jīng)過這種處理后，上述第一種情況可以得到修正，因?yàn)榇蟮氖醉撏ǔ４嬖谳^大的出度；第二種情況中默認(rèn)網(wǎng)頁鏈出的網(wǎng)頁一般指向該軟件生產(chǎn)廠家的首頁，頁面一樣且數(shù)量少，且因其通常在國外故可在研究WebInfomall時(shí)過濾掉。我們從上述的隨機(jī)樣本中抽取了5組，經(jīng)過擴(kuò)展以后的網(wǎng)頁樣本數(shù)量以及覆蓋數(shù)量如下：編號(hào)135710存在數(shù)95252418570817擴(kuò)展樣本容量10842584385954848094覆蓋URL數(shù)17459684112041899在驗(yàn)證的過程中，我們將用IP地址表示的URL轉(zhuǎn)化成域名URL，以便搜集系統(tǒng)的驗(yàn)證。這種轉(zhuǎn)換經(jīng)過了兩級反向解析，第一步是通過網(wǎng)上DNS效勞器的解析，第二步是通過搜集系統(tǒng)保存的域名與IP對應(yīng)數(shù)據(jù)。對得到的結(jié)果作線性擬合，得到的圖幾〔沒有標(biāo)〕如下，從擬合結(jié)果可得到信息覆蓋率約為23.5%?？梢姡趯δＰ妥餍拚?，覆蓋率有很大的增幅；如果考慮到域名與IP之間的動(dòng)態(tài)關(guān)系〔即大量域名的IP是可變的，DNS系統(tǒng)每隔幾分鐘更新一次〕，我們?nèi)コ魳颖局幸訧P表示的URL，數(shù)量覆蓋率數(shù)據(jù)將還會(huì)有小幅度的提高，這才是真正的數(shù)量覆蓋率大小。通過隨機(jī)IP法產(chǎn)生的網(wǎng)頁樣本很好的考察了搜集系統(tǒng)對有向圖*些入度為0或是從出發(fā)頂點(diǎn)無法到達(dá)頂點(diǎn)的覆蓋情況。這啟示我們在搜集網(wǎng)頁過程中，選取適當(dāng)數(shù)量的以隨機(jī)IP法產(chǎn)生的URL作為起始頂點(diǎn)集合的一局部，能提高搜集系統(tǒng)的數(shù)量信息覆蓋率和WebInfomall中網(wǎng)頁信息的有效性。廣度優(yōu)先法隨機(jī)IP法雖然具有較好的隨機(jī)性和全局性，但在使用過程中發(fā)現(xiàn)許多有待改良之處；為了使對的取樣在邏輯構(gòu)造上與實(shí)際情況更加接近，考慮到對隨機(jī)IP法作修正時(shí)對邏輯關(guān)系的利用，我們提出了絕對廣度優(yōu)先搜集取樣的方法。這種方法實(shí)現(xiàn)的實(shí)際就是一個(gè)最原始的搜集系統(tǒng)的工作過程，只是在搜集過程中按照絕對廣度優(yōu)先的方式一級級的擴(kuò)展開去。這種取樣是從局部的角度來進(jìn)展的，原理如以下圖所示。3.2.1取樣我們選取了五個(gè)URL作為起始點(diǎn)，采取上述絕對廣度優(yōu)先搜集網(wǎng)頁的方法分別獲得五組網(wǎng)頁樣本，樣本容量從幾萬到數(shù)十萬不等。算法如下：〔1〕選取*個(gè)網(wǎng)頁S作為起始URL；〔2〕創(chuàng)立隊(duì)列Q存儲(chǔ)未搜集的網(wǎng)頁，S入隊(duì)列；創(chuàng)立構(gòu)造數(shù)組A存儲(chǔ)已經(jīng)搜集過的網(wǎng)頁，按照URL字符串排序；〔3〕取得隊(duì)列頭元素，通過1.0協(xié)議獲取H的源文件，提取出其中包含的的全部URL，并記錄關(guān)系；〔4〕在A中用二分法尋找〔3〕中得到的URL是否已被搜集，如果沒有搜集，則使其進(jìn)入隊(duì)列Q；〔5〕判斷A中的網(wǎng)頁數(shù)量是否已到達(dá)要求，假設(shè)沒有繼續(xù)〔3〕。得到的結(jié)果列表如下：樣本編組12345種子URL.21....sina..擴(kuò)展URL數(shù)668912116291543147238661740783.2.2驗(yàn)證和分析得到網(wǎng)頁樣本之后，我們可以在WebInfomall的網(wǎng)頁數(shù)據(jù)庫中驗(yàn)證被覆蓋的比例。為了快速的檢驗(yàn)數(shù)據(jù)，到達(dá)磁盤性能的極限，我們啟動(dòng)了數(shù)百個(gè)進(jìn)程從URL列表中讀取并通過Hash算法從庫中查找。得到的覆蓋率數(shù)據(jù)如下表所示。對于這組離散的覆蓋率值，我們計(jì)算均值和方差分別為41.6%和0.0230，前者即為通過絕對廣度優(yōu)先法得到的數(shù)量覆蓋率。樣本編組12345擴(kuò)展URL數(shù)66891211629154314723866174078覆蓋數(shù)量26732875626717827306674370數(shù)量覆蓋率40.0%41.4%43.5%37.7%42.7%對于使用這種采樣方法得到的數(shù)量覆蓋率41.6%，較之采用隨機(jī)IP法具有較高的覆蓋率值是可以理解的。因?yàn)檫@兩批數(shù)據(jù)是從兩個(gè)不同的方面說明搜集系統(tǒng)的信息覆蓋情況：隨機(jī)IP法著眼于全局，而絕對廣度優(yōu)先法著眼于局部，更類似于搜索引擎的搜集過程。通常搜集系統(tǒng)是在中的最**通子圖內(nèi)遍歷，絕對廣度優(yōu)先法恰好反映了搜集系統(tǒng)對這一最**通子圖的覆蓋比例。由于這一最**通子圖占據(jù)了中90%[10]左右的網(wǎng)頁，而且我們選取的起始URL均落在這一子圖之內(nèi)，故絕對廣度優(yōu)先法得到的結(jié)論應(yīng)該修正為乘以90%這一參數(shù)才能在全局角度上反映搜集系統(tǒng)的覆蓋率，因此準(zhǔn)確的數(shù)量覆蓋率應(yīng)該是37.4%。當(dāng)樣本容量越大,覆蓋率就應(yīng)該約逼近此值,這從我們采用的大容量樣本(第4組)結(jié)果中已經(jīng)得到了驗(yàn)證。隨機(jī)IP法反映的是搜集系統(tǒng)對中所有點(diǎn)的覆蓋情況，因此這種采樣更容易采集到入度為0或由于其他原因?qū)е滤鸭到y(tǒng)無法遍歷到的網(wǎng)頁〔稱為不可到達(dá)網(wǎng)頁〕。由于不可到達(dá)網(wǎng)頁中大量的點(diǎn)是孤立點(diǎn)，在沒有很好的區(qū)分這些IP地址上所存在的網(wǎng)頁數(shù)據(jù)量的情況下，這種樣本需要經(jīng)過多級擴(kuò)展才能全面的反映真實(shí)的。也就是說，如果對初始URL不斷作擴(kuò)展，最后的數(shù)據(jù)會(huì)不斷接近37.4%，這在我們作第一級擴(kuò)展之后已經(jīng)有了好的反映。我們可以預(yù)測到，如果將兩種采樣方法的優(yōu)點(diǎn)結(jié)合起來，通過隨機(jī)IP法產(chǎn)生URL集合作為絕對廣度優(yōu)先法取樣的種子集合再進(jìn)展擴(kuò)展，在樣本容量足夠大之后，最后的數(shù)量覆蓋率數(shù)據(jù)應(yīng)該與通過文獻(xiàn)[10]的工作做的估計(jì)相符，在37.4%附近。質(zhì)量覆蓋率考察搜集系統(tǒng)在質(zhì)量上對的信息覆蓋率，需要通過有效的網(wǎng)頁重要性評測方法找到一組重要網(wǎng)頁樣本。盡管通?？梢酝ㄟ^用戶評選提交的方式得到他們在瀏覽網(wǎng)頁過程中發(fā)現(xiàn)的重要網(wǎng)頁集合作為樣本，但在本文研究中，為了保證樣本的隨機(jī)性和客觀性，我們采用兩類基于對構(gòu)造的分析而對中重要網(wǎng)頁進(jìn)展取樣的有效方法。這些方法的根本思想都是找到一組具有較強(qiáng)關(guān)系的網(wǎng)頁〔初始取樣〕，通過基于分析的網(wǎng)頁權(quán)值算法，求出其中所有網(wǎng)頁的相對重要性值，從而可以對網(wǎng)頁進(jìn)展排序取出前假設(shè)干位作為重要網(wǎng)頁的樣本。這些經(jīng)典的權(quán)值算法包括斯坦福大學(xué)開發(fā)Google系統(tǒng)提出的PageRank算法[15]和IBM研究院開發(fā)Clever系統(tǒng)提出的HITS算法[16]〔Hyperlink-InducedTopicSearch〕，它們都是基于對有向圖構(gòu)造的理解提出的。網(wǎng)頁重要性評測方法上的信息資源數(shù)量如此之大，無論是搜集系統(tǒng)本身還是承受返回結(jié)果的查詢用戶，都要求有好的方法對網(wǎng)頁集合按照重要性進(jìn)展排序，因?yàn)橄到y(tǒng)搜集的和用戶關(guān)心的一般都只是其中的*一子集。準(zhǔn)確的區(qū)分出重要的網(wǎng)頁加以優(yōu)先搜集，準(zhǔn)確的計(jì)算出重要的網(wǎng)頁返回給用戶優(yōu)先瀏覽，要做到這些，我們需要適宜的網(wǎng)頁重要性評定方法。這里，網(wǎng)頁的重要性用權(quán)值來衡量，權(quán)值越高表示網(wǎng)頁越重要。我們可以從三個(gè)角度來分析網(wǎng)頁的權(quán)值，討論它的相關(guān)因素。從網(wǎng)頁本身的唯一屬性URL出發(fā)來考慮：網(wǎng)頁的權(quán)值可以從URL的屬性中得到反映。一般而言，URL所在的域名越短，所在上相對于根目錄的層次越淺，網(wǎng)頁的權(quán)值越大。例如，大學(xué)的首頁../一般被認(rèn)為比大學(xué)計(jì)算機(jī)系首頁..的權(quán)值要高；而../page1.htm比../dir1/dir2/page2.htm的權(quán)值顯然也要高。這一原理可以在網(wǎng)頁搜集過程中加以利用。從網(wǎng)頁作為有向圖的一個(gè)節(jié)點(diǎn)來考慮：網(wǎng)頁的權(quán)值可以根據(jù)它的認(rèn)可度來判斷，由于網(wǎng)頁間的通常代表著認(rèn)可度的傳遞，我們可以統(tǒng)計(jì)網(wǎng)頁的入度來評判其重要性。如果網(wǎng)頁A上存在網(wǎng)頁B的URL，排除掉純粹導(dǎo)航的因素，表示著網(wǎng)頁A的作者存在對網(wǎng)頁B的認(rèn)可；而這種認(rèn)可的增多則意味著網(wǎng)頁B權(quán)值的上升。因此，入度越大，權(quán)值通常越高。從網(wǎng)頁本身的內(nèi)容出發(fā)來考慮：在搜索引擎搜集網(wǎng)頁的過程中，通常都要保存網(wǎng)頁的關(guān)鍵詞或全文信息，以便建立索引。由于網(wǎng)頁的重要性一般又對應(yīng)著用戶較高的關(guān)心程度，我們可以通過對用戶遞交給搜索引擎的查詢詞與網(wǎng)頁的內(nèi)容〔全文或關(guān)鍵詞〕進(jìn)展匹配，匹配程度越高意味著網(wǎng)頁的權(quán)值越高。當(dāng)然，這要求用戶遞交的查詢是希望得到大量相關(guān)網(wǎng)頁的寬主題查詢。該情況在Kleinberg的論文[18]中有詳細(xì)討論。當(dāng)前大多數(shù)搜索引擎所采用的網(wǎng)頁權(quán)值計(jì)算方法正是上面提到的的PageRank算法和HITS算法兩種，它們分別利用了上述中的后兩種原理，而且對其間的網(wǎng)頁關(guān)系作了更深層次的挖掘。PageRank算法[15]是一種利用網(wǎng)頁間關(guān)系進(jìn)展權(quán)值計(jì)算的典型方法，它是學(xué)術(shù)論文引用統(tǒng)計(jì)原理在上的推廣，它統(tǒng)計(jì)每個(gè)網(wǎng)頁被引用的次數(shù)，但每一次引用又因引用者權(quán)值的不同而不同；而HITS算法[17]將網(wǎng)頁的權(quán)值分為目錄型權(quán)值和權(quán)威型權(quán)值分別進(jìn)展計(jì)算，目錄型權(quán)值高表示它鏈向很多權(quán)威型權(quán)值高的網(wǎng)頁，而權(quán)威型權(quán)值高則表示它被很多目錄型權(quán)值高的網(wǎng)頁所到。〔目錄型、權(quán)威型沒有解釋〕基于這兩種權(quán)值算法，我們提出了下面的兩類質(zhì)量覆蓋率確定方法。廣度優(yōu)先法4.2.1取樣PageRank算法根據(jù)網(wǎng)頁間的關(guān)系來評判網(wǎng)頁的重要性，因此我們選取的初始網(wǎng)頁集合必須和有著大致一樣的構(gòu)造，保證初始樣本中每個(gè)網(wǎng)頁的入度與實(shí)際互聯(lián)網(wǎng)絡(luò)相差不大，或者網(wǎng)頁入度的相對大小變化不大。這樣才能使得初始樣本中的相對網(wǎng)頁權(quán)值保持不變。我們可以利用絕對廣度優(yōu)先的方法，從初始URL開場向外遍歷。隨著初始樣本容量的加大，每個(gè)樣本網(wǎng)頁的入度越來越接近于它在中的實(shí)際入度，樣本網(wǎng)頁的入度相對大小也越來越固定。我們以數(shù)量覆蓋率研究中的廣度優(yōu)先法所獲樣本作為初始樣本，它們的數(shù)量一般在數(shù)十萬，已能根本保證其中相當(dāng)數(shù)量網(wǎng)頁的相對入度大小。用PageRank算法從中計(jì)算選出權(quán)值在前M位的網(wǎng)頁集合作為樣本。顯然，M值越小，樣本的有效性越容易得到保證。4.2.2PageRank算法假定網(wǎng)頁A在里面被網(wǎng)頁T1…Tn所鏈到，C(A)表示從A鏈出去的網(wǎng)頁數(shù)量〔即出度〕，則A的權(quán)值可以表示如下：PR(A)=[17]這種根本思想可以從以下圖中表達(dá)：考慮到用戶從Ti出發(fā)只有d〔0<d<1〕的可能性繼續(xù)瀏覽網(wǎng)頁，則相應(yīng)的權(quán)值也只有相應(yīng)比例的一局部傳到A，因此PR(A)可以調(diào)整如下：PR(A)=〔1-d〕+d[15]如果將所有的網(wǎng)頁依次編號(hào)為1至N，他們的權(quán)值可以看作矢量W，則W的轉(zhuǎn)秩〔是這個(gè)秩嗎.〕為〔PR〔1〕，PR〔2〕，……，PR〔N〕〕；考慮矩陣R，如果存在從網(wǎng)頁i到網(wǎng)頁j的，則R[i,j]=1/C(i)，否則R[i,j]=0；則所有的網(wǎng)頁權(quán)值可以寫成如下式子：W=d*W×R+E其間，E為常數(shù)向量。我們可以用迭代的方法求W的值,反復(fù)計(jì)算W〔i+1〕=d*W(i)×R+E，直到W經(jīng)判斷已經(jīng)收斂。事實(shí)上，這里的d已經(jīng)成了一個(gè)收斂因子，盡管其實(shí)際意義為繼續(xù)瀏覽網(wǎng)頁的概率。沒看懂4.2.3算法實(shí)現(xiàn)和試驗(yàn)結(jié)果根據(jù)以上算法的需求，我們在網(wǎng)頁搜集過程中記錄了所有搜集到的網(wǎng)頁間的關(guān)系，隨著這個(gè)樣本網(wǎng)頁群體的增大，它在關(guān)系上將與越來越接近。出于對系統(tǒng)內(nèi)存需求的考慮，所有的網(wǎng)頁都被以整數(shù)統(tǒng)一編號(hào)而代替其URL字符串；網(wǎng)頁之間的關(guān)系以二元組<id1,id2>的形式存入關(guān)系數(shù)據(jù)庫。當(dāng)網(wǎng)頁的數(shù)量足夠大時(shí)，所有的網(wǎng)頁及其屬性無法一次全部存入內(nèi)存中，故需要分塊對矩陣進(jìn)展迭代。具體的實(shí)現(xiàn)算法如下：創(chuàng)立數(shù)據(jù)構(gòu)造存儲(chǔ)網(wǎng)頁的整數(shù)ID、權(quán)值、出度、入度以及所有鏈入網(wǎng)頁的ID，以此作為矢量W的單元；根據(jù)網(wǎng)頁的平均入度[2]估計(jì)系統(tǒng)內(nèi)存一次能存放的URL數(shù)量N，在我們的系統(tǒng)中，估計(jì)約為1MB；從數(shù)據(jù)庫中導(dǎo)出N個(gè)URL到內(nèi)存，按ID排序；再將全部的關(guān)系導(dǎo)入，對于上述N中的每一個(gè)，填充進(jìn)它的屬性；對于N中的每一個(gè)，用二分法找到它的鏈入U(xiǎn)RL的數(shù)組下標(biāo)，如果不在當(dāng)前內(nèi)存中則其權(quán)值以平均值計(jì)算，運(yùn)用PageRank算法計(jì)算其權(quán)值；如果全部的URL都已經(jīng)導(dǎo)入計(jì)算過，則對該矢量進(jìn)展處理使得所有URL的權(quán)值之和為1；否則繼續(xù)〔4〕；如果先后兩次計(jì)算的W距離足夠小，則對權(quán)值排序選取前M個(gè)輸出到文件；否則繼續(xù)〔3〕。將輸出文件中的所有URL整數(shù)ID轉(zhuǎn)換為URL字符串。實(shí)驗(yàn)在RedHat7.2系統(tǒng)上運(yùn)行，主要硬件指標(biāo)是1GB內(nèi)存，P=3\*ROMANIII550CPU。我們以數(shù)量覆蓋率計(jì)算中得到的五組樣本作為初始樣本，如果選擇權(quán)值排序位于前面約5%左右的網(wǎng)頁作為重要網(wǎng)頁的標(biāo)準(zhǔn)，得到了如下結(jié)果：樣本編組12345種子URL.21....sina..初始擴(kuò)展數(shù)量66891211629154314723866174078PageRank取數(shù)352384978702334368408占前百分之幾5.3%4.0%5.6%4.6%4.8%覆蓋URL數(shù)154240324754177173456質(zhì)量覆蓋率43.8%47.5%54.6%53.0%41.1%取前M個(gè),為什么每組占前百分之幾不一樣。對五組樣本檢驗(yàn)得到的質(zhì)量覆蓋率計(jì)算均值和方差分別是48.0%和0.0579。為了保證所求樣本網(wǎng)頁的重要性有效，我們選取了上述樣本中的第2組和第4組，改變判斷重要性的標(biāo)準(zhǔn)，質(zhì)量覆蓋率隨此而變化的情形如下表所示。對于第二組網(wǎng)頁樣本：重要網(wǎng)頁個(gè)數(shù)18113434511768088497占前百分之幾0.86%1.62%2.42%3.22%4.02%覆蓋網(wǎng)頁數(shù)11452068278833634032質(zhì)量覆蓋率63.2%60.2%54.5%49.4%47.5% 以下圖是隨著重要性標(biāo)準(zhǔn)的放松，質(zhì)量覆蓋率的變化情況：對于第四組網(wǎng)頁樣本：重要網(wǎng)頁個(gè)數(shù)1732133436491986445079155占前百分之幾2.39%4.62%6.80%8.90%10.9%覆蓋網(wǎng)頁數(shù)990317717247183112636780質(zhì)量覆蓋率57.2%53.0%50.2%48.3%46.5% 以下圖是隨著重要性標(biāo)準(zhǔn)的放松，質(zhì)量覆蓋率的變化情況： 從這兩*圖中可以看出，當(dāng)重要標(biāo)準(zhǔn)很苛刻時(shí)重要網(wǎng)頁樣本容量很小，此時(shí)搜集系統(tǒng)的覆蓋率很高；但隨著重要標(biāo)準(zhǔn)的放松導(dǎo)致樣本容量的增大，搜集系統(tǒng)的質(zhì)量覆蓋率會(huì)越來越低；當(dāng)重要性的標(biāo)準(zhǔn)放至最低，即所有網(wǎng)頁的地位平等時(shí)，質(zhì)量覆蓋率變?yōu)樽钚。瑸閿?shù)量覆蓋率值。這兩*圖中都顯示，當(dāng)重要標(biāo)準(zhǔn)降至約5%左右時(shí)，曲線開場逐漸變得平緩，因此此點(diǎn)的覆蓋率數(shù)據(jù)48.0%無疑最適合作為我們所測的的搜集系統(tǒng)質(zhì)量覆蓋率。主題查詢法網(wǎng)頁具有作為有向圖構(gòu)造中一個(gè)頂點(diǎn)的相關(guān)邏輯屬性，它又可根據(jù)其內(nèi)容本身而屬于人類社會(huì)信息資源的*一主題類別。例如，網(wǎng)頁可以根據(jù)其內(nèi)容分為屬于社會(huì)、人文或休閑娛樂等類別以及它們的子類的網(wǎng)頁。基于這一點(diǎn)的考慮，我們的研究工作中采取了通過主題查詢獲得重要網(wǎng)頁樣本的方法。這類似于文獻(xiàn)[19]的工作中HITS算法選擇的網(wǎng)頁集合所采用的方法。由于上同一主題的網(wǎng)頁之間具有較強(qiáng)的關(guān)系[19]，我們可用HITS算法對此網(wǎng)頁集合進(jìn)展權(quán)值計(jì)算，進(jìn)展排序后得到前假設(shè)干網(wǎng)頁作為在這一主題類別的重要網(wǎng)頁樣本。4.3.1取樣假設(shè)我們希望得到關(guān)于主題T的重要網(wǎng)頁樣本，我們一般會(huì)通過遞交假設(shè)干與T相關(guān)的查詢詞Q提交給搜索引擎，它返回的網(wǎng)頁集合為R。對于通常的搜索引擎，R的網(wǎng)頁一般都具有和T較高的相關(guān)度，因?yàn)椴樵冎型ǔＪ褂米址ヅ?，使得返回的網(wǎng)頁中大多含有Q之類的字樣。但是，也有大量的重要網(wǎng)頁不適合這種情況，例如天網(wǎng)系統(tǒng)的主頁并沒有搜索引擎的字樣供匹配。出于對這種特殊現(xiàn)象的考慮，需要對R以適當(dāng)?shù)臄U(kuò)展，參加R網(wǎng)頁鏈出去的網(wǎng)頁和鏈向R元素的網(wǎng)頁得到初始樣本S，如圖示：我們選擇了八個(gè)主題的查詢詞遞交給天網(wǎng)搜索引擎，在用以上的方式對返回結(jié)果進(jìn)展擴(kuò)展之后，得到了八組初始網(wǎng)頁樣本如下：樣本編組12345678查詢詞大學(xué)考研股票Linu*教程聯(lián)想集團(tuán)三個(gè)代表世界杯返回?cái)?shù)量18021802180218021355180218021802擴(kuò)展數(shù)量11667193791340311006265481549811608208234.3.2HITS算法上圖中的S正是我們用HITS算法進(jìn)展權(quán)值計(jì)算的對象。對于S中的任意一個(gè)元素P，設(shè)H(P)表示其目錄型權(quán)值〔HubWeight〕，A(P)表示其權(quán)威型權(quán)值〔AuthorityWeight〕，F(xiàn)1,F2,……,Fm是鏈到P的網(wǎng)頁，T1,T2,……,Tn是從P鏈出的網(wǎng)頁，則A(P)和H(P)可以從下面的式子計(jì)算：A(P)=H(P)=同PageRank算法類似，我們可以將所有的網(wǎng)頁的目錄型權(quán)值看作矢量H，將所有網(wǎng)頁的權(quán)威型權(quán)值看作矢量A，設(shè)樣本中所有網(wǎng)頁及關(guān)系構(gòu)成的有向圖的鄰接矩陣為M，考慮到兩個(gè)URL之間最多有一個(gè)使得假設(shè)存在網(wǎng)頁i到網(wǎng)頁j的則M[i,j]=1否則M[i,j]=0，則上面的式子可以寫成：A=M×HH=M×A由此兩式可得A=M×M×A，即實(shí)際上A是M×M的特征向量；同理H是M×M的特征向量，我們因此也可以用冪法或QR算法等來通過迭代來求得A和H的值。但考慮到系統(tǒng)內(nèi)存對初始樣本容量的限制，假設(shè)數(shù)量很大的時(shí)候需要分塊對兩個(gè)矩陣進(jìn)展迭代。4.3.3試驗(yàn)結(jié)果在我們的研究工作中，我們沒有通過計(jì)算特征向量而采取了根據(jù)前一組公式直接進(jìn)展迭代計(jì)算A和H值的方法，具體的實(shí)現(xiàn)算法如下：采集初始樣本時(shí)將所有的URL編號(hào)存入數(shù)據(jù)庫，同時(shí)存入U(xiǎn)RL之間的關(guān)系；創(chuàng)立相關(guān)的數(shù)據(jù)構(gòu)造存儲(chǔ)每個(gè)URL的Hub和Auth權(quán)值及關(guān)系，從數(shù)據(jù)庫中導(dǎo)出所有URL屬性并填充到數(shù)據(jù)構(gòu)造中；給予H和A*個(gè)初始值，分別計(jì)算A〔i+1〕=M×H〔i〕和H(i+1)=M×A(i)，直至A(i+1)和A(i)的距離足夠小為止；分別對Auth和Hub值進(jìn)展冒泡排序，輸出前假設(shè)干個(gè)URL到文件中。在確定重要網(wǎng)頁的界限時(shí)，我們選取的是初始網(wǎng)頁樣本中權(quán)值排在前面約15%左右的局部，大致與搜索引擎響應(yīng)查詢詞返回的網(wǎng)頁數(shù)量相當(dāng)。即搜索引擎就此主題返回*個(gè)重要網(wǎng)頁，我們經(jīng)過計(jì)算后也給出*個(gè)“真正〞重要的網(wǎng)頁，檢查搜集系統(tǒng)覆蓋其中的比例作為質(zhì)量覆蓋率。對于具有較高Hub權(quán)值的重要網(wǎng)頁，實(shí)驗(yàn)的數(shù)據(jù)如下：樣本編組12345678查詢詞大學(xué)考研股票Linu*教程聯(lián)想集團(tuán)三個(gè)代表世界杯初始數(shù)量1166719379134031100626548154981160820823Hub取數(shù)16711701153210401508142818591961覆蓋數(shù)量958956578312772514793651覆蓋率57.3%56.2%37.7%30%51.2%36.0%42.7%33.2%八組樣本所得的質(zhì)量覆蓋率分別為表幾所示，它們的均值和方差分別為43.0%和0.106，前者即為搜集系統(tǒng)對Hub型重要網(wǎng)頁的覆蓋率。對于具有較高Auth權(quán)值的重要網(wǎng)頁，實(shí)驗(yàn)的數(shù)據(jù)如下：樣本編組12345678查詢詞大學(xué)考研股票Linu*教程聯(lián)想集團(tuán)三個(gè)代表世界杯初始數(shù)量1166719379134031100626548154981160820823Auth取數(shù)1400157211249301197104715811985覆蓋數(shù)量9439303853016926319271052覆蓋率67.4%59.2%34.3%32.4%57.8%60.3%58.6%53.0%八組樣本所得的質(zhì)量覆蓋率分別為，它們的均值為，表幾所示方差為52.9%和0.1269，前者即為搜集系統(tǒng)對Auth型重要網(wǎng)頁的質(zhì)量覆蓋率。4.3.3修正與分析在上述的HITS算法中，我們將所有的地位視為平等，而事實(shí)上并非如此，我們可以從它的導(dǎo)向詞與查詢詞的匹配度的不同處著手，這在SoumenChakrabarti和ByronDom的工作[19]中有論述。這里的導(dǎo)向詞指的是該出現(xiàn)在網(wǎng)頁源文件的地方前后約150個(gè)字符之內(nèi)的信息，它們一般含有該網(wǎng)頁內(nèi)容或?qū)傩缘恼f明。即，*個(gè)網(wǎng)頁中兩個(gè)url1和url2，如果url1的導(dǎo)向詞中出現(xiàn)“大學(xué)〞10次，而url2的導(dǎo)向詞中未出現(xiàn)此字眼，在查詢的主題是“大學(xué)〞時(shí)，url1的地位要高于url2。我們稱以此為根底的算法為擴(kuò)展HITS算法。假定查詢詞是Q，存在網(wǎng)頁A到B的，提取出網(wǎng)頁A中B的導(dǎo)向詞，設(shè)F(A,B)為Q在導(dǎo)向詞中匹配的次數(shù)，則可以對HITS算法作如下修正：A(P)=H(P)=我們用這種算法對上述的8組初始樣本進(jìn)展計(jì)算，然后分別選取Hub權(quán)值和Auth權(quán)值在前假設(shè)干位的重要網(wǎng)頁作為重要網(wǎng)頁樣本，從Hub和Auth兩個(gè)角度求得的搜集系統(tǒng)信息質(zhì)量覆蓋率均值分別為46.2%和50.3%。從實(shí)驗(yàn)數(shù)據(jù)可以看出，廣度優(yōu)先法和主題查詢法所求得的質(zhì)量覆蓋率數(shù)據(jù)能夠很好的符合，WebInfomall的搜集系統(tǒng)對普通的重要網(wǎng)頁覆蓋率在50%左右。如果對重要網(wǎng)頁的標(biāo)準(zhǔn)提高一些，則質(zhì)量覆蓋率的數(shù)據(jù)還要更高。結(jié)論本文針對搜索引擎搜集子系統(tǒng)對的信息覆蓋能力，創(chuàng)立了信息覆蓋率的量化研究模型。在這個(gè)模型中，我們提出兩套取樣方法，采取了兩類典型的網(wǎng)頁權(quán)值算法，分別從量和質(zhì)的角度上分析計(jì)算搜集系統(tǒng)的信息覆蓋率。運(yùn)用這個(gè)模型，我們針對中國Web進(jìn)展樣本采集，從而對北大天網(wǎng)系統(tǒng)的WebInfomall平臺(tái)所存儲(chǔ)的中國國內(nèi)網(wǎng)頁數(shù)據(jù)的信息覆蓋率進(jìn)展評估。得到的數(shù)據(jù)顯示，在數(shù)量上WebInfomall平臺(tái)覆蓋了中國國內(nèi)網(wǎng)頁總數(shù)的37%，而在質(zhì)量上覆蓋了重要網(wǎng)頁總數(shù)的50%左右。這個(gè)數(shù)據(jù)也顯示天網(wǎng)的覆蓋率與國際上諸如Google的幾個(gè)大搜索引擎系統(tǒng)相當(dāng)，尤其是在數(shù)量覆蓋率這一方面。對于同一類型的信息覆蓋率，采用不同取樣和權(quán)值計(jì)算方法所驗(yàn)證得到的數(shù)據(jù)能夠很好的符合，證明了信息覆蓋率模型的正確性以及所獲得WebInfomall平臺(tái)信息覆蓋率的準(zhǔn)確性。實(shí)驗(yàn)結(jié)果肯定了天網(wǎng)搜集系統(tǒng)的較強(qiáng)搜集能力，并對進(jìn)一步改良這種搜集能力及相關(guān)WebInfomall平臺(tái)的性能提供了重要的客觀依據(jù)。本文缺乏之處在于對網(wǎng)頁重要性的定性標(biāo)準(zhǔn)不夠嚴(yán)密，對于PageRank算法，我們選取了權(quán)值位于前5%的網(wǎng)頁作為重要網(wǎng)頁；而對于HITS算法計(jì)算的查詢所得擴(kuò)展網(wǎng)頁集合，我們選取重要的標(biāo)準(zhǔn)是和初始返回結(jié)果相等的量，約占權(quán)值排序后前