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

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

2、eb 中获取知识的需要。许多时候人们苦于在巨大的网络世界中不容易找到自己感兴趣的、权威的内容。所以人们迫切需要找到这样的工具，能够从 WEB 上快速地、有效地发现资源，发现隐含的规律性的内容，提高在 WEB 上检索信息、利用信息的效率。数据挖掘便应运而生。数据挖掘通常有内容挖掘、使用挖掘和结构挖掘三种类型。本文主要研究结构挖掘。Web 结构挖掘是指通过分析不同网页之间的超链结构，发现许多蕴涵在 Web 内容之外的对我们有潜在价值的模式和知识的过程。2 结构挖掘WWW 没有数据库那样严格统一的语义模式，但也不像平面文件那样完全没有结构，从信息结构的角度来看，WWW 上的资源有三种类型：结构化资源

3、、半结构化资源和无结构化资源，它的语义隐含在语法结构之中。忽略掉 Web 页面上的文本和其它内容，只考虑页面间的超链，WWW 可以被看作是以 Web 页面为节点、页面之间超链为有向边所构成的网状结构的有向图，把 Web 看成是一个巨大的有向图 G =(V,E)，结点 vV 代表一个Web 页面，有向边(p,q)E 代表从结点 p 指向结点 q 的超链接。结构挖掘就是要在这样的网络有向图中进行超链分析。通过分析超链可以获悉网站的受欢迎程度及与其它网站的关系，而且，通过网页之间的链接还能够快速了解一个网站的内部结构。WWW 是一个超文本文档信息系统，而超链是表示信息的一个重要方式，所以挖掘超链的语

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

5、的网站的权威程度来衡量,同时它会推荐给用户许多好的权威网站，对其它网站的权威性起到了一定程度的增强作用。3 Web 结构挖掘的算法利用超链进行挖掘的两个典型的算法是：PageRank 算法及 HITS算法。本文主要介绍 HITS 算法，并针对 HITS 算法的不足之处提出一种改进的方法。采用这种改进算法，可以从任意页面集中计算出具有最大Authority 权值和 Hub 权值的页面。3.1 HITS 算法HITS(Hyperlink Induced Topic Search) 是 Web 结构挖掘的一个基本算法。此算法建立在下面几个定义之上： Hubs 页，指的是一个指向权威页的超链接集合的

6、Web 页；Authorities 页，指的是被许多 Hubs 页指向的权威的 Web 页； 以及由这两个定义所衍生出来的一个 Web 页的 Authority 权重(由网页的 out-link 决定) 和 Hub 权重(由网页的 in-link 决定)。其算法步骤如下： 1) 根据用户查询请求，首先用一个现有的商业搜索引擎进行查询，取其部分查询结果(约 200 个左右)作为算法的根集，记为 R.2) 将 R 进行扩充，对 R 中每一个结点，将所有指向该结点或该结点所指向的网页补充进来，形成基集，记为 S.3) 计算 S 中每一个网页的 Authority 权重和 Hub 权重，这是一个递归过

7、程.先将网页 p 的 Authority 权重记为 ap ，Hub 权重记为 hp，为 S中所有网页赋初值：ap (0)1，hp (0)1；再通过以下迭代公式对 ap 和 hp 进行反复修正，直至结果收敛：I 操作： O 操作： 这里 qp 的含义是存在一个由 q 指向 p 的超链接。设 且 ，a ( t) 、h ( t) 迭代的初始向量为 1, 1 T, 则 a3 、h3 分别收敛为矩阵 XTX、XXT 主特征向量。因此，页面 i 的Authority 权重为 ai3，Hub 权重为 hi3。具有较大的 a3 和 h3 的页面就是 Authorities 页和 Hubs 页。基于 HITS

8、算法的系统包括 Clever、Google 也基于同样的原理。这些系统由于纳入了 Web 链接和文本内容信息，查询效果明显优于基于词类索引引擎产生的结果，如 AltaVista , 和基于人工的本体论生成的结果，如 Yahoo！。3.2 对 HITS 算法的改进我们不难发现，HITS 算法完全不考虑页面文本的内容，在实际应用中也出现了一定的问题，如主题漂移等。这主要是由于算法认为页面中的所有超链具有同等价值引起的，根据算法描述，只要两个页面之间存在超链，则邻接矩阵中对应的值即为 1，这完全忽视了超链之间的差异，引起了算法结果的偏差。通过引入页面文本的语义信息可以解决这个问题，已有不少研究者对算

9、法进行改进，在一定程度上改善了这些偏差。在 Clever 系统中使用 HITS 算法，通过在超链的周围文字中匹配查询关键字并计算词频的方法来计算超链的权值，用计算出的权值来代替邻接矩阵中相应的值，从而达到引入语义信息的目的，取得了一定的效果。然而，网络上的页面形式十分复杂，很多时候超链周围文字无法代表链接页面的内容，甚至与链接页面的内容大相径庭。基于 HITS 算法的这些不足之处本文提出了计算超链权值的解决方案。在页面的文本中，最能够代表链接页面语义信息的是超链文字(本文仅考虑以文本为载体的超链，对以图像、动画等为载体的超链暂时不作考虑)。超链文字是超链的载体，通常可以作为链接页面内容的标题，

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

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

12、k)，否则对应项的值为 0。经过 n 次迭代后，输出 x 向量中值最大的一组页面作为 authority 页面，y 向量中值最大的一组页面作为 hub 页面，其中结果的数量可以根据具体的应用要求定制。迭代次数 n 的选择来自于矩阵特征向量的理论，经过足够数量的迭代，结果向量最终将收敛于矩阵 ATA 的特征向量。采用这种算法，可以从任意页面集中计算出具有最大 authority 权值和 hub 权值的页面。本文在分析网络结构的基础上，介绍了结构挖掘中 HITS 算法模型，并针对其弱点提出了改进方案。对于 HITS 算法而言，还有其它的方式可以进一步改进它的精度。在今后的工作中，可以考虑根据这些思

13、想进一步改进算法。参考文献1 刘丽珍等. 网络结构挖掘的关键分析 .计算机应用研究,2003(5) 116-1182 陈定权. Web 结构挖掘研究. 情报理论与实践 ,2003(1) 59-613 Bharat K, Henzinger M R. Improved Algorithms for Topic Distillation in a Hyperlinked Environment. In Proceedings of the ACM-SIGIR, 19984 Chakrabarti S, Dom B, Gibson D, et al. Automatic Resource List Compilation by Analyzing Hyperlink Structure and Associated Text. In Proc. of the 7th Int. WWW Conference, 1998-05