基于三支概念分析的地理试题自动解题

洪启航,杨思春

(安徽工业大学计算机科学与技术学院, 安徽 马鞍山 243032)

随着计算机技术的快速发展,人工智能技术渗透到各个领域,如智能管理、智能优化等[1-2].近年来,国内外研究机构开始研究如何让计算机来自动解题,比如日本大学入学考试机器人、科大讯飞高考答题机器人等.目前,自动解题已成为人工智能领域的研究热点,除了基于数学模型的试题自动解题外[3],还出现了应用于地理等学科的自动解题系统[4-5].作为自动解题技术的核心,解题知识的获取直接决定了自动解题系统的性能.现有自动解题系统主要通过手工或半自动方式从试题文本及相关资源中获取相关解题知识.但是,对自动解题系统来说,这些知识可能还不足以支持正确解题,还需要深度挖掘知识.

形式概念分析[6]作为数据挖掘领域一种有效的数据分析和知识获取工具,可以挖掘对象(样本)与属性(特征)之间隐含的各种类型规则知识,并已成功应用于形式决策分析、属性简约、知识获取[7-10]等领域.传统的形式概念分析理论仅支持二支决策,三支概念分析将具有两支决策的形式概念分析推广为支持三支决策,进而实现更为有效的数据分析和知识发现[11-14].本文基于三支概念分析理论,通过挖掘试题文本中隐含的解题知识,拓展现有自动解题系统的隐含解题知识获取途径,为自动解题的语义分析提供更充分的支持,进而提升自动解题系统的性能.

1 试题文本语义分析

对试题文本进行语义分析是自动解题系统的基础,它直接关系到自动解题系统的性能.本文利用相关自然语言处理技术,通过对试题文本进行分词、词性标注、关键词提取、实体关联类及其属性提取等操作,实现对试题文本的关键特征信息提取,进而为后续获取隐含解题知识提供基础.

1) 分词和词性标注.采用开源中文分词工具包结巴分词(Jieba)和词性标注器NLTK[18]对试题文本进行分词和词性标注,同时结合领域词典提高分词准确率.本文以地理课程为例,所构造的领域词典共收集4 930个术语词,分成10个不同的类型,并以[关键字,分类,上级,下级]四元组的形式存储.为了提高试题文本分词结果的准确率,对分词结果进行预处理,包括去除副词、虚词、停用词等;加入领域词典以保证领域词汇不被分开.

试题1：减少各个国家和地区的贸易限制、控制和减免关税等是下列哪个国际组织的主要职能？

A. IOC B. OAO

C. OPEC D. WTO

对该试题进行分词和词性标注后的结果为：

减少/vi各个/v国家/n和/v地区/n的/p贸易/n限制/n、控制/vi和/f减免/vi关税/n等/f是/v下列/r哪个/r国际/n组织/n的/p主要/r职能/n？/wky

A. /n IOC/n B. /n OAO/n

C. /n OPEC/n D. /n WTO/n

试题1中的“贸易”和“限制”通过领域词典结合成“贸易限制”,“国际”和“组织”通过领域词典结合成“国际组织”.

2) 关键词提取.利用TextRank提取试题文本中的关键词.TextRank是一种基于词语链条之间共现关系的文本提取算法.试题1应用TextRank算法得到关键词集合[‘贸易限制’,‘关税’,‘国际组织’,‘主要职能’].

3) 实体关联类及其属性提取.基于三支概念分析理论进行试题文本隐含解题知识获取需要从试题文本中提取决策形式背景构建所对应的对象和属性信息.实体关联类及其属性提取的具体流程为：① 把试题文本中所有的关键词作为实体;② 针对每个实体分别计算它与领域词典中每个概念的相似度,把相似度排名前二的概念作为该实体的关联类,并作为后续所需构建决策形式背景的对象集;③ 搜索该实体及其实体关联类在领域词典的键值,得到包含实体的四元组集合;④ 检索实体及其实体关联类的上级与同级信息,若能检索到(≠∅)则将该信息添加到该实体的实体关联类集合;⑤ 检索实体及其实体关联类的下级信息,若能检索到则将该信息作为后续所需构建决策形式背景的属性集.

对于试题1,其实体关联类及其属性提取的具体步骤为：① 根据试题1得到的关键词集合为：[‘贸易限制’,‘关税’,‘国际组织’,‘主要职能’] 为试题实体;② 计算每个实体与领域词典中每个概念的相似度,把相似度排名前二的概念作为该实体的关联类,并作为后续所需构建决策形式背景的对象集，试题1中‘国际组织’=[‘国际机构’,‘国际团体’];③ 搜索每个实体及其实体关联类在领域词典的键值,得到包含实体的四元组集合,‘关税’的四元组集合为：[实体：‘关税’,上级：‘税收’,下级：‘优惠关税’、‘保护关税’、‘反倾销关税’、‘反补贴关税’、‘报复关税’,同级：未检索到(∅)];④ 检索实体及其实体关联类的上级与同级信息,若能检索到则将该信息添加到该实体的实体关联类集合,‘关税’：上级检索到‘税收’,同级未检索到,将‘税收’加入‘关税’的实体关联类集合;⑤ 检索实体及其实体关联类的下级信息,若能检索到则将该信息作为后续所需构建决策形式背景的属性集,‘税收’：下级检索到‘税收优惠关税’、‘保护关税’、‘反倾销关税’、‘反补贴关税’、‘报复关税’,将这些下级信息添加到 ‘关税’的属性集合.

2 基于三支概念分析的试题文本隐含解题知识获取

基于三支概念分析理论,对试题文本进行语义分析后,通过试题文本决策形式背景构造、三支概念格构建和决策规则提取实现试题文本中隐含解题知识的获取.

2.1 试题文本的决策形式背景构造

对试题文本进行三支概念分析时,根据试题文本中每个实体的关联类及其属性来构造试题文本的决策形式背景.

根据试题1中提取的每个实体关联类及其属性,构造该试题的决策形式背景,如表1所示.表1中：G为试题的实体关联类集合，G={‘国际组织’,‘贸易限制’,‘关税’,‘税收’,‘主要职能’},以X1—X5表示;M为实体的属性集，M=[‘惠关税’,‘保护关税’,‘联合国’,‘世界卫生组织’,‘管理国际问题’],以C1—C5表示;试题的4个选项作为决策属性集N，N=[‘IOC’,‘OAO’,‘OPEC ’,‘WTO’],以V1—V4表示；×表示XI对象具有CJ/VJ属性,其中对象与属性的关系以I表示,对象与决策属性的关系以J表示.

表1 决策形式背景

2.2 试题文本的三支概念格构建

表1所示决策形式背景的三支概念格具体构建过程为：

1) 构造表1所示决策形式背景的补背景L(K-),如表2所示.

表2 决策形式背景的补背景

2) 采用Cbo算法[14-15,17]构建表1所示决策形式背景的概念格L(G,M,I)和L(G,N,J),如图1、图2所示.

图1 概念格L(G,M,I)

图2 概念格L(G,N,J)

3) 采用文献[17]中的三支概念格构造算法,分别构建表1所示决策形式背景的对象导出三支概念格OEL(G,M,I)和OEL(G,N,J),如图3、图4所示.同理,构建属性导出三支概念格AEL(G,N,J)和AEL(G,M,I),如图5、图6所示.

图3 对象导出三支概念格OEL(G,M,I)

图4 对象导出三支概念格OEL(G,N,J)

图5 属性导出三支概念格AEL(G,N,J)

图6 属性导出三支概念格AEL(G,M,I)

4) 对于属性导出候选三支概念格AEL(K)中的((A1,B1),C1)和((A2,B2),C2),若C1=C2 且 (A1⊆A2或B1⊆B2),则((A1,B1),C1)作为冗余概念删除;对于对象导出候选三支概念格OEL(K)中的(A1,(B1,C1))和((A2((B2,C2)),若A1=A2且(C1⊆C2或B1⊆B2),则(A1,(B1,C1))作为冗余概念删除.

2.3 基于三支合并概念格的试题文本决策规则提取

在构建对象/属性导出三支概念格基础上,构建对象/属性导出合并三支概念格OAEL(G,M,I)和对象/属性导出合并三支概念格OAEL(G,N,J),然后基于所构建的对象/属性导出合并三支概念格实现决策规则提取.基于对象/属性导出合并三支概念格的规则提取流程为：

1) 构建决策形式背景的补背景;

2) 根据形式背景分别生成概念格L(G,M,I)与决策概念格L(G,N,J);

3) 对概念格L(G,M,I)分别构建对象导出三支概念格OEL(G,M,I)与属性导出三支概念格AEL(G,M,I);

4) 对概念格L(G,N,J)分别构建属性导出三支概念格AEL(G,N,J)与属性导出三支概念格AEL(G,N,J);

5) 对AEL(G,M,I)中的每个概念((X,Y),A)),若OEL(G,M,I)中存在对应概念(X,(A,B))或(Y,(B,A)),则生成新概念((X,Y), (A,B)),基于以上方法,根据表1的决策形式背景(G,M,I,N,J),分别构建对象/属性导出合并三支概念格OAEL(G,M,I)与对象/属性导出合并三支概念格OAEL(G,N,J);

6) 若OAEL(G,M,I)中存在概念((X,Y),(A,B)),OAEL(G,N,J)中存在概念((Z,W),(C,D)),且满足X⊆Z、Y⊆W,则导出新规则R=R∪{A→C,B→D},相比文献[17]中X=Z且Y=W时导出的规则,该方法可以得到更多有用规则,但同时也会生成更多冗余规则;

7) 去除冗余规则,对规则(X,{A→C})和((Y,{B→D}),若满足X=Y、A⊆B、C⊆D,则规则((Y,{B→D})是冗余规则,同时,前提或结论为∅的规则也为冗余规则;

8) 简化规则,对于规则A→C、规则B→F,若有A=B,则用新规则A→C∪F替代原规则;

9) 置信度计算,进一步优化规则.

这里,规则的置信度和支持度分别定义为：

(1)

式中:X为对象集;V为决策属性集;L(V)为决策属性为VI的对象构成的集合.

3 试验结果与分析

3.1 试验数据

本文以地理课程为例,试验数据主要来自学科网、新东方在线网络课程、亿库地理、组卷网、百度百科以及中学地理课程教材,收集了1 027道地理选择题,题型涵盖了地理试题中10个不同的类.

3.2 试验结果分析

为验证本文所提隐含解题知识获取方法对自动解题的贡献,在前期开发的地理课程自动解题原型系统的基础上,通过向原来的本体知识库加入所获取的三支概念格规则来验证实际解题效果.

表3给出了传统本体知识库及加入三支概念格规则后的本体知识库在各类试题上的有效解题结果.由表3可见：与传统本体知识库的自动解题效果相比,加入三支概念格规则的本体知识库自动解题效果比传统方法提高了4.8%；加入三支概念格规则的本体知识库在对比类、陈述类试题上的解题效果有明显提升,这是因为这类试题的解答往往需要一定的推理,而基于三支概念分析从试题文本中所获取的相关决策规则在推理方面有明显的优势；本文所提方法在含有图片或表格类试题上的解题效果提升不明显,这是因为在构建试题本体时是通过百度API接口实现图片文字识别并结合人工描述图片信息,而图片文字识别技术及人工描述图片信息可能与实际信息存在一定出入,对于这类题目往往不能构建出有效本体.后续研究将考虑引入OpenCV模块实现图片非文字信息的图像识别.

表3 传统本体知识库和加入三支概念格规则的本体知识库在各类试题上的有效解题结果

4 结语

针对现有自动解题系统难以获取试题文本中隐含解题知识的问题,本文基于三支概念分析理论,通过决策形式背景构造、三支概念格构建和决策规则提取,实现试题文本中隐含解题知识的获取.同时,将所获取的这些隐含解题知识加入到传统的本体知识库中,以提升现有自动解题系统的解题效果.试验结果验证了三支概念格规则对自动解题的有效性.后续研究中,将逐步扩大试题集规模和覆盖面,使得本文方法具有更好的适用性;对其他学科(比如历史/语文学科)的试题进行试验,进一步验证本文方法的通用性.