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

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

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

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ù)表達形式10<

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

9、><p>　　3.1.1 算法中PR值的含義15</p><p>　　3.1.2 從投票角度分析算法的本質15</p><p>　　3.1.3 算法改進的詳細設計思路16</p><p>　　3.2 計算每個訪問者的PageRank值17</p><p>　　3.2.1 計算訪問者PR值的數(shù)學表達式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 網頁PR值的計算方

11、法37</p><p>　　3.3.1 計算網頁PR值的理論基礎37</p><p>　　3.3.2 建立數(shù)學模型38</p><p>　　3.3.3 Visual Basic編程驗證算法的正確性39</p><p>　　3.3.4 matlab編程驗證算法的正確性42</p><p>　　4．改進算法的事實

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

46、<p>　　此處的 v 代表所有的網頁集合,每一個第i+1次的PageRank 值都是基于上次的PageRank值重新計算的。具體的迭代次數(shù)在實際運算中是有限的。</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) :網頁A頁的PageRank值； </p><p>　　PR(Ti) :鏈接到A頁的網頁Ti的PageRank值； </p><p>　　C(Ti) :網頁Ti的出站鏈接數(shù)量； </p><p>　　d :阻尼系數(shù)，0<d<1。</p>&l

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

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

50、為0.85，但這里我們?yōu)榱撕啽阌嬎憔蛯⑵湓O為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、，等于網頁的總數(shù)。就像以上所提的，此結果對于這個簡單的范例來說并不特殊。</p><p>　　對于這個只有三個頁面的簡單范例來說，通過方程組很容易求得PageRank值。但實際上，互聯(lián)網包含數(shù)以億計的文檔，是不可能解方程組的。下面闡述迭代過程。</p><p>　　由于實際的互聯(lián)網網頁數(shù)量，Google搜索引擎使用了一個近似的、迭代的計算方法計算PageRank值。就是說先給每個網頁一個初

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

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

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

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

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

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

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

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

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

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

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

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

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

66、<p>　　3.1由訪問者知識水平及其投票的情況決定網頁排名的 PageRank 算法</p><p>　　3.1.1 算法中PR值的含義</p><p>　　在Google PageRank傳統(tǒng)算法中，PageRank就是一個概率(它反映了一個人在網絡中不同的頁面上隨機點擊鏈接會到達某個特定網站的概率)。只不過因為人們不太喜歡看小數(shù)，Google才更改了度量。 轉化為0~1

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

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

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

70、價中的作用進行區(qū)別對待。事實上，沒有重點的評價就不算是客觀的評價。 </p><p>　　打個比方說, 一件事情, 你給它打100分, 你的老板給它打60分, 如果平均, 則是(100+60)/2=80分. 但因為老板說的話分量比你重, 假如老板的權重是2, 你是1, 這時求平均值就是加權平均了, 結果是(100*1 + 60*2)/(1+2)=73.3分, 顯然向你的老板那里傾斜了。假如老板權重是3，你的權重是

71、1，結果是(100*1+60*3)/(1+3)=70。這就是根據權重的不同進行的平均數(shù)的計算，所以又叫加權平均數(shù)。</p><p>　　同樣道理每個訪問者和每個網頁的權重都是不同的因為他們的權威性是不同的。例如：一個工程院院士關于PageRank網頁的投票的權重，比我對PageRank網頁的投票的權重大得多，因為院士的該領域知識水平(PR值)遠遠高于我。</p><p>　　接著是看投票情

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

89、訪問者沒有投票</p><p>　　0 ，訪問者n沒有訪問網頁Pij</p><p>　　表達式一的表示其實不嚴密，有少數(shù)訪問者會多次訪問同一個網頁但是在這部分人之中又會有極少數(shù)的人會對網站的評價進行多次不同的投票也就是給出不同的評價，這并不奇怪，因為人的思想是隨著認知水平和社會情況而變化的，因此越后面的投票越具有權威性，因此最后面投票基本反映了最近的社會情況，越后的投票時訪問者經過更加縝

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

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

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

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

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

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

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

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

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

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ù),規(guī)范因子的計算，以保證計算結果的正確性</p><p>　　PRin(i)= Ci PRin(i) //進行規(guī)范化得出的結果</p><p><b>　　i=i+1</b></p><p><b>　　}</b></p><p>

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

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

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

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

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

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