基于遗传算法的中文多文档自动摘要方法研究

摘要：本文研究的重点是中文多文档自动的几个关键技术：包括子主题划分、基于子主题的句子抽取等。在传统的基于子主题的句子抽取方法的基础上提出一种基于子主题的遗传算法句子抽取方法，并对形成摘要的句子采用新的排序方法。所实现的中文多文档摘要系统具有重点突出，可读性强等特点.
论文关键词：遗传算法,多文档,摘要,句子抽取,聚类

　　随着互联网上信息的急剧膨胀，怎样快速有效使用庞大而丰富的网上信息成为一个重要而紧迫的问题。由于网上信息很大部分都是以文本形式存在，即通过自然语言描述的，因此通过使用自然语言理解技术对这些信息进行提炼分析己经成为近年来海量信息处理的一个热点研究方向，信息检索、信息抽取、自动文摘等自然语言处理的高层课题都吸引了很多研究者。多文档自动摘要技术也是其中一个重要的研究课题。

　　2 预处理

　　文本预处理模块的主要任务是对文档进行章节、段落、句子等划分，主要以标点符号为划分依据。符号对于语法或者语义的影响可能比较大，但是对于文本预处理而言，符号就是句子间隔，将输入的原文本按照其所属章节、段落和句子等信息进行标记。

　　另外摘要句的句式多为陈述句，象感叹句、疑问句等特殊句式一般不直接表达文章的中心主旨，考虑这些因素，因此在文档预处理分析时，不对该类句式进行处理。在进行文档划分时，还应该考虑到全角半角标点标号的区别，为保证文本标识的准确性，还要处理文本的各种标点符号，识别文本的结构，最终达到以句子为单位对文本进行分隔的目的。预处理主要包括两个部分：结构预处理和统计两部分。

　　3 句子分类

　　分类模块：将文档簇中描述同类问题的句子进行归类。即对文档簇进行句子聚类。

　　句子聚类：本文选择K-means均值聚类。选择原因，由于其效率高，它的计算复杂度为O(nkt)，其中n为样本点的个数，k为类的个数，t为循环次数。应用K-means均值聚类需先定义两个句子间的距离。两个句子的距离可定义为：，其中SIM(A,B)为句子A和句子B之间的相似度。

　　聚类算法：

　　输入：文档簇的句子，聚类个数k个

　　输出：k个类

　　① 随机选择k个句子作为每个类的中心；

　　② 重复下面操作：

　　----依据样本到中心的距离，将每个向量分配到距它最近的类中；

　　----计算新的类中心；

　　③ 直到类中心变化很小为止

　　聚类中k值的确定

　　通常，用户都不希望看到太长的文摘，因此会限定文摘的最大长度。如此一来，当限定了文摘的长度后，类的个数k值就可用文摘的长度除以句子的平均长度来确定：

　　

　　其中表示用户指定的文摘最大长度。表示原文档簇中句子的平均长度。

　　4 句子抽取

　　通常一篇好的文摘应该具有以下特点：长度符合用户规定、尽可能多地覆盖原文档的要点、更忠实地保留原文档中的重要信息、较少的冗余、可读性好等，本节中评价函数的设计遵照上述的前四个特点。本节采用演化算法进行句子抽取。

　　该算法在句子分类的基础上首先随机产生一个文摘种群，再通过对文摘种群中的文摘个体进行评价、选择、杂交和变异生成新的种群，如此反复进行，直至满足一定的终止条件为止。

　　基因的编码方式：采用十进制不定长编码。每一个代码表示一个句子，一组编码表示一个摘要。编码的长度不能太长，也不能太短，长度的范围为用户要求句子数的0.5倍至1.5倍。

　　选择方法：

　　采用轮盘式选择：这种选择策略在遗传算法中使用的最多，它也是先计算个体的相对适应值记为Pi然后根据选择概率把圆盘分成N份，其中第i扇形的中心角为。在进行选择时，可以假想转动一下圆盘，若某参照点落入第i个扇形内，则选择个体i。这种选择策略可以如下实现：先生成一个[0，1]内的随机数r，若则选择个体i。易见，这种选择方式非常类似轮盘赌中的转盘。小扇区的面积越大，色子落入其中的概率也越大，即个体的适应值越大，它被选择到的机会也越多。从而，其基因结构被遗传到下一代的可能性也越大。

　　交叉策略：采用单点杂交。即随机选择两个亲代摘要的一部分作交换，形成新的子代摘要。亲代形式如下：Parent1(12548|96)，Parent2(386|52)。交换摘要的中间部分，去除重复句子得到子代形式如下：Child1(12548) ，Child2(3869)。

　　变异策略：随机选择摘要句的一个位置加入随机不重复的一个句子。

　　评价函数的定义为：

　　，其中：S是摘要种群中的一个摘要个体；

　　5 文摘句排序

　　在获得文摘句后，还需要考虑其在文摘中的先后顺序。文摘句之间存在多种排列，如有n个文摘句，其排列共有n!种之多，这种排列会影响到文摘的质量，特别是一致性、流畅性、逻辑性等，直接关系到文摘可读性的好坏。在摘要句聚类的基础上提出了将摘要句按类排序。即属于同一类的摘要句排在一起。并且属于同类的摘要句按句子分值高低排序。对于不同类的摘要句将类内摘要句数多的摘要句排在前列。

　　6 实验结果

　　6.1 测试语料集

　　所选的测试语料包括10篇新闻文章，选自人民网的“高校评估”检索的10篇文章。

　　高校评估拟引入社会评价采集时间2008年10月23日

　　

　　教学评估岂能因噎废食 采集时间2008年9月5日

　　

　　高校评估，乱了象牙塔里人们读书的心 采集时间2008年9月5日

　　

　　关于教育发展的建议 采集时间2008年9月5日

　　

　　高校评估的最大受益者真是学生？ 采集时间2008年9月5日

　　

　　西西弗斯的石头与迷失的大学 采集时间2008年9月5日

　　

　　从虎照鉴定到高校评估 采集时间2008年9月5日

　　

　　高校评估劳民伤财易出现弄虚作假 应当改革 采集时间2008年9月5日

　　

　　高校评估当改革 采集时间2008年9月5日

　　

　　教育部规范本科教学评估 大学评估拒绝造假 采集时间2008年9月5日

　　

　　6.2 产生部分综述文本如下：

　　①为此，今后我国高校教学评估关注的焦点不是是否要坚持评估制度，而是为评估制度的发展提出建设性意见，不断完善评估制度。②一直颇受社会争议的高校评估将可能在今年有新的转变，教育部正在探索在原本专家进校评估以及教学状态数据发布的基础上引入社会评价。③在高校评估这根“获利链条”上，受益者多多。④而如今的高校评估，却是以行政为主导，是教育部等行政部门做出的。在目前的高等教育体系中，大学生医疗保障是一个空白。⑤大学发展的基本问题是让人安心读书。⑥譬如评估组成员，在我国的教育体系中，高等教育中的贫困生问题同样令人揪心，虽然建立了高等教育助学贷款体系，但无法保证所有的贫困大学生都能获得贷款申请，而助学贷款发放后难以收回也使银行陷入两难境地。⑦在市场和政府的双重影响下，大学要坚持自己的崇高使命和精神品质，看来还需要纪宝成所强调的，有极强的自制力和自治力。⑧提升高等教育质量、提高教育效率是教育发展的永恒诉求。⑨加强教师队伍建设对于促进教育体制改革与发展，提高教育质量，营造公平教育环境都有着重要意义。⑩而提升教育效率的前提是进行反思与评估，发现教育存在的问题，并以问题为改进的起点。教育部要的指标本来是要在教学实际中提升达到的，但是很多学校发现这样做太困难。

　　6.3 自动评测系统的实现

　　自动文摘目前还没有比较理想的性能评估方法。因为文摘没有绝对答案，所以结果的评估难以摆脱主观性。另外，不同的用户对摘要的要求各不相同，很难制定出统一的评价标准。而自动综述的评估方法更不成熟。在实验中我们借鉴了自动文摘的主观评价方法。我找了20位同学对综述结果的可接受度给与打分评定。评价结果如下：综述的接受程度，按5分制打分为3分，认为基本可以接受。

　　6.4 小结

　　实验结果表明，所产生的摘要文本较好地覆盖了原有专题的各个关键部分。同时所选的句子有较好的代表性，能够反映这个侧面的主要内容。同时具有一定的可读性，这些结果说明基本达到了预定的实验目标。

　　从实验结果还可看到一些不足之处。目前的摘要文本形成在时间性能上表现不理想，这与遗传算法本身有关。今后需要在这些方面做进一步研究完善。

参考文献
[1] 郭燕慧，钟义信，马志勇，姚均勇 自动文摘综述 情报学报 2002，21（5）582-591页
[2] 李蕾，郭祥昊，钟义信 面向特定领域的理解性中文自动文摘系统 计算机研究发展 2000，37（4） 6-10页

本文链接：http://www.qk112.com/lwfw/sklw/kejilunwen/265903.html