1、PageRank算法算法一小組：王高翔，李渠，劉晴，柳永康，劉昊騁二小組: 王飛，李天照，趙俊杰，陳超，陳瑾翊基本PageRank面向主題PageRankLink Spam與反作弊導(dǎo)航頁與權(quán)威頁一一.Pagerank定義及終點(diǎn)，自連接點(diǎn)的概念定義及終點(diǎn)，自連接點(diǎn)的概念早期搜索引擎的弊端Pagerank的定義終止點(diǎn)自連接點(diǎn)1.早期搜索引擎的弊端早期搜索引擎的弊端早期很多搜索引擎根本不評(píng)價(jià)結(jié)果重要性，而是直接按照某自然順序（例如時(shí)間順序或編號(hào)順序）返回結(jié)果。一旦結(jié)果集變大，簡(jiǎn)直就是一場(chǎng)災(zāi)難，這也注定這種方法不可能用于現(xiàn)代的通用搜索引擎基于檢索詞評(píng)價(jià)的思想非常樸素：檢索關(guān)鍵詞出現(xiàn)次數(shù)越多的頁面匹配度

2、越高，而匹配度越高的頁面重要性越高作弊者可在他網(wǎng)頁上增加一個(gè)詞項(xiàng)，并將該詞項(xiàng)重復(fù)千百次，搜索引擎可能以為該網(wǎng)頁與檢索關(guān)鍵詞高度相關(guān)而把該網(wǎng)頁放在搜索結(jié)果的前列 Pagerank思想： “被越多優(yōu)質(zhì)的網(wǎng)頁所指的網(wǎng)頁，它是優(yōu)質(zhì)的概率就越大”2.Pagerank的定義的定義 Pagerank是一個(gè)函數(shù)，它對(duì)Web中的每個(gè)網(wǎng)頁賦予一個(gè)實(shí)數(shù)值。它的意圖在于，網(wǎng)頁的Pagerank越高，那么它就越“重要”。 首先，我們將Web做如下抽象：1、將每個(gè)網(wǎng)頁抽象成一個(gè)節(jié)點(diǎn)；2、如果一個(gè)頁面A有鏈接直接鏈向B，則存在一條有向邊從A到B。因此，整個(gè)Web被抽象為一張有向圖。2.Pagerank的定義的定義一個(gè)N維矩

3、陣，其中i行j列的值表示用戶從頁面j轉(zhuǎn)到頁面i的概率。這樣一個(gè)矩陣叫做轉(zhuǎn)移矩陣、對(duì)應(yīng)的轉(zhuǎn)移矩陣如左圖設(shè)初始時(shí)每個(gè)頁面的rank值為1/N，這里就是1/4。按A-D順序?qū)㈨撁鎟ank為向量v：第一步之后，沖浪者的概率分布為Mv； 第二步之后，沖浪者的概率分布為Mv； 第i步之后，依次類推，可得沖浪者經(jīng)過i步之后的位置概率分布向量為Miv。 我們可以從初向量v出發(fā)，不斷左乘矩陣M， 直到前后兩輪迭代產(chǎn)生的結(jié)果向量差異很小時(shí)停止，從而得到M的主特征向量。 實(shí)際上，對(duì)于Web本身而言，迭代50-75次已經(jīng)足夠收斂。 3.終止點(diǎn)終止點(diǎn)一個(gè)沒有出鏈的網(wǎng)頁稱為終止點(diǎn)。這里D頁面不存在外鏈，是一個(gè)終止點(diǎn)。由矩

4、陣論的知識(shí)可推知，迭代結(jié)果將最終歸零。那么該如何處理終止點(diǎn)呢？迭代拿掉圖中的終止點(diǎn)及終止點(diǎn)相關(guān)的邊（之所以迭代拿掉是因?yàn)楫?dāng)目前的終止點(diǎn)被拿掉后，可能會(huì)出現(xiàn)一批新的終止點(diǎn)），直到圖中沒有終止點(diǎn)。對(duì)剩下部分計(jì)算rank，然后以拿掉終止點(diǎn)逆向順序反推終止點(diǎn)的rank值。4.自連接點(diǎn)自連接點(diǎn)如下圖，D有外鏈所以不是終止點(diǎn)，但是它只鏈向自己（注意鏈向自己也算外鏈，當(dāng)然同時(shí)也是個(gè)內(nèi)鏈）。這種節(jié)點(diǎn)叫做自連接點(diǎn)，如果對(duì)這個(gè)圖進(jìn)行計(jì)算，會(huì)發(fā)現(xiàn)D的rank越來越大趨近于1，而其它節(jié)點(diǎn)rank值幾乎歸零。單擊添加擊添加為了克服這種問題，需要對(duì)PageRank計(jì)算方法進(jìn)行一個(gè)平滑處理，具體做法是加入“跳轉(zhuǎn)因子（tel

5、eporting）”。所謂跳轉(zhuǎn)因子，就是我們認(rèn)為在任何一個(gè)頁面瀏覽的用戶都有可能以一個(gè)極小的概率瞬間轉(zhuǎn)移到另外一個(gè)隨機(jī)頁面。當(dāng)然，這兩個(gè)頁面可能不存在超鏈接，因此不可能真的直接轉(zhuǎn)移過去，跳轉(zhuǎn)因子只是為了算法需要而強(qiáng)加的一種純數(shù)學(xué)意義的概率數(shù)字。單擊此處添加段落文字內(nèi)容單擊此處添加段落文字內(nèi)容其中往往被設(shè)置為一個(gè)比較小的參數(shù)（0.2或更?。?，e為N維單位向量，加入e的原因是這個(gè)公式的前半部分是向量，因此必須將/N轉(zhuǎn)為向量才能相加。這樣，整個(gè)計(jì)算就變得平滑，因?yàn)槊看蔚慕Y(jié)果除了依賴轉(zhuǎn)移矩陣外，還依賴一個(gè)小概率的心靈轉(zhuǎn)移。如果按這個(gè)公式迭代算下去，會(huì)發(fā)現(xiàn)自連接點(diǎn)的問題解決了，從而每個(gè)頁面都擁有一個(gè)

6、合理的pagerank。單擊此處添加段落文字內(nèi)容單擊此處添加段落文字內(nèi)容分塊式Pagerank算法：原來的算法存在的問題：原來的算法存在的問題：1.時(shí)間開銷大。每次迭代就算時(shí)間開銷為2.因特網(wǎng)中數(shù)據(jù)大部分是分布式的，計(jì)算過程需要多次傳遞數(shù)據(jù)，網(wǎng)絡(luò)負(fù)擔(dān)太大。3.n維矩陣式一個(gè)稀疏矩陣，無論計(jì)算還是存儲(chǔ)都很浪費(fèi)資源。能否考慮先算出局部的Pagerank值？單擊此處添加段落文字內(nèi)容單擊此處添加段落文字內(nèi)容分塊式Pagerank算法：1.分?jǐn)?shù)據(jù)塊，計(jì)算每一個(gè)網(wǎng)絡(luò)圖Gi的的Local Pagerank。算法實(shí)現(xiàn)步驟：2.根據(jù)各數(shù)據(jù)塊之間的相關(guān)性，計(jì)算縮略圖p的Blockrank。3.將所得Local P

7、agerank和Blockrank按照一定原則進(jìn)行計(jì)算，得到一個(gè)新的n維Pagerank. 4.將n維Pagerank多次迭代，得到最后收斂的pagerank向量。面向主題面向主題PageRank動(dòng)機(jī)動(dòng)機(jī)n 不同的人有不同的興趣，而有時(shí)完全不同的興趣卻采用相同的查詢?cè)~項(xiàng)來表達(dá)。如果搜索引擎能夠推斷出用戶的興趣，那么在返回相關(guān)頁面的時(shí)候會(huì)表現(xiàn)得更好n 比如用戶搜索蘋果理想情況實(shí)際情況做法做法每個(gè)用戶有一個(gè)私人的PageRank向量對(duì)每一個(gè)主題方向建立偏向該主題的一個(gè)PageRank向量Open Directory(DMOZ)分16個(gè)頂層類別思路及公式思路及公式假定我們知道某些網(wǎng)頁代表一個(gè)主題（體

8、育），為了構(gòu)建面向主題的PageRank，我們可以安排隨機(jī)沖浪者只到達(dá)一個(gè)隨機(jī)的體育類網(wǎng)頁，而不是到達(dá)任意類別的一個(gè)網(wǎng)頁。這種做法的后果是，隨機(jī)沖浪者很可能停留在已知的體育類網(wǎng)頁上，或者從這些已知的體育類網(wǎng)頁上通過較短的路徑就可到達(dá)的網(wǎng)頁上。體育類網(wǎng)頁鏈向的網(wǎng)頁很可能與體育類相關(guān)，隨著離已知體育類網(wǎng)頁的距離的增加，這些網(wǎng)頁離體育相關(guān)的概率也隨之降低。假定S是一個(gè)網(wǎng)頁的集合，其中的網(wǎng)頁屬于類別S（隨機(jī)跳轉(zhuǎn)集合）。es是一個(gè)向量，如果其分量對(duì)應(yīng)的網(wǎng)頁屬于S，則該分量置為1，否則為0。于是S的面向主題的PageRank的迭代公式如下:M 是Web的轉(zhuǎn)移矩陣，|S|是集合S的大小例子例子n 假設(shè) =

9、0.8 S=B,D.于是轉(zhuǎn)移矩陣乘以得：那么(1 )eS/|S| 的第二和第四個(gè)分量是 1/10，其它分量為0.因?yàn)? =1/5,S的大小為2,向量es中B和D對(duì)應(yīng)的分量為1，A和C 對(duì)應(yīng)分量為0n 迭代過程:初始V面向主題的面向主題的PageRank的使用的使用n 為了將面向主題的PageRank集成到搜索引擎中，我們必須1.確定哪些主題需要構(gòu)建特定的PageRank2.對(duì)每個(gè)主題選擇一個(gè)隨機(jī)跳轉(zhuǎn)集合，使用該集合來計(jì)算面向當(dāng)前主題的PageRank向量值3.對(duì)特定的搜索查詢請(qǐng)求，尋找一種方法來確定最相關(guān)的主題和主題集合4.對(duì)上述查詢，應(yīng)用步驟3中選出的主題和主題的集合的PageRank向量來

10、返回應(yīng)答結(jié)果。上述過程第三步是最棘手的，現(xiàn)有一些解決方法：A.允許用戶從菜單中選擇一個(gè)主題B.通過用戶最近搜索查詢或最近瀏覽的Web網(wǎng)頁來推斷主題C.利用用戶的信息（如用戶的收藏夾或者社交網(wǎng)站上列出的興趣）來推斷主題確定一個(gè)網(wǎng)頁的所屬類別可以使用“基于詞匯的主題判斷”方法三、三、Link Spam與反作弊與反作弊Link Spam方法方法 交交 換換 鏈鏈 接接交換鏈接是指網(wǎng)站之間人為地互相增加對(duì)方網(wǎng)站的鏈接，是增加外鏈成本最低和使用最多的一種方法。由于交換鏈接可以增加網(wǎng)站的外鏈，提高網(wǎng)站的pagerank值。 鏈鏈 接接 農(nóng)農(nóng) 場(chǎng)場(chǎng) 鏈接農(nóng)場(chǎng)是指由互聯(lián)網(wǎng)中的一部分網(wǎng)頁組成，這些網(wǎng)頁非常密集地

11、互相連接在一起。鏈接農(nóng)場(chǎng)是通過創(chuàng)建一個(gè)堆砌大量鏈接而沒有實(shí)質(zhì)內(nèi)容的網(wǎng)頁，這些鏈接彼此互鏈，或指向特定網(wǎng)站，以提高某個(gè)或者某些特定網(wǎng)頁的Pagerank值為目的。Link Spam 開開 源源 建建 站站 系系 統(tǒng)統(tǒng)開源建站系統(tǒng)中的大多數(shù)網(wǎng)頁都是由網(wǎng)頁模板生成的，網(wǎng)頁模板中含有固定的鏈接指向一些共同的網(wǎng)頁甚至是作弊網(wǎng)頁。 黃黃 金金 鏈鏈 指一些高權(quán)重的網(wǎng)站出售首頁的鏈接給作弊網(wǎng)站，提高作弊網(wǎng)站的pagerank值。鏈接農(nóng)場(chǎng)鏈接農(nóng)場(chǎng)設(shè)T的總rank為y，則y由三部分組成：1、可達(dá)頁的rank貢獻(xiàn)，設(shè)為x。2、心靈轉(zhuǎn)移的貢獻(xiàn)，為/n。其中n為全部網(wǎng)頁的數(shù)量，為轉(zhuǎn)移參數(shù)。3、支持頁的貢獻(xiàn)：設(shè)有m個(gè)支

12、持頁，因?yàn)槊總€(gè)支持頁只和T有鏈接，所以可以算出每個(gè)支持頁的rank為： 則支持頁貢獻(xiàn)的全部rank為：因此可以得到： 鏈接農(nóng)場(chǎng)鏈接農(nóng)場(chǎng) 由于相對(duì)，n非常巨大，所以可以認(rèn)為/n近似于0。 簡(jiǎn)化后的方程為： 解方程得： 假設(shè)為0.2，則1/(2-2) = 2.77則這個(gè)spam farm可以將x約放大2.7倍。Link Spam反作弊反作弊 一種方法是通過對(duì)網(wǎng)頁的圖拓?fù)浣Y(jié)構(gòu)分析找出可能存在的spam farm。 但是隨著Web規(guī)模越來越大，這種方法非常困難，因?yàn)閳D的特定結(jié)構(gòu)查找是時(shí)間復(fù)雜度非常高的一個(gè)算法，不可能完全靠這種方法反作弊。網(wǎng)絡(luò)拓?fù)浞治鼍W(wǎng)絡(luò)拓?fù)浞治鯨ink Spam反作弊反作弊 Trus

13、tRank的思想很直觀：如果一個(gè)頁面的普通rank遠(yuǎn)高于可信網(wǎng)頁的topic rank，則很可能這個(gè)頁面被spam了。設(shè)一個(gè)頁面普通rank為P，TrustRank為T，則定義網(wǎng)頁的Spam Mass為：(P T)/P。Spam Mass越大，說明此頁面為spam目標(biāo)頁的可能性越大。TrustRank四、權(quán)威頁與導(dǎo)航頁四、權(quán)威頁與導(dǎo)航頁P(yáng)age 28鏈接分析技術(shù)鏈接分析技術(shù)PageRank：關(guān)注 鏈接 的入度和出度，即本網(wǎng)頁與其他網(wǎng)頁的關(guān)系，計(jì)算出一個(gè)PR值，由此，來判斷網(wǎng)頁的重要程度。而此項(xiàng)，是搜索引擎查詢時(shí)另外一個(gè)依據(jù)，可以說是第一個(gè)過濾項(xiàng)。HITS: 分析網(wǎng)頁的導(dǎo)航度和權(quán)威度，由此來判斷

14、網(wǎng)頁的作用。倒排索引：第一代搜索技術(shù)，將網(wǎng)頁的數(shù)據(jù)分解成關(guān)鍵詞項(xiàng)，然后按關(guān)鍵字建立索引，由關(guān)鍵字索引找到對(duì)應(yīng)的網(wǎng)頁。另外，還有非主屬性值，有稱副鍵值。帶有倒排索引的文件被稱為倒排文件，倒排文件中 次關(guān)鍵字索引被稱為倒排表。由倒排表可以對(duì)集合進(jìn)行并、交等操作，得到結(jié)果后再對(duì)記錄進(jìn)行操作。Page Rank判斷頁面重要性判斷頁面重要性Page 29PageRank，有效地利用了 Web 所擁有的龐大鏈接構(gòu)造的特性。 從網(wǎng)頁A導(dǎo)向網(wǎng)頁B的鏈接被看作是對(duì)頁面A對(duì)頁面B的支持投票，Google根據(jù)這個(gè)投票數(shù)來判斷頁面的重要性。可是 Google 不單單只看投票數(shù)(即鏈接數(shù))，對(duì)投票的頁面也進(jìn)行分析。重要

15、性高的頁面所投的票的評(píng)價(jià)會(huì)更高，因?yàn)榻邮苓@個(gè)投票頁面會(huì)被理解為重要的物品。根據(jù)這樣的分析,得到了高評(píng)價(jià)的重要頁面會(huì)被給予較高的 Page Rank(網(wǎng)頁等級(jí))，在檢索結(jié)果內(nèi)的名次也會(huì)提高。PageRank 是 Google 中表示網(wǎng)頁重要性的綜合性指標(biāo)，而且不會(huì)受到各種檢索(引擎)的影響。倒不如說，PageRank 就是基于對(duì)使用復(fù)雜的算法而得到的鏈接構(gòu)造的分析，從而得出的各網(wǎng)頁本身的特性。當(dāng)然，重要性高的頁面如果和檢索詞句沒有關(guān)聯(lián)同樣也沒有任何意義。為此 Google 使用了精練后的文本匹配技術(shù)，使得能夠檢索出重要而且正確的頁面。PageRank 能夠?qū)W(wǎng)頁的重要性做出客觀的評(píng)價(jià)Page 3

16、01、敏感度較高，反應(yīng)較快 Google對(duì)新建的網(wǎng)站具有較高的查知性， Google收錄新建網(wǎng)站的兩個(gè)途徑是： 第一，通過網(wǎng)站的外部鏈接； 第二，通過向Google提交網(wǎng)站登錄數(shù)據(jù)。 如果Google對(duì)外部鏈接網(wǎng)站的評(píng)價(jià)高、收錄頻率高那么其發(fā)現(xiàn)新站的速度也相應(yīng)地高，新建網(wǎng)站被收錄的日期就會(huì)被提前。2、并重相關(guān)性和重要性Google 使用 PageRank 技術(shù)檢查整個(gè)網(wǎng)絡(luò)鏈接結(jié)構(gòu)，并確定哪些網(wǎng)頁重要性最高。然后進(jìn)行超文本匹配分析，以確定哪些網(wǎng)頁與正在執(zhí)行的特定搜索相關(guān)。在綜合考慮整體重要性以及與特定查詢的相關(guān)性之后，Google 才把最相關(guān)最可靠的搜索結(jié)果放在首位。PageRank 能夠?qū)W(wǎng)頁

17、的重要性做出客觀的評(píng)價(jià)Page 314、較重視鏈接的文字描述Google會(huì)把鏈接的文字描述作為關(guān)鍵詞加以索引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)估該頁的重要性。3、變化較快、機(jī)動(dòng)性較高Google 漫游器會(huì)定期抓取 Web，把大量網(wǎng)頁列入索引。稍后完成的下一次抓取會(huì)注意到新網(wǎng)站、對(duì)現(xiàn)有網(wǎng)站的更改以及失效的鏈接，并對(duì)內(nèi)容的變化在搜索結(jié)果中加以調(diào)整。Page 32權(quán)威頁與導(dǎo)航頁權(quán)威頁與導(dǎo)航頁某些網(wǎng)頁提

18、供某個(gè)主題的信息，而且具有非常重要的信息，這些網(wǎng)頁被稱為權(quán)威頁不提供主題信息，但可以找到有關(guān)該主題的網(wǎng)頁信息，這樣網(wǎng)頁的被稱為導(dǎo)航頁“導(dǎo)航頁和權(quán)威頁”的計(jì)算方式類似于pagerank，通過矩陣-向量的方式迭代，直到一個(gè)收斂的點(diǎn)。其算法又稱HITS算法。pagerank考慮的是網(wǎng)頁重要性的一維重要性信息，而HITS認(rèn)為網(wǎng)頁具有二維的重要性信息：Page 33導(dǎo)航頁與權(quán)威頁導(dǎo)航頁與權(quán)威頁表示形式：每個(gè)網(wǎng)頁都有一個(gè)權(quán)威度和導(dǎo)航度屬性，若分別用h和a來表示網(wǎng)頁的兩個(gè)屬性，那么h和a第j個(gè)分量就分別表示第j個(gè)網(wǎng)頁的權(quán)威度值和導(dǎo)航度值。每個(gè)網(wǎng)頁的導(dǎo)航度就等于累加其鏈出網(wǎng)頁的權(quán)威度，每個(gè)網(wǎng)頁的權(quán)威度就等于累加其鏈入網(wǎng)頁的導(dǎo)航度。并保證歸一化。單擊此處添加段落文字內(nèi)容單擊此處添加段落文字內(nèi)容這樣會(huì)