信息检索之HITS算法.doc

.页眉. .页脚. 一、实验目的?理解搜索引擎的链接结构子系统的基本功能; ?了解万维网链接的结构图及特性; ?理解 HITS 算法的基本思想和原理。二、实验原理及基本技术路线图(方框原理图) 万维网的链接结构通常使用有向图的方式来描述,在万维网链接结构图中,网页是图的节点; 而超链接则是链接节点的有向边(从源网页指向目的网页) 。每一条从源网页指向目的网页的超链接,既称为源网页的“出链接”,又称为目的网页的“入链接”。用图表示万维网链接结构,如下图: HB A FD E C G 关于万维网结构图的规模很难给出一个准确的统计结果,这是因为:图中的节点存在形式纷繁复杂,即使不考虑网页的可访问性问题(部分网页会对用户访问加以限制,如采取登录策略等), 只考虑能够被自由访问的网页,这些网页中既有以传统形式存在的静态页面,又有随用户查询要求在服务器端实时生成的动态页面,甚至还有用 AJAX 技术生成的 URL 相同但页面内容千差万别的页面。而超链接的界定在当前的网络环境下也存在诸多困难。 2008 年7 月,谷歌在其官方博客上声称其索引量达到 1万亿网页,这一估计一定程序上反映了图的节点集合规模。链接结构信息是网络信息环境与传统信息媒介的最大区别之一。对于搜索引擎而言,与用户查询需求乃至页面内容均相对独立的超链接结构是用以评价万维网数据质量的重要依据。在 2001 年 SIGIR 会议上, Craswell 等人对链接结构分析算法的应用方式进行了分析,. .页脚. 万维网超链接应具有的两个特性: 如果存在超链接 L从页面 P source 指向页面 P destiny ,则 P source 与P destiny 满足: 特性 1:( 内容推荐特性)页面 P source 的作者推荐页面 P destiny 的内容,且利用 L 的链接文本内容对 P destiny 进行描述。特性 2:( 主题相关特性) 被超链接连接的两个页面 P source 与 P destiny 的页面内容涉及类似的主题。然而这两个特性对于万维网数据爆炸性增长的背景下被认为过于理想主义。万维网节点之间的超链接关系远比特性 1和特性 2描述的情况要复杂的多。但是,一方面,经过改进的链接分析算法还是可以为页面质量评估提供参考;另一方面,在经过数据清理之后的近似理想的网络环境中,它们还是可以发挥其挑选高质量网页的作用,因此链接分析算法仍旧是当前研究的热点之一。 HITS 算法是由 Jon Kleinberg 在 20 世纪 90 年代提出的一种链接分析算法。 HITS 算法是 Hyperlink-Induced Topic Search (基于超链接推演的主题搜索算法)的简称,它的核心思想是对网页如下两个方面的权威程度进行评价。首先,内容权威度( Authority Value ), 即网页本身内容的受欢迎程序;其次,链接权威度( Hub Value ),即网页链接到其他受欢迎资源的程度。 HITS 算法的实施包括两个阶段,对用户输入的查询主题而言,首先是通过文本搜索过程获取与此查询主题内容相关的网页集合,并适当扩充该网页集合,以包括尽可能多的结果候选网页, 同时使用结果集合网页间的链接结构关系更加完整;随后则是通过一个“迭代—收敛”的过程计算网页集合中每个页面对应的链接权威度和内