（计算机应用技术专业论文）基于dom的网页净化方法研究.pdf

摘要 i n t e m e t 已经成为最重要的信息库。浏览i n t e m e t 会看到网页中会包含大量和我们关 心内容无关的导航条j 广告信息、版权信息、以及调查问卷等。这些不相关的内容严重 影响了w e b 信息挖掘的效果。网页净化技术致力于把混乱的网页内容清晰化、结构化、 条理化，并清除不相关的内容。网页净化技术已经成为w e b 信息挖掘的关键技术。 介绍了网页净化的相关技术及其在w e b 信息挖掘中的重要作用，研究了目前流行 的网页分割模型，分析了它们的优势和不足。根据目前商业网页的设计风格是“d i v 加 c s s 风格，并且网页设计师特意把逻辑相关的信息放到同一个 标签里并用样式 表控制布局这样一个事实，提出了一种新的网页分割模型d s sd o m 。该模型识别出网 页中的基本数据单元，并划分出整个网页的逻辑区域。研究了基于d s sd o m 模型的网 页净化算法，该算法分析了网页噪音的特点，总结出一套评价准则，通过分配权重的方 式判断出网页各个逻辑区域的重要性，识别出主题区域和噪音区域，达到了净化网页的 目的。 利用开源项目l u c e n e 对净化后的网页集建立了索引，在网页净化的基础上实现了 搜索功能。实验证明d s sd o m 模型及其算法减少了l u c e n e 的索引量，提高了l u c e n e 的查准率。把d s sd o m 模型及其算法应用于c p c k 中文网页分类器，在网页净化的基 础上实现了中文网页自动分类。实验结果表明，d s sd o m 模型及其算法明确了各个网 页的主题和类别，提高了网页分类的准确性。 关键词：网页净化，d o m ，网页分割，网页噪音，网页分类 r e s e a r c ho fw e b p a g ep u r i f y i n gm e t h o d b a s e do nd o c u m e n t0 b je c tm o d e l x uc h a o ( c o m p u t e r a p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db yp r o f l ic u n h e a b s t r a c t ac o m m e r c i a lw e bp a g et y p i c a l l yc o n t a i n sm a n yi n f o r m a t i o nb l o c k s a p a r tf r o mt h e m a i nc o n t e n tb l o c k s ，i tu s 砌l yh a ss u c hb l o c k sa sn a v i g a t i o np a n e l s ，c o p y r i g h ta n dp r i v a c y n o t i c e s ，a n da d v e r t i s e m e n t sf o rb u s i n e s sp u r p o s e sa n df o re a s yu s g ra c c e s s w ec a l lt h e s e b l o c k st h a ta r en o tt h em a i nc o n t e n tb l o c k so ft h ep a g et h en o i s yb l o c k s w es h o wt h a tt h e i n f o r m a t i o nc o n t a i n e di nt h e s en o i s yb l o c k sc a r ls e r i o u s l yh a r mw e bd a t am i n i n g d e t e c t i n g a n de l i m i n a t i n gt h e s en o i s e si st h u so fg r e a ti m p o r t a n c e t h i st h e s i sp r o p o s e san e wp a g es e g m e n t a t i o nm o d e lc a l l e dd s s d o mb a s e do nt h e f o l l o w i n go b s e r v a t i o n ：m a n yp o p u l a rc o m m e r c i a lw e bp a g e sa r ed e s i g n e dw i t ht h eh e l po f t a g sa n ds t y l es h e e t s w e bd e s i g n e rl i k e st op u tt h es a n l es e m a n t i cc o n t e n t si n t oa b l o c ka n dc o n t r o lt h el a y o u to ft h e b l o c kb yt h es t y l es h e e t s t h et e c h n i q u ei s c a l l e d d i vp l u sc s s ”b a s e do nt h i so b s e r v a t i o n ，aw e bp a g ei sf i r s tp a r t i t i o n e di n t os e v e r a l b l o c k su s i n gd s s d o m s e c o n d l yi m p o r t a n c ev a l u e sa r ea s s i g n e dt oa l lt h eb l o c k su s i n ga n e v a l u a t i o na l g o r i t h m t h ea l g o r i t h mi n v o l v e st h ei n f o r m a t i o no fs t y l es h e e t sa n dt h es t r u c t u r e o fd s s d o m t h ec o n t e n t si nl o w - i m p o r t a n c e - v a l u e - b l o c k sa r en o t - r e l a t e d - c o n t e n t s d s s d o mi d e n t i f i e st h eb a s i cd a t au n i tb yt h es t r u c t u r a lf e a t u r e sa n ds e m a n t i cf e a t u r e s a n dd e t e r m i n e st h el o g i c a ls t r u c t u r eo fw e bp a g e s t h ea l g o r i t h mb a s e do nd s s d o m e s t i m a t e si m p o r t a n c eo fd wb l o c k sa n di d e n t i f i e st h en o t r e l a t e d b l o c k s t h ep r o p o s e dt e c h n i q u ei se v a l u a t e d 晰t ht w od a t am i n i n gt a s k s ，w e bs e a r c he n g i n ea n d w e bp a g ec l a s s i f i c a t i o n e x p e r i m e n t a lr e s u l t ss h o wt h a t0 1 2 l n o i s ee l i m i n a t i o nt e c h n i q u ei s a b l et oi m p r o v et h em i n i n gr e s u l t ss i g n i f i c a n t l y k e yw o r d s ：w e bp a g ep u r i f y i n g ；d o m ；w e bp a g es e g m e n t a t i o n ；w e bp a g en o i s e s ；w e b p a g ec l a s s i f i c a t i o n 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：兰釜盟 日期：切卜箩月2 z 日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部f - j ( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签名：互笠盟 指导教师签名：鲡合 日期：2 , o r 7 年多月) z 日 日期：2 删7 年5 月) 2e t 中国石油大学( 华东) 硕士学位论文 1 1 课题的背景与意义 第一章前言 随着互联网技术的高速发展，w e b 资源也在急剧的增加，w e b 作为一个大型的信息 库，给人们的学习和生活带来了巨大的便利，人们越来越依赖于w e b 来获取信息。但为 了商业上的考虑和网站的维护，很多网页都充斥着大量重复性高且与网页主题内容无关 的信息。例如：导航条、广告信息、版权信息以及调查问卷等，本文称之为噪音内容。 噪音内容分布于网页四周，甚至附着在正文旁边，文档主题很不明确，使用户不能迅速 定位所需信息。 所谓网页净化【1 】( n o i s er e d u c t i o n ) 就是识别和清除网页内的噪音内容，并提取网页 的主题以及和主题相关的内容。 在主题搜索领域，大量的噪音内容会导致主题漂移( t o p i cd r i f t ) 。这说明传统的主 题搜索算法中以网页为粒度构造的w e b 图不够准确，必须深入到网页内部将处理单元的 粒度缩小，才能提高内容分析的准确性。 在低端设备领域，大量噪音内容使得p d a 和手机用户不能迅速定位所需信息。用户 需要花费很长时间来操作滚动条，跳过大量无关的图片和文字，严重影响用户获取信息 的速度。 在w e b 信息检索领域，检索结果的相关性和检索的速度是评价一个w e b 检索系统的 两个指标。如果不除去原始网页中的噪音内容，检索系统必然对噪音内容也建立索引， 从而导致仅仅因为查询词在某个网页的噪音内容中出现，而把该网页作为结果返回，而 网页的主题内容可能和这个查询词完全无关。可以看出，噪音内容不仅使索引结构的规 模变大，而且还导致了检索准确性的下降。 在网页分类领域，由于噪音内容与主题无关，训练集中的噪音内容会导致各个类别 的特征不够明显，而待分类网页中的噪音内容则会导致该网页类别不明确，因而影响了 网页自动分类的效果。 上述分析我们看到，噪音内容对基于网页的研究工作的影响是普遍而严重的。因此， 如何更好的消除网页噪音，寻找主题信息，己经成为当前研究和应用领域的一个重要课 题。 第一章前言 1 2 论文内容的提出 为了在各个领域都能够快速准确的识别网页噪音，最首要的任务就是如何把网页分 割成相互独立而又包含完整信息的区域。本文提出一个网页分割模型d s sd o m ，非常 简洁的把网页分成了若干个相互独立的信息块。 该模型可以应用于低端设备领域，为了使p d a 和手机用户能够迅速定位所需信息， 需要把网页划分成若干信息块，并且提供一种好的浏览机制给用户，简单来说就是删除 噪音信息块，保留主题信息块。 该模型可以应用于搜索引擎以改善搜索引擎查询结果的排序。传统的搜索引擎把整 个网页当成一个信息单元。经过d s sd o m 的处理，搜索引擎会把各个信息块当成若干 信息单元，还会根据重要性的不同给每个信息单元分配不同的权重。从而能够实现搜索 引擎索引的优化和排序的优化。 同样该模型可以应用于网页分类领域，去除噪音内容的影响，提高网页分类的准确 性。 然而网页在最初设计的时候仅仅是展示信息，并没有考虑信息的结构特性。x m l 标签在一定程度上解决了展示与逻辑结构的矛盾，也越来越受欢迎，但是目前大多数网 页是用h t m l 标签编写的。 h t m l 标签只有展示信息没有结构信息，例如：通过 标签我们只能知道它是 个图片，然而这个图片有可能充当标题，菜单项，照片，广告或是视觉分割线。 标签既可以用来布局网页，也可以用来展示信息，很难通过标签本身来区分。 利用h t m l 的这种特性，可以把网页解析成一颗具有层次结构的d o m 树团，然而用 d o m 树代表网页的逻辑结构是有缺陷的： ( 1 ) d o m 树能够很好的表示网页h t m l 标签的嵌套关系，但是粒度较细。一般情况 下，一个大小适中的网页对应的d o m 树拥有数以百计的结点。很多结点对应的h t m l 标签仅仅是描述文本的样式，例如： ， 标签。 所有叶子结点的父结点同样对应 标签，这些父结点实现了整个网页的逻辑区域分 割。论文中，我们把叶子结点称作基本数据单元( b a s i c d a t a t r a i t ) ，把这些父节点称作基 本 数据块( b a s i c d a m b l o c k ) 。 _ i = = f p _ _ i f q ! 1 5 ；= = = = = = = = g g 剁 b m ”。“、 霉i 竖望粤型篓望蛩萼烹警嘲 霞霖纛i 焉薏 熏i i i 。雹i 三。 _ o 。0 ；罐辫 圈k l 网页信息区域划分示倒 f i g 卜l n e x a m p l eo f i n f o r m a t i o n r e g i o n s o n a w e b p a g e 璧 第一章前言 图1 - 2d s s _ d o m 模型的结构 f i 9 1 - 2t h es t r u c t u r eo fd s s _ i ) o m 在上面的d s sd o m 树中，带阴影的结点是基本 数据块，圆形结点是基本数 据单元。以上面的网页为例，d s sd o m 树的根结点代表整个网页，根结点的所有孩子 结点中，有7 个基本 数据块，各个数据块呈现的信息有焦点新闻，国内新闻，国 外新闻等。每个基本 数据块包含了若干基本数据单元。例如在国内新闻这个基本 数据块中，一条一条的新闻标题就是基本数据单元。 识别网页噪音首要任务是把整个网页分割成信息相对独立的逻辑区域，并标记每个 逻辑区域的结构信息。最大的难点在于找到各个逻辑区域的边界。我们观察到这样一个 现象：流行的商业化网站设计网页时更愿意用 标签配合样式表来完成。美工人员 喜欢把具有相同语义特征，相同结构特点的数据元素放在一个 标签里面，然后用 样式表控制布局。这样我们可以通过 标签得到一个天然的逻辑区域的边界，并提 出一个网页分割模型d s sd o m 。 1 4 论文组织结构 论文共分六个章节，主要内容组织如下： 第一章，主要概述了网页净化技术在w e b 信息挖掘中的作用和现状，给出了本课 题研究的意义，讲述了论文的研究内容和研究方法。 第二章，对网页净化技术进行概述，并给出了网页净化的定义和研究范围，分析了 4 中国石油大学( 华东) 硕士学位论文 它的现实性和可能性。 第三章，深入研究d o m 模型，在d o m 模型的基础上提出d s s d o m 网页分割模 型，详细介绍了d s s d o m 模型的结构和构建过程。 第四章，深入剖析d s s d o m 网页分割模型，提出基于d s s d o m 网页分割模型 的网页净化算法，该算法能够有效的去除网页噪音。 第五章，把d s s d o m 网页分割模型和净化算法应用于l u c e n e 搜索引擎和c p c k 中文网页分类器，对实验结果进行测试和评价。 最后对全文进行了总结，说明了论文的主要工作、主要创新点、存在的不足以及未 来发展的方向。 5 第二章网页净化技术概述 第二章网页净化技术概述 所谓网页净化【l 】( n o i s er e d u e t i o n ) 就是识别和清除网页内的噪音内容( 如广告、版 权信息等) ，并提取网页的主题以及和主题相关的内容。是w e b 挖掘系统预处理环节的 重要组成部分。 今天，当我们浏览w e b ，从中获取所需信息的同时，还会常常看见大量和我们所关 心内容无关的导航条、广告信息、版权信息以及调查问卷等，我们称之为“噪音”内容。 有时候，我们可能从这些噪音内容中得到一些意外的惊喜；另一些时候，我们可能不喜 欢这些东西消耗人类宝贵的注意力资源。同时，我们观察到噪音内容通常伴随着相关的 超链。因此，噪音内容会导致相互链接的网页常常并无内容相关性。这样，网页内容的 混乱不仅给w e b 上基于网页内容的研究工作带来困难，也给基于网页超链指向的研究 工作带来困难。另外，随着w e b 上各种研究与应用的深入发展，仅仅是原始网页内容 已经不能满足需求，还要求能够提供便于计算机处理的元数据信息，例如关键词、摘要、 网页内容类别等。然而，现在w e b 上大部分网页仍然是普通h t m l 网页，并不包含必 要的元数据。 所以，很多专家学者致力于网页净化方面的研究。网页净化的研究主要包含三个方 面：信息提取，网页分割，网页适应。 2 1 信息提取 2 1 1w r a p p e r 方式 w r a p p e r 是一个程序，可译成包装器，用于从特定的信息源中自动抽取相关内容， 并以特定形式( 如x m l ) 加以表示。 a l a e n d e r 等人【3 1 专门研究了一种生成w r a p p e r 的技术。有两种生成方式，一种是手 工方式，一种是利用自动化工具的方式。 手工方式需要各个领域的专家参与，专家根据自己研究领域的专业知识分析数据 源，制定一系列的规则，用测试集测试这些规则，修改规则，再测试，再修改，迭代进 行。手工方式在领域知识完整、正确的条件下，可以得到满意的结果。但是开发时间太 长，维护的代价很大。 自动化的工具需要具备足够规模的训练集，其中训练集的信息已经被很好的标注 了。在训练集的基础上，应用一个训练算法，w r a p p e r 就构造出来了。利用自动化的工 6 中国石油大学( 华东) 硕士学位论文 具产生w r a p p e r s 可以缩短开发时间，降低维护的代价，但是对训练集标记的工作量太 大。 为了方便生成w r a p p e r ，需要建立一个好的网页分割模型和分析方法用来分析网页 的布局。 2 1 2d o m 树方式 d o m 2 1 ( t h ed o c u m e n to b j e c tm o d e l ，文档对象模型) 可以作为网页内容、网页结 构、网页样式展示的中问状态。在d o m 模型中，各个数据元素组织成一个分层次的树 状结构，如图2 1 。d o m 树的各个子树对应网页上的一个视觉块。因为最初人们在设计 网页的时候，愿意把逻辑相关的内容放到位置接近的区域，所以d o m 树在最初分析网 页布局时起过一定的积极作用。也对更深入的研究提供了一些参考和线索。 图2 1h t m l 代码片段和d o m 树 f i 9 2 1h t m l c o d ef r a g m e n ta n dt h ed o mt r e e j c a v e r l e e 等人 4 1 开发了一个挖掘系统，该系统能够在搜索引擎查询出结果的时候， 自动发现并提取与查询相关的信息区域。对搜索引擎提交不同的查询会产生不同的结果 页面，他们的工作是通过比较不同结果页面的d o m 树结构来完成的。由于结果页面是 由相同的程序或者脚本生成的，所以结果页面的d o m 树有类似的结构布局。这个方法 基于下面的假设：查询结果页面中菜单以及导航栏这样的与查询不相关的区域只有微小 的差别。这种假设之下提取差异最大的d o m 子树作为与查询相关的信息区域。 这种方法有两个缺陷：首先，d o m 树只是网页展示的一个中间状态，不适合也不 曾作为一个网页逻辑区域划分的模型。其次，这个方法没有考虑到每片区域的逻辑性和 生存期。这个方法只是识别了两种区域，相关区域和不相关区域。相关区域在各个页面 都不相同，不相关区域在各个页面基本相同或是有微小差别。这个假设在很多场合是不 成立的。例如广告等网页区域，生存期是很短的，对于相同的查询很可能有完全不同的 7 第二章网页净化技术概述 广告。所以这个方法只是简单的比较了d o m 树而没有考虑网页的逻辑结构。这个方法 不一定能够得到正确的查询结果。 2 1 3 网页模板方式 很多动态网页是由特定的网页模板( t e m p l a t e ) 生成的。网页模板是一个连续的文 本标记的集合。这些文本标记会出现在每个网页中。网页模板可以用来动态产生网页。 根据动态产生的网页构造网页模板这个逆过程是很有意义的。因为得到网页模板就可以 利用模板提取网页中感兴趣的信息了。 y h e d l e y 等人【5 】通过分析网页的文本内容及其附近的标签结构得到一个模板，用来 产生搜索引擎的结果页面。 l m a 等人【6 】提出一种方法能够从动态网页中提取非结构化的数据。他们的目的是 去除网页模板信息，保留信息含量丰富的区域。他们的做法是首先扫描网页，然后根据 特定的h t m l 标签例女1 1 把网页分成若干文本块，最后计算各个文 本块在网页中出现的频率。出现频率大于某个阈值的时候，文本块作为模板被去除掉； 保留的文本块全部在域值范围内，被认定是信息含量丰富的区域，把这些文本块提取出 来做进一步的处理。 a a r a s u 和h g a r c i a m o l i n a 7 】提出的方法能够从动态网页中提取结构化的数据。他 们把由模板动态生成的一组网页作为输入，去掉模板数据，输出网页中的结构化的数据。 算法有两个阶段。首先，识别出一组在网页中出现频率相同的标记( t o k e n ) ；然后，通 过这组标记推导出网页的模板。这样就可以通过网页模板把网页中的结构化的数据提取 出来了。 使用网页模板实现信息提取的技术关键在于计算文本标记和文本块的出现频率并 通过频率的大小探测网页模板。但是没有考虑到文本标记和文本块逻辑关系。这种方法 遵从了一种启发式规则：网页模板在各个网页中是一致的；网页主要内容在各个网页中 各不相同。这种方法精力主要集中在网页集合的对比上，而没有专注于单一网页的结构 布局分析。这种方法局限在同一个模板的网页集，而w e b 上的网页模板不计其数，因 此该方法显然不够通用。 2 1 4 站点结构方式 站点结构就是同一站点下的所有网页的链接关系。利用站点结构可以实现信息提 取。 8 中国石油大学( 华东) 硕士学位论文 例如：很多站点的查询结果页面都是半结构化的形式展示的。每个查询结果都有一 句简单的描述，同时包含一个指向目标页面的超链接。目标页面是对查询结果的详细阐 述。分析结果页面和目标页面的逻辑关系，可以对查询结果到更好的理解。因此，利用 网页的链接关系可以把查询结果分割成若干块。 k l e r m a n 等人【8 】提出两个算法解决上述问题。第一个算法的思想是把目标页面的信 息编码之后作为约束条件，然后通过解决带约束条件的优化问题解决查询结果的分割问 题。第二个算法的思想利用了统计学的结论实现了查询结果的分割。 这些方法是通过分析页面的链接结构实现的。这种方法间接的解决了问题，绕开了 主要问题，绕开了研究对象。所以这些方法的有效性完全的依赖于对链接结构分析的正 确性。有的时候需要人工帮助才能得到站点的结构，所以这些方法在一些场合是不适用 的。 2 2 网页分割 网页净化领域的另一个分支是网页分割，网页分割顾名思义就是试图把网页分割成 信息相对独立相对完整的子区域。 如何得到整个网页的逻辑区域划分呢? 关键是要识别网页中信息相对独立的子区 域，即网页要被恰当地分割开。先要找到逻辑区域的边界，识别逻辑区域边界的思想有 很多：探测特定的h t m l 标签；分析d o m 树的各个子树的逻辑关系和相似度；识别视觉 分割线；分析布局相似的网页集。 2 2 1 探测h t m l 标签 由于h t m l 标签成对出现，对应信息的开头和结尾，所以最直接的网页分割方法是 探测特定的h t m l 标签。 d e m b l e y 等人9 1 提出一种方法从未知结构的表格中提取数据。他们假定一个 标签对应一个表格，而且把 标签作为网页信息块( 逻辑区域) 的标 记。然而这种假定在很多情况下是不成立的。 标签不仅可以作为一个独立的 基本信息单元( 此时代表一条结构化的信息) ，也可以纯粹用来展示信息，对网页进行 布局。仅仅通过 标签本身，很难区分表格的用途。 g p e n n 等人提出的方法可以解决上述问题，可以区分包含数据的真正表格与纯 粹做布局的表格，这里简单称作数据表格和布局表格。他们的方法基于下面的启发式规 9 第二章网页净化技术概述 则：真正的数据表格包含的行和列较多，数据表格的单元格粒度较小，低于某个阈值。 s l i n 署- i j h o 1 1 】提出的方法能够自动发现网页中的主题信息块。与e m b l e y l 均t 作类 似的是，s l i n 和j h o 同样使用了 标签作为信息块的标记。但是他们主要针对 的 标签全部是用作布局的表格，布局表格的 和q d 标签自然成了划分信 息块的标记。他们先利用 t a b i d 这三种标签把网页分成若干个信息块，然 后根据网页集合关键字的出现频率计算每个信息块的信息熵。信息熵大于某个阈值的信 息块，被认定为主题信息块。 一般情况下，基于特定标签进行网页分割的方法依赖于一些启发式规则。因此，这 些方法只是在一些特殊场合是有效的，不能算是完备的网页分割方法。 2 2 2 识别视觉分割线 在大多数站点，网页设计师都会自觉或不自觉地把网页设计成若干视觉块。每个视 觉块由一组逻辑相关的内容组成。各个视觉块是由视觉分割线分开的。视觉分割线可以 是水平或垂直的直线，也可以是空白的空间。通过识别这些视觉分割线，可以对网页进 行科学合理的分割。 yy a n g 和h z h a n g 1 2 】计算了网页各个区域的视觉相似度( 利用了模糊理论) 。利用 后缀树检测到经常出现的视觉模式，在启发式规则的指导下选择出最可能的视觉模式。 d c a i 1 3 】【1 4 】等人定义了一个等级结构的网页分割模型v i p s ，如图2 2 。这个网页分 割模型是基于可视化的，充分利用了网页的布局特征，如：字体、颜色、大小等。首先， 识别网页的视觉分割线，并给每个分割线指定权重。然后使用启发式规则把网页分割成 若干视觉块。 分割网页时，开始用d o m 树表示网页，整个网页( 即d o m 树的树根) 作为一个 视觉块。视觉块的分割基于下面的启发式规则： l f o n eo f t h ec h i l d n o d e so f t h ed o m n o d e h a sh t m lt a g t h e nd i v i d et h sn o d e ”： l f t h en o d eh a sa tl e a s to n et e x tn o d ec h i l do ra t l e a s to n ev i s u a lt e x tn o d ec h i l d , a n dt h en o d e 量r e l a t i v es i z ei ss m a l l e rt h a nat h r e s h o l d , t h e n t h en o d ec a n n o tb ed i v i d e d ”【1 3 】。最后依据视觉块间的关系( 即视觉分割线) 把视觉块组 织成一个分层次的结构。 对于每一个网页块，定义一个一致度d o c ( d e g r e eo f c o h e r e n c e ) 来描述网页块中内容 的一致程度。假设网页块1 中一部分内容是关于汽车的信息，另一部分是关于飞机的信 息，网页块2 中的内容全是关于汽车的信息，那么网页块2 的d o c 值大于网页块1 的d o c 1 0 值。d o c 值具有三个特性：( 1 ) 取值范围：0 - , i ；( 2 ) d o c 越大，网页块中的内容越一致： ( 3 ) 在内容块等级树中，子结点的d o e 值不小于父结点d o c 。可以预先定义一个一致度 d o c ，控制内容块等级树的深度，如果某个内容块的d o c 超过了预先定义的d e c ，则停 止分割。预先定义的d o c 值越小，则构建的网页内容结构越粗糙。 i i i 面磊= j j i j 粤l 霹 i 1 誉 - i 勇- _ _ _ _ _ 蠡：黼 盈 l v s 221 i l v b 222 l l v b 223 l 忱22 畦蛭 v b 3 母2 - 2 罔页实例的基于视觉的内容结构和布局结构 f i 9 2 - 2 t h e l a y o u t s t r u c t u r ea n d v i s i o n - b a s e d c o n t e n ts t r u c t u r e o f a m e x a m p l e p a g e 采用v i p s 算法的网页划分过程如图2 3 所示。这种方法对于多主题的网页净化优于 其他的方法，并且在一定程度上能满足复杂页面的要求：但由于视觉特征的复杂性，运用 的启发知识往往较为模糊，需要人工来不断总结调整规则。如果处理的页面结构很复杂， 需要的规则就非常多，一条规则的加入就会对已经成功分析的网页产生影响。因此，如 何保证规则集的一致性是一大难点。 * = $ 月化# $ 镕 婴鼍芎厣日i 矗书面 。矗牛一l 鐾一旦日n * e* ! ! ! ! ! ! 二 ；主务匿 f i 9 2 - 3 t h e v i s i o n - b a s e d p a g es e g m e n t a t i o n a l g o r i t h m k a a s i n e n l l5 提出d e s k - c a r d 模型，将网页( d e s k ) 分为若干c a r d ，每次显示一个c a r d ， 减少了页面大小，但是没有提取出信息，用户需要阅读多个c a r d 才能确定主题。 b u y u k k o m e n 1 6 1 提出了s t u ( s e m a n t i ct e x t u a lu n i 0 模9 2 ，s t u 对应网页中的块 ( b l o c k ) ，将网页分割为平行的s t u ，d e s b c a r d 模型和s t u 模型都采用了分块思想，后 者减少了定位时间，但是它们都改变了源网页的结构和内容，而且没有提取出主题信息， 保留了无关的文字和链接。 g u p t a lt i 等人的方法是从网页中删除无关部分，维持了源网页的结构和内容，但在 删除链接时较少考虑上下文的语义，极易删除正文中的链接列表，使提取结果不完整。 王琦 1 s l 等人综合了b u y u k k o k t e n 和g u p t a 的方法，提出s t u d o m 树模型，在删除 无关结点的同时有效保留了与主题相关的文字和链接，但是该方法没有考虑到显示对象 的位置特征。 n 1 9 1 等人仓i 造性的把g o o g l e 的p a g e r a n k 算法应用到识别网页主题内容上来。该 方法把单个网页看成一个网络，把与网页对应的d o m 树的时结点看成网络中的站点， 然后通过“链接分析”来计算各个结点的p a g e r a n k 值，并最终根据这些值来识别主题 内容。 2 23 分析网页集 lr a m a s w a m y 2 。1 等人提出的方法能够自动监测网页集中的信息块。主要思想是 把网页集转变成d o m 森林；然后定义阂值m ，通过识别m 棵d o m 树的最大子树，检测 出网页信息块。 他们的方法认为动态网页集的很多网页的结构是相同的。并且网页全部格式良好。 所以使用d o m 模型解析网页。 垂 i 中国石油大学( 华东) 硕士学位论文 芝加哥大学的刘冰圈】等根据“对同一个网站，那些与主题无关的部分常常有着相 同的内容和表现风格”这样一个事实，根据页面的d o m 结构构造s t y l et r e e ，树上结点 的熵值就代表该结点的重要性。下面是s t 树的简单例子，这个例子是将d o m l 和d o m 2 合并起来，如下图2 4 所示。 图2 - 4d o m 树合并成s t y l e 树 f i 9 2 4d o m t r e e sa n dt h es t y l et r e e 从这个例子中我们可以看到d o m l 和d o m 2 除了深色结点的子结点不同外，其他结 点一样，这样d o m l 和d o m 2 便能够合并起来。对于同一个网站的网页来说，网页的布 局具有相似性，因此同一个网站内的多个网页可以合并成一棵s s t 树。在d o m l 和d o m 2 中都是从b o d y 标签开始，b o d y 标签下有相同的格式，都是t a b l e i m g t a b l e 。在 s t 树中将这样的整个序列称之为类型结点( s t y l en o d e ) ，在s t 树中将这样的整个序列称之 为类型结点( s t y l en o d e ) ，在s t 树中用虚方框标出。为了与d o m 树中的标签结点区别，将 s t 树中的结点称之为元素结点( e l e m e n tn o d e s ) 。例如，t a b l e i m g t a b l e 这个类型结 点有三个元素结点t a b l e ，i m g 和t a b l e 。在d o m l 和d o m 2 中深色元素下的类型结点 是两种不同的形式，分别是p i m g p a 和p b r p 。通过将两颗d o m 树合并成一颗s t 树， 可以找到它们的相同之处和不同之处。 s t 树如何构建呢? s t 树包含两种类型的结点，类型结点和元素结点。下面明确一 第二章网页净化技术概述 下类型结点和元素结点的定义。类型结点s 表示一个布局或描述形式，它有两部分组成， 用( e s ，n ) 表示，e s 表示一个元素结点序列，设e s 在各个网页的d o m 树中处于l 层，则n 是 在l 层中具有e s 这种类型的网页个数。对于一个元素结点e 来说，它有三部分组成，用 ( t a g ，a t t r ，s s ) 表示，t a g 是标签名称，如“i m g ”，a m 是t a g 的属性集合，如“w i d t h = 1 0 0 ，s s 是e 结点下的类型结点集合。首先为网站中的每一个网页构建d o m 树，然 后以自顶向下的方式将这些d o m 树合并成一棵类型树。对于s t 树中某个特定的元素结 点e 来说，假设在d o m 树中对应的标签结点为t 。检查d o m 树中t 结点的子标签序列是 否与s t 树中e 结点的子类型结点s 一样，如果一样，增加类型结点e 的n 值，即增加与此 类型结点相同的网页数量，然后继续合并d o m 树中剩下的结点；如果不一样，在s t 树 t p 元素结点e 下创建一个新的类型结点，将d o m 树中标签结点t 的子树作为该类型结点。 在判断s t 树中噪音元素结点时基于以下两点假设：( 1 ) s t 树中某个元素结点下的类 型结点越多则该结点越重要，类型结点越少则该结点越不重要；( 2 ) 元素结点包含的内容 越多样，该结点越重要。通过这两点来衡量元素结点的重要性。对于一个网站的s t 树即 s s t 数来说，内部结点和叶结点采用不同的处理方式。对于s s t 中内部结点e ，它的重要 程度用c o m p l m p ( e ) 表示，计算方式如下： c o m p l m p ( e ) = ( 1 - z 7 ) n o d e l m p ( e ) + 7 7 ( p f c o m p l m p ( s , ) ) s = l ( 2 1 ) r， d 撕( 耻j 善训o g 棚，矿渺1 其中 l 1 i fm = 1 ( 2 2 ) l 代表元素结点e 的子类型结点的个数；p i 是网页使用e 结点的第i 个子类型的概率， 即出现第i 个子类型的网页个数与总网页个数的比值；s i 是e 的子类型结点；y 是一个大 于零的可调参数；另外 k c o m p i m p ( e j )j _ j c d 咖( s ) = 旦厂 ( 2 - 3 ) c o i n p i i n p ( s i ) 表示类型结点s i 的重要程度，马表示s i 中的元素结点，k 表示s i 中元素结 点的个数。 对于s s t 树中的叶结点e ，重要程度计算公式如下， 1 4 中国石油大学( 华东) 硕士学位论文 = 卜学z ( 2 4 ) 其中a i 表示结点e 中的特征项，如词语，图像文件，链接等；l 是结点e 中特征项的个 数；m 是含有e 结点的网页个数；h ( a i ) 是a i 的信息熵。h ( a i ) 计算公式如下， l h ( a f ) = 一p ，l o g 。p l ， “ ( 2 5 ) 其中p i i 中表示含有结点e 的网页中出现a i 的概率。噪声的判断：如果s s t 中元素结点e 的所有后继结点的重要程度以及自身的重要程度小于某个阈值则认为e 是噪声。 这种方法虽然很容易识别网页中的噪音，但是对从任意网站下载的网页集无效。 w a n g 等人【2 4 】提出d s e ( d a t a - r i c hs e c t i o ne x t r a c t i o n ) 算法，该算法通过自顶向下比较两 棵同模板的网页树，去除相同的子树，把剩余部分作为网页的主题内容。但至于如何找 到两个属于同一模板的网页，文中并没有提出明确的方法。 2 2 4 分析单个网页 b c h r i s t o s 2 5 】等人提出了一个网页分割算法。他们的方法针对的网页全部是用嵌套 表格来布局的。他们首先把网页解析成h t m l 树( 没有对h t m l 树做任何解释，我们 认为h t m l 树是d o m 树的另一种提法) 。然后删除 标签之外的所有标签， 剩余的部分构成一棵“索引树”。他们的算法首先遍历这棵索引树，找出符合标准的结 点。把符合标准的结点的子树标记成信息块，并且停止对子树的继续遍历。 他们在算法中使用了两条标准。如果索引树的结点满足标准1 ，算法结束，不再检 查标准2 ，并把该结点的子树标记为信息块。当结点不符合标准1 ，用标准2 检查，如 果符合标准2 ，该结点子树标记为信息块。 标准1 网页索引树结点必须中等尺寸大小。索引树的结点是中等尺寸当且仅当结点 的纯文本长度( 不包含标签) 与整个页面的文本长度的比值大于等于z “m 戕且小于等 于u u m 积。其中u m 戤是索引树中结点个数，z 和扰是下界和上届，实验中设定为l 和2 。 标准2 算法检查是否存在结点拥有少于4 个的孩子结点或少于5 个的子孙结点，不 包括布局结点。这里的布局结点是指标签不太重要的结点。( 这里的解释有些模糊，没 有对重要性作出任何说明) 。 这个方法仅仅依靠一些经验性的启发式规则( 标准1 和标准2 ) ，没有形成正规的 第二章网页净化技术概述 模型。 2 3 网页适应 网页净化相关的另一个领域是网页适应。网页适应是通过改变网页布局的方式重塑 网页。以增强网页的可读性并减少视觉障碍。 为了满足用户的个性化需求，需要使用网页适应技术，例如，调整网页布局和大小 适应小屏幕设备，如手机、p d a 等。目标就是改变网页布局，加强网页内容的可读性。 对于有视力缺陷的用户，同样需要网页适应技术，改变网页布局，加强网页内容的可读 性。 很多学者在网页适应研究中做出贡献 2 6 1 1 2 7 】【2 8 1 2 9 3 0 3 1 】【3 2 】【3 3 1 ，提出各种各样的方法。 然而很少有人尝试挖掘并利用网页的结构布局信息。这些信息对改变网页布局、实现网 页适应是至关重要的。 j c h e n 3 4 等人提出了一个网页分割模型f o m ( f u n c t i o n b