PageRank對網(wǎng)頁排名的算法，曾是Google發(fā)家致富的法寶。以前雖然有實驗過，但理解還是不透徹，這幾天又看了一下，這里總結(jié)一下PageRank算法的基本原理。 一、什么是pagerank
PageRank的Page可是認(rèn)為是網(wǎng)頁，表示網(wǎng)頁排名，也可以認(rèn)為是Larry Page(google 產(chǎn)品經(jīng)理)，因為他是這個算法的發(fā)明者之一，還是google CEO（^_^）。PageRank算法計算每一個網(wǎng)頁的PageRank值，然后根據(jù)這個值的大小對網(wǎng)頁的重要性進行排序。它的思想是模擬一個悠閑的上網(wǎng)者，上網(wǎng)者首先隨機選擇一個網(wǎng)頁打開，然后在這個網(wǎng)頁上呆了幾分鐘后，跳轉(zhuǎn)到該網(wǎng)頁所指向的鏈接，這樣無所事事、漫無目的地在網(wǎng)頁上跳來跳去，PageRank就是估計這個悠閑的上網(wǎng)者分布在各個網(wǎng)頁上的概率。
二、最簡單pagerank模型
互聯(lián)網(wǎng)中的網(wǎng)頁可以看出是一個有向圖，其中網(wǎng)頁是結(jié)點，如果網(wǎng)頁A有鏈接到網(wǎng)頁B，則存在一條有向邊A->B，下面是一個簡單的示例：
這個例子中只有四個網(wǎng)頁，如果當(dāng)前在A網(wǎng)頁，那么悠閑的上網(wǎng)者將會各以1/3的概率跳轉(zhuǎn)到B、C、D，這里的3表示A有3條出鏈，如果一個網(wǎng)頁有k條出鏈，那么跳轉(zhuǎn)任意一個出鏈上的概率是1/k，同理D到B、C的概率各為1/2，而B到C的概率為0。一般用轉(zhuǎn)移矩陣表示上網(wǎng)者的跳轉(zhuǎn)概率，如果用n表示網(wǎng)頁的數(shù)目，則轉(zhuǎn)移矩陣M是一個n*n的方陣；如果網(wǎng)頁j有k個出鏈，那么對每一個出鏈指向的網(wǎng)頁i，有M[i][j]=1/k，而其他網(wǎng)頁的M[i][j]=0；上面示例圖對應(yīng)的轉(zhuǎn)移矩陣如下：
初試時，假設(shè)上網(wǎng)者在每一個網(wǎng)頁的概率都是相等的，即1/n，于是初試的概率分布就是一個所有值都為1/n的n維列向量V0，用V0去右乘轉(zhuǎn)移矩陣M，就得到了第一步之后上網(wǎng)者的概率分布向量MV0,（nXn）*(nX1)依然得到一個nX1的矩陣。下面是V1的計算過程：
注意矩陣M中M[i][j]不為0表示用一個鏈接從j指向i，M的第一行乘以V0，表示累加所有網(wǎng)頁到網(wǎng)頁A的概率即得到9/24。得到了V1后，再用V1去右乘M得到V2，一直下去，最終V會收斂，即Vn=MV(n-1)，上面的圖示例，不斷的迭代，最終V=[3/9,2/9,2/9,2/9]‘：
三、終止點問題
上述上網(wǎng)者的行為是一個馬爾科夫過程的實例，要滿足收斂性，需要具備一個條件：
- 圖是強連通的，即從任意網(wǎng)頁可以到達其他任意網(wǎng)頁：
互聯(lián)網(wǎng)上的網(wǎng)頁不滿足強連通的特性，因為有一些網(wǎng)頁不指向任何網(wǎng)頁，如果按照上面的計算，上網(wǎng)者到達這樣的網(wǎng)頁后便走投無路、四顧茫然，導(dǎo)致前面累計得到的轉(zhuǎn)移概率被清零，這樣下去，最終的得到的概率分布向量所有元素幾乎都為0。假設(shè)我們把上面圖中C到A的鏈接丟掉，C變成了一個終止點，得到下面這個圖：
對應(yīng)的轉(zhuǎn)移矩陣為：
連續(xù)迭代下去，最終所有元素都為0：
四、陷阱問題
另外一個問題就是陷阱問題，即有些網(wǎng)頁不存在指向其他網(wǎng)頁的鏈接，但存在指向自己的鏈接。比如下面這個圖：
上網(wǎng)者跑到C網(wǎng)頁后，就像跳進了陷阱，陷入了漩渦，再也不能從C中出來，將最終導(dǎo)致概率分布值全部轉(zhuǎn)移到C上來，這使得其他網(wǎng)頁的概率分布值為0，從而整個網(wǎng)頁排名就失去了意義。如果按照上面圖對應(yīng)的轉(zhuǎn)移矩陣為：
不斷的迭代下去，就變成了這樣：
五、解決終止點問題和陷阱問題
上面過程，我們忽略了一個問題，那就是上網(wǎng)者是一個悠閑的上網(wǎng)者，而不是一個愚蠢的上網(wǎng)者，我們的上網(wǎng)者是聰明而悠閑，他悠閑，漫無目的，總是隨機的選擇網(wǎng)頁，他聰明，在走到一個終結(jié)網(wǎng)頁或者一個陷阱網(wǎng)頁（比如兩個示例中的C），不會傻傻的干著急，他會在瀏覽器的地址隨機輸入一個地址，當(dāng)然這個地址可能又是原來的網(wǎng)頁，但這里給了他一個逃離的機會，讓他離開這萬丈深淵。模擬聰明而又悠閑的上網(wǎng)者，對算法進行改進，每一步，上網(wǎng)者可能都不想看當(dāng)前網(wǎng)頁了，不看當(dāng)前網(wǎng)頁也就不會點擊上面的連接，而上悄悄地在地址欄輸入另外一個地址，而在地址欄輸入而跳轉(zhuǎn)到各個網(wǎng)頁的概率是1/n。假設(shè)上網(wǎng)者每一步查看當(dāng)前網(wǎng)頁的概率為a，那么他從瀏覽器地址欄跳轉(zhuǎn)的概率為(1-a)，于是原來的迭代公式轉(zhuǎn)化為：
現(xiàn)在我們來計算帶陷阱的網(wǎng)頁圖的概率分布：
重復(fù)迭代下去，得到：
六、用Map-reduce計算Page Rank
上面的演算過程，采用矩陣相乘，不斷迭代，直到迭代前后概率分布向量的值變化不大，一般迭代到30次以上就收斂了。真的的web結(jié)構(gòu)的轉(zhuǎn)移矩陣非常大，目前的網(wǎng)頁數(shù)量已經(jīng)超過100億，轉(zhuǎn)移矩陣是100億*100億的矩陣，直接按矩陣乘法的計算方法不可行，需要借助Map-Reduce的計算方式來解決。實際上，google發(fā)明Map-Reduce最初就是為了分布式計算大規(guī)模網(wǎng)頁的pagerank，Map-Reduce的pagerank有很多實現(xiàn)方式，我這里計算一種簡單的。
考慮轉(zhuǎn)移矩陣是一個很多的稀疏矩陣，我們可以用稀疏矩陣的形式表示，我們把web圖中的每一個網(wǎng)頁及其鏈出的網(wǎng)頁作為一行，這樣第四節(jié)中的web圖結(jié)構(gòu)用如下方式表示：
1 2 3 4 | 1 A B C D
2 B A D
3 C C
4 D B C
|
A有三條出鏈，分布指向A、B、C，實際上，我們爬取的網(wǎng)頁結(jié)構(gòu)數(shù)據(jù)就是這樣的。
1、Map階段
Map操作的每一行，對所有出鏈發(fā)射當(dāng)前網(wǎng)頁概率值的1/k，k是當(dāng)前網(wǎng)頁的出鏈數(shù)，比如對第一行輸出<B，1/3*1/4>,<C，1/3*1/4>,<D，1/3*1/4>;
2、Reduce階段
Reduce操作收集網(wǎng)頁id相同的值，累加并按權(quán)重計算，pj=a*(p1+p2+…Pm)+(1-a)*1/n，其中m是指向網(wǎng)頁j的網(wǎng)頁j數(shù)，n所有網(wǎng)頁數(shù)。
思路就是這么簡單，但是實踐的時候，怎樣在Map階段知道當(dāng)前行網(wǎng)頁的概率值，需要一個單獨的文件專門保存上一輪的概率分布值，先進行一次排序，讓出鏈行與概率值按網(wǎng)頁id出現(xiàn)在同一Mapper里面，整個流程如下：
這樣進行一次迭代相當(dāng)于需要兩次MapReduce，但第一次的MapReduce只是簡單的排序，不需要任何操作，用python調(diào)用Hadoop的Streaming.
SortMappert.py代碼如下:
1 2 3 4 5 | 1 #!/bin/python
2 '''Mapper for sort'''
3 import sys
4 for line in sys.stdin:
5 print line.strip()
|
SortReducer.py也是一樣
1 2 3 4 5 | 1 #!/bin/python
2 '''Reducer for sort'''
3 import sys
4 for line in sys.stdin:
5 print line.strip()
|
PageRankMapper.py代碼:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | 1 ''' mapper of pangerank algorithm'''
2 import sys
3 id1 = id2 = None
4 heros = value = None
5 count1 = count2 = 0
6
7 for line in sys.stdin:
8 data = line.strip().split('\t')
9 if len(data) == 3 and data[1] == 'a':# This is the pangerank value
10 count1 += 1
11 if count1 >= 2:
12 print '%s\t%s' % (id1,0.0)
13
14 id1 = data[0]
15 value = float(data[2])
16 else:#This the link relation
17 id2 = data[0]
18 heros = data[1:]
19 if id1 == id2 and id1:
20 v = value / len(heros)
21 for hero in heros:
22 print '%s\t%s' % (hero,v)
23 print '%s\t%s' % (id1,0.0)
24 id1 = id2 = None
25 count1 = 0
|
PageRankReducer.py代碼:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | 1 ''' reducer of pagerank algorithm'''
2 import sys
3 last = None
4 values = 0.0
5 alpha = 0.8
6 N = 4# Size of the web pages
7 for line in sys.stdin:
8 data = line.strip().split('\t')
9 hero,value = data[0],float(data[1])
10 if data[0] != last:
11 if last:
12 values = alpha * values + (1 - alpha) / N
13 print '%s\ta\t%s' % (last,values)
14 last = data[0]
15 values = value
16 else:
17 values += value #accumulate the page rank value
18 if last:
19 values = alpha * values + (1 - alpha) / N
20 print '%s\ta\t%s' % (last,values)
|
在linux下模仿Map-Reduce的過程：
1 2 3 4 5 6 7 8 9 10 | 1 #!/bin/bash
2 PATH=/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games
3 export PATH
4 max=10
5 for i in `seq 1 $max`
6 do
7 echo "$i"
8 cat links.txt pangerank.value > tmp.txt
9 cat tmp.txt |sort|python PageRankMapper.py |sort|python PageRankReducer.py >pangerank.value
10 done
|
這個代碼不用改動就可以直接在hadoop上跑起來。調(diào)用hadoop命令：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | 1 #!/bin/bash
2
3 #sort
4 mapper=SortMapper.py
5 reducer=SortReducer.py
6 input="yours HDFS dir"/links.txt
7 input="yours HDFS dir"/pagerank.value
8 output="yours HDFS dir"/tmp.txt
9
10 hadoop jar contrib/streaming/hadoop-*streaming*.jar
11 -mapper /home/hduser/mapper.py
12 -reducer /home/hduser/reducer.py
13 -input $input
14 -output $output
15
16
17 #Caculator PageRank
18 mapper=PageRankMapper.py
19 reducer=PageRankReducer.py
20 input="yours HDFS dir"/tmp.txt
21 output="yours HDFS dir"/pagerank.value
22
23 hadoop jar contrib/streaming/hadoop-*streaming*.jar
24 -mapper /home/hduser/mapper.py
25 -reducer /home/hduser/reducer.py
26 -input $input
27 -output $output
|
關(guān)于使用python操作hadoop可以查看參考文獻。python代碼寫得濃濃的C味，望海涵！
第四步中帶環(huán)的陷阱圖，迭代40次，權(quán)值a取0.8，計算結(jié)果如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | 1 A B C D
2 0.15 0.216666666667 0.416666666667 0.216666666667
3 0.136666666666 0.176666666666 0.51 0.176666666666
4 0.120666666666 0.157111111111 0.565111111111 0.157111111111
5 0.112844444444 0.145022222222 0.597111111111 0.145022222222
6 0.108008888889 0.138100740741 0.615789629629 0.138100740741
7 0.105240296296 0.134042666667 0.62667437037 0.134042666667
8 0.103617066667 0.131681145679 0.633020641975 0.131681145679
9 0.102672458272 0.130303676049 0.636720189629 0.130303676049
10 0.10212147042 0.129500792625 0.638876944329 0.129500792625
11 0.10180031705 0.129032709162 0.640134264625 0.129032709162
12 0.101613083665 0.128759834878 0.640867246578 0.128759834878
13 0.101503933951 0.128600756262 0.641294553524 0.128600756262
14 0.101440302505 0.128508018225 0.641543661044 0.128508018225
15 0.10140320729 0.128453954625 0.64168888346 0.128453954625
16 0.10138158185 0.128422437127 0.641773543895 0.128422437127
17 0.101368974851 0.128404063344 0.64182289846 0.128404063344
18 0.101361625338 0.128393351965 0.641851670733 0.128393351965
19 0.101357340786 0.128387107543 0.641868444129 0.128387107543
20 0.101354843017 0.128383467227 0.64187822253 0.128383467227
21 0.101353386891 0.128381345029 0.641883923053 0.128381345029
22 0.101352538012 0.128380107849 0.641887246292 0.128380107849
23 0.10135204314 0.128379386609 0.641889183643 0.128379386609
24 0.101351754644 0.128378966148 0.641890313062 0.128378966148
25 0.101351586459 0.128378721031 0.641890971481 0.128378721031
26 0.101351488412 0.128378578135 0.64189135532 0.128378578135
27 0.101351431254 0.128378494831 0.641891579087 0.128378494831
28 0.101351397932 0.128378446267 0.641891709536 0.128378446267
29 0.101351378507 0.128378417955 0.641891785584 0.128378417955
30 0.101351367182 0.128378401451 0.641891829918 0.128378401451
31 0.10135136058 0.128378391829 0.641891855763 0.128378391829
32 0.101351356732 0.12837838622 0.64189187083 0.12837838622
33 0.101351354488 0.12837838295 0.641891879614 0.12837838295
34 0.10135135318 0.128378381043 0.641891884735 0.128378381043
35 0.101351352417 0.128378379932 0.64189188772 0.128378379932
36 0.101351351973 0.128378379284 0.64189188946 0.128378379284
37 0.101351351714 0.128378378906 0.641891890474 0.128378378906
38 0.101351351562 0.128378378686 0.641891891065 0.128378378686
39 0.101351351474 0.128378378558 0.64189189141 0.128378378558
40 0.101351351423 0.128378378483 0.641891891611 0.128378378483
41 0.101351351393 0.128378378439 0.641891891728 0.128378378439
|
可以看到pagerank值已經(jīng)基本趨于穩(wěn)定，并與第四步的分?jǐn)?shù)表示一致。
PageRank的簡介就介紹到這里了，如果想深入可以參考原論文或者下面的參考文獻
參考文獻
1.《Mining of Massive Datasets》
2.《An introduction to information retrival》
3.使用python操作Hadoop
4.js可視化展示PageRank計算過程(可能需要梯子)，可訪問作者博客.
|
