（计算机系统结构专业论文）基于视觉特征中文网页分类方法的研究.pdf

山东大学硕士学位论文 摘要 近年来，基于视觉特征的网页分割技术越来越受到人们的关注，它模拟了人 们在视觉感知角度上对于一个网页结构的理解，此技术对于信息检索、信息提取、 网页自动分类等网络应用技术将起到极大的推动作用。网页自动分类问题是网页 分割技术的重要应用之一。作为一个具有代表性的网页分类问题，中文网页分类 一直是众多学者研究对象。本文的研究主要着眼于以下几个方面： 首先，将传统的基于文档对象模型( d o c u m e n to b j e c tm o d e l ，d o m ) 树的网页表 示方法与基于视觉特征( v i s i o nb a s e d ) 的网页表示法进行了全面的比较。基于视觉 特征的网页表示法在进行网页结构分析时采用的是一种自上而下、不依赖于标签 树( t a g t r e e ) 的方式，即与编写网页的h t m l 文档的表达方式无关。它充分利用了网 页中可视化的信息从而得到基于视觉特征的网页结构，较好地解决了网页的d o m 树结构与语义结构的兼容问题。利用可视化的分割符将网页划分成分块并抽象成 层次结构，这种层次化的语义结构在一定程度上与人们的直观感知是相吻合的。 其次，在基于视觉特征的网页分割算法的基础上，提出了种根据分块重要 度进行中文网页分类的方法。利用基于视觉特征的网页分割法将中文网页分割后， 由于网页中“噪声”信息的存在，所得到的分块并不都是具有同等权值( 重要度) 的，只有权值较高的分块才能在语义上反映出网页的主题，利用这些高权值分块 进行中文网页分类可以获得更好的分类质量。在分类系统中，查全率( r e c a l l ) 矛3 查 准率( p r e c i s i o n ) 反映了分类质量的两个不同方面，两者必须综合考虑，表示为f 1 测试值，本文实验用f 1 值来衡量最终的分类质量。 在本文实验中，将传统的全文网页分类方法和基于视觉特征的利用分块重要 度的网页分类法进行了比较。实验结果表明利用分块重要度的分类法由于综合考 山东大学硕士学位论文 虑了网页层次结构和语义机构，其分类质量为最佳。实验中的分类器选择的是支 持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 分类器和k 一近邻法( k n e a r e s tn e i g h b o u r , k n n l 分类器。 基于视觉特征网页分类法具有较好的分类质量，它对信息检索、网页分类等 应用起到了极大的推动作用，例如分块检索思想在图像检索领域的引入等，这在 本文中都有相应的介绍。 关键词：视觉特征；网页分割；分块重要度；支持向量机；网页分类 i i 山东大学硕士学位论文 a b s t r a c t r e c e n t l y ，t h ev i s i o nb a s e dp a g es e g m e n t a t i o na l g o r i t h m ( v i p s ) h a sb e e nw i d e l y r e s e a r c h e d ，w h i c hs i m u l a t e sh o wau s e ru n d e r s t a n d sw e bl a y o u ts t r u c t u r eb a s e do nh i s v i s u a lp e r c e p t i o n m a n yw e ba p p l i c a t i o n ss u c ha si n f o r m a t i o nr e t r i e v a l ，i n f o r m a t i o n e x t r a c t i o na n da u t o m a t i cw e bp a g ec l a s s i f i c a t i o nc a nb e n e f i tf r o mt h i sa l g o r i t h m t h e a u t o m a t i cw e bp a g ec l a s s i f i c a t i o ni so n eo fi m p o r t a n ta p p l i c a t i o nf i e l d so fw e bp a g e s e g m e n t a t i o n t h e c h i n e s ew e b p a g e c l a s s i f i c a t i o ni sa r e p r e s e n t a t i v ep a g e c l a s s i f i c a t i o np r o b l e ma n dh a sb e e nr e s e a r c h e db yn u m e r o u sr e s e a r c h e r s t h i sp a p e r f o c u s e so nt h ef o l l o w i n ga s p e c t s f i r s t l y ，w ec o m p a r et h et r a d i t i o n a lp a g er e p r e s e n t a t i o nm e t h o db a s e do nd o m ( d o c u m e n to b je c tm o d e l ) t r e ew i t ht h ev i s i o nb a s e dm e t h o d ，w h i c hi sa na u t o m a t i c t o p d o w n ，t a g t r e ei n d e p e n d e n ta p p r o a c h t od e t e c tw e bc o n t e n ts t r u c t u r ea n d i n d e p e n d e n t t ot h eh t m ld o c u m e n t a t i o ns t r u c t u r e t h ev i s i o nb a s e d p a g e r e p r e s e n t a t i o nm e t h o dt a k e sa d v a n t a g e so fv i s u a lc u e st oo b t a i nt h ev i s i o nb a s e dc o n t e n t s t r u c t u r eo faw e bp a g ea n dt h u ss u c c e s s f u l l yb r i d g e st h eg a pb e t w e e nt h ed o mt r e e s t r u c t u r ea n dt h es e m a n t i cs t r u c t u r e t h ew e bp a g ei ss e g m e n t e db a s e do nv i s u a l s e p a r a t o r sa n ds t r u c t u r e da s as e m a n t i ch i e r a r c h y w h i c hi sc o n s i s t e n t 谢t hh u m a n p e r c e p t m nt os o m ee x t e n t s e c o n d l y ，ip r o p o s eab l o c ki m p o r t a n c eb a s e dc h i n e s ew e bp a g ec l a s s i f i c a t i o n m e t h o db a s e do nt h ev i p s iu t i l i z ev i s i o nb a s e dp a g es e g m e n t a t i o nm e t h o dt op a r t i t i o n t h ec h i n e s ew e bp a g ea n do b t a i ns e v e r a lb l o c k sw i t hd i f f e r e n tw e i g h t sr t h ei m p o r t a n c e o faw e bp a g e ) b e c a u s eo fal a r g ev a r i e t yo fn o i s yi n f o r m a t i o ni nw e bp a g e o n l yt h e b l o c k sw i t hh i g hw e i g h t s ，w h i c hc a nb eu t i l i z e dt oc l a s s i f yt h ec h i n e s ew e bp a g e sa n d g e tt h eb e t t e rr e s u l t s ，c a nd i s c r i m i n a t ed i f f e r e n ts e m a n t i c sw i t h i naw e bp a g e t h er e c a l l a n dp r e c i s i o na r et w oi m p o r t a n ta s p e c t si nw e bp a g ec l a s s i f i c a t i o na n dm e a s u r e db yt h e p a r a m e t e rf 1i nt h ee x p e r i m e n to ft h i sp a p e r t h ev i s i o nb a s e dp a g ec l a s s i f i c a t i o nm e t h o di sc o m p a r e dw i t ht h eo t h e ro n ef f u l l d o c u m e n tb a s e dp a g ec l a s s i f i c a t i o nm e t h o d ) i nt h ee x p e r i m e n to ft h i sp a p e r ，i nw h i c h t h ev i s i o nb a s e dp a g ec l a s s i f i c a t i o ni sb e t t e r s i n c et h ev i s i o nb a s e dp a g ec l a s s i f i c a t i o n i i i 山东大学硕士学位论文 m e t h o di n t e g r a t e st h eh i e r a r c h i c a ls t r u c t u r ea n ds e m a n t i ci n f o r m a t i o no fap a g e ，i tg a i n s t h eb e t t e rc l a s s i f i c a t i o nr e s u l t s i nt h ee x p e r i m e n t ，iu t i l i z et h es u p p o r tv e c t o rm a c h i n e ( s v m ) a n dk n e a r e s tn e i g h b o u r ( k n n ) a sc l a s s i f i e r s t h ew e ba p p l i c a t i o n ss u c ha si n f o r m a t i o nr e t r i e v a la n dc h i n e s ew e bp a g e c l a s s i f i c a t i o nc a nb e n e f i tf r o mt h ev i s i o nb a s e dp a g ec l a s s i f i c a t i o nm e t h o db e c a u s eo fi t s b e t t e rc l a s s i f i c a t i o nr e s u l t a so n ea p p l i c a t i o no ft h ev i s i o nb a s e dp a g ec l a s s i f i c a t i o n ， t h ei m a g er e t r i e v a li si n t r o d u c e di nt h i sp a p e r k e yw o r d s ： v sio nb a s e dp a g es e g m e n t a tio n ：bo c km p o r t a n c e ：s v m ：w e bp a g e c la s s i f i c a t i o n i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：亟笙啤 日 期：翌z ：竺： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：姬啦 导师签名：日期：翌z ：竺 山东大学硕士学位论文 第1 章绪论 1 1 概述 1 1 1 背景分析 随着信息时代的来临，互联网已经成为人们获取信息的最大数据源。目前， 在大多数基于互联网的信息检索应用系统中，总是将网页看作是最小的、不可分 割的单位，但是随着网页编写以及网页内容的复杂化、多样化，一个网页往往包 含了多重主题，并且很多时候这些主题之间并不具备很强的相关性”。另外，网页 中通常还会存在诸如导航条、网页美化部分、互动区域以及联系信息等与网页主 题无关的内容。以上的这些问题严重影响了信息检索系统返回值的精确性，而通 过合理地划分网页的语义结构、正确地获取网页主题，能够在很大程度上提高信 息检索系统的准确性。 在许多网络应用中都涉及到了网页内容的语义结构。例如，在网络信息存取 ( i n f o r m a t i o na c c e s s i n g ) 中，为了解决顺序浏览以及关键词搜索的局限性，有些学者 提出使用数据库技术中的包装器( w r a p p e r ) 来对网络数据进行结构化嘲口l 【4 】”。在构 建包装器的过程中，需要将网络文档分割成多个信息块( i n f o r m a t i o nc h u n k ) ，但由 于网页类型的多样性，这是一个较为复杂的过程p 】【6 】，即利用a dh o c 的方法来处理 不同类型的网页。如果我们能够得到网页内容的语义结构，那么无论是包装器的 构建还是网页信息的提取都将更为容易。网页语义结构的另外一个应用就是近年 来日益受到关注的网页链接分析7 】【引。在过去的研究中，链接分析算法均建立在 个假设的基础上，即如果两个网页之间存在着一个链接的话，那么这两个网页整 体之间就存在一定的关联。这种做法充分考虑了每一个链接对网页问关联的影响， 但缺点也很明显，它对同一网页中的不同链接总是不加区分地同等处理。近来的 研究发现，在大多数情况下两个网页之间的链接仅仅表明这两个网页的某些部分 之间可能存在着一定的关联，而并不代表这两个完整的网页之间也存在着这样的 山东大学硕士学位论文 关联。另外，大量噪声链接的存在更是会给命中算法( t sa l g o r i t h m ) 带来主题漂 移的问题 7 1 1 9 1 。引入网页语义结构分析后，会将网页中的链接根据语义分析进行划 分，使链接分析更加具体化，从而得到较好的结果，这些在后续的一些关于主题 提炼、抓取的文献中得到了很好的验证( 1 0 】【“j 【1 2 1 。此外，随着个人掌上电子设备的 普及，利用掌上电子设备进行互联网信息浏览成为可能，而在使用掌上电子设备 小巧的显示屏进行较大网页的浏览时，自然需要对网页进行语义上的分割，从而 使信息的浏览更具直观性和目的性”】。 上述应用都涉及到了网页的语义结构，以往的研究都是以网页的文档对象模 型树( d o mt r e e t l q ) 为基础，通过h t m ld o m 树来抽取网页的结构化信息 【6 】【”1 1 12 】。需要指出的是，由于h t m l 语言的灵活性，许多网页的编写都没有遵 守w 3 c 规范l “】，这就会导致网页的d o m 树结构出现错误，因而利用d o m 树并不能 对网页实现真正意义上的语义分割。另外，d o m 树创立的初衷并非是表达网页的 语义结构，而是用来表示网页各部分间位置关系的。在网页中经常会出现这样的 例子：d o m 树中两个结点拥有共同的父结点，但它们之间在语义表达上并不具备 较强的相关性，反而是和其它的结点有很强的语义相关性，这也从另一个方面说 明d o m 树并不适合用来表示网页的语义结构。 从人的理解角度来看，我们往往将一个网页看作不同语义对象的集合体而并 非是传统意义上的单一整体，并且研究结果表明，用户常常希望诸如导航条、广 告栏这些具有特定功能的部分出现在网页中特定的位置“7 1 。当用户看到一个网页 时，网页中一些在空间上和视觉上较为明显的条框总是使用户下意识地把这个网 页划分成具有某些独立语义性的分块，这也就使得利用这些空间、视觉提示进行 网页自动分割成为可能“1 。 1 1 2 相关研究进展 在上一节中我们提到，许多的实际应用技术都需要提取网页语义内容的结构， 许多学者已经着手于这方面的研究。 山东大学硕士学位论文 有的研究人员针对网页的t a g 信息，以网页q ，t a g 的类型为依据进行网页划分。 需要指出的是，并非所有的t a g 都对网页的划分起到参考作用，真正有用的t a g 包括： ( p a r a g r a p h ) 、 ( t a b l e ) 、 ( 1 i s t ) 、 - - ( h e a d i n g ) 等。不同的 研究者对于上述t a g 的利用程度也是不同的。例如，有的研究人员综合利用上述所 有的t a g 信息通过一个具有学习功能的w e b 查询处理系统对网页进行分割18 】；而有 的研究人员则仅仅利用t a g ，他们将t a g ) 5 t 其后代看作一个内容 分块，利用熵信息法来找寻分割依据1 9 1 ：另外，在自适应系统的信息传递中，一 些研究者利用 、 、 这些简单的t a g 来切分网页，然后根据切分结 果进行相应的转化操作1 3 】啪】；还有的研究人员为了进行网页分割专门定义了一些 t a g 类型并且对每一部分加上标签以便于网页分类2 1 i 。 除了利用t a g 的思想以外，另外一些算法则充分考虑了网页中正文的内容或者 链接信息。其中，有人使用一些启发式的规则来探寻网页中的记录边界从而将数 据信息从网页中提取出来吲圈；c h a k r a b a r t i 等人则通过分析网页中的链接结构以及 文本分布来进行网页主题提取，这种方法具有粒度细密、无需聚合等优点【“1 ； 最近，u r l 链接分析或网页分解等思想更是被陆续提出例阱l 彤1 。 为了更好地解读网页的内容，有些学者提出了一种基于功能的对象模型 ( f u n c t i o n b a s e do b j e c tm o d e l ，f o i v 0 ”1 。在这种模型中，t a g 树中所有不可再分的元 素被定义为基本对象( b a s i co b j e c t ) ，基本对象组合起来就构成了复合对象( c o m p o s i t e o b j e 鳓。网页中的每个对象都被赋予一个功能类型( f u n c t i o n t y p e ) ，这样就可以建立 一个针对此网页的分层结构( h i e r a r c h i c a ls t r u c t u r e ) 。但f o m 模型难以准确定义对象 组合的规则以及功能的类型，这就使整个t a g 树处理起来较为困难。 上述三类方法虽然各具特点，但是都没有考虑到网页的视觉结构，而基于视 觉特征的方法则解决了这个问题，在下一节中我们将作介绍。 山东大学硕士学位论文 1 1 3 基于视觉特征的网页分类概述 在1 1 1 节中提到，d o m 树仍旧是一个线性结构，并不适合用来表示网页的 语义结构，并且像 、 这样的标签不仅仅用作网页内容的表示，而且还 用于网页布局结构的表示，这就难以获得比较合适的分割粒度。而根据空间视觉 特征划分的网页分块则可以将网页的主题和语义结构准确地表述出来，这就使得 利用空间视觉特征进行网页自动分割继而运用分割得到的分块进行网页分类成为 可能，即基于视觉特征的网页分类法( v i s i o nb a s e d p a g es e g m e m a t i o n ，w p s ) 。 在基于视觉特征分类法中，网页被表示成一个分层的语义结构，这个结构中 的每一个结点对应着网页中的一个具体分块。每个分块都被赋予一个相关度值 ( d e g r e e o f c o h e r e n c e 。d o c ) ，d o c 值用来衡量每一个分块在视觉空间上的内容一致 度。 基于视觉特征的网页分类法的最显著的特点是：它将网页表述成一个自上而 下的分层结构并且充分利用这些分层的特征来进行网页分类。首先，在网页的d o m 树中抽取出适当的分块，然后在分块间找寻分割符，最后，根据分割符的划分结 果构建出网页的语义结构。 1 2 本文的工作 本文在现有的分块算法基础之上提出了一种改进的基于视觉特征利用分块重 要度进行中文网页分类的方法。基于视觉特征的分割法比较好地利用了网页的版 面特征，但是在根据网页的语义特征进行第一步粗略划分时，仅仅是利用了相近 部分间的相关性，而没有考虑多个部分之问的相关性，从而造成了在那些较长的 网页中，有些相关的内容可能会由于篇幅跨度较大，其一致度反而会变得很小。 所以，我们提出了一种摘要的方法，不但考虑利用网页相近部分的语义相关性， 还要通过摘要提取关键词句的方法来衡量多个部分之间的相关性，从而使得最终 划分的分块具有较好的语义一致性和粒度。 山东大学硕士学位论文 在第四章的实验中，首先根据视觉特征分割法将网页粗分块，在粗分块时综 合考虑网页的版面结构特征和提取的摘要内容，从而保证语义相近的内容不被分 隔开。接下来，利用内容的相关性将粗分块细化，得到既具有适当语义一致性又 具有一定粒度的细分块，这些细分块能够更好地体现网页的主题信息。分块粗细 的程度通过预先设定的粒度控制。 根据第三章介绍的支持向量机的相关理论，s v m 分类器对于较大规模数据具 有很好的分类性能，为了说明其优越性，在第四章的实验中将s v m 分类器与先前 较常用的k n n 分类器做了比较。结果证明，s 分类器的分类质量确实要优于 k n n 分类器。 最后，在第五章中简单介绍了基于视觉特征网页分割技术的一些具有发展前 景的应用，如基于w e b 的多媒体检索等。 1 3 本文的组织 第二章介绍了基于视觉特征的网页分割算法，这其中包括基本模型的定义、分 割算法的主要步骤等。基本模型的流程图列举在第二章的相关部分，分割算法的 三个主要步骤“分块抽取”、“探知分割符”和“构建网页结构”在相关的章节中 也有详细的介绍。 第三章是关于支持向量机的相关理论，具体按照线性可分和线性不可分两种情 形讨论。 第四章介绍了几种主要的网页分块算法，在此基础上提出了一种改进的基于视 觉特征利用分块重要度进行中文网页分类的方法，并通过实验证明，这种方法相 比于传统的f u l ld o e 分类在分类质量上有明显的提高。同时，通过实验数据验证 了s v m 分类器要优于k n n 分类器。 第五章对本文的工作进行总结，并对一些新技术进行了展望。 山东大学硕士学位论文 第2 章基于视觉特征的网页分割算法 2 1 背景介绍 基于视觉特征的网页分割算法( v i s i o nb a s e dp a g es e g m e n t a t i o na l g o r i t h m ，v i p s ) 不同于以往的网页处理技术，它充分考虑了人们的视觉感知对网页主题获知的影 响。在此算法中，网页被表述成一个分层的语义结构，这个结构中的每一个结点 对应着网页中的一个具体分块，而这些分块与人们对一个网页的直观划分是较为 一致的。每个分块都被赋予一个表示相关度的值( d o c ) ，d o c 值用来衡量每一个分 块之间在视觉空间上的内容一致度。 基于视觉特征的网页分割算法最显著的特点是：它将原始网页表述成一个自上 而下的分层结构，利用这些分层结构的特征我们可以进行网页分类等实际应用。 其过程可以简单地概括为：首先，在网页的d o m 树中抽取出适当的分块；然后， 在分块间找寻分割符；最后，根据分割符的划分结果构建出网页的语义结构“1 。 在下面几节的内容中，我们将详细讨论基于视觉特征网页分割算法的模型定 义、具体算法描述、分块及分割符的抽取、分块结构的建立等。 2 2 基本模型定义 在文档对象模型算法中，网页表示成d o m 树结构，树中的叶子结点( l e a f n o d e ) 被视为基本元素，每个叶子结点不可再分。与d o m 树不同，基于视觉特征的网页 分割算法中，组成网页内容结构体( c o n t e n ts t r u c t u r e ) 的基本元素是分块( b l o c k ) ，并 且分块还可以是基本元素的集合体。d o m 树结构中的叶子结点与基于视觉特征网 页结构体的分块并不一定是对应的。 基于视觉特征网页分割算法的数学模型与传统的文档结构表示法类似“，具 体描述如下： 一个网页可以用一个三元组q = ( d ，q 占) 来表示，其中，网页分块为有限集 0 = 妞1 ，q 2 ，q ” ，所有分块之间互不包含。与网页能够划分成分块一样，每一 个分块也可以看作是一个子网页( s u b w e bp a g e ) 从而继续划分成更小的分块。网页 山东大学硕士学位论文 的分割符用有限集中= 移1 ，妒2 ，妒7 表示，分割符包括水平分割符和垂直分割符两 种。每一个分割符都有相应的权重来表明其明显度( v i s i b i l i t y ) ，同一个有限集。中 的分割符具有相同的权重。占用来表示o 中分块间的关联，描述为： j = o o - - 虬 n z ：l l 。 我们前面提到，每一个分块q 都是原始网页的子网页，因而q 。就与原始网页 q 具有相似的内容结构，所以我们可以相应地得到q ：= ( 0 ：，m ：，彰) 、 叫= 缸：，q ：，q 、巾：沈，元，毋 和彰= q q 一中：u 计眦 。其中， o ：表示在第s 层子网页中的第f 个对象，。和l 分别表示有限集q 和m ：中对象 的数量。 图2 1 为一个按照基于视觉特征划分的山东大学主页结构田i ，图中清楚地反 映出基于视觉特征划分的网页的版面结构布局。在第一层划分中，原始网页被3 个分割符( 一矿) 分割成4 个分块w m w 4 ) ，详细描述如式2 - 1 。然后，对于子 网页v b l v b 4 中可以再分割的部分构建新的子结构。例如，子网页v b 2 就有3 个 子元素，可以通过2 个分割符划分开，详细描述如式2 2 。按照上述方法，最终将 网页划分为图2 - 1 所示的布局，而网页划分后的内容关联结构如图2 - 2 所示。 o = ( w l ，v b 2 ，v b 3 ，v b 4 ) 西= 移1 ，( p 2 矿( 2 一1 ) r ( v b l ，2 ) 1f 妒1 j ( 2 ，3 ) j 一伊2 。i ( 3 ，v b 4 ) 矿 l e l s e j i 。已 v b 2 = ( v b 2 _ i ，v b 22 ，v b 2 _ 3 ) 。2 = 钮，西) 鲠 谚 u 阻 ( 2 2 ) 7 n 川川l 筛出 私 山东大学硕士学位论文 图2 1 网页划分后的版面布局 图2 2 网页划分后的内容关联结构 基于视觉特征划分的网页结构能够很好地表现出网页各部分的语义结构，图 2 - 2 中的每一个结点都含有一定的语义内容。例如，图2 一l 中的v b 22l 是这个 网页的主干“山大要闻”部分，而v b 222 则是近期的公告通知等内容。对于这 些分块所表达的内容，我们可以利用范围在1 一l o 之间的整数所定义的“一致度” ( d e g r e eo f c o h e r e n c e ，d o c ) 来衡量其相关性。d o c 的值越大，表明分块间的内容就 越相关。在分层结构中，子分块的d o c 值不小于父辈分块的d o c 值。 对于不同的实际应用，我们可以根据需要预先指定d o c 的值从而获得不同的 山东大学硕士学位论文 分割粒度，这个预先定义的d o c 值称为p d o c ( p e r m i t t e d d e g r e eo f c o h e r e n c e ) 值。 p d o c 的值越小，整个网页内容结构的划分就粗糙。例如，假设p d o c 的值设置过 小，那么图2 - 1 中的v b 221 和v b 222 就不会被划分开。不同的应用所需要的 划分结果不同，可以根据实际情况选取合适的p d o c 值利用基于视觉特征的方法 对网页进行划分，从而获取不同划分粒度的结果。 2 3 基于视觉特征的网页分割算法 基于视觉特征的网页分割算法是一个自上而下的过程，它可以概括为三个步 骤：分块的抽取、分割符的探知以及网页内容结构的构建，这三个步骤可以循环 执行。关于以上三个步骤的详细过程，我们将在下面的三节中作相关阐述。在具 体执行过程中，网页首先被分割成若干较大分块并记录下当前的层次结构。然后， 对于那些较大的分块继续执行分割，直到得到足够小的分块。判定分块足够小的 依据就是2 2 节中介绍的分块的一致度，当一个分块的d o c 值大于预先定义的 p d o c 值时，分割结束。 在每一轮循环中，可以提取与当前分块相应的带有视觉信息的d o m 树。分块 抽取操作由d o m 树的根结点开始，根据视觉上的界限从d o m 树中提取。d o m 树中的每一个结点都要依次判别是否能构成一个独立的分块，如果不能，则按照 同样方式判定其后代结点是否可以。 当所有分块抽取完毕后，根据其视觉特征赋予d o c 值并存放在存储池中。然 后，标定出分块间的分割符，分割符的权重根据其相邻分块的视觉特征来设定， 利用这些分割符可以建立网页的版面布局结构。分割算法每执行一轮，都会产生 一个新的版面布局结构。这时就要判断内容结构中的叶结点是否已经满足预先要 求的粒度，如果还不能的话，那么这些叶结点被看作是子网页继续被分割。例如， 假设图2 - 3 中的b 分块不能满足要求，那么在执行过程中就将其看作是子网页继 续分割，得到图2 - 4 中的b l 和b 2 。 9 山东大学硕士学位论文 图2 - 3 网页版面布局及d o m 树结构 图2 - 4 分块b 的版面布局及d o m 树结构 在所有分块处理完毕后，就得到了此网页基于视觉特征所建立的内容结构图 如图2 - 5 所示。 图2 - 5 基于视觉特征的网页内容结构 1 0 山东大学硕士学位论文 2 4 分块抽取 我们在上一节介绍了基于视觉特征网页分割算法的三个步骤，其中第一步就 是分块抽取。一般来说，d o m 树的每一个结点可以表示一个视觉上的分块，但是 也存在像 、 这样的大结点，这些结点只适合内容的表示而不适于用来 表示版面结构。遇到这样的结点，就要将这些结点细分，用它们的子结点来代替。 根据一个d o m 结点本身及其子结点的特性，我们可以判定它是否可以再分，这些 特性包括h t m l 标签、背景色彩以及结点所对应的分块的大小、形状等。 在具体描述一个d o m 结点如何继续划分之前，我们先给出几个定义。d o m 树 的结点根据其特性可以分为两类：内结点和外结点口”。内结点一般包括 、 、 e 移、 、 i 、，、 、 这些能够影响外观的标签，而 外结点则是包含除上述标签以外其它标签的结点。根据结点在网页中所代表的内 容以及其子结点的特性又可以将结点分为有效结点( v a l i dn o d e ) 、文本结点( t e x t n o d e ) 和虚文本结点( v i r t u a lt e x tn o d e ) 。有效结点代表的内容通过网页可以直观地 看到，结点的高度和宽度都不为o ；文本结点则对应着不包含h t m l 标签的文本； 如果内结点的子结点全部都是文本结点或者只含有文本结点和虚文本结点，那么 这样的内结点就称为虚文本结点。 根据以上的定义，我们可以制定出一些用于划分分块的重要依据：标签、颜 色、文本以及大小。标签 m 等经常作为视觉上区分不同主题的依据，所以，如 果个d o m 结点包含这类标签，那么就将这个结点继续划分。一个内结点如果有 一个子结点是外结点，那么这个内结点也需要继续划分。有些结点的背景色与其 某个子结点的背景色不同，这时就要将这个结点划分，但是在这一轮划分中，与 其不同背景色的子结点并不进行划分。当一个结点的大多数子结点是文本结点或 者虚文本结点时，这个结点需要继续进行划分。如果一个结点的大小超过了预先 设定的阈值，那么这个结点也需要继续划分。 综合考虑标签、颜色、文本、大小等依据，我们可以完成对一个结点的划分， 从而抽取出网页分块并给这些分块赋d o c 值，d o c 值的大小是根据分块内部视觉 上的差异来确定的。网页分块抽取的算法d i v i d ed o mt r e e 如下： 山东大学硕士学位论文 a l g o r i t h md i v i d e _ d o m _ t r e e ( p n o d e ，n l e v e l ) i f ( d i v i d a b l e ( p n o d e ，n l e v e l ) = = t r u e ) f o re a c hc h i l do fp n o d e d i v i d ed o m _ t r e e ( c h i l d , n l e v e l ) ； ) e l s e p u tt h es u b t r e e ( p n o d e ) i n t ot h ep o o la sab l o c k ； 我们以图2 - 1 中的网页为例，在进行了一轮划分后，可以抽取出了v b l 、 v b 21 、v b 22 、v b 23 、v b 3 和v b 4 等分块并将这些分块存放在存储池中。图 2 - 1 中分块v b 2l 、v b 22 、v b 23 所在的子网页是一个t a b l e 结构，其d o m 树 如图2 - 6 所示。在分块抽取过程中，当遇到标签 时，这个t a b l e 结构只有 一个有效的子结点 ，即v b 21 、v b 22 、 v b 23 。由于第- - ( v b 21 ) 的背景色与 的背景色不一致，那么根据上面 定义的标准，需要将q 飞 划分，但是在这次划分中，第一个q d 并不被划分而是 作为一个分块存放在存储池中，第二和第三个 则被划分。最终，得到分块 v b 2l 、v b 22 、v b 23 。 山东大学硕士学位论文 2 5 探知分割符 圈2 - 6 分块抽取 在将所有分块抽取出来并存放在存储池中以后，接下来要进行的是分割符的 探知。分割符定义为网页中可见的、不与分块相交的水平或竖直线，这些水平或 竖直线最适合在视觉上区分网页中不同语义的内容。分割符表示为一个二元组的 形式：( p s ，只) ，其中，只为起始位置只为终点位置，分割符的宽度可以通过计算只、 只的差值得出。 2 5 1 分割符探知算法 由于分割符有水平、竖直两类，所以在分割符探知过程中，需要分别从水平、 竖直两个方向进行探知，其算法描述如下： ( 1 ) 初始化分割符序列。在初始情况下，分割符序列中只有一个初始分割符 魄，只。) ，此分割符的大小与存储池中整个页面的大小一致。 ( 2 ) 随着分块不断被抽取出来加入存储池中，需要对分割符进行不断调整，规 则如下： 如果分块包含在分割符内，则将分割符划分； 山东大学硕士学位论文 如果分块与分割符相交，相应改变分割符的大小； 如果分割符贯穿分块，则删除分割符。 ( 3 ) 删除位于存储池4 个边的分割符。 在实际执行时，可以按照上述算法描述先进行水平方向的操作，再进行竖直 方向的操作，最终得到所有分割符。图2 - 7 ( 1 ) ( 2 ) 所示为分割符探知过程，其中， 深色矩形代表网页中的分块。 图2 - 7 分割符探知过程 图2 - 7 ( 1 ) 为水平方向操作。在初始隋况下，存储池中只有一个分割符，即整个 存储池。当把第一个分块投入池中后，根据算法中的( 2 ) 一，分割符划分成s l 、 s 2 。同理，分块2 、3 进入后，得到s 1 、s 2 、s 3 和s 4 。当最后一个分块4 进入存 储池中，根据( 2 ) 一，调整s 2 的大小，根据( 2 ) 一，删除s 3 。最后，根据( 3 ) 删 除上下两个边沿的分割符，就得到了水平方向的分割符s 2 。同理，竖直方向的分 割符探知过程如图2 - 7 ( 2 ) 所示。 2 5 2 分割符的权重设置 由原始网页划分成的分块都具有一定的语义内容，而这些分块依靠分割符进 山东大学硕士学位论文 行区别，因而分割符的权值可以依据相邻分块间内容上的差异度来进行设定。具 体规则如下： ( 1 ) 分割符两边分块的距离越远，分割符的权值越大； ( 2 ) 分割符与某些特定的h t m l 标签( 如标签 ， ； 量鲁拦 l 由寨睿如暇军文曩芏与匿贼戢照嘏场鞭酾 山柬尖掌蚪军艺术尧岢业招生擅l i 昕年临床孵礤士啦掌髓据誊篱重 i 蝌牟弼雠力率糟顿圭学位撼生糟t 图2 - 8 分割符及权重 以图2 _ 6 中第二个 ( v b 2 _ 2 ) 为例，经过分块抽取得到5 个分块，探知得 到4 个分割符。根据上述规则( 4 ) ，分块3 为普通字体而分块4 为加深字体，所以 它们之间的分割符权重要大一些，其余分块之间分割符权重相同且比分块2 、3 之 间的分割符权重小，体现在图2 8 中为分割符的粗细不同，越粗表明权重越大。 2 6 网页结构的构建 当对一个网页进行了分块抽取和分割符的探知、赋权值等操作以后，就可以 山东大学硕士学位论文 根据网页内容构建网页的结构框架了。由权值最小的分割符开始，将其两边的分 块合并构成新的分块，重复执行此过程，直至遇到权值最大的分割符。新分块的 d o c 值根据分割符的权重设置。在合并操作结束以后，检查合并后的分块是否满 足粒度需要( d o c 值大于p d o c 值) 。如果满足需要，则根据合并结果构建起整个网 页的内容结构：如果不满足，则要重新进行新的子分块抽取操作。 以图2 - 8 为例，在第一轮合并操作过程中，分割符1 、2 、4 的权值最小，所 以将这些分割符两侧的分块合并，如分块v b 2221 和分块v b 2222 通过合并 构成新的分块v b 222 。经过两轮合并，遇到了权值最大的分割符3 ，则分块 v b 22l 和v b 222 不再合并，分块合并操作结束。分块v b 221 和v b 22 2 都是v b 22 的叶子节点，检查一下它们是否满足粒度要求。最终，构建起整个网 页的内容结构。 2 7 本章小结 在本章中，我们主要讨论了基于视觉特征的网页分割算法，算法的关键在于 分块抽取、分割符探知和构建网页内容结构这三个步骤。在结果满足预先设定的 粒度之前，分割算法是循环执行的。分割算法的流程如图2 9 所示。 分割算法得到的结果适用于许多实际应用，在下一章中，我们将详细讨论如 何利用分割算法的结果进行中文网页分类。 图2 9 基于视觉特征网页分割算法流程 山东大学硕士学位论文 第3 章支持向量机理论在网页分类中的应用 3 1 支持向量机理论 3 1 1 支持向量机概述 支持向量机( s u p p o r tv e c t o rm a c h i n e ，s 吗由v 印l l i k 及其合作者发明，在1 9 9 2 年 计算学习理论的会议上介绍进入机器学习领域，之后受到了广泛的关注。在上个世 纪9 0 年代中后期得到了全面深入的发展，现在已成为机器学习和数据挖掘领域的标 准工具，其算法实现策略以及实际应用也发展迅速。 支持向量机是机器学习领域若干标准技术的集大成者。它集成了最大间隔超平 面、m e r c e r 核、凸二次规划、稀疏解和松弛变量等多项技术。在若干挑战性的应用 中( 如文