PageRank對(duì)網(wǎng)頁(yè)排名的算法，曾是Google發(fā)家致富的法寶。以前雖然有實(shí)驗(yàn)過(guò)，但理解還是不透徹，這幾天又看了一下，這里總結(jié)一下PageRank算法的基本原理。 一、什么是pagerank
PageRank的Page可是認(rèn)為是網(wǎng)頁(yè)，表示網(wǎng)頁(yè)排名，也可以認(rèn)為是Larry Page(google 產(chǎn)品經(jīng)理)，因?yàn)樗沁@個(gè)算法的發(fā)明者之一，還是google CEO（^_^）。PageRank算法計(jì)算每一個(gè)網(wǎng)頁(yè)的PageRank值，然后根據(jù)這個(gè)值的大小對(duì)網(wǎng)頁(yè)的重要性進(jìn)行排序。它的思想是模擬一個(gè)悠閑的上網(wǎng)者，上網(wǎng)者首先隨機(jī)選擇一個(gè)網(wǎng)頁(yè)打開(kāi)，然后在這個(gè)網(wǎng)頁(yè)上呆了幾分鐘后，跳轉(zhuǎn)到該網(wǎng)頁(yè)所指向的鏈接，這樣無(wú)所事事、漫無(wú)目的地在網(wǎng)頁(yè)上跳來(lái)跳去，PageRank就是估計(jì)這個(gè)悠閑的上網(wǎng)者分布在各個(gè)網(wǎng)頁(yè)上的概率。
二、最簡(jiǎn)單pagerank模型
互聯(lián)網(wǎng)中的網(wǎng)頁(yè)可以看出是一個(gè)有向圖，其中網(wǎng)頁(yè)是結(jié)點(diǎn)，如果網(wǎng)頁(yè)A有鏈接到網(wǎng)頁(yè)B，則存在一條有向邊A->B，下面是一個(gè)簡(jiǎn)單的示例：
這個(gè)例子中只有四個(gè)網(wǎng)頁(yè)，如果當(dāng)前在A網(wǎng)頁(yè)，那么悠閑的上網(wǎng)者將會(huì)各以1/3的概率跳轉(zhuǎn)到B、C、D，這里的3表示A有3條出鏈，如果一個(gè)網(wǎng)頁(yè)有k條出鏈，那么跳轉(zhuǎn)任意一個(gè)出鏈上的概率是1/k，同理D到B、C的概率各為1/2，而B(niǎo)到C的概率為0。一般用轉(zhuǎn)移矩陣表示上網(wǎng)者的跳轉(zhuǎn)概率，如果用n表示網(wǎng)頁(yè)的數(shù)目，則轉(zhuǎn)移矩陣M是一個(gè)n*n的方陣；如果網(wǎng)頁(yè)j有k個(gè)出鏈，那么對(duì)每一個(gè)出鏈指向的網(wǎng)頁(yè)i，有M[i][j]=1/k，而其他網(wǎng)頁(yè)的M[i][j]=0；上面示例圖對(duì)應(yīng)的轉(zhuǎn)移矩陣如下：
初試時(shí)，假設(shè)上網(wǎng)者在每一個(gè)網(wǎng)頁(yè)的概率都是相等的，即1/n，于是初試的概率分布就是一個(gè)所有值都為1/n的n維列向量V0，用V0去右乘轉(zhuǎn)移矩陣M，就得到了第一步之后上網(wǎng)者的概率分布向量MV0,（nXn）*(nX1)依然得到一個(gè)nX1的矩陣。下面是V1的計(jì)算過(guò)程：
注意矩陣M中M[i][j]不為0表示用一個(gè)鏈接從j指向i，M的第一行乘以V0，表示累加所有網(wǎng)頁(yè)到網(wǎng)頁(yè)A的概率即得到9/24。得到了V1后，再用V1去右乘M得到V2，一直下去，最終V會(huì)收斂，即Vn=MV(n-1)，上面的圖示例，不斷的迭代，最終V=[3/9,2/9,2/9,2/9]‘：
三、終止點(diǎn)問(wèn)題
上述上網(wǎng)者的行為是一個(gè)馬爾科夫過(guò)程的實(shí)例，要滿足收斂性，需要具備一個(gè)條件：
- 圖是強(qiáng)連通的，即從任意網(wǎng)頁(yè)可以到達(dá)其他任意網(wǎng)頁(yè)：
互聯(lián)網(wǎng)上的網(wǎng)頁(yè)不滿足強(qiáng)連通的特性，因?yàn)橛幸恍┚W(wǎng)頁(yè)不指向任何網(wǎng)頁(yè)，如果按照上面的計(jì)算，上網(wǎng)者到達(dá)這樣的網(wǎng)頁(yè)后便走投無(wú)路、四顧茫然，導(dǎo)致前面累計(jì)得到的轉(zhuǎn)移概率被清零，這樣下去，最終的得到的概率分布向量所有元素幾乎都為0。假設(shè)我們把上面圖中C到A的鏈接丟掉，C變成了一個(gè)終止點(diǎn)，得到下面這個(gè)圖：
對(duì)應(yīng)的轉(zhuǎn)移矩陣為：
連續(xù)迭代下去，最終所有元素都為0：
四、陷阱問(wèn)題
另外一個(gè)問(wèn)題就是陷阱問(wèn)題，即有些網(wǎng)頁(yè)不存在指向其他網(wǎng)頁(yè)的鏈接，但存在指向自己的鏈接。比如下面這個(gè)圖：
上網(wǎng)者跑到C網(wǎng)頁(yè)后，就像跳進(jìn)了陷阱，陷入了漩渦，再也不能從C中出來(lái)，將最終導(dǎo)致概率分布值全部轉(zhuǎn)移到C上來(lái)，這使得其他網(wǎng)頁(yè)的概率分布值為0，從而整個(gè)網(wǎng)頁(yè)排名就失去了意義。如果按照上面圖對(duì)應(yīng)的轉(zhuǎn)移矩陣為：
不斷的迭代下去，就變成了這樣：
五、解決終止點(diǎn)問(wèn)題和陷阱問(wèn)題
上面過(guò)程，我們忽略了一個(gè)問(wèn)題，那就是上網(wǎng)者是一個(gè)悠閑的上網(wǎng)者，而不是一個(gè)愚蠢的上網(wǎng)者，我們的上網(wǎng)者是聰明而悠閑，他悠閑，漫無(wú)目的，總是隨機(jī)的選擇網(wǎng)頁(yè)，他聰明，在走到一個(gè)終結(jié)網(wǎng)頁(yè)或者一個(gè)陷阱網(wǎng)頁(yè)（比如兩個(gè)示例中的C），不會(huì)傻傻的干著急，他會(huì)在瀏覽器的地址隨機(jī)輸入一個(gè)地址，當(dāng)然這個(gè)地址可能又是原來(lái)的網(wǎng)頁(yè)，但這里給了他一個(gè)逃離的機(jī)會(huì)，讓他離開(kāi)這萬(wàn)丈深淵。模擬聰明而又悠閑的上網(wǎng)者，對(duì)算法進(jìn)行改進(jìn)，每一步，上網(wǎng)者可能都不想看當(dāng)前網(wǎng)頁(yè)了，不看當(dāng)前網(wǎng)頁(yè)也就不會(huì)點(diǎn)擊上面的連接，而上悄悄地在地址欄輸入另外一個(gè)地址，而在地址欄輸入而跳轉(zhuǎn)到各個(gè)網(wǎng)頁(yè)的概率是1/n。假設(shè)上網(wǎng)者每一步查看當(dāng)前網(wǎng)頁(yè)的概率為a，那么他從瀏覽器地址欄跳轉(zhuǎn)的概率為(1-a)，于是原來(lái)的迭代公式轉(zhuǎn)化為：
現(xiàn)在我們來(lái)計(jì)算帶陷阱的網(wǎng)頁(yè)圖的概率分布：
重復(fù)迭代下去，得到：
六、用Map-reduce計(jì)算Page Rank
上面的演算過(guò)程，采用矩陣相乘，不斷迭代，直到迭代前后概率分布向量的值變化不大，一般迭代到30次以上就收斂了。真的的web結(jié)構(gòu)的轉(zhuǎn)移矩陣非常大，目前的網(wǎng)頁(yè)數(shù)量已經(jīng)超過(guò)100億，轉(zhuǎn)移矩陣是100億*100億的矩陣，直接按矩陣乘法的計(jì)算方法不可行，需要借助Map-Reduce的計(jì)算方式來(lái)解決。實(shí)際上，google發(fā)明Map-Reduce最初就是為了分布式計(jì)算大規(guī)模網(wǎng)頁(yè)的pagerank，Map-Reduce的pagerank有很多實(shí)現(xiàn)方式，我這里計(jì)算一種簡(jiǎn)單的。
考慮轉(zhuǎn)移矩陣是一個(gè)很多的稀疏矩陣，我們可以用稀疏矩陣的形式表示，我們把web圖中的每一個(gè)網(wǎng)頁(yè)及其鏈出的網(wǎng)頁(yè)作為一行，這樣第四節(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，實(shí)際上，我們爬取的網(wǎng)頁(yè)結(jié)構(gòu)數(shù)據(jù)就是這樣的。
1、Map階段
Map操作的每一行，對(duì)所有出鏈發(fā)射當(dāng)前網(wǎng)頁(yè)概率值的1/k，k是當(dāng)前網(wǎng)頁(yè)的出鏈數(shù)，比如對(duì)第一行輸出<B，1/3*1/4>,<C，1/3*1/4>,<D，1/3*1/4>;
2、Reduce階段
Reduce操作收集網(wǎng)頁(yè)id相同的值，累加并按權(quán)重計(jì)算，pj=a*(p1+p2+…Pm)+(1-a)*1/n，其中m是指向網(wǎng)頁(yè)j的網(wǎng)頁(yè)j數(shù)，n所有網(wǎng)頁(yè)數(shù)。
思路就是這么簡(jiǎn)單，但是實(shí)踐的時(shí)候，怎樣在Map階段知道當(dāng)前行網(wǎng)頁(yè)的概率值，需要一個(gè)單獨(dú)的文件專(zhuān)門(mén)保存上一輪的概率分布值，先進(jìn)行一次排序，讓出鏈行與概率值按網(wǎng)頁(yè)id出現(xiàn)在同一Mapper里面，整個(gè)流程如下：
這樣進(jìn)行一次迭代相當(dāng)于需要兩次MapReduce，但第一次的MapReduce只是簡(jiǎn)單的排序，不需要任何操作，用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的過(guò)程：
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
|
這個(gè)代碼不用改動(dòng)就可以直接在hadoop上跑起來(lái)。調(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可以查看參考文獻(xiàn)。python代碼寫(xiě)得濃濃的C味，望海涵！
第四步中帶環(huán)的陷阱圖，迭代40次，權(quán)值a取0.8，計(jì)算結(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的簡(jiǎn)介就介紹到這里了，如果想深入可以參考原論文或者下面的參考文獻(xiàn)
參考文獻(xiàn)
1.《Mining of Massive Datasets》
2.《An introduction to information retrival》
3.使用python操作Hadoop
4.js可視化展示PageRank計(jì)算過(guò)程(可能需要梯子)，可訪問(wèn)作者博客.
|
