关于做美食的小视频网站,手机软件编程,住房建设部官方网站专家注册,大学生作业做网站文章目录 #x1f4da;链接分析#x1f4da;随机矩阵#x1f4da;random walk#x1f4da;Google formulation #x1f4da;链接分析 将链接看做投票#xff0c;从重要的网站来的链接其权重更高#xff0c;所以是递归定义的。 如果网页j权重为rj#xff0c;有n个出边链接分析随机矩阵random walkGoogle formulation 链接分析 将链接看做投票从重要的网站来的链接其权重更高所以是递归定义的。 如果网页j权重为rj有n个出边每个出边的权重为rj/n而网页j的自身权重为所有入边的权重之和。定义如下 3个未知数3个方程没有唯一解都是free的所以可以引入限制sum1 随机矩阵 使用矩阵表达rMr: 该随机邻近矩阵M每列求和为1对于向量r来说列元素求和为1ri表示i的重要性评分。同时r是M的特征向量对应的特征值为1由于1是M的最大特征值所以可以使用幂迭代法对r进行快速求解
random walk t时刻浏览者在网页i在t1时刻从i的超链接中随机选择一个作为下一个浏览的网页选择每一个网页的概率是一致的 p ( t 1 ) M ⋅ p ( t ) p(t1)M·p(t) p(t1)M⋅p(t)。 假设随机游走达到一个状态 p ( t 1 ) M ⋅ p ( t ) p ( t ) p(t1)M·p(t)p(t) p(t1)M⋅p(t)p(t)时称pt为随机游走的稳定分布。 我们的原始r向量满足rMr所以r就是随机游走的稳定分布。 满足确定条件的图来说其稳定分布是存在且唯一的且无论初始向量是什么最后一定会到达平稳分布
Google formulation 原来表达形式的问题不一定会收敛或者收敛不到我们想要的结果 可能存在的两种特殊情况 dead end没有出边随机行走没有下一个点可以选择容易造成泄漏 spider traps环所有的出边都在环内将被困在环中最终spider trap吸收了所有的importance 举例如果走到m则不会跳出将一直访问m最后r向量收敛为[0,0,1]。 解决方法随机跳转teleports 在每一个时间t中用户有两种选择以概率beta随机选择一个连接进行随即游走或者以概率 1 − β 1-\beta 1−β进行随机跳转 β \beta β一般在0.8-0.9之间。进而用户可以跳出spider trap。同时对于dead-ends来说用户直接执行随机跳转此时访问其他连接的概率为1/N。 理解 spider-traps不是问题但是trap的pagerank 评分不是我们想要的所以我们使用随机跳转在有限步内跳出trap不会被困在里面 dead-ends是一个问题因为此时列向量不是随机向量不满足初始条件所以我们在之上执行随机游走将列向量变为随机向量 最后公式变为 此时矩阵A可以写为 从而 r A ⋅ r rA·r rA⋅r依然可以使用幂迭代法实际中 β \beta β0.8 补充博客pagerank算法实现PageRank算法中Power Iteration的解释。 Power Iteration的基本思想是通过不断迭代更新网页的权重值直到收敛。以下是Power Iteration算法的基本步骤 初始化将所有网页的初始PageRank值设置为相同的数值通常为1/N其中N是网页的总数。迭代计算重复进行以下步骤直到收敛为止 对于每个网页i根据其当前的PageRank值和其出链的数量来计算对其他网页的贡献值即将自己的PageRank值平均分配给其出链的网页。将网页i的贡献值累加到其每个入链网页j的PageRank值上。对每个网页j根据收到的所有入链网页的贡献值来更新其新的PageRank值。收敛判定当所有网页的PageRank值变化小于设定的阈值时算法收敛。 Power Iteration的核心思想是通过不断传递和累积网页权重值直到每个网页的PageRank值稳定下来。
