HITS算法概述

基于HITS算法的搜索引擎概述摘要：本文简要介绍了目前搜索引擎中应用较为广泛的一种算法——HITS算法。HITS算法是Web结构挖掘中最具有权威性和使用最广泛的算法。其基本思想是利用页面之间的引用链来挖掘隐含在其中的有用信息（如权威性），具有计算简单且效率高的特点。HITS算法通过两个评价权值——内容权威度（Authority）和链接权威度（Hub）来对网页质量进行评估。HITS算法认为对每一个网页应该将其内容权威度和链接权威度分开来考虑，在对网页内容权威度做出评价的基础上再对页面的链接权威度进行评价，然后给出该页面的综合评价。它专注于改善泛指主题检索的结果，通过一定的计算(迭代计算)方法以得到针对某个检索提问的最具价值的网页，即排名最高的authority。关键词：搜索引擎；HITS算法；权威度；网页排名引言：随着因特网的迅猛发展,搜索引擎的应用已经非常普及。然而,人们对搜索引擎的核心技术———算法设计知之并不多。了解搜索引擎的算法设计思想及原理,有助于提高我们的信息检索能力,评价搜索引擎。更为重要的是,我国在信息技术领域内的发展情况与发达国家相比还有相当的差距,只有真正掌握了搜索引擎的核心技术,才可能开发出属于我们自己功能强大的搜索引擎,以使我们在当今的信息社会中立于不败之地。国内目前对搜索引擎排序算法的介绍较少,从已有的文献来看,多集中于对更具影响力的PageRank算法的介绍和分析研究,而对全球已有较大影响的HITS算法和SALSA算法介绍较少。本文中所重点说明的HITS算法是由康奈尔大学(CornellUniversity)的JonKleinberg博士于1998年首先提出的,HITS的英文全称为Hypertext-InducedTopicSearch。目前,它为IBM公司阿尔马登研究中心(IBMAlmadenResearchCenter)的名为“CLEVER”的研究项目中的一部分。一、搜索引擎搜索引擎为用户提供信息检索服务，作为辅助人们检索信息的工具，是在Web上发现信息的关键技术，是用户访问万维网的最佳入口。它借助于自动搜索网页的软件，在网络上通过各种链接获得大页面文档的信息，并按照一定算法与规则进行归类整理，形成文档索引数据库，以备用户查询。1）搜索引擎的工作原理搜索引擎有两个重要组成部分，即离线部分和在线部分。离线部分由搜索引擎定期执行，包括下载网站的页面集合，并经处理把这些页面转换成可搜索的索引。在线部分在用户查询时被执行，根据与用户需求的相关性，利用索引去选择候选文档并排序显示。搜索引擎原理－三段式工作流程2）搜索引擎算法获得网站网页资料，建立数据库并提供查询的系统，我们都可以把它叫做搜索引擎。搜索引擎的数据库是依靠一个叫“网络机器人（Spider）”或叫“网络蜘蛛（crawlers）”的软件，通过网络上的各种链接自动获取大量网页信息内容，并按一定的规则分析整理形成的。Google、百度都是比较典型的搜索引擎系统。为了更好的服务网络搜索，搜索引擎的分析整理规则---既搜索引擎算法是变化的。3）搜索引擎排名算法分类在各种搜索引擎上进行同样搜索时会产生不同的结果。究其原因，首先，检索依赖于网络蜘蛛能找到的信息。其次，并非搜索引擎都使用相同的排名算法。排名算法趋势：以Yahoo为代表的第一代文本搜索算法；雅虎的人工分类方式，网站目录搜索第二代以PageRank和HITS为代表的基于链接分析的搜索算法；第二代半基于网站的访问量。第三代应该具有智能化、个性化和社区化等特征。二、HITS算法HITS(Hyperlink-InducedTopicSearch)是由Kleinberg在90年代末提出的基于链接分析的网页排名算法。描述两种类型的网页：“权威型（Authority）网页”：对于一个特定的检索，该网页提供最好的相关信息；“目录型（Hub）网页”：该网页提供很多指向其它高质量权威型网页的超链。由此，我们可以在每个网页上定义“目录型权值”和“权威型权值”两个参数。1）Hits算法的基本思想1.好的Hub型网页指向好的Authority网页2.好的Authority网页是由好的Hub型网页所指向的网页。2）Hits算法HITS(Hyperlink-InducedTopicSearch)算法是利用HubPAuthority的搜索方法,具体算法如下:将查询q提交给基于关键字查询的检索系统，从返回结果页面的集合总取前n个网页（如n=200），作为根集合(rootset)，记为S，则S满足：1.S中的网页数量较少2.S中的网页是与查询q相关的网页3.S中的网页包含较多的权威（Authority）网页通过向S中加入被S引用的网页和引用S的网页,将S扩展成一个更大的集合T.以T中的Hub网页为顶点集V1,以权威网页为顶点集V2。V1中的网页到V2中的网页的超链接为边集E,形成一个二分有向图.对V1中的任一个顶点v,用h(v)表示网页v的Hub值,且h(v)收敛;对V2中的顶点u,用a(u)表示网页的Authority值。开始时h(v)=a(u)=1,对u执行I操作,修改它的a(u),对v执行O操作,修改它的h(v),然后规范化a(u)Ph(v),如此不断的重复计算下面的I操作和O操作,直到a(u)。其中I操作:a(u)=Σh(v);O操作:h(v)=Σa(u)。每次迭代对a(u)、h(v)进行规范化处理:a(u)=a(u)PΣ[a(q)]2;h(v)=h(v)PΣ[h(q)]2。HITS算法可以获得比较好的查全率,输出一组具有较大Hub值的网页和具有较大权威值的网页.但在实际应用中,HITS算法有以下几个问题:由S生成T的时间开销是很昂贵的,由T生成有向图也很耗时,需要分别计算网页的APH值,计算量大;网页中广告等无关链接影响A、H值的计算,降低HITS算法的精度;HITS算法只计算主特征向量,处理不好主题漂移问题;进行窄主题查询时,可能产生主题泛化问题。相关分析算法大体可以分为4类:基于随机漫游模型的算法,比如PageRank,Repution算法;基于Hub和Authority相互加强模型的算法,如HITS及其变种;基于概率模型的算法,如SALSA,PHITS;基于贝叶斯模型的算法,如贝叶斯算法.所有的算法在实际应用中都结合传统的内容分析技术进行优化。AllanBorodin也指出没有一种算法是完美的,在某些查询下,结果可能很好,在另外的查询下,结果可能很差.将S扩展为基本集合(baseset)T，T包含由S指出或指向S的网页。可以设定一个上限如1000—5000个网页。开始权重传播。在集合T中计算每个网页的目录型权值和权威型权值。Clever的做法是采用目录型网页和权威型网页相互评价的办法进行递归计算。对于一个网页p，用xp来表示网页p的权威型权值，用yp来表示它的目录型权值，并且用如下公式进行计算：1.计算各节点的Hub和Authority：2.赋予每个节点的hub值和authority值都为1。3.运行Authority更新规则。4.运行Hub更新规则。5.Normalize数值，即每个节点的Hub值除所有Hub值之和，每个Authority值除所有Authority值之和。6.必要时从第二步开始重复。三、HITS与PageRank的区别PageRank和HITS的迭代算法都利用了特征向量作为理论基础和收敛性依据。这也是超链接环境下此类算法的一个共同特征。但两种算法也有着明显的不同点，下面着重阐述两种算法的不同点。从两者的权值传播类型来看，PageRank算法基于随机冲浪(RandomSurfer)模型，将网页权值直接从authority网页传递到authority网页；而HITS算法则是将authority网页的权值经过hub网页的传递进行传播。从算法思想上看，虽然均同为链接分析算法，但二者之间还是有一定的区别。HITs的原理如前所述，其authority值只是相对于某个检索主题的权重，因此HITS算法也常被称为query—dependent算法。而PageRank算法独立于检索主题，因此也常被称为query—independent算法。PageRank的发明者(PageBrin)把引文分析思想借鉴到网络文档重要性的计算中来，利用网络自身的超链接结构给所有的网页确定一个重要性的等级数。当然PageRank并不是引文分析的完全翻版，根据因特网自身的性质等，它不仅考虑网页引用数量，还特别考虑了网页本身的重要性。从处理的数据量及用户端等待时间来分析。表面上看，HITS算法对需排序的网页数量需求较小，所计算的网页数量一般为1000至5000个，但由于需要从基于内容分析的搜索引擎中提取根集并扩充基本集，这个过程需要耗费相当的时间，而PageRank算法表面上看，处理的数据数量上远远超过了HITS算法。从两者的处理对象来看，都是针对整个万维网上的网页的一个子集进行排序、筛选，没有一个搜索引擎能够将万维网上的网页全部搜索下来。但是，PageRank算法的处理对象是一个搜索引擎上当前搜索下来的所有网页，一般在几千万个页面以上；而HITS的处理对象是搜索引擎针对具体查询主题所返回的结果，从几百个页面扩展到几千几万个页面。从两者的具体应用来看，PageRank算法应用于搜索引擎服务端，可以直接用于标题查询并获得较好的结果，若要用于全文本查询，需要与其它相似度判定标准(向量模型等)进行复合，以针对具体查询形成最终排名，搜索机器人(Crawler)可以将PageRank作为搜索优先次序的标准，算法中E的取值可以用来定制个人搜索引擎；HITS算法一般用于全文本搜索引擎的客户端l1，对于宽主题的搜索相当有效，可以用于自动编撰万维网分类目录，通过找到指向某网页的Hub网页并以此为根集R，查找该网页的相关网页，也可以用于元搜索引擎的网页排序。参考文献：西北大学可视化研究所常庆、周明全、耿国华《基于PageRank和HITS的Web搜索》苏州大学范聪贤、徐汀荣、范强贤《Web结构挖掘中HITS算法改进的研究》第三军医大学图书馆何晓阳、吴强、吴治蓉《HITS算法与PageRank算法比较分析》