（计算机应用技术专业论文）自动文本摘要方法的研究及应用.pdf

y 6 0 8 4 9 0 华北电力大学 ( 北京)硕 i _ 论文 摘要 随着万维网 ( www)的迅猛发展，用户可在线获得的信息量呈指数级增长。 面对如此浩瀚的信息， 人们迫切需要寻找一条能够快速、 准确获得所需信息的途径， 因而出现了多种文本处理技术，包括信息检索、文本分类、文本摘要等。其中文本 摘要技术因其既可以压缩文本，减少用户的浏览负担，又可以为其他文本处理技术 提供支持，逐渐成为国内外研究的热点。 本文就文本摘要进行了较为系统的研究:首先全面系统地综述了自动文本摘要 的相关问题和技术;然后根据网页自身的特点 ( 如结构、链接等) ，提出了一种基 于网页分割技术的文本摘要算法;其次鉴于 自动摘要能够有效除去噪声、提取出文 章的主题内容的特点，我们把 自 动摘要技术运用在网页分类上，实验证明这种方法 能够使分类性能大大提高:在论文的最后，介绍了我们的网络挖掘系统一we b me 中的自动摘要子模块的设计 与 实现。 关键词:文本挖掘，文本摘要，网页摘要，网页分类 abstract a s a c c e s s i b l e o n l i n e t e x t u a l d a t a a n d i n f o r m a t i o n c o n t i n u o u s l y e x p o n e n t i a l l y p r o l i f e r a t e s o n i n t e r n e t , t h e t r a d i t i o n a l p r o c e s s i n g a n d m a n a g e me n t t e c h n i q u e s o n t e x t d a t a c a n n o t s a t i s f y t h e v a r i o u s d e m a n d s o f u s e r s a n y l o n g e r . i n d e ma n d o f a n e f f i c i e n t a p p r o a c h f o r s e a r c h i n g t h e u s e f u l i n f o r m a t i o n , r e s e a r c h a n d a p p l i c a t i o n o f a u t o ma t i c s u m m a r i z a t i o n h a s r e v i v e d t h e s e y e a r s . i n o r d e r t o s a t i s f y t h e r e q u i r e m e n t s o f t h e o ry r e s e a r c h a n d r e a l - w o r l d a p p l i c a t i o n , t h i s p a p e r s t u d i e s o n t h e s u mm a r i z a t i o n t e c h n o l o g y s y s t e mi c a l l y . f i r s t w e o v e r v i e w a u t o m a t i c s u m ma r i z a t i o n t e c h n o l o g i e s , a n d t h e n w e p u t f o r w a r d a n e w w e b p a g e s u m m a r y a l g o r i t h m b a s e d o n p a g e s e g m e n t a t i o n . n e x t w e u s e w e b s u m m a r i z a t i o n m e t h o d s t o e x t r a c t m o s t r e l e v a n t f e a t u r e s f r o m w e b p a g e s t o i m p r o v e t h e a c c u r a c y o f w e b c l a s s i f i c a t i o n . a n d l a s t l y w e i n t r o d u c e o u r a u t o m a t i c s u mm a r y m o d u l e , o n e o f t h r e e m o d u l e s i n o u r w e b m i n i n g s y s t e m - we b m e , i n d e t a i l . c o n g y a n ( c o m p u t e r a p p l i c a t i o n t e c h n o l o g y ) d i r e c t e d b y p r o f . wa n g y o n g k e y wo r d s : t e x t mi n i n g , t e x t s u mma r i z a t i o n , we b p a g e s u m ma r i z a t i o n , we b p a g e c l a s s i f i c a t i o n i 华北电力大学 ( 北京)硕 论文 主要符号表 1 句 号 句 号的形式为 “ 。 ” 。陈述句末尾的停顿。用句号。语气舒缓的祈使句末尾，也 用句号。 2问号 问号的形式为 “ ? 尸 。疑问句末尾的停顿，用问号。反问句的末尾，也用问号。 3 叹号 叹号的形式为 “ ! ” 。感叹句末尾的停顿，用叹号。语气强烈的祈使句末尾，也 用叹号。语气强烈的反问句末尾，也用叹号。 4逗号 逗号的形式为 “ ， ” 。 句子内部主语与 谓语之间 如需 停顿， 用逗号。句子内 部动 词一 与宾语之间如需停顿，用逗号。句子内部状语后边如需停顿，用逗号。复句内各 分句之间的停顿，除了有时要用分号外，都要用逗号。 5顿 号 顿号的形式为 “ 、 ” 。句子内部并列词语之间的停顿，用顿号。 6 分号 分号的形式为 “ : ” 。复句内部并列分句之间的停顿，用分号。非并列关系 ( 如 转折关系、因果关系等)的多重复句，第一层的前后两部分之间，也用分号。分行 列举的各项之im，也可用分号。 7冒号 冒号的形式为 “ : ” 。用在称呼语后边，表示提起下文。用在 “ 说、想、是、证 明、宣布、指出、透露、例如、如下”等词语后边，表示提起下文。用在总说性话 语的后边， 表示引起下文的分 说。 用在需要解释的词语后边， 表示引出解释或说明。 总括性话语的前边，也可以用冒号，以总结上文。 8 引号 引号的形式为双引号 “ “ ” ”和单引号 “ ” ， 。 行文中直接引用的话， 用引号标示。 需要着重论述的对象，用引号标示。具有特殊含意的词语，也用引号标示。引号里 面还要用引号时，外面一层用双引号，里面一层用单引号。 9括号 括号常用的形式是圆括号 “ ( ) ” 。此外还有方括号 “ 仁 ” 、六角括号 “ ”和方 头括号 “ 【 】 ” 。行文中注释性的文字，用括号标明。注释句子里某种词语的，括 注紧贴在被注释词语之后:注释整个句子的，括注放在句末标点之后。 t o 破折号 破折号的形式为 “ 一一” 行文中解释说明的语句，用破折号标明。话题突然 转变，用破折号标明。声音延长，像声词后用破折 号。事项列举分承，各项之前用 t v 华北电力大学 ( 北京)硕 论文 破折号。 1 1 省略号 省略号的形式为 “ ” ，六个小圆点，占两个字的位置。如果是整段文章或 诗行的省略，可以使用十二个小圆点来表示。引文的省略，用省略号标明。列举的 省略，用省略号标明。说话断断续续，可以用省略号标示。 1 2 着重号 着重号的形式为 “ ， ” 。要求读者特别注意的字、词、句，用着重号标明。 1 3连接号 连接号的形式为 “ 一” ，占一个字的位置。连接号还有另外三种形式，即长横 “ 一一”( 占两个字的长度) 、半字线 “ 一 ”( 占半个字的长度)和浪纹 “ 一 ”( 占一个 字的长度) 。两个相关的名词构成一个意义单位，中间用连接号。相关的时间、地 点或数目之问连接号，表示起止。相关的字母、阿拉伯数字等之间，用连接号，表 示产品型号。几个相关的项目表示递进式发展，中间用连接号。 1 4间隔号 问隔号的形式为 “” 。外国人和某些少数民族人名内各部分的分界，用间隔号 标示。书名与篇 ( 章、卷)名之间的分界，用问隔号标示。 1 5书名号 书名号的形式为双书名号 “ ”和单书名号 “ m m r 等; 各种混合方法的出现，如词汇链，r s t树等。 随着网络资源的爆炸式增长，文本摘要在研究领域和商用领域均展现了很好的 发展前景，尤其是基于统计的方法，由于其健壮性和实用性而得到了厂泛的应用。 另外随着 自 然语言处理技术的发展，应用于文本自动摘要的方法也会越来越多。而 且出现了许多新的研究和应用领域:多文本摘要、多语言摘要、多媒体摘要等。 2 . 3自 动文本摘要的类型 按照不同的分类标准，可以将文本摘要分为以下几种类型: ( 1 )根据摘要功能的不同，可以将摘要分为:指示摘要 ( i n d i c a t i v e ) 、信息摘要 ( i n f o r m a t i v e )和评价摘要 ( c r i t i c a l ) . 指示摘要是用来帮助用户决定是否需要阅读原文档的， 用户可以通过指示摘要 来决定是否需要进一步阅读原文档。信息摘要在一定程度上覆盖了原文档中所有的 重要信息，可以作为原文档的某种替代，用户不再需要考虑原文档。介于这两种摘 要之间的是评价摘要，表述作者的主要观点，含有对文档内容的评价。 ( 2 )根据与原文档关系的不同，可以将摘要分为:抽取 ( e x t r a c t i o n )和摘要 ( a b s t r a c t i o n) . 抽取的内容完全由从输入文档中拷贝的内容组成，抽取可以由原文中的句子组 成，还可以是短语的列表，例如关键词、专有名词、剪枝的句子等。摘要的内容则 包含了一些输入文档中没有表达的东西。例如，在摘要中可能加入了对原文的评价 等，摘要中涉及的原文中的句子也不需要完全对应。 ( 3 )根据对象的不同，可以将摘要分为:单文档摘要和多文档摘要。 单文档摘要是对单个文档产生摘要，多文档摘要是指对具有相关主题或内容的 文档集产生的摘要。 ( 4 )基于用户类型的摘要分类:卞题摘要和普通摘要。 以用户 ( 卞题或查询)为中心的方式产生摘要，适应于特定用户或用户组的需 求。这就意味着摘要着重考虑用户感兴趣的东西。普通摘要面对的是一般的、广泛 的用户，是基于文本内容的。 ( 5 ) 从机器学习的 角度分类: 有指导的 摘要和无指导的摘要 有指导的 摘要 ( s u p e r v i s e d s u m m a r i z a t i o n )需要 提供一定的 训练数据， 也就是 文本和摘要组成的样本对。把摘要问题转化为一个分类的问题，并利用前面提到的 华北电力大学 北京)硕士论文 一些文本分类的方法来训练生产摘要器 ( s u m m a r i z e r ) 。 无指导摘要则不需要训练数 据，直接在文本上生产摘要。 2 . 4自动文本摘要的方法 从摘要技术的实现方法上来划分， 文本摘要技术大致可分为抽取 ( e x t r a c t i o n ) 和摘要 ( a b s t r a c t i o n )两类方法。其中这两类方法的处理对象都可以是单文档或 是多文档的，实现技术也可以是有指导的或是无指导的。 e x t r a c t i o n的实现技术大 部分是基于统计方法和浅层语义理解， 而a b s t r a c t i o n 的 实现则是以自 然语言 理解 ( n l p ) 技术为基础的。 近几年来， 受限于n l p 技术的发展， a b s t r a c t i o n发展缓慢， 而 e x t r a c t i o n则由于其健壮、实用的性能得以在研究领域和商用领域大放异彩。 在本节中，这两种方法将通过经典的算法进行深入的分析。 2 . 4. 1 e x t r a c ti o n 正如在前面所定义的， e x t r a c t i o n 是指最终摘要的内容完全是原文档内容的部分 拷贝，目前，基于抽取的摘要基本上是以句子为抽取单元的，因为基于句子的抽取 方法尽管可能会使句间存在不连贯，但句子本身是保持一致性和连贯性的;基于段 落的抽取会造成抽取出的摘要冗余度较大，并且摘要的长度难以控制。因此本文中 所介绍的抽取方法基本是基于句子抽取的，它的方法可以用图2 - 1 概括如下: 图 2 - 1基于抽取的自动文本摘要方法 华北 电力大学 北京 )硕 : 论 文 从图中可以看出，摘要过程分为三个阶段:分析、转化、合成。 分析:这一阶段卞要完成对输入文档的分析，对原文档进行各种特征的提取， 这些特征可以是基于词频等的表面级信息，也可以是基于修辞结构的论述级信息。 主要包括:关键词 ( 指在文中经常出现用来代表文章主题的词汇 ) ，加权词 ( 指在 标题，用户查询中出现的单词) ，位置信息 ( 指句子段落等在文章中出现的位置， 如文章的6句、末句等标示卞题的位置信息) ，固定短语 ( 如线索词，指示词等) ， 结构信息 ( 指修辞结构信息) ，内聚性信息 ( 用于连接文本单元的基于重复、同义、 限制等的连接信息) 。 转化:这一阶段的任务是完成文档从内容表示到摘要表示的转化。从图中可以 看 出 ， 其 方 法 是 通 过 把 分 板 阶 段 所 得 到 的 特 征 进 行 线 性 加 权合 并 ， 从 而 得到 文 中 句 子的最终加权值。 合成:将摘要表示经过平滑、加工后以某种顺序输出，形成一个具有可读性， 能较准确、较全面概括原文主题内容的文摘。例如，在单文档摘要中，最终的摘要 在经过加权排序后是按原文顺序输出的，而多文档摘要中，最终的摘要可能按照年 代顺序，或是按句子权值大小输出。 2 . 4 . 1 . 1 e d u m u n d s o n i a n方法 e d u m u n d s o n i a n在 1 9 6 9年提出了一种基于词频、位置等表面形式特征的经典 摘要算法，这种算法至今仍然是很多基于抽取的摘要方法的核心思想。 这种算法的处理步骤为:计算词的权值一) 计算句子的权值一 对原文中所有的 句子按权值高低降序排列一 权值最高的若干句子被确定为文摘句一 将所有文摘 句按照它们在原文中的出现顺序输出。 e d m u n d s o n 选择文摘句的依据是文本的四种形式特征:f( 词频) 、t( 标题) 、 l( 位置)和 c( 线索词) ，他用一个简单的线性方程 w = a , c 十a , k 十a , t + a 止将四种 基本的句子选择方法集成在一 起。 其中: w代表句子的最终权重， c 代表线索词( c u e ) 的权值，k代表根据词频计算而得的关键词的权值，丁代表题名词( t i t l e ) 权值，l 代表位置 ( l o c a t i o n )权值 ，a a 2 , a , . a ; 为调一 节参数。 这种力法是一种基于单文档的无指导的摘要算法，它所依据的是文本形式上的 规律，避免了对语法和句法的考虑，因而易于实现，应用领域广泛。 2 . 4 . 1 . 2潜在语义分析法 ( l a t e n t s e m a n t i c a n a l y s i s ) g o n g y i h o n g和 l i u x i n提出了 一种基于潜在 语义分析和相关性计算的 方法 来进行摘要提取这种方法6先将文档分解成一个 “ 句子一词项”的矩阵，矩阵的 行为文档 中的词项，列表示为词项在句子中的权重。然后对矩阵做奇异值分解 华北电力大学 ( 北京)硕士论文 ( s v d ，s i n g u l a r v a l u e d e c o m p o s i t i o n ) 将矩阵 分解产生一个 索引矩阵， 利用这个 索引矩阵来选取合适数量的句子来组成摘要。s v d 能够建模不同词项的内部关联， 因此具有语义聚类词项和句子的能力。 它的主要步骤为: 1 将文档表示为句子一词项的矩阵 a ; 2 . 使用s o方法 将矩阵a分解为 a 二 u e v , ， 在奇异值空间中，每个句子被表示成 v ， 的列向量。 3 .设置 k 为 1 ; 4 . 选择在右奇异值中具 有最大索引值的第k 个句子，将它加入摘要中; 5 . k 加 1 ，重复步骤 4 ，直至所选取的摘要达到预先的设置。 这也是一种基于单文档的无指导的摘要方法。它除了使用文档的表面级信息， 如词频等，还使用了潜在语义的方法。 2 . 4 . 1 . 3 m m r - m d ( m a x i m u m m a r g i n a l r e l e v a n c e m u l t i d o c u m e n t )方法 多文档摘要同单文档摘要相比有许多相似之处，也有很多不同。在单文档中所 采用的一些特征都可以用在多文档中，包括:关键词、指示词、位置信息、修辞结 构等。多文档同时又有许多不同于单文档的特征，如在对多文档进行摘要时，是需 要将相似的文档或段落进行聚类的， 以此来抽取相关信息; 在多文档中进行摘要时， 因为是从相似的文档中来抽取信息，所以摘要不可避免的存在冗余，需要对最终的 摘要进行去冗余的处理;最终摘要顺序的排列也是不同于单文档摘要的，可能是按 照时间顺序来排列，也可能按照句子权重大小来排列。 m mr -md方法是基于 e d m u n d s o n核心算法的一种完善，同时它也是一种基 于用户查询的多文档摘要。它的目的是使文摘保持对用户查询或文档主题的最大相 关性，同时又使摘要的冗余度最低。 m mr -md的输入是己经聚类的给定文档的句子集， 其中句子和整个文档使用 v s m ( v e c t o r s p a c e m o d e l ) 来表示。 通过计算句子与 查询或主题的最大相似度， 和 与 现有文摘的最小相似度来得到最终的文摘。这样就保证了最与查询相关的句子被 抽取出，而最终的文摘冗余度又很低。 该方法的核心公式如下所示: m m r 一 m d 三 a rg m a x a s im ,( p u , q , 吼 ) 一 ( 1 一 幻 耀爹 s im , ( p ; , p , , c , s )1 其中s i m ， 是计算句子p ii 同 查询q和聚类c ;j 间的相似度，s i m : 计算句子 p 6 同被 抽 选出的摘要、聚类间的相似度，人是调整参数。 华北 电力大学( 北京)硕士论文 2 . 4 . 1 . 4有指导的摘要方法 在 自动文摘的研究领域，机器学习的力法也得到了广泛的应用。对机器摘要而 言，机器学习 的目 的就是通过训 练样本集对系 统的训练使系统获得 摘要提取器或摘 要提取规则。一个基于文本集的摘要提取过程如图2 - 2 所示。 一:一| 自动 全 成 的 摘 耍 结 具 图 2 - 2有指导的文本摘要方法 系统的输入是文本一 摘要对。 从训练文本中提取特征， 然后用对应的训练摘要标 记原文本特征向量。学习算法经过训练，可以利用产生的规则确定文本中的句子是 否应该包含在摘要中，从而实现对文本的自 动摘要。分类器的精度通过在测试文本 集上的测试获得。 该方法中有三个关键技术:文本特征选择、标记和学习算法。文本特征选择可 以包括句长、提示词、位置、主题词、关键词等离散特征;标记过程是指原文本与 对应摘要的匹配过程;学习算法最常用的贝叶斯算法。 2 . 4 . 2 a b s t r a c ti o n a b s t r a c t i o n是针对 e x t r a c t i o n 来说的， 它主要是 利用白 然语言处理技术对文 档 进行浅层的或是深层的理解，对其中的词项、句子进行重组或替代来形成摘要。总 体上可分为框架抽取和概念生成两种方法。 框架抽取方法是以文摘框架为中枢，分为选择和生成两个阶段。文摘框架是一 张中请表，它以空槽的形式提出应从原文中获取的各项内容在选择阶段，利用特 华北电力大学 ( 北京)硕士论文 征词从文本中抽取相关的短语或句子来填充文摘框架。在生成阶段，利用文摘模板 将文摘框架中的内容转换为文摘输出。文摘模板是带有空白部分的现成的套话，其 空白部分与文摘框架中的空槽相对应。 概念生成的方法最大的特点是对知识的利用，它不仅利用语言学知识获取语言 结构，更重要的是利用领域知识进行判断、推理，得到文摘的概念表示，最后从概 念表示中生成摘要。它首先借助词典中的语言学知识对原文中的句子进行语法分 析，获得语法结构树;然后运用知识库中的语义知识将语法结构转换成语义表示; 再根据领域知识在上下文中进行推理，并将提取出来的关键内容存入一张信息表; 最后将信息表中的内容转换为一段完整的文字输出。 a b s t r a c t i o n的缺点在于领域受限， 因为面向大规模真实语料的语法语义分析技 术尚未完全成熟，要想获得高质量的语言分析结果，就必须将待处理的语料限制在 某个范围之内，因此很难移植。并且机器产生的摘要可能会造成文摘的一致性和连 贯性等问题。 2 . 5 自动文本摘要的评价 自动文摘研究属于自然语言理解范畴， 因而对一个文摘系统的评价实际上就是 对一个 自 然语言理解系统进行评价。一般对于一个自然语言理解系统来说， 它的评 价方法是其研究的一个重要的组成部分， 但同时也是最容易引起人们争议的地方。 究其原因在于理解本质上是客观事物在人脑中的一种主观反映。既然是一种主观反 映， 就可能随着主体对象人的不同而不同， 甚至同一个卞体对象由于环境发生了变 化， 在不同的时刻也可能有不同的反映。正是由于理解是一种主观反映， 使得我们很 难制订一套客观的标准来评判一个自然语言理解系统。所以对自动摘要的评价也陷 入了相同的困境。 目前国内外 已经在研究中使用的评价方法有: 机器摘要与人下摘要( 专家摘要 或作者摘要) 进行比较;几个机器系统之间相互比较;生成的摘要 与 原文进行比较 ( 预先对原文进行分析， 找出文章中的主题， 以此来衡量摘要的质量) 等多种方法。总 结这些方法， j o n n e s . k . s . ( 1 9 9 8 ) 提出从) 义的角度将自 动文摘的评价方法大致分 为两类: 一种称作内部评价( i n t r i n s i c ) 方法， 它通过直接分析摘要的质量来评价文 摘系统。第二种称作外部评价( e x t r i n s i c ) 方法， 它是一种问接的评价方法， 将 自 动 文摘应用于某一个特殊的任务中， 根据摘要功能提高这项任务的效果来评价自动文 摘系统的性能。 利用 内部评价方法好处在于直接对获得的摘要进行分析， 比较有针对性， 特别 适合于研究者对 自己的系统进行内部评价时采用， 对系统改进研究具有较大的帮助 其评价过程也是对其系统的一种深入研究学习过程。缺陷在于该方法主观性太强， 华 北电力大学 ( 北京 )硕士 论文 不利于大规模地对多个文摘系统进行客观性评测。外部评价方法通常是在一个具体 的任务中来评价文摘系统， 因而相对于内部评价方法具有较少的主观性， 易于对多 个文摘系统进行评价。此外， 在特定应用中评价系统也有助于自动文摘系统在其他 领域中的应用研究。然而， 这类方法也具有一些缺点: ( 1 ) 每次评测只是针对一个特 定任务， 局限性太大， 不利于系统性能的全面改进。( 2 ) 由于情报处理工作中有各种 各样的任务， 所以评测方法种类繁多， 难以统一标准化。 华北电力大学 ( 北京)硕 t : 论文 第三章 基干网页分割技术的网页摘要算法 前一章介绍的主要是基于纯文本的摘要算法，但随着 i n t e rne t 的迅速发展，万 维网上的数据呈指数级增长，人们面临的不再单纯是结构化的文本数据，而是海量 的具有半结构化特征的网页数据。如何从这些数据中有效的提取出用户所需的信 息，网页摘要技术提供了有力的帮助。 网页摘要技术是由于处理 www 上不断膨胀的数据需要从文本摘要中发展而 来的，尽管两者之间有很多相似之处，但网页摘要由于网页的特殊性也有 自己的独 特之处， 一些文本摘要技术并不适用网贞摘要，即使可用也需要建立在对we b网页 进行预处理的基础上。本章从网页的结构特征出发，通过分析网页的结构和层次特 征，将网页分割成块，从中提取出网页的主体内容，从而提出了一种基于网页分割 技术的摘要算法。 3 . 1网页的结构特征 we b上的大部分文档用 h t ml来存储和传播。可以说 h t ml是一种简单的语 言，非常适合超文本、多媒体和显示简单的小文档。但是它不允许用户定义自己的 标签或者属性，使得用户无法从语义上限定他们的数据;不支持定义在表示数据库 模式或者面向对象的层次时需要的嵌套结构;也不提供允许应用程序检查重要数据 的结构合法性的语言规范。总的来说，h t ml侧重于外观和版面安排问题，而不是 结构化和模型化数据。 人们在设计网页的时候，总是准备了一定的素材，这些素材是设计者希望通过 网页传达给访问者的信息 ( 类似于通信中的信号) 。但是由于孤立的网页很难被访 问，设计者会增加一些内容来连接不同的页面，例如增加超链接目录或者具有搜索 功能的表单等。 增加的文字仅仅起向导的作用， 内容通常和页面原有的内容不重叠， 因而它们的加入会影响网页内容的原貌 ( 类似于通信中的噪声) 。 对于网页摘要来说，所应提取的是网页主题内容中最重要的信息，而网页除了 主题内容之外，还包括大量的无关信息。包括; . 多媒体信息:嵌入在网页中的声音、图像、v i d e 。 等信息; . 导航信息:用来指示用户链接到不同网页的链接信息; . 其他信息:广告、版权和地址信息等。 我们把网页设 计者为了辅助网站组织而增加的信息定义为 “ 噪声” ，把原本要 表达的文字素材称为 “ 主题内容” 。当噪声和主题内容己经混合在一个半结构化的 h t ml文件中时，想依据设计者的意图把两者分开并不是一件容易的事情。 通过对大量的网页结构进行分析，我们发现一种有趣的现象:人们在设计网页 时，通常把不同功能的信息用不同的格式来表示，例如背景颜色、字体大小、位置 华北电力人学( 北京) 硕士论文 等。所以我们考虑通过把网页分割成块来去除噪声、提取内容文本。 3 2 阿页分块模型 实际当中，人们在设计网页时，常常将网页分成多个区域，把不同主题、不同 作用的文字安排在不同的区域里，这样阅读起来会比较清晰。这种方法类似于报纸、 书刊、杂志中的排版。连贯的文字通常放在一起组成段落，并采用一致的版式表达， 而不相关联的内容则用不同的版式加以区分。 版式表达了内容的关联性。同一块内的文字，要么在内容上是连贯的：要么具 有相同或者并列的作用，总是有比较紧密的关系。在不同块之间则相互关系比较松 散，在语义上也不连贯。 由此启发我们对网页建立一种分块模型，语法表示如下： ：= ( 块 f 我们定义： “抉”是指关联文字的集合。同一块内的文字位置邻近，内容连贯或者作用相 同，具有一致的版式；“问隔”是对能在空问上或者内容上起分隔作用的标记而言 的。h t m l 提供了多种控制格式的标记，其中一些在空间上有分隔作用，例如，p 、 、 等，它们表现为较大的空行，起分隔段落的作用；另一些标记被用来对 内容做分隔，例如 ，它表现为水平线，人们习惯用它分隔关系松散的章节；还 有一些标记在空间上表现为分隔，同时也被用来表达在意义上比较完整和独立的文 字段，例如， 、 、 等。实验发现，在网页中连续出现多 个分隔标记是前后文字不关联的标志，我们把这些标记的集合称为“间隔”。其中 连续的含义是指在标记和标记之间不出现可在网页上显示的文字。集合元素个数的 最小值需要通过实验来确定，我们把它记作参数s ，s 是判断连续的分隔标记是否 能构成间隔的阈值。 我们知道，一个h t m l 文件是一串线性的字符流，如果把它看成一条线，把间 隔看成分割点，那么块就是相邻的两个分割点之间的文字段。显然，块和块之间不 会重叠。 根据这个分块模型的概念，我们实现了一个h t m l 解析器，它可以自动地将网 页划分成块。图3 - 1 所示为利用p a r s e r 将该网贞分割成6 个语义块，分割结果与人 1 ：丰观划分的结果基本一致。在网页中，标号为0 ，1 ，2 分别是图片，导航条和链 接信息等，3 为标题信息，4 为主题内容，5 是地址信息。分块的粗细程度可以由问 隔阂值s 来调节。 华北电力大学( 北京) 硕士论文 3 3 网页主题内容的提取 图3 - i 自动分块的网页 将网页自动分块后，下一步需要过滤噪音，将主题内容提取出来。因此，我们 提出一种算法来提取网页的主题内容：通过计算不同块之问的相似度，构造语义块 问的相似关系图，根据这个相似关系图来调整阚值，控制提取出的主题内容的大小。 我们定义每个语义块为图中的一个节点；如果两个块的相似度超过给定的闽 值，则认为这两个块有语义联系，这两个节点间建立一条边。跟多个节点都有语义 联系的节点被定义为核心节点，一个网页可以有多个核心节点，这在多主题网页中 经常出现，为了简单起见，这里我们是定义具有最大度节点为核心节点。选出核心 节点后，可以把与核心前点有语义关系的节点组合起来作为主题内容。通过调整相 似度阈值，我们可以抽取出那些相似度较高的块作为丰题内容。 基于前面的假设，即在同一语义块中的内容是相似的，那如果两个语义块问的 相似度比较高的话，我们可以认为他们是主题相关的。显而易见，那些与主题无关 的语义块问的相似度应该比较低，因为他们传达的是不同的信息，如版权信息，欢 迎信息，、一告等语义块与网页的内容快之阃几乎没有相似的内容。因此，通过这样 调整不同语义块问的相似度，可以抽取出网页的丰题内容，滤掉导航信息、j 、告等 噪声。 如果两个语义块b 1 、b 2 用向量x 、y 来表示，其中 x = ，y = y 】，y z , y 3 y n ，我们可以通过计算不同块问夹角余弦得到相似度 华北电力大学( 北京) 硕士论文 值，计算公式为： x , y k 跏，皇，垦) = t 尹一 掂挺善露) 表3 一l 为图3 1 所示网页节点间的相似度值，当我们取闽值为o 2 时，可以抽取 出3 、4 节点作为主题内容。从网贞的实际内容上看，我们抽取的结果也是十分合 理的。 ol23 4 5 01 0 0 0o 0 0 00 0 0 0谯o o o0 o o o0 0 0 0 l0 。0 0 01 o o o0 1 4 50 0 0 00 0 0 0o 0 0 0 2 o o o o ( z )文章结尾的段落的加权值为:0 . 1 ; ( 3 )位于段首的句子的加权值为:0 . 3 ; ( 4 )位于段尾的句子的加权值为:0 . 1 ; ( 5 )标题后紧邻的段落的加权值为:0 . 1 ; ( 6 )被抽取出的句子的单词数 1 0 . 根据词频、标题、关键词、段落等信息对词项进行加权相加后取算术平均得 句子的最终权值。 本方法中对 t f -i s f 方法所采用的加权公式为: w( t i ) = l o g ( t f + 1 ) * l o g ( n / n + 1 ) ( 其中t f为词项在某句中出现的频率， n为文章的总句数， n为出现该词的句 数，w( t i ) 为词项的权重。 ) 对句子的加权公式为: w (s ) = 艺 l w (t i ) l n w( s ) = c s * c p * w ( s ) ( c s为句子在段落中所处位置的权值，c p为句子所处段落的权值，n为句子的总 词数，w( s )为句子的临时权重，w( s ) 为句子的最终权重。 ) 最后根据用户所输入的压缩率和摘要方式， 计算出所要抽取的摘要， 将摘要 输出。 3 , 5小结 网贞的内容十分丰富，包含很多的视听信息，例如:纯文本、图像、v i d e o和 a u d i o等;从功能来说包括诸如内容文本、导航条、) 、 一 告和欢迎信息等信息。网页的 结构特点使得对网页进行摘要较之对纯文本进行摘要有更丰富的信息可以利用。这 z 2 华北电力大学 ( 北京)硕士论文 些可 用的标记 信息包括: t i t l e , b o d y , m e t a d a t a , h e a d i n g s , a n c h o r , u r l等等。 在本章中，我们根据这些网页的 h t ml 标记， 提出了一种基于网页分割技术的 自动摘要方法。 首先利用一个h t ml分解器根据网页内容功能的不同将网页分割成 语义块，然后在这些语义块上建立相似关系图，通过调整相似度闹值，达到提取网 页文本内容，除去噪声的目的。在得到网页的主题内容后，在此基础上运用基于统 计的方法进行自动摘要的抽取。通过对大量的实验结果的观察，我们发现这种方法 是行之有效的，能够达到提取主题，除去噪声的效果。在下一章中，我们将给出这 种方法与文本分类结合起来的实验数据，实验证明这种方法能够大幅度的提高网页 分类的性能。 华北电力大学 ( 北京)硕士论文 第四章 摘要技术在网页分类中的应用 4 . 1网 页分类技术简介 随着网 络技术的发展， 万维网上的网页数量迅速膨胀， g o o g l 。目 前己 经索引了 3 0 多 亿个网页， 能 否从 海量的互联网中迅速、 准确的搜索用户感兴趣的 信息是 对网 页分类技术的一个挑战。文本分类技术在信息检索 ( i r )领域进行了深入的研究， 而网页格式灵活、内容丰富、来源) “ 泛以及增长速度极快等特点对网页分类技术提 出了更高的要求，拥有海量数据的万维网也为网页分类的研究提供了丰富的实验平 台。因此，网页分类相关技术的研究正逐渐成为继文本分类之后机器学习领域的一 个新的研究热点。 4 . 1 . 1网页分类的难点 网页分类是在文本分类技术上发展起来的，但网页分类相对文本分类来说要难 处理的多，要考虑更多的因素，这卞要是由网页的特征决定的。首先，网页的格式 非常 灵活， 有h t m l , a s p , x m l 等多种 格式并 存; 而且由 于任何人、 任何单位都可以 把自己制作的网页发布到互联网上，因此网页的写作风格、网页的内容变化很大: 同时网页含有丰富的结构信息， 能否合理的利用这些信息， 必然影响分类器的性能。 网页中了结构信息以外，还有其它一些内容是对分类无益的。网页还有许多与 卞题无关的内容，如版权信息、欢迎信息等，这些构成网页的噪声，如果不能有效 的过滤掉这些噪音，网页分类的性能会很低，因此，这也是网页分类的难点所在。 4 . 1 . 2网页分类算法 下面我们介绍几个网页分类算法，本文认为它们代表网页分类的几个主要研究 方 向。 4 . 1 . 2 . 1概率模型方法 贝叶斯算法是一种基于概率模型进行网页分类的算法。该算法首先提出一些关 于待分类网页产生方式的假设，然后建立一个能体现这些假设的随机模型，再根据 训练集估计这个随机模型的参数，最后把待分类网页按贝叶斯规则标记为最有可能 产生这个网页的类。朴素贝叶斯算法是所有贝叶斯算法中最简单一种，它基于 “ 简 单贝叶斯”假设，也就是 “ 表示网页的各个特征分量之问是相互独立的” 。朴素贝 叶斯算法主要包括以下两个计算步骤:第一步，计算特征词属于每个类别的儿率向 量，( w , w , , w , . . . . . . w) 其中， w , =p ( w k c 华北电力大学 ( 北京)硕士论文 卜艺 id1 i n ( 二 * ， j ) 1v i + e 巴 y o ,i n ( w d . ) 第二步， 在新 we b网页到达时，根据特征词分词， 然后按下面的公式计算该文 本 d ; 属 于 类 c ; 的 几 率 :p ( c ; i d ,; 6 ) 二 p ( c l i 41 c = , p ( w . c i ;b ) n (w k,d,) 裂, p ( c , i b ) l l k d p ( w k i c矿(w d ;) 其中，p ( c ; 1 0 ) c i 训 练 文 档 数 总训练文档数 ，p ( c , i b )为相似含义，i c!为类的总数， n ( 嗽， 试 )为 嗽 在 d ， 中 的 词 频， n 为 特 征 词总 数。 分 类 时， 把d ， 分 到 几 率 最 大 的类别中。 4 . 1 . 2 . 2关系学习 ( r e l a t i o n l a l e a r n i n g )方法 由于一阶谓词的描述能力比陈述式强， 使用关系学习方法能够有效的利用网贞 之间的链接信息。象c 4 . 5 / c a r t 等决策树学习算法，由于使用陈述式的描述规则， 无法利用对象之间的关系信息，限制了学习算法的性能。关系学习方法用于网页分 类，巧妙的使用一阶谓词描述网页特征和网页之问的关系，使用归纳学习算法进行 归纳学习，得到分类规则。 有不少学者 在这个 方向 进行了深 入的研究工作。 c o h e n 的 f l i p p e r 系统 把关系学 习方法用于文本分类，p a r s o n 使用p r o g o l 算法结合w o r d n e t 中的语义信息进行网页 分类。c m u 大学s l a t t e r y 和m i t c h e l l 成功的将q u i n l a n 的f o i l 归纳算法用于网页分 类。我们主要介绍s l a t t e r y 的工作。他使用三类谓词表示所有网页: h a s w o r d ( p a g e ) ， 表示网页p a g e 中出现 w o r d 这个 特征词: l i n k _ t o ( p a g e l , p a g e 2 ) ，表示网页p a g e l 中有一个链接指向网页p a g e 2 ; c l a s s _ n ( p a g e ) ， 表示网页 p a g e 属于第 n 类。 将所有网页 用谓词 表示， 然后用 f o i l 进行归纳学习。 s l a t t e r y 在 w e b k b 数据集 上进行了大量的试验。 试验结果显示使用关系学习方法进行网页分类的性能不低于传统的文本分类 算法。当存在h u b 网贞时，通常h u b页指向的网页属于相近的类，使用关系学习方 法能够发现类似的规律，而且学习到的规则容易解释。 4. 1 . 2 . 3 v a p n (s rm ) , 支持向量机( s v m ) 方法 i k教授高瞻远瞩，对统计学习理论深入分析，提出了结构风险最小化原则 在此理论基础上发展起来的s v m 方法，能够有效的解决小样本集的机器 华北电力大学 ( 北京)硕士论文 学习问题，s v m 已经被广泛应用在多个领域。j o a c h i ms 最早将 s v m 方法成功应用 到文本分类中， 并取得了非常高的分类性能。由 于 s v m 方法解决 分类问 题的 关键 是选择合适的 核函 数，因 此随着 s v m 方法在文本分类领域研究的不断 深入，出 现 了 许多 新的 核函 数。 j o a c h i m s 使用多 项式核函数、 r b f 核函数和s i g m o i d 核函 数进 行文本分类。 h u m a l o d h i 和j o h n s h a w e - t a y l o r 等 人将字符串核函数( s t r i n g k e r n e l ) 引入文本分类，这种核函数可以有效利用特征词的顺序信息而且通过近似方法降低 了 算法的 执行时p 13 ; n e l l o c r i s t i a n i n i 等人 则使 用语义核函数( l a t e n t s e m a n t i c k e r n e l ) 设计文本分类器。 基于核函数的学习机器所需的全部信息即核矩阵 k ( k e r n e l ma t r i x ) , k = (k ( x , , x ; ) 7 i= t 矩阵中的 元素描述样本之何的相 似性。s a i t o h 指出 如果函数k ( x , 2 ) 在有限 集合 上计算得到的 矩阵 满足对称、正定， 则k ( x , z ) 就是 有效的 核函 数。 另外， 容易证明 对 于系 数。 a _ 1 ， 如果戈( x , z ) , k z ( x . z ) 为 核函 数， 则. 1 k , ( x , z ) + ( 1 一 幻 k 2 ( x , z ) 为 有效核函数。这就为我们构造核函数提供了两种不同的方法，一是利用专家的先验 知识构造符合条件的核矩阵，或者组合己有的核函数构造新的核函数。 j o a c h i m s 从理论上证明组合独立的核函数在满足一定条件下可以设计出推广能 力更好的学习机器，并成功的通过组合核函数的方法把支持向量机用于网页分类。 他用