基于三支概念分析的地理試題自動解題

洪啟航,楊思春

(安徽工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院, 安徽 馬鞍山 243032)

隨著計算機技術(shù)的快速發(fā)展,人工智能技術(shù)滲透到各個領(lǐng)域,如智能管理、智能優(yōu)化等[1-2].近年來,國內(nèi)外研究機構(gòu)開始研究如何讓計算機來自動解題,比如日本大學(xué)入學(xué)考試機器人、科大訊飛高考答題機器人等.目前,自動解題已成為人工智能領(lǐng)域的研究熱點,除了基于數(shù)學(xué)模型的試題自動解題外[3],還出現(xiàn)了應(yīng)用于地理等學(xué)科的自動解題系統(tǒng)[4-5].作為自動解題技術(shù)的核心,解題知識的獲取直接決定了自動解題系統(tǒng)的性能.現(xiàn)有自動解題系統(tǒng)主要通過手工或半自動方式從試題文本及相關(guān)資源中獲取相關(guān)解題知識.但是,對自動解題系統(tǒng)來說,這些知識可能還不足以支持正確解題,還需要深度挖掘知識.

形式概念分析[6]作為數(shù)據(jù)挖掘領(lǐng)域一種有效的數(shù)據(jù)分析和知識獲取工具,可以挖掘?qū)ο?樣本)與屬性(特征)之間隱含的各種類型規(guī)則知識,并已成功應(yīng)用于形式?jīng)Q策分析、屬性簡約、知識獲取[7-10]等領(lǐng)域.傳統(tǒng)的形式概念分析理論僅支持二支決策,三支概念分析將具有兩支決策的形式概念分析推廣為支持三支決策,進而實現(xiàn)更為有效的數(shù)據(jù)分析和知識發(fā)現(xiàn)[11-14].本文基于三支概念分析理論,通過挖掘試題文本中隱含的解題知識,拓展現(xiàn)有自動解題系統(tǒng)的隱含解題知識獲取途徑,為自動解題的語義分析提供更充分的支持,進而提升自動解題系統(tǒng)的性能.

1 試題文本語義分析

對試題文本進行語義分析是自動解題系統(tǒng)的基礎(chǔ),它直接關(guān)系到自動解題系統(tǒng)的性能.本文利用相關(guān)自然語言處理技術(shù),通過對試題文本進行分詞、詞性標(biāo)注、關(guān)鍵詞提取、實體關(guān)聯(lián)類及其屬性提取等操作,實現(xiàn)對試題文本的關(guān)鍵特征信息提取,進而為后續(xù)獲取隱含解題知識提供基礎(chǔ).

1) 分詞和詞性標(biāo)注.采用開源中文分詞工具包結(jié)巴分詞(Jieba)和詞性標(biāo)注器NLTK[18]對試題文本進行分詞和詞性標(biāo)注,同時結(jié)合領(lǐng)域詞典提高分詞準(zhǔn)確率.本文以地理課程為例,所構(gòu)造的領(lǐng)域詞典共收集4 930個術(shù)語詞,分成10個不同的類型,并以[關(guān)鍵字,分類,上級,下級]四元組的形式存儲.為了提高試題文本分詞結(jié)果的準(zhǔn)確率,對分詞結(jié)果進行預(yù)處理,包括去除副詞、虛詞、停用詞等;加入領(lǐng)域詞典以保證領(lǐng)域詞匯不被分開.

試題1：減少各個國家和地區(qū)的貿(mào)易限制、控制和減免關(guān)稅等是下列哪個國際組織的主要職能？

A. IOC B. OAO

C. OPEC D. WTO

對該試題進行分詞和詞性標(biāo)注后的結(jié)果為：

減少/vi各個/v國家/n和/v地區(qū)/n的/p貿(mào)易/n限制/n、控制/vi和/f減免/vi關(guān)稅/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中的“貿(mào)易”和“限制”通過領(lǐng)域詞典結(jié)合成“貿(mào)易限制”,“國際”和“組織”通過領(lǐng)域詞典結(jié)合成“國際組織”.

2) 關(guān)鍵詞提取.利用TextRank提取試題文本中的關(guān)鍵詞.TextRank是一種基于詞語鏈條之間共現(xiàn)關(guān)系的文本提取算法.試題1應(yīng)用TextRank算法得到關(guān)鍵詞集合[‘貿(mào)易限制’,‘關(guān)稅’,‘國際組織’,‘主要職能’].

3) 實體關(guān)聯(lián)類及其屬性提取.基于三支概念分析理論進行試題文本隱含解題知識獲取需要從試題文本中提取決策形式背景構(gòu)建所對應(yīng)的對象和屬性信息.實體關(guān)聯(lián)類及其屬性提取的具體流程為：① 把試題文本中所有的關(guān)鍵詞作為實體;② 針對每個實體分別計算它與領(lǐng)域詞典中每個概念的相似度,把相似度排名前二的概念作為該實體的關(guān)聯(lián)類,并作為后續(xù)所需構(gòu)建決策形式背景的對象集;③ 搜索該實體及其實體關(guān)聯(lián)類在領(lǐng)域詞典的鍵值,得到包含實體的四元組集合;④ 檢索實體及其實體關(guān)聯(lián)類的上級與同級信息,若能檢索到(≠?)則將該信息添加到該實體的實體關(guān)聯(lián)類集合;⑤ 檢索實體及其實體關(guān)聯(lián)類的下級信息,若能檢索到則將該信息作為后續(xù)所需構(gòu)建決策形式背景的屬性集.

對于試題1,其實體關(guān)聯(lián)類及其屬性提取的具體步驟為：① 根據(jù)試題1得到的關(guān)鍵詞集合為：[‘貿(mào)易限制’,‘關(guān)稅’,‘國際組織’,‘主要職能’] 為試題實體;② 計算每個實體與領(lǐng)域詞典中每個概念的相似度,把相似度排名前二的概念作為該實體的關(guān)聯(lián)類,并作為后續(xù)所需構(gòu)建決策形式背景的對象集，試題1中‘國際組織’=[‘國際機構(gòu)’,‘國際團體’];③ 搜索每個實體及其實體關(guān)聯(lián)類在領(lǐng)域詞典的鍵值,得到包含實體的四元組集合,‘關(guān)稅’的四元組集合為：[實體：‘關(guān)稅’,上級：‘稅收’,下級：‘優(yōu)惠關(guān)稅’、‘保護關(guān)稅’、‘反傾銷關(guān)稅’、‘反補貼關(guān)稅’、‘報復(fù)關(guān)稅’,同級：未檢索到(?)];④ 檢索實體及其實體關(guān)聯(lián)類的上級與同級信息,若能檢索到則將該信息添加到該實體的實體關(guān)聯(lián)類集合,‘關(guān)稅’：上級檢索到‘稅收’,同級未檢索到,將‘稅收’加入‘關(guān)稅’的實體關(guān)聯(lián)類集合;⑤ 檢索實體及其實體關(guān)聯(lián)類的下級信息,若能檢索到則將該信息作為后續(xù)所需構(gòu)建決策形式背景的屬性集,‘稅收’：下級檢索到‘稅收優(yōu)惠關(guān)稅’、‘保護關(guān)稅’、‘反傾銷關(guān)稅’、‘反補貼關(guān)稅’、‘報復(fù)關(guān)稅’,將這些下級信息添加到 ‘關(guān)稅’的屬性集合.

2 基于三支概念分析的試題文本隱含解題知識獲取

基于三支概念分析理論,對試題文本進行語義分析后,通過試題文本決策形式背景構(gòu)造、三支概念格構(gòu)建和決策規(guī)則提取實現(xiàn)試題文本中隱含解題知識的獲取.

2.1 試題文本的決策形式背景構(gòu)造

對試題文本進行三支概念分析時,根據(jù)試題文本中每個實體的關(guān)聯(lián)類及其屬性來構(gòu)造試題文本的決策形式背景.

根據(jù)試題1中提取的每個實體關(guān)聯(lián)類及其屬性,構(gòu)造該試題的決策形式背景,如表1所示.表1中：G為試題的實體關(guān)聯(lián)類集合，G={‘國際組織’,‘貿(mào)易限制’,‘關(guān)稅’,‘稅收’,‘主要職能’},以X1—X5表示;M為實體的屬性集，M=[‘惠關(guān)稅’,‘保護關(guān)稅’,‘聯(lián)合國’,‘世界衛(wèi)生組織’,‘管理國際問題’],以C1—C5表示;試題的4個選項作為決策屬性集N，N=[‘IOC’,‘OAO’,‘OPEC ’,‘WTO’],以V1—V4表示；×表示XI對象具有CJ/VJ屬性,其中對象與屬性的關(guān)系以I表示,對象與決策屬性的關(guān)系以J表示.

表1 決策形式背景

2.2 試題文本的三支概念格構(gòu)建

表1所示決策形式背景的三支概念格具體構(gòu)建過程為：

1) 構(gòu)造表1所示決策形式背景的補背景L(K-),如表2所示.

表2 決策形式背景的補背景

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

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

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

3) 采用文獻[17]中的三支概念格構(gòu)造算法,分別構(gòu)建表1所示決策形式背景的對象導(dǎo)出三支概念格OEL(G,M,I)和OEL(G,N,J),如圖3、圖4所示.同理,構(gòu)建屬性導(dǎo)出三支概念格AEL(G,N,J)和AEL(G,M,I),如圖5、圖6所示.

圖3 對象導(dǎo)出三支概念格OEL(G,M,I)

圖4 對象導(dǎo)出三支概念格OEL(G,N,J)

圖5 屬性導(dǎo)出三支概念格AEL(G,N,J)

圖6 屬性導(dǎo)出三支概念格AEL(G,M,I)

4) 對于屬性導(dǎo)出候選三支概念格AEL(K)中的((A1,B1),C1)和((A2,B2),C2),若C1=C2 且 (A1?A2或B1?B2),則((A1,B1),C1)作為冗余概念刪除;對于對象導(dǎo)出候選三支概念格OEL(K)中的(A1,(B1,C1))和((A2((B2,C2)),若A1=A2且(C1?C2或B1?B2),則(A1,(B1,C1))作為冗余概念刪除.

2.3 基于三支合并概念格的試題文本決策規(guī)則提取

在構(gòu)建對象/屬性導(dǎo)出三支概念格基礎(chǔ)上,構(gòu)建對象/屬性導(dǎo)出合并三支概念格OAEL(G,M,I)和對象/屬性導(dǎo)出合并三支概念格OAEL(G,N,J),然后基于所構(gòu)建的對象/屬性導(dǎo)出合并三支概念格實現(xiàn)決策規(guī)則提取.基于對象/屬性導(dǎo)出合并三支概念格的規(guī)則提取流程為：

1) 構(gòu)建決策形式背景的補背景;

2) 根據(jù)形式背景分別生成概念格L(G,M,I)與決策概念格L(G,N,J);

3) 對概念格L(G,M,I)分別構(gòu)建對象導(dǎo)出三支概念格OEL(G,M,I)與屬性導(dǎo)出三支概念格AEL(G,M,I);

4) 對概念格L(G,N,J)分別構(gòu)建屬性導(dǎo)出三支概念格AEL(G,N,J)與屬性導(dǎo)出三支概念格AEL(G,N,J);

5) 對AEL(G,M,I)中的每個概念((X,Y),A)),若OEL(G,M,I)中存在對應(yīng)概念(X,(A,B))或(Y,(B,A)),則生成新概念((X,Y), (A,B)),基于以上方法,根據(jù)表1的決策形式背景(G,M,I,N,J),分別構(gòu)建對象/屬性導(dǎo)出合并三支概念格OAEL(G,M,I)與對象/屬性導(dǎo)出合并三支概念格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,則導(dǎo)出新規(guī)則R=R∪{A→C,B→D},相比文獻[17]中X=Z且Y=W時導(dǎo)出的規(guī)則,該方法可以得到更多有用規(guī)則,但同時也會生成更多冗余規(guī)則;

7) 去除冗余規(guī)則,對規(guī)則(X,{A→C})和((Y,{B→D}),若滿足X=Y、A?B、C?D,則規(guī)則((Y,{B→D})是冗余規(guī)則,同時,前提或結(jié)論為?的規(guī)則也為冗余規(guī)則;

8) 簡化規(guī)則,對于規(guī)則A→C、規(guī)則B→F,若有A=B,則用新規(guī)則A→C∪F替代原規(guī)則;

9) 置信度計算,進一步優(yōu)化規(guī)則.

這里,規(guī)則的置信度和支持度分別定義為：

(1)

式中:X為對象集;V為決策屬性集;L(V)為決策屬性為VI的對象構(gòu)成的集合.

3 試驗結(jié)果與分析

3.1 試驗數(shù)據(jù)

本文以地理課程為例,試驗數(shù)據(jù)主要來自學(xué)科網(wǎng)、新東方在線網(wǎng)絡(luò)課程、億庫地理、組卷網(wǎng)、百度百科以及中學(xué)地理課程教材,收集了1 027道地理選擇題,題型涵蓋了地理試題中10個不同的類.

3.2 試驗結(jié)果分析

為驗證本文所提隱含解題知識獲取方法對自動解題的貢獻,在前期開發(fā)的地理課程自動解題原型系統(tǒng)的基礎(chǔ)上,通過向原來的本體知識庫加入所獲取的三支概念格規(guī)則來驗證實際解題效果.

表3給出了傳統(tǒng)本體知識庫及加入三支概念格規(guī)則后的本體知識庫在各類試題上的有效解題結(jié)果.由表3可見：與傳統(tǒng)本體知識庫的自動解題效果相比,加入三支概念格規(guī)則的本體知識庫自動解題效果比傳統(tǒng)方法提高了4.8%；加入三支概念格規(guī)則的本體知識庫在對比類、陳述類試題上的解題效果有明顯提升,這是因為這類試題的解答往往需要一定的推理,而基于三支概念分析從試題文本中所獲取的相關(guān)決策規(guī)則在推理方面有明顯的優(yōu)勢；本文所提方法在含有圖片或表格類試題上的解題效果提升不明顯,這是因為在構(gòu)建試題本體時是通過百度API接口實現(xiàn)圖片文字識別并結(jié)合人工描述圖片信息,而圖片文字識別技術(shù)及人工描述圖片信息可能與實際信息存在一定出入,對于這類題目往往不能構(gòu)建出有效本體.后續(xù)研究將考慮引入OpenCV模塊實現(xiàn)圖片非文字信息的圖像識別.

表3 傳統(tǒng)本體知識庫和加入三支概念格規(guī)則的本體知識庫在各類試題上的有效解題結(jié)果

4 結(jié)語

針對現(xiàn)有自動解題系統(tǒng)難以獲取試題文本中隱含解題知識的問題,本文基于三支概念分析理論,通過決策形式背景構(gòu)造、三支概念格構(gòu)建和決策規(guī)則提取,實現(xiàn)試題文本中隱含解題知識的獲取.同時,將所獲取的這些隱含解題知識加入到傳統(tǒng)的本體知識庫中,以提升現(xiàn)有自動解題系統(tǒng)的解題效果.試驗結(jié)果驗證了三支概念格規(guī)則對自動解題的有效性.后續(xù)研究中,將逐步擴大試題集規(guī)模和覆蓋面,使得本文方法具有更好的適用性;對其他學(xué)科(比如歷史/語文學(xué)科)的試題進行試驗,進一步驗證本文方法的通用性.