百筑吧-网站优化_搜索引擎关键词快速排名软件! www.baizhu8.com

积分充值收藏本站

1、关键词快速排名,灰色词违规行业勿扰
2、优化选择:整站优化,单词优化两种模式可选
3、优化步骤:注册账户,充值,添加关键词
4、数据查看:登录账户,查看关键词排名数据
5、扣费情况:关键词优化按天扣费,单天不达标不收费
当前位置:首页 > 算法规范

HITS算法及其变种

admin 算法规范 2021-01-14 10:12:00 0

  PageRank算法中对于向外链接的权值贡献是平均的,也就是不考虑不同链接的重要性。而WEB的链接具有以下特征:

  1.有些链接具有注释性,也有些链接是起导航或广告作用。有注释性的链接才用于权威判断。

  2.基于商业或竞争因素考虑,很少有WEB网页指向其竞争领域的权威网页。

  3.权威网页很少具有显式的描述,比如Google主页不会明确给出WEB搜索引擎之类的描述信息。

  可见平均的分布权值不符合链接的实际情况。J. Kleinberg提出的HITS算法中引入了另外一种网页,称为Hub网页,Hub网页是提供指向权威网页链接集合的WEB网页,它本身可能并不重要,或者说没有几个网页指向它,但是Hub网页确提供了指向就某个主题而言最为重要的站点的链接集合,比一个课程主页上的推荐参考文献列表。一般来说,好的Hub网页指向许多好的权威网页;好的权威网页是有许多好的Hub网页指向的WEB网页。这种Hub与Authoritive网页之间的相互加强关系,可用于权威网页的发现和WEB结构和资源的自动发现,这就是Hub/Authority方法的基本思想。

HITS算法及其变种

一:HITS算法

  HITS(Hyperlink-Induced Topic Search)算法是利用Hub/Authority方法的搜索方法,算法如下:将查询q提交给传统的基于关键字匹配的搜索引擎.搜索引擎返回很多网页,从中取前n个网页作为根集(root set),用S表示。S满足如下3个条件:

  1.S中网页数量相对较小

  2.S中网页大多数是与查询q相关的网页

  3.S中网页包含较多的权威网页。

  通过向S中加入被S引用的网页和引用S的网页将S扩展成一个更大的集合T.

  以T中的Hub网页为顶点集Vl,以权威网页为顶点集V2,Vl中的网页到V2中的网页的超链接为边集E,形成一个二分有向图SG=(V1,V2,E)。对V1中的任一个顶点v,用h(v)表示网页v的Hub值,对V2中的顶点u,用a(u)表示网页的Authority值。开始时h(v)=a(u)=1,对u执行I操作修改它的a(u),对v执行O操作修改它的h(v),然后规范化a(u),h(v),如此不断的重复计算下面的操作I,O,直到a(u),h(v)收敛。(证明此算法收敛可见 )

  I 操作: (1) O操作: (2)

  每次迭代后需要对a(u),h(v)进行规范化处理:

  式(1)反映了若一个网页由很多好的Hub指向,则其权威值会相应增加(即权威值增加为所有指向它的网页的现有Hub值之和)。式(2)反映了若一个网页指向许多好的权威页,则Hub值也会相应增加(即Hub值增加为该网页链接的所有网页的权威值之和)。

  和PageRank算法一样,可以用矩阵形式来描述算法,这里省略不写。

  HITS算法输出一组具有较大Hub值的网页和具有较大权威值的网页。

二:HITS的问题

  HITS算法有以下几个问题:

  1.实际应用中,由S生成T的时间开销是很昂贵的,需要下载和分析S中每个网页包含的所有链接,并且排除重复的链接。一般T比S大很多,由T生成有向图也很耗时。需要分别计算网页的A/H值,计算量比PageRank算法大。

  2.有些时候,一主机A上的很多文档可能指向另外一台主机B上的某个文档,这就增加了A上文档的Hub值和B上文档的Authority,相反的情况也如此。HITS是假定某一文档的权威值是由不同的单个组织或者个人决定的,上述情况影响了A和B上文档的Hub和Authority值。

  3.网页中一些无关的链接影响A,H值的计算。在制作网页的时候,有些开发工具会自动的在网页上加入一些链接,这些链接大多是与查询主题无关的。同一个站点内的链接目的是为用户提供导航帮助,也与查询主题不甚无关,还有一些商业广告,赞助商和用于友情交换的链接,也会降低HITS算法的精度。

  4.HITS算法只计算主特征向量,也就是只能发现T集合中的主社区(Community),忽略了其它重要的社区。事实上,其它社区可能也非常重要。

  5.HITS算法最大的弱点是处理不好主题漂移问题(topic drift),也就是紧密链接TKC(Tightly-Knit Community Effect)现象。如果在集合T中有少数与查询主题无关的网页,但是他们是紧密链接的,HITS算法的结果可能就是这些网页,因为HITS只能发现主社区,从而偏离了原来的查询主题。下面讨论的SALSA算法中解决了TKC问题。

  6.用HITS进行窄主题查询时,可能产生主题泛化问题,即扩展以后引入了比原来主题更重要的新的主题,新的主题可能与原始查询无关。泛化的原因是因为网页中包含不同主题的向外链接,而且新主题的链接具有更加的重要性。

三:HITS的变种

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

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

  对于上述提到的HITS遇到的第2个问题,Monika R. Henzinger和Krishna Bharat在中进行了改进。假定主机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。I,O操作改为如下

  I 操作:

  O操作:

  调整后的算法有效的解决了问题2,称之为imp算法。

  在这基础上,Monika R. Henzinger和Krishna Bharat还引入了传统信息检索的内容分析技术来解决4和5,实际上也同时解决了问题3。具体方法如下,提取根集S中的每个文档的前1000个词语,串连起来作为查询主题Q,文档Dj和主题Q的相似度按如下公式计算:

  , , =项i在查询Q中的出现次数,

  =项i在文档Dj中的出现次数,IDFi是WWW上包含项i的文档数目的估计值。

  在S扩展到T后,计算每个文档的主题相似度,根据不同的阈值(threshold)进行刷选,可以选择所有文档相似度的中值,根集文档相似度的中值,最大文档相似度的分数,如1/10,作为阈值。根据不同阈值进行处理,删除不满足条件的文档,再运行imp算法计算文档的A/H值,这些算法分别称为med,startmed,maxby10。

  在此改进的算法中,计算文档的相似度时间开销会很大。

五: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次就可以,所以ARC算法有很高的计算效率,开销主要是在扩展根集上。

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

  Allan Borodin等在指出了一种现象,设有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等在中同时提出了3种阈值控制的算法,分别是Hub阈值算法,Authority阈值算法,以及结合2者的全阈值算法。

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

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

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

版权声明
上一篇:SALSA算法
下一篇:返回列表