Pagerank 算法背景、原理、矩陣化計(jì)算
2.3.1Pagerank 算法背景伴隨著全球計(jì)算機(jī)信息技術(shù)的飛速發(fā)展,通過互聯(lián)網(wǎng)搜尋來獲取信息給用 戶的生活帶來了巨大的便利。但是人們怎樣才能在浩瀚的信息海洋中快速搜尋 到有用的信息呢? 1988年,Google公司的創(chuàng)始人、Stanford大學(xué)計(jì)算機(jī)博士 Lawrence Page和Sergey Brin合作共同研究出了 Pagerank算法[85],通過這種算 法能對搜索引擎上的網(wǎng)頁的相關(guān)性和重要性進(jìn)行排名,從而在信息篩選方面給 用戶提供便利。伴隨著Google公司在全世界范圍內(nèi)取得巨大成功,Pagerank算 法也成為全球經(jīng)典的十大數(shù)據(jù)挖掘算法及改變未來的九大算法之一。互聯(lián)網(wǎng)上 龐大的網(wǎng)頁群之間彼此鏈接存在著十分復(fù)雜的相關(guān)性,Pagerank算法正是基于 網(wǎng)頁的鏈接關(guān)系來進(jìn)行網(wǎng)頁的排序,網(wǎng)頁的重要度高低直接決定著其排名的高 低。2.3.2Pagerank 算法原理Pagerank算法是單純依據(jù)頁面之間的復(fù)雜鏈接關(guān)系來進(jìn)行重要度計(jì)算,每 個(gè)頁面的重要度指標(biāo)為其Pagerank值(下文將簡稱PR值),重要度高的頁面將 對應(yīng)較高的PR值,而不太重要的網(wǎng)頁將對應(yīng)較低的PR值。表2.1是部分國內(nèi) 網(wǎng)站的PR值排名。通過表格可知PR值與網(wǎng)頁的反鏈數(shù)有關(guān),所謂反鏈數(shù)即從 其他網(wǎng)頁導(dǎo)入本網(wǎng)頁的鏈接數(shù)量(在有向圖中稱為入度)。一般來講反鏈數(shù)越多 (入度越大),其PR值也越大,但通過表格統(tǒng)計(jì)發(fā)現(xiàn)騰訊網(wǎng)的反鏈數(shù)為1252835 個(gè),在所有網(wǎng)頁中是最多的,但是其PR值僅僅排在第三位,這是因?yàn)轫撁娴?PR值不僅與其反鏈數(shù)有關(guān),還與被鏈接過來網(wǎng)頁的重要度有關(guān)。就像在由多個(gè) 社會個(gè)體組成的社會關(guān)系網(wǎng)絡(luò)中衡量個(gè)體的社會影響力,不僅需要朋友越多, 而且還要朋友質(zhì)量越高才代表個(gè)體的社會地位越高。所以Pagemnk算法的主要原理是:如果頁面A能夠鏈接到頁面B,那么將 認(rèn)為頁面A傳遞給頁面B —個(gè)重要度值(PR值),此值的大小取決于頁面A的 重要度(PR值)以及其出鏈數(shù),并假設(shè)任何頁面的重要度都被平均傳遞到它所 鏈接的頁面。由于網(wǎng)頁之間存在相互鏈接關(guān)系,這個(gè)計(jì)算過程會一直迭代下去, 最后根據(jù)頁面迭代后的平穩(wěn)PR值進(jìn)行排序。基于這一思想,將整個(gè)互聯(lián)網(wǎng)系 統(tǒng)抽象成一個(gè)有向圖G= (V,E),其中將n個(gè)頁面抽象成網(wǎng)絡(luò)圖的節(jié)點(diǎn)V,用有向邊E代表頁面之間的鏈接關(guān)系。若網(wǎng)頁'、%、...Vk是鏈入到網(wǎng)頁A的頁面 節(jié)點(diǎn),那么網(wǎng)頁A的PR值PR(A)計(jì)算公式為:式(2.4)中PR(Vi)和CCV;)為分別為頁面節(jié)點(diǎn)'的PR值和出度;根據(jù) Pagerank算法原理我們可以總結(jié)出:①鏈入到頁面A的網(wǎng)頁數(shù)量k越大,頁面A的PR值就會越大,頁面A的重要度越大;②頁面A的鏈入頁面乂、%、...'的重要度越大,頁面A會受它們的影響變得更重要;③頁面節(jié)點(diǎn)\的出度越大,即CCVD越大,那么頁面節(jié)點(diǎn)A從頁面節(jié)點(diǎn)乂處 分得的PR值越少。公式(2.4)假設(shè)當(dāng)用戶在瀏覽頁面\時(shí),下一個(gè)瀏覽頁面是均勻地選擇下一個(gè)其所指向的頁面。Pagemnk算法可以用隨機(jī)沖浪模式來進(jìn)行刻畫[85],用戶 在互聯(lián)網(wǎng)上隨機(jī)瀏覽網(wǎng)頁,那么網(wǎng)頁的重要度和網(wǎng)頁被訪問的概率成正比,得 到的PR值就是網(wǎng)頁被訪問的概率和網(wǎng)頁排序的依據(jù)。如圖有6個(gè)頁面A、B、 C、D、E、F,假如初始PR值都是1,那么: 圖中頁面節(jié)點(diǎn)重要度排名依次是B、A、C、E、F、D,圖2.7所示的有向 圖是一種非常理想的情況,節(jié)點(diǎn)的重要度只能沿著有向邊進(jìn)行傳遞,是否任何 有向圖經(jīng)過反復(fù)迭代后會達(dá)到平穩(wěn)狀態(tài)呢?顯然不會,由若干個(gè)節(jié)點(diǎn)組成的有 向圖中,如果存在以下3種情況,那么節(jié)點(diǎn)的PR值將不會收斂。①如果存在強(qiáng)連通圖(圖中任意節(jié)點(diǎn)相互可達(dá))只有入鏈沒有出鏈,我們 稱這種情況為等級下沉(Rank sinks)如圖2.9所示,網(wǎng)頁節(jié)點(diǎn)D、E、F組成的強(qiáng)連通圖只有入鏈沒有出鏈,那么來自其他節(jié)點(diǎn)的PR值進(jìn)入強(qiáng)連通圖后會一 直停留,無法進(jìn)入節(jié)點(diǎn)A、B、C。最終的結(jié)果是節(jié)點(diǎn)D、E、F的PR值會一直 增大,直到節(jié)點(diǎn)A、B、C的PR值為0,那么PR值的計(jì)算將失去意義。②如果有向圖中存在節(jié)點(diǎn)F只有鏈入的頁面節(jié)點(diǎn),并且出度為0,如圖2.10 所示,我們稱之為等級泄露(Rank leaks),那么頁面訪問將被困在頁面節(jié)點(diǎn)F, 頁面節(jié)點(diǎn)A、B、C、D、E的PR值終將會變?yōu)?,而節(jié)點(diǎn)F的PR值將達(dá)到最 大,顯然這種情況也無法通過迭代獲得平穩(wěn)的PR值。③有向圖中存在節(jié)點(diǎn)F的出度和入度都為0,我們稱之為孤立節(jié)點(diǎn),如圖 2.11,那么按照公式(2.4),節(jié)點(diǎn)F的PR值將會為0,但是頁面F還有被用戶 訪問的可能,顯然PR值為0不符合實(shí)際。其中PR (A)為網(wǎng)頁A的PR值,n為總頁面的數(shù)量,'、、...'代表能夠鏈入A的頁面,CCX)為頁面節(jié)點(diǎn)\的出度,d為阻尼因子,它是為了避免等級 下沉或登記泄露而設(shè)立的緩沖因子,它代表頁面沿著鏈接方向進(jìn)行傳遞的概率為d,谷歌公司一般取為d=0.85,每條鏈接對應(yīng)傳遞的PR值都是 考慮到孤立節(jié)點(diǎn)的存在,賦予每個(gè)頁面節(jié)點(diǎn)一個(gè)PR初始值^^。2.3.3PR值的矩陣化計(jì)算當(dāng)有向圖中節(jié)點(diǎn)比較少時(shí),可以通過解方程組的方式進(jìn)行節(jié)點(diǎn)的PR值計(jì) 算,但是當(dāng)節(jié)點(diǎn)數(shù)量比較龐大時(shí),這種方法就顯得難以實(shí)現(xiàn)。Pagerank算法假 設(shè)用戶所瀏覽的網(wǎng)頁與過去的瀏覽歷史無關(guān),依賴現(xiàn)有的瀏覽狀態(tài),可以看作是一個(gè)馬爾可夫過程,那么對于n個(gè)頁面和鏈接關(guān)系組成的有向圖G = (V,E),其鄰接矩陣C中元素為1的個(gè)數(shù)為有向圖的鏈接數(shù),將矩陣C每行元素除以此 行元素的總和(行元素全為0除外)會得到一個(gè)矩陣C',矩陣Cf每行元素之 和都為1,那么矩陣C'可以看作是馬爾科夫轉(zhuǎn)移概率矩陣。圖2.7所示的有向 圖的鄰接矩陣及轉(zhuǎn)移概率矩陣分別為:若指定一個(gè)n維向量P,向量的分量分別代表各個(gè)網(wǎng)頁節(jié)點(diǎn)的PR值,Px+1表示第(x+1)次迭代所得到的各個(gè)網(wǎng)頁的PR值所組成的(nxl)矩陣,用概率轉(zhuǎn) 移矩陣計(jì)算PR值的公式為:其中E為(nxl)階矩陣并且元素全為1,設(shè)S為指定的迭代收斂平穩(wěn)閥值, 取各網(wǎng)頁節(jié)點(diǎn)的初始PR值P1,迭代計(jì)算當(dāng)滿足|PX+1-PX|<S時(shí),迭代結(jié)束。 所以Pagemnk算法的實(shí)現(xiàn)過程可以通過如圖2.12所示的算法流程圖來進(jìn)行刻畫。本文采摘自“基于故障率相關(guān)的加工中心的可靠性及風(fēng)險(xiǎn)評估”,因?yàn)榫庉嬂щy導(dǎo)致有些函數(shù)、表格、圖片、內(nèi)容無法顯示,有需要者可以在網(wǎng)絡(luò)中查找相關(guān)文章!本文由海天精工整理發(fā)表文章均來自網(wǎng)絡(luò)僅供學(xué)習(xí)參考,轉(zhuǎn)載請注明!