（计算机软件与理论专业论文）基于聚类算法的中文自动文摘方法研究.pdf

摘要 随着搜索引擎技术的发展，人们能够通过搜索引擎方便的得到自己想要的各 种信息，无论哪方面的内容，这些搜索引擎都能帮助人们快速地找到相关的网页。 用户只需输入一些关键字，它们马上就会搜索出相关的网页。但搜索引擎不能提 供给用户简洁、直接的答案，用户很难快速准确地定位到所需的信息。自动文摘 技术的目标是致力于将信息全面的、简洁的文档直接呈现给用户，提高用户获取 信息效率，所以说自动文摘技术的重要性是不言而喻的，它的应用前景将非常广 泛。 针对目前中文自动文摘冗余度过高的问题，本文将潜在语义分析，h o w n e t 概 念抽取与句子聚类方法相结合。利用潜在语义分析与h o w n e t 概念抽取来计算句子 相似度。在进行潜在语义分析的时候，对词频矩阵进行了加权转换，提高了句子 相似度计算的准确性。 研究了目前主流的句子聚类算法，对比分析了层次聚类算法与划分聚类算法 的优点与不足，提出了一种新的混合聚类算法。将层次聚类算法( a g n e s ) 与k 一中心 聚类算法( k - m e a n s ) 相结合对文本中的句子进行聚类，提高了文本主题划分的准确 性。 设计并实现了一个原型系统来验证本文所提出的方法，并在此原型系统的基 础上设计了两个实验。实验一比较了两种句子相似度计算方法所得文摘的准确率 与召回率；实验- n 比较了三种聚类算法的聚类划分准确度。最后对实验结果进 行了详细的分析。 关键词：自动文摘；句子相似度；聚类算法 a b s t r a c t w i t ht h ed e v e l o p m e n to fs e a r c he n g i n et e c h n o l o g y , p e o p l ec a l lu s ev a r i o u ss e a r c h e n g i n e st of i n dt h ei n f o r m a t i o nt h e yn e e d p e o p l ee n t e rs o m ek e y w o r d sa n dt h es e a r c h e n g i n ew i l lr e t u r nt h er e l a t e dw e bp a g e s u n f o r t u n a t e l y , s e a r c he n g i n e sc a n n o tr e t u r n c o n c i s ea n s w e r st ot h eu s e r s s oa u t o m a t i cs u m m a r i z a t i o nt e c h n o l o g yb e c o m e sm o r e a n dm o r ei m p o r t a n t ，a n di th a sa ne x t e n s i v ea p p l i c a t i o np r o s p e c t a st os o l v et h er e d u n d a n c yp r o b l e mi nc h i n e s ea u t o m a t i cs u m m a r i z a t i o n ，w e c o m b i n el a t e n ts e m a n t i ca n a l y s i s ( l s a ) ，h o w n e ta n ds e n e n c ec l u s t e r i n ga l g o r i t h mt o g e n e r a t ec h i n e s ea u t o m a t i cs u m m a r i z a t i o n w eu s el s aa n dh o w n e tc o n c e p t e x t r a c t i o nt oc o m p u t et h es i m i l a r i t yo fs e n t e n c e s ，w h i c hi n c r e a s et h e a c c u r a c yo f s e n t e n c es i m i l a r i t yc o m p u t i n g o nt h eo t h e rh a n d ，w ed on o tu s eas i n g l eh i e r a r c h i c a lc l u s t e r i n ga l g o r i t h mo r p a r t i t i o nc l u s t e r i n ga l g o r i t h m ，i n s t e a dw eu s eam i x e da l g o r i t h mi n s t e a d ，w h i c hm i x b o t hh i e r a r c h i c a l c l u s t e r i n ga l g o r i t h m a n dp a r t i t i o n c l u s t e r i n ga l g o r i t h m t h e e x p e r i m e n ts h o w st h a tt h eh y p e rc l u s t e r i n ga l g o r i t h mh a sab e t t e rr e s u l t w ed e s i g na n dd e v e l o pap r o t o t y p et ov e r i f yt h em e t h o d sr e p r e s e n t e di nt h i s d i s s e r t a t i o n ，a n dd e s i g nt w oe x p e r i m e n t su s i n gt h i ss y s t e m e x p e r i m e to n ec o m p a r e st h e p r e c i s i o na n dr e c a l lr a t eo ft h et w os e n t e n c es i m i l a r i t yc o m p u t i n gm e t h o d s e x p e r i n e t t w oc o m p a r e st h ec l u s t e r i n ga c c u r a c yo ft h r e ec l u s t e r i n ga l g o r i t h m s i nt h ee n d ，w e a n a l y s i st h ee x p e r i m e n tr e s u l t si nd e t a i l k e y w o r d s ：a u t o m a t i cs u m m a r i z a t i o n ；s i m i l a r i t yo fs e n t e n c e s ；c l u s t e r i n ga l g o r i t h m 厦门大学学位论文原创性声明 本人呈交的学位论文是本人在导师指导下，独立完成的研究成 果。本人在论文写作中参考其他个人或集体已经发表的研究成果，均 在文中以适当方式明确标明，并符合法律规范和厦门大学研究生学 术活动规范( 试行) 。 另外，该学位论文为() 课题( 组) 的研究成果，获得() 课题( 组) 经费或实验室的 资助，在() 实验室完成。( 请在以上括号内填写课 题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特 别声明。) 声明人( 签名) ：形j 酝 力印年c 7 月 日 厦门大学学位论文著作权使用声明 本人同意厦门大学根据中华人民共和国学位条例暂行实施办 法等规定保留和使用此学位论文，并向主管部门或其指定机构送交 学位论文( 包括纸质版和电子版) ，允许学位论文进入厦门大学图书 馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国 博士、硕士学位论文共建单位数据库进行检索，将学位论文的标题和 摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。 本学位论文属于： () 1 经厦门大学保密委员会审查核定的保密学位论文， 于年月日解密，解密后适用上述授权。 2 不保密，适用上述授权。 ( 请在以上相应括号内打“”或填上相应内容。保密学位论文 应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密 委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认 为公开学位论文，均适用上述授权。) 声明人： 密勿 如a 1 年6 月乡日 第一章绪论 1 1 研究的目的和意义 第一章绪论 中文网页自动摘要课题隶属于“十一五 国家高技术研究发展计划( 8 6 3 ) 重点 课题项目跨媒体海量信息融合与智能内容搜索引擎产品开发。此项目实现用 母语来检索其它语言的文档，并且检索结果也通过机器翻译用母语来呈现。这样 的系统可以带给用户更好的搜索体验。它主要内容包括检索词扩展翻译，跨语言 摘要的生成，解码空间的缩剪，管理翻译记忆。而我的研究任务是对检索结果网 页生成中文自动文摘。 随着搜索引擎技术的发展，人们能够通过搜索引擎方便的得到自己想要的各 种信息，比较有名的搜索引擎有g o o g l e 、s o h u 、y a h o o 等。无论哪方面的内容， 这些搜索引擎都能帮助人们快速地找到相关的网页。用户只需输入一些关键字， 它们马上就会搜索出相关的网页。但搜索引擎不能提供给用户简洁、直接的答案， 因为通过现有的搜索引擎存在以下问题：1 返回的相关网页太多，有大量文本是 重复和相似的，用户很难快速准确地定位到所需的信息。2 返回答案的是以文档 为单位的，而用户所要的答案仅仅是其中的一部分，或者是某个句子，或者是某 个段落，甚至是某些文档的汇总。自动文摘技术的目标是致力于将信息全面的、 简洁的文档直接呈现给用户，提高用户获取信息效率，所以说自动文摘技术的重 要性是不言而喻的，它的应用前景将非常广泛。 目前自动摘要的主要方法有三种：自动摘录，基于理解和信息抽取。自动摘 录将文本视为句子的线性序列，将句子视为词的线性序列。它通常分四步进行：1 计算词的权值；2 计算句子的权值；3 对原文中的所有句子按权值高低降序排列， 权值最高的若干句子被确定为文摘句；4 将所有文摘句按照它们在原文中的出现顺 序输出。自动摘录能够适用于非受限域，这是它突出的优点。但是自动摘录的质 量很不稳定。当加权函数调整时又总是顾此失彼，对这一类文章的效果好了，对 另一类文章的效果又差了。而基于理解的自动文摘通常有以下步骤：1 语法分析； 2 语义分析；3 语用分析和信息提取；4 文本生成。基于理解自动文摘的不足在于 基于聚类算法的中文自动文摘方法研究 领域严格受限。基于理解的文摘方法需要对文章进行全面的分析，生成详尽的语 义表达，但这对于大规模真实文本而言是很难实现的。而基于信息抽取方法生成 的摘要使用模板来生成摘要，使得文摘的语言千篇一律，十分呆板。 对于文本摘要，传统的算法并不能应对文本所特有的高冗余度。我们把聚类 的思想应用到文本摘要上，对文本中的句子进行聚类，再从各个主题里抽取出重 要的句子来组成摘要。在计算句子相似度的时候，我们使用了两种不同的方法： 基于潜在语义分析的语义空间和基于h o w n e t 的概念获取，提高了句子相似度计算 和文本主题划分的准确性。 1 2 主要研究工作和创新点 1 2 1 主要研究工作 充分的调研是做好本课题的必要条件，针对本文课题的研究对像及目的，本 文主要做了以下工作： 1 研究了基于潜在语义的句子相似度计算问题，将句子向量从词形向量空间 映射到潜在语义空间，获取句子的语义结构以消除词之间的相关性，可以 解决特征间的“斜交”问题，从而提高句子相似度计算的准确性。 2 将h o w n e t 概念获取应用于自动文摘，以概念( i 百- j 义) 作为义项取代词语， 用概念统计代替传统的词频统计，建立基于概念统计的向量空间模型，对 句子集合进行聚类划分，最后计算句子重要度，抽取文摘句。 3 为了克服目前句子聚类算法存在的局限性，提出了一种新的混合聚类算 法。首先使用层次聚类算法对句子进行初始聚类，其次用得到的聚类类别 数目作为划分聚类算法( 如k m e a n s ) 的k 值，最后使用划分聚类算法 得到最终的聚类结果。 1 2 2 本文的创新点 本文的创新点归纳如下： 1 在句子聚类的过程中，为了克服传统方法在句子相似度计算上的局限性， 本文提出了两种新的计算方法：基于潜在语义分析( l s a ) 的句子相似度计 2 第一章绪论 算和基于h o w n e t 概念抽取的句子相似度计算。将传统的向量空间模型转 换成潜在语义分析和h o w n e t 概念空间。实验结果表明两种计算方法生成 的文摘都有较好的召回率和准确率。 2 为了解决传统句子聚类算法聚类划分准确度不高的问题，本文在聚类分析 算法的设计上，并没有采用单一的层次聚类算法或者划分算法，而是结合 层次聚类算法( a g n e s ) 和划分算法( k - m e a n s ) ，提出了一种混合的聚类算法 对句子进行聚类，提高了句子聚类划分的精度。 3 基于聚类算法的中文自动文摘方法研究 第二章自动文摘综述 自动文摘是计算机语言学和情报科学共同关注的课题，其本质是信息的挖掘 和信息的浓缩。从理论上讲，对自动文摘的研究将有助于探讨人类理解、概括自 然语言文本，并从中获取知识的认识模型。自动文摘被认为是计算机实现自然语 言理解的重要标志之一。从应用角度讲，在文献电子化和i n t e m e t 迅速发展的今天， 自动文摘系统的使用将大幅度降低编制文摘的成本，缩短文摘的出版周期，为人 们廉价、迅速和准确地获得所需要的信息提供方便。 2 1 文摘的概念 对于文摘的定义，有多种不同的描述：国际标准文献工作一出版物的文摘 和文献工作( 工5 0 2 1 4 1 9 7 6 ( e ) ) 中的文摘指的是：“一份文献内容的缩短的精确 的表达而无须补充解释或评论。且对写文摘的人来说没有差别。”而在中华人民共 和国国家标准文摘编写规则( g b 6 4 4 7 8 6 ) 中，文摘被定义为：“以提供文献内容 梗概为目的，不加评论和补充解释、简明、确切地记述文献重要内容的短文。 美 国国家标准学会a n s i 文摘编写标准1 1 1 中则给出了文摘的另一个定义：“某一文 献内容的简要而准确的表达，不加解释和评论，也不区分这篇文摘是谁写的。 m a n i t 2 】指出，文摘就是从信息源抽取内容，用简练并且用户感兴趣的方式把最 主要的内容呈现给用户。 孙春葵、钟义信1 3 也给出了一个定义。文摘是对一篇文档中提出的中心主题的 概括性的、准确的描述，内容精炼，篇幅短小。它的基本作用是提示性的，帮助 读者决定是否有必要对全文进行浏览。除了提示作用外，一篇文摘还可以含有有 用信息，如试验结果和主要结论。 综合以上的描述，文摘可以概括为：准确全面地反映某一文献中心内容的简洁连 贯的短文。从中可以看出文摘的特点如下： 1 简洁性：文摘比所摘的文献短，长度为原文献的5 1 0 的文摘就能基本上 反映文献的主要内容；当文献的长度达到原文献的1 0 2 5 ，很多文献的 写作风格就可以在文摘中体现出来了。 4 第二章自动文摘综述 2 准确性：无论长短，文摘必须准确无误地报道原文献的基本内容，不能主 观改变原文观点，科技文献的文摘要确保正确引用原文中的各项数据。 3 清晰性：必须使用一种易读的文体把文献内容清晰地表示出来，最好用完 整的句子编写文摘，并尽可能使用著作者自己使用的词语。 2 2 文摘的分类 不同的分类标准产生了不同的分类方式。这里主要介绍三种分类。 1 从摘要内容同原文档的对比来看，可以将摘要类别分为：提取和摘要两不 中。提取的内容完全由输入文档中拷贝的内容组成。因此，一个典型的、 压缩率为1 0 的提取，将从原文档中拷贝1 0 的内容。这1 0 的内容指 的是以文档中的词或句子，甚至是段落为基准的提取量。通常情况下，我 们都选取句子数作为压缩率的度量基础。在早期的搜索引擎中，一般选择 提取文档的前2 5 的句子作为该文档的摘要。而实际上，一个提取并不需 要由句子组成，它还可以是短语的列表，例如关键词、专有名词、剪枝的 句子等。摘要的内容则包含了一些输入文档中没有表达的东西。例如，在 摘要中可能加入对原文的评价等。而摘要中涉及的原文中的句子也不需要 完全对应。 2 从摘要的信息量来看，可以分为：指示摘要( i n d i c a t i v ea b s t r a c t ) 、信息摘 要( i n f o r m a t i v ea b s t r a c t ) 和评价摘要( c r i t i c a la b s t r a c t ) 。指示摘要为还需进 一步阅读原文档的用户提供了参考功能，也就是说指示摘要是用来帮助用 户决定是否需要阅读原文档的，因为它包含的信息量少，所以往往不能代 替原始文献。美国的工程索引、日本的科技文献速报等都是这一 类的指示性文摘工具。相反，信息摘要在一定程度上覆盖了原文档中所有 的重要信息，可以作为原文档的某种替代，而用户就不再需要考虑原文档。 前苏联的文摘杂志、英国德温特公司的基本专利文摘均属于这一 类。介于这两种摘要之间的是评价摘要。这是近代发展起来的一种文摘。 在这种文摘中，文摘员也是文献的评论者，与各国早期关于文摘的定义要 求不同，文摘员应插入自己的看法和分析。评论性文摘的价值很大程度上 5 基于聚类算法的中文自动文摘方法研究 依赖于文摘员的专业水平。 3 基于用户类型的摘要分类：主题摘要和普通摘要。以用户( 主题或查询) 为中心的方式产生摘要，适应于特定用户或用户组的要求。这就意味着摘 要着重考虑用户感兴趣的东西。普通摘要面对的是一般的，广泛的用户， 基于文本内容。以前，普通摘要都由作者或专职摘要提取人员提供。 自动文摘按文摘对象进行分类，又可分为单文档，多文档两大类，在多文档 文摘的基础上，现阶段又兴起了网页文摘，以及事件追踪探测和文摘等一系列技 术。如果按照使用的技术分，则大致可以分为自动摘录、基于理解和信息抽取三 种方法。这三种方法都适用于单文档或多文档的文摘。 2 2 1 自动摘录 自动摘录( a u t o m a t i ce x t r a c t i o n ) 将文本视为句子的线性序列，将句子视为词的 线性序列。它通常分4 步进行：1 计算词的权值；2 计算句子的权值；3 对原文中 的所有句子按权值高低降序排列，权值最高的若干句子被确定为文摘句；4 将所有 文摘句按照它们在原文中的出现顺序输出。 在自动摘录中，计算词权、句权、选择文摘句的依据是文本的五种形式特征： ( 1 ) 词频( f r e q u e n c y ) ：能够指示文章主题的所谓有效词( s i g n i f i c a n tw o r d s ) 往往 是中频词。根据句子中有效词的个数可以计算句子的权值，这是l u h n 首 先提出的自动摘录方法的基本依据【4 】。v a o s w a l d 主张句子的权值应按其 所含代表性“词串”的数量来计算【5 】。美国b i m 公司在1 9 6 0 年前后研制 了一套文摘自动生产程序a c s l 2 m a t i c ，该程序在句子权值的计算方面对 l u h n 的方法进行了改进。1 9 9 5 年美国g e 研究与开发中心的l i s a e r a u 等人完成了a n e s ( a u t o m a t i cn e w se x t r a c t i o ns y s t e m ) 系统，该系统采用相 对词频作为词的权值 6 1 。 ( 2 ) 标题( t i t l e ) ：标题是作者给出的提示文章内容的短语，借助停用词词表 ( s t o p l i s t ) ，在标题或小标题中剔除功能词或只具有一般意义的名词，剩下 的词和原文内容往往有紧密的联系，可以作为有效词。 ( 3 ) 位置( l o c a t i o n ) ：美国的p e b x a n e d a e l 的调查结果显示：段落的论题是段落 首句的概率为8 5 ，是段落末句的概率为7 。因此，有必要提高处于特 6 第二章自动文摘综述 殊位置的句子的权值。 ( 4 ) 句法结构( s y n t a c t i cs t r u c t u r e ) ：句式与句子的重要性之间存在着某种联系， 比如文摘中的句子大多是陈述句，而疑问句、感叹句等则不宜进入文摘。 ( 5 ) 线索词( c u e ) - e d m u n d s o n 的文摘系统中有一个预先编制的线索词词典， 词典中的线索词分为3 种：取正值的褒义词( b o n u sw o r d s ) ，取负指的贬义 词( s t i g m aw o r d s ) ，取零值的无效词( n u l lw o r d s ) 1 7 , 8 】。句子的权值就等于句 中每个线索词的权值之和。7 0 年代初，俄亥俄州立大学的j a m e sa r u s h 教授和他的学生开发了a d a m ( a u t o m a t i cd o c u m e n ta b s t r a c t i n gm e t h o d ) 系统。a d a m 强调的是排斥句子的标准而不是选择句子的标准，词控表 ( w c l ) q b 大多数词是否定性的【9 】。 2 2 2 基于理解的自动文摘 基于理解的自动文摘通常采用如下的步骤： ( 1 ) 语法分析：借助词典中的语言学知识对原文中的句子进行语法分析，获得 语法结构树。 ( 2 ) 语义分析：运用知识库中的语义知识将语法结构描述转换成以逻辑和意义 为基础的语义表示。 ( 3 ) 语用分析和信息提取。根据知识库中预先存放的领域知识在上下文中进行 推理，并将提取出来的关键内容存入一张信息表。 ( 4 ) 文本生成：将信息表中的内容转换为一段完整连贯的文字输出。 理解文摘的不足在于领域严格受限。造成领域受限的原因在于面向大规模真 实语料的语法语义分析技术尚未完全成熟，因此如果想获得高质量的语言分析结 果，就必须将待处理的语料限制在某个范围之内。其次，理解文摘方法的基础是 框架等知识表示，框架需要根据领域知识预先拟定，因此如果想把适用于某个领 域的理解文摘系统推广到另一领域，则需重新拟定框架，这种填充和组织领域知 识的沉重负担使理解文摘难以移植。 2 2 3 基于信息抽取的自动文摘 基于理解的文摘方法需要对文章进行全面的分析，生成详尽的语义表达，这 7 基于聚类算法的中文自动文摘方法研究 对于大规模真实文本而言是很难实现的。与之相比，信息抽取( i n f o r m a t i o n e x t r a c t i o n ) 只对有用的文本片段进行有限深度的分析，其效率和灵活性显著提高。 英国l a n c a s t e r 大学p a i c e 等人在19 9 3 年提出的选择与生成文摘法，实质上就 是信息抽取方法。目前该系统主要针对“小麦实验方面的文章，但研究者们正 在努力使它能够方便地移植到其它领域【5 l 。英国曼彻斯特的b l a c k 是p a i c e 的合作 者【1 0 1 。由于文摘框架的编写完全依赖于领域知识，所以信息抽取仍然是受领域限 制的，只不过文摘框架比理解文摘中的脚本等要简单得多，更易于编写。信息抽 取要相应用于多个领域，就必须为每个领域都编写一个文摘框架，在处理文本时 先进行主题识别，根据主题调用相应的文摘框架。另外，单凭特征词或特征短语 的提示作用来填充文摘框架并不是非常准确的，而且由于语言的灵活多样，一些 有价值的文本片段可能没有明显的特征。最后，由于使用模板生成文摘，使得文 摘的语言千篇一律，十分呆板。 2 3 自动文摘技术的评价方法 自动文摘通常被视为自然语言处理的一项任务，而如何评价自动文摘的好坏 一直以来都是个很困难的问题，因为对于一个文本或文本集合来说并不存在一个 最优的文摘，不同的人可能对于同一篇文章的摘要有不同的看法。除此之外，目 前还缺乏一种标准的人工或者自动的评价体系，使得比较不同自动文摘系统的结 果变得十分困难。 从广义的角度可将自动文摘的评价方法大致分为两类【1 1 l ：一种称作内部评价 ( i n t r i n s i c ) 方法，与系统的目的相关，它通过直接分析摘要的质量来评价文摘系统。 第二种称作外部评价( e x t r i n s i c ) 方法，它是一种间接的评价方法，与系统的功能相 应，将文摘应用于某一个特殊的任务中，根据摘要功能提高这项任务的效果来评 价自动文摘系统的性能。文摘的评价较索引的评价要复杂的多，它需要更多的知 识( 语言学、领域知识和上下文关系) 做支持。内部评价方法【1 2 l 按信息的覆盖面 和正确率来评价文摘的质量，一般采用与“理想摘要 相比较的方法。这种评价 方法源于信息抽取技术。信息抽取是将原文的关键要点抽取出来，并与人工抽取 的内容在召回率( r e c a l l ) 、准确率( p r e c i s i o n ) 、冗余率( o v e rg e n e r a t i o n ) 及错误率( f a l l o u t ) 8 第二章自动文摘综述 几个指标上进行比较。这其中“理想摘要通常是直接用原文作者摘要来充当， 但也有人主张采用专家对文章直接抽取句子进行摘要。不同的专家所撰写的摘要 是不同的，有时在内容上很少交叠。特别是评论或解释性文摘，内容更难达到一 致。许多情况下，只能判断文摘的合理性。例如，若文摘虽囊括了原文的要点， 但可读性差，不利于人的理解，那么就没起到它应有的作用。 在国际上，d u c 是目前比较权威的关于评测的会议。这个会议是由n s l t 支持 的，它的目的是为了使文摘技术有更进一步的发展，给研究者们提供一个参加大 规模实验的机会。在d u c z o o l 中，对自动文摘规定了三种评测任务： 1 全自动的单文档文摘； 2 全自动的多文档文摘：给定一个单一主题的多文档集合，要求参加者为这些 多文档集合分别做出5 0 字、1 0 0 字、2 0 0 字、4 0 0 字的文摘。这些多文档集分为两 部分，一部分为训练集，由人工对这部分文档集做出5 0 字、1 0 0 字、2 0 0 字、4 0 0 的文摘，另一部分为测试集； 3 探索性文摘：鼓励参加者研究可选取的方法，并评测这种方法生成的文摘结 果。评价一个文摘是否能满足用户的需求以及它是否能脱离原文独立成篇也很重 要f l l 】。 评价文摘的工具通常比较昂贵。它要求在完全受控条件下进行足够多次的试 验。例如，要比较不同人写的文摘，测试文摘对文献筛选的影响。一般认为要建 立一种客观有效的文摘评价方法，还有待迸一步的探索和研究。 2 4 自动文摘技术的研究现状 早在1 9 5 8 年，美国i b m 公司的h p l u h n 在i b m 7 0 4 机器上开始了自动文摘 系统的研制工作，开创了自动文摘的先河【4 1 。他最重要的发现是使用词频来判断一 个词在一个文本中的重要性，并由此来判断一个句子的重要性。最后将这些句子 按重要性大小进行排序，抽取重要性较大的几个句子组成摘要。除此之外，在他 论文中的其它一些发现为今后的自动文摘技术奠定了重要基础。同样来自i b m 公 司的b a x e n d a l e 在1 9 5 8 年也发表了关于自动文摘技术的文章【1 3 1 ，他使用句子位置 来寻找一个文本中的重要部分，并通过抽取这些重要部分中的句子来组成文摘。 9 基于聚类算法的中文自动文摘方法研究 e d m u n d s o n 在1 9 6 9 年提出了一个自动文摘系统。他结合了词频和句子位置这2 种 特征，并在此基础上引入了2 种新的特性：文本中的提示词( 例如：重要的，几 乎不等等) 和文档的框架( 例如：一个句子是否是标题或句首) 。不同的权值被赋 予给这几种特征，在通过加权计算后得到一个新的句子权值，并将所有句子的权 值进行排序，取出权值较大的一些句子组成文摘。 到了上个世纪9 0 年代，随着机器学习技术和自然语言处理技术的不断发展， 有人开始提出使用统计学的方法来生成自动文摘。k u p i e j l 4 】等人在1 9 9 5 年对 e d m u n d s o n 的方法进行改进，他们使用一个b a y e s 分类函数来区分一个句子是否 足够重要来组成文摘，函数如公式2 1 所示，s 代表文本中的一个句子，s 是组成 文摘的所有句子的集合，最，e ，e 代表句子的特征值，并假设这些特征值是相 互独立的： 。 耶删辑驴业一 ， 互，最，e 除了包含了e d m u n d s o n 提出的那些特征外，还额外引入了2 个特 征：句子长度和句子中的大写字母。每个句子通过公式2 1 计算得出一个权值，权 值排在前1 1 个的句子被抽取出来作为文摘。a o n e 等人在1 9 9 9 年提出了一个名为 d i m s u m 的自动文摘系统，该系统同样使用了b a y e s 分类函数，但是使用了更多的 句子特征值：词频( t f ) 和逆词频( i d f ) ，逆词频是通过从一个主题相似的文档集合中 计算获得的。 近年来自动文摘技术也得到了迅速的发展，c o m o y 和0 l e a f y 使用隐马尔可夫 模型( h m m ) 来从文档中抽取句子【1 5 】，里面只使用了3 个特征：句子在文档中的位 置，句子包含的词语数量和句子中的词语组成文摘的可能性。s v o r e 在2 0 0 7 年提 出了一个基于神经网络的方法来生成自动文摘，由该方法生成的文摘质量比起之 前的方法有了显着的提高。 而在国内，我国从1 9 8 5 年开始介绍国外自动文摘方面的研究情况，从8 0 年 代末开始研究自文摘实验系统。在形式特征方面，汉语和西文主要区别是汉语词 间没有空格，因而存在着自动分词问题。汉语自动分词是一项经过多年研究仍未 圆满解决的难题，以至于南京大学信息管理系的李明提出了从汉字频率统计出发 1 0 第二章自动文摘综述 提取文摘的权宜之计，从而回避自动分词问题【1 6 】。然而因为汉语中真正负载信息 的是词而不是字，所以如果分词技术能够满足大规模真实文本处理的需要，那么 以词为基础的自动文摘必然优于以字为基础的自动文摘。实际上，大多数中文文 摘系统都要对文本进行分词处理，只是由于采用的分词方法不同，使得分词精度 有所不同。此外，汉语的词汇极为丰富，同一个概念可以用很多不同的词汇表达， 这给词频统计带来了一定的困难。上海交通大学王永成教授从8 0 年代末就开始研 究自动摘录技术，1 9 9 7 年研制了o a 中文文献自动摘要系统。该系统集成了位置 法、指示短语法、关键词法和标题法等多种方法，是一个实用的系统【1 7 2 0 】。中科 院软件所的李小滨，徐越依靠语法，语义的分析，提出了一个自动文摘系统 e a a s 2 1 ) - 2 1 。 哈尔滨工业大学王开铸教授于1 9 9 2 年研制了基于自然语言理解的文摘实验 系统m a t a s l 2 3 1 ，1 9 9 4 年研制了自动摘录类的h i t 2 8 6 3i 型自动文摘系统【2 4 】。 1 9 9 6 年刘挺提出了基于信息抽取和文本生成的自动文摘方案【2 5 1 ，1 9 9 8 年完成了 基于篇章多级依存结构的h i t 2 8 6 3i i 型自动文摘系统。 近两年来，从事这项研究的单位不断增加。北京邮电大学信息工程系钟义信 教授采用的文摘方法类似于p a i c e 的选择与生成文摘法，目前主要针对计算机病毒 方面的文章 2 6 1 。山西大学郭炳炎教授也在开展自动文摘的研究，他们采用基于统 计的方法分析文本结构1 2 7 1 。据悉，i b m 中国研究中心和大陆微软公司都在研制 中文自动文摘的产品。 基于聚类算法的中文自动文摘方法研究 第三章基于潜在语义分析的句子相似度计算 句子相似度的计算是基于句子聚类算法自动文摘的一个重要环节，它关系到 最后生成文摘的准确性。目前普遍采用的是基于词形建立向量空间模型( v s m ) 的方 法。一个句子s 可以看做n 维空间中的一个向量尸( s ，；s 2 ，；瓯，呢) ，其中 s ，s 2 ，鼠为句子s 中不同的n 个词，w i 为s i 的t f - i d f 值。通过计算2 个不同向 量的余弦值来得到2 个句子的相似度。v s m 假设不同向量的各个特征是相互正交 的，然而在很多文本中，经常出现几个不同的词表达同一个概念的情形。这些词 可能是同义词，也可能具有上下位关系，这就造成以词形为基础的v s m 向量的各 特征间可能存在密切的语义联系，即出现“斜交”，这就在一定程度上降低了句子 相似度计算的准确性。 潜在语义分析( l a t e n ts e m a n t i ca n a l y s i s ，l s a ) 是s t d u m a i s 2 8 】等人提出的，是 一种用于知识获取和展示的计算理论。它的出发点是组成句子的词与词之间存在 着某种联系，即存在某种潜在的语义结构。这种潜在的语义结构隐含在词语的上 下文使用模式中，因此可以采用统计计算的方法对大量的句子进行分析来寻找这 种潜在的语义结构，并且用语义结构来表示词和句子。因此，使用l s a 将句子向量 从词形向量空间映射到潜在语义空间，获取句子的语义结构以消除词之间的相关 性，可以解决特征间的“斜交 问题，从而提高句子相似度计算的准确性。 目前的基于l s a 的自动文摘方法，由于受向量空间模型方法影响而没有考虑文 档权重的重要性，大多是直接对词频矩阵进行奇异值分解，从而导致潜在语义分 析的结果不佳。为了克服潜在语义分析的这个不足，本文对词频矩阵进行了权重 改进，然后对加权改进后的矩阵进行奇异值分解，最后再对新得到的矩阵进行聚 类分析，取得了较好的实验结果。 3 1 潜在语义分析的基本思想 潜在语义分析的前提假设是文本中词与词之间存在某种联系，即存在某种潜 在的语义结构 3 0 , 3 1 】。在潜在语义分析中，文本被看作词语空间中的一个子空间， 1 2 第三章基于潜在语义分析的句子相似度计算 两个文本所对应子空间之间的距离越小，那么这两个文本在语义上就越接近；词 语被看作文本空间中的一个子空间，两个词语所对应子空间之间的距离越小，那 么这两个词语在语义上就越接近【2 9 1 。 由于词一文本矩阵的数据往往非常庞大，并且受到一词多义与同义词带来的 “噪声 干扰。因此，潜在语义分析还要利用矩阵奇异值分解( s i n g u l a rv a l u e d e c o m p o s i t i o n ，缩写为s v d ) 的方法，把原来的语义结构空间简化为潜在语义结 构空间。在潜在语义结构空间中，文本空间和词语空间的维数大大下降，不仅简 化了语义结构空间，而且消除了“噪声”干扰【3 2 1 。 在l s a 空间结构中，文本和词语依据语义上的相关程度被组织存放，分散在不 同文本中的同义词空间位置相邻。l s a 方法对语义空间的维度进行约简，消除语义 表达中的“噪音”( 词语罕见或者不重要的用法、含义) ，词语含义是词语多种含 义的带权平均( 如果词语的实际语义偏离这个平均语义很远，l s a 在表达是会产生 偏颇) 。 l s a 利用潜在的语义结构表示词条和文本，将词条和文本映射到同一个k 维的 语义空间内，均表示为k 个因子的形式，向量的含义发生了很大的变化。它反映的 不再是简单的词条出现频率和分布关系，而是强化的语义关系哗l 。 由于词条和文本被映像到同一k 维的语义空间，所以在l s a 模型中不仅能够进 行传统的词条与词条、文本与文本之间的相似关系分析，而且能够分析词条与文 本之间的相似关系，与传统的向量空间模型相比，具有更好的灵活性。 对于原始的“词语文本 矩阵，通过l s a 提取出k 维语义空间。在保留大部分 信息的同时使得k 0 ，当x = 0 时，l | x l l = 0 ； 2 齐次性：i la xi i = | la ix0 ，a r ，x v ； 3 三角不等式：l | x + y 悃ix l i + l | y0 ，x ，y v ； 则称i ix | i 为v _ lr 句m x 的范数，简称向量范数。 定义3 4 ：矩阵空间c 一是一个m xr 维线性空间，设a = ( ) c 舭疗，那么 开刀 l ia i i = ( l 嘞1 2 ) j 被称为f r o b e i l i u s 范数或简称为f 一范数。 定义3 5 ：对于一个秩为r 的矩阵a ，4 r 么的特征值为 如4 4 + 。= = = 0 ，那么有l ia i i f = j o , 2 ，o a 1 1 2 = ，其中 lf ；l q = 石，i = l ，2 ，n 称为a 的奇异值。 定理l ：奇异值分解定理( s i n g u l a r v a l u ed e c o p o s i t i o n ) 设a r ”，且r a n k ( a ) = ， i i s - p 1 1 2 - - - - i is 一圳2 2 五+ l ( 3 3 ) ( 3 4 ) ( 3 5 ) ( 3 6 ) 性质1 和性质2 说明s 和筑之差的f r o b e n i u s 范数和2 范数是矩阵s 的奇异值函 数。性质1 还说明，与其它降秩方法相比，t s v d 是原矩阵s 在秩为k 的前提下，最 小二乘意义m 1 上的最优的近似解。根据奇异值分解定理， 如4 o ，当k 较小时，垒掣较大，当k 较大时，垒掣较小。 庀庀 3 2 潜在语义分析的权重计算改进 在上面关于潜在语义分析的讨论中，是直接对词频矩阵x 进行奇异值分解。然 而文本中不同的词语对语义空间的贡献程度是不同的，因而需要定义一种权重函 w q ，) ，对词频矩阵进行加权转换，得到一个转换后的矩阵x ，然后再对x 进 行奇异值分解以及截断。向量空间模型方法的研究多集中在权重计算方法的选择 上 4 7 , 4 8 1 ，在l s a 中，权重计算也同样非常重要。l s a 中权重计算方法很多继承于 v s m ，但是又有区别。v s m 本质上将词语看做空间的维度，将文档根据其包含的 词语看做该空间中的一个点；l s a 中不再将词语看做单独的维度，潜在语义空间中 的维度被认为是对应着各个“潜概念 ，词语向量被看作是它们在各个“潜概念 上的投影，文档向量是其它所包含的词语向量之和。l s a 通过s v d 将v s m 的空间 作了基变换生成了新的空间基，而词语在这些基向量上的投影体现出词语间的语 义关系。在潜在语义分析中定义权重，体现出一种信息归约的作用，会使潜在语 义空间的基更能呈现出主要的语义结构。本文对词频矩阵进行了局部权重和全局 1 9 基于聚类算法的中文自动文摘方法研究 权重进行了改进，提高了基于潜在语义分析的自动文摘的实验结果。 3 2 1 现有l s a 权重计算方法 传统的权重计算方法一般将权重分解为两部分分别定义，一部分称为局部权 重( 记作l r g ( i ，j ) ) ，用来记录词语i 在文尚中的词频信息蠊；另一部分称为词语 全局权重( 记作g w t ( o ) ，词语全局权重说明了不同的词语在文档集中区别分辨 文档语义的能力是不同的。l s a 的重要任务就是提取语义结构，即词语之间潜在 的语义关系。两个权重较大的词语之间隐含的语义关系，更容易被l s a 认为是重要 的语义关系而被保留。因此权重函数一般可以用下式表示： 形( j ) = l w ( i ，歹) 木g w t ( i ) ( 3 7 ) 3 2 2 词语局部权重计算方法的改进 局部权重强调某一词语在某一文档中的重要性1 4 9 1 。最简单的就是将词频作为 局部权重的定义。 三( f ，) = 玩 ( 3 8 ) 在上面这种定义下，有时某一文档中的某一高频词语权重会过分突出，为了有 效地消减高频词对潜在语义空间的影响，本文取词频的对数作为局部权重的定义。 三( f ，歹) = l 0 9 2 ( 玩+ 1 ) ( 3 9 ) 公式( 6 ) 中对数底取2 。根据矩阵的稀疏程度，非零元素的分布状况，或者原始 文档的平均长度，可以选取不同的对数底。 3 2 3 词语全局权重计算方法的改进 目前在对矩阵进行潜在语义分析时，大多都不考虑词语全局权重在整个权重 计算中的作用，即直接取g w t = 1 ，然而词语全局权重强调某一词语在整个文档集 中的重要性，它在一定程度上代表了某一