资源描述
本科生毕业论文题目：(中文) 大规模网页模块识别与信息提取 系统设计与实现 (英文) Design and Implementation of Large Scale Web Template Detection and Information Extraction System姓 名： 学 号： 院 系：计算机 专 业：搜索引擎与互联网信息挖掘 指导教师： 38摘要本文在已有的基于Dom-Tree和启发式规则的网页信息提取算法的基础上，通过为所有符合W3C规范的Html标签分类，逐个分析各Html标签所包含的语义信息，细化规则设置，实现了一种自底向上的无信息遗漏的网页分块算法，并在此基础上，利用统计方法得到详细的概率分布数据，实现了文本相似度比较和Bayes后验概率估计两种网页主题内容信息块识别算法，并将其求交，提高了主题内容信息块的识别精确度。上述算法已集成到天网搜索引擎平台的网页预处理模块中，并且在SEWM 2008会议中，以这套算法为框架，组织了主题型网页识别和网页主题内容信息块提取两个中文Web信息检索评测项目。在这套算法的基础上，基于天网文件系统与Map-Reduce计算平台，实现了分布式的网页块级别PageRank算法，命名为QuarkRank算法。实际检验表明，该套算法具有很好的适应性与可扩展性，并达到了很高的精度和召回率。关键词：网页分块 信息提取 SEWM 评测 PageRankAbstractThis paper has been based on the Dom-Tree and heuristic rules of the Web information extraction method, by classifying all the Html tags in line with W3C standards, and by analyzing semantic information contained in the Html tags one by one, it refines the rules set and achieves a bottom-up page block algorithm without information missing. On this basis, with the probability distribution of data getting from statistical methods, this paper realizes two algorithms of information block recognition, one is text similarity comparison and the other is Bayes posterior probability estimates, and the final result comes from their intersection, which improves the accuracy of information theme block recognition.These algorithms have been integrated into the page pretreatment module of TianWang search engine platform, and in SEWM 2008 meeting, using these algorithms, we organized two Chinese Web Information Retrieval Evaluation Project,Which two are theme-based Web page identification and block extraction of the information theme content.In this method, based on TianWang file system and the Map-Reduce computing platform, this paper reports the distributed block-level PageRank algorithm, named QuarkRank algorithm here. The actual test showed that these algorithms are good at adaptability and scalability, and reach a very high precision and recall.Keywords: Web-Page Blocking, SEWM, Information Extraction, Evaluation , PageRank目录第 1 章序言3第 2 章相关研究工作52.1基于语义的网页信息提取算法52.2基于视觉的网页分块算法62.3Block Level PageRank算法82.3.1Block Level Web Graph82.3.2Block Level PageRank10第 3 章天网搜索引擎Quark模块113.1网页分块算法133.2网页主题内容提取163.3算法效果演示18第 4 章SEWM2008中文Web信息检索评测234.1评测任务介绍234.1.1主题型网页发现任务234.1.2网页内容信息发现任务244.2评测格式254.3评测结果254.3.1主题型网页发现任务评测结果264.3.2网页内容信息发现任务评测结果284.4评测综述31第 5 章网页分块的分布式应用325.1QuarkRank325.2其他应用34第 6 章总结与展望356.1总结356.2展望36第 1 章 序言信息时代，非Web无以制胜。互联网的高速发展，改变了我们的生活方式，打破了我们的时空界限，重塑着我们的社会形态。经济、政治、学习、工作、生活、娱乐等等各个层面都在Web网络中激荡起伏，深刻地影响着人类的未来。而Web网络的灵魂，就是流动在其中的无穷无尽的信息。Web2.0的意义就在于网络内容的提供方从商人和专业人员转变为网络上的每一个普通用户，从而几何级数地增长了Web的信息量。然而信息量的增大，随着而来的就是存储成本的增大和信息提取难度的增大，如何有效的获取和整合Web信息成为大家面对的共同课题。传统意义上，整个Web网络就是由无数的Web页面而构成，它们是网络信息存储和提取的基本单位，获取了这些Web页面就相当于获取了Web信息内容。但是把整个页面作为最基本的信息处理单位有一些不合理之处。首先是因为Web页面中信息量的分布非常不均匀，有主题内容，也有广告，导航栏，版权信息，装饰信息，以及在大量网页中重复出现的部分，它们自身的信息含量千差万别。当网页浏览者刚打开一个新页面的时候，如果之前没有浏览过类似页面，就会目不暇接，眼花缭乱，有无所适从的感觉，必须仔细探寻一番才能定位到这个页面的要害；如果之前浏览过类似页面，比如常上这个网站，那么通常浏览者就已经训练出一种直觉或者说是条件反射，他会立刻定位到他所想要浏览的部分，从而忽略掉页面中的其他部分。其次还因为现在很多Web页面是动态更新的，比如博客页面或者论坛讨论帖，它们的更新是以一个一个网页块的形式进行的，更新时页面上大部分内容并没有变化，如果仍然以整个页面为处理单位，则不可避免地存在效率损失和定义的混淆。这些情况促使我们反思以整个页面为基本信息单元的做法不仅不尽合理，一定程度上甚至已经损害了网络浏览者的用户体验，妨碍了网络信息提取的效率。解决这个问题的办法其实有两种思路。第一种就是从信息的产生方那儿就不再提供网页式的信息，而改为直接提供网页块或者文字段式的信息。最常见的例子就是RSS（聚合内容，Really Simple Syndication），博客或者新闻的提供方省去了浏览者访问网站查看更新的麻烦，直接将精简后的网页块或者文字段发送给RSS的订阅方。第二种则更为普适，就是细分网页中的信息单元，也就是给网页分块，在网页分块的基础上存储和提取Web页面的语义信息。基于网页分块的Web页面的语义信息提取在很多方面都有应用。比如，在常规搜索引擎中，可以以网页分块为基础去除网页中的噪音信息，识别出网页中的主题内容信息块，从而用提取出的主题内容信息来构建对这个页面的描述，完成网页分类、网页消重等应用。还可以凭此改进搜索引擎的索引模块和检索模块的效率，比如改进TF/IDF和PageRank的算法（详见第五章）。 Web页面的语义分块另外一个重要用途在于移动终端访问互联网，比如手机和IPod等。因为目前大部分的Web页面都是针对PC机设计的，要求有相对较大的屏幕。而移动设备通常屏幕较小，计算能力有限，无法直接访问这些页面。为了解决这个问题，要么是内容提供商手工编辑专门适用于移动设备的页面，要么就只有对页面进行语义分割，并在分割后的页面中选择信息量最高的语义块。除此之外，Web页面的语义分块还可能对常规搜索引擎之外的其他信息检索系统有帮助。比如类似于新闻人物追踪和历史新闻检索等应用，出于节约存储空间，提高检索精度，方便更新等目的，可以直接存储和操作网页中的主题内容语义块，而舍弃网页中其他与系统需求无关的语义块。在这篇论文中，第二章介绍了本文的相关研究工作，包括常见的网页分块和信息提取算法、基于视觉的网页分块算法，以及网页分块的一个应用Block Level PageRank算法；第三章介绍了我实现的网页分块和主题信息提取算法Quark算法；第四章介绍了Quark算法在SEWM2008中文Web信息检索评测项目中的实际检验；第五章介绍了在Quark算法基础上实现的一个分布式QuarkRank程序。第六章是对本文的总结和工作展望。第 2 章 相关研究工作2.1 基于语义的网页信息提取算法由于对Web页面有效分块之后可以极大地方便内容提取、数据挖掘、Web结构分析等各项Web信息检索领域的相关工作，所以早有很多研究人员前赴后继，就此展开了很多工作。其中，基于语义信息对网页分块是最简便，也最基础的一种方法。所谓语义信息，通常包括网页中包含的HTML标签信息，HTML DOM树的结构信息，文字内容信息，超链接信息，以及其他通过统计或学习而得到的全局信息等等，也可以理解成为除了网页中的视觉信息之外的所有可以得到的信息。通常基于语义的网页分块算法是和后续的网页主题内容提取结合在一起的，也就是在网页分块的过程中，同时完成了主题内容提取的工作，并且主要的注意点是在主题内容提取上，因此分块算法就比较简单，甚至不显式地分块，在此我们统称它们为网页信息提取算法。总的来说，网页信息提取算法可以分为两类，一类属于网站级别（Site-Level），一类属于网页级别（Page-Level），当然也有将两类方法结合使用的算法。Site-Level的算法顾名思义，就是分析一个网站或者网页集内部的所有网页，从中提取反复出现的模式，而一般来说，在多个网页里重复出现的模式（可理解为Dom-Tree子树）就是导航栏、广告等噪音信息了，单个网页中减去这些信息，剩下的就是主题信息内容。关于Site-Level的研究一直在继续，WWW2008上就有一篇名为Web page sectioning using regex-based template1的论文使用正则表达式来提取重复模式，从而更适应网页间的细微变化，增加了Site-Level的召回率。Page-Level的算法在处理大型网站的网页时效率常常不如Site-Level，但优势在于灵活，不受网页类型限制。它只利用单个页面内部的信息，当然也可能会用到一些全局信息。宾夕法尼亚州立大学2005年的论文2就是其中的典型。这篇论文提出简化块与块之间的层次结构，直接提取一些原子块（Atomic Block），诸如以list, table, link, object, frame, form等为根节点的html子树，来完成分块工作。这一方法虽然简单而易于实现，但依赖于事先给出的原子块列表，同时忽略了原子块之间的嵌套链接问题。在分块之后，它也只是简单计算了文字长度等几个变量来决定主题信息块。合并Site-Level和Page-Level的方法也一直有人尝试。WWW2007的论文Page-level template detection via isotonic smoothing3先利用一个Site-Level噪音模板提取器来构建训练集，然后对所有页面构建DOM树，为各节点提取分类特征，比如各节点的文本向量，各节点中链接的平均字数，各节点中链接文字所占比例等，最后利用以上训练集对测试集中每一个DOM树节点打分，经过等压平滑之后，判定每个DOM树节点的类型。所以它是典型的先Site-Level，后Page-Level的方法。2.2 基于视觉的网页分块算法基于语义的网页分块算法具有一些无法克服的先天性局限。首先，HTML语言版本众多，一直没有有效统一，而且其语法规范很松散，一些不符合HTML规则的网页也能被完全识别，所以网页编写者在制作网页时相对随意，导致Web上的很多网页都没有完全遵循W3C规范；其次，IE、Firefox等浏览器各自为政，对HTML标签的识别不尽相同，IE甚至还特别为Office软件设计了特别的html标签以辅助显示，这些都增加了基于规则分块的复杂性。在实际编程中，就必须得借助一些HTML规范工具如tidy等来修正DOM树结构的错误，但个别中文网页仍然存在无法修正的情况。而且DOM树最早引入是为了在浏览器中进行布局显示而不是进行Web页面的语义结构描述。比如，即使DOM树中两个结点具有同一个父结点，那么这两个结点在语义上也不一定就是有联系的。反之，两个在语义上有关系的结点却可能分布在DOM树的不同之处。因此仅仅通过分析DOM树并不能完全获取Web页面的语义信息，所以依赖于DOM树的启发式规则算法存在先天不足。而基于视觉的网页分块算法就弥补了这个不足。它的原理来自于用户的实际观察体验，即用户并不关心Web页面的内部结构，而是使用一些视觉因素，比如背景颜色、字体颜色和大小、边框、逻辑块和逻辑块之间的间距等等来识别出页面中的语义块。因此如果充分的使用Web页面的视觉信息，模拟人眼识别语义块的过程，并结合DOM树结构分析进行页面分块，则可以达到更好的效果。微软亚洲研究院在其2003年的论文VIPS: A vision based page segmentation algorithm4里首次提出了基于视觉的网页分块算法VIPS(Vision-based page segmentation)。VIPS算法充分利用了Web页面的布局特征（见图1），它有三个主要步骤：首先从DOM树中以较小的粒度提取出所有可视标签块，并且给每个可视标签块计算出一个DOC（“一致性程度”，Degree of Coherence）值来描述该块内部内容的相关性。DOC的值越大，则表明该块内部的内容之间的联系越紧密，反之越松散。第二步利用每个可视标签块的绝对位置和相对位置信息，检测出它们之间的所有的分割条，包括水平和垂直方向。最后基于这些分割条，利用更多的诸如颜色等视觉信息，重新构建Web页面的语义结构。VIPS算法的优点十分明显，它充分利用了网页的视觉信息和结构信息，相对于传统的基于规则的分块算法来说，大大提高了分块的精确度。但VIPS算法也有其局限性：首先，提取网页视觉信息代价很高。因为HTML语言本身并没有包含足够的视觉信息，所以网页真正显示出来的效果因浏览器，因操作系统，甚至因硬件而异。为了得到网页的完整视觉信息，必须完全下载该网页所链接的CSS文件，JavaScript文件，图片文件等等，然后调用浏览器内核代码渲染这些网页文件，最后从浏览器内核代码的接口中得到每个HTML标签的视觉信息。整个步骤不仅耗时，而且十分依赖于浏览器内核代码。网络上看到的一些VIPS算法实现都是调用了IE COM接口，而微软自身的实现是利用单独优化后的IE内核，他们都是基于Windows编程环境。在Linux编程环境下，可以利用的只有Mozilla（Firefox）浏览器的开源代码。但Mozilla代码并没有针对网页视觉信息提取这一需求给出方便的使用接口，只有在其渲染完网页之后再截取视觉信息。我们实验室的毛先领师兄曾经研究Mozilla代码，完成了这项艰苦的工作，但实验表明，提取一个网页的视觉信息所需时间超过1秒钟，不能满足搜索引擎等常规应用的使用要求。其次，VIPS算法虽能改进分块精确度，但算法相对比较复杂，迭代轮数较多，而基于规则的分块算法却只用较少的迭代轮数。2.3 Block Level PageRank算法在VIPS算法的分块基础上，微软2004年的论文Block-level Link Analysis5中提出了Block Level PageRank(BLPR)算法。之前的大多数链接分析算法都是以一个Web页面为Web图中的一个节点，而BLPR算法以网页中的语义块为原子节点，从链接结构和页面结构中提取出Page-to-Block，Block-to-Page关系矩阵，构建出新的Web语义图，并以此计算PageRank。实验表明，BLPR改进了PageRank的质量。2.3.1 Block Level Web Graph首先定义两个集合P和B。P为所有网页的集合，P = p1, p2, , pk，k为网页总数。B为所有语义块的集合，B = b1, b2, , bn，n为语义块总数。对每个语义块来说，只有一个网页包含它，bi pj意味着语义块i包含于网页j。而每个网页包含有多个语义块。然后定义两个矩阵，block-to-page 矩阵Z和page-to-block矩阵X。在上述两个矩阵的基础之上，可以构建两个web图模型，即网页图GP (VP,EP, WP) 和语义块图GB (VB, EB, WB)。对这两个图来说，V是节点集合（节点分别是网页和语义块），E是连接两个节点的边的集合，而W是边的权值矩阵。2.3.1.1 Block-to-Page矩阵块页（block-to-page）矩阵Z的维数为nk，定义如下： si是block i所链接的网页总数。Zij可以理解成是用户从block i链接到page j的概率。2.3.1.2 Page-to-Block矩阵页块（page-to-block）矩阵X的维数为kn，定义如下：si是page i所包含的block总数。上面的公式分配给page i中的每一个block以相同的权值，显然是过于简化了，不能区分block的重要程度。在BLPR算法中，采用了一个简单的block重要度区分的公式，即用block的文字多少和离整个页面中心点位置的远近来计算block的重要度。每个block包含的文本长度越大，离页面中心点越近，则越重要。改进后的X定义如下：其中f函数给page i中的每一个block j赋予一个重要度权值。函数值越大，则block越重要。在BLPR的实现中函数f的定义如下：其中为正规化因子，使得对每个page，fp(b)的总和为1。即fp(b)可以理解为是用户在浏览page p的时候，关注block b的可能性。2.3.1.3 Page Graph传统的PageRank算法中Page Graph的权值矩阵计算十分简单，如果从page i到page j有链接的话，则WP(i,j)为1，反之为0。然而在BLPR算法中，Page Graph需要体现出不同的语义块的重要程度的不同。也就是说，当用户点击页面中的超链接时，更偏好选择重要的语义块中的URL。所以在BLPR中，WP的定义为：即。WP(, )可以理解为是从page 开始，以page 中包含的各语义块为媒介，跳转到page 的概率。2.3.1.4 Block GraphWB的定义为：即。WB(a,b)可以理解为用户从block a开始，以包含block b的page 为媒介，跳转到block b的概率。2.3.2 Block Level PageRankBlock Level PageRank跟PageRank区别的实质在于，PageRank算法基于原始的只有1和0的Page Graph，而BLPR算法基于上面提到的GP。BLPR算法的数学计算公式如下：其中p为结果向量，共n维，每一维代表一个网页的PageRank值。为适配参数，以1-的概率，用户在当前页面中随机选择一个超链接，跳转到该链接指向的页面；以的概率，用户从所有网页中随机选择一个URL并跳转。所以U为nn的转换矩阵，它满足对所有的i，j，Uij = 1/n。而M也是nn的转换矩阵，它是由上面提到的WP权值矩阵对每一行做归一化，令每一行的权值之和为1得到的。p向量的值以马尔科夫链的形式循环计算下去，直到算法收敛。Block Level PageRank比单纯的PageRank包含了更多的语义信息。因为它的计算基于网页中各语义块的重要程度，噪音块、广告块中的超链接指向的网页的重要性显然不如导航块、正文块中的超链接所指向的网页，所以前者会被分配到较少的PageRank值，而后者则被分配到较多的PageRank值。也就是说，网页中的无关信息区域在PageRank的计算过程中起的作用相对较小，所以BLPR的效果要优于单纯的PageRank。第 3 章 天网搜索引擎Quark模块搜索引擎系统一般包括网页的抓取、预处理、存储、索引、检索等几个部分，其中预处理部分的作用是分析、处理原始网页数据如去除网页噪音，消除重复网页，计算PageRank，中文切词等等，并为后继模块提供统一的数据访问接口，规范数据管理，避免重复计算。同时在天网搜索引擎平台中，基于功能扩展和实验室内部其他相关研究的需要，必须将对原始网页的处理部分单独出来，从而方便模块复用，统一代码管理，减少重复劳动。在天网搜索引擎平台的搭建过程中，也包括了抓取、存储、分析（预处理）、索引、检索等模块，其中的分析模块接受成批量原始网页的输入，然后对每个网页调用Quark模块，进行网页分块、信息提取等工作，最后将处理后的数据存成TwDocView格式，再提供给下游模块。我的毕业设计的主要工作，就是围绕Quark模块而展开。从上面的介绍中可以看出，天网搜索引擎Quark模块有两个比较重要的特点：1、可扩展性。因为搜索引擎是一个比较庞大的系统，并且一直在不停的有新算法，新需求的加入，所以对数据的要求也会一直变化。而基于对原始网页数据集中处理的原则，为了应对下游模块可能提取的新的数据访问需求，Quark模块必须具备良好的可扩展性，并且提供尽量多的各种类型的数据访问接口。同时由于实验室人员的不固定性，代码的维护十分重要。我自己在刚开始阅读旧有的天网搜索引擎相关代码的时候，就常有十分难懂的感觉，无法复用已有代码，只好自己重新编写。而正由于Quark模块的可扩展性要求，所以它的代码的可阅读性也十分重要，在编写的过程中，我尽量注意了这一点，遵守了我们统一的代码规范。2、独立性。在我们实验室内部，除了搜索引擎之外，还有Web数据挖掘，Map-reduce应用等相关工作也可能需要使用对单个网页的处理和数据提取程序。因此Quark模块必须能独立于搜索引擎代码之外单独编译运行，并且方便他人调用这部分代码。基于上述两个特点，我初步实现了Quark模块。该模块的类结构图如下：1、图中右下及中间蓝色的部分为Quark模块的核心功能类，包括QuarkTree、QuarkElement、QuarkRecognizer、QuarkAnalyzer等四个类。QuarkTree类的作用有两个，一个是以原始网页为输入，建立Html的Dom Tree；另一个是存储分好的网页块（在我们的系统中，每一个网页块就叫做一个Quark）并记录Quark与Quark之间的组织架构。QuarkElement类指代一个Quark,即每个Quark自身就是一个QuarkElement类的对象。QuarkRecognizer类肩负网页分块的重任，从网页中识别出所有语义块。它依赖于前面的两个类。QuarkAnalyzer类依赖于QuarkRecognizer类，它在分好的块的基础上，判断各个块的类型，提取正文信息。这个类是整个Quark模块最核心的类，目前功能只是初步实现，还有很大的改进空间，将来也可以根据功能将其分割成多个类。2、中上部绿色的部分为Quark模块的评测和演示类，包括QuarkEvaluation和QuarkHtmlBuilder两个类。QuarkEvaluation类是评测类，用来评测Quark核心类的实现效果。当前实现的是对网页正文信息提取的评测，评测需要接受人工标记的网页或网页集为输入。评测算法的细节见后文。QuarkHtmlBuilder类是演示类，用来查看Quark模块各步骤的实现效果。目前可以查看网页分块的效果，也可以查看主题信息提取的效果。3、最上面黄色的部分为Quark模块的应用类，包括QuarkRank、QuarkDuplicate、QuarkClassification等，它们都是利用分好的网页块实现的一些算法，比如基于Quark的PageRank算法，基于Quark的网页消重算法，以及基于Quark的网页分类算法。4、左下方灰色的部分为Quark模块依赖的外部类接口，包括中文切词类ChineseTokenizer，以及图中没有的编码转换类CodeConvert等等。5、中下部红色的部分为Quark模块直接的下游模块，包括TwDocView类和TwMd5类。3.1 网页分块算法算法主体在QuarkRecognizer类中。参见在第二章相关研究里提到的，除了基于视觉的算法之外，大部分基于语义的算法都是利用html标签及其包含的文字信息的特性来给网页分块的。并且由于大多数论文的着重点在于分块后的内容提取上，所以对分块算法本身着墨不多。综合各篇论文里提到的分块方法，我设计实现了QuarkRecognizer算法。这一算法首先的一大特点就是实用性强。所谓实用性强是指适合在实际系统中使用，效率高，定义完整。我详细分析了W3C制定的HTML4.01格式规范，将所有规范的Html标签根据QuarkRecognizer算法的需要分类，完整地列出了所有对网页分块起重要作用的标签，而不是像所有已有论文那样仅仅象征性地列举出几个html标签。分类后的详细html标签清单如下：1、超级标签（Super Tag，简称为S型标签）：这种标签可以被直接认定是一个网页块的根标签，在算法过程中一旦遇到这种标签，就可以直接将其加入网页块池。包括：HEAD, SCRIPT, STYLE, OBJECT, FIELDSET, FRAMESET, IFRAME2、大标签（Big Tag，简称为B型标签）：这种标签通常都代表一个网页块，只不过有时其内部内容过少，需要跟其他节点合并成一个网页块，或者在特殊情况下其内部没有可见字符。所以在算法过程中，遇到这种标签，就判断其单独作为一个网页块的条件是否已经成熟，如成熟，则将其加入网页块池。包括：DIV, TD, TABLE, FORM, FIELDSET, CENTER, NOFRAMES, NOSCRIPT, PRE, BODY, HTML这里需要注意的是像BODY，HTML两个标签也作为B型标签，原因是这样可以防止分块之后网页内部文字信息的遗漏，因为最终即使有遗漏，也会至少包含在HTML这个最后把关的门神标签手中。3、排版标签（Layout Tag，简称为L型标签）：这种标签能影响到网页的显示效果，改变文字布局。如果一颗html子树中包含多个L型标签，则该子树单独成块的可能性增加。包括：P, UL, OL, DL, DIR, LI, DT, BLOCKQUOTE, ADDRESS,BR, HR, COL, COLGROUP, IMG, MENU, SELECT4、显示标签（Display Tag，简称为D型标签）：这种标签数量最多，都是对文字的显示方式做微幅的调整，如改变字体、颜色、粗细等等。由于它们的存在与否不改变网页布局，所以不影响网页分块。包括：A, ABBR, ACRONYM, AREA, B, BASE, BASEFONT,BDO, BIG, BUTTON, CAPTION, CITE, CODE, DD, DEL, DFN, EM, FONT, H1, H2, H3, H4, H5, H6, I, INS, KBD, LABLE, SMALL, STRIKE, STRONG, SUB, SUP, Q, S, SAMP, SPAN, THEAD, TFOOT, TEXTAREA, U, TT, VAR, O:SMARTTAGTYPE5、附属标签（Affiliated Tag，简称为A型标签）：这种标签从属与上述四种标签的某一种，同时有些也出现在了前面四种里面。由于它们一般不单独出现，对网页布局的影响体现在了其属主标签中，所以在QuarkRecognizer算法中也不予考虑。包括：FRAME, INPUT, ISINDEX, LEGEND, LINK, MAP, META, OPTION, OPTGROUP, PARAM, TD, TH, TR, TBODY, TITLE6、定制标签（Customized Tag，简称为C型标签）：因为不同的应用中，对网页分块会有些不同的要求。比如我们实验室的WebDigest小组在进行新闻网页的数据挖掘的工作中，需要使用到网页分块，但是他们特别需要提取该新闻网页的发布日期和时间，而这部分内容通常是在新闻标题与新闻正文之间的一小行文字，正常的网页分块程序并不会将其单独提取成一个网页块。所以我添加了定制标签，由用户指定，它可以是普通的标签如“TITLE”等，也可以是正则表达式，凡是其内部文字满足该正则表达式的S型、B型和L型标签，都将被单独提取为网页块。例如：H1, H2, TITLE在明确了各html标签的类别之后，利用DomTree中各标签节点的类别信息和内部文字长度，以及其子标签节点的类别信息，对DomTree自底向上遍历，在遍历的过程中不断判断出新的网页块，并加入网页块池中，当遍历到最上部的html根节点时，算法结束，网页分块完毕。QuarkRecognizer算法的核心伪码如下：_ ALGORITHM QuarkRecognizer (DomTree tree，TagList CType) INPUT : 某单个网页构建的DomTree，定制标签(C型)节点列表BEGIN 1 用DomTree的叶子节点，也就是文字节点建立一个当前节点队列，开始自底向上遍历。2 取当前节点队列的第一个节点。3 如果遇到S型节点，则立即将此节点加入网页块池。4 如果遇到C型节点，则立即将此节点加入网页块池。5 如果遇到B型节点，则判断该节点内部的文字长度是否已超过阈值，或者该节点内部的L型节点比例是否超过阈值，如果满足上述两个条件之一，则将此节点加入网页块池；否则将其内部文字长度信息和自身信息向父节点传递，然后将父节点加入当前节点队列，回到2。6 如果遇到L型节点，则将其内部文字长度信息和其自身信息向父节点传递，然后将父节点加入当前节点队列，回到2。7 如果遇到D型或A型节点，则将其内部文字长度信息向父节点传递，然后将父节点加入当前节点队列，回到2。8 当前节点队列为空时，遍历结束，算法终止。END_ 网页块池中的网页块是以QuarkElement的格式存储，而QuarkElement类中包括原来的html子树的DomTree结构和其他相关信息，同时在上述遍历的过程中，即使有的网页块从html结构上来说包含在更高层的网页块之下，但在QuarkElement中也消除了包含关系，所有网页块都互相独立，互不包含。3.2 网页主题内容提取算法主体在QuarkAnalyzer类中。采用了基于规则和基于Bayes的语义分析相交的方法，也就是分别用基于文本相似度的方法和基于Bayes的方法判断每个网页块的类型（是不是主题块），然后对它们求交集，只有两个方法共同认定的主题内容块才能最终被认定。QuarkAnalyzer算法的核心伪码如下：_ 第一步，基于文本相似度的方法：1、首先，把所有网页块中，文本长度最大的那个网页块判定为主题内容块。2、然后用其余网页块逐个与最大的网页块比较文本相似度。文本相似度的计算如下： 2.1 将两个网页块分别切词，去除停用词后，存储成token流。 2.2 对两个token流分别排序。 2.3 对排序后的两个token流计算token的重复数。 2.4 用token的重复数除以较小的token流中的token个数，得到两个网页块的文本相似度。3、若文本相似度大于一个阈值，则该网页块也判定为主题内容块。第二步，基于Bayes的方法：根据下面列出的7项先验概率和该网页块相对应的这7项特性的（0，1）值，利用Bayes概率的计算公式，计算出每个网页块是不是主题内容块的后验概率。若该后验概率大于0.5，则判定该网页块为主题内容块，否则反之。第三步，求交。两个方法共同判定的主题内容块即为最后认定的主题内容块。_ 其中Bayes方法的各先验概率事先用手工标记的样本网页计算得到，结果如下：在该网页块为主题内容块的条件下，# 该块中包含定制标签的概率p1_costomizedTag = 0.29;# 该块中包含常见噪音词并且文本长度小于100的概率p1_noise = 0.04;# 该块中每10个字符中的标点符号数大于0.3的概率p1_punctuationScale = 0.85; # 该块中标点符号总数大于4的概率p1_punctuation = 0.77# 该块中非锚接文本的长度大于200的概率p1_size = 0.84# 该块中链接数量大于20的概率p1_linkNum = 0.10; # 该块中锚接文本和非锚接文本的长度之比大于0.3p1_scale = 0.08;在该网页块为非主题内容块的条件下，# 该块中包含定制标签的概率p2_costomizedTag = 0.01;# 该块中包含常见噪音词并且文本长度小于100的概率p1_noise = 0.45;# 该块中每10个字符中的标点符号数大于0.3的概率p2_punctuationScale = 0.25; # 该块中标点符号总数大于4的概率p2_punctuation = 0.34# 该块中非锚接文本的长度大于200的概率p2_size = 0.06# 该块中链接数量大于20的概率p2_linkNum = 0.71; # 该块中锚接文本和非锚接文本的长度之比大于0.3p2_scale = 0.85;网页块为主题内容块的概率：p_isContent = 0.16;网页块为非主题内容块的概率：p_isNoise = 1 - p_isContent;3.3 算法效果演示为了检验上述算法的效果，除了下一章会提到的评测程序外，还可以用QuarkHtmlBuilder类所编写的演示程序以及自搭的Apache服务器上的python脚本来查看网页分块后和主题信息提取后的效果。限于篇幅，这里就不再详细介绍算法的细节，但是附有几张对照图片，以利说明。第一幅图：这是用python脚本写的一个在浏览器上查看网页主题内容提取效果的demo，可以选择用PageModel的算法（即Quark模块），也可以选择用SiteModel的算法，点击submit按钮，就可以出现手工标记的主题内容，和程序判断的主题内容的对比画面。由于时间关系，该Demo比较粗糙，没有过多修饰。Submit后的效果图见后面的第五幅图。第一幅图：这是从新浪网上保存的一个新闻网页。显然，其主题内容信息块应该是屏幕中左部的大块文字内容。在处理这种类型的新闻网页时，算法的效率很高，但事实上，Quark模块还可以处理更复杂的网页类型。第二幅图：这是网页分块之后的示意图。从图中可以看出，红色、绿色、紫色的网页块间杂排列，就像地图一样，每一种颜色表示一个被识别出的网页块。图中没有颜色，依旧是蓝色的链接色的部分是新浪网动态生成的内容，在html源代码中并不存在，所以没有被标上字体颜色。第三幅图：这是网页正文提取之后的示意图。图中红色的部分为QuarkAnalyzer识别的正文内容，绿色部分为其识别的相关链接，其余紫色部分为噪音内容。从图中可以看出，就这个网页而言，网页主题内容的提取基本成功了。第五幅图：这是第一幅图所示Demo的结果界面截图，可见，图片上方是手工标注的文字内容，共720个字符。图片下方是程序生成的文字内容，共628个字符。两部分内容大致相等，说明网页主题内容提取成功。第 4 章 SEWM2008中文Web信息检索评测 4.1 评测任务介绍SEWM中文Web信息检索评测6是由北京大学网络实验室主办的中文Web检索评测项目，自2004年起，在SEWM会议中已连续举办了五届，今年（2008年）是第五届。其目标在于为中文信息检索领域的研究人员提供一个标准的评测平台，希望在国内外各个研究小组的共同参与下建立并完善以中文为主的网页测试集CWT(Chinese Web Test collection)，解决支持中文WEB研究的基础设施建设和应用中的基本方法与关键技术，一起推动中文Web信息检索技术的发展。SEWM2008中文Web信息检索评测有三个任务： 主题型网页发现和网页内容信息块发现，非网页数字资源分类和垃圾邮件过滤，其中前两个任务主要由何靖师兄设计，由我处理各参赛队伍提交的数据并给出评测结果。本届评测采用的数据集是CWT70th。文档集数据格式参见7。 由于本次评测任务的设计和上文提到的天网Quark模块关系密切，评测所使用的程序就是天网Quark模块中QuarkEvaluation类的python版本的代码，同时天网Quark模块的一个稍早期版本也参加了第二个任务关于网页主题内容的评测，所以也可以作为天网Quark模块的一个实验结果，检验第三章提到的算法的效率。4.1.1 主题型网页发现任务主题型网页是指通过文字描述了一件或多件事物，具有一定主题的网页。如一张具体的新闻网页就是典型的主题型网页。下面是对主题型网页的一个补充定义：1、仅由图片，flash，网络视频等构成主题块的网页，除非亦包括独立成段的文字性描述信息，否则不属于主题型网页。2、某些导航型网页，如同类软件下载网页中，虽然对每个链接都使用了适量文字来介绍，从而文字比例比较高，但也应该算作非主题型网页。3、错误网页，空网页，垃圾网页，Spam网页等属于非主题型网页。4、论坛、博客网页属于主题型网页，但没有主贴，只包括无意义回复语句的网页属于非主题型网页。任务评测根据准确度、召回率和Macro-F1三个指标，它们的定义如下：4.1.2 网页内容信息发现任务在一个主题型的网页中， 一般会包括主题内容信息，噪音信息，和相关链接信息。本项任务的目的在于找出主题型网页中的主题内容信息。噪音信息定义：a. 与网页主旨内容不相关的信息b. 由网站提供的内容模板信息c. 广告信息d. 脚本程序信息相关链接定义：指向与本网页相关网页的链接，如新闻网页下方的相关新闻链接。补充定义：1、 新闻网页的内容信息应包括出现在页面里的标题，时间，通讯社，记者名等信息。2、一个网页中的内容信息不一定只有一块，可能有多块，甚至可能是零散分布的文字段。3、无意义的论坛回帖（如”顶”等）不属于内容信息，但有一定内容的论坛回帖属于内容信息。4、相关链接不算内容信息。任务评测根据准确度、召回率和Macro-F1三个指标，它们的定义如下：4.2 评测格式评测要求参加评测单位以一定的格式提交，每个评测任务接受参加者的一到二组检索结果。具体要求如下：主题型网页发现：提交一个纯文本文件，包含所有找到的主题网页，每个网页的编号占一行。如： CWTquark080103-00000010 CWTquark080103-00000019 网页内信息块发现：只需要把正文内容找出来即可， 一个网页可能包括多个彼此不连续的正文内容， 正文内容可以包括包含内容标签， 也可以不包含内容标签。 结果的格式如下： Document-Number Start-Position Length三元组 其中Document-Number是网页的编号，Start-Position是某段正文内容在原网页文档中的开始位置（网页的起始位置从0开始计算）， Length是该段正文内容的长度。 一个网页可以有多个正文内容段， 因此可以有类似下面的情况： CWTquark080103-00000001 200 300 / 该网页中的第一段正文内容CWTquark080103-00000001 450 500 / 该网页中的第二段正文内容4.3 评测结果本次评测任务最终共有七支参赛队伍，提交了12组结果。1、大连理工大学信息检索实验室 DLUT1 DLUT22、四川大学计算机学院数据库与知识工程研究所 SCU1 SCU2 3、华南理工大学广东省计算机网络重点实验室一队 SCUT1 SCUT24、华南理工大学广东省计算机网络重点实验室二队 SCUT3 SCUT4 5、山东大学信息检索实验室 SDU1 SDU26、人民大学信息学院 RUC 7、北京大学网络实验室 PKU4.3.1 主题型网页发现任务评测结果在数据集CWT70th中的所有71502个网页中，有71281个不重复URL。在这71281个网页中，随机抽取了300个URL，人工判断其类型。为了消除对主题型网页认定上的分歧，在300个URL中去除了部分混合型以及不易判别类型的网页，共得到227个确定类型的网页，其中包括138个主题型网页，89个非主题型网页，主题型网页数目/非主题型网页数目 = 1.5505618，经验证，大致符合原网页集中的类型分布。利用该227个网页，评测各组参赛数据。虽然我们的样本数偏少，但由于样本中的类型分布大致符合原网页集中的类型分布，所以评测结果基本反映了各组的实际分类质量，只不过没有形成明显差距。华南理工一队和大连理工的分类质量相对最佳，而人民大学和山东大学提交的三个结果，分别将71502个网页中的66498、56509、55111个判断为了主题型网页，过高地估计了主题型网页的比例，从而大大降低了精度，但值得一提的是，山东大学提交的结果2获得了最高的召回率。评测结果如下：TEAMMacro-PrecisionMacro-RecallMacro-F1DLUT10.8888888888890.8695652173910.879120879121DLUT20.895522388060.8695652173910.882352941176SCU10.8461538461540.8768115942030.861209964413SCU20.8402777777780.8768115942030.858156028369SCUT10.8832116788320.8768115942030.88SCUT20.8897058823530.8768115942030.883211678832SCUT30.821192052980.8985507246380.858131487889SCUT40.7948717948720.8985507246380.843537414966SDU10.781250.9057971014490.838926174497SDU20.7745664739880.9710144927540.861736334405RUC0.6701030927840.942028985507
展开阅读全文