网页结构挖掘算法研究论文

摘要Web页面包含了丰富的、动态的超链信息，挖掘超链及其周围的文档可以帮助用户找到感兴趣的、权威的内容。主要论述了基于超链的Web结构挖掘的方法，并对Web结构挖掘的一般方法HITS算法进行改进。采用这种改进算法，可以从任意页面集中计算出具有最大Authority权值和Hub权值的页面。从而把一个可信度的、权威的网站推荐给用户。

关键词网页结构超链挖掘算法

1数据挖掘

Web作为目前Internet的主要信息渠道，包含了丰富的、动态的超链接信息，这为数据挖掘提供了丰富的资源。现有的知识发现(KDD)的方法和技术已不能满足人们从Web中获取知识的需要。许多时候人们苦于在巨大的网络世界中不容易找到自己感兴趣的、权威的内容。所以人们迫切需要找到这样的工具，能够从WEB上快速地、有效地发现资源，发现隐含的规律性的内容，提高在WEB上检索信息、利用信息的效率。数据挖掘便应运而生。数据挖掘通常有内容挖掘、使用挖掘和结构挖掘三种类型。本文主要研究结构挖掘。Web结构挖掘是指通过分析不同网页之间的超链结构，发现许多蕴涵在Web内容之外的对我们有潜在价值的模式和知识的过程。

2结构挖掘

WWW没有数据库那样严格统一的语义模式，但也不像平面文件那样完全没有结构，从信息结构的角度来看，WWW上的资源有三种类型：结构化资源、半结构化资源和无结构化资源，它的语义隐含在语法结构之中。忽略掉Web页面上的文本和其它内容，只考虑页面间的超链，WWW可以被看作是以Web页面为节点、页面之间超链为有向边所构成的网状结构的有向图，把Web看成是一个巨大的有向图G=(V,E)，结点v∈V代表一个Web页面，有向边(p,q)∈E代表从结点p指向结点q的超链接。结构挖掘就是要在这样的网络有向图中进行超链分析。通过分析超链可以获悉网站的受欢迎程度及与其它网站的关系，而且，通过网页之间的链接还能够快速了解一个网站的内部结构。WWW是一个超文本文档信息系统，而超链是表示信息的一个重要方式，所以挖掘超链的语义结构十分必要和有意义。

在WWW上网页内部的超链用HTML、XML表示成树形结构，文档表示成URL中的目录路径结构，站点之间通过超链同其它相关联的站点或页面相链接。相关主题的站点和页面之间一般都存在大量的链接，通过这种链接方式相聚集。但主题相同的所有站点或页面不一定会围绕一个中心(Hub)相聚集，也就是说一个主题会存在多个聚集中心。一个网站如果链接了许多权威网站，那么它就是一个中心网站(Hub)；如果一个网站被许多中心网站链接，那么它就是一个权威网站(Authority)，如图1、图2所示。很多网站管理和设计人员通常愿意链接可信度高的网站。因而一个网站的可信度可以根据它所链接的网站的权威程度来衡量,同时它会推荐给用户许多好的权威网站，对其它网站的权威性起到了一定程度的增强作用。

3Web结构挖掘的算法

利用超链进行挖掘的两个典型的算法是：PageRank算法及HITS算法。本文主要介绍HITS算法，并针对HITS算法的不足之处提出一种改进的方法。采用这种改进算法，可以从任意页面集中计算出具有最大Authority权值和Hub权值的页面。

3.1HITS算法

HITS(HyperlinkInducedTopicSearch)是Web结构挖掘的一个基本算法。此算法建立在下面几个定义之上：

①Hubs页，指的是一个指向权威页的超链接集合的Web页；

②Authorities页，指的是被许多Hubs页指向的权威的Web页；

③以及由这两个定义所衍生出来的一个Web页的Authority权重(由网页的out-link决定)和Hub权重(由网页的in-link决定)。

其算法步骤如下：

1)根据用户查询请求，首先用一个现有的商业搜索引擎进行查询，取其部分查询结果(约200个左右)作为算法的根集，记为Rδ.

2)将Rδ进行扩充，对Rδ中每一个结点，将所有指向该结点或该结点所指向的网页补充进来，形成基集，记为Sδ.

3)计算Sδ中每一个网页的Authority权重和Hub权重，这是一个递归过程.

先将网页p的Authority权重记为ap，Hub权重记为hp，为Sδ中所有网页赋初值：ap(0)←1，hp(0)←1；再通过以下迭代公式对ap和hp进行反复修正，直至结果收敛：

I操作：

O操作：

这里q←p的含义是存在一个由q指向p的超链接。

设且，a(t)、h(t)迭代的初始向量为[1,…,1]T,则a3、h3分别收敛为矩阵XTX、XXT主特征向量。因此，页面i的Authority权重为ai3，Hub权重为hi3。具有较大的a3和h3的页面就是Authorities页和Hubs页。

基于HITS算法的系统包括Clever、Google也基于同样的原理。这些系统由于纳入了Web链接和文本内容信息，查询效果明显优于基于词类索引引擎产生的结果，如AltaVista,和基于人工的本体论生成的结果，如Yahoo！。

3.2对HITS算法的改进

我们不难发现，HITS算法完全不考虑页面文本的内容，在实际应用中也出现了一定的问题，如主题漂移等。这主要是由于算法认为页面中的所有超链具有同等价值引起的，根据算法描述，只要两个页面之间存在超链，则邻接矩阵中对应的值即为1，这完全忽视了超链之间的差异，引起了算法结果的偏差。

通过引入页面文本的语义信息可以解决这个问题，已有不少研究者对算法进行改进，在一定程度上改善了这些偏差。在Clever系统中使用HITS算法，通过在超链的周围文字中匹配查询关键字并计算词频的方法来计算超链的权值，用计算出的权值来代替邻接矩阵中相应的值，从而达到引入语义信息的目的，取得了一定的效果。然而，网络上的页面形式十分复杂，很多时候超链周围文字无法代表链接页面的内容，甚至与链接页面的内容大相径庭。

基于HITS算法的这些不足之处本文提出了计算超链权值的解决方案。在页面的文本中，最能够代表链接页面语义信息的是超链文字(本文仅考虑以文本为载体的超链，对以图像、动画等为载体的超链暂时不作考虑)。超链文字是超链的载体，通常可以作为链接页面内容的标题，因而能够很好地反映链接页面的语义信息。本文通过引入加权系数α来控制超链周围文字在超链权值中所占的比例。

在计算超链权值时，需要将文本中的语义信息进行量化，这样才能够使语义信息这一概念具有可计算性。本文使用查询关键字在超链文字中出现的次数，即词频信息进行语义信息的量化。为了方便描述，定义从页面p指向页面q关于查询关键字k的超链权值为w(p,q,k)，这个数值随着查询关键字在超链文字和周围文字中出现数量的增多而增大；定义t(k)st(k)为查询关键字在周围文字中出现的次数，系数α用于控制周围文字的语义信息在超链权值中的比例，可用式(1)来计算权值w的值：

w(p,q,k)=1+t(k)+α*st(k)(1)

其中，系数α的值可以根据不同页面集进行调整。根据式(1)计算出的w值是大于1的，在迭代过程中得到的向量会不断增大。然而，本文所关心的只是它们之间的相对大小，而不是权值的绝对数值，因此，为了把结果向量的数值控制在一定范围内，可以在每次迭代后进行标准化。所有超链的权值计算完成后，就可以根据公式

x←ATy←ATAx←(ATA)x，y←Ax←AATy←(AAT)y(2)

进行迭代得到authority权值向量x和hub权值向量y。其中邻接矩阵A中每一项的值是这样定义的，如果存在超链从页面p指向页面q，则A中对应项的值为w(p,q,k)，否则对应项的值为0。经过n次迭代后，输出x向量中值最大的一组页面作为authority页面，y向量中值最大的一组页面作为hub页面，其中结果的数量可以根据具体的应用要求定制。迭代次数n的选择来自于矩阵特征向量的理论，经过足够数量的迭代，结果向量最终将收敛于矩阵ATA的特征向量。采用这种算法，可以从任意页面集中计算出具有最大authority权值和hub权值的页面。

本文在分析网络结构的基础上，介绍了结构挖掘中HITS算法模型，并针对其弱点提出了改进方案。对于HITS算法而言，还有其它的方式可以进一步改进它的精度。在今后的工作中，可以考虑根据这些思想进一步改进算法。

参考文献

[1]刘丽珍等.网络结构挖掘的关键分析.计算机应用研究,2003(5)116-118

[2]陈定权.Web结构挖掘研究.情报理论与实践,2003(1)59-61

[3]BharatK,HenzingerMR.ImprovedAlgorithmsforTopicDistillationinaHyperlinkedEnvironment.InProceedingsoftheACM-SIGIR,1998

[4]ChakrabartiS,DomB,GibsonD,etal.AutomaticResourceListCompilationbyAnalyzingHyperlinkStructureandAssociatedText.InProc.ofthe7thInt.WWWConference,1998-05