页面搜索HITS算法新编.ppt

Web 页面搜索 HITS 算法 HITS(Hyperlink-Induced Topic Search) 算法是由康奈尔大学( Cornell University ) 的 Jon Kleinberg 博士于 1997 年首先提出的基于链接分析的网页排名算法。 Hub 页面(枢纽页面) 和 Authority 页面(权威页面) 是 HITS 算法最基本的两个定义。?“ Authority ”页面,是指与某个领域或者某个话题相关的高质量网页, eg: 搜索引擎领域, Google 和百度首页即该领域的高质量网页, eg: 视频领域,优酷和土豆首页即该领域的高质量网页。?“目录型( Hub )网页”:该网页提供很多指向其它高质量权威型网页的超链。 eg: hao123 首页可以认为是一个典型的高质量“ Hub ”网页。 HITS 算法的基本思想 “Authority ”页面会被很多好的“Hub ”页面指向; “Hub ”页面会指向很多好的“Authority ”页面; 具体算法: 可利用上面提到的两个基本思想, 以及相互增强关系等原则进行多轮迭代计算, 每轮迭代计算更新每个页面的两个权值,直到权值稳定不再发生明显的变化为止。 HITS 算法的步骤根集合: 将查询 q提交给基于关键字查询的检索系统,从返回结果页面的集合总取前 n个网页(如 n=200 ), 作为根集合(root set) ,记为 root ,则 root 满足: 1).root 中的网页数量较少 2).root 中的网页是与查询 q相关的网页 3).root 中的网页包含较多的权威(Authority) 网页这个集合是个有向图结构: ?? EVG, 第一步: 第二步扩展集合 base : 在根集 root 的基础上, HITS 算法对网页集合进行扩充(如图)集合 base ,扩充原则是:凡是与根集内网页有直接链接指向关系的网页都被扩充到集合 base , 无论是有链接指向根集内页面也好,或者是根集页面有链接指向的页面也好, 都被扩充进入扩展网页集合 base 。 HITS 算法在这个扩充网页集合内寻找好的“ Hub ”页面与好的“ Authority ”页面。根集与扩展集第三步计算扩展集 base 中所有页面的 Hub 值(枢纽度) 和 Authority 值(权威度) 1、分别表示网页结点 i 的 Authority 值(权威度)和 Hub 值(中心度)。 2、对于“扩展集 base ”来说,我们并不知道哪些页面是好的“ Hub ”或者好的“ Authority ”页面, 每个网页都有潜在的可能,所以对于每个页面都设立两个权值,分别来记载这个页面是好的 Hub 或者 Authority 页面的可能性。在初始情况下,在没有更多可利用信息前,每个页面的这两个权值都是相同的,可以都设置为1,即: ???? ihia,1,1 00??ha 3、每次迭代计算 Hub 权值和 Authority 权值网页 a (i) 在此轮迭代中的 Authority 权值即为所有指向网页 a (i) 页面的 Hub 权值之和: a (i) = Σ h (i) ; 网页 a (i) 的 Hub 分值即为所指向的页面的 Authority 权值之和: h (i) = Σ a (i) 。 4、对 a (i) 、 h (i) 进行规范化处理将所有网页的中心度都除以最高中心度以将其标准化: a (i) = a (i)/|a(i)| 将所有网页的权威度都除以最高权威度以将其标准化: h (i) = h (i)/ |h(i)| 5、如此不断的重复第 4): 上一轮迭代计算中的权值和本轮迭代之后权值的差异,如果发现总体来说权值没有明显变化,说明系统已进入稳定状态,则可以结束计算,即 a ( u),h(v) 收敛。算法描述: 代码如上图所示,给出了迭代计算过程中,某个页面的 Hub 权值和 Authority 权值的更新方式。假设以 A(i) 代表网页 i 的 Authority 权值,以 H(i) 代表网页 i的 Hub 权值。在图 6- 14 的例子中, “扩充网页集合”有3个网页有链接指向页面1,同时页面 1有3个链接指向其它页面。那么,网页 1在此轮迭代中的 Authority 权值即为所有指向网页 1页面的 Hub 权值之和;类似的,网页 1的 Hub 分值即为所指向的页面的 Authority 权值之和。 Hub 与 Authority 权值计算