第3章03節(jié)-網(wǎng)絡(luò)信息主動獲取及處理-PageRank排序

1、信息內(nèi)容安全信息內(nèi)容安全 王佰靈王佰靈技術(shù)技術(shù)CellCellEmail:wblhitEmail: 2Google簡介l 1998年由斯坦福大學(xué)計算機系的博士研究生Larry Page 和Sergey Brin創(chuàng)辦。l 革命性發(fā)明：Page Rank網(wǎng)頁排名算法l 徹底解決了搜索結(jié)果排序的問題3Baidu v.s. Google 百度注重文字，谷歌注重代碼 百度注重用戶，谷歌注重技術(shù) 百度很謹慎，谷歌很效率4Google搜索核心算法網(wǎng)頁級別（PageRank） 按網(wǎng)頁鏈接廣泛程度判斷網(wǎng)頁重要性，是Google中表示網(wǎng)頁重要性的綜合性指標。頁面

2、分析（PageAnalysis） 按頁面標題是否出現(xiàn)關(guān)鍵詞、網(wǎng)頁內(nèi)關(guān)鍵詞出現(xiàn)的頻率及關(guān)鍵詞出現(xiàn)的位置確定哪些網(wǎng)頁與正在執(zhí)行的搜索密切相關(guān)。5PageRank技術(shù) PageRank會通過解析一個具有5億多個變量和20億個條件方程，對網(wǎng)頁的重要性進行客觀測定。PageRank會將網(wǎng)頁A上指向網(wǎng)頁B的鏈接解釋為由網(wǎng)頁A對網(wǎng)頁B所投的一票，而不是計算直接的鏈接數(shù)。然后Page根據(jù)網(wǎng)頁收到的票數(shù)來評估其重要性。 Page也會考慮發(fā)出投票的每個網(wǎng)頁的重要性，也就是某些網(wǎng)頁的投票具有價值較大，為該鏈接的頁面富裕的價值也就較大。重要的網(wǎng)頁會得到較高的PageRank，并出現(xiàn)在搜索的頂部。Google技術(shù)是利用

3、網(wǎng)絡(luò)融合信息來確定網(wǎng)頁的重要性。因為沒有人工干涉，也就不對結(jié)果進行操縱，所以用戶一直信任Google是一個不會因為付費而影響排名的客觀信息來源。6PageRank對搜索結(jié)果的影響結(jié)合了所有網(wǎng)頁重要性和相關(guān)性指標，Google將最相關(guān)和最可靠的結(jié)果放在搜索結(jié)果的頂端。一般而言，PageRank對于排名的影響比頁面分析還高。7PageRank算法思想簡介 基本依據(jù)： PageRank 基于假設(shè)關(guān)系“許多優(yōu)質(zhì)的許多優(yōu)質(zhì)的網(wǎng)頁鏈接的網(wǎng)頁，必定是優(yōu)質(zhì)網(wǎng)頁網(wǎng)頁鏈接的網(wǎng)頁，必定是優(yōu)質(zhì)網(wǎng)頁”，判定所有網(wǎng)頁的重要性。8PageRank要點大致有3個: 鏈入鏈接鏈入鏈接數(shù) 單純意義上的受歡迎度指標 鏈入鏈接鏈入鏈

4、接是否來自受歡迎程度高的頁面 有根據(jù)的受歡迎指標 鏈入鏈接源鏈入鏈接源頁面的鏈出鏈接數(shù) 被選中的概率指標9PageRank計算 互聯(lián)網(wǎng)是一個有向圖 每一個網(wǎng)頁是圖的一個頂點 網(wǎng)頁間的每一個超鏈接是圖的一個有向邊 用鄰接矩陣來表示圖，即：定義鄰接矩陣為G，若網(wǎng)頁j到網(wǎng)頁i有超鏈接，則 ；反之， 。 顯然，如果網(wǎng)頁有N 個，則矩陣為NN 的0、1方陣。1ijg0ijg10多個網(wǎng)頁相多個網(wǎng)頁相互鏈接的圖互鏈接的圖對應(yīng)的鄰接對應(yīng)的鄰接矩陣（這里矩陣（這里將將0,10,1值用值用二值圖像顯二值圖像顯示，黑色代示，黑色代表表0 0，白色，白色代表代表1 1）11PageRank的計算 定義鄰接矩陣為G，若

5、網(wǎng)頁j到網(wǎng)頁i有超鏈接，則 ；反之， 。 記矩陣G的列和、行和分別是 它們分別給出了頁面j的鏈出鏈接數(shù)目和鏈入鏈接數(shù)目iijjgcjijigr1ijg0ijg12PageRank的計算 假設(shè)我們在上網(wǎng)的時侯瀏覽頁面并選擇下一個頁面，這個過程與過去瀏覽過哪些頁面無關(guān)，而僅依賴于當前所在的頁面，那么這一選擇過程可以認為是一個有限狀態(tài)、離散時間的隨機過程，其狀態(tài)轉(zhuǎn)移規(guī)律用Markov鏈描述。 定義轉(zhuǎn)移概率矩陣)(ijaAjijijcga nji.1,13PageRank的計算 根據(jù)Markov鏈的基本性質(zhì)，對于正則Markov鏈，存在平穩(wěn)分布 ，滿足 表示在極限狀態(tài)（轉(zhuǎn)移次數(shù)趨于無限）下各網(wǎng)頁被訪問

6、的概率分布。 定義為網(wǎng)頁的PageRank向量， 表示第i個網(wǎng)頁的PageRank值TNxxx),(21Aiix1ix14某7個網(wǎng)頁之間的鏈接關(guān)系圖 15網(wǎng)頁鏈接圖的鄰接矩陣 0 1 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0G = 16PageRank的計算 011/2 01/41/201/501/21/3 0 001/50 01/31/4 001/50 0 01/4 001/50 01/3 01/21 00 0 01/4 001/50 0 0 0

7、00A =狀態(tài)轉(zhuǎn)移概率矩陣A17PageRank的計算0.6994565338373890.3828604185215180.3239588156720540.2429691117540400.4123112199462510.1030778049865630.1398913067674780.3035143769968050.1661341853035140.1405750798722040.1054313099041530.1789137380191690.04472843450479230.0607028753993610求特求特征值征值1 1對對應(yīng)的應(yīng)的特征特征向量向量歸一化歸一化18

8、7個網(wǎng)頁的PageRank值19PageRank結(jié)果的評價 將 PageRank 的評價按順序排列(PageRank小數(shù)點3位四舍五入):20頁面之間相互關(guān)系及狀態(tài)轉(zhuǎn)移圖21PageRank結(jié)果的評價 首先應(yīng)該關(guān)注的是，PageRank的名次和鏈入鏈接鏈入鏈接的數(shù)目是基本一致的。無論鏈接多少鏈出鏈接鏈出鏈接都幾乎不會影響PageRank，相反地有多少鏈入鏈接鏈入鏈接卻是從根本上決定PageRank的大小。 但是，僅僅這些并不能說明第1位和第2位之間的顯著差別，在鏈入鏈接相同的情況下，鏈出鏈接數(shù)也影響PageRank的大小。(同樣地、第3位和第4位，第6位和第7位之間的差別)。 總之，絕妙之處在

9、于PageRank并不只是通過鏈入鏈接鏈入鏈接數(shù)來決定的。 22PageRank結(jié)果的評價 讓我們詳細地看一下。ID=1 的頁面的PageRank 是0.304，占據(jù)全體的三分之一，成為了第1位。特別需要說明的是，起到相當大效果的是從排在第3位的 ID=2 頁面中得到了所有的PageRank (0.166) 數(shù)。ID=2頁面有從3個地方過來的鏈入鏈接鏈入鏈接，而只有面向 ID=1頁面的一個鏈接，因此(面向ID=1頁面的)鏈接就得到了所有的PageRank數(shù)。不過，就因為ID=1頁面是鏈出鏈出鏈接鏈接和鏈入鏈接鏈入鏈接最多的頁面，也可以理解它是最受歡迎的頁面。23PageRank結(jié)果的評價 反過

10、來，最后一名的 ID=6 頁面只有 ID=1 的15的微弱評價，這可以理解為是因為沒有來自 PageRank 很高的 ID=1 的鏈接而使其有很大地影響。 總之，即使有同樣的鏈入鏈接鏈入鏈接的數(shù)目，鏈接源頁面評價的高低也影響 PageRank 的高低。24 實際地試著計算一下PageRank的收支。因為=1所以計算很簡單，只要將自各頁的流入量單純相加即可。譬如 ID=1 的流入量=(ID=2發(fā)出的發(fā)出的Rank)+(ID=3發(fā)出的發(fā)出的Rank)+ (ID=5發(fā)出的發(fā)出的Rank)+(ID=6發(fā)出的發(fā)出的Rank) = 0.166+0.141/2+0.179/4+0.045/2 = 0.303

11、75 頁面之間狀態(tài)轉(zhuǎn)移圖的驗證25PageRank算法實際應(yīng)用的困難算法實際應(yīng)用的困難1.現(xiàn)實世界和假想模型不同；2.實際計算上，80億的網(wǎng)頁數(shù)量，計算非常困難。 26現(xiàn)實世界和假想模型的不同現(xiàn)實世界和假想模型的不同現(xiàn)實世界： 1. 順著鏈接前進的話，有時會走到完全沒有鏈出鏈接的網(wǎng)頁； 2. 同樣道理，只有鏈出的鏈接而沒有鏈入的鏈接的頁面也是存在的。（不考慮） 3.有時候也有鏈接只在一個集合內(nèi)部旋轉(zhuǎn)而不向外界鏈接的現(xiàn)象。假想的理論模型： 正則鏈（或稱回歸類，無吸收狀態(tài)） 現(xiàn)實世界和假想模型的不同現(xiàn)實世界和假想模型的不同28實際問題可能出現(xiàn)的情況 最大特征值不唯一，導(dǎo)致特征向量不唯一，無法對網(wǎng)頁

12、進行排序29問題的解決方法 為了解決這樣的問題， PageRank考慮了這樣一種瀏覽模型用戶雖然在許多場合用戶雖然在許多場合都順著當前頁面中的鏈接前進都順著當前頁面中的鏈接前進, 但時常會跳但時常會跳躍到完全無關(guān)的頁面躍到完全無關(guān)的頁面。 將時常這個概率固定為 15 來計算。則用戶在 85 的情況下沿著鏈接前進, 但在 15 的情況下會突然跳躍到無關(guān)的頁面中去。(注:PageRank 的原始參數(shù)是87(1/1.15 )和13(0.15/1.15)。) 30問題的解決方法 即A= c*A +(1-c)*1/N 其中，1/N是所有要素為 1/N 的 N次正方行列，c =0.85(=1-0.15)。

13、A是新的狀態(tài)轉(zhuǎn)移矩陣。 也就是說，根據(jù) PageRank 的變形，原先求矩陣A的特征值問題變成了求矩陣 A的最大特征值對應(yīng)特征向量的問題了。31方法的數(shù)學(xué)解釋 從數(shù)學(xué)角度看，把非正則鏈的狀態(tài)轉(zhuǎn)移矩陣正則化，就是把不是強聯(lián)通的圖變成強聯(lián)通的，是一種變換操作。 對全部的要素都考慮0.15的轉(zhuǎn)移概率，意味著將原本非正則的狀態(tài)轉(zhuǎn)移矩陣轉(zhuǎn)換為正則的狀態(tài)轉(zhuǎn)移矩陣，將原本并非強連通的圖變成了強聯(lián)通的。 相對于原來的狀態(tài)轉(zhuǎn)移矩陣，這樣的變換操作能保證最大特性值的次數(shù)為1，也就保證了PageRank的存在。PageRank數(shù)值計算難點33PageRank數(shù)值計算難點（一） 計算機容量限制 假設(shè) N 是 104 的 order。通常，數(shù)值計算程序內(nèi)部行列和矢量是用雙精度記錄的，N 次正方行列 A 的記憶領(lǐng)域為 sizeof(double)* N * N =8 *104 * 104800MB。N 如果變成