发布时间: 2016-08-31
摘要：本文研究的重点是中文多文档自动的几个关键技术：包括子主题划分、基于子主题的句子抽取等。在传统的基于子主题的句子抽取方法的基础上提出一种基于子主题的遗传算法句子抽取方法，并对形成摘要的句子采用新的排序方法。所实现的中文多文档摘要系统具有重点突出，可读性强等特点.
论文关键词：遗传算法,多文档,摘要,句子抽取,聚类
随着互联网上信息的急剧膨胀，怎样快速有效使用庞大而丰富的网上信息成为一个重要而紧迫的问题。由于网上信息很大部分都是以文本形式存在，即通过自然语言描述的，因此通过使用自然语言理解技术对这些信息进行提炼分析己经成为近年来海量信息处理的一个热点研究方向，信息检索、信息抽取、自动文摘等自然语言处理的高层课题都吸引了很多研究者。多文档自动摘要技术也是其中一个重要的研究课题。
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日
http://edu.people.com.cn/GB/116076/8621468.html
教学评估岂能因噎废食 采集时间2008年9月5日
http://theory.people.com.cn/GB/49157/49166/7811086.html
高校评估，乱了象牙塔里人们读书的心 采集时间2008年9月5日
http://scitech.people.com.cn/GB/7207282.html
关于教育发展的建议 采集时间2008年9月5日
http://npc.people.com.cn/GB/28320/119930/121907/121911/7239438.html
高校评估的最大受益者真是学生？ 采集时间2008年9月5日
http://edu.people.com.cn/GB/7175878.html
西西弗斯的石头与迷失的大学 采集时间2008年9月5日
http://opinion.people.com.cn/GB/7171877.html
从虎照鉴定到高校评估 采集时间2008年9月5日
http://zb.people.com.cn/GB/7169742.html
高校评估劳民伤财易出现弄虚作假 应当改革 采集时间2008年9月5日
http://politics.people.com.cn/GB/1026/7155116.html
高校评估当改革 采集时间2008年9月5日
http://theory.people.com.cn/GB/49157/49166/7155016.html
教育部规范本科教学评估 大学评估拒绝造假 采集时间2008年9月5日
