现在的位置: 首页 > 综合 > 正文

搜索引擎算法研究专题二:HITS算法及其衍生算法分析

2017年12月19日 ⁄ 综合 ⁄ 共 3038字 ⁄ 字号 评论关闭

一个网页的重要性分析的算法,是根据一个网页的入度(指向此网页的超链接)和出度(从此网页指向别的网页)来衡量网页的重要性。其最直观的意义是如果一个网页的重要性很高,则他所指向的网页的重要性也高。一个重要的网页被另一个网页所指,则表明指向它的网页重要性也会高。指向别的网页定义为Hub值,被指向定义为Authority值。

  通常HITS算法是作用在一定范围的,比如一个以程序开发为主题网页,指向另一个以程序开发为主题的网页,则另一个网页的重要性就可能比较高,但是指向另一个购物类的网页则不一定。

  在限定范围之后根据网页的出度和入度建立一个矩阵,通过矩阵的迭代运算和定义收敛的阈值不断对两个向量Authority和Hub值进行更新直至收敛。HITS算法也可推广至别的类似的排序系统。

  HITS的变种

  HITS算法遇到的问题,大多是因为HITS是纯粹的基于链接分析的算法,没有考虑文本内容,继J. Kleinberg提出HITS算法以后,很多研究者对HITS进行了改进,提出了许多HITS的变种算法,主要有:

  Monika R. Henzinger和Krishna Bharat对HITS的改进

  对于上述提到的HITS遇到的第2个问题,Monika R. Henzinger和Krishna Bharat在[7]中进行了改进。假定主机A上有k个网页指向主机B上的某个文档d,则A上的k个文档对B的Authority贡献值总共为1,每个文档贡献1/k,而不是HITS中的每个文档贡献1,总共贡献k。类似的,对于Hub值,假定主机A上某个文档t指向主机B上的m个文档,则B上m个文档对 t的Hub值总共贡献1,每个文档贡献1/m。

  ARC算法

  IBM Almaden研究中心的Clever工程组提出了ARC(Automatic Resource Compilation)算法,对原始的HITS做了改进,赋予网页集对应的连结矩阵初值时结合了链接的锚(anchor)文本,适应了不同的链接具有不同的权值的情况。

  ARC算法与HITS的不同主要有以下3点:

  1.由根集S扩展为T时,HITS只扩展与根集中网页链接路径长度为1的网页,也就是只扩展直接与S相邻的网页,而ARC中把扩展的链接长度增加到2,扩展后的网页集称为增集(Augment Set)。

  2.HITS算法中,每个链接对应的矩阵值设为1,实际上每个链接的重要性是不同的,ARC算法考虑了链接周围的文本来确定链接的重要性。考虑链接p->q,p中有若干链接标记,文本1锚文本文本2,设查询项t在文本1,锚文本,文本2,出现的次数为n(t),则w(p,q)=1+n(t)。文本1和文本2的长度经过试验设为50字节[10]。构造矩阵W,如果有网页i->j ,Wi,j=w(i,j),否则Wi,j=0,H值设为1,Z为W的转置矩阵,迭代执行下面3个的操作:

  (1)A=WH (2)H=ZA (3)规范化A,H

  3.ARC算法的目标是找到前15个最重要的网页,只需要A/H的前15个值相对大小保持稳定即可,不需要A/H整个收敛,这样2中迭代次数很小就能满足,[10]中指出迭代5次

  Hub平均( Hub-Averaging-Kleinberg)算法

  Allan Borodin等在[11]指出了一种现象,设有M+1个Hub网页,M+1个权威网页,前M个Hub指向第一个权威网页,第M+1个Hub网页指向了所有M+1个权威网页。显然根据HITS算法,第一个权威网页最重要,有最高的Authority值,这是我们希望的。但是,根据HITS,第M+1个 Hub网页有最高的Hub值,事实上,第M+1个Hub网页既指向了权威值很高的第一个权威网页,同时也指向了其它权威值不高的网页,它的Hub值不应该比前M个网页的Hub值高。因此,Allan Borodin修改了HITS的O操作:

  O操作: ,n是(v,u)的个数

  调整以后,仅指向权威值高的网页的Hub值比既指向权威值高又指向权威值低的网页的Hub值高,此算法称为Hub平均(Hub-Averaging-Kleinberg)算法。

  ARC算法

  IBM Almaden研究中心的Clever工程组提出了ARC(Automatic Resource Compilation)算法,对原始的HITS做了改进,赋予网页集对应的连结矩阵初值时结合了链接的锚(anchor)文本,适应了不同的链接具有不同的权值的情况。

  ARC算法与HITS的不同主要有以下3点:

  1.由根集S扩展为T时,HITS只扩展与根集中网页链接路径长度为1的网页,也就是只扩展直接与S相邻的网页,而ARC中把扩展的链接长度增加到2,扩展后的网页集称为增集(Augment Set)。

  2.HITS算法中,每个链接对应的矩阵值设为1,实际上每个链接的重要性是不同的,ARC算法考虑了链接周围的文本来确定链接的重要性。考虑链接p->q,p中有若干链接标记,文本1锚文本文本2,设查询项t在文本1,锚文本,文本2,出现的次数为n(t),则w(p,q)=1+n(t)。文本1和文本2的长度经过试验设为50字节[10]。构造矩阵W,如果有网页i->j ,Wi,j=w(i,j),否则Wi,j=0,H值设为1,Z为W的转置矩阵,迭代执行下面3个的操作:

  (1)A=WH (2)H=ZA (3)规范化A,H3.ARC算法的目标是找到前15个最重要的网页,只需要A/H的前15个值相对大小保持稳定即可,不需要A/H整个收敛,这样2中迭代次数很小就能满足,[10]中指出迭代5次就可以,所以ARC算法有很高的计算效率,开销主要是在扩展根集上。

  Hub平均( Hub-Averaging-Kleinberg)算法

  Allan Borodin等在[11]指出了一种现象,设有M+1个Hub网页,M+1个权威网页,前M个Hub指向第一个权威网页,第M+1个Hub网页指向了所有M+1个权威网页。显然根据HITS算法,第一个权威网页最重要,有最高的Authority值,这是我们希望的。但是,根据HITS,第M+1个 Hub网页有最高的Hub值,事实上,第M+1个Hub网页既指向了权威值很高的第一个权威网页,同时也指向了其它权威值不高的网页,它的Hub值不应该比前M个网页的Hub值高。因此,Allan Borodin修改了HITS的O操作:

  O操作: ,n是(v,u)的个数 调整以后,仅指向权威值高的网页的Hub值比既指向权威值高又指向权威值低的网页的Hub值高,此算法称为Hub平均(Hub-Averaging-Kleinberg)算法。

  阈值(Threshhold—Kleinberg)算法

  Allan Borodin等在[11]中同时提出了3种阈值控制的算法,分别是Hub阈值算法,Authority阈值算法,以及结合2者的全阈值算法。

  计算网页p的Authority时候,不考虑指向它的所有网页Hub值对它的贡献,只考虑Hub值超过平均值的网页的贡献,这就是Hub阈值方法。

  Authority阈值算法和Hub阈值方法类似,不考虑所有p指向的网页的Authority对p的Hub值贡献,只计算前K个权威网页对它Hub值的贡献,这是基于算法的目标是查找最重要的K个权威网页的前提。

  同时使用Authority阈值算法和Hub阈值方法的算法,就是全阈值算法。

抱歉!评论已关闭.