2.2.2HITS的问题
HITS算法有以下几个问题:
1.实际应用中,由S生成T的时间开销是很昂贵的,需要下载和分析S中每个网页包含的所有链接,并且排除重复的链接。一般T比S大很多,由T生成有向图也很耗时。需要分别计算网页的A/H值,计算量比PageRank算法大。
2.有些时候,一主机A上的很多文档可能指向另外一台主机B上的某个文档,这就增加了A上文档的Hub值和B上文档的Authority,相反的情况也如此。HITS是假定某一文档的权威值是由不同的单个组织或者个人决定的,上述情况影响了A和B上文档的Hub和Authority值[7]。
3.网页中一些无关的链接影响A,H值的计算。在制作网页的时候,有些开发工具会自动的在网页上加入一些链接,这些链接大多是与查询主题无关的。同一个站点内的链接目的是为用户提供导航帮助,也与查询主题不甚无关,还有一些商业广告,赞助商和用于友情交换的链接,也会降低HITS算法的精度[8]。
4.HITS算法只计算主特征向量,也就是只能发现T集合中的主社区(Community),忽略了其它重要的社区[12]。事实上,其它社区可能也非常重要。
5.HITS算法最大的弱点是处理不好主题漂移问题(topicdrift)[7,8],也就是紧密链接TKC(Tightly-KnitCommunityEffect)现象[8]。如果在集合T中有少数与查询主题无关的网页,但是他们是紧密链接的,HITS算法的结果可能就是这些网页,因为HITS只能发现主社区,从而偏离了原来的查询主题。下面讨论的SALSA算法中解决了TKC问题。
6.用HITS进行窄主题查询时,可能产生主题泛化问题[5,9],即扩展以后引入了比原来主题更重要的新的主题,新的主题可能与原始查询无关。泛化的原因是因为网页中包含不同主题的向外链接,而且新主题的链接具有更加的重要性。
2.2.3HITS的变种
HITS算法遇到的问题,大多是因为HITS是纯粹的基于链接分析的算法,没有考虑文本内容,继J.Kleinberg提出HITS算法以后,很多研究者对HITS进行了改进,提出了许多HITS的变种算法,主要有:
2.2.3.1MonikaR.Henzinger和KrishnaBharat对HITS的改进
对于上述提到的HITS遇到的第2个问题,MonikaR.Henzinger和KrishnaBharat在[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。I,O操作改为如下
I操作:
O操作:
调整后的算法有效的解决了问题2,称之为imp算法。
在这基础上,MonikaR.Henzinger和KrishnaBharat还引入了传统信息检索的内容分析技术来解决4和5,实际上也同时解决了问题3。具体方法如下,提取根集S中的每个文档的前1000个词语,串连起来作为查询主题Q,文档Dj和主题Q的相似度按如下公式计算:
,,=项i在查询Q中的出现次数,
=项i在文档Dj中的出现次数,IDFi是WWW上包含项i的文档数目的估计值。
在S扩展到T后,计算每个文档的主题相似度,根据不同的阈值(threshold)进行刷选,可以选择所有文档相似度的中值,根集文档相似度的中值,最大文档相似度的分数,如1/10,作为