Ｔｒａｗｌｉｎｇ算法在Ｗｅｂ结构挖掘中的应用

杨　焰

摘要：在Web信息检索中，如何能够提取出与某个主题信息相关的网页变得异常重要，web结构挖掘作为web数据挖掘的一个重要方面，主要挖掘web潜在的链接结构模式，通过分析一个网页链接和被链接数量以及对象来建立web自身的链接结构模式，可以用于网页归类，本文探讨了Trawling算法在Web结构挖掘中的应用。

关键词：Trawling算法 web 数据挖掘 结构挖掘

0 引言

随着互联网的飞速发展，人们越来越多地在互联网上发布和获取信息。web已经成为信息制造、发布、加工和处理的主要平台，其涵盖的信息面之广阔、信息量之丰富、都使得它毫无疑问地成为当前最大的信息资源库。随着海量信息涌入万维网，互联网中特有的许多问题，诸如超大规模的非结构化文档数量、良荞不齐的网页质量，包含在文档中的大量多媒体信息，甚至相当含糊或不规范的用户查询表示等，必然给检索数据带来很大的困难。因此，在Web信息检索中，如何能够提取出与某个主题信息相关的网页变得异常重要。将传统的数据挖掘技术跟web结合起来，进行web挖掘活动将更有效的从web中抽取感兴趣的、潜在的、有用的信息。web挖掘是一项综合技术，涉及了统计学、人工智能、模式识别、并行计算、机器学习、数据库等多个领域。web结构挖掘作为web数据挖掘的一个重要方面，主要挖掘web潜在的链接结构模式，通过分析一个网页链接和被链接数量以及对象来建立web自身的链接结构模式，可以用于网页归类，并且可以由此获得有关不同网页间相似度及关联度的信息，有助于用户找到相关主题的权威站点。

1 Web数据结构挖掘

1.1 web数据挖掘 web数据挖掘起源于数据挖掘，数据挖掘(Data Mining)是指从大型数据库的数据中提取人们感兴趣的知识，而这些知识是隐含的、事先未知的、潜在的有用信息。数据挖掘的提出最初是针对大型数据库的，但是从更广泛的角度来讲，数据挖掘意味着在一些事实或观察数据的集合中寻找模式的决策支持过程。因而，数据挖掘的对象不仅仅可以是数据库，还可以是任何组织在一起的数据集合，如www信息资源等。WWW以超文本的形式给用户提供了包含从技术资料、商业信息到新闻报道、娱乐信息等多种类别和形式的信息，可以说是web当今世界上最大的电子信息仓库，蕴含着巨大潜在价值的知识。然而，Internet是一个具有开放性、动态性、异构性的全球分布式网络，资源分布分散，没有统一的管理和结构，这就导致了信息、知识获取的困难，即所谓的Rich Data poor Information的问题。因此，运用现有数据挖掘技术对分布的、异构的web信息资源进行挖掘，就成为了数据挖掘技术的挑战和未来的发展方向，由此产生了基于web的数据挖掘。web数据挖掘(web Data Mining)，简称Web挖掘，是一项综合技术，涉及web、数据挖掘、计算机语言学、信息学、数据库技术等多个领域。web数据挖掘是针对包括web页面内容、页面之间的结构、用户访问信息、电子商务信息等在内的各种web数据源，在一定基础上应用数据挖掘的方法以发现有用的隐含的知识的过程。

1.2 Web数据结构挖掘 在逻辑上可以把Web看作是位于物理网络之上的一个有向图G=(V，E)，其中节点集V对应于Web上的所有文档，而有向边集E则对应于节点之间的超链接(Hyperlink)。对节点集作进一步的划分，V={Vi，Vj}所有的非叶节点Vij是HTML文档，其中除了包括文本以外，还包含了标记以指定文档的属性和内部结构，或者嵌入了超链接以表示文档间的结构关系。叶节点Vi可以是HTML文档，也可以是其他格式的文档。Web上信息的多样性决定了Web知识发现的多样性，当前Web上的信息主要分为三类:①Web页面中的内容，包括文本信息和各种多媒体信息；②Web页面中超链接之间相互引用的数据；③Web服务器上的用户登录网站的访问日志数据。

由此Web数据挖掘可以分为Web内容挖掘(web Content Mining)、web结构挖掘(Web Strueture Mining)、Web使用挖掘(Web usage Mining)三大类（图1）。

Web结构挖掘即挖掘Web潜在的超链接结构模式，通过分析一个网页链接和被链接数量以及对象来建立Web自身的链接结构模式。这种模式可以用于网页归类，并且由此可以获得有关不同网页间相似度及关联度的信息，帮助用户找到相关主题的权威站点。Web结构挖掘的主要内容在于超链接分析，即通过分析页面的链接关系来研究网页的引用关系。超链接分析最早被用于搜索引擎，它的基本原理就是通过统计分析互联网上哪些页面被链接的次数多，那么该网页就被认为是比较重要的页面或者权威页面(Authority Pages)。与传统的搜索引擎使用的基于词频统计的查询结果排序算法相比，基于超链接分析的算法的优势在于它提供了一种客观的、不容易作弊(一些Web文档通过增加不可见的字符串用来欺骗传统搜索引擎)的Web资源评价方法。Web结构挖掘还应用于网站架构上，一个架构完善的网站可以提高使用者浏览的兴趣、吸引更多的使用者上线浏览。此外，Web结构挖掘还可以用于对Web页进行分类，预测用户的链接使用以及链接属性的可视化，对各个商业搜索引擎的Web页数量进行统计分析等。

2 基于有向二分图的Trawling算法在Web结构挖掘的应用

拖网(trawling)算法是建立在web页面上集心页面与权威页面的二分图关系上的。它从二分有向图的角度对互联网上的社给出了一种明确的定义描述。根据随机二分图的理论，一个足够大而稠密的随二分图将以很高的概率包含一个完全二分有向图，那么如果将某个社区的链接构看作一个大而稠密的二分有向图，则社区的核就可以用一个完全二分有向图complete bipartite graph)来表示。具体到互联网环境中，可以对上述概念有如下观的理解:如果在互联网上存在一个某种主题的社区，那么这种二分的核必将含在其中。一个二分有向图是这样一个图:图Kij的节点集合可以被分为两个集合，用(ran)和c(center)来表示。集合F中有i个节点，集合C中有j个节点，并且合F中的每个节点到集合C中的每个节点都存在一条有向边。拖网算法数据来源不是依据某个主题，而采用的是一般的爬取结果，通过扫描数据集合发现所有潜在的Fan集合，同时也确定了Center集合。然后通过重复的包含/排除剪枝得到所有的核，最后采用关联规则挖掘算法(Priorial gorithm)聚类为较小规模的核的集合。最后，每个核就是一个社区。

拖网算法为:①获取数据源，如web搜索结果的备分；②删除所有重复或镜像页面，以防产生虚假网站核；③由于只考虑那些潜在的网站，所以删去入度超过某一值(比如50)的所有）center；④考虑每一条边，对于指定的有向完全二分图的要求，或者产生一个相应的网站核，或者删除这条边，无论如何，都将移去这条边；⑤对于扫描到的较小规模的网站核，即有向完全二分图，滤去那些fans中包含来自同一个域的多个fans的结果；⑥一个有向完全二分图的任何真子集都是有向完全二分图，通过aPriori算法发现所有更大规模的网站核；⑦对于找到的网站核，使用HITS算法将他们扩展为真正的网站。HITS(Hypertext Indueed Topic Seareh)算法是关于超链接的检索算法。该算法通过对网络中超链接的分析，利用页面的被引用次数及其链接数目来决定不同网页的权威性。Hub和Anthority的关系可以用图2来表示:

因此，一个Hub页应该指向许多好的权威页，而被许多Hub页指向的一定是权威页。HITs算法中网页的Anthority权重和Hub权重有相互增强的关系。HITS算法的实现过程:根据用户查询请求，首先用一个现有的商业搜索引擎进行查询，取其部分查询结果(约200个左右)作为算法的根集(RootSet)，记为RQ。由于这些页面中的许多页面是假定与搜索内容相关的，因此它们中应包含指向最权威页面的指针。所以，对RQ中每一个节点，将所有指向该节点或该节点所指向的网页补充进来形成基集(BaseSet)，记为BQ。计算BQ中每一个网页的Anthority权重和Hub权重，这是一个递归的过程。

拖网算法中使用的共同引用过于严格而排除了一些可能的潜在网站，造成有用网站的遗漏。通过宽松引用(relaxed-cocited)重新定义了稠密二分有向图和完全二分有向图，使得一些原来被排斥在外的页面包括进来。拖网算法是针对整个Web爬取结果进行的，因此，发现的网站较为完整。而且，拖网的结果是客观的，与主题无关。

参考文献：

[1]Gordons.Linoff Michael J.A.Berry等著.沈钧毅，燕彩蓉等译.Web数据结构挖掘:将客户数据转化为客户价值.北京.电子工业出版社.2004.

[2]秦拯，张玲，李娜.改进的PagcRank在Web信息搜集中的应用.计算机研究与发展.2006(6).

[3]高琐，谷士文，唐琏.基于链接分析web社区发现技术的研究.计算机应用研究.2006(07).