PageRank算法R語(yǔ)言實(shí)現(xiàn)

Google搜索，早已成為我每天必用的工具，無(wú)數(shù)次驚嘆它搜索結(jié)果的準(zhǔn)確性。同時(shí)，我也在做Google的SEO，推廣自己的博客。經(jīng)過(guò)幾個(gè)月嘗試，我的博客PR到2了，外鏈也有幾萬(wàn)個(gè)了。總結(jié)下來(lái)，還是感嘆PageRank的神奇！

改變世界的算法，PageRank！

目錄

PageRank算法介紹

PageRank算法原理

PageRank算法的R語(yǔ)言實(shí)現(xiàn)

1. PageRank算法介紹

PageRank是Google專(zhuān)有的算法，用于衡量特定網(wǎng)頁(yè)相對(duì)于搜索引擎索引中的其他網(wǎng)頁(yè)而言的重要程度。它由Larry Page 和 Sergey Brin在20世紀(jì)90年代后期發(fā)明。PageRank實(shí)現(xiàn)了將鏈接價(jià)值概念作為排名因素。

PageRank讓鏈接來(lái)”投票”

一個(gè)頁(yè)面的“得票數(shù)”由所有鏈向它的頁(yè)面的重要性來(lái)決定，到一個(gè)頁(yè)面的超鏈接相當(dāng)于對(duì)該頁(yè)投一票。一個(gè)頁(yè)面的PageRank是由所有鏈向它的頁(yè)面（“鏈入頁(yè)面”）的重要性經(jīng)過(guò)遞歸算法得到的。一個(gè)有較多鏈入的頁(yè)面會(huì)有較高的等級(jí)，相反如果一個(gè)頁(yè)面沒(méi)有任何鏈入頁(yè)面，那么它沒(méi)有等級(jí)。

簡(jiǎn)單一句話(huà)概括：從許多優(yōu)質(zhì)的網(wǎng)頁(yè)鏈接過(guò)來(lái)的網(wǎng)頁(yè)，必定還是優(yōu)質(zhì)網(wǎng)頁(yè)。

PageRank的計(jì)算基于以下兩個(gè)基本假設(shè)：

數(shù)量假設(shè)：如果一個(gè)頁(yè)面節(jié)點(diǎn)接收到的其他網(wǎng)頁(yè)指向的入鏈數(shù)量越多，那么這個(gè)頁(yè)面越重要

質(zhì)量假設(shè)：指向頁(yè)面A的入鏈質(zhì)量不同，質(zhì)量高的頁(yè)面會(huì)通過(guò)鏈接向其他頁(yè)面?zhèn)鬟f更多的權(quán)重。所以越是質(zhì)量高的頁(yè)面指向頁(yè)面A，則頁(yè)面A越重要。

要提高PageRank有3個(gè)要點(diǎn)：

反向鏈接數(shù)

反向鏈接是否來(lái)自PageRank較高的頁(yè)面

反向鏈接源頁(yè)面的鏈接數(shù)

2. PageRank算法原理

在初始階段：網(wǎng)頁(yè)通過(guò)鏈接關(guān)系構(gòu)建起有向圖，每個(gè)頁(yè)面設(shè)置相同的PageRank值，通過(guò)若干輪的計(jì)算，會(huì)得到每個(gè)頁(yè)面所獲得的最終PageRank值。隨著每一輪的計(jì)算進(jìn)行，網(wǎng)頁(yè)當(dāng)前的PageRank值會(huì)不斷得到更新。

在一輪更新頁(yè)面PageRank得分的計(jì)算中，每個(gè)頁(yè)面將其當(dāng)前的PageRank值平均分配到本頁(yè)面包含的出鏈上，這樣每個(gè)鏈接即獲得了相應(yīng)的權(quán)值。而每個(gè)頁(yè)面將所有指向本頁(yè)面的入鏈所傳入的權(quán)值求和，即可得到新的PageRank得分。當(dāng)每個(gè)頁(yè)面都獲得了更新后的PageRank值，就完成了一輪PageRank計(jì)算。

1). 算法原理

PageRank算法建立在隨機(jī)沖浪者模型上，其基本思想是：網(wǎng)頁(yè)的重要性排序是由網(wǎng)頁(yè)間的鏈接關(guān)系所決定的，算法是依靠網(wǎng)頁(yè)間的鏈接結(jié)構(gòu)來(lái)評(píng)價(jià)每個(gè)頁(yè)面的等級(jí)和重要性，一個(gè)網(wǎng)頁(yè)的PR值不僅考慮指向它的鏈接網(wǎng)頁(yè)數(shù)，還有指向’指向它的網(wǎng)頁(yè)的其他網(wǎng)頁(yè)本身的重要性。

PageRank具有兩大特性：

PR值的傳遞性：網(wǎng)頁(yè)A指向網(wǎng)頁(yè)B時(shí)，A的PR值也部分傳遞給B

重要性的傳遞性：一個(gè)重要網(wǎng)頁(yè)比一個(gè)不重要網(wǎng)頁(yè)傳遞的權(quán)重要多

2). 計(jì)算公式：

PR(pi): pi頁(yè)面的PageRank值

n: 所有頁(yè)面的數(shù)量

pi: 不同的網(wǎng)頁(yè)p1,p2,p3

M(i): pi鏈入網(wǎng)頁(yè)的集合

L(j): pj鏈出網(wǎng)頁(yè)的數(shù)量

d:阻尼系數(shù), 任意時(shí)刻，用戶(hù)到達(dá)某頁(yè)面后并繼續(xù)向后瀏覽的概率。 (1-d=0.15) :表示用戶(hù)停止點(diǎn)擊，隨機(jī)跳到新URL的概率 取值范圍: 0 < d ≤ 1, Google設(shè)為0.85

3). 構(gòu)造實(shí)例：以4個(gè)頁(yè)面的數(shù)據(jù)為例

圖片說(shuō)明：

ID=1的頁(yè)面鏈向2,3,4頁(yè)面，所以一個(gè)用戶(hù)從ID=1的頁(yè)面跳轉(zhuǎn)到2,3,4的概率各為1/3

ID=2的頁(yè)面鏈向3,4頁(yè)面，所以一個(gè)用戶(hù)從ID=2的頁(yè)面跳轉(zhuǎn)到3,4的概率各為1/2

ID=3的頁(yè)面鏈向4頁(yè)面，所以一個(gè)用戶(hù)從ID=3的頁(yè)面跳轉(zhuǎn)到4的概率各為1

ID=4的頁(yè)面鏈向2頁(yè)面，所以一個(gè)用戶(hù)從ID=4的頁(yè)面跳轉(zhuǎn)到2的概率各為1

構(gòu)造鄰接表：

鏈接源頁(yè)面     鏈接目標(biāo)頁(yè)面
    1             2,3,4
    2             3,4
    3             4
    4             2

構(gòu)造鄰接矩陣(方陣):

列：源頁(yè)面

行：目標(biāo)頁(yè)面

[,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    1    0    0    1
[3,]    1    1    0    0
[4,]    1    1    1    0

轉(zhuǎn)換為概率矩陣(轉(zhuǎn)移矩陣)

[,1] [,2] [,3] [,4]
[1,] 0      0    0    0
[2,] 1/3    0    0    1
[3,] 1/3  1/2    0    0
[4,] 1/3  1/2    1    0

通過(guò)鏈接關(guān)系，我們就構(gòu)造出了“轉(zhuǎn)移矩陣”。

3. R語(yǔ)言單機(jī)算法實(shí)現(xiàn)

創(chuàng)建數(shù)據(jù)文件：page.csv

1,2
1,3
1,4
2,3
2,4
3,4
4,2

分別用下面3種方式實(shí)現(xiàn)PageRank:

未考慮阻尼系統(tǒng)的情況

包括考慮阻尼系統(tǒng)的情況

直接用R的特征值計(jì)算函數(shù)

1). 未考慮阻尼系統(tǒng)的情況

R語(yǔ)言實(shí)現(xiàn)

#構(gòu)建鄰接矩陣
adjacencyMatrix<-function(pages){
  n<-max(apply(pages,2,max))
  A <- matrix(0,n,n)
  for(i in 1:nrow(pages)) A[pages[i,]$dist,pages[i,]$src]<-1
  A
}

#變換概率矩陣
probabilityMatrix<-function(G){
  cs <- colSums(G)
  cs[cs==0] <- 1
  n <- nrow(G)
  A <- matrix(0,nrow(G),ncol(G))
  for (i in 1:n) A[i,] <- A[i,] + G[i,]/cs
  A
}

#遞歸計(jì)算矩陣特征值
eigenMatrix<-function(G,iter=100){
  iter<-10
  n<-nrow(G)
  x <- rep(1,n)
  for (i in 1:iter) x <- G %*% x
  x/sum(x)
}

> pages<-read.table(file="page.csv",header=FALSE,sep=",")
> names(pages)<-c("src","dist");pages
  src dist
1   1    2
2   1    3
3   1    4
4   2    3
5   2    4
6   3    4
7   4    2

> A<-adjacencyMatrix(pages);A
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    1    0    0    1
[3,]    1    1    0    0
[4,]    1    1    1    0

> G<-probabilityMatrix(A);G
          [,1] [,2] [,3] [,4]
[1,] 0.0000000  0.0    0    0
[2,] 0.3333333  0.0    0    1
[3,] 0.3333333  0.5    0    0
[4,] 0.3333333  0.5    1    0

> q<-eigenMatrix(G,100);q
          [,1]
[1,] 0.0000000
[2,] 0.4036458
[3,] 0.1979167
[4,] 0.3984375

結(jié)果解讀：

ID=1的頁(yè)面，PR值是0，因?yàn)闆](méi)有指向ID=1的頁(yè)面

ID=2的頁(yè)面，PR值是0.4，權(quán)重最高，因?yàn)?和4都指向2，4權(quán)重較高，并且4只有一個(gè)鏈接指向到2，權(quán)重傳遞沒(méi)有損失

ID=3的頁(yè)面，PR值是0.19，雖有1和2的指向了3，但是1和2還指向的其他頁(yè)面，權(quán)重被分散了，所以ID=3的頁(yè)面PR并不高

ID=4的頁(yè)面，PR值是0.39，權(quán)重很高，因?yàn)楸?,2,3都指向了

從上面的結(jié)果，我們發(fā)現(xiàn)ID=1的頁(yè)面，PR值是0，那么ID=1的頁(yè)，就不能向其他頁(yè)面輸出權(quán)重了，計(jì)算就會(huì)不合理！所以，增加d阻尼系數(shù)，修正沒(méi)有鏈接指向的頁(yè)面，保證頁(yè)面的最小PR值>0，。數(shù)據(jù)分析師培訓(xùn)

2). 包括考慮阻尼系統(tǒng)的情況

增加函數(shù)：dProbabilityMatrix

#變換概率矩陣,考慮d的情況
dProbabilityMatrix<-function(G,d=0.85){
  cs <- colSums(G)
  cs[cs==0] <- 1
  n <- nrow(G)
  delta <- (1-d)/n
  A <- matrix(delta,nrow(G),ncol(G))
  for (i in 1:n) A[i,] <- A[i,] + d*G[i,]/cs
  A
}

> pages<-read.table(file="page.csv",header=FALSE,sep=",")
> names(pages)<-c("src","dist");pages
  src dist
1   1    2
2   1    3
3   1    4
4   2    3
5   2    4
6   3    4
7   4    2

> A<-adjacencyMatrix(pages);A
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    1    0    0    1
[3,]    1    1    0    0
[4,]    1    1    1    0

> G<-dProbabilityMatrix(A);G
          [,1]   [,2]   [,3]   [,4]
[1,] 0.0375000 0.0375 0.0375 0.0375
[2,] 0.3208333 0.0375 0.0375 0.8875
[3,] 0.3208333 0.4625 0.0375 0.0375
[4,] 0.3208333 0.4625 0.8875 0.0375

> q<-eigenMatrix(G,100);q
          [,1]
[1,] 0.0375000
[2,] 0.3738930
[3,] 0.2063759
[4,] 0.3822311

增加阻尼系數(shù)后，ID=1的頁(yè)面，就有值了PR(1)=(1-d)/n=(1-0.85)/4=0.0375，即無(wú)外鏈頁(yè)面的最小值。

3). 直接用R的特征值計(jì)算函數(shù)

增加函數(shù)：calcEigenMatrix

#直接計(jì)算矩陣特征值
calcEigenMatrix<-function(G){
  x <- Re(eigen(G)$vectors[,1])
  x/sum(x)
}

> pages<-read.table(file="page.csv",header=FALSE,sep=",")
> names(pages)<-c("src","dist");pages
  src dist
1   1    2
2   1    3
3   1    4
4   2    3
5   2    4
6   3    4
7   4    2

> A<-adjacencyMatrix(pages);A
     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    1    0    0    1
[3,]    1    1    0    0
[4,]    1    1    1    0

> G<-dProbabilityMatrix(A);G
          [,1]   [,2]   [,3]   [,4]
[1,] 0.0375000 0.0375 0.0375 0.0375
[2,] 0.3208333 0.0375 0.0375 0.8875
[3,] 0.3208333 0.4625 0.0375 0.0375
[4,] 0.3208333 0.4625 0.8875 0.0375

> q<-calcEigenMatrix(G);q
[1] 0.0375000 0.3732476 0.2067552 0.3824972

直接計(jì)算矩陣特征值，可以有效地減少的循環(huán)的操作，提高程序運(yùn)行效率。

在了解PageRank的原理后，使用R語(yǔ)言構(gòu)建PageRank模型，是非常容易的。實(shí)際應(yīng)用中，我們也愿意用比較簡(jiǎn)單的方式建模，驗(yàn)證后，再用其他語(yǔ)言語(yǔ)言去企業(yè)應(yīng)用！