Internet是一个巨大、分布广泛、全球性的信息服务中心，它提供了各种各样的信息服务。但如何从Internet浩如烟海的信息中获取所需信息或是从中提取有用知识，一直是相关专家探究的问题。将传统的数据挖掘技术和Web结合起来，对Web进行数据挖掘成为解决这一问题的重要途径。由于Web上的链接结构含有非常丰富和重要的信息，链接分析技术已经被成功地用于分析Web超链接数据来确定权威信息源。而在各种对网页进行链接分析并提取主题的算法中，HITS算法是最典型的。
1 HITS算法
1.1  HITS算法的基本思想
　　HITS 算法[1]是一种Web结构挖掘算法[1], 该算法基于用户的查询, 根据给定的查询通过分析Web的前向链接和后向链接来发现一组相关网页，从而找出Web集合中的authority网页(与给定查询主题的上下文最为相关并具有权威性的网页)和hub网页(提供指向权威网页链接集合的Web网页)。为每个网页定义两个度量值:权威权重(authority weight)和中心权重(Hub weight)，通过这两个权重来判定该网页对特定主题的重要性。
1.2  HITS算法的具体过程
　　整个HITS算法主要可以分为以下几个步骤:
　　(1)在搜索引擎上输入给定的关键词, 以此搜索到的最前面的r个等级最高的查询结果网页作为根集(root set)R，R需满足如下3个条件： ①R中网页数量相对较小.②R中网页大多数是与查询关键词q相关的网页。③R中网页包含较多的权威网页。
　　(2)通过向R中加入被R引用的网页和引用R的网页将R扩展成一个更大的基础集合(base set)B。扩展规则为：将根集中的全部网页加入进来, 并加入最多d个链接到根集R中的Web网页。
　　(3)以B中的Hub网页为顶点集V_l，以authority网页为顶点集V₂，V_l中的网页到V₂中的网页的超链接为边集E，形成一个二分有向图G＝(V₁，V₂，E)。对V1中的任一个顶点v，用h(v)表示网页v的hub值，对V₂中的顶点u，用a(u)表示网页的authority值。假设Web链接结构子图G中包含n个节点(网页)，对这n个节点加以编号：1，2，…，n，这样就可以为Web链接结构子图G定义一个n×n的邻接矩阵A，如果页面i指向页面j，则矩阵中的项(i, j)为1，否则为0。同样把所有节点的authority和hub值定义为向量形式，即：a=(a₁,a₂,...,a_n)和h=(h₁,h₂,...,h_n)。

　　根据线性代数的理论，向量a和h经过展开计算后，会收敛至对称矩阵A^TA和AA^T的主特征向量。A^TA的主特征向量代表权威网页，而其主特征向量中数值越高代表网页的权威权重也越高；同样，AAT的主特征向量代表中心网页，而其主特征向量中数值越高代表网页的中心权重也越高。通过以上过程可以看出，经过若干次迭代计算后, 即可得到每一页面的authority 和hub。基集B中网页的权威权重和中心权重从根本上说是由基集B中网页的链接关系所决定的，更具体地说，是由对称矩阵ATA和AAT所决定的。
2 HITS算法中存在的问题
　　HITS算法虽然在某些查询主题下能够较为准确地提取出权威网页, 但在一些场合中仍会使得算法发生严重的“主题漂移”[2]的现象( authorities集中到一些链接稠密的非相关网页的现象被称为“主题漂移”) 。该现象的出现说明在传统HITS算法中仍存在一些缺点, 这就要求对传统HITS算法进行改进, 以使其具有更为广泛的适用性, 提高权威页面搜索的效率。
3 HITS算法的改进
　　HITS算法遇到的问题，多是因为HITS是纯粹的基于链接分析的算法，没有考虑文本内容。继KLIINBERG J提出HITS算法以后，很多研究者对HITS进行了改进，提出了许多HITS的变种算法，主要有IBM Almaden研究中心Clever搜索引擎的ARC(Automatic Resource Compilation)算法[4]和由GEVREY J和RUGER S于2002年提出来的两个基于超链接和内容的网页排序算法[5]：Average算法和Sim算法等。
　　针对HITS算法发生的“主题漂移”的现象，本文在链接分析的基础上引入了网页内容信息[3]的判断，提出了一种改进的HITS算法。
3.1  改进思想
　　HITS 算法中, 构造一个基本集R集, 然后通过基本集扩展到B集, 形成整个Web 子图。这样做的原因是R集可能并不包含真正的用户需要的页面。例如搜索关键词“搜索引擎”时, 文本搜索引擎返回的页面通常不会包含Google、Yahoo等搜索引擎的页面, 因为它们的页面通常不会出现搜索引擎这样的字眼。这使得原本很重要的页面不能被包含在第一步得到的结果中。B集可以解决这个问题, 因为可以通过R集中网页的链接来得到需要的网页。但是也正是由于HITS 算法的这种特性使得它在构造B集时, 常常会引入过多与主题无关的页面, 它们有些还由于拥有互相指向的链接而拥有较高的权威值。如果控制B集构造时的半径, 可能得不到足够的页面,B集半径足够大可能会找到真正的合适页面, 但是这时也已经引入了过多的无关页面。
　　针对此，本文在链接分析的基础上引入网页内容信息[2]的判断，通过计算B集中每一网页与主题的相似度，设定阈值去掉相似度较低的页面，然后将网页的相似度用于最终的迭代计算，有效地去除“主题漂移”现象。
　　改进算法采用的模型和技术与当前Web检索系统大多采用的向量空间模型(VSM)和技术有最大的兼容性，以便算法的有效实现以及与当前检索系统的有效集成。改进后的算法主要包括3个过程：(1)有效地选取基集；(2)扩展基集时通过余弦公式对网页内容信息进行判断，使扩展后的网页与查询主题有最大的相关性，从而避免“主题漂移”；(3)迭代计算与返回结果[4-8]。
3.2  算法详细步骤
　　(1)合理地获取基集，构造链接结构子图G，对于图G中的每一个节点V(网页)有两个值, 分别是hub值与authority 值, 用H(v),A(V)表示, 把所有节点的authority和hub值定义为向量形式，即：a=(a₁,a₂,...,a_n)和h=(h₁,h₂,...,h_n)V=1,2,3..N;N为G中节点(网页)数量。
　　(2)对H(v),A(v)进行初始化, 使得H(v) = 1，A(v) = 1。
　　(3)内容匹配：将B集中扩展得到的网页看做一篇文档，把文档d和查询式q表示成向量形式(d =(d 1,d2…dn)di代表第i篇文档q=(q₁,q₂…q_n)q_i代表查询主题中第i个关键词)。文档d(document)可看成是由相互独立的若干词条(term) ( t₁,t₂...t_n)组成,对于每一词条t_i,根据词条在文档中隐含的语义及重要程度赋以一定的权值W_ti , 则文档的特征向量为(W_t1,W_t2...W_tn), 通过Similarity(d_i,Q) 余弦公式来表示第i篇文档与查询条件Q的相关度。

　　并以此作为权重赋予相应的节点(网页)，Web节点的内容与查询主题相关度越大，对应的权值也越大。这样，链接结构图就成了节点带权的有向图，使用这样的权重来合理控制链接分析时节点对authority/hub值的影响，最终有效控制主题偏移现象。

4  实验结果与分析
　　在测试文档集的选择上，选用BORODIN A等人提供的Web文档集[9](包括“Abortion”、 “Genetic”、 “Movies”、“Harvard”等关键词依次对应的2 849，2 613，5 613,1 583个网页)对改进的HITS算法和原HITS算法进行了实验比较，实验数据如表1所示。

　　通过实验数据，对搜索出来的前30位的网页进行相关率比较如图1所示。在前30位网页中发现原HITS算法将许多与查询主题无关的网页排了进来，使得网页相关率较低；而改进后的HITS算法排在前30内的网页相关率明显高于原HITS算法。

　　再对获取网页的前10位进行权威度比较(这里网页权威度是根据大多数人的评价得来的)，发现原HITS算法由于获取相关网页的准确率不高，使得获取权威网页的总体效果也不佳，而改进后的HITS算法明显优于原HITS算法，如图2所示。

　　以上结果说明，在原HITS算法中出现了TKC问题，排序较高的相关页面中存在与查询主题无关的网页，而改进的算法则有效地控制了TKC问题，通过加入对文本内容的分析使排序权值较高的页面与查询主题紧密相关。
　　文章在深入研究了Web挖掘和Web链接结构分析的基础上，重点分析了主题提取算法HITS的基本思想和算法步骤。针对HITS算法基于纯链接，容易发生“主题偏移”现象，本文从网页文本内容着手，提出一种将网页文本内容和链接结构相结合的改进HITS算法，并通过实验结果证明了改进后算法的有效性。
参考文献
[1] 王晓宇,周傲英.万维网的链接结构分析及其应用综述[J].软件学报, 2003, 14( 10) : 1768-1780.
[2] 倪现军. 结构挖掘中web有向图模型的改进算法[J].微计算机信息,2007,12-3:163-165.
[3] 黄丽雯, 钱微. 多文档文本摘要的一种改进HITS算法[J].计算机应用,2006,26(11):2625-2627.
[4]  CHAKRABARTI S,DOM B,RAGHAVAN P,et al.Automatic resource compilation by analyzing hyperlink structure and associated text[J].Computer Networks and ISDN Systems,1998,30(4):1-7.
[5]  GEVREY J,RUGER S.Link-based approaches for text retrieval.Proceedings of TREC-10,NIST(Gaithersburg,MD,13-16Nov2001)[M].NIST Special Publication,2002.
[6] XINGW , GHORBANIA. Weighted pagerank algorithm[C].Proceedings of the Second Conference on Communication Networks and Services Research, 2004: 305- 314.
[7]  KOSALA R, BLOCKEEL H. Web mining research: A Survey. ACMSIGKDD, 2000(07).
[8]  MIZUUCHI Y. Finding Context Paths for web pages[J]. InProc. of ACM Hypertext, 1999,2(2)：13-22.
[9]  BORODIN A, ROBERTS G O, Rosenthal J S, etal.Finding authorities and hubs form link structures on the World Wide Web[C].In Web,Hong Kong,China,May 2001.