資源描述：
《信息檢索之pagerank算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、...一、實驗?zāi)康膗理解PageRank算法的基本思想和原理；u了解鏈接結(jié)構(gòu)分析的應(yīng)用和意義（主要是與排序因素的融合）；u了解PageRank的簡化算法、標(biāo)準(zhǔn)算法和加速算法的異同及改進(jìn)辦法。二、實驗原理及基本技術(shù)路線圖（方框原理圖）PageRank是Google公司的拉里·佩奇（LarryPage）等人提出的鏈接分析算法，算法也以佩奇的姓氏命名為“PageRank”。PageRank是根據(jù)萬維網(wǎng)超鏈接關(guān)系對網(wǎng)頁重要程序進(jìn)行估計的算法，相關(guān)技術(shù)在2008年1月申請了美國專利，并在同年謝爾蓋·布林和拉里·佩奇的論文“大規(guī)模超文本萬維網(wǎng)搜索引擎的架構(gòu)”（TheAn
2、atomyofaLarge-ScaleHypertextualWebSearchEngine）中首次被公開。PageRank依靠萬維網(wǎng)鏈接結(jié)構(gòu)分析對網(wǎng)頁個體的質(zhì)量進(jìn)行評估，算法將從頁面A到頁面B的超鏈接作為A向B的一次投票，但并非簡單地靠統(tǒng)計票數(shù)來衡量質(zhì)量高低，算法還充分考慮了投票者的因素，本身較“重要”的網(wǎng)頁的投票會更受重視。顯然這樣計算出的網(wǎng)頁質(zhì)量評估結(jié)果比單純依靠入度的評估方式更為合理，因為后者實質(zhì)上是認(rèn)為鏈接向當(dāng)前頁面的各個頁面的地位是平等的，這是一個不符合萬維網(wǎng)實際情況的假設(shè)。PageRank是一種衡量“網(wǎng)頁質(zhì)量”的方式，由于“質(zhì)量”的定義本身帶有
3、很強(qiáng)的主觀性，因此“網(wǎng)頁質(zhì)量”的定義也千差萬別，可以從時效性、頁面結(jié)構(gòu)組織、獨(dú)特性等不同角度加以定義，而HITS算法使用的“鏈接權(quán)威度”與“內(nèi)容權(quán)威度”也是一種“網(wǎng)頁質(zhì)量”的定義方式。對于PageRank而言，它使用用戶隨機(jī)瀏覽互聯(lián)網(wǎng)時訪問到某個頁面的概率大小作為此頁面的“質(zhì)量”的定義。PageRank算法所建立的用戶瀏覽模型被稱為“隨機(jī)游走”（randomwalk）模型。用戶使用一個特殊的瀏覽器來瀏覽網(wǎng)頁，這個瀏覽器沒有地址欄、后退按鈕，即只能順著網(wǎng)頁鏈接瀏覽。同時提供一個“隨便逛逛”的功能，可以通過點(diǎn)此按鈕隨機(jī)打開萬維網(wǎng)上的一個網(wǎng)頁開始瀏覽。那么，網(wǎng)頁A
4、被訪問的概率可以用如下公式計算得到：......上式右半部分是使用“隨便逛逛”功能訪問到頁面A的概率，而后半部分則是使用超鏈接訪問到頁面A的概率，兩者相加即為訪問到頁面A的總概率大小?？芍绻o定參數(shù)α，頁面A的PageRank值事實上是由鏈接到它的各個頁面的PageRank值決定的。其計算過程與HITS算法的計算過程類似，也是一個迭代計算的過程，算法流程如下所示：PageRank（簡化）算法（1）取萬維網(wǎng)鏈接結(jié)構(gòu)圖G，G的規(guī)模為N，則G中包含N個結(jié)點(diǎn)。對于G中的每一個結(jié)點(diǎn)n，設(shè)PR(n)是其PageRank值，而向量為G對應(yīng)的PageRank結(jié)果向量。（
5、2）設(shè)定，即：對G中每一個節(jié)點(diǎn)n，設(shè)定其初始值PR(0)(n)均為。（3）Fork=1,2,3,…,TN對G中每一個節(jié)點(diǎn)n，其中，α為預(yù)先設(shè)定的參數(shù)，Outdegree(Pi)為頁面Pi的出度值。（4）當(dāng)結(jié)果向量收斂時，返回（3）繼續(xù)循環(huán)；當(dāng)收斂時，算法結(jié)束，輸出所計算出的G中每一個節(jié)點(diǎn)n的PR(n)的結(jié)果。上述算法要求G中不存在沒有超鏈接的“死胡同”網(wǎng)頁，為解決這一問題，可以采用如下算法：PageRank（標(biāo)準(zhǔn)）算法（1）取萬維網(wǎng)鏈接結(jié)構(gòu)圖G，G的規(guī)模為N，則G中包含N個結(jié)點(diǎn)。對于G中的每一個結(jié)點(diǎn)n，設(shè)PR(n)是其PageRank值，而向量為G對應(yīng)的Pa
6、geRank結(jié)果向量。......（2）設(shè)定，即：對G中每一個節(jié)點(diǎn)n，設(shè)定其初始值PR(0)(n)均為，同時設(shè)定臨時變量。（3）Fork=1,2,3,…,M①對G中每一個節(jié)點(diǎn)n，若Outdegree(n)>0，則有：，，若Outdegree(n)=0，則有：，其中，α為預(yù)先設(shè)定的參數(shù)，Outdegree(Pi)為頁面Pi的出度值。②將臨時變量賦值給：③臨時變量賦初值：（4）當(dāng)結(jié)果向量收斂時，返回（3）繼續(xù)循環(huán)；當(dāng)收斂時，算法結(jié)束，輸出所計算出的G中每一個節(jié)點(diǎn)n的PR(n)的結(jié)果。可以看出，與簡化算法相比，標(biāo)準(zhǔn)算法考慮到?jīng)]有超鏈接網(wǎng)頁的情況，對這部分網(wǎng)頁，“隨
7、機(jī)游走”的瀏覽方式則只能點(diǎn)擊“隨便逛逛”功能進(jìn)行跳轉(zhuǎn)，而任何G中的網(wǎng)頁都可能成為跳轉(zhuǎn)目標(biāo)。因此步驟（1）中需要在G的網(wǎng)頁集合中均分這部分“死胡同”網(wǎng)頁的PageRank值。事實上，這相當(dāng)于先在“死胡同”網(wǎng)頁和G中的所有網(wǎng)頁兩兩之間添加了一條虛擬的超鏈接，之后，再在這個經(jīng)過修改的鏈接關(guān)系圖上進(jìn)行簡化算法。三、所用儀器、材料（設(shè)備名稱、型號、規(guī)格等）硬件：PC機(jī)一臺操作系統(tǒng)：Windows7編程語言：JavaIDE：eclipse3.5.2四、實驗方法、步驟......編程實現(xiàn)PageRank算法，能夠?qū)y試數(shù)據(jù)計算PageRank算法，并輸出每次迭代的計算結(jié)果
8、。要求給出詳細(xì)的算法設(shè)計過程五、實驗過程原始記錄(數(shù)
