aihot  2017-11-25 16:52:57  C++ |   查看评论   

浅谈搜索引擎基础(下)

链接分析

  我们在最开始说过,搜索引擎在查找能够满足用户需求的网页时,主要会考虑两方面的因素,一方面是用户发出的查询与网页内容的相关性得分,另一点就是通过链接分析方法计算获得的得分,也即网页的重要性

PageRank算法

  PageRank算法是Google创始人于1997年构建早期搜索系统原型时提出的链接分析算法,目前很多重要的链接分析算法都是在PageRank算法基础上衍生出来的。

  对于某个网页A来说,该网页的PageRank计算基于以下两个基本假设:

  • 数量假设:在Web图模型中,如果一个页面节点接收到的其他网页指向的入链数量越多,那么这个页面越重要。
  • 质量假设:指向页面A的入链质量不同,质量高的页面会通过链接向其他页面传递更多的权重。所以越是高质量的页面指向页面A,页面A越重要。

  PageRank计算得出的结果是网页的重要性评价,这和用户输入的查询是没有任何关系的。也即如果有一个搜索引擎完全基于PageRank,那用户不论输入什么查询语句,返回的结果都是相同的,都是PageRank值最高的页面。

PageRank计算

  初始阶段,每个页面设置相同的PageRank值,通过若干轮的计算,每个页面会收敛到最终的PageRank值。

  在一轮PageRank得分的更新计算中,每个页面将其当前的PageRank值平均分配到本页包含的出链上,这样每个链接即获得了相应的权值。而每个页面将所有指向本页面的入链所传入的权值求和,即可得到新的PageRank得分。当每个页面都获得了更新后的PageRank值,就完成了一轮PageRank计算。

链接陷阱与远程跳转

  如果仔细思考一下就会发现上面的PageRank算法存在问题。一个典型的例子就是链接陷阱,比如三个网页,相互链接指向,形成了一个环结构,这种结构在计算PageRank的时候,该结构将导致系统只会吸收传入的分支,而不能将获得的分值传播出去,随着PageRank一轮轮地连续计算,链接陷阱内的页面PageRank值将会越来越高。

  远程跳转是解决链接陷阱的通用方式,所谓远程跳转,即在网页向外传递分值的时候,不限于向出链所指网页传递,也可以以一定的概率向任意其他网页跳转。权值通过这种虚拟边向外传递,以此来避免链接陷阱导致的问题。

HITS算法(Hypertext Induced Topic Selection)

Hub页面与Authority页面

  Hub页面与Authority页面是HITS算法最基本的两个定义,所谓Authority页面是指与某个领域或某个话题相关的高质量网页;所谓Hub页面,指的是包含了很多指向高质量Authority页面链接的网页。

相互增强关系

  HITS算法隐含并利用了两个基本假设:

  • 一个好的Authority页面会被很多好的Hub页面指向
  • 一个好的Hub页面会指向很多好的Authority页面

  通过这种相互增强关系不断迭代计算,即可找出哪些页面是高质量的Hub页面和Authority页面。

HITS算法流程

  HITS算法与PageRank一个显著的区别就是HITS算法与用户输入的查询请求密切相关,而PageRank算法是与查询无关的全局算法。

  HITS算法接收到了用户查询之后,会将查询提交给某个现有的搜索引擎或是自己构建的检索模型,并在返回的搜索结果中,提取排名靠前的网页,得到一组与用户查询高度相关的初始网页集合,这个集合被称为根集。

  在根集的基础上,凡是与根集网页有直接链接指向关系(指向根集内页面/根集页面有链接指向)的网页都被扩充进扩展网页集合。HITS算法在这个扩展网页集合内寻找好的Hub页面与Authority页面。

  对于扩展网页集合,我们对每个页面都设置两个初始权值,一般将Hub权值和Authrity权值都初始化为1

  之后可以根据前面的两条基本假设不断进行迭代,直到权值收敛。

  HITS算法存在主题漂移问题,如果在扩展网页集合里包含部分与查询主题无关的页面,而且这些页面之间有较多的相互链接指向,那么HITS算法很可能给给予这些无关网页很高的排名,这种现象被称为紧密链接社区现象。

  HITS算法计算效率较低,且较容易被作弊者操纵结果,而PageRank因为增加了远程跳转,机制上优于HITS算法。

SALSA算法

  SALSA算法融合了PageRank与HITS算法的基本思想,是目前效果最好的链接分析算法之一。

  SALSA算法有两个阶段,首先是确定计算对象集合的阶段,这一阶段与HITS算法基本相同;第二阶段是链接关系传播过程,这一阶段采纳了PageRank的随机游走模型。

 1/6    1 2 3 4 5 6 下一页 尾页
  
 

除特别注明外,本站所有文章均为 人工智能学习网 原创,转载请注明出处来自浅谈搜索引擎基础(下)

留言与评论(共有 0 条评论)
   
验证码: