基于网页结构挖掘算法研究

1、基于网页构造挖掘算法研究摘要eb页面包含了丰富的、动态的超链信息，挖掘超链及其周围的文档可以帮助用户找到感兴趣的、权威的内容。主要阐述了基于超链的eb构造挖掘的方法，并对eb构造挖掘的一般方法HITS算法进展改良。采用这种改良算法，可以从任意页面集中计算出具有最大Authrity权值和Hub权值的页面。从而把一个可信度的、权威的网站推荐给用户。关键词网页构造超链挖掘算法eb作为目前Internet的主要信息发布渠道，包含了丰富的、动态的超链接信息，这为数据挖掘提供了丰富的资源。现有的知识发现(KDD)的方法和技术已不能满足人们从eb中获取知识的需要。许多时候人们苦于在宏大的网络世界中不容易找到

2、自己感兴趣的、权威的内容。所以人们迫切需要找到这样的工具，可以从EB上快速地、有效地发现资源，发现隐含的规律性的内容，进步在EB上检索信息、利用信息的效率。数据挖掘便应运而生。数据挖掘通常有内容挖掘、使用挖掘和构造挖掘三种类型。本文主要研究构造挖掘。eb构造挖掘是指通过分析不同网页之间的超链构造，发现许多蕴涵在eb内容之外的对我们有潜在价值的形式和知识的过程。没有数据库那样严格统一的语义形式，但也不像平面文件那样完全没有构造，从信息构造的角度来看，上的资源有三种类型：构造化资源、半构造化资源和无构造化资源，它的语义隐含在语法构造之中。忽略掉eb页面上的文本和其它内容，只考虑页面间的超链，可以被

3、看作是以eb页面为节点、页面之间超链为有向边所构成的网状构造的有向图，把eb看成是一个宏大的有向图G=(V,E)，结点vV代表一个eb页面，有向边(p,q)E代表从结点p指向结点q的超链接。构造挖掘就是要在这样的网络有向图中进展超链分析。通过分析超链可以得悉网站的受欢送程度及与其它网站的关系，而且，通过网页之间的链接还可以快速理解一个网站的内部构造。是一个超文本文档信息系统，而超链是表示信息的一个重要方式，所以挖掘超链的语义构造非常必要和有意义。在上网页内部的超链用HTL、XL表示成树形构造，文档表示成URL中的目录途径构造，站点之间通过超链同其它相关联的站点或页面相链接。相关主题的站点和页面

4、之间一般都存在大量的链接，通过这种链接方式相聚集。但主题一样的所有站点或页面不一定会围绕一个中心(Hub)相聚集，也就是说一个主题会存在多个聚集中心。一个网站假如链接了许多权威网站，那么它就是一个中心网站(Hub)；假如一个网站被许多中心网站链接，那么它就是一个权威网站(Authrity)，如图1、图2所示。很多网站管理和设计人员通常愿意链接可信度高的网站。因此一个网站的可信度可以根据它所链接的网站的权威程度来衡量,同时它会推荐给用户许多好的权威网站，对其它网站的权威性起到了一定程度的增强作用。3eb构造挖掘的算法利用超链进展挖掘的两个典型的算法是：PageRank算法及HITS算法。本文主要

5、介绍HITS算法，并针对HITS算法的缺乏之处提出一种改良的方法。采用这种改良算法，可以从任意页面集中计算出具有最大Authrity权值和Hub权值的页面。3.1HITS算法HITS(HyperlinkInduedTpiSearh)是eb构造挖掘的一个根本算法。此算法建立在下面几个定义之上：Hubs页，指的是一个指向权威页的超链接集合的eb页；Authrities页，指的是被许多Hubs页指向的权威的eb页；以及由这两个定义所衍生出来的一个eb页的Authrity权重(由网页的ut-link决定)和Hub权重(由网页的in-link决定)。其算法步骤如下：1)根据用户查询恳求，首先用一个现有的

6、商业搜索引擎进展查询，取其局部查询结果(约200个左右)作为算法的根集，记为R.2)将R进展扩大，对R中每一个结点，将所有指向该结点或该结点所指向的网页补充进来，形成基集，记为S.3)计算S中每一个网页的Authrity权重和Hub权重，这是一个递归过程.先将网页p的Authrity权重记为ap，Hub权重记为hp，为S中所有网页赋初值：ap(0)1，hp(0)1；再通过以下迭代公式对ap和hp进展反复修正，直至结果收敛：I操作：操作：这里qp的含义是存在一个由q指向p的超链接。设且，a(t)、h(t)迭代的初始向量为1,1T,那么a3、h3分别收敛为矩阵XTX、XXT主特征向量。因此，页面i

7、的Authrity权重为ai3，Hub权重为hi3。具有较大的a3和h3的页面就是Authrities页和Hubs页。基于HITS算法的系统包括lever、Ggle也基于同样的原理。这些系统由于纳入了eb链接和文本内容信息，查询效果明显优于基于词类索引引擎产生的结果，如AltaVista,和基于人工的本体论生成的结果，如Yah3.2对HITS算法的改良我们不难发现，HITS算法完全不考虑页面文本的内容，在实际应用中也出现了一定的问题，如主题漂移等。这主要是由于算法认为页面中的所有超链具有同等价值引起的，根据算法描绘，只要两个页面之间存在超链，那么邻接矩阵中对应的值即为1，这完全无视了超链之间的

8、差异，引起了算法结果的偏向。通过引入页面文本的语义信息可以解决这个问题，已有不少研究者对算法进展改良，在一定程度上改善了这些偏向。在lever系统中使用HITS算法，通过在超链的周围文字中匹配查询关键字并计算词频的方法来计算超链的权值，用计算出的权值来代替邻接矩阵中相应的值，从而到达引入语义信息的目的，获得了一定的效果。然而，网络上的页面形式非常复杂，很多时候超链周围文字无法代表链接页面的内容，甚至与链接页面的内容大相径庭。基于HITS算法的这些缺乏之处本文提出了计算超链权值的解决方案。在页面的文本中，最可以代表链接页面语义信息的是超链文字(本文仅考虑以文本为载体的超链，对以图像、动画等为载体

9、的超链暂时不作考虑)。超链文字是超链的载体，通常可以作为链接页面内容的标题，因此可以很好地反映链接页面的语义信息。本文通过引入加权系数来控制超链周围文字在超链权值中所占的比例。在计算超链权值时，需要将文本中的语义信息进展量化，这样才可以使语义信息这一概念具有可计算性。本文使用查询关键字在超链文字中出现的次数，即词频信息进展语义信息的量化。为了方便描绘，定义从页面p指向页面q关于查询关键字k的超链权值为(p,q,k)，这个数值随着查询关键字在超链文字和周围文字中出现数量的增多而增大；定义t(k)st(k)为查询关键字在周围文字中出现的次数，系数用于控制周围文字的语义信息在超链权值中的比例，可用式

10、(1)来计算权值的值：(p,q,k)=1+t(k)+*st(k)(1)其中，系数的值可以根据不同页面集进展调整。根据式(1)计算出的值是大于1的，在迭代过程中得到的向量会不断增大。然而，本文所关心的只是它们之间的相对大小，而不是权值的绝对数值，因此，为了把结果向量的数值控制在一定范围内，可以在每次迭代后进展标准化。所有超链的权值计算完成后，就可以根据公式xATyATAx(ATA)x，yAxAATy(AAT)y(2)进展迭代得到authrity权值向量x和hub权值向量y。其中邻接矩阵A中每一项的值是这样定义的，假如存在超链从页面p指向页面q，那么A中对应项的值为(p,q,k)，否那么对应项的值

11、为0。经过n次迭代后，输出x向量中值最大的一组页面作为authrity页面，y向量中值最大的一组页面作为hub页面，其中结果的数量可以根据详细的应用要求定制。迭代次数n的选择来自于矩阵特征向量的理论，经过足够数量的迭代，结果向量最终将收敛于矩阵ATA的特征向量。采用这种算法，可以从任意页面集中计算出具有最大authrity权值和hub权值的页面。本文在分析网络构造的根底上，介绍了构造挖掘中HITS算法模型，并针对其弱点提出了改良方案。对于HITS算法而言，还有其它的方式可以进一步改良它的精度。在今后的工作中，可以考虑根据这些思想进一步改良算法。1刘丽珍等.网络构造挖掘的关键分析.计算机应用研究,2022(5)116-1182陈定权.eb构造挖掘研究.情报理论与理论,2022(1)59-613BharatK,HenzingerR.IprvedAlgrithsfrTpiDistillati