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

1、<p>　　社會環(huán)境下網(wǎng)頁重要性的研究</p><p><b>　　中文摘要　</b></p><p>　　近年來，隨著internet的不斷發(fā)展，Web已經(jīng)成為人們的重要信息來源，為人們提供了豐富的信息資源。與此同時，它所具有的海量數(shù)據(jù)、復(fù)雜性、極強(qiá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)頁訪問者對網(wǎng)頁重要度權(quán)值的影響 ,所以在一定程度上會造成偏差 。因此 ,合理的將兩者進(jìn)行結(jié)合,充分利用訪問者的知識水平和網(wǎng)頁內(nèi)容特征對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由訪問者知識水平及其投票的情況決定網(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è)計思路16</p><p>　　3.2 計算每個訪問者的PageRank值17</p><p>　　3.2.1 計算訪問者PR值的數(shù)學(xué)表達(dá)式17</

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

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

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)計報告 ( 2005/1) 》用戶在互聯(lián)網(wǎng)上獲取信息最常用的方法是通過搜索引擎:占70. 7 %。遠(yuǎn)遠(yuǎn)高于位于第二位的直接訪問已

14、知的網(wǎng)站:占24. 6% 。搜索引擎的后起之秀 Google 每天處理的搜索請求已達(dá) 2 億次?，F(xiàn)在全球有75%的網(wǎng)上信息搜索是靠Google的技術(shù)完成，大大促進(jìn)了人類的信息搜索的效率。而作為品牌價值，僅Google這個名字的無形資產(chǎn)，竟出人意料地在如此短的時間，一下子超過了蘋果、IMB、可口可樂，真正實現(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ù)理念，以平等、實用、公正為組織原則，優(yōu)化整合全球Web網(wǎng)頁資源。在搜索方法上，Google更是化繁為簡，為大多數(shù)網(wǎng)民利益考慮，做到軟件使用大眾化。其次，在對待語言工具的問題上，不搞大國沙文主義，真正擯棄了語言上的貴賤之分，將多種語言平等地整合在同一界面，實現(xiàn)了以人為

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

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

18、護(hù)量大、信息量少、信息更新不及時。</p><p>　　機(jī)器人搜索引擎:是指通過網(wǎng)絡(luò)搜索軟件(又稱為網(wǎng)絡(luò)蜘蛛[2],網(wǎng)絡(luò)爬行機(jī)器人,網(wǎng)絡(luò)搜索機(jī)器人) 或網(wǎng)站登錄等方式 ,以某種策略自動地在互聯(lián)網(wǎng)中搜集和發(fā)現(xiàn)信息,經(jīng)過加工處理后建庫,從而能夠?qū)τ脩籼岢龅母鞣N查詢作出響應(yīng),提供用戶所需的信息。該類搜索引擎的優(yōu)點(diǎn)是信息量大、更新及時、毋需人工干預(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、自動化程度比目錄式搜索引擎高。網(wǎng)絡(luò)信息量太大了，用計算機(jī)代替人去查找，可以節(jié)省大量的人力。</p><p>　　元搜索引擎：這類搜索引擎沒有自己的數(shù)據(jù)，而是將用戶的查詢請求同時向多個搜索引擎遞交，將返回的結(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、知識庫Repository、索引系統(tǒng)(包括索引器indexer，桶barrels ,文件索引等)、排序器Sorter和搜索器Searcher 5個部分組成。</p><p>　

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

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

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

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

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

27、頁編排成一個與Repository相連接的文檔索引(Document Index)，并記錄下網(wǎng)頁的URL和標(biāo)題，以便可以準(zhǔn)確查找出在Repository中存儲的原網(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形成“鏈接對”，存入Link數(shù)據(jù)庫中；(c)將Anchor Text指向的網(wǎng)頁的docID與順排檔特殊索引項Anchor Hits相連接。 </p><p>　　(7)數(shù)據(jù)庫Link記錄了網(wǎng)頁的鏈接關(guān)系，用來計算網(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)對數(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)生一個新的索引詞表供搜索器(Searcher)使用。搜索器的功能是由網(wǎng)頁服務(wù)器實現(xiàn)的，根據(jù)新產(chǎn)生的索引詞表結(jié)合上述的文檔索引(Document Index)和Link數(shù)據(jù)庫計算的網(wǎng)頁P(yáng)ageRank值來匹配檢索。</p><p>

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

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

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

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)修改和對照。</p><p>　　超鏈分析技術(shù)主

35、要是指利用網(wǎng)頁間存在的各種超鏈指向, 對網(wǎng)頁之間的引用關(guān)系進(jìn)行分析，依據(jù)網(wǎng)頁鏈入數(shù)的多少計算該網(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)把整個網(wǎng)頁文檔集看作一個有向的拓?fù)鋱D，其中每個網(wǎng)頁都構(gòu)成圖中的一個結(jié)點(diǎn)，網(wǎng)頁之間的鏈接就構(gòu)成了結(jié)點(diǎn)間的有向邊，按照這個思想，可以根據(jù)每個結(jié)點(diǎn)的出度和入度來評價網(wǎng)頁的作用。</p>&l

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

37、；b. PageRank 算法是利用整個網(wǎng)頁集合進(jìn)行計算的，不像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)頁重要度的分析，所以不可避免地會產(chǎn)生很多問題，其中，比較明顯

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

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

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

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

42、頁重要度的影響也相應(yīng)降低。綜上而言，一個網(wǎng)頁的重要性決定著同時也依賴于其他網(wǎng)頁的重要性。</p><p>　　PageRank絕對是個很科學(xué)的小創(chuàng)意。說他科學(xué)，你會在我以后的文章中看到Google是如何將數(shù)學(xué)(具體來說多數(shù)是統(tǒng)計學(xué))理論淋漓盡致地發(fā)揮在搜索技術(shù)之中。說他“小”，因為這些理論對于搞數(shù)學(xué)的人來說實在太微不足道了，甚至稍微有些科學(xué)高數(shù)知識的人都能理解。他所用到的統(tǒng)計學(xué)就是循環(huán)迭代計算收斂值的方法！[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表示一個網(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為一個方陣，行和列對應(yīng)網(wǎng)頁集的網(wǎng)頁。如果網(wǎng)頁i有指向網(wǎng)頁j的一個鏈接，則Aij=1/Ni，否則Aij=0。設(shè)V是對應(yīng)網(wǎng)頁集的一個向量，有V=cAV，V為A的特

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

46、<p>　　此處的 v 代表所有的網(wǎng)頁集合,每一個第i+1次的PageRank 值都是基于上次的PageRank值重新計算的。具體的迭代次數(shù)在實際運(yùn)算中是有限的。</p><p>　　Lawrence Page和Sergey Brin在個別場合描述了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的基本計算原理，并不具有普遍性，因為沒有迭代收斂的步驟。</p><p>　　所有PR(Ti)之和還要乘以一個阻尼系數(shù)d，它的值在0到1之間。阻尼系數(shù)的使用，減少了其它頁面對當(dāng)前頁面A的排序貢獻(xiàn)。</p><p>　　一個頁面通過隨機(jī)沖浪到達(dá)的概率就是鏈入它的別的頁面上的鏈接的被點(diǎn)擊概率的和。并且，阻尼系數(shù)d減低了這個概率。阻尼系數(shù)d

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

50、為0.85，但這里我們?yōu)榱撕啽阌嬎憔蛯⑵湓O(shè)為0.5。盡管阻尼系數(shù)d的精確值無疑是影響到PageRank值的，可是它并不影響PageRank計算的原理。因此，我們得到以下計算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>　　這些方程很容易求解，以下得到每個頁面的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é)果對于這個簡單的范例來說并不特殊。</p><p>　　對于這個只有三個頁面的簡單范例來說，通過方程組很容易求得PageRank值。但實際上，互聯(lián)網(wǎng)包含數(shù)以億計的文檔，是不可能解方程組的。下面闡述迭代過程。</p><p>　　由于實際的互聯(lián)網(wǎng)網(wǎng)頁數(shù)量，Google搜索引擎使用了一個近似的、迭代的計算方法計算PageRank值。就是說先給每個網(wǎng)頁一個初

53、始值，然后利用上面的公式，循環(huán)進(jìn)行有限次運(yùn)算得到近似的PageRank值。我們再次使用“三頁面”的范例來說明迭代計算，這里設(shè)每個頁面的初始值為1。</p><p>　　重復(fù)幾次后，我們的到一個良好的接近PageRank理想值的近似值。根據(jù)Lawrence Page和Sergey Brin共開發(fā)表的文章，他們實際需要進(jìn)行100次迭代才能得到整個互聯(lián)網(wǎng)的滿意的網(wǎng)頁級別值。</p><p>　　

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

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

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

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

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

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

60、個網(wǎng)頁文檔都有的、相同的E ( u)</p><p><b>　　n1</b></p><p>　　PageRank迭代運(yùn)算都利用了特征向量作為理論基礎(chǔ)和收斂性依據(jù)[9]，這是超鏈接環(huán)境下此類算法的一個共同特征。</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ì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)頁集會增加很多無關(guān)的網(wǎng)頁 , 產(chǎn)生主題漂移、

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

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

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

66、<p>　　3.1由訪問者知識水平及其投票的情況決定網(wǎng)頁排名的 PageRank 算法</p><p>　　3.1.1 算法中PR值的含義</p><p>　　在Google PageRank傳統(tǒng)算法中，PageRank就是一個概率(它反映了一個人在網(wǎng)絡(luò)中不同的頁面上隨機(jī)點(diǎn)擊鏈接會到達(dá)某個特定網(wǎng)站的概率)。只不過因為人們不太喜歡看小數(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è)知識水平越高。網(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 對網(wǎng)頁 B 所投的一票，由其他網(wǎng)頁對網(wǎng)頁本身的投票來計算網(wǎng)頁的PR值。在改進(jìn)算法中，訪問者對網(wǎng)頁的投票的被認(rèn)同度就是其他訪問者對他的投票，由其他訪問者對他的投票來計算訪問者的PR值。在計算網(wǎng)頁P(yáng)R值時，網(wǎng)頁由訪問者對它的投票來決定網(wǎng)頁的PR值。</p><p>　　不是每個訪問者和網(wǎng)頁的

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

70、價中的作用進(jìn)行區(qū)別對待。事實上，沒有重點(diǎn)的評價就不算是客觀的評價。 </p><p>　　打個比方說, 一件事情, 你給它打100分, 你的老板給它打60分, 如果平均, 則是(100+60)/2=80分. 但因為老板說的話分量比你重, 假如老板的權(quán)重是2, 你是1, 這時求平均值就是加權(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ù)的計算，所以又叫加權(quán)平均數(shù)。</p><p>　　同樣道理每個訪問者和每個網(wǎng)頁的權(quán)重都是不同的因為他們的權(quán)威性是不同的。例如：一個工程院院士關(guān)于PageRank網(wǎng)頁的投票的權(quán)重，比我對PageRank網(wǎng)頁的投票的權(quán)重大得多，因為院士的該領(lǐng)域知識水平(PR值)遠(yuǎn)遠(yuǎn)高于我。</p><p>　　接著是看投票情

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

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

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

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

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

77、的領(lǐng)域有不同的PR值，假設(shè)網(wǎng)頁根據(jù)內(nèi)容可以劃分為i類，即分為i個領(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)站一般給出 好、中、差 或者是贊成、反對、中立等幾個選項給訪問者直接選擇，訪問者只可以選擇其中一個對網(wǎng)頁進(jìn)行評價。投票又可以分為登錄投票和匿名投票

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

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

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

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

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

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

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

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

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

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

88、定會投票，因此上式中的Kijn分四種情況，具體如下：</p><p>　　與訪問者n相同的評價(投票)占所有評價的比例</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á)式一的表示其實不嚴(yán)密，有少數(shù)訪問者會多次訪問同一個網(wǎng)頁但是在這部分人之中又會有極少數(shù)的人會對網(wǎng)站的評價進(jìn)行多次不同的投票也就是給出不同的評價，這并不奇怪，因為人的思想是隨著認(rèn)知水平和社會情況而變化的，因此越后面的投票越具有權(quán)威性，因此最后面投票基本反映了最近的社會情況，越后的投票時訪問者經(jīng)過更加縝

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

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

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

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

94、/p><p>　　PRin(i+1)= (Kijn×L)。</p><p>　　上式表示對i領(lǐng)域的所有網(wǎng)頁中訪問者n被認(rèn)同度的疊加得到PRin，但是相同的認(rèn)同度對于不同的網(wǎng)頁所對訪問者的PR值貢獻(xiàn)是不同的，所以對于不同的網(wǎng)頁有不同的權(quán)重，乘以這個權(quán)重就比較準(zhǔn)確反映了 j網(wǎng)頁對訪問者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值才會對網(wǎng)頁的權(quán)重做出越多貢獻(xiàn)(只有訪問者被認(rèn)同越高，本身的PR值才會對網(wǎng)頁的PR做出相應(yīng)的貢獻(xiàn)，所以乘以Kijn)。</p><p>　　考慮到還有2的網(wǎng)站是非分類網(wǎng)頁，非分類網(wǎng)頁的PR值需要根據(jù)每個訪問者

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

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

98、=設(shè)置歸一化常數(shù)Ci=</p><p>　　因此最后得出某個訪問者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) = //初始化每個訪問者的PageRank</p><p>　　while (|PRin(i)- PRin(i-1)|>ε)　//PageRank收斂前的循環(huán)計算判斷</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ī)范因子的計算，以保證計算結(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ù)的增加，計算結(jié)果越來越收斂，越來越接近真實的PR值，只要循環(huán)次數(shù)足夠多可以得到任何精度的網(wǎng)頁P(yáng)R值。</p><p>　　3.2.3訪問者PR值算法的簡單模型</p><p>　　據(jù)統(tǒng)計，Web已經(jīng)擁有100億左右的靜態(tài)網(wǎng)頁和550億左右的動態(tài)網(wǎng)頁，網(wǎng)民數(shù)量僅中國就有4.16億，因此，PageRank要處理的矩陣是“世界上最大的矩陣”，為了便于討論驗證算法的正確性同時也是

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

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個訪問者的PR是PRi(1)> PRi(2)> PRi(3)> P

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

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

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