logo资料库

搜索引擎中的 PageRank和HITS算法.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.31M 资料格式：doc 举报 版权申诉
第1页 / 共17页
第2页 / 共17页
第3页 / 共17页
第4页 / 共17页
第5页 / 共17页
第6页 / 共17页
第7页 / 共17页
第8页 / 共17页
资料共17页，剩余部分请下载后查看
    1. PageRank算法概述
    2. 从入链数量到 PageRank
    3. PageRank算法原理
    4. PageRank幂法计算(线性代数应用)
    5. PageRank算法优缺点
    1. Hub页面与Authority页面
    2. 算法基本思想：相互增强关系
    3. HITS算法
    4. HITS算法存在的问题
    5. HITS算法与PageRank算法比较
    1. PageRank 算法概述 PageRank,即网页排名，又称网页级别、Google 左侧排名或佩奇排名。 是 Google 创始人拉里·佩奇和谢尔盖·布林于 1997 年构建早期的搜索系统原型时提出的链接分析算法，自从 Google 在 商业上获得空前的成功后，该算法也成为其他搜索引擎和学术界十分关注的计算模型。目前很多重要的链接分析算法都是在 PageRank 算法基础上衍生出来的。PageRank 是 Google 用于用来标识网页的等级/重要性的一种方法，是 Google 用来衡量 一个网站的好坏的唯一标准。在揉合了诸如 Title 标识和 Keywords 标识等所有其它因素之后，Google 通过 PageRank 来调整 结果，使那些更具“等级/重要性”的网页在搜索结果中另网站排名获得提升，从而提高搜索结果的相关性和质量。其级别从 0 到 10 级，10 级为满分。PR 值越高说明该网页越受欢迎（越重要）。例如：一个 PR 值为 1 的网站表明这个网站不太具有流 行度，而 PR 值为 7 到 10 则表明这个网站非常受欢迎（或者说极其重要）。一般 PR 值达到 4，就算是一个不错的网站了。 Google 把自己的网站的 PR 值定到 10，这说明 Google 这个网站是非常受欢迎的，也可以说这个网站非常重要。 2. 从入链数量到 PageRank 在 PageRank 提出之前，已经有研究者提出利用网页的入链数量来进行链接分析计算，这种入链方法假设一个网页的入 链越多，则该网页越重要。早期的很多搜索引擎也采纳了入链数量作为链接分析方法，对于搜索引擎效果提升也有较明显的 效果。 PageRank 除了考虑到入链数量的影响，还参考了网页质量因素，两者相结合获得了更好的网页重要性评价标准。 对于某个互联网网页 A 来说，该网页 PageRank 的计算基于以下两个基本假设：  数量假设：在 Web 图模型中，如果一个页面节点接收到的其他网页指向的入链数量越多，那么这个页面越重要。  质量假设：指向页面 A 的入链质量不同，质量高的页面会通过链接向其他页面传递更多的权重。所以越是质量高的页面 指向页面 A，则页面 A 越重要。 利用以上两个假设，PageRank 算法刚开始赋予每个网页相同的重要性得分，通过迭代递归计算来更新每个页面节点的 PageRank 得分，直到得分稳定为止。 PageRank 计算得出的结果是网页的重要性评价，这和用户输入的查询是没有任何关 系的，即算法是主题无关的。假设有一个搜索引擎，其相似度计算函数不考虑内容相似因素，完全采用 PageRank 来进行排 序，那么这个搜索引擎的表现是什么样子的呢？这个搜索引擎对于任意不同的查询请求，返回的结果都是相同的，即返回 PageRank 值最高的页面。 3. PageRank 算法原理 PageRank 的计算充分利用了两个假设：数量假设和质量假设。步骤如下： 1）在初始阶段：网页通过链接关系构建起 Web 图，每个页面设置相同的 PageRank 值，通过若干轮的计算，会得到每 个页面所获得的最终 PageRank 值。随着每一轮的计算进行，网页当前的 PageRank 值会不断得到更新。
    2）在一轮中更新页面 PageRank 得分的计算方法：在一轮更新页面 PageRank 得分的计算中，每个页面将其当前的 PageRank 值平均分配到本页面包含的出链上，这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传 入的权值求和，即可得到新的 PageRank 得分。当每个页面都获得了更新后的 PageRank 值，就完成了一轮 PageRank 计算。 3.2 基本思想： 如果网页 T 存在一个指向网页 A 的连接，则表明 T 的所有者认为 A 比较重要，从而把 T 的一部分重要性得分赋予 A。这 个重要性得分值为：PR（T）/L(T) 其中 PR（T）为 T 的 PageRank 值，L(T)为 T 的出链数 则 A 的 PageRank 值为一系列类似于 T 的页面重要性得分值的累加。 即一个页面的得票数由所有链向它的页面的重要性来决定，到一个页面的超链接相当于对该页投一票。一个页面的 PageRank 是由所有链向它的页面（链入页面）的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级，相反 如果一个页面没有任何链入页面，那么它没有等级。 3.3 PageRank 简单计算： 假设一个由只有 4 个页面组成的集合：A，B，C 和 D。如果所有页面都链向 A，那么 A 的 PR（PageRank）值将是 B， C 及 D 的和。 继续假设 B 也有链接到 C，并且 D 也有链接到包括 A 的 3 个页面。一个页面不能投票 2 次。所以 B 给每个页面半票。 以同样的逻辑，D 投出的票只有三分之一算到了 A 的 PageRank 上。 换句话说，根据链出总数平分一个页面的 PR 值。 例子： 如图 1 所示的例子来说明 PageRank 的具体计算过程。
    3.4 修正 PageRank 计算公式： 由于存在一些出链为 0，也就是那些不链接任何其他网页的网， 也称为孤立网页，使得很多网页能被访问到。因此需要 对 PageRank 公式进行修正，即在简单公式的基础上增加了阻尼系数（damping factor）q， q 一般取值 q=0.85。 其意义是，在任意时刻，用户到达某页面后并继续向后浏览的概率。 1- q= 0.15 就是用户停止点击，随机跳到新 URL 的 概率）的算法被用到了所有页面上，估算页面可能被上网者放入书签的概率。 最后，即所有这些被换算为一个百分比再乘上一个系数 q。由于下面的算法，没有页面的 PageRank 会是 0。所以，Google 通过数学系统给了每个页面一个最小值。 这个公式就是.S Brin 和 L. Page 在《The Anatomy of a Large- scale Hypertextual Web Search Engine Computer Networks and ISDN Systems 》定义的公式。 所以一个页面的 PageRank 是由其他页面的 PageRank 计算得到。Google 不断的重复计算每个页面的 PageRank。如果 给每个页面一个随机 PageRank 值（非 0），那么经过不断的重复计算，这些页面的 PR 值会趋向于正常和稳定。这就是搜索 引擎使用它的原因。
    4. PageRank 幂法计算(线性代数应用) 4.1 完整公式： 关于这节内容，可以查阅：谷歌背后的数学 首先求完整的公式： Arvind Arasu 在《Junghoo Cho Hector Garcia - Molina, Andreas Paepcke, Sriram Raghavan. Searching the Web》 更加准 确的表达为： 是被研究的页面， 是 链入页面的数量， 是 链出页面的数量，而 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 ( l X - R I < ) { //如果最后两次的结果近似或者相同，返回 R return R; } else { X =R; R = AX; } } 4.3 求解步骤：
    一、 P 概率转移矩阵的计算过程: 先建立一个网页间的链接关系的模型,即我们需要合适的数据结构表示页面间的连接关系。 1) 首先我们使用图的形式来表述网页之间关系： 现在假设只有四张网页集合：A、B、C，其抽象结构如下图 1： 图 1 网页间的链接关系 显然这个图是强连通的（从任一节点出发都可以到达另外任何一个节点）。 2）我们用矩阵表示连通图： 用邻接矩阵 P 表示这个图中顶点关系 ，如果顶（页面）i 向顶点（页面）j 有链接情况 ，则 pij = 1 ，否则 pij = 0 。 如图 2 所示。如果网页文件总数为 N ， 那么这个网页链接矩阵就是一个 N x N 的矩 阵 。 3）网页链接概率矩阵 然后将每一行除以该行非零数字之和，即（每行非 0 数之和就是链接网个数）则得到新矩阵 P’，如图 3 所示。 这个矩阵 记录了 每个网页跳转到其他网页的概率，即其中 i 行 j 列的值表示用户从页面 i 转到页面 j 的概率。图 1 中 A 页面链向 B、C， 所以一个用户从 A 跳转到 B、C 的概率各为 1/2。 4）概率转移矩阵 P 采用 P’ 的转置矩 阵进行计算， 也就是上面提到的概率转移矩阵 P 。 如图 4 所示：
    图 2 网页链接矩阵： 图 3 网页链接概率矩阵： 图 4 P’ 的转置矩 阵 二、 A 矩阵计算过程。 1）P 概率转移矩阵 : 2） /N 为： 3）A 矩阵为：q × P + ( 1 一 q) * /N = 0.85 × P + 0.15 * /N
    初始每个网页的 PageRank 值均为 1 ， 即 X~t = ( 1 ， 1 ， 1 ) 。 三、 循环迭代计算 PageRank 的过程 第一步： 因为 X 与 R 的差别较大。 继续迭代。 第二步： 继续迭代这个过程... 直到最后两次的结果近似或者相同，即 R 最终收敛，R 约等于 X，此时计算停止。最终的 R 就是各个页面的 PageRank 值。 用幂法计算 PageRank 值总是收敛的，即计算的次数是有限的。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料