搜索引擎链接算法之:HITS算法解析

标签: 搜索引擎 链接 算法 | 发表时间:2012-02-06 21:25 | 作者:malefactor
出处:http://blog.csdn.net

                                                                       

                                      本文节选自《 这就是搜索引擎:核心技术详解》第六章

      HITS算法也是链接分析中非常基础且重要的算法,目前已被Teoma搜索引擎(www.teoma.com)作为链接分析算法在实际中使用。


6.4.1 Hub页面与Authority页面

 

     Hub页面和Authority页面是HITS算法最基本的两个定义。所谓“Authority”页面,是指与某个领域或者某个话题相关的高质量网页,比如搜索引擎领域,Google和百度首页即该领域的高质量网页,比如视频领域,优酷和土豆首页即该领域的高质量网页。所谓“Hub”页面,指的是包含了很多指向高质量“Authority”页面链接的网页,比如hao123首页可以认为是一个典型的高质量“Hub”网页。

      图6-11给出了一个“Hub”页面实例,这个网页是斯坦福大学计算语言学研究组维护的页面,这个网页收集了与统计自然语言处理相关的高质量资源,包括一些著名的开源软件包及语料库等,并通过链接的方式指向这些资源页面。这个页面可以认为是“自然语言处理”这个领域的“Hub”页面,相应的,被这个页面指向的资源页面,大部分是高质量的“Authority”页面。

                         

                                          图6-11 自然语言处理领域的Hub页面

 

     HITS算法的目的即是通过一定的技术手段,在海量网页中找到与用户查询主题相关的高质量“Authority”页面和“Hub”页面,尤其是“Authority”页面,因为这些页面代表了能够满足用户查询的高质量内容,搜索引擎以此作为搜索结果返回给用户。


6.4.2 相互增强关系


    很多算法都是建立在一些假设之上的,HITS算法也不例外。HITS算法隐含并利用了2个基本假设:

       基本假设1:一个好的“Authority”页面 会被很多好的“Hub”页面指向;

       基本假设2:一个好的“Hub”页面 会指向很多好的“Authority”页面;

到目前为止,无论是从“Hub”或者“Authority”页面的定义也好,还是从两个基本假设也好,都能看到一个模糊的描述,即“高质量”或者“好的”,那么什么是“好的”Hub页面?什么是“好的”Authority页面?两个基本假设给出了所谓“好”的定义。

      基本假设1说明了什么是“好的”Authority页面,即被很多好的Hub页面指向的页面是好的“Authority”页面,这里两个修饰语非常重要:“很多”和“好的”,所谓“很多”,即被越多的Hub页面指向越好,所谓“好的”,意味着指向本页面的“Hub”页面质量越高,则本页面越好。即综合了指向本页面的所有Hub节点的数量和质量因素。

      基本假设2则给出了什么是“好的”Hub页面的说明,即指向很多好的Authority页面的网页是好的Hub页面。同样的,“很多”和“好的”两个修饰语很重要,所谓“很多”,即指向的Authority页面数量越多越好;所谓“好的”,即指向的Authority页面质量越高,则本页面越是好的Hub页面。也即综合考虑了该页面有链接指向的所有页面的数量和质量因素。

      从以上两个基本假设可以推导出Hub页面和Authority页面之间的相互增强关系(参考图6-12), 即某个网页的Hub质量越高,则其链接指向的页面的Authority质量越好;反过来也是如此,一个网页的Authority质量越高,则那些有链接指向本网页的页面Hub质量越高。通过这种相互增强关系不断迭代计算,即可找出哪些页面是高质量的Hub页面,哪些页面是高质量的Authority页面。

                                                   

                                                    图6-12 相互增强关系

                                                            

6.4.3 HITS算法

      HITS算法与Pagerank算法一个显著的差异是:HITS算法与用户输入的查询请求密切相关,而Pagerank是与查询无关的全局算法。HITS后续计算步骤都是在接收到用户查询后展开的,即是与查询相关的链接分析算法。

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

      在根集的基础上,HITS算法对网页集合进行扩充(参考图6-13),扩充原则是:凡是与根集内网页有直接链接指向关系的网页都被扩充进来,无论是有链接指向根集内页面也好,或者是根集页面有链接指向的页面也好,都被扩充进入扩展网页集合。HITS算法在这个扩充网页集合内寻找好的“Hub”页面与好的“Authority”页面。

                                       

                                                       图6-13 根集与扩展集

      对于“扩充网页集合”来说,我们并不知道哪些页面是好的“Hub”或者好的“Authority”页面,每个网页都有潜在的可能,所以对于每个页面都设立两个权值,分别来记载这个页面是好的Hub或者Authority页面的可能性。在初始情况下,在没有更多可利用信息前,每个页面的这两个权值都是相同的,可以都设置为1。

      之后,即可利用上面提到的两个基本假设,以及相互增强关系等原则进行多轮迭代计算,每轮迭代计算更新每个页面的两个权值,直到权值稳定不再发生明显的变化为止。

     图6-14给出了迭代计算过程中,某个页面的Hub权值和Authority权值的更新方式。假设以A(i)代表网页i的Authority权值,以H(i)代表网页i的Hub权值。在图6-14的例子中,“扩充网页集合”有3个网页有链接指向页面1,同时页面1有3个链接指向其它页面。那么,网页1在此轮迭代中的Authority权值即为所有指向网页1页面的Hub权值之和;类似的,网页1的Hub分值即为所指向的页面的Authority权值之和。

                                                  

                                                                图6-14  Hub与Authority权值计算

         “扩充网页集合”内其它页面也以类似的方式对两个权值进行更新,当每个页面的权值都获得了更新,则完成了一轮迭代计算,此时HITS算法会评估上一轮迭代计算中的权值和本轮迭代之后权值的差异,如果发现总体来说权值没有明显变化,说明系统已进入稳定状态,则可以结束计算。将页面根据Authority权值得分由高到低排序,取权值最高的若干页面作为响应用户查询的搜索结果输出。如果比较发现两轮计算总体权值差异较大,则继续进入下一轮迭代计算,直到整个系统权值稳定为止。

                     

6.4.4  HITS算法存在的问题

      HITS算法整体而言是个效果很好的算法,目前不仅应用在搜索引擎领域,而且被“自然语言处理”以及“社交分析”等很多其它计算机领域借鉴使用,并取得了很好的应用效果。尽管如此,最初版本的HITS算法仍然存在一些问题,而后续很多基于HITS算法的链接分析方法,也是立足于改进HITS算法存在的这些问题而提出的。

       归纳起来,HITS算法主要在以下几个方面存在不足:

        1.计算效率较低

           因为HITS算法是与查询相关的算法,所以必须在接收到用户查询后实时进行计算,而HITS算法本身需要进行很多轮迭代计算才能获得最终结果,这导致其计算效率较低,这是实际应用时必须慎重考虑的问题。

        2.主题漂移问题

          如果在扩展网页集合里包含部分与查询主题无关的页面,而且这些页面之间有较多的相互链接指向,那么使用HITS算法很可能会给予这些无关网页很高的排名,导致搜索结果发生主题漂移,这种现象被称为“紧密链接社区现象”(Tightly-Knit CommunityEffect)。

        3.易被作弊者操纵结果

          HITS从机制上很容易被作弊者操纵,比如作弊者可以建立一个网页,页面内容增加很多指向高质量网页或者著名网站的网址,这就是一个很好的Hub页面,之后作弊者再将这个网页链接指向作弊网页,于是可以提升作弊网页的Authority得分。

        4.结构不稳定

         所谓结构不稳定,就是说在原有的“扩充网页集合”内,如果添加删除个别网页或者改变少数链接关系,则HITS算法的排名结果就会有非常大的改变。

 

6.4.5 HITS算法与PageRank算法比较

 

     HITS算法和PageRank算法可以说是搜索引擎链接分析的两个最基础且最重要的算法。从以上对两个算法的介绍可以看出,两者无论是在基本概念模型还是计算思路以及技术实现细节都有很大的不同,下面对两者之间的差异进行逐一说明。       

      1.HITS算法是与用户输入的查询请求密切相关的,而PageRank与查询请求无关。所以,HITS算法可以单独作为相似性计算评价标准,而PageRank必须结合内容相似性计算才可以用来对网页相关性进行评价;

      2.HITS算法因为与用户查询密切相关,所以必须在接收到用户查询后实时进行计算,计算效率较低;而PageRank则可以在爬虫抓取完成后离线计算,在线直接使用计算结果,计算效率较高;

      3.HITS算法的计算对象数量较少,只需计算扩展集合内网页之间的链接关系;而PageRank是全局性算法,对所有互联网页面节点进行处理;

      4.从两者的计算效率和处理对象集合大小来比较,PageRank更适合部署在服务器端,而HITS算法更适合部署在客户端;

       5.HITS算法存在主题泛化问题,所以更适合处理具体化的用户查询;而PageRank在处理宽泛的用户查询时更有优势;

      6.HITS算法在计算时,对于每个页面需要计算两个分值,而PageRank只需计算一个分值即可;在搜索引擎领域,更重视HITS算法计算出的Authority权值,但是在很多应用HITS算法的其它领域,Hub分值也有很重要的作用;

      7.从链接反作弊的角度来说,PageRank从机制上优于HITS算法,而HITS算法更易遭受链接作弊的影响。

      8.HITS算法结构不稳定,当对“扩充网页集合”内链接关系作出很小改变,则对最终排名有很大影响;而PageRank相对HITS而言表现稳定,其根本原因在于PageRank计算时的“远程跳转”。


作者:malefactor 发表于2012-2-6 21:25:00 原文链接
阅读:9 评论:0 查看评论

相关 [搜索引擎 链接 算法] 推荐:

搜索引擎链接算法之:HITS算法解析

- - CSDN博客推荐文章
本文节选自《 这就是搜索引擎:核心技术详解》第六章.       HITS算法也是链接分析中非常基础且重要的算法,目前已被Teoma搜索引擎(www.teoma.com)作为链接分析算法在实际中使用. 6.4.1 Hub页面与Authority页面.      Hub页面和Authority页面是HITS算法最基本的两个定义.

搜索引擎网页去重算法

- - 醉清风
  相关统计数据表明:互联网上近似重复的网页的数量占网页总数量的比例高达29%,完全相同的网页大约占网页总数量的22%.研究表明,在一个大型的信息采集系统中,30%的网页是和另外70%的网页完全重复或近似重复的.     即:互联网的网页中相当高的比例的网页内容是近似相同或完全相同的. 搜索爬虫抓取会产生网页重复的类型:.

Google公布调整搜索引擎算法的细节

- tt5ryan - Solidot
淘宝网女装秋装 写道 "尽管Google拥有很多开放的产品和项目,但搜索引擎算法一直是保密的. 换句话说,搜索是Google的一个黑盒子. Google此前表示,如果Google向外界公布搜索引擎算法,那么将会引起搜索结果排序的混乱. 但Google周五在官方博客上发布了一则视频,视频给出了Google工程师调整搜索引擎算法的细节.

简易垂直搜索引擎的核心算法总结

- - CSDN博客架构设计推荐文章
倒排索引源于实际应用中需要根据属性值(字段)来查找记录(所在的文件位置). 这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址. 目前主流的索引技术有三种:倒排索引、后缀数组以及签名. 后缀数组虽然快,但是维护困难,代价高昂,不适合作为搜索引擎的索引. 而签名的速度和性能都不如倒排索引.

Goolge十年对搜索引擎算法做出的改善

- - CSDN博客互联网推荐文章
谷歌过去十年,在搜索引擎上做出了巨大的努力,其努力的方向就是不断完善搜索引擎算法,不断打击非真实的数据,从PR、nofollow、企鹅新算法的出现也是必然的. 2000年12月 – Google工具条. Google发布了浏览器工具条,正是这个工具条上绿色小条(PR值),日后让无数的站长为之疯狂,形成了买卖产业链.

uSniff:BT种子搜索引擎

- leqoqo - 软件志
一、uSniff相关信息: 1、官方主页:http://www.usniff.com/ 2、简介:uSniff是一个BT种子搜索引擎,简单、易用、实时是其最大的优点,其搜索引擎数据库包含了17个知名种子站点的种子信息,目的是想发展成为世界上最大的BT种子搜索引擎,而且对于每个种子,该搜索引擎都会进行安全认证,以保证用户的正常使用.

人眼启发视觉搜索引擎

- feng823 - Solidot
Google上周宣布将支持声音和图片进行搜索,但一家创业公司在图像搜索方面走在了Google前面. 源自伦敦帝国学院研究项目的创业公司Cortexica,开发出视觉搜索工具,通过手机拍摄产品照片,它会自动呈现价格信息. Cortexica已经发布了一个用于比较酒价格的工具WINEfindr. Cortexica的视觉搜索技术是受到了人眼视觉系统的启发,它能识别出一个目标的关键特征,不受方位、大小、光线亮暗的影响.

比较好的学术搜索引擎

- hfut_chen - C++博客-首页原创精华区
     摘要: 1、http://scholar.google.com/. Google学术搜索滤掉了普通搜索结果中大量的垃圾信息,排列出文章的不同版本以及被其它文章的引用次数. 略显不足的是,它搜索出来的结果没有按照权威度(譬如影响因子、引用次数)依次排列,在中国搜索出来的,前几页可能大部分为中文的一些期刊的文章.

Blekko 对搜索引擎的新探索

- thinkingit - 知乎的博客
Blekko 这款搜索产品做的如何. 从目前我的使用过程来看,Blekko还是很让人激动的. 在谈Blekko之前就要先问:为何在搜索这个看似已经垄断的行业还会有人想去分一杯羹,这些小团队能与Google或微软这样的巨头抗衡吗. 比如之前的Powerset,后来的Cuil,和现在的Blekko. 在Google之前Yahoo是靠人工收录网页,Google的算法和蜘蛛革了搜索的命,一直垄断搜索业十余年,而现在随着WEB 2.0的发展,让人又看到了搜索业革命的火种,可以说Blekko就是这样的一个产品.

Mr.Icons:图标icon搜索引擎

- 壮壮爱 - 够趣堂
之前Anliu在如何更换更好的icon文章里面推荐了4个icon搜索引擎,目前部分已经不复存在. 不过Mr.Icons倒是又一个不错的选择,可以搜索图标icon进行下载,有PNG、ico格式以及不同大小提供下载. Mr.Icons还提供图标icon集打包下载,比如动物图标等. 和之前的介绍几款搜索引擎一样,依然不支持中文.