基于特征值特征向量的網(wǎng)頁分級算法VIP

1、基于特征值特征向量的網(wǎng)頁分級算法摘要 隨著互聯(lián)網(wǎng)的高速發(fā)展，我們如若想在浩瀚的互聯(lián)網(wǎng)海洋上獲取到想要的信息難度與日俱增，因為我們需要不斷地篩選、排除沒用的信息，這會耗費我們大量的時間和精力。所以，我們需要一個好的搜索引擎幫我們過濾掉許多沒用的信息，使我們能夠方便快捷的找到所需信息，Google在這一方面就做的非常優(yōu)秀。當我們用Google搜索某個詞條時，常常會發(fā)現(xiàn)自己感興趣的頁面會排在比較前面的地方，這很大程度上是源于Google的PageRank算法。本文的主要目的是介紹PageRank算法，闡明了PageRank算法的基本原理，并分析了隨機沖浪模型，最后介紹冪法。關鍵詞 PageRank

2、特征向量 隨機沖浪模型 冪法Page classification algorithm based on eigenvalue and eigenvector Abstract With the rapid development of the internet, we get to the wanted information on the internet increasing difficulty, since we need to constantly screened to exclude useless information, which will cost us a lot o

3、f time and energy. So, we need a good search engine to help us to filter out a lot of useless information, which can enables us to easily and quickly find the information we need, in this regard, Google doing very good. When we use Google search for a term, we often find that our interested page wil

4、l be ranked front in the result listings, which largely due to Google's PageRank algorithm. The main purpose of this paper is to introduce the PageRank algorithm, and clarify the basic principles of PageRank algorithm, and analyzes the random surfer model. last, introduce the power method.Keywor

5、ds PageRank Eigenvector The Random Surfer Model Power Method目錄1 引言12簡介搜索引擎12.1 搜索引擎的基本框架13 PageRank算法33.1 PageRank算法簡介33.2 PageRank算法原理33.3 PageRank算法44 隨機沖浪模型75 冪法86結論107 致謝詞11 1 引言隨著現(xiàn)代化科技的高速發(fā)展，我們逐漸進入了大數(shù)據(jù)時代，相應的，互聯(lián)網(wǎng)上的數(shù)據(jù)量也正在以指數(shù)的形式暴增?？偟膩碚f，Web具有四大特點：龐大性、動態(tài)性、異構性、半結構化的數(shù)據(jù)結構環(huán)境。面對越來越多的數(shù)據(jù)，搜索引擎已然成為我們在網(wǎng)上檢索信息的重

6、要工具，Google的搜索引擎是一個成功的例子?；ヂ?lián)網(wǎng)上的網(wǎng)頁除了包含文本、圖片、視頻等信息外，還包含了許多鏈接，用戶可以通過該鏈接訪問其他網(wǎng)頁，Google用鏈接到該網(wǎng)頁的數(shù)量和質量作為評價網(wǎng)頁的重要性的指標。Google查詢的全過程通常不超過半秒，其主要過程是網(wǎng)絡服務器先將查詢發(fā)送到索引服務器，索引服務器所包含的內容與書本索引目錄相似，即說明哪些網(wǎng)頁包含與查詢匹配的文字；然后將查詢的相關結果傳輸?shù)轿臋n服務器，生成描述每個搜索結果的摘錄；最后將結果返回到用戶。PageRank算法主要是將檢索出來的網(wǎng)頁按照重要程度排序，將一些比較重要的網(wǎng)頁放在搜索結果的前面。與HITS相比，PageRank在

7、穩(wěn)定性和適用性上更勝一籌，更適合大規(guī)模的搜索引擎。本文先簡單介紹搜索引擎的基本框架，用以了解搜索引擎的基本工作原理，接著介紹PageRank算法和隨機沖浪模型，最后簡述用冪法求其重要性排序。2 簡介搜索引擎2.1 搜索引擎的基本框架 從本質上說，搜索引擎是一個資料檢索系統(tǒng)，搜索引擎擁有一個資料庫（即互聯(lián)網(wǎng)頁面），用戶提交一個檢索條件（例如關鍵詞），搜索引擎返回符合查詢條件的資料列表。這樣，搜索引擎有兩個核心問題：1、建立資料庫；2、建立一種數(shù)據(jù)結構，可以根據(jù)關鍵詞找到含有這個詞的頁面。 第一個問題一般是通過一種叫做爬蟲的特殊程序實現(xiàn)的。爬蟲就是從一個頁面出發(fā)，通過HTTP協(xié)議通信獲取這個頁面的

8、所有內容，把這個頁面url和內容記錄到資料庫，然后分析頁面的鏈接，再去分別獲取這些鏈接鏈向的頁面內容，將鏈接到的頁面內容記錄到資料庫然后再分析這個頁面的鏈接，一直重復這個過程，就可以將整個互聯(lián)網(wǎng)的頁面全部獲取下來（當然這是理想的情況，要求整個web是一個強連通圖，并且所有頁面的http協(xié)議允許爬蟲抓取頁面，為了簡單，我們假設web是一個強連通圖，且不考慮robots協(xié)議）。下圖為通用爬蟲框架的基本結構圖。圖2-1 通用爬蟲框架 Google至少包含兩套不同目的的爬蟲系統(tǒng)，一套被稱為Fresh Bot，主要考慮網(wǎng)頁的時新性，對于內容更新頻繁的網(wǎng)頁，目前可以達到以秒的更新周期；而另外一套被稱之為D

9、eep Crawl Bot ，主要針對其他更新不是那么頻繁的網(wǎng)頁抓取，以天為更新周期。下圖為Google的兩套爬蟲系統(tǒng)基本結構示意圖。 圖2-2 Google的兩套爬蟲系統(tǒng) 第二個問題是通過一種叫倒排索引來實現(xiàn)的，倒排索引是搜索引擎用來快速查找包含某個單詞的文檔集合的數(shù)據(jù)結構，抽象來說倒排索引是一組key-value結構，key是關鍵詞，value是一些頁面編號集合（假設資料庫中每個頁面都有唯一編號），表示這些頁面含有這個關鍵詞。 例如我們要查詢“張三 微博”：搜索引擎獲取“張三 微博”查詢條件后，將其分為“張三”和“微博”兩個詞；接著從倒排索引中找到“張三”所對應的集合，假設是1,2,4,6

10、,8,12；“微博”所對應的集合試試1,3,4,7,9,12,15,26；將這兩個集合做交運算，結果是1,4,12，最后從資料庫中將1、4、12所對應的頁面返回給用戶就可以了。 PageRank算法的主要作用是對檢索出的結果進行重要性排序，即對上例中的1、4、12進行排序。3 PageRank算法3.1 PageRank算法簡介 PageRank算法是Google專有的算法，用于衡量特定網(wǎng)頁相對于搜索引擎中的其他網(wǎng)頁而言的重要程度。它是由Larry Page和Sergey Brin在20世紀90年代后期提出的，是Google用來標識網(wǎng)頁的等級或重要性的一種方法，是一種在搜索引擎中根據(jù)網(wǎng)頁之間相

11、互的鏈接關系計算網(wǎng)頁排名的技術，其網(wǎng)頁等級為1到10級，級別越高，表示越重要。其實現(xiàn)了將鏈接價值概念作為排名因素，將對頁面的鏈接看成投票，指示了重要性。網(wǎng)頁分級是基于“從許多優(yōu)質的網(wǎng)頁鏈接過來的網(wǎng)頁必定還是優(yōu)質網(wǎng)頁”的回歸關系,來判定所有網(wǎng)頁的重要性.目前為了能夠提高搜索引擎的效率，人們已經進行了許多相關方面的研究，其中有側重于縮短收斂時間的，也有側重于提高查詢結果的準確性。其中也有人提出了分塊式PageRank收斂算法。該算法將網(wǎng)絡中的網(wǎng)頁劃分成不同的數(shù)據(jù)塊，然后計算塊內PageRank值和塊間PageRank值，最后通過兩種PageRank值求得最終向量值，其用分塊的方式降低了矩陣的維數(shù)，

12、有效減少了原算法中的0元素和0相乘計算，從而達到了減少系統(tǒng)運行時的時空開銷目的。3.2 PageRank算法原理 對于某個互聯(lián)網(wǎng)網(wǎng)頁A來說，該網(wǎng)頁的PageRank值計算基于以下兩個基本假設： 數(shù)量假設:在Wed圖模型中，如果一個頁面節(jié)點接收到的其他頁面指向的入鏈數(shù)量越多，那么這個頁面就越重要。質量假設：指向頁面A的入鏈質量會有所不同，質量高的頁面會通過鏈接向其他頁面?zhèn)鬟f更多的權重。所以越是質量高的頁面指向頁面A，頁面A就越重要。PageRank算法使用了投票思想。PageRank依靠的是網(wǎng)民對站點的支持率，利用大量的鏈接結構表明某個單獨頁面的價值。它就像是一個由互聯(lián)網(wǎng)上所有其他頁面發(fā)起的投票

13、，并由此來決定一個網(wǎng)頁的重要性，一個指向某頁面的鏈接代表一張投票。例如，有四個頁面ABCD，其中頁面A只有鏈向頁面B，頁面C鏈向頁面A和頁面D，假設最初每個頁面都同等重要，頁面B跟頁面D都獲得了一票，但鏈向頁面B的頁面A只有一條出鏈，而鏈向頁面D的頁面C有兩條出鏈，這樣頁面C的投票重要性就會被平分，所以，同樣只有一票的頁面B跟頁面D，頁面B顯得更重要一些。即鏈入的頁面數(shù)量跟質量決定了頁面的重要性，如果鏈入的數(shù)量越多且質量越高，則頁面的重要性分數(shù)越高。3.3 PageRank算法 基于前面的兩個假設，我們將網(wǎng)絡上網(wǎng)頁之間的關系抽象成有向圖，即網(wǎng)頁可以看做圖中的節(jié)點，網(wǎng)頁之間的超鏈接看作圖中的有向

14、邊。用表示頁面1到頁面的重要性分數(shù)，則每個頁面的重要性分數(shù)可以由式子 （3-1）表示，其中代表頁面向外的鏈接數(shù)，為頁面的反向鏈接的集合。記，則網(wǎng)絡中所有頁面的關系可以表示成，其中為鄰接矩陣。我們也可以直接根據(jù)圖可以寫出它們的鄰接矩陣，其中如果頁面鏈接到頁面，則，否則。因為頁面跳到他所有鏈接的頁面中的一個的概率是一樣的，所以將頁面的PageRank值平均分配到它所鏈接的頁面上，即對矩陣的每一行做歸一化處理，得矩陣。但是PageRank算法主要關注的不是頁面鏈接到哪些頁面上，而是被哪些頁面鏈接，所以PageRank算法中的矩陣是的轉置，即，其稱為轉移概率矩陣。網(wǎng)頁的重要性分數(shù)就是矩陣的特征值為1所

15、對應的特征向量。 下面證明矩陣有值為1的特征值。定義1：如果方陣的每一項元素都是非負的且每列元素相加和為1，則稱方陣為列隨機矩陣。沒有懸掛結點的網(wǎng)絡所對應的矩陣是列隨機的。命題1：每個列隨機矩陣都有一個值為1的特征值。證明：記為一個的列隨機矩陣，為維列向量且其分量都等于1。因為矩陣和有相同的特征值；又因為是列隨機的，可以容易得出，所以1是的一個特征值，即1也是的特征值。 2 1 3 4圖3-1 簡單的網(wǎng)絡示意圖 例1：如上圖所示，求其頁面的重要性排序。解：由上可得， 求出矩陣的特征值為1的特征向量。再歸一化得到，。 所以得出頁面4最重要，頁面2次之，再到頁面3，最后是頁面1。雖然頁面2獲得了其

16、他所有頁面的鏈接，但卻不是最重要的。頁面2只有鏈接到頁面4，所以將所有投票投給頁面4，再加上頁面1的投票，所以使頁面4變成最重要的。 但是使用上述方法進行網(wǎng)頁排名的時候會出現(xiàn)一些問題。這里我們討論兩個問題:非一性排名跟懸掛節(jié)點。 非唯一排名。當把網(wǎng)絡抽象成有向圖是由幾個互不相連的子圖構成時，此時其矩陣有多個值為1的特征值，所以導致排名不唯一。例2：在圖一中在加兩個頁面，頁面5和頁面6，使其兩兩互相鏈接，如下圖。 5 21 6 43圖3-2 網(wǎng)絡簡單示意圖 相應的矩陣為： ， 求出值為1的特征值有兩個線性無關的特征向量，即和，此時排序就不唯一了。 懸掛節(jié)點。懸掛網(wǎng)頁可能是一個pdf文件或是網(wǎng)頁向

17、外指向的超鏈接還沒有被搜索引擎搜索到，即懸掛節(jié)點是指沒有出鏈的網(wǎng)頁節(jié)點。包含懸掛節(jié)點的網(wǎng)絡生成的矩陣會包含一個或更多個全為0的列。在這種情況下，是列子隨機的，也就是說矩陣的每列分量之和小于或等于1。這種矩陣的所有特征值小于或等于1，但1并不一定要是矩陣的一個特征值。然而，網(wǎng)絡中有懸掛節(jié)點的網(wǎng)頁可以使用類似的技術進行排名。相應的子隨機矩陣必須有一個正的特征值以及對應的非負特征向量用來進行網(wǎng)頁的排名。4 隨機沖浪模型 PageRank算法原理中有個重要的假設：所有的網(wǎng)頁形成一個閉合的鏈接圖，除了這些文檔以外沒有其他任何鏈接的出入，并且每個網(wǎng)頁能從其他網(wǎng)頁通過超鏈接達到但是在現(xiàn)實的網(wǎng)絡中，并不完全是

18、這樣的情況當一個頁面沒有出鏈的時候，它的PageRank值就不能被分配給其它的頁面。同樣道理，只有出鏈接而沒有入鏈接的頁面也是存在的但PageRank并不考慮這樣的頁面，因為沒有流入的PageRank而只流出的PageRank，從對稱性角度來考慮是很奇怪的有時候也有鏈接只在一個集合內部旋轉而不向外界鏈接的現(xiàn)象在現(xiàn)實中的頁面，無論怎樣順著鏈接前進，僅僅順著鏈接是絕對不能進入的頁面群總歸是存在的例如有四個頁面，頁面A鏈向頁面B，頁面B鏈向頁面C，頁面C鏈向頁面D，最后頁面D鏈向頁面A，四個頁面鏈接構成一個環(huán)，則頁面的PageRank值在這個環(huán)內一直傳遞，就不能將值傳遞出去，會導致PageRank值

19、沉淀現(xiàn)象。 PageRank技術為了解決這樣的問題，提出用戶的隨機沖浪模型：用戶雖然在大多數(shù)場合都順著當前頁面中的鏈接前進，但有時會突然停止前進重新打開瀏覽器隨機進入到完全無關的頁面Google認為：用戶在85的情況下沿著鏈接前進，但在15的情況下會跳躍到無關的頁面中用公式表示相應的轉移概率矩陣為 （3-1）其中，為分量全為l的維列向量，從而為全1矩陣，d(0，1)為權重因子，在實際中Google取d=085。也就是說，在隨機沖浪模型中，求各個頁面等級值PageRank 的問題變成了求正矩陣形的最大特征值所屬的特征向量問題 首先證明有值為1的特征值？ 證明：因為d(0，1)，所以可以。又有，所

20、以是正的列隨機矩陣，故有值為1的特征值。 可以證明的值為1的特征值只有唯一一個。由此可以知道無論是由多少個子網(wǎng)組成的網(wǎng)絡，其只有唯一一個排名。 例3：用替換例1中的，并計算其排名。（d取0.85） 得到重要性分數(shù)，與例1有相同的排名，只是分數(shù)略有不同。例4：用替換例1中的，并計算其排名。（d取0.85） 求得，歸一化得重要性分數(shù)為，。此時，用計算有唯一的排序，即允許我們比較不同子網(wǎng)站的網(wǎng)頁。5 冪法 PageRank值的計算步驟： 初始階段:網(wǎng)頁通過鏈接關系構建起Web圖，每個頁面設置相同的PageRank值，通過若干輪的迭代計算，會得到每個頁面所獲得的最終PageRank值。隨著每一輪的計算

21、進行，網(wǎng)頁當前的PageRank值會不斷得到更新。 在每一輪中更新網(wǎng)頁PageRank值的計算方法：在每一輪更新頁面的PageRank值的計算中，每個頁面將其當前的PageRank值平均分配到本頁面包含的出鏈上，這樣每個鏈接就獲得了相應的權值。而每個頁面將所有指向本頁面的入鏈所傳入的權值求和，即可得到新的PageRank值。當每個頁面都獲得了更新后的PageRank值，就完成了一輪PageRank值計算。 PageRank算法在最初的時候賦予每個網(wǎng)頁相同的重要性分數(shù)，通過迭代遞歸計算來更新每個頁面節(jié)點的PageRank值，直到PageRan值穩(wěn)定為止?；谇懊娴挠嬎悴襟E，下面介紹用冪法求特征向

22、量。用冪方法計算矩陣的特征向量的大致思想是：冪法是一種計算矩陣主特征值（按模最大的特征值）及對應特征向量的迭代方法，特別是用于大型稀疏矩陣。若矩陣有特征值，即求及其所對應的特征向量，因為鄰接矩陣的最大特征根為1，所以用冪法迭代出的結果即為網(wǎng)頁的重要性分數(shù)。 1 從向量開始，根據(jù)公式（即）不斷迭代，直到趨于穩(wěn)定，其中為任意一個非零初始向量，為轉移概率矩陣，即上文中的。向量可以看作是矩陣的最大特征值所對應的特征向量。然而，取決于特征值的大小，向量可能是沒有邊界或者接近于0向量。然而，為了確保冪方法在一個合理的范圍內收斂，一個重要的要求是矩陣的最大特征值為1.也就是說，的多項式特點應該是這樣的形式，

23、其中的度為,且不能整除. 或者，矩陣的特征值對應的特征向量應該具有除了特征向量在中的其他不一般性。 2 3圖5-1 網(wǎng)絡簡單示意圖 例6：如上圖，可以得出，其中d=0.85.取則,與相差較大，繼續(xù)迭代。繼續(xù)迭代，.，一直迭代直到于收斂。將歸一化得；若直接取，其直接收斂于。可以求出的特征值為1所對應的特征向量，歸一化得。 在計算機實現(xiàn)的過程中，由于機器運算的特性，收斂的過程使用遞歸運算更為有效，因此使用遞歸運算式，算法表示如下：function =PowerMethod();k=1;Repeat ;k=k+1;Until 其中為設定的閾值，當小于時，便認為已達到收斂了。6 結論 PageRank

24、算法的優(yōu)缺點。 優(yōu)點：PageRank算法是一個與查詢無關的靜態(tài)算法，所有網(wǎng)頁的PageRank值通過離線計算獲得；有效減少在線查詢時的計算量，極大降低了查詢響應時間。 缺點： 1.人們的查詢具有主題特征，PageRank算法忽略了主題相關性，導致結果相關性和主題性降低，會產生主題漂移現(xiàn)象。這樣如果重要性高的排在前面的頁面和搜索主題無關同樣也是沒有意義的，為此，Google使用了完善的超文本匹配分析技術，使得能夠檢索出重要而正確的網(wǎng)頁。2. 舊的頁面等級會比新頁面高，因為即使是非常好的新頁面也不會有很多外鏈，除非它是某個站點的子站點。新的頁面往往沒有較多的頁面鏈向它，所以會導致其PageRan

25、k值會相對舊的頁面小，這時有的新的頁面是比較重要的，卻排在比較靠后的位置。 PageRank算法主要根據(jù)網(wǎng)頁上的網(wǎng)頁的外部鏈接站點的數(shù)量和質量及鏈接頁面等級決定PageRank值的大小，由PageRank值來決定改網(wǎng)頁在搜索引擎中的排名，卻忽略了鏈接頁面對查詢條件的主題相關性。如果該頁面只是在內容中出現(xiàn)了關鍵詞，可主題內容與該關鍵詞相差很大，也會因其存在的頁面PageRank值大而獲得一個比較靠前的排名，這對用戶來說是沒有意義的。所以決定網(wǎng)頁排名不但需要考慮網(wǎng)頁的頁面等級，更要考慮網(wǎng)頁的頁面主題內容與查詢主題的相關性是否對稱。7 致謝詞 本論文是在儲理才老師悉心指導下完成的，感謝老師在忙碌的工

26、作中，抽出時間來解答我的問題，審查修改我的論文，給予我指導與幫助，使我能夠順利完成論文。在此，謹向老師表示崇高的敬意和衷心的感謝！參考文獻1 張巍.基于PageRank算法的搜索引擎優(yōu)化策略研究D.四川：四川大學，2005.2 呂克強.Web超鏈接分析及其在搜索引擎中的應用研究D.北京:中國石油大學，2008.3 張俊林.這就是搜索引擎：核心技術詳解M.北京：電子工業(yè)出版社，2012.4 吳秋月、何江宏.Google矩陣和它的性質J.大學數(shù)學，2006,22(6)：139-143.5 馮振明.分塊式PageRank收斂算法及其改進D.南京:河海大學，2006.6 宿.PageRank算法Z.7 Kurt Bryan、Tanya Leise.The $25,000,000,000 Eigenvector:The Liner Algebra behind GoogleJ.Society for Industrial and Applied Mathematics,2006,48(3):569-581.8 趙國、宋建成.Google搜索引擎的數(shù)學模型及其應用J.西南民族大學學報（自然科學版），2010，36(3):1-4.9 馮振明.Google核心PageRank算法深討J.計算機技術與發(fā)展，2006,16(7):3-6.10 Arasu A.Pagerank c