< 链接分析算法 - HITS算法 >

< 链接分析算法 - HITS算法 >

背景

  • 1999年,Jon Kleinberg 提出了HITS算法。作为几乎是与PageRank同一时期被提出的算法,HITS同样以更精确的搜索为目的,并到今天仍然是一个优秀的算法。

  • HITS算法的全称是Hyperlink-Induced Topic Search超链接诱导主题搜索。在HITS算法中,每个页面被赋予两个属性:hub属性和authority属性。同时,网页被分为两种:hub页面和authority页面。hub是中心的意思,所以hub页面指那些包含了很多指向authority页面的链接的网页,比如国内的一些门户网站;authority页面则指那些包含有实质性内容的网页。HITS算法的目的是:当用户查询时,返回给用户高质量的authority页面。

  • 核心思想:
    • 一个高质量的authority页面会被很多高质量的hub页面所指向

    • 一个高质量的hub页面会指向很多高质量的authority页面。

HITS - 算法原理

  • 高质量定义:由hubauthority值确定
    • 页面hub值:$ h(u) = Σa(v) \(,\)u\(为待求页面,\)v$出链页面。

    • 页面authority值:$ a(u) = Σh(v) \(,\)u\(为待求页面,\)v$入链页面。

    • PageRank不同的是,HITS是在用户搜索后运行,只处理关键字相关页面,所以处理对象集合相比小得多。

  • 互联网有向图\(G=(V,E)\),用户搜索关键字设为\(\sigma\),所有包含关键字\(\simga\)页面集合\(Q _ {\sigma}\)。
    • 返回给用户的集合\(S _ {\sigma}\)需要满足的条件为:
      1. \(S _ {\sigma}\)确实足够小
      2. \(S _ {\sigma}\)包含很多与查询相关的页面
      3. \(S _ {\sigma}\)包含很多高质量的 authority页面
    • 我们首先取相关度排名最靠前的t(一般去200)个网页作为初始集合记为\(R _ {\sigma}\)。其能满足前两条件但不满足第三条件。

    • 一开始令\(S _ {\sigma}=R_ {\sigma}\)。然后将所有 \(R _ {\sigma}\)指向的网页加入\(S_ {\sigma}\),再把一定数量 指向 \(R _ {\sigma}\)集合中的网页(每个\(R_ {\sigma}\)最多添加 d个指向它的网页,一般设为50)加入\(S _ {\sigma}\)中。通常情况下拓展后集合大小为1000-5000

    • 之后对\(S _ {\sigma}\)进行处理:先把同一域名下的网页之间的链接全部删除(防止类似站内导航链接干扰),构成新集合\(G _ {\sigma}\)。然后对\(G _ {\sigma}\)集合计算 hub & authority值,初始化\(a(p)=h(p)=1\)。

    • 每一轮迭代后要进行标准化,使\(Σh(i)^{2}=Σa(i)^{2}=1\)。设置迭代次数上线或者阈值来控制迭代结束,最后返回给用户authority值靠前的网页即可。

  • HITS算法的缺点:
    • 计算效率低。因为要求实时计算,在用户提出搜索请求之后才开始运行的,然而计算出结果又需要多次迭代计算,所以就这点上来说HITS算法效率仍然较低。(但计算量相比较少)

    • 主题漂移(紧密链接社区现象)。在集合生成变动与拓展时容易添加进与搜索主题无关的网页。若是这部分网页中又恰恰有着一些高质量的authority页面,则很有可能返回给用户,降低用户的搜索体验。

    • 作弊网页。试想如果弄一个页面指向很多高质量的authority页面,那么这个页面就成为了一个高质量的hub页面。然后再弄个链接指向自己的搓网页,按照HITS算法,将大大提升自己的搓网页的authority值。

    • 稳定性差。对于一个网页集合,若是删除其中的某条链接,就有可能造成一些网页的hub值和authority值发生巨大变化。

  • PageRank相比两者都是是用来Random Walk思想(当前状态只依赖于前一个状态,与其他状态无关)。除了各自的优缺点外,HITSquery-dependentPageRankquery-independent
    • 因为HITS是输入一个查询的关键词,而后才根据关键词构造的网页集合,因此它的搜索结果是和查询内容有关系的。而PageRank是把所有的网页构成的集合当做是一个大的网络,PageRank是在初始化之后,一直迭代直到最后稳定,而他的结果只和网页之间的链接有关系。所以,对于一个没有采用和内容相关策略控制方法、纯用PageRank的算法做成的系统,无论你输入什么样的搜索内容,返回的结果都是一样的,都是排序结果的前面几个值。

HITS - 算法证明

HITS - 算法实现

上一篇:python操作elasticsearch


下一篇:新版本中的hits.total匹配数说明