算法推荐

MachineLearning：PageRank算法

1。PageRank优化算法简介

PageRank，的意思是页面排名，也称为页面排名谷歌左排名或页面排名。

在谷歌核心互联网技术检索之前，大部分搜索引擎选择的是基于网页中被搜索词出现频率的排名算法——网页出现频率越高，排名越靠前。这个标准不能说不合理。因为一个客户搜索一个词，一般说明他对这个词很感兴趣。在这种情况下，该短语在网页中出现得越频繁，该网页就越有可能是客户所必需的。

遗憾的是，这种看似有效的方式，实际上在大通汽车身上是行不通的。按照这种方式，所有像祥林嫂这种折腾一些关键词的网页，不管标准有多差，一旦被检索到，都会立刻“金榜提名”。这对于广告和废网页的制作者来说，真是人间天堂。

它是Google创始人SagePage和SvitlanaBrin在1997年搭建最初的检索系统软件原型时明确提出的链接分析优化算法。自从Google在商业服务上取得前所未有的成功后，这种优化算法也成为了其他搜索引擎和学术界非常关注的计算实体模型。目前很多关键环节分析优化算法基本都是由PageRank优化算法衍生而来。

PageRank是Google用来标记网页级别/必要性的一种方式，是Google用来考量一个网站优劣的唯一标准。在整合了所有其他元素，比如标题logo、关键词logo之后，Google根据PageRank对结果进行调整，让这些更有“级别/必要性”的页面在百度搜索中提升其他搜索引擎的排名，从而提升百度搜索的相关性和质量。它的等级是零到零，十级是100分。PR值越高，网页就越热(越关键)。

比如一个网站，PR值为1表示这个网站不时尚，PR值为7到10表示这个网站非常受欢迎(也就是非常重要)。一般PR值为4的，就是非常好的网站。把Google自己网站的PR值设置为10，说明Google的网站很受欢迎，也可以说这个网站很关键。

2。从链接总数到PageRank

在PageRank明确提出之前，已经有学者明确提出用网页的链接总数来进行链接分析和计算。这种链接方法假设一个网页的链接越多，它就越重要。当初很多搜索引擎也是听取链接总数的意见作为链接分析方法，搜索引擎实际效果的提升也有显著的实际效果。PageRank不仅充分考虑了链接总数的危害，还参考了网页的质量因素，两者紧密结合，得到了网页必要评论的更强判据。

对于互联网技术网页A，该网页的PageRank的计算基于以下两个基本假设:

假设:在Web图实体模型中，如果一个页面连接点从其他页面接收的链接越多，这个页面就越关键。

质量的假设:A页的链接质量不同，质量高的页面会根据链接向其他页面发送大量的权重值。所以页面质量越高，A页就越关键。

利用上述两个假设，PageRank优化算法初始赋予每个网页相同的必要性分值，并根据迭代更新和递归计算来更新每个页面连接点的PageRank分值，直至分值稳定。PageRank计算出来的结果是网页的必要评论，与客户的打字和浏览无关，即优化算法与主题风格无关。假设有一个搜索引擎，它的相似度计算功能没有考虑内容的相似元素，完全选择PageRank进行排名，那么这个搜索引擎的主要性能是什么？这个搜索引擎针对随机不同的查看需求，返回的结果都是一样的，就是返回到PageRank值最大的页面。

3。PageRank优化算法的基本原理

PageRank的计算灵活运用了两个假设:总数假设和质量假设。流程如下:

1)原链接中:网页根据连接关联构建网页图，每个页面设置相同的PageRank值。根据多轮计算，会得到最终的每个页面的PageRank值。随着每一轮的计算，当前网页的PageRank会不断升级。

2)一轮升级页面的PageRank分值的计算方法:在一轮升级页面的PageRank分值的计算中，每个页面将其当前的PageRank值平均划分到该页面包含的出站链接中，使每个链接得到一个相对权重值。而且每个页面都会偏向这个页面的入站链接传来的权重值求饶，可以获得新的PageRank分数。当每个页面都获得升级后的PageRank值时，一轮PageRank计算就完成了。

3.2基本思路:

如果网页T中有偏向网页A的链接，说明T的用户认为A更关键，然后给T的一部分必要性评分。这个必要性的得分是:PR(T)/L(T)

其中PR(T)是T的PageRank值，L(T)是T的链数。

那么A的PageRank值就是一系列类似于t的页面必要性得分的累加。

也就是一个页面的投票数是由所有链接到它的页面的必要性决定的，链接到一个页面就相当于给那个页面投了一票。一个页面的PageRank是通过递归算法对其页面的所有链接(链接到页面)的必要性得到的。有更多链接的页面会有更高的级别。相反，如果一个页面没有所有的链接，它就没有层次。

3.3PageRank简单计算:

假设一个组合只包含4个页面:A、B、C、d，如果所有页面都链接到A，那么A的PR(PageRank)值将是B、C、d之和。

再次假设B也连接到C，D也连接到包含a的3个页面，你不能为一个页面在线投票两次。因此给每一页半张票。同样的逻辑，D投的票只有三分之一到了A的PageRank。

也就是说，一个页面的PR值是按照链接数量平分的。

示例:

图1中的例子展示了PageRank的整个实际计算过程。

3.4调整PageRank计算公式:

因为有一些0的外链，也就是这些不与其他所有网页相连的网络，也叫独立网页，所以可以浏览很多网页。所以需要对PageRank公式的计算进行调整，即阻尼因子Q基本上是在简单公式计算的基础上增加的，Q一般赋为q=0.85。

实际上，它意味着客户在任意时刻到达某个页面后再次访问的概率。1-q=0.15是客户停止后跳转到新URL的概率。所有页面都采用了优化算法，估计页面很有可能被冲浪者放进了笔记。

最后，这一切都计算成百分比，再乘以一个指数q，由于下面的优化算法，没有页面的PageRank将为0。所以Google根据数学课系统软件给了每个页面一个最小值。

公式计算是由定义的公式计算。布林和佩奇在《大规模超文本网络搜索引擎计算机网络和isdn系统的拓扑结构》中。

所以一个页面的PageRank是通过其他页面的PageRank计算出来的。Google不断重复计算每个页面的PageRank。如果给每个页面一个任意的PageRank值(除了0)，那么这个页面的PR值在不断的重复计算后会趋于正常稳定。这就是为什么搜索引擎使用它。

4。PageRank幂法计算(离散数学的应用)

4.1详细公式计算:

对于这一部分，您可以查看:谷歌背后的数学知识

先求详细的公式计算:

在Junghoo乔埃克托·加西亚莫利纳，安德烈亚斯帕佩克，室里拉姆Raghavan。通过搜索网页，Ardarasu更精确地表达了如下内容:

科学研究的是页面，链接页面总数，链接页面总数，n是所有页面总数。

PageRank值是唯一排水矩阵中一个矩阵的特征值。这个矩阵的特征值是:

R是下式的解:

如果网页I具有偏向网页J的连接，那么

否则=0。

4.2用幂法求PageRank

那么大家的PageRank公式计算就可以转化为得到的值，

其中排水矩阵为A=q×P(1-q)*/N..p是概率转移矩阵，都是N维的1行。然后=

功率计算的整个过程如下:

x设原空之间的任意向量，即设置每个原网页的PageRank值。一般1。

R=AX

while(1)

(if(lX-RI<；)

{//如果最后两个结果相似或相同，返回R返回R；

}

否则{

x=R；R=AX

}

}

4.3计算过程:

一、P概率转移矩阵计算全过程:

首先，创建一个网页之间的连接和关联的实体模型，即我们必须设计一个合适的算法来显示网页之间的连接和关联。

1)首先，我们要用图来描述网页的中间关联:

现在，假设只有四个网页组合在一起:A、B、C，它们的抽象结构如下:图1:

图1网页之间的连接关联

很明显，这个图是强连通的(你可以从任何一个连接点到达所有其他连接点)。

2)我们用排水矩阵来表示连通图:

邻接矩阵P用于指示该图上端点的关联。如果顶部(页面)I连接到端点(页面)J，则pij=1，否则pij=0。如图2所示。如果web文档数为N，那么这个web连接引流矩阵就是一个N×N矩矩阵。

3)网络连接概率的排水矩阵

然后将每一行除以该行非零数据之和，即(每行非零数之和为链接网络数)得到新的引流矩阵P’，如图图3所示。这个引流矩阵记录了每个网页自动跳转到其他网页的概率，即第I行和第J列的值表示客户从第I页跳转到第J页的概率，在图1中，A页链接到B和C，所以一个客户从A自动跳转到B和C的概率是1/2。

4)概率转移矩阵P

选择P'的转置矩阵进行计算，也就是上面提到的概率转移矩阵P。如图图4所示:

二、一个排水矩阵计算的全过程。

1)P概率转移矩阵:

2)/N是:

3)一个排水矩阵为:q×P(1-q)*/n=0.85×P0.15*/n。

每个原创网页的PageRank值为1，即x~t=(1，1，1)。

三。计算PageRank的整个过程由循环系统迭代更新

第一步:

因为X和r相差太大.再次迭代更新。

第二步:

再次迭代更新整个过程。...

直到最后2次结果相近或相同，即R最终收敛，R等于X，则终止计算。最后一个r是每页的PageRank值。

幂法计算的PageRank值总是收敛的，即计算的频率是有限的。

拉里·佩奇·谢尔盖·布林(LarryPageSergeyBrin)已经从理论上证明了，无论初始值如何选取，这种优化算法都能保证网页排名的预测值收敛到它们的真实值。

因为互联网技术的网页总数是巨大的，上面说的二维引流矩阵理论上有几个平方米网页数的元素。如果我们假设有10亿个网页，那么这个引流矩阵就有100亿个原始时间。如此大的矩阵相乘需要巨大的计算量。拉里·佩奇·谢尔盖·布林采用稀疏矩阵计算方法，大大简化了计算量。

5。PageRank优化算法的优缺点

优势:

它是一种与查看无关的静态数据优化算法，所有网页的PageRank值都是离线计算的。减少合理快速查询中的计算量，大幅降低查看响应速度。

缺陷:

1)每个人的视图都具有主题风格的特征，PageRank忽略了主题风格的相关性，导致结果与主题元素的相关性降低。

2)旧页面级别将高于新页面级别。再好的新页面也不会有很多上下游链接，除非是某个网站的子站点。

注:本文创作者为Leonis_v，百度站长工具已授予转贴拦截权限，未经创作者许可，不得转贴。