写点什么

Week 13 命题作业

用户头像
Jeremy
关注
发布于: 2020 年 09 月 15 日
Week 13 命题作业
Google 搜索引擎是如何对搜索结果进行排序的?(请用自己的语言描述 PageRank 算法。)



PageRank算法做了两个基本假设:

数量假设:被更多的网页链接到的网页更重要。

质量假设:有更高权重的网页会传递更高的权重出去。

PageRank的公式简单模型:

PRi​=jϵBj​∑​LjPRj​​

PR为权重,L为出链数。在理想状态下,页面i的权重是所有链接到该页面的页面平均投票权重的总和。

在初始化阶段,设所有页面的权重都为1,根据以上公式进行迭代计算,更新各个页面的PR值,直到PR值收敛。

终止点:

终止点是指一个没有任何出链的网页。

在基础公式中,终止点会导致转移矩阵终止转移概率,最后迭代的结果是所有的网页PR值都是0。

因此当访问到终止点时,以等概率跳转到下一个网页。该概率为1/矩阵行数。

陷阱:

陷阱/黑洞指的是只有指向自身链接的网页,如图中C点。

根据基础公式多次迭代,会使得陷阱页面的PR值为1,而其他正常网页的概率为0。

为了解决这个问题,就有了随机浏览模型。

PRi​=djϵBj​∑​LjPRj​​+N1−d

其中d为阻尼系数,N为所有页面的数量。



用户头像

Jeremy

关注

还未添加个人签名 2018.01.21 加入

还未添加个人简介

评论

发布
暂无评论
Week 13 命题作业