面向特定领域自动问答系统的语句相似度计算

李　健，郑　诚，代　宁

(安徽大学 计算机科学与技术学院，安徽 合肥 230039)



面向特定领域自动问答系统的语句相似度计算

李健，郑诚，代宁

(安徽大学 计算机科学与技术学院，安徽 合肥 230039)

[摘要]本文针对教务管理系统学生选课自动问答系统，提出一种语句相似度计算方法。该方法先采用基于布尔型VSM掩码的方法实现问题的初分类，再采用改进的编辑距离算法计算句子相似度来判断FAQ库的匹配，从而使系统返回问题的答案。实验结果表明该方法可行。

[关键词]问答系统；向量空间模型；编辑距离；相似度计算 在语的比较阶段，因为用户输入的是一句话，长度较短，所以在这里采用了相对简单的关键词提取与比较方法，构建关键词语库，在构建关键词语库的同时构建同义词库，因为同一个意思词语可能有不同的表达方法。例如：

问答系统能用准确、简洁的自然语言回答用户用自然语言提出的问题。它是目前自然语言处理中一个比较热门的研究领域。目前的问答系统主要包含以下几类：基于专业领域知识库的问答系统、基于常见问题集的自动问答系统(FAQ)和开放领域问答系统。

从系统的设计与实现来看，自动问答系统主要包括三个主要组成部分：问题分析与理解、信息检索和答案抽取[2]。问题的分析与理解就是对问句进行正确的分词、提取关键词组、识别问句中的主题词，从而确定访问的数据源。信息的检索是进行问题与相关句子上的匹配，即进行句子相似比较。常用的信息检索模型有布尔模型，向量模型和概率模型。答案的抽取主要是提取候选答案，并返回最优答案。

本文研究基于学生选课领域的自动问答系统关键技术。在中科院的ICTCL分词和同义词扩展的基础上，提出一种基于布尔型VSM掩码的分类方法实现初步分类，并结合改进的编辑距离算法计算句子的相似度。

1相关工作

中文问答系统起步较晚, 不够成熟, 这和中文的语法、语义复杂性等多种因素有关。随着问答系统的研究，我国也发展了一系列相关的理论和算法，如基于领域本体，基于词共现图的自动问答系统[3]，基于高频词和共现词的文本主题词抽取方法；基于改进贝叶斯模型的问句分类[6]；基于潜在语义分析的汉语问答系统答案提取[7]；基于句法结构特征分析及分类技术的答案提取算法[8]等等。这些研究成果，都为中文问答系统的研究和发展提供了很好的理论基础和实践经验。

2系统模型

选课系统涉及到教务部门、各院系的教学办、学生和教师。结合教务管理特点，研究教务问答系统的关键技术。高校教务管理是两级管理，一级是教务处管理，另一级是院系管理。教务处管理涉及到学分制管理、学生选课、学籍等教务的通用的政策和办法，院系管理涉及与专业相关的教务。本系统将问答系统问题-答案库设计成两级，一级是通用教务问题-答案库，这个库由教务处人员维护，另一级是各专业问题-答案库，由各个院系分别维护。系统首先进行问题初分类，判断出问题是通用问题还是专业问题，若与专业无关，则是通用问题，从通用问题答案库中抽取答案，否则，从相应的专业问题答案库抽取答案。

2.1系统框架

系统模型分为三层：用户层、分析层、数据层。其中用户层作用是用户问题输入和显示系统提取的答案；分析层作用是问题的分析、检索得到最佳答案；数据层作为系统的知识存储主要包含停用词库、专业词库、同义词库、FAQ常用问题库，其中常用问题库包含了用户询问频率很高的问题。

在问答系统中，对用户问题的正确理解是系统的关键技术部分。将问答系统分两级进行实现，第一级实现初分类，确定问题是属于教务部门管理中通用问题，还是涉及所属院系相关的专业问题。采用了一种基于布尔型VSM掩码分类方法来提取问题答案，系统框架如图1所示。

图1　教务问答系统框架

系统首先进行问题的分析理解，提取关键词，同义词扩展，与语料库词典的训练文档词条进行匹配编码。然后，将编码后的掩码与库中各专业的掩码进行“与”操作，识别问题含义，从而区分出用户问题的类别。在FAQ库的匹配中，通过运用编辑距离算法计算句子相似度并对阈值进行判断，如果满足条件，直接返回准确答案。需要指出的是，在系统使用辅助功能的同时，系统管理员根据需要对系统的词库、FAQ库等进行更新，以确保在系统之后遇到同样的问题，能自动返回答案。

2.2向量空间模型VSM

向量空间模型VSM(Vector Space Mode)，是以特征值作为文档表示的基本单位[9],其将文档映射为一个特征向量V(d)=((t1,ω1(d)),…,(tn, ωn(d)))，其中ti(i=1,2, …,n)为一列互不相同的词条项，ωi(d)为词条ti在d中的权值, 这样文本可以表示成为结构化数据的形式。

在VSM模型中，词条ti的权重计算方法有很多种，按其值类型可分为布尔型和数值型两种。在布尔型VSM中，将所有训练文档的词条作为全集，若某一个词条出现，设其权值为1，否则设为0。数值型VSM中，权重可以表示其对应的词条在文档中出现的次数。

这样，向量空间中的N个文档可以用一个矩阵来表示，矩阵中的一个元素对应文档中一个词条项的权重，文档集的一般表示方法如下所示：

2.3句子相似度计算

编辑距离，又称为Levenshtein距离，是指两个字串之间，由一个转换成另一个所需的最少编辑操作次数，距离越大，说明字串越不同。编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

最原始的编辑距离算法在文献[4]中进行了详细的介绍，但是这个算法并不适用于中文。例如“什么时候是选课的时间？”,“选课的时间是什么时候?”同样的语义，二者的编辑距离会很大。因此文献[5]对此算法进行了初步的改变。

设句子组M(s1…silen,t1…tjlen),其中ilen,jlen分别为句子s,t的字个数，文献[5]中的方法是对原始的编辑算法进行了一个初步的改进，使相邻位置的词可以进行交换,编辑距离算法可以构造如下(ilen+1)*(jlen+1)的矩阵Distance(i,j)。

上述等式分别包含了删除，插入，交换，替换四种操作。计算最后结果Distance(ilen,jlen)为两个句子的编辑距离。计算相似度的公式为Similarity=1-Dis/Lmax其中Dis为编辑距离，Lmax为两个句子的最大值。这种编辑距离的计算会出现特殊情况，如“再见朋友”和“朋友再见”编辑距离为4，而相似度为0.因此文献[1]采用了下面的这种改进计算编辑距离的方法。

在原有计算编辑距离的基础上，通过拓展交换操作减少编辑操作的数量。文献[1]对交换的操作进行了拓展：

3关键技术实现

3.1问题分析模块

当用户输入问题，进行问题分析理解模块的操作。该模块的内容主要包括对问句的分词，删除停用词，问句关键词语的提取。流程如下图所示：

图2　问题分析模块处理流程

“毛概什么时候选？”和“毛泽东思想什么时候选？”

两个问句是同一个意思，但是却是不同的关键字，需要为“毛概”和“毛泽东思想”这两个词语建立同义词库。

在实验中不断的对自己关键词语领域库及其同义词库进行更新，并利用分词技术，将问句分词后所得到的结果逐个与这两个词语领域库比较，保留问句中与词语领域库相同的词语。然后在数据库中优先选取包含问题中关键词数目较多的答案。

3.2初分类模块

3.2.1布尔型VSM掩码

所谓布尔型VSM掩码，是系统中针对每个学院都有与训练文档词条对应的掩码向量V=(v1,v2...vi...vn) ，其中n为语料库中词语的总数，vi的值设置为0或者1，表示vi这个词出现与否。每个学院根据自己专业的核心词汇可以生成上述的向量，我们称之为本专业的布尔型VSM掩码，如表1所示。

表1　布尔型VSM掩码举例

3.2.2初分类算法

为了实现系统对问题的初步分类，我们提出了一种基于布尔型VSM掩码的分类方法，算法如图3所示。

图3　布尔型VSM掩码初分类算法

3.3FAQ库的匹配

当用户输入完问题，分析问题之后，通过初分类提取出问题所属的专业库，将问题直接与FAQ常用问题库进行问句匹配，即句子相似度的计算，直接运用改进的编辑距离算法计算，当句子相似度的值大于一定的阀值，则选出相应的句子答案。若拥有多个句子相似度的值大于设定的阀值，则直接返回句子相似度值最大的问句答案。若所返回句子相似度的值小于设定的阀值，则使用其他策略。

4实验

通过调查收集某高校计算机科学与技术学院，化学化工学院，物理与材料科学学院，管理学院等学生在选课过程提出的问题集，以及各学院教学秘书和教务处回答作为答案集。

4.1初分类实验结果

实验结果显示，基于布尔型的VSM掩码初分类方法，对于将问题分到不同的院系类别中，只要专业的词典建立的比较丰富，分类效果非常好，平均正确率在96%以上，如表2所示。

表2　初分类实验结果

4.2相似度计算实验结果

因为中文有不同的语序表达同一个意思，所以，直接对上述的初分类结果，用编辑距离方法计算相似度计算进行细分类，效果并不理想，如表3所示。

表3　编辑距离相似度计算实验结果

出现上述这种结果的主要原因是因为类似“在什么时候选量子力学”和“量子力学选课在什么时候”这样的问题只是颠倒了语序，他们的语意相似度非常的高，但是，用编辑距离计算的话，这样两句话的距离却非常的远，基于此，我们选取了可以处理颠倒语序却同义的改进的编辑距离的方法，提高效果，如表4所示。

表4　采用改进的编辑距离相似度计算

综上，通过初分类的方法，确定问题是所属的学科，再通过改进的编辑距离方法进一步确定问题是什么，通过两次效果的叠加，可以获取到一个时间性能和效果都很不错的一个分类器，基本满足了问答系统的要求。

5结束语

本文主要针对教务管理中，开展学生选课自动问答系统的研究，采用了一种基于布尔型VSM掩码的分类方法和改进的编辑距离算法计算句子相似度，提高了系统返回问题的准确率。该方法在小规模的领域中测试效果较好。但是在处理巨量的信息领域，该方法在时间上体现出了明显的不足。这有待于算法的进一步完善。另外，还存在初分类的专业词典要求较高问题，这也是未来有待改进的地方。

[参考文献]

[1]赵作鹏，尹志民，王潜平，许新征，江海峰。一种改进的编辑距离算法及其在数据处理中的应用[J]，计算机应用，2009，29(2):424-426.

[2]刘里，曾庆田，自动问答系统研究综述[J]，山东科技大学学报(自然科学版) ,2007,26(4):73-76.

[3]钱强，庞林斌，高尚，一种基于词共现图的受限领域自动问答系统[J],计算机应用研究，2013,30(3):841-843.

[4]LEVENSHTEIN V L.Binary codes capable of correcting deletions,Insertions and reversals[J].Doklady Akademii Nauk SSSR,1966,163(4):707-710.

[5]LOWRANCE R,WAGNER R A.An extension of the string to string correction problem[J]. Journal of the ACM,1975,22(2):177-183.

[6]张宇, 刘挺, 文勖. 基于改进贝叶斯模型的问题分类[J]. 中文信息学报, 2005(2).

[7]余正涛, 樊孝忠, 郭剑毅, 耿曾民. 基于潜在语义分析的汉语问答系统答案提取[J]. 计算机学报, 2006(10).

[8]胡宝顺, 王大玲, 于戈, 马婷. 基于句法结构特征分析及分类技术的答案提取算法[J]. 计算机学报, 2008(04).

[9]Wang S K M，Ziarko W，Wong P C N． Generalized vector space model in information retrieval[C]/ /Proceedings of the 8th annual international ACM SIGIR conference on research and development in information retrieval． 1985: 18-25．

Sentence Similarity Computing in Question Answering System for Specific Domain

LI Jian, ZHENG Cheng, DAI Ning

(SchoolofComputerScienceandTechnology,AnhuiUniversity,Hefei230001,China)

Abstract：The technique of sentence similarity computing in question answering system for students' course selection in the educational administration is presented. Firstly, preliminary classification is implemented by using a method based on VSM mask of Boolean. Secondly, sentence similarity computing is carried out through the improved editting distance algorithm. Finally the best answer of the problem is returned. The experimental results show that the method is feasible.

Key words：question answering; VSM; editting distance; similarity computing

[中图分类号]TP391.1

[文献标识码]A

[文章编号]1674-2273(2015)06-0038-04

作者简介][第一 李健(-)，男，安徽大学计算机科学与技术学院硕士研究生。

[基金项目]安徽省高校自然科学研究重点项目(KJ2013A020)资助和安徽大学科研训练计划资助

[收稿日期]2015-05-08