一篇學會 PageRank 算法與實踐
如果讓我們自己去做搜索的話，我們能夠想到的是文章和搜索詞的相關性，以此來判斷這個文章是否是我們想要的，最開始的搜索有的是這樣做的，還有的是按照網(wǎng)站的種類做個大的索引表，但是可以索引的關鍵字有限。
互聯(lián)網(wǎng)上的網(wǎng)頁估計有千百億規(guī)模了(猜測)，那么顯然不是所有包含搜索關鍵字的網(wǎng)頁都同等重要。有的在標題中包含關鍵字，有的在文檔中包含關鍵字;有的是權(quán)威機構(gòu)網(wǎng)站，有的是個人博客，顯然在給用戶返回網(wǎng)頁的時候，比較重要的網(wǎng)頁的應該排在前面，不重要的網(wǎng)頁信息排在后面。那又來一個問題，如何確定一個網(wǎng)頁的重要性那。
網(wǎng)頁是通過鏈接來組織的，那么我們可以把整個互聯(lián)網(wǎng)看成一張大的圖，每個節(jié)點為一個個網(wǎng)頁，網(wǎng)頁之間的鏈接看成邊。網(wǎng)頁是否重要，要看是否有多個網(wǎng)頁鏈接到它。被越多網(wǎng)頁鏈接的網(wǎng)頁越重要，當然鏈接這個網(wǎng)頁的多個鏈接的重要性又是不相同的。
假設我們搜索得到很多網(wǎng)頁，其中一個網(wǎng)頁Y的排名應該來自所有指向這個網(wǎng)頁X1，X2，X3的權(quán)重之和：
Y網(wǎng)頁的權(quán)重 = X1+X2+X3...+Xn
而X1，X2，...Xn的權(quán)重分別是多少，如何度量，這又需要通過鏈接到它的網(wǎng)頁的權(quán)重來計算，這樣循環(huán)往復，就無解了。據(jù)說是Google的布林破解了這個怪圈，就是開始的時候給每個網(wǎng)頁設置相同的初始值，那么經(jīng)過多輪計算后，這個算法可以保證網(wǎng)頁排名多次之后回收斂到排名的真實值。
我理解下，大概是這樣子的：
第一輪的時候，我們假設所有網(wǎng)頁的權(quán)重都是1，那么A這個網(wǎng)頁的權(quán)重為1+1+1為3， 第二輪計算的時候，與A相連的網(wǎng)頁權(quán)重變成了2，那么最終A這個網(wǎng)頁的權(quán)重就變成了2+2+2=6，這樣多次計算后，被更多權(quán)重高的網(wǎng)頁鏈接的網(wǎng)頁，排名靠前，其他的靠后。
這整個過程有點類似于民主選舉，選舉過程中每個人的票的權(quán)重又是不一樣的，這和現(xiàn)實也很類似。 那么PageRank算法除了計算網(wǎng)頁排名還有什么用那，數(shù)據(jù)實戰(zhàn)45講里面，有個例子比較有意思，計算泄露出來希拉里郵件列表中的人物影響力的情況，通過python的networkx庫可以方便地計算PageRank的值。
下面的網(wǎng)絡圖的：
簡單的計算PageRank的代碼：
import networkx as nx
# 創(chuàng)建有向圖
G = nx.DiGraph()
# 有向圖之間邊的關系
edges = [("B1", "B"), ("B2", "B"), ("C1", "C"), ("C2", "C"), ("D1", "D"), ("D2", "D"), ("D", "A"), ("C", "A"), ("B", "A")]
for edge in edges:
G.add_edge(edge[0], edge[1])
pagerank_list = nx.pagerank(G, alpha=1)
print("pagerank值是：", pagerank_list)
結(jié)果：
整個數(shù)據(jù)集合分為三個文件：Aliases.csv,Emails.csv和Persons.csv,其中Emails文件為郵件內(nèi)容，包括重要的發(fā)送者和接收者信息。 Persons文件統(tǒng)計郵件中所有人的姓名和對應ID。 下面代碼是數(shù)據(jù)實戰(zhàn)中的代碼直接拿過來了，其實過程也是比較簡單，只是這個思路比較重要。
# -*- coding: utf-8 -*-
# 用 PageRank 挖掘希拉里郵件中的重要任務關系
import pandas as pd
import networkx as nx
import numpy as np
from collections import defaultdict
import matplotlib.pyplot as plt
# 數(shù)據(jù)加載
emails = pd.read_csv("./input/Emails.csv")
# 讀取別名文件
file = pd.read_csv("./input/Aliases.csv")
aliases = {}
for index, row in file.iterrows():
aliases[row['Alias']] = row['PersonId']
# 讀取人名文件
file = pd.read_csv("./input/Persons.csv")
persons = {}
for index, row in file.iterrows():
persons[row['Id']] = row['Name']
# 針對別名進行轉(zhuǎn)換
def unify_name(name):
# 姓名統(tǒng)一小寫
name = str(name).lower()
# 去掉, 和 @后面的內(nèi)容
name = name.replace(",","").split("@")[0]
# 別名轉(zhuǎn)換
if name in aliases.keys():
return persons[aliases[name]]
return name
# 畫網(wǎng)絡圖
def show_graph(graph, layout='spring_layout'):
# 使用 Spring Layout 布局，類似中心放射狀
if layout == 'circular_layout':
positions=nx.circular_layout(graph)
else:
positions=nx.spring_layout(graph)
# 設置網(wǎng)絡圖中的節(jié)點大小，大小與 pagerank 值相關，因為 pagerank 值很小所以需要 *20000
nodesize = [x['pagerank']*20000 for v,x in graph.nodes(data=True)]
# 設置網(wǎng)絡圖中的邊長度
edgesize = [np.sqrt(e[2]['weight']) for e in graph.edges(data=True)]
# 繪制節(jié)點
nx.draw_networkx_nodes(graph, positions, node_size=nodesize, alpha=0.4)
# 繪制邊
nx.draw_networkx_edges(graph, positions, edge_size=edgesize, alpha=0.2)
# 繪制節(jié)點的 label
nx.draw_networkx_labels(graph, positions, font_size=10)
# 輸出希拉里郵件中的所有人物關系圖
plt.show()
# 將寄件人和收件人的姓名進行規(guī)范化
emails.MetadataFrom = emails.MetadataFrom.apply(unify_name)
emails.MetadataTo = emails.MetadataTo.apply(unify_name)
# 設置遍的權(quán)重等于發(fā)郵件的次數(shù)
edges_weights_temp = defaultdict(list)
for row in zip(emails.MetadataFrom, emails.MetadataTo, emails.RawText):
temp = (row[0], row[1])
if temp not in edges_weights_temp:
edges_weights_temp[temp] = 1
else:
edges_weights_temp[temp] = edges_weights_temp[temp] + 1
# 轉(zhuǎn)化格式 (from, to), weight => from, to, weight
edges_weights = [(key[0], key[1], val) for key, val in edges_weights_temp.items()]
# 創(chuàng)建一個有向圖
graph = nx.DiGraph()
# 設置有向圖中的路徑及權(quán)重 (from, to, weight)
graph.add_weighted_edges_from(edges_weights)
# 計算每個節(jié)點（人）的 PR 值，并作為節(jié)點的 pagerank 屬性
pagerank = nx.pagerank(graph)
# 將 pagerank 數(shù)值作為節(jié)點的屬性
nx.set_node_attributes(graph, name = 'pagerank', values=pagerank)
# 畫網(wǎng)絡圖
show_graph(graph)
# 將完整的圖譜進行精簡
# 設置 PR 值的閾值，篩選大于閾值的重要核心節(jié)點
pagerank_threshold = 0.005
# 復制一份計算好的網(wǎng)絡圖
small_graph = graph.copy()
# 剪掉 PR 值小于 pagerank_threshold 的節(jié)點
for n, p_rank in graph.nodes(data=True):
if p_rank['pagerank'] < pagerank_threshold:
small_graph.remove_node(n)
# 畫網(wǎng)絡圖,采用circular_layout布局讓篩選出來的點組成一個圓
show_graph(small_graph, 'circular_layout')
