知识吧 知识资讯 搜索策略产品经理必读系列—第五讲Page Rank算法 | 人人都是产品经理

搜索策略产品经理必读系列—第五讲Page Rank算法 | 人人都是产品经理

搜索引擎中最早网页搜索结果排序效果比较优的算法就是Google创始人提出的Page Rank算法,作为搜索领域的从业者必须要了解该经典算法的思想。本文结合实际案例一篇讲懂Page Rank算法的基本思想,同时还为大家介绍后续优化后的Page Rank算法。

一、基本假设

在正式介绍Page Rank算法前我们先通过实际生活中的一个案例入手。日常我们写论文时经常会引用别人的论文,某个行业里的经典论文会被大量的论文所引用。如果该论文恰好还被另外一篇经典论文所引用的话,则更加能够凸显出该篇论文的重要性和权威性,其实网页的重要性和权威性也是如此。

于是我们设定以下两大假设。

数量假设:当一个网页被其他网页链接的数量越多,入链数越大,则该网页越重要。

搜索策略产品经理必读系列—第五讲Page Rank算法 | 人人都是产品经理

如上图所示,网站“WWW1”被众多网站引用,形成了链接,则说明网站“WWW1”很重要。

  • 质量假设:被高质量的网页链接时,说明被链接的网页质量也很高,权威性也很强。

搜索策略产品经理必读系列—第五讲Page Rank算法 | 人人都是产品经理

如上图所示,网站“WWW8”被高质量网站“WWW1”引用,形成了链接,说明网站“WWW8”同样也很权威。PageRank算法的整体思想都是建立在上述假设上的。

二、Page Rank基本算法

基于以上两大假设,我们展开介绍Page Rank算法。首先我们将互联网想象为一个图网络,网络的每一个节点(Node)就是一个个独立的网页,如果两个网页之间存在超链接的关系,则它们两个之间存在一条有方向的边(Edge),每个节点向外链接的节点数被称为该节点的出度。

每个节点的Page Rank值(以下简称PR值)表示该节点的权威性。我们核心是构建一个用户在图网络中的游走模型,基于游走模型来进行PR值的更新迭代。

搜索策略产品经理必读系列—第五讲Page Rank算法 | 人人都是产品经理

上面即为Page Rank算法的基本定义,首先节点 ν_1 的PR值是由链接到该节点的其他节点PR值决定的,假设链接节点是 ν_2、ν_3 。链接的其他节点越多则该节点的PR值越大,所以算法迭代使用累加 ∑ 。需要将节点 ν_2、ν_3 的PR值进行累加,此迭代思路对应着上述的“数量假设”。

链接的其他节点PR值越大,则该节点的PR值也越大,对应着上述的“质量假设”。同时 ν_2、ν_3 节点还链接其他节点,用户通过节点 ν_2、ν_3 跳转到节点 ν_1 的概率为 1/O(ν_j ) , O(ν_j ) 为节点 ν_j 的出度。节点 ν_2、ν_3 的PR值分别乘以 1/O(ν_2 )和1/O(ν_3 ) ,再进行累加即为节点 ν_1 的PR值。我们通过该方式不断迭代更新节点的PR值,直到最终整个网络里所有节点的PR值满足收敛条件。

三、具体案例

下面我们通过一个例子来详细介绍Page Rank算法的迭代过程。

搜索策略产品经理必读系列—第五讲Page Rank算法 | 人人都是产品经理

初始时4个节点的PR值均为1/4。经过第一次迭代,我们得到了 R_1 =[3/8,5/24,5/24,5/24]^T 。我们可以将上述计算过程变成一个矩阵计算,通过矩阵化的表达,可以快速的计算得到PR值。

首先我们基于各个节点的出度构建一个转移概率矩阵 M ,节点A的出度为3,链接了B、C、D三个节点,我们认为节点A转移到B、C、D节点的概率均为1/3,以此类推我们可以得到一个转移概率矩阵 M 。那么PR的迭代公式就变为: M*R_t=R_(t+1) 。

搜索策略产品经理必读系列—第五讲Page Rank算法 | 人人都是产品经理

如上所示 M*R_1=R_2 ,和我们最上方计算的结果完全一致。但是上述Page Rank基本算法应用时会存在以下两大问题:

问题一:很多网站并没有和其他网站建立任何的链接,出度为0。这类网站的出现会导致按照上述算法进行 R_i 迭代,最终所有节点的PR值归于零。

问题二:用户打开某一个网站后,即使该网站链接了其他网站,但是用户还是可能会随机打开其他网站,所以没有链接的其他网站转移概率不应该是0,系统可以设置一个随机概率。

四、Page Rank优化算法

基于Page Rank基本算法存在的两大问题上,科学家们又对Page Rank算法进行了优化,优化后的Page Rank算法可以适用于所有的网络结构,更加贴近于实际用户浏览行为。优化后的算法PR值更新迭代如下:

R_(t+1)=d*M*R_t+(1-d)*E/N

全新迭代公式的业务理解是:用户在浏览网页时有两种情况,第一种情况是以概率 d(0≤d≤1) 完全按照原本的转移概率矩阵进行游走,第二种情况是以概率(1- d )随机访问任何其他的节点,每个节点的链接概率都是1/N, E 是元素1填满的N*N矩阵。

d 又被成为阻尼因子, d 的取值一般由经验决定,正常在0.8-0.9之间。当 d 接近1时,用户随机游走主要依照转移概率矩阵 M 进行;当 d 接近0时,用户随机游走主要以等概率随机访问各个结点。

虽然目前搜索引擎的排序算法已经优化迭代了很多版本,但是Page Rank算法的核心思想仍然在被使用,也应用到了其他领域。Page Rank是从事搜索领域人士必须要了解的算法之一。

本文由 @King James 原创发布于知识吧。未经许可,禁止转载。

题图来自 Unsplash,基于 CC0 协议

该文观点仅代表作者本人,知识吧平台仅提供信息存储空间服务。

给作者打赏,鼓励TA抓紧创作!



本文来自网络,不代表知识吧立场,转载请注明出处:https://zhishiba.net/2473.html
上一篇
下一篇

发表回复

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

返回顶部

Warning: error_log(/www/wwwroot/www.zhishiba.net/wp-content/plugins/spider-analyser/#log/log-2805.txt): failed to open stream: No such file or directory in /www/wwwroot/www.zhishiba.net/wp-content/plugins/spider-analyser/spider.class.php on line 2900