PageRank算法–从原理到实现 – 刀刀流

本文将引见PageRank算法的有关主题。,详细列举如下:

1。算法源
2。算法规律
三。算法宣布
付出代价计算方法
幂迭代法
固有值法
代数法
5.算法实现
鉴于迭代法的复杂实现
5.2 MapReduce实现
算法的缺陷
7。写完
参考资料


1. 算法源

这理所当然从搜索引擎的开展开端。。最早运用的搜索引擎是 分类学目录[^ref_1] 的方法,即,手工操作分类学网页和有组织的高大多网站。。这么 Yahoo 和海内的 hao123 这执意它被运用的方法。。

后头,越来越多的网页。,手工分类学是不现实的。。搜索引擎在。 课文检索 的使苍老,即,计算用户查询保留字和Web CONE中间的相关性。。这种方法溃了大批的限度局限。,仅有的搜索产生产生断层上等的。。因常常当然啦网页一来一往骨碌某一尖形指示牌。。

因而我们的的指挥将攀登表演场地。。没错,谷歌的两位创始人,事先,斯坦福综合性大学。 (斯坦福综合性大学) 综合性大学) 课题生的阅读 (拉里 页) 布林 (波兹南队员克里维茨 布林) 对网页分类的课题开端。。他们运用学术评价的普通方法对ACA的根本停止了根究。, 那执意看报纸被援用多少次。。从合乎逻辑的推论是角度视域,网页的根本也可以被评价为ACC。。合乎逻辑的推论是PageRank的要点思惟是[^ RefI2]的暴露。,这很复杂:

  • 万一网页被很多的如此等等网页勾住,合乎逻辑的推论是阅读就更要紧了。,即,PageRank值将绝对较高。
  • 万一具有高PageRank值的网页勾住到另一任一某一网页,勾住的网页的PageRank值将相当的加法运算

列举如下图所示(请求图)

请求图


2. 算法规律

PageRank算法[^ref_3]一般而言执意预给每个网页一任一某一PR值(下面用PR值参考书PageRank值),因PR值是物理身分意思上的,网页是AC的概率。,因而普通来说 \frac{1}{N} $,n这是一任一某一网页总额。。到旁边,普通健康状况下,领地网页上公关的付出代价积和为1。。万一产生断层1,那产生断层不值得讨论的的。,上个,不相等地网页中间的pr值中间的相干是STI。,它不克不及立即的思索概率。。

预使竖起PR值后,,迭代经过下面的算法,直到手脚能够到的范围排除散布。。

因特网上的很多的网页可涉及有向图。。下面是一任一某一复杂的诉讼[^ RefMy4]:

sample1

此刻,A的pr值可以表现为:

\[ PR(a) = PR(b) + PR(C) \]

除非C不计,,B和D有不仅有的每一链。,合乎逻辑的推论是,前述的语句是不正确的。。承担用户如今阅读B网页。,合乎逻辑的推论是,下一步他翻开对折的或D页是统计数字上完全同样的的概率。。合乎逻辑的推论是,A公关的付出代价理所当然表现为:

\[ PR(a) = \frac{PR(b)}{2} + \frac{PR(C)}{1} \]

有些网页在互联网网上不在。,列举如下图:

sample1

图正中鹄的C页缺少外链。,无PR值对如此等等网页的奉献,我们的用不着合乎逻辑的推论是自私自利的网页。 Markov 链收敛,合乎逻辑的推论是,它为领地网页使被安排好了一任一某一链,包罗它自己。,图正中鹄的a的pr值可以表现为:

\[ PR(a) = \frac{PR(b)}{2} + \frac{PR(C)}{4} \]

仅有的让我们的思索替代的健康状况。:互联网网上的网页孤独地它自己的监禁。,或几页的链体现一任一某一圆形的。。在陆续迭代程序中,这对折的或更多页的pr值只会加法运算。,显然是不合理的的。。譬如,下面的图片正中鹄的C页仅有的J的网页。:

sample3

为了处理合乎逻辑的推论是问题。我们的设想一任一某一恣意的网阅读器。,当他抵达C网页时,显然产生断层愚笨地被C的幼稚的人困住了。。我们的承担他有必然的可能性,他将进入网地址。,跳到每个网页的概率是相等地的。。去图正中鹄的a的pr值可以表现为:

\[ PR(a) = \alpha(\frac{PR(b)}{2}) + \frac{(1 – \alpha)}{4}\]

在普通健康状况下,网页的pr值按列举如下计算:

\[ PR(p_{i}) = \alpha \sum_{p_{j} \in M_{p_{i}}} \frac{PR(p_{j})}{L(p_{j})} + \frac{(1 – \alpha)}{N} \]

就中\(M_{p_{i}}\)是领地对\(p_{i}\)带链的网页,\(L(p_{j})\)这是一任一某一网页\(p_{j}\)输出链数,\(N\)这是一任一某一网页总额,\(\alpha\)普通采用。
土地下面的语句,我们的可以计算每个网页公关的付出代价。,当迭代波动更时,这执意终极产生。。详细来说,以任何方式波动。,我们的在下面的PR付出代价计算方法切开改装解说。


3. 算法宣布

  • $ \lim_{n 姓 \infty}P_{n} 它在吗?
  • 万一在限度,其中的哪一个与\(P_0\)选择无干吗?

PageRank算法的效力包罗超过两点[^。为便宜起见,让我们的先时装领域PR值的计算方法。。

言传身教。

sample3

我们的可以用矩阵来表现链和柴中间的相干。,\(S_{ij} = 0\)表现\(j\)缺少阅读。\(i\)网退出链:

\[ S =
\left(
\begin{array}{cccc}
0 & 1/2 & 0 & 0 \\
1/3 & 0 & 0 & 1/2 \\
1/3 & 0 & 1 & 1/2 \\
1/3 & 1/2 & 0 & 0 \\
\end{array}
右)
\]

\(e\)说起领地立法机构 1 的列矢径,因此构成释义矩阵。:

\[ A = \alpha S + \frac{(1 – \alpha)}{N}ee^T \]

PR值按列举如下计算,就中\(P_{n}\)由N个迭代正中鹄的每个阅读公关的付出代价结合的列矢径。:

\[ P_{n+1} = A P_{n} \]

合乎逻辑的推论是,PR值的计算变成一任一某一程序。 Markov 程序,因此将PageRank算法的宣布转变为宣布。 Markov 程序收敛性宣布:万一合乎逻辑的推论是 Markov 程序收敛,这么$ \lim_{n 姓 \infty}P_{n} (在),与P00$的选择与它无干。。

万一A Markov 程序收敛,因此它的资格转变矩阵(A)必要使确信[^ Ref6]:

  1. A是一任一某一随机矩阵。。
  2. A是不行约的。。
  3. A抵抗周期性的。。

先看第在某种程度上。,随机矩阵也称为概率矩阵。 Markov 矩阵,使确信拥护者合格证书:

\[
A.中矩阵I的线J元素A{{ij},则
\forall i = 1 \dots n, j = 1 \dots n, a_{ij} \geq 0, 且
\forall i = 1 \dots n, \sum_{j = 1}^n a_{ij} = 1
\]

显然,我们的A矩阵的领地元素都大于或能与之比拟的东西0。,每个列有1个元素。。

次要的点,不行约矩阵:方针A是不行约的。当且仅当与A对应的有向图是强联通的。有向图\(G = (V,E)\)它是强连通的,且仅说起每对结节。\(u,v \in V\),在从\(u\)\(v\)的方法和资源。因我们的在先于设定用户在阅读阅读的时分有决定概率经过输出网址的方法拜访一任一某一随机网页,合乎逻辑的推论是,A矩阵也使确信不行约的需要。。

第三点,需要A抵抗周期性的。。同样的人周期性,思索在马尔柯夫链的周期性。。万一A是周期性的。,因此,马尔柯夫链的资格是周期性的。。因A是素矩阵(素矩阵指使自花授精的某个次幂为正矩阵的矩阵),因而A抵抗周期性的。。

这么,宣布了PageRank算法的效力。。


4. PR付出代价计算方法

幂迭代法

率先,为每个阅读分派一任一某一随机PR值。,因此经过 P_{n+1} = A P_{n} 迭代迭代PR值。当使确信以下可能性时,迭代完毕。,获取领地阅读公关的付出代价:

\[ |P_{n+1} – P_{n}| < \epsilon \]

固有值法

当前述的马尔柯夫链收敛时,,必有:

\[
P = A P 姓 P是对应于矩阵1的固有值的特征矢径。 \\
(随机矩阵只得具有固有值1)。,本征矢径的领地体重均为正或负。
\]

代数法

类似的,当前述的马尔柯夫链收敛时,,必有:

\[
P = A P \\
姓 P = \lgroup \alpha S + \frac{(1 – \alpha)}{N}ee^T \rgroup P \\
因 e说起领地立法机构 1 的列矢径,P的领地身分积和为1。 \\
姓 P = \alpha SP + \frac{(1 – \alpha)}{N}e \\
姓 (ee^T – \alpha S)P = \frac{(1 – \alpha)}{N}e \\
姓 P = (ee^T – \alpha S)^{-1} \frac{(1 – \alpha)}{N}e \\
\]


5. 算法实现

鉴于迭代法的复杂实现

用python实现[^ref_7],你必要先使竖起Python图形要点。。

# -*- coding: utf-8 -*-

from pygraph.classes.digraph import digraph


class PRIterator:
    __doc__ = 计算图片中公关的付出代价。

    def __init__(self, DG)
         =   # 使沮丧系数,即α
         = 100  # 最大迭代次数
        self.min_delta = 0001  # 决定迭代其中的哪一个完毕。,即ϵ
         = dg

    def page_rank(self):
        #  率先,在图中缺少链的结节被时装领域为具有链F。
        for node in .nodes():
            if LeN((结节)) == 0:
                for node2 in .nodes():
                    (, (结节), node2))

        nodes = .nodes()
        graph_size = len(结节)s)

        if graph_size == 0:
            return {}
        page_rank = (结节)s, 1.0 / graph_size)  # 将初始PR值分派给每个结节。
        damping_value = (1.0 - ) / graph_size  # 语句的(1*a)/n切开

        flag = False
        for i in range():
            change = 0
            for node in nodes:
                rank = 0
                for incident_page in .incidents(结节)):  # 遍历领地输出阅读
                    rank +=  * (page_rank[incident_page] / len((incident_page)))
                rank += damping_value
                change += ABS(PaGeQueRange[结节] - 年级)  # 绝对的
                page_rank[结节] = rank

            誊写版印刷机(合乎逻辑的推论是 is NO.%s iteration" % (i + 1))
            print(page_年级)

            if change < self.min_delta:
                flag = True
                break
        if flag:
            print("finished in %s iterations!" % node)
        else:
            print("finished out of 100 iterations!")
        return page_rank


if __name__ == ''__main__'':
    dg = digraph()

    [(a)], "B", "C", "D", "E"])

    ((a), "B"))
    ((a), "C"))
    ((a), "D"))
    (("B", "D"))
    (("C", "E"))
    (("D", "E"))
    (("B", "E"))
    (("E", A

    pr = PRIterator(dg)
    page_ranks = ()

    誊写版印刷机( final page rank is\n", page_ranks)

运行产生:

finished in 36 iterations!
The final page rank is
{A , ''C'': , ''B'': , ''E'': , ''D'': }

程序中给出的网页中间的相干从:

begin

迭代的完毕列举如下:

end

5.2 MapReduce实现

作为Hadoop(散布式系统平台)的要点模块之一,MapReduce是一种高效的散布式计算框架。。让我们的从MapReduce规律的复杂引见开端。。

同样的人的MapReduce,有两个操作。:Mapping和Reducing[^ref_8]。

  • 映射(映射):对集合正中鹄的每个目标应用完全同样的的操作。。
  • 简化(约简) ):遍历返回的映射中返回的元素以返回一任一某一综合。

举个典型诉讼。:如今有3个课文文件。,有必要计算领地有吸引力的单词的词频。。传统的想法是让一任一某一人顺序阅读这3个文件,每遇到一任一某一字,看看你以前其中的哪一个见过面。。词频加上遇到的一任一某一。:(词语),N + 1),否则,新单词将被记录下来。,词频一:(词语),1)。

MapReduce方法是:把这3份文件分成3个人。,每个人都阅读文档。。每当我遇到一任一某一字,把合乎逻辑的推论是单词记下来。:(词语),1)(无论你以前其中的哪一个遇到过合乎逻辑的推论是词),即,可能有多个完全同样的的词。。之后,将发送另一任一某一人来添加完全同样的的单词。,终极的产生可以得到。。

词频统计的详细实现可见点我。

下面是运用MapReduce实现PageRank的详细代码[^ref_9]。率先是通用地图和还原模块。。万一你觉得很难理解,可以先看看词频统计的实现代码,下面的模块也被运用。:

class MapReduce:
    __doc__ = ''提供MaPixRead函数''。

    @staticmethod
    def map_reduce(i, mapper, 减速机)
        """
        map_reduce方法
        :param i: 必要一任一某一MapReduce的集合。
        :param mapper: 自构成释义映射器方法
        :param reducer: 定制减速器法
        :return: 以定制减速器法的返回值为元素的一任一某一列表
        """
        intermediate = []  # 存储领地(中间的)密钥, intermediate_付出代价)
        for (钥匙, 付出代价) in i.items():
            (mapper(钥匙, 付出代价))

        # 排序返回一任一某一有序的列表。,因列表正中鹄的元素是元组。,密钥是土地元组正中鹄的前几个元素来设置的。
        # GROPBY提取迭代器正中鹄的相邻重复元素,并将T,密钥土地前几项设置重复元素的选择。
        # 下面的循环中groupby返回的key是intermediate_key,和组是列表。,它是1个或更多。
        # 有着完全同样的intermediate_key的(intermediate_key, intermediate_付出代价)
        groups = {}
        for key, group in itertools.groupby(sorted(intermediate, key=lambda im: IM〔0〕, key=lambda x: x[0]):
            组[键] = [y for x, y in 组
        # 群组是一本字典。,它的关键是下面提到的中间体。,value为领地对应intermediate_key的intermediate_value
        # 立法机构列表
        return [reducer(intermediate_key, groups[intermediate_key]) for intermediate_key in 组

接下来是PR值的计算的类。,就中实现了用于PR值的计算的mapper和reducer:

class PRMapReduce:
    __doc__ = PR值的计算

    def __init__(self, DG)
         =   # 使沮丧系数,即α
         = 100  # 最大迭代次数
        self.min_delta = 0001  # 决定迭代其中的哪一个完毕。,即ϵ
         = len(())  # 网页总额

        # 图代表整个网图。。是字典类型。
        # graph[i][0] 存储阅读公关的付出代价
        # graph[i][1] 存放第i网退出链大批
        # graph[i][2] 存放第i网退出链网页,这是一张单子。
         = {}
        for node in ():
            [结节] = [1.0 / , LeN((结节)), (结节))]

    def ip_mapper(self, input_key, input_付出代价):
        """
        查看网页其中的哪一个有链。,返回值正中鹄的 1 缺少物理身分意思。,仅有的为了在
        MpjRoad正中鹄的组字典的密钥仅为1。,相当的的值都是挂起的网页。
        公关的付出代价
        :param input_key: 网页名,如 A
        :param input_value: [input_key]
        :return: 万一缺少退出链,挂网页,因此回到[(1),合乎逻辑的推论是网页公关的付出代价)];否则,它将返回。
        """
        if input_value[1] == 0:
            return [(1, input_值〔0〕]
        else:
            return []

    def ip_reducer(self, input_key, input_value_list):
        """
        计算领地悬挂网页公关的付出代价积和
        :param input_key: 土地IPML映射器的返回值,合乎逻辑的推论是输出键是:1
        :param input_value_list: 领地悬挂网页公关的付出代价
        :return: 领地悬挂网页公关的付出代价积和
        """
        return sum(input_value_list)

    def pr_mapper(self, input_key, input_付出代价):
        """
        映射法
        :param input_key: 网页名,如 A
        :param input_value: [input_key],即,合乎逻辑的推论是网页上的相关信息。
        :return: [网页名称], ), (外链第1页), 出链网页1分得公关的付出代价), (外链第2页), 出链网页2分得公关的付出代价)...]
        """
        return [(input_key, )] + [(out_link, input_value[0] / input_value[1]) for out_link in input_value[2]]

    def pr_reducer_inter(self, intermediate_key, intermediate_value_list, DP)
        """
        还原法
        :param intermediate_key: 网页名,如 A
        :param intermediate_value_list: A领地分得公关的付出代价的列表:[,分得公关的付出代价,分得公关的付出代价...]
        :param dp: 领地悬挂网页公关的付出代价积和
        :return: (页名),计算所得公关的付出代价)
        """
        return (intermediate_key,
                 * sum(intermediate_value_list) +
                 * dp /  +
                (1.0 - ) / )

    def page_rank(self):
        """
        PR值的计算,每次迭代都必要两次调用MapReduce。。一次是计算悬挂网页PR值积和,一次
        是计算领地网页公关的付出代价
        :return: ,就中公关的付出代价已经计算好
        """
        iteration = 1  # 迭代次数
        change = 1  # 记录每轮迭代后公关的付出代价变化健康状况,初始值为1,确保至少一次迭代。
        while change > self.min_delta:
            誊写版印刷机(迭代 " + STR(迭代)

            # 因可能有网页挂起。,这执意为什么我们的有以下的DangLink列表。
            # dangling_list存放的是[领地悬挂网页公关的付出代价积和]
            # dp表现领地悬挂网页公关的付出代价积和
            dangling_list = (, self.ip_mapper, self.ip_reducer)
            if dangling_list:
                dp = dangling_list[0]
            else:
                dp = 0

            # 因所需的减速器只能有两个参数。,而我们的
            # 必要传3个参数(多了一任一某一领地悬挂网页公关的付出代价积和,即,DP),因而用它
            # 下面的lambda表达式用于实现该目标。
            # NexPr是一任一某一列表。,元素为:(页名),计算所得公关的付出代价)
            new_pr = (, self.pr_mapper, lambda x, y: self.pr_reducer_inter(x, y, DP)

            # 计算合乎逻辑的推论是车轮的PR值的变化。
            change = 求和([ABS(NexPr[i])〔1〕 - [new_pr[i][0]][0]) for i in range()])
            誊写版印刷机(更改 " + STR(变化)

            # 更新公关付出代价
            for i in range():
                [new_pr[i][0]][0] = new_pr[i][1]
            iteration += 1
        return 

上个一切开是测试切开。,我用Python的有向图来创建有向图。,并调用下面的方法来PR值的计算:

if __name__ == ''__main__'':
    dg = digraph()

    [(a)], "B", "C", "D", "E"])

    ((a), "B"))
    ((a), "C"))
    ((a), "D"))
    (("B", "D"))
    (("C", "E"))
    (("D", "E"))
    (("B", "E"))
    (("E", A

    pr = PRMapReduce(dg)
    page_ranks = ()

    誊写版印刷机( final page rank 是
    for key, value in page_ranks.items():
        print(钥匙 + " : ", 值〔0〕

附加操作产生:

Iteration: 44
Change: 1.275194338951069e-05
Iteration: 45
Change: 1.0046004543212694e-05
Iteration: 46
Change: 7.15337406470562e-06
The final page rank is
E :  0.3133376132128915
C :  0.11396289866948645
B :  0.11396289866948645
A :  0.2963400114149353
D :  0.1623965780332006

超过便是PageRank的MapReduce实现。代码正中鹄的注释更详细。,这理所当然很容易理解。。


这是一任一某一天才算法。,规律复杂,效果却令人惊叹。。然而,在PageRank算法中仍然在某一缺陷。。

第一,站导航链路中间缺少区别。。很多的网站有很多勾住到如此等等网页在他们的主页上。,称为勾住导航勾住。这些勾住与不相等地网站中间的勾住停止比较。,当因此者更能传递传递相干。。

次要的,缺少过滤勾住和功能勾住被过滤。(譬如,共同分享微博)。。这些勾住通常缺少什么实用付出代价。,前者勾住到广告阅读。,后者经常勾住到社交网站的主页。。

第三,对新网页不友好。一任一某一新的网页的总入口链绝对较小。,即使它的内容是高大多的。,它仍然必要很长的时间才能变成一任一某一高PR值阅读。。

针对PageRank算法的不足,有人建议。TrustRank算法。它最初来自斯坦福综合性大学和雅虎的联合课题。,用于检测垃圾网站。TrestRANK算法的工作规律:率先,手工操作识别高大多阅读(即种子页)。,由种子页引导的阅读也可以是一任一某一高大多的阅读。,即,它的Tr值也很高。,勾住从种子阅读越远。,阅读的TR值越低。。种子页可以选择更多勾住的阅读。,可选地,具有较高PR值的网站也是可用的。。

TrestRANK算法给出了每个网页的TR值。。将PR值与TR值相结合。,你可以更正确地判断网页的根本。。


7. 写在上个

谷歌运用PR值对网页停止分类学。,有0~10级,普通4或超过是好主页。。谷歌自己的公关付出代价是9。,百度也是9。,博客园公关的付出代价则为6。

如今,公关付出代价已经不像以前这么要紧了。、广告勾住和功能勾住导致公关本身的付出代价,对新网页不友好。,但PR仍然是交通交易中非常要紧的参考因素。。

上个,有一任一某一图形网站,为PageRank提供动态图表。:点我。

最近,博客花园对标记语法的支持率不高。。万一语句不完整,,你可以在这里看到。。

参考资料

1:这是搜索引擎。:要点技术详解,张俊林

2:PageRank暴露于那一年的论文:The PageRank Citation Ranking: Bringing Order to the Web

3:维基百科PageRank

4:PageRank算法简介及Map-Reduce实现

5:博客谷歌背后的数学,陆长海

6背后的数学:博客PageRank

7:PageRank算法

8:MapReduce规律与设计思惟

9:运用 MapReduce to compute PageRank

发表评论

电子邮件地址不会被公开。 必填项已用*标注