社會(huì)環(huán)境下網(wǎng)頁重要性的研究畢業(yè)論文

1、<p>　　社會(huì)環(huán)境下網(wǎng)頁重要性的研究</p><p><b>　　中文摘要　</b></p><p>　　近年來，隨著internet的不斷發(fā)展，Web已經(jīng)成為人們的重要信息來源，為人們提供了豐富的信息資源。與此同時(shí)，它所具有的海量數(shù)據(jù)、復(fù)雜性、極強(qiáng)的動(dòng)態(tài)性和用戶的多態(tài)性等特點(diǎn)也給We資源的發(fā)展發(fā)掘造成了相當(dāng)?shù)碾y度。通過分析和研究作為一種相當(dāng)成功的基于超鏈

2、分析的算法Google PageRank，可以有效地衡量網(wǎng)頁重要度權(quán)值 ,然而進(jìn)一步的研究也表明 ,這種純粹依賴于超鏈分析的算法由于沒有考慮到網(wǎng)頁訪問者對(duì)網(wǎng)頁重要度權(quán)值的影響 ,所以在一定程度上會(huì)造成偏差 。因此 ,合理的將兩者進(jìn)行結(jié)合,充分利用訪問者的知識(shí)水平和網(wǎng)頁內(nèi)容特征對(duì)PageRank 算法進(jìn)行改進(jìn)，得出最終搜索引擎排序優(yōu)化算法，可以極大的提高這種算法的有效性和正確性。</p><p>　　關(guān)鍵詞：超鏈分

3、析，PageRank，算法，訪問者，優(yōu)化</p><p><b>　　ABSTRACT </b></p><p>　　In recent years, along with the continuous development of the Internet, Web has become an important source of information, the

4、 people for the people provides abundant information resources. Meanwhile, it has the mass data, complexity, and strong dynamics and characteristics of the user to ship polymorphism of the development of resources of exc

5、avation caused considerable difficulty. Through the analysis and research as a fairly successful based on the analysis of the algorithm is hyperlinked Pag</p><p>　　Keywords: hyperlink analysis algorithm, th

6、e visitor, PageRank optimization</p><p><b>　　目錄</b></p><p>　　1．Google 搜索引擎簡介5</p><p>　　1.1 Google的軟件文化理念5</p><p>　　1.2 搜索引擎的分類5</p><p>　　1.

7、3 Google搜索引擎工作原理[3]6</p><p>　　2．傳統(tǒng)Google PageRank算法分析9</p><p>　　2.1 傳統(tǒng)Google PageRank算法概述[4]9</p><p>　　2.2 傳統(tǒng) PageRank算法回顧10</p><p>　　2.2.1傳統(tǒng) PageRank算法代數(shù)表達(dá)形式10<

8、;/p><p>　　2.2.2 傳統(tǒng) PageRank算法向量表達(dá)形式12</p><p>　　2.3 傳統(tǒng)Google PageRank的缺陷和改進(jìn)方法13</p><p>　　3．Google PageRank 算法改進(jìn)15</p><p>　　3.1由訪問者知識(shí)水平及其投票的情況決定網(wǎng)頁排名的 PageRank 算法15</p

9、><p>　　3.1.1 算法中PR值的含義15</p><p>　　3.1.2 從投票角度分析算法的本質(zhì)15</p><p>　　3.1.3 算法改進(jìn)的詳細(xì)設(shè)計(jì)思路16</p><p>　　3.2 計(jì)算每個(gè)訪問者的PageRank值17</p><p>　　3.2.1 計(jì)算訪問者PR值的數(shù)學(xué)表達(dá)式17</

10、p><p>　　3.2.2 訪問者PR值的循環(huán)收斂計(jì)算方法19</p><p>　　3.2.3訪問者PR值算法的簡單模型21</p><p>　　3.2.4 Visual Basic編程驗(yàn)證算法收斂23</p><p>　　3.2.5 matlab編程驗(yàn)證算法收斂29</p><p>　　3.3 網(wǎng)頁P(yáng)R值的計(jì)算方

11、法37</p><p>　　3.3.1 計(jì)算網(wǎng)頁P(yáng)R值的理論基礎(chǔ)37</p><p>　　3.3.2 建立數(shù)學(xué)模型38</p><p>　　3.3.3 Visual Basic編程驗(yàn)證算法的正確性39</p><p>　　3.3.4 matlab編程驗(yàn)證算法的正確性42</p><p>　　4．改進(jìn)算法的事實(shí)

12、可行性44</p><p>　　5．將改進(jìn)算法與Google PageRank傳統(tǒng)算法結(jié)合的最完美排序方法46</p><p><b>　　6．小結(jié)48</b></p><p><b>　　附錄49</b></p><p><b>　　參考文獻(xiàn)51</b></p

13、><p><b>　　致謝52</b></p><p>　　1．Google 搜索引擎簡介</p><p>　　1.1 Google的軟件文化理念</p><p>　　根據(jù)《中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告 ( 2005/1) 》用戶在互聯(lián)網(wǎng)上獲取信息最常用的方法是通過搜索引擎:占70. 7 %。遠(yuǎn)遠(yuǎn)高于位于第二位的直接訪問已

14、知的網(wǎng)站:占24. 6% 。搜索引擎的后起之秀 Google 每天處理的搜索請(qǐng)求已達(dá) 2 億次?，F(xiàn)在全球有75%的網(wǎng)上信息搜索是靠Google的技術(shù)完成，大大促進(jìn)了人類的信息搜索的效率。而作為品牌價(jià)值，僅Google這個(gè)名字的無形資產(chǎn)，竟出人意料地在如此短的時(shí)間，一下子超過了蘋果、IMB、可口可樂，真正實(shí)現(xiàn)了跳躍性的發(fā)展。Google主頁面不以花哨取勝，而以功能表現(xiàn)為本。它的先進(jìn)的軟件理念正是建立在軟件功能模塊上，研究其功能特點(diǎn)，我們發(fā)

15、現(xiàn)Google技術(shù)上的先進(jìn)，來自于文化理念上的先進(jìn)，并敢于打破傳統(tǒng)獨(dú)樹一幟[1]。</p><p>　　首先，Google用先進(jìn)的PageRank技術(shù)理念，以平等、實(shí)用、公正為組織原則，優(yōu)化整合全球Web網(wǎng)頁資源。在搜索方法上，Google更是化繁為簡，為大多數(shù)網(wǎng)民利益考慮，做到軟件使用大眾化。其次，在對(duì)待語言工具的問題上，不搞大國沙文主義，真正擯棄了語言上的貴賤之分，將多種語言平等地整合在同一界面，實(shí)現(xiàn)了以人為

16、本的軟件理念。同時(shí)注重創(chuàng)新，注意吸納新網(wǎng)站，以組成世界信息大家庭，并且充分尊重新網(wǎng)站的特殊要求和選擇權(quán)利，再進(jìn)行搜索引擎數(shù)據(jù)庫的錄入處理。再次，Google的中文搜索引擎的完美設(shè)計(jì)，體現(xiàn)了設(shè)計(jì)者的國際市場(chǎng)合作精神，Google搜索引擎對(duì)中文的支持力度，使它成為目前是收集亞洲網(wǎng)站最多的搜索引擎，同時(shí)能夠取他人之長，與他人聯(lián)手，以團(tuán)隊(duì)合作精神推出新技術(shù)新功能。</p><p>　　1.2 搜索引擎的分類</p&

17、gt;<p>　　搜索引擎是指因特網(wǎng)上專門提供查詢服務(wù)的一類網(wǎng)站,它以一定的策略在互聯(lián)網(wǎng)中搜集、發(fā)現(xiàn)信息，對(duì)信息進(jìn)行理解、提取、組織和處理,并為用戶提供檢索服務(wù)，從而起到信息導(dǎo)航的作用。</p><p>　　搜索引擎系統(tǒng)可以分為：目錄式搜索引擎、機(jī)器人搜索引擎和元搜索引擎。</p><p>　　目錄式搜索引擎因?yàn)榧尤肓巳说闹悄?，所以信息?zhǔn)確、導(dǎo)航質(zhì)量高，缺點(diǎn)是需要人工介入、維

18、護(hù)量大、信息量少、信息更新不及時(shí)。</p><p>　　機(jī)器人搜索引擎:是指通過網(wǎng)絡(luò)搜索軟件(又稱為網(wǎng)絡(luò)蜘蛛[2],網(wǎng)絡(luò)爬行機(jī)器人,網(wǎng)絡(luò)搜索機(jī)器人) 或網(wǎng)站登錄等方式 ,以某種策略自動(dòng)地在互聯(lián)網(wǎng)中搜集和發(fā)現(xiàn)信息,經(jīng)過加工處理后建庫,從而能夠?qū)τ脩籼岢龅母鞣N查詢作出響應(yīng),提供用戶所需的信息。該類搜索引擎的優(yōu)點(diǎn)是信息量大、更新及時(shí)、毋需人工干預(yù)，缺點(diǎn)是返回信息過多，有很多無關(guān)信息，用戶必須從結(jié)果中進(jìn)行篩選。這類搜索引

19、擎的代表是： AltaVista 、Northern Light 、Excite 、Infos2 eek 、Inktomi 、FAST、Lycos 、Google ; 國內(nèi)代表為：“天網(wǎng)”、 “百度”等。本文論述的Google 搜索引擎就是機(jī)器人搜索引擎，通過網(wǎng)絡(luò)蜘蛛(Crawler) 搜集和發(fā)現(xiàn)網(wǎng)頁排序所需要的信息。</p><p>　　目錄式搜索引擎和機(jī)器人搜索引擎，各有優(yōu)缺點(diǎn)，應(yīng)用都很廣泛。機(jī)器人搜索引擎的

20、自動(dòng)化程度比目錄式搜索引擎高。網(wǎng)絡(luò)信息量太大了，用計(jì)算機(jī)代替人去查找，可以節(jié)省大量的人力。</p><p>　　元搜索引擎：這類搜索引擎沒有自己的數(shù)據(jù)，而是將用戶的查詢請(qǐng)求同時(shí)向多個(gè)搜索引擎遞交，將返回的結(jié)果進(jìn)行重復(fù)排除、重新排序等處理后，作為自己的結(jié)果返回給用戶。服務(wù)方式為面向網(wǎng)頁的全文檢索。這類搜索引擎的優(yōu)點(diǎn)是返回結(jié)果的信息量更大、更全，缺點(diǎn)是不能夠充分使用搜索引擎的功能，用戶需要做更多的篩選。這類搜索引擎的

21、代表是WebCrawler 、InfoMarket 等 .</p><p>　　1.3 Google搜索引擎工作原理[3]</p><p>　　搜索引擎一般由網(wǎng)絡(luò)爬行機(jī)器人crawler、知識(shí)庫Repository、索引系統(tǒng)(包括索引器indexer，桶barrels ,文件索引等)、排序器Sorter和搜索器Searcher 5個(gè)部分組成。</p><p>　

22、　Google PageRank一般一年更新四次(由crawler程序的效率及搜索引擎的規(guī)模決定)，所以剛上線的新網(wǎng)站不可能獲得PR值。你的網(wǎng)站很可能在相當(dāng)長的時(shí)間里面看不到PR值的變化，特別是一些新的網(wǎng)站。PR值暫時(shí)沒有，這不是什么不好的事情，耐心等待就好了。Google PageRank每更新一次都是按照以下的步驟進(jìn)行：</p><p>　　(1)Google使用高速的分布式爬行器(Crawler)系統(tǒng)中的漫

23、游遍歷器(Googlebot)定時(shí)地遍歷網(wǎng)頁，將遍歷到的網(wǎng)頁送到存儲(chǔ)服務(wù)器(Store Server)中。</p><p>　　(2)存儲(chǔ)服務(wù)器使用zlib格式壓縮軟件將這些網(wǎng)頁進(jìn)行無損壓縮處理后存入數(shù)據(jù)Repository中。Repository獲得了每個(gè)網(wǎng)頁的完全Html代碼后，對(duì)其壓縮后的網(wǎng)頁及URL進(jìn)行分析，記錄下網(wǎng)頁長度、URL、URL長度和網(wǎng)頁內(nèi)容，并賦予每個(gè)網(wǎng)頁一個(gè)文檔號(hào)(docID)。</p

24、><p>　　(3)索引器(Indexer)從Repository中讀取數(shù)據(jù)，以后做以下四步工作：</p><p>　　(4)(a)將讀取的數(shù)據(jù)解壓縮后進(jìn)行分析，它將網(wǎng)頁中每個(gè)有意義的詞進(jìn)行統(tǒng)計(jì)后，轉(zhuǎn)化為關(guān)鍵詞(wordID)的若干索引項(xiàng)(Hits)，生成索引項(xiàng)列表，該列表包括關(guān)鍵詞、關(guān)鍵詞的位置、關(guān)鍵詞的大小和大小寫狀態(tài)等。索引項(xiàng)列表被存入到數(shù)據(jù)桶(Barrels)中，并生成以文檔號(hào)(doc

25、ID)部分排序的順排檔索引。</p><p>　　索引項(xiàng)根據(jù)其重要程度分為兩種：</p><p>　　當(dāng)索引項(xiàng)中的關(guān)鍵詞出現(xiàn)在URL、標(biāo)題、錨文本(Anchor Text)和標(biāo)簽中時(shí)，表示該索引項(xiàng)比較重要，稱為特殊索引項(xiàng)(Fancy Hits)；其余情況則稱為普通索引項(xiàng)(Plain Hits)。 </p><p>　　順排檔索引和Hit的存儲(chǔ)結(jié)構(gòu)如圖1.1所示。&l

26、t;/p><p>　　(b)索引器除了對(duì)網(wǎng)頁中有意義的詞進(jìn)行分析外，還分析網(wǎng)頁的所有超文本鏈接，將其Anchor Text、URL指向等關(guān)鍵信息存入到Anchor文檔庫中。</p><p>　　(c)索引器生成一個(gè)索引詞表(Lexicon)，它包括兩個(gè)部分：關(guān)鍵詞的列表和指針列表，用于倒排檔文檔相連接(如圖1.1所示)。 </p><p>　　(d)索引器還將分析過的網(wǎng)

27、頁編排成一個(gè)與Repository相連接的文檔索引(Document Index)，并記錄下網(wǎng)頁的URL和標(biāo)題，以便可以準(zhǔn)確查找出在Repository中存儲(chǔ)的原網(wǎng)頁內(nèi)容。而且把沒有分析的網(wǎng)頁傳給URL Server，以便在下一次工作流程中進(jìn)行索引分析。</p><p>　　(5)URL分析器(URL Resolver)讀取Anchor文檔中的信息，然后做⑥中的工作。</p><p>　　

28、(6)(a)將其錨文本(Anchor Text)所指向的URL轉(zhuǎn)換成網(wǎng)頁的docID；(b)將該docID與原網(wǎng)頁的docID形成“鏈接對(duì)”，存入Link數(shù)據(jù)庫中；(c)將Anchor Text指向的網(wǎng)頁的docID與順排檔特殊索引項(xiàng)Anchor Hits相連接。 </p><p>　　(7)數(shù)據(jù)庫Link記錄了網(wǎng)頁的鏈接關(guān)系，用來計(jì)算網(wǎng)頁的PageRank值。 </p><p>　　(8

29、)文檔索引(Document Index)把沒有進(jìn)行索引分析的網(wǎng)頁傳遞給URL Server，URL Server則向Crawler提供待遍歷的URL，這樣，這些未被索引的網(wǎng)頁在下一次工作流程中將被索引分析。 </p><p>　　(9)排序器(Sorter)對(duì)數(shù)據(jù)桶(Barrels)的順排檔索引重新進(jìn)行排序，生成以關(guān)鍵詞(wordID)為索引的倒排檔索引。倒排檔索引結(jié)構(gòu)如圖所示： </p><

30、;p><b>　　圖1.1</b></p><p>　　(10)將生成的倒排檔索引與先前由索引器產(chǎn)生的索引詞表(Lexicon)相連接產(chǎn)生一個(gè)新的索引詞表供搜索器(Searcher)使用。搜索器的功能是由網(wǎng)頁服務(wù)器實(shí)現(xiàn)的，根據(jù)新產(chǎn)生的索引詞表結(jié)合上述的文檔索引(Document Index)和Link數(shù)據(jù)庫計(jì)算的網(wǎng)頁P(yáng)ageRank值來匹配檢索。</p><p>

31、;　　在執(zhí)行檢索時(shí)，Google通常遵循以下步驟(以下所指的是單個(gè)檢索詞的情況)： (1)將檢索詞轉(zhuǎn)化成相應(yīng)的wordID；</p><p>　　(2)利用Lexicon，檢索出包含該wordID的網(wǎng)頁的docID；</p><p>　　(3)根據(jù)與Lexicon相連的倒排檔索引，分析各網(wǎng)頁中的相關(guān)索引項(xiàng)的情況，計(jì)算各網(wǎng)頁和檢索詞的匹配程度，必要時(shí)調(diào)用順排檔索引； </p>

32、<p>　　(4)根據(jù)各網(wǎng)頁的匹配程度，結(jié)合根據(jù)Link產(chǎn)生的相應(yīng)網(wǎng)頁的PageRank情況，對(duì)檢索結(jié)果進(jìn)行排序；</p><p>　　(5)調(diào)用Document Index中的docID及其相應(yīng)的URL，將排序結(jié)果生成檢索結(jié)果的最終列表，提供給檢索用戶。 </p><p>　　這些過程都是離線進(jìn)行的。當(dāng)用戶在線提交一個(gè)查詢時(shí)，先從反向索引庫中查找含有查詢關(guān)鍵詞的網(wǎng)頁，返回一系

33、列相關(guān)的網(wǎng)頁的docID，由docID在存儲(chǔ)PageRank的庫中找到它們對(duì)應(yīng)的PageRank值，然后將所有結(jié)果進(jìn)行排序輸出給用戶?？梢钥闯觯麄€(gè)過程中在線進(jìn)行的只是查詢，所有的計(jì)算都是離線進(jìn)行的，因此搜索引擎能以較快的速度將結(jié)果返回給用戶。另外，查詢過程沒有考慮用戶提交的關(guān)鍵詞和訪問者的自身情況。基于鏈接的PageRank離線進(jìn)行計(jì)算一次后，會(huì)在一段時(shí)間保持不變。據(jù)資料稱，Google的PageRank計(jì)算周期大概是三個(gè)月。

34、 </p><p>　　2．傳統(tǒng)Google PageRank算法分析</p><p>　　2.1 傳統(tǒng)Google PageRank算法概述[4]</p><p>　　我要做的工作是將PageRank的算法改進(jìn)，所以先簡述Google PageRank的情況方便下面的改進(jìn)修改和對(duì)照。</p><p>　　超鏈分析技術(shù)主

35、要是指利用網(wǎng)頁間存在的各種超鏈指向, 對(duì)網(wǎng)頁之間的引用關(guān)系進(jìn)行分析，依據(jù)網(wǎng)頁鏈入數(shù)的多少計(jì)算該網(wǎng)頁的重要度權(quán)值，一般認(rèn)為 ,如果A網(wǎng)頁有超鏈指向B網(wǎng)頁，相當(dāng)于A網(wǎng)頁投了B網(wǎng)頁一票，即A認(rèn)可B網(wǎng)頁的重要性。深入理解超鏈分析算法，可以根據(jù)鏈接結(jié)構(gòu)把整個(gè)網(wǎng)頁文檔集看作一個(gè)有向的拓?fù)鋱D，其中每個(gè)網(wǎng)頁都構(gòu)成圖中的一個(gè)結(jié)點(diǎn)，網(wǎng)頁之間的鏈接就構(gòu)成了結(jié)點(diǎn)間的有向邊，按照這個(gè)思想，可以根據(jù)每個(gè)結(jié)點(diǎn)的出度和入度來評(píng)價(jià)網(wǎng)頁的作用。</p>&l

36、t;p>　　其中有代表性的算法主要是 Larry Page等人設(shè)計(jì)的PageRank算法和 Kleinberg 創(chuàng)造的HITS算法。其中PageRank算法在實(shí)際使用中的效果要好于 HITS算法，這主要是由于以下原因: a. PageRank 算法可以一次性、脫機(jī)并且獨(dú)立于查詢地對(duì)網(wǎng)頁進(jìn)行預(yù)計(jì)算，以得到網(wǎng)頁重要度的估計(jì)值，然后在具體的用戶查詢中，結(jié)合其他查詢指標(biāo)值再一齊對(duì)查詢結(jié)果進(jìn)行相關(guān)性排序，從而節(jié)省了系統(tǒng)查詢時(shí)的運(yùn)算開銷

37、；b. PageRank 算法是利用整個(gè)網(wǎng)頁集合進(jìn)行計(jì)算的，不像HITS算法易受到局部連接陷阱的影響而產(chǎn)生“主題漂移”,所以現(xiàn)在這種技術(shù)廣泛地應(yīng)用在許多信息檢索系統(tǒng)和網(wǎng)絡(luò)搜索引擎中，Google 搜索引擎的成功也表明了以超鏈分析為特征的網(wǎng)頁相關(guān)度排序算法日益成熟。</p><p>　　但是 PageRank算法由于只考慮到網(wǎng)頁間的超鏈關(guān)系并僅僅以此進(jìn)行網(wǎng)頁重要度的分析，所以不可避免地會(huì)產(chǎn)生很多問題，其中，比較明顯

38、的問題在于它在計(jì)算每個(gè)網(wǎng)頁具體的重要度權(quán)值的時(shí)候，根本沒有考慮到任何網(wǎng)頁本身內(nèi)容特征對(duì)權(quán)值的影響，如PageRank算法完全忽略了網(wǎng)頁具有的不同主題，不同的主題應(yīng)該具有不同的重要度權(quán)值，進(jìn)一步說，在用戶查詢的時(shí)候，網(wǎng)頁的重要程度值的大小與查詢所表達(dá)的主題關(guān)系很大，其實(shí)，在HITS算法[5]中恰恰考慮了這種因素，所以它更易于表達(dá)與特定查詢主題的相關(guān)度排序，有效地在PageRank算法中考慮查詢主題對(duì)網(wǎng)頁權(quán)重值的影響是一個(gè)有效改進(jìn)此算法的重

39、要方法，再如，PageRank算法也沒有考慮網(wǎng)頁的創(chuàng)建時(shí)間 ,并不對(duì)新舊網(wǎng)頁進(jìn)行有效的區(qū)分,相反 ,按照 PageRank 的既有算法甚至?xí)a(chǎn)生舊網(wǎng)頁比新網(wǎng)頁具有較高重要度權(quán)值的可能性。這些都是Google PageRank存在的缺點(diǎn)，也是本文對(duì)PageRank算法進(jìn)行改進(jìn)的原因。</p><p>　　2.2 傳統(tǒng) PageRank算法回顧</p><p>　　PageRank技術(shù)：通過對(duì)

40、由超過 50,000 萬個(gè)變量和 20 億個(gè)詞匯組成的方程進(jìn)行計(jì)算，PageRank 能夠?qū)W(wǎng)頁的重要性做出客觀的評(píng)價(jià)。PageRank 并不計(jì)算直接鏈接的數(shù)量，而是將從網(wǎng)頁 A 指向網(wǎng)頁 B 的鏈接解釋為由網(wǎng)頁 A 對(duì)網(wǎng)頁 B 所投的一票。這樣，PageRank 會(huì)根據(jù)網(wǎng)頁 B 所收到的投票數(shù)量來評(píng)估該頁的重要性。</p><p>　　雖然 PageRank 認(rèn)為網(wǎng)頁的鏈入超鏈數(shù)可以反應(yīng)該網(wǎng)頁的重要程度 ,但是

41、現(xiàn)實(shí)中人們?cè)谠O(shè)計(jì)網(wǎng)頁的各種超鏈時(shí)往往并不嚴(yán)格，有很多網(wǎng)頁的超鏈純粹是為了諸如網(wǎng)頁導(dǎo)航、商業(yè)推薦等目的而制作的，顯然這類網(wǎng)頁對(duì)于它所指向網(wǎng)頁的重要度貢獻(xiàn)程度并不高，但是，由于算法的復(fù)雜性，PageRank 沒有過多考慮網(wǎng)頁超鏈內(nèi)容對(duì)網(wǎng)頁重要度的影響,只是使用了兩個(gè)相對(duì)簡單的方法： 其一，如果一個(gè)網(wǎng)頁的鏈出網(wǎng)頁數(shù)太多，則它對(duì)每個(gè)鏈出網(wǎng)頁重要度的認(rèn)可能力相應(yīng)降低；其二， 如果一個(gè)網(wǎng)頁由于本身鏈入網(wǎng)頁數(shù)很低造成它的重要度降低，則它對(duì)它的鏈出 網(wǎng)

42、頁重要度的影響也相應(yīng)降低。綜上而言，一個(gè)網(wǎng)頁的重要性決定著同時(shí)也依賴于其他網(wǎng)頁的重要性。</p><p>　　PageRank絕對(duì)是個(gè)很科學(xué)的小創(chuàng)意。說他科學(xué)，你會(huì)在我以后的文章中看到Google是如何將數(shù)學(xué)(具體來說多數(shù)是統(tǒng)計(jì)學(xué))理論淋漓盡致地發(fā)揮在搜索技術(shù)之中。說他“小”，因?yàn)檫@些理論對(duì)于搞數(shù)學(xué)的人來說實(shí)在太微不足道了，甚至稍微有些科學(xué)高數(shù)知識(shí)的人都能理解。他所用到的統(tǒng)計(jì)學(xué)就是循環(huán)迭代計(jì)算收斂值的方法！[6]

43、</p><p>　　2.2.1傳統(tǒng) PageRank算法代數(shù)表達(dá)形式</p><p>　　按照上面思路，Page給出了PageRank的簡單定義[7]：</p><p><b>　　(2.1)</b></p><p>　　此處的u表示一個(gè)網(wǎng)頁，R ( u) 表示網(wǎng)頁u的PageRank值，B ( u)表示鏈接到網(wǎng)頁u的

44、網(wǎng)頁集合，即網(wǎng)頁u 的鏈入網(wǎng)頁集合，N ( v ) 表示從網(wǎng)頁 v 向外的鏈接數(shù)量，即網(wǎng)頁v 的鏈出網(wǎng)頁數(shù)，C為規(guī)范化因子，用于保證所有網(wǎng)頁的PageRank總和為常量 (如為1)。</p><p>　　這就是算法的形式化描述，也可以用矩陣來描述此算法，設(shè)A為一個(gè)方陣，行和列對(duì)應(yīng)網(wǎng)頁集的網(wǎng)頁。如果網(wǎng)頁i有指向網(wǎng)頁j的一個(gè)鏈接，則Aij=1/Ni，否則Aij=0。設(shè)V是對(duì)應(yīng)網(wǎng)頁集的一個(gè)向量，有V=cAV，V為A的特

45、征根為c的特征向量。實(shí)際上只需要求出最大特征根的特征向量，就是網(wǎng)頁集對(duì)應(yīng)的最終PageRank值，這可以用迭代方法計(jì)算。</p><p>　　具體計(jì)算時(shí)，可以給每個(gè)網(wǎng)頁一個(gè)初始的PageRank值，然后反復(fù)迭代運(yùn)算，即 ： </p><p>　　R(i+1)(v)=R(i)(u)/Nu (2.2)</p>

46、<p>　　此處的 v 代表所有的網(wǎng)頁集合,每一個(gè)第i+1次的PageRank 值都是基于上次的PageRank值重新計(jì)算的。具體的迭代次數(shù)在實(shí)際運(yùn)算中是有限的。</p><p>　　Lawrence Page和Sergey Brin在個(gè)別場(chǎng)合描述了PageRank最初的算法。這就是</p><p>　　PR(A) = (1-d) + d (PR(T1)/C(T1) + ...

47、+ PR(Tn)/C(Tn)) </p><p>　　式中：PR(A) :網(wǎng)頁A頁的PageRank值； </p><p>　　PR(Ti) :鏈接到A頁的網(wǎng)頁Ti的PageRank值； </p><p>　　C(Ti) :網(wǎng)頁Ti的出站鏈接數(shù)量； </p><p>　　d :阻尼系數(shù)，0<d<1。</p>&l

48、t;p>　　上式最初算法只是表達(dá)了PageRank的基本計(jì)算原理，并不具有普遍性，因?yàn)闆]有迭代收斂的步驟。</p><p>　　所有PR(Ti)之和還要乘以一個(gè)阻尼系數(shù)d，它的值在0到1之間。阻尼系數(shù)的使用，減少了其它頁面對(duì)當(dāng)前頁面A的排序貢獻(xiàn)。</p><p>　　一個(gè)頁面通過隨機(jī)沖浪到達(dá)的概率就是鏈入它的別的頁面上的鏈接的被點(diǎn)擊概率的和。并且，阻尼系數(shù)d減低了這個(gè)概率。阻尼系數(shù)d

49、的引入，是因?yàn)橛脩舨豢赡軣o限的點(diǎn)擊鏈接，常常因無聊而隨機(jī)跳入另一個(gè)頁面。</p><p>　　PageRank的特性可以通過以下范例用插圖表示。 </p><p><b>　　圖2.1</b></p><p>　　假設(shè)一個(gè)小網(wǎng)站由三個(gè)頁面A、B、C組成，A連接到B和C，B連接到C，C連接到A。雖然Page和Brin實(shí)際上將阻尼系數(shù)d設(shè)

50、為0.85，但這里我們?yōu)榱撕啽阌?jì)算就將其設(shè)為0.5。盡管阻尼系數(shù)d的精確值無疑是影響到PageRank值的，可是它并不影響PageRank計(jì)算的原理。因此，我們得到以下計(jì)算PageRank值的方程：</p><p>　　PR(A) = 0.5 + 0.5 PR(C)</p><p>　　PR(B) = 0.5 + 0.5 (PR(A) / 2)PR(C)=0.5+0.5(PR(A)/2+

51、PR(B))</p><p>　　這些方程很容易求解，以下得到每個(gè)頁面的PageRank值：</p><p>　　PR(A)= 14/13 = 1.07692308</p><p>　　PR(B)=10/13 = 0.76923077PR(B)=15/13 = 1.15384615</p><p>　　很明顯所有頁面PageRank之和為3

52、，等于網(wǎng)頁的總數(shù)。就像以上所提的，此結(jié)果對(duì)于這個(gè)簡單的范例來說并不特殊。</p><p>　　對(duì)于這個(gè)只有三個(gè)頁面的簡單范例來說，通過方程組很容易求得PageRank值。但實(shí)際上，互聯(lián)網(wǎng)包含數(shù)以億計(jì)的文檔，是不可能解方程組的。下面闡述迭代過程。</p><p>　　由于實(shí)際的互聯(lián)網(wǎng)網(wǎng)頁數(shù)量，Google搜索引擎使用了一個(gè)近似的、迭代的計(jì)算方法計(jì)算PageRank值。就是說先給每個(gè)網(wǎng)頁一個(gè)初

53、始值，然后利用上面的公式，循環(huán)進(jìn)行有限次運(yùn)算得到近似的PageRank值。我們?cè)俅问褂谩叭撁妗钡姆独齺碚f明迭代計(jì)算，這里設(shè)每個(gè)頁面的初始值為1。</p><p>　　重復(fù)幾次后，我們的到一個(gè)良好的接近PageRank理想值的近似值。根據(jù)Lawrence Page和Sergey Brin共開發(fā)表的文章，他們實(shí)際需要進(jìn)行100次迭代才能得到整個(gè)互聯(lián)網(wǎng)的滿意的網(wǎng)頁級(jí)別值。</p><p>　　

54、同樣，用迭代計(jì)算的方式，每個(gè)網(wǎng)頁的PageRank值之和仍然收斂于整個(gè)網(wǎng)絡(luò)的頁面數(shù)的。因此，每個(gè)頁面的平均的PageRank值為1。實(shí)際上的值在(1－d)和(dN+(1-d))之間，這里的N是互聯(lián)網(wǎng)網(wǎng)頁總數(shù)。如果所有頁面都連接到一個(gè)頁面，并且此頁單獨(dú)地連接自身，那么將出現(xiàn)理論上的最大值。</p><p>　　2.2.2 傳統(tǒng) PageRank算法向量表達(dá)形式</p><p>　　上述過程在

55、本質(zhì)上可以表達(dá)為特征向量的計(jì)算,首先每個(gè)網(wǎng)頁文檔的PageRank 值可以表示一個(gè)向量 ,即一個(gè) N 行1列的向量 (N 為所有的網(wǎng)文檔數(shù))，為了便于計(jì)算，開始時(shí)可以給每個(gè)元素的值設(shè)為 1/ N。</p><p>　　Rank = ［1/ N ］n ×1</p><p>　　設(shè)M為一個(gè)隨機(jī)矩陣，它的橫縱行列數(shù)分別為整個(gè)網(wǎng)頁集合的文檔數(shù)，每個(gè)矩陣元素值表示兩兩網(wǎng)頁之間的鏈接關(guān)系,

56、即如果網(wǎng)頁Di指向Dj，則矩陣元素Mij 對(duì)應(yīng)的值為1/ Ni ( Ni表示Di的鏈出網(wǎng)頁數(shù))；如果網(wǎng)頁Di不指向Dj，則M ij值為 0。</p><p><b>　　M=</b></p><p>　　所以 , PageRank 值的計(jì)算就可以表示為：</p><p>　　Rank = MT ×Rank

57、 (2.3)</p><p>　　而且這個(gè)過程是個(gè)反復(fù)迭代的過程,直至 Rank值最終收斂。但是，實(shí)際的網(wǎng)頁結(jié)構(gòu)并非表現(xiàn)為一個(gè)完全牢固的鏈接圖，不是所有的網(wǎng)頁都可以從其他網(wǎng)頁 通過超鏈來達(dá)到，而PageRank值的計(jì)算正依賴于此，所以Page等人就提出了改進(jìn)方案，對(duì)存在的等級(jí)沉沒(Rank Sink)和等級(jí)泄漏(Rank Leak)[8]等問題進(jìn)行了有效的解決。整個(gè)網(wǎng)頁圖中的一組緊密鏈接的網(wǎng)頁如果沒

58、有外出的鏈接就產(chǎn)生等級(jí)沉沒，一個(gè)獨(dú)立的網(wǎng)頁如果沒有外出的鏈接就產(chǎn)生等級(jí)泄漏。所以，Page改進(jìn)措施為：一是剔除產(chǎn)生等級(jí)泄漏的獨(dú)立網(wǎng)頁以消除其不利影響；二是給產(chǎn)生等級(jí)沉沒的網(wǎng)頁添加一個(gè)指向鏈入網(wǎng)頁的返回鏈接，此時(shí)使得所有網(wǎng)頁 PageRank 值的計(jì)算就不完全依賴現(xiàn)有鏈接了，所以修正的PageRank計(jì)算公式為 ：</p><p><b>　　(2.4)</b></p><

59、p>　　其中，‖R′‖1=1，對(duì)應(yīng)的矩陣形式為V’=c(AV’+E)。</p><p>　　E(u)是個(gè)常量，它可以抑制 PageRank 值的傳播，使得所有網(wǎng)頁的PageRank 值至少會(huì)為E ( u) ，而不會(huì)為0。具體的E ( u)值可以有多種取法，簡單的做法可以設(shè)為p，如取1/ N ( N為網(wǎng)頁文檔總數(shù))。</p><p>　　從特征向量的角度來考察，可以設(shè)置P列向量以代表每

60、個(gè)網(wǎng)頁文檔都有的、相同的E ( u)</p><p><b>　　n1</b></p><p>　　PageRank迭代運(yùn)算都利用了特征向量作為理論基礎(chǔ)和收斂性依據(jù)[9]，這是超鏈接環(huán)境下此類算法的一個(gè)共同特征。</p><p>　　設(shè)置 D 向量以代表網(wǎng)頁文檔的鏈出網(wǎng)頁數(shù)是否為 0 , 即</p><p>　　1

61、 如果網(wǎng)頁Di的鏈出網(wǎng)頁數(shù)為0</p><p><b>　　Di=</b></p><p>　　0 如果網(wǎng)頁Di的鏈出網(wǎng)頁數(shù)非0</p><p>　　則上述 PageRank 的計(jì)算可以進(jìn)一步表達(dá)為 :</p><p>　　Rank = C ( M + P ×D T ) ×Rank + C

62、P</p><p>　　2.3 傳統(tǒng)Google PageRank的缺陷和改進(jìn)方法</p><p>　　基于鏈接分析的算法 ,目前的研究都還很不成熟，無論是Page Rank算法，還是HITS算法等，有一些共同的問題影響著算法的精度。</p><p>　　( 1) 根集的質(zhì)量。根集質(zhì)量應(yīng)該是很高的 , 否則 , 擴(kuò)展后的網(wǎng)頁集會(huì)增加很多無關(guān)的網(wǎng)頁 , 產(chǎn)生主題漂移、

63、主題泛化等一系列的問題 ,計(jì)算量也增加很多。 算法再好 ,也無法在低質(zhì)量網(wǎng)頁集找出很多高質(zhì)量的 網(wǎng)頁。</p><p>　　(2) 錨文本的利用。錨文本有很高的精度 ,對(duì)鏈接 和目標(biāo)網(wǎng)頁的描述比較精確。上述算法在具體的 實(shí)現(xiàn)中利用了錨文本來改進(jìn)算法。如何準(zhǔn)確充分地利用錨文本 ,對(duì)算法的精度影響很大。</p><p>　　(3) 噪音鏈接。Web 上不是每個(gè)鏈接都包含了有用的信息，比如廣告、

64、站點(diǎn)導(dǎo)航、贊助商、用于友情交換的鏈接，對(duì)于鏈接分析不僅沒有幫助，而且還影 響結(jié)果。如何有效去除這些無關(guān)鏈接，也是算法的一個(gè)關(guān)鍵點(diǎn)。</p><p>　　(4) 查詢的分類。每種算法都有自身的適用情況 , 對(duì)于不同的查詢 ,應(yīng)該采用不同的算法 ,以求獲得最好的結(jié)果。因此 ,對(duì)于查詢的分類也顯得非常重要。</p><p>　　文中對(duì)Google PageRank算法進(jìn)行了深入探討和比較,但在這

65、幾個(gè)方面需要繼續(xù)做深入的研究,相信在不久的將來會(huì)有更多的有價(jià)值的成果出現(xiàn)。本文正是針對(duì)Google PageRank存在的問題進(jìn)行算法的改進(jìn)，將改進(jìn)的算法和Google PageRank的傳統(tǒng)算法完美結(jié)合，不僅解決的Google PageRank完全不考慮訪問者自身知識(shí)水平的缺陷，還預(yù)示了將不同算法結(jié)合是未來搜索引擎的發(fā)展趨勢(shì)。</p><p>　　3．Google PageRank 算法改進(jìn)</p>

66、<p>　　3.1由訪問者知識(shí)水平及其投票的情況決定網(wǎng)頁排名的 PageRank 算法</p><p>　　3.1.1 算法中PR值的含義</p><p>　　在Google PageRank傳統(tǒng)算法中，PageRank就是一個(gè)概率(它反映了一個(gè)人在網(wǎng)絡(luò)中不同的頁面上隨機(jī)點(diǎn)擊鏈接會(huì)到達(dá)某個(gè)特定網(wǎng)站的概率)。只不過因?yàn)槿藗儾惶矚g看小數(shù)，Google才更改了度量。 轉(zhuǎn)化為0~1

67、0度量 。因此可以認(rèn)為傳統(tǒng)算法的網(wǎng)頁P(yáng)R值，反映了網(wǎng)頁的熱度(訪問人數(shù))，PR值越大，則表示網(wǎng)頁越熱，越多人訪問。</p><p>　　在改進(jìn)算法中，訪問者的PR值表示為PRin，PRin越大則表示訪問者的專業(yè)知識(shí)水平越高。網(wǎng)頁的PR值表示為Pij，Pij越大表示網(wǎng)頁的權(quán)威性、正確性越大。</p><p>　　3.1.2 從投票角度分析算法的本質(zhì)</p><p>　

68、　從投票的角度來分析兩種算法的本質(zhì)：Google PageRank傳統(tǒng)算法中，從網(wǎng)頁 A 指向網(wǎng)頁 B 的鏈接解釋為由網(wǎng)頁 A 對(duì)網(wǎng)頁 B 所投的一票，由其他網(wǎng)頁對(duì)網(wǎng)頁本身的投票來計(jì)算網(wǎng)頁的PR值。在改進(jìn)算法中，訪問者對(duì)網(wǎng)頁的投票的被認(rèn)同度就是其他訪問者對(duì)他的投票，由其他訪問者對(duì)他的投票來計(jì)算訪問者的PR值。在計(jì)算網(wǎng)頁P(yáng)R值時(shí)，網(wǎng)頁由訪問者對(duì)它的投票來決定網(wǎng)頁的PR值。</p><p>　　不是每個(gè)訪問者和網(wǎng)頁的

69、投票都是對(duì)訪問者或者網(wǎng)頁的PR值貢獻(xiàn)一樣的，因?yàn)槊總€(gè)訪問者和網(wǎng)頁的權(quán)重不一樣，兩者的權(quán)重分別與它們的知識(shí)水平和網(wǎng)頁權(quán)威性有關(guān)。因此計(jì)算兩者PR值之前要計(jì)算兩者的權(quán)重。</p><p>　　權(quán)重是一個(gè)相對(duì)的概念，是針對(duì)某一指標(biāo)而言。某一指標(biāo)的權(quán)重是指該指標(biāo)在整體評(píng)價(jià)中的相對(duì)重要程度。 </p><p>　　權(quán)重表示在評(píng)價(jià)過程中，是被評(píng)價(jià)對(duì)象的不同側(cè)面的重要程度的定量分配，對(duì)各評(píng)價(jià)因子在總體評(píng)

70、價(jià)中的作用進(jìn)行區(qū)別對(duì)待。事實(shí)上，沒有重點(diǎn)的評(píng)價(jià)就不算是客觀的評(píng)價(jià)。 </p><p>　　打個(gè)比方說, 一件事情, 你給它打100分, 你的老板給它打60分, 如果平均, 則是(100+60)/2=80分. 但因?yàn)槔习逭f的話分量比你重, 假如老板的權(quán)重是2, 你是1, 這時(shí)求平均值就是加權(quán)平均了, 結(jié)果是(100*1 + 60*2)/(1+2)=73.3分, 顯然向你的老板那里傾斜了。假如老板權(quán)重是3，你的權(quán)重是

71、1，結(jié)果是(100*1+60*3)/(1+3)=70。這就是根據(jù)權(quán)重的不同進(jìn)行的平均數(shù)的計(jì)算，所以又叫加權(quán)平均數(shù)。</p><p>　　同樣道理每個(gè)訪問者和每個(gè)網(wǎng)頁的權(quán)重都是不同的因?yàn)樗麄兊臋?quán)威性是不同的。例如：一個(gè)工程院院士關(guān)于PageRank網(wǎng)頁的投票的權(quán)重，比我對(duì)PageRank網(wǎng)頁的投票的權(quán)重大得多，因?yàn)樵菏康脑擃I(lǐng)域知識(shí)水平(PR值)遠(yuǎn)遠(yuǎn)高于我。</p><p>　　接著是看投票情

72、況，如果院士投了反對(duì)票，這個(gè)網(wǎng)頁的PR將大打折扣，如果我投了反對(duì)票，對(duì)網(wǎng)頁P(yáng)R的影響可能不大，因?yàn)槲业臋?quán)重比院士的權(quán)重小很多。</p><p>　　網(wǎng)頁也有它的權(quán)重，因?yàn)樵L問者在不同權(quán)重的網(wǎng)頁被認(rèn)同，對(duì)訪問者的PR值貢獻(xiàn)是不同的。例如，我在中國期刊網(wǎng)的投票被別人贊同，和在自己QQ空間被被人贊同，前者將大大增加我的PR值，后者影響較小，因?yàn)閮蓚€(gè)網(wǎng)頁的權(quán)重差幾個(gè)數(shù)量級(jí)。</p><p>　　權(quán)

73、重就是反映影響力的一個(gè)值，訪問者的權(quán)重越大，則對(duì)網(wǎng)頁的PR值影響越大，至于是正面還是負(fù)面影響，還有看投票評(píng)價(jià)情況。在計(jì)算PRin時(shí)，網(wǎng)頁的權(quán)重越大，則對(duì)訪問者的PR影響越大，至于是正面還是負(fù)面影響，還有看投票評(píng)價(jià)被認(rèn)同情況。</p><p>　　3.1.3 算法改進(jìn)的詳細(xì)設(shè)計(jì)思路</p><p>　　事實(shí)上，PageRank 值雖然在一定程度上表達(dá)了網(wǎng)頁與用戶查詢的相關(guān)度 ,但是存在的問題

74、也是明顯的, 其中最明顯的在于 PageRank 的計(jì)算是獨(dú)立于用戶查詢而進(jìn)行的先期運(yùn)算，根本沒有考慮訪問者自身的情況和訪問者對(duì)網(wǎng)頁的評(píng)價(jià)，這樣，網(wǎng)頁的PageRank值只是一個(gè)基于全部網(wǎng)頁集合計(jì)算出來的一個(gè)獨(dú)立值。而網(wǎng)頁的排名不應(yīng)該單單看網(wǎng)頁的訪問量，還要看網(wǎng)頁內(nèi)容的權(quán)威性和正確性，因?yàn)槊總€(gè)用搜索引擎的訪問者希望自己搜索的結(jié)果是正確的具有一定的權(quán)威性的，當(dāng)然網(wǎng)絡(luò)多人訪問在一定程度上說明了它的正確性，但是也不能夠完全這樣來判斷網(wǎng)頁的正確

75、性，還要結(jié)合訪問者對(duì)網(wǎng)頁的評(píng)價(jià)來決定網(wǎng)頁的權(quán)威性和正確性。但是PageRank算法僅僅根據(jù)訪問量來決定網(wǎng)站的重要性，這個(gè)有點(diǎn)不完善，搜索引擎不單只要返回多人關(guān)注的網(wǎng)站排位，而且還要考慮網(wǎng)站的內(nèi)容是否正確權(quán)威，這個(gè)可以從訪問者的知識(shí)水平來判斷網(wǎng)頁的權(quán)威性。</p><p>　　我做的工作就是增加訪問者的具體情況影響PageRank值，首先就是訪問者的知識(shí)水平不同他對(duì)網(wǎng)站的PR值貢獻(xiàn)不同，在不同的領(lǐng)域不同的訪問者具有

76、不同PR(PageRank，下同)值，這個(gè)PR值，首先計(jì)算每個(gè)訪問者的PR值，類似PageRank根據(jù)鏈接數(shù)量判斷網(wǎng)頁重要性的算法首先假設(shè)有N個(gè)訪問者每個(gè)訪問者本身有一個(gè)PR值1/ N。有的網(wǎng)站允許訪問者對(duì)網(wǎng)頁內(nèi)容評(píng)價(jià)，這時(shí)多數(shù)的訪問者表態(tài)代表了正確的評(píng)價(jià)，即訪問者的評(píng)價(jià)對(duì)網(wǎng)頁的評(píng)價(jià)得到越多的人的贊同則訪問者的PR值越高，否則就越低，通過大量的訪問記錄，則統(tǒng)計(jì)結(jié)果表明訪問者本身的PR值，同時(shí)由于訪問者在不同領(lǐng)域的知識(shí)水平不同，應(yīng)該在不同

77、的領(lǐng)域有不同的PR值，假設(shè)網(wǎng)頁根據(jù)內(nèi)容可以劃分為i類，即分為i個(gè)領(lǐng)域，則訪問者在i領(lǐng)域的PageRank值為PR(i)，網(wǎng)絡(luò)網(wǎng)站總量為T，i領(lǐng)域的網(wǎng)站的總量是T(i)。</p><p>　　將所有網(wǎng)站分為兩類：一種是訪問者可以投票的網(wǎng)站，第二種是訪問者不可以投票。投票網(wǎng)站一般給出 好、中、差 或者是贊成、反對(duì)、中立等幾個(gè)選項(xiàng)給訪問者直接選擇，訪問者只可以選擇其中一個(gè)對(duì)網(wǎng)頁進(jìn)行評(píng)價(jià)。投票又可以分為登錄投票和匿名投票

78、，都沒有問題，因?yàn)橄旅鏁?huì)講到本文是由物理地址標(biāo)志訪問者的。同時(shí)現(xiàn)在的網(wǎng)站大部分都是分主題的，一個(gè)網(wǎng)站就是講一個(gè)領(lǐng)域的知識(shí)，按照現(xiàn)在的比例百分之九十八的網(wǎng)站都是講一個(gè)領(lǐng)域或者說是主題的內(nèi)容(分類網(wǎng)頁)，例如體育、軍事、健康、新聞、娛樂……等等，大概有百分之二的網(wǎng)站是同時(shí)具有幾個(gè)主題的(非分類網(wǎng)頁)，根據(jù)這個(gè)情況，我們可以抓主要的先，先將網(wǎng)頁分為i個(gè)主題，每個(gè)主題的網(wǎng)頁是j個(gè)，最后才考慮多個(gè)主題的少數(shù)網(wǎng)頁，這些非分類網(wǎng)頁的PR值可以通過由分

79、類網(wǎng)頁計(jì)算出來的訪問者PR值計(jì)算，因?yàn)榉诸惥W(wǎng)頁的算法是根據(jù)絕大部分網(wǎng)頁(約98%)來計(jì)算訪問者PR值的，非分類網(wǎng)頁(約2%)對(duì)訪問者PR值的計(jì)算的影響微乎其微[10]。因此由分類網(wǎng)頁計(jì)算出來的訪問者PR值來計(jì)算網(wǎng)頁的PR值具有統(tǒng)計(jì)特性，可以準(zhǔn)確反映每個(gè)訪問者的實(shí)際情況，這樣計(jì)算出來的PR值是可靠的，反映了網(wǎng)頁的真實(shí)重要性(也就是網(wǎng)頁</p><p>　　由于本論文研究的改進(jìn)搜索引擎排序算法是由訪問者的知識(shí)水平及其

80、投票情況決定網(wǎng)頁的排名，因此在計(jì)算網(wǎng)頁的PR值之前首先就要求出訪問者本身的PR值，第二步才是求網(wǎng)頁的PR值，下面將改進(jìn)方法分兩步詳細(xì)說明。</p><p>　　3.2 計(jì)算每個(gè)訪問者的PageRank值</p><p>　　3.2.1 計(jì)算訪問者PR值的數(shù)學(xué)表達(dá)式</p><p>　　為了下面的運(yùn)算現(xiàn)在設(shè)置好運(yùn)算的變量，假設(shè)總共N個(gè)訪問者，整個(gè)網(wǎng)絡(luò)的網(wǎng)頁有b=98%

81、的網(wǎng)頁是單一主題的，另外的2%網(wǎng)頁具有多個(gè)主題，單一主題的網(wǎng)頁可以分為i個(gè)領(lǐng)域，每個(gè)領(lǐng)域有j個(gè)網(wǎng)頁，因此Pij就指向具體的任何一個(gè)網(wǎng)頁。</p><p>　　首先計(jì)算某個(gè)訪問者n在i領(lǐng)域的PR值PRin，設(shè)Zijn表示訪問者n對(duì)網(wǎng)頁P(yáng)ij的訪問次數(shù)，Kijn為訪問者n對(duì)網(wǎng)頁P(yáng)ij的投票評(píng)價(jià)的被認(rèn)同度 (例如：10個(gè)訪問者訪問網(wǎng)頁P(yáng)ij，其中8人投贊成票，2人投反對(duì)票。則投了贊成票的8個(gè)人的Kijn為80%或0.8

82、，投反對(duì)票的2人的Kijn為20%或0.2)。</p><p>　　訪問者在i領(lǐng)域的PR值PRin可以用下式表示</p><p>　　PRin= (Kijn ×Zijn×PRin×Kijn) (3.1)</p><p>　　上式兩邊都有PRin，不是說上式存在錯(cuò)誤，上式只是表達(dá)出了一種計(jì)算

83、思路，遇到由自身求自身的數(shù)學(xué)問題，類似先有蛋還是先有雞的問題，在這里和Google PageRank傳統(tǒng)算法計(jì)算網(wǎng)頁P(yáng)R的情況類似了，式(2.1)也是由網(wǎng)頁自身PR值求網(wǎng)頁自身PR值，因此我們可以完全借鑒Google PageRank傳統(tǒng)的計(jì)算思路，利用循環(huán)計(jì)算收斂值的方法解決這個(gè)問題。</p><p>　　下面詳細(xì)分析一下上式(3.1)的思路：</p><p>　　Zijn×P

84、Rin×Kijn (3.2)</p><p>　　式(3.2)整體可以看做網(wǎng)頁j權(quán)重，這個(gè)權(quán)重乘以Kijn得出網(wǎng)頁j對(duì)訪問者n的PR值的貢獻(xiàn)，將i領(lǐng)域所有網(wǎng)頁的貢獻(xiàn)疊加就得到訪問者n在i領(lǐng)域的PR值表示為PRin?；\統(tǒng)來說訪問者在每一個(gè)網(wǎng)頁的被認(rèn)同度越高，訪問者的PR值就越高，但是每個(gè)網(wǎng)頁對(duì)訪問者的PR值計(jì)算中貢獻(xiàn)的份量是不一樣的，也就是權(quán)重不同，舉個(gè)例

85、子，像中國期刊網(wǎng)的權(quán)重是非常大的，比一般的QQ空間要大幾個(gè)數(shù)量級(jí)，當(dāng)訪問者在中國期刊網(wǎng)得到認(rèn)同，和訪問者在自己的QQ空間被別人認(rèn)同對(duì)訪問者的PR計(jì)算的貢獻(xiàn)是差異極大的，相差好幾個(gè)數(shù)量級(jí)。所以計(jì)算PRin時(shí)首先要算出網(wǎng)頁的權(quán)重。</p><p>　　Zijn×PRin×Kijn </p><p>　　式(3.2)中的Zijn×PRin也是一個(gè)權(quán)重，表示訪問者n

86、在計(jì)算網(wǎng)頁j權(quán)重中的份量，乘以Zijn的原因是，訪問者訪問的次數(shù)越多，說明這個(gè)網(wǎng)頁越受訪問者n關(guān)注，稱為關(guān)注度，當(dāng)然一個(gè)網(wǎng)頁受訪問者n關(guān)注越多，并不表示網(wǎng)頁j的權(quán)重(3.2)越大，還要看訪問者的被認(rèn)同度Kijn，Zijn×PRin只是作為一個(gè)權(quán)重 ，還要看他的意見是否得到大家的贊同，所以乘以Kijn，簡單舉個(gè)例子，一個(gè)資深的學(xué)者訪問一個(gè)本專業(yè)的網(wǎng)頁，并不是訪問次數(shù)越多對(duì)網(wǎng)頁權(quán)重的貢獻(xiàn)就越大，還要乘以一個(gè)系數(shù)Kijn，當(dāng)沒有人同

87、意這位資深學(xué)者的評(píng)價(jià)時(shí)，這位資深學(xué)者本身在這個(gè)領(lǐng)域很高的PR值當(dāng)然不可以貢獻(xiàn)在網(wǎng)頁j的權(quán)重上，相反如果很多人贊同這位資深學(xué)者的評(píng)價(jià)，即Kijn很大，這位資深學(xué)者本身的PR就會(huì)很大比例地對(duì)網(wǎng)頁j的權(quán)重做出貢獻(xiàn)。</p><p>　　Kijn表示在投票網(wǎng)頁P(yáng)ij的所有訪問者之中，與訪問者n有相同投票的人占得比例?？紤]到不是每個(gè)網(wǎng)站都設(shè)置有投票欄，也不是每個(gè)領(lǐng)域所有的網(wǎng)站，訪問者n都會(huì)去訪問，有的訪問者訪問了網(wǎng)站卻不一

88、定會(huì)投票，因此上式中的Kijn分四種情況，具體如下：</p><p>　　與訪問者n相同的評(píng)價(jià)(投票)占所有評(píng)價(jià)的比例</p><p>　　Kijn= 50% ，網(wǎng)頁沒有投票欄 </p><p><b>　　表達(dá)式一</b></p><p>　　50%，

89、訪問者沒有投票</p><p>　　0 ，訪問者n沒有訪問網(wǎng)頁P(yáng)ij</p><p>　　表達(dá)式一的表示其實(shí)不嚴(yán)密，有少數(shù)訪問者會(huì)多次訪問同一個(gè)網(wǎng)頁但是在這部分人之中又會(huì)有極少數(shù)的人會(huì)對(duì)網(wǎng)站的評(píng)價(jià)進(jìn)行多次不同的投票也就是給出不同的評(píng)價(jià)，這并不奇怪，因?yàn)槿说乃枷胧请S著認(rèn)知水平和社會(huì)情況而變化的，因此越后面的投票越具有權(quán)威性，因此最后面投票基本反映了最近的社會(huì)情況，越后的投票時(shí)訪問者經(jīng)過更加縝

90、密結(jié)合了最新的事實(shí)綜合考慮的結(jié)果，因此我們只需要考慮訪問者最好一次的投票，為了使計(jì)算更加精確所以有必要對(duì)Kijn進(jìn)行修正：</p><p>　　與訪問者最后一次的評(píng)價(jià)(投票)相同的評(píng)價(jià)占所有評(píng)價(jià)的比例</p><p>　　Kijn= 50 %，網(wǎng)頁沒有投票欄 表達(dá)式二</p><p>　

91、　50%，訪問者沒有投票</p><p>　　0 ，訪問者n沒有訪問網(wǎng)頁P(yáng)ij</p><p>　　這時(shí)有人可能會(huì)問，既然上面已經(jīng)對(duì)Kijn進(jìn)行了修正，Kijn其實(shí)是考慮最后一次投票的，再乘以訪問次數(shù)，顯得不合理，這樣的說法其實(shí)不對(duì)因?yàn)樵L問者訪問這個(gè)網(wǎng)站越多就說明對(duì)這個(gè)網(wǎng)站關(guān)注越多，說明這個(gè)網(wǎng)站比較重要，再乘以訪問者對(duì)網(wǎng)站的最終評(píng)價(jià)，正好反映了網(wǎng)站的權(quán)威性重要性。一個(gè)本身PR值越高的人訪問

92、某網(wǎng)頁的次數(shù)越多則網(wǎng)頁越重要。對(duì)網(wǎng)頁內(nèi)容的評(píng)價(jià)越高則網(wǎng)頁越權(quán)威相應(yīng)的PR值越高，因此以上表達(dá)式是合理的可行的。 </p><p>　　3.2.2 訪問者PR值的循環(huán)收斂計(jì)算方法</p><p>　　類似Google PageRank計(jì)算方法，首先賦予每個(gè)訪問者相同的PageRank值簡稱PR值，首先假設(shè)每個(gè)訪問者的PR值為常數(shù)。</p><p>　　PRin(i+1

93、)= (Kijn ×Zijn×PRin(i)×Kijn) (3.3)</p><p>　　這里是根據(jù)上一次的PRin計(jì)算下一次的PRin，設(shè)</p><p>　　L=Zijn×PRin(i)×Kijn</p><p><b>　　則上式可以表達(dá)為</b><

94、/p><p>　　PRin(i+1)= (Kijn×L)。</p><p>　　上式表示對(duì)i領(lǐng)域的所有網(wǎng)頁中訪問者n被認(rèn)同度的疊加得到PRin，但是相同的認(rèn)同度對(duì)于不同的網(wǎng)頁所對(duì)訪問者的PR值貢獻(xiàn)是不同的，所以對(duì)于不同的網(wǎng)頁有不同的權(quán)重，乘以這個(gè)權(quán)重就比較準(zhǔn)確反映了 j網(wǎng)頁對(duì)訪問者n的PR值的貢獻(xiàn)。L的具體算法是</p><p>　　Zijn×PRi

95、n(i)×Kijn </p><p>　　L權(quán)重是由訪問者本身的權(quán)重乘以訪問次數(shù)(訪問次數(shù)越多說明網(wǎng)頁越受關(guān)注)。訪問者本身有PR值但是只有訪問者被認(rèn)同越高，他本身的PR值才會(huì)對(duì)網(wǎng)頁的權(quán)重做出越多貢獻(xiàn)(只有訪問者被認(rèn)同越高，本身的PR值才會(huì)對(duì)網(wǎng)頁的PR做出相應(yīng)的貢獻(xiàn)，所以乘以Kijn)。</p><p>　　考慮到還有2的網(wǎng)站是非分類網(wǎng)頁，非分類網(wǎng)頁的PR值需要根據(jù)每個(gè)訪問者

96、在相關(guān)領(lǐng)域的PR值來計(jì)算，與兩個(gè)以上的領(lǐng)域有關(guān)的非分類網(wǎng)頁的PR值，是將本網(wǎng)頁有關(guān)的領(lǐng)域的PR值的疊加再除以涉及到的領(lǐng)域數(shù)，而不是在單獨(dú)的領(lǐng)域計(jì)算總的PR值，如果不將不同領(lǐng)域的所有訪問者的PR值進(jìn)行歸一化將出現(xiàn)以下的情況，一個(gè)訪問者在兩個(gè)不同的領(lǐng)域的知識(shí)水平一樣但是他在這兩個(gè)領(lǐng)域的PR值相差很大，如果一個(gè)非分類網(wǎng)頁包含這兩個(gè)領(lǐng)域，將各個(gè)領(lǐng)域的網(wǎng)頁P(yáng)R相加得到總的PR的方法計(jì)算的結(jié)果將會(huì)出現(xiàn)偏差，因?yàn)槭?3.1)中，不同領(lǐng)域的PRin是獨(dú)

97、立運(yùn)算的，計(jì)算分類網(wǎng)頁時(shí)只需要結(jié)果分出相對(duì)大小就行，對(duì)計(jì)算出來的PRin本身的大小則不要求，式(3.1)僅僅限于單領(lǐng)域網(wǎng)頁即分類網(wǎng)頁的PR計(jì)算，因此在不同領(lǐng)域它們的基數(shù)不一樣，為了使計(jì)算結(jié)果更加準(zhǔn)確，所以必須要對(duì)PRin進(jìn)行歸一化以方便跨領(lǐng)域的PR值疊加運(yùn)算。為了避免出現(xiàn)不同領(lǐng)域總的PR值不同給下面計(jì)算非分類網(wǎng)頁總的PR值帶來偏差的情況，下面對(duì)計(jì)算所有訪問者對(duì)各個(gè)領(lǐng)域的總的PR值的和。</p><p>　　PRi

98、=設(shè)置歸一化常數(shù)Ci=</p><p>　　因此最后得出某個(gè)訪問者n在i領(lǐng)域的PR值</p><p>　　PRin(i+1)=Ci (Kijn ×Zijn×PRin(i)×Kijn) (3.4) </p><p>　　上式就是結(jié)合訪問者的自身情況得出的改進(jìn)

99、算法</p><p><b>　　算法描述如下：</b></p><p>　　PRin(0) = //初始化每個(gè)訪問者的PageRank</p><p>　　while (|PRin(i)- PRin(i-1)|>ε)　//PageRank收斂前的循環(huán)計(jì)算判斷</p><p>　　{ε=0.000000000

100、0001</p><p><b>　　i=1</b></p><p>　　for each n∈N</p><p>　　PRin(i)= (Kijn ×Zijn×PRin(i-1)×Kijn)</p><p><b>　　PRi=</b></p>&l

101、t;p>　　Ci= //設(shè)置歸一化常數(shù),規(guī)范因子的計(jì)算，以保證計(jì)算結(jié)果的正確性</p><p>　　PRin(i)= Ci PRin(i) //進(jìn)行規(guī)范化得出的結(jié)果</p><p><b>　　i=i+1</b></p><p><b>　　}</b></p><p>

102、;　　隨著循環(huán)次數(shù)的增加，計(jì)算結(jié)果越來越收斂，越來越接近真實(shí)的PR值，只要循環(huán)次數(shù)足夠多可以得到任何精度的網(wǎng)頁P(yáng)R值。</p><p>　　3.2.3訪問者PR值算法的簡單模型</p><p>　　據(jù)統(tǒng)計(jì)，Web已經(jīng)擁有100億左右的靜態(tài)網(wǎng)頁和550億左右的動(dòng)態(tài)網(wǎng)頁，網(wǎng)民數(shù)量僅中國就有4.16億，因此，PageRank要處理的矩陣是“世界上最大的矩陣”，為了便于討論驗(yàn)證算法的正確性同時(shí)也是

103、為了讓讀者更加容易理解算法的結(jié)構(gòu)邏輯，下面建立簡單的模型，驗(yàn)證程序是否可行。</p><p><b>　　圖3.1</b></p><p>　　PRin(i)= (Kijn× Zijn×PRin(i-1)×Kijn) (3.5)</p><p>　　以上圖示為了方便驗(yàn)證下面

104、的結(jié)果是否正確，如圖，圓圈表示訪問者，方框表示網(wǎng)頁，直線表示訪問相應(yīng)的網(wǎng)頁。 3×0.7表示訪問次數(shù)3次最終的Kijn為0.7，其他的依次類推。</p><p>　　圖3.1設(shè)置的數(shù)值都很明顯,訪問者1的被認(rèn)同度明顯是高于其他三人，訪問者4的被認(rèn)同度明顯低于其他三人，而訪問者2的被認(rèn)同度又高于訪問者3，讀者可以明顯看出4個(gè)訪問者的PR是PRi(1)> PRi(2)> PRi(3)> P

105、Ri(4)。如果下面的計(jì)算結(jié)果同上，則說明我所改進(jìn)的算法，不存在邏輯的錯(cuò)誤，計(jì)算結(jié)果沒有錯(cuò)誤。</p><p>　　Visual Basic作為非計(jì)算機(jī)專業(yè)科學(xué)工作者的常用編程軟件深得使用者的好評(píng)，用來實(shí)現(xiàn)數(shù)學(xué)運(yùn)算簡單方便，可以將公式的(3.1)的運(yùn)算關(guān)系表達(dá)的很清楚，但是存在的缺點(diǎn)是對(duì)于多重循環(huán)運(yùn)算，對(duì)編程者的編程水平要求較高。Matlab是矩陣實(shí)驗(yàn)室（Matrix Laboratory）的簡稱，作為數(shù)學(xué)矩陣的

106、專用軟件，由美國新墨西哥大學(xué)教授設(shè)計(jì)，自誕生以來，版本從1.0到7.0，一直受到數(shù)學(xué)工作者的喜愛，對(duì)于數(shù)學(xué)矩陣運(yùn)算編程方法簡單，是數(shù)學(xué)運(yùn)算的常用工具。本文改進(jìn)算法可以表示為矩陣的運(yùn)算，采用matlab計(jì)算比較合適，而且Google 搜索引擎就是用矩陣運(yùn)算得出網(wǎng)頁P(yáng)R值的，但是缺點(diǎn)是不能夠清楚表達(dá)原來的運(yùn)算關(guān)系。比較兩者的優(yōu)缺點(diǎn)，采用兩種方法同時(shí)編程運(yùn)算，發(fā)揮兩者的優(yōu)點(diǎn)，使讀者比較容易理解本文改進(jìn)算法的設(shè)計(jì)思路。同時(shí)也是檢驗(yàn)運(yùn)算結(jié)果是否正

107、確的雙保險(xiǎn)。[11]</p><p>　　3.2.4 Visual Basic編程驗(yàn)證算法收斂</p><p>　　將上面的算法結(jié)合上圖編寫相應(yīng)的VB程序，運(yùn)行循環(huán)結(jié)構(gòu)后得出收斂后的結(jié)果驗(yàn)證算法的正確性：</p><p>　　private Sub Command1_Click()</p><p>　　Dim m, n, l, i, j, k