HITS

1 概述

HITS(hypertext induced topic search)超链接归纳主题搜索是由kleinbers在90年代提出的基于链接分析的网页排名算法。Hits算法是利用HubAuthority的搜索方法,即中心权威的思想。

Hits算法的基本思想:

  1. 好的中心网页拥有很多的链出链接,这些链接都指向权威网页。
  2. 好的权威网页拥有很多的链入链接,这些链接都来自中心网页。

即:一个优秀的中心页必然会指向很多优秀的权威页,一个优秀的权威页必然会被很多优秀的中心页指向。

2 网页收集

在算法描述前,先描述HITS算法是如何收集待评级的网页的。HITS将根据如下描述来搜索页面集合:

  1. 它将搜搜字段q送至搜索引擎系统,然后收集t个排名最高的网页,这些网页都是与查询字段q高度相关的。该集合称为根集W。
  2. 然后它通过将指向W集合内部的网页或者W集内部网页指向的外部网页加入W集的方式来扩充W。这就得到了一个更大的集合,我们称为集合S,S被称为基本集。然而,这个集合可能相当的大,算需要通过相纸每个W集内部的网页,仅允许它们最多将K个指向自己的网页加入S来限制S集的大小。

接着HITS对S集内部的每张网页进行处理,对每张S集内部的网页指定一个权威分值和中心分值。

3 HITS算法

HITS算法的求解过程如下:

  1. 收集根集页面
  2. 将所有根集页面的A(Authority Score)和H(hub Score)赋予初值
  3. 根据公式计算新一轮的H和A的值
  4. 规范化结果
  5. 重复(3)(4),直到结果收敛。

具体操作:

    假设待考察的网页数目为n。我们用G=(V,E)来表示S的有向链接图。V是网页集,E是有向边集。我们用L来表示图的邻接矩阵。

HITS-LMLPHP

每张网页i的权威分值被表示为a(i),中心分值被表示为h(i)。两种分值的相互增益关系为:

HITS-LMLPHP

将它们写成矩阵形式,用a表示所有权威分值的列向量,HITS-LMLPHP

用h表示所有中心分值的列向量,HITS-LMLPHP

HITS-LMLPHP

计算权威分值和中心分值采用幂迭代方法。迭代公式如下:

HITS-LMLPHP

初始情况如下:

HITS-LMLPHP

在每次迭代后,数据要进行归一化处理。满足:

HITS-LMLPHP

HITS-LMLPHP时,停止迭代。

4 HITS算法和PageRank算法比较

    相同:

两种算法那都利用了特征向量作为理论基础和收敛基础。这也是超链接环境下此类算法的共同特征。

    不同:

  1. 权值的传播角度:HITS算法是将权威网页的权值经过中心网页的传递进行传播;PageRank算法是将网页的权值直接从权威网页传递给权威网页。
  2. 算法思想角度:HITS算法的权威值只是相对于某个检索主题的权重;PageRank算法独立于搜索主题
  3. 处理的数据量及用户端的等待时间角度:HITS算法对所需排序的网页数量需求少,一般为1000到5000,但由于需要从基于内容分析的搜索引擎中提取根集并扩充基本集,耗时长;PageRank算法处理的数据远远多于HITS。
  4. 从两者处理的对象角度:HITS处理的对象是搜索引擎针对具体查询主题所返回的记过,从几百个页面到几千个页面;PageRank处理的对象是一个搜索引擎上当前搜索下来的所有网页,一般在几千万以上。
  5. 从具体应用的角度:THIS一般用于全文本所有引擎的客户端,对于宽主题的所有相当有效,可以用于自动编撰万维网分类目录或者元搜索引擎的网页排序;PageRank一般用于搜索引擎的服务端,直接用于标题查询并获得较好的结果。

参考文献:

 

[1] [1]常庆,周明全,耿国华. 基于PageRank和HITS的Web搜索[J]. 计算机技术与发展,2008,(07):77-79.

[2] http://blog.csdn.net/androidlushangderen/article/details/43311943

 

 

05-11 19:38