溫雪峰 崔仙姬 張俊星

（大連民族大學信息與通信工程學院 大連 116600）

1 引言

近年來，線上教育發(fā)展得更加豐富和多元化。線上教育是指通過互聯(lián)網(wǎng)、移動設(shè)備等傳播媒體實施教學的教育形式［1］。現(xiàn)階段線上教育已經(jīng)成為主流教育方式之外的另一大教育方式［2］。2020年1月爆發(fā)的新冠肺炎疫情，對在校學生的學習生活造成極大影響，大中小學寒假被迫延長，政府號召“停課不停學”，各大學校紛紛開展線上教育，以保證學生的學習生活。線上教育的一大重點便是線上考試，但現(xiàn)階段大多數(shù)線上考試系統(tǒng)的實現(xiàn)原理基本類似，都是人工將試題輸入到數(shù)據(jù)庫中，然后從數(shù)據(jù)庫中抽取試題組成試卷［3］。這種人工構(gòu)建試題庫的方式不僅需要耗費大量的人力和時間資源，而且難以控制試題的規(guī)范性以及試題的難度。通過自動生成試題，可以大大地減少出題時間，節(jié)省人力資源，試題更具規(guī)范，難度易于控制。

隨著語義網(wǎng)的發(fā)展以及在線知識庫發(fā)布知識的便利性，本體論進入了研究者的視野，研究人員開始研究如何通過本體測試特定領(lǐng)域的內(nèi)容。本體是通過抽象出客觀世界中一些現(xiàn)象的相關(guān)概念而得到的模型［4］，從不同層次的形式化模式上給出詞匯和詞匯之間相互關(guān)系的明確定義［5］。通過使用本體不僅可以讓電腦識別信息，人也可以明確其中含義，實現(xiàn)人機交互［6］。基于本體的上述特點，使用本體生成選擇題是一種便捷且高效的方法。本體作為知識的有效組織和表示形式，在線上考試當中受到了廣泛的關(guān)注和應(yīng)用［7］。

國內(nèi)外的研究人員將基于本體的試題自動生成的重點放在了選擇題自動生成方法的研究中。國外的研究工作有以下內(nèi)容，Edmond等首次將本體應(yīng)用于教育方面［8］，并于2006年提出了使用本體來生成評估問題的策略［9］。Andreas Papasalouros等提出了一種自動生成選擇題的方法，該方法基于本體公理以及OWL（Web Ontology Language）開發(fā)的知識庫中的斷言生成選擇題［10］。2010年Cubric和Tosic提出使用問題模板來避免自動生成的問題中的語法問題，并通過考慮新的本體元素（即注釋）擴展了他們以前的工作［11～12］。Al-Yahya等使用本體中有關(guān)領(lǐng)域?qū)嶓w（如類、屬性和個體）的固有知識來生成語義正確的評估項［13～14］。Vinu E.V等提出使用謂詞模式應(yīng)用本體以生成選擇題的方法［15］。2017年Vinu E.V等對謂詞模式生成選擇題的方法進行了改進，改進后的方法可以使用二元以上的謂詞模式生成題干，并提出了一種控制問題難度的方法［16］。

目前國內(nèi)的相關(guān)研究有以下內(nèi)容，劉明等提出了一種混合相似策略，用于自動生成漢語多項選擇題，該策略通過統(tǒng)計回歸模型生成漢語多項選擇干擾源［17］。肖文彥等提出了一種適合不同語言水平的非英語母語學習者的介詞多項選擇題生成方法［18］。劉昭麟等提出了一種詞義辨析的演算法，利用詞典和selection preference所提供的資訊，分析試題答案的詞義，并以collocation為基礎(chǔ)的方法篩選干擾項［19］。鹽城師范學院的丁向民等提出了通過元知識點模式和本體技術(shù)來自動生成多項選擇題的方法［20］。

目前基于本體自動生成選擇題的技術(shù)具有生成的問題數(shù)量龐大、問題相似度高、問題難度無法控制、干擾項質(zhì)量較低等問題。因此，需要對自動生成的題目進行進一步篩選，從而選擇合適的、具有代表性的問題進行測試，并選擇所需難度的高質(zhì)量干擾項對問題進行難度控制。基于上述問題，本文提出一種結(jié)合最小頂點覆蓋問題的相似性篩選方法對選擇題問題進行篩選，并通過計算選擇題選項之間的語義相似性生成對應(yīng)難度的干擾項來控制問題的整體難度。

2 基于本體的選擇題自動生成系統(tǒng)框架

如圖1所示，基于本體的選擇題自動生成系統(tǒng)主要包括三個模塊：題干生成模塊，問題篩選模塊以及干擾項生成模塊。題干生成模塊的主要作用是生成選擇題的題干部分；篩選模塊主要作用是通過篩選以減少問題的數(shù)量，選擇更具代表性的問題用于測試；整個系統(tǒng)中最后的一步是干擾項生成，干擾項是決定選擇題質(zhì)量和難度的主要因素，通過干擾項可以控制問題的難度級別。

圖1 選擇題自動生成系統(tǒng)

在基于本體的選擇題自動生成系統(tǒng)中，輸入一個本體文件，通過題干生成模塊生成數(shù)量龐大的問題，題干生成的主要方法是基于本體的元組，利用簡單的SPARQL查詢模板來生成問題。對于已生成的問題需要進一步進行篩選，否則問題的數(shù)量過于龐大、問題不具有代表性，不適合用于測試特定領(lǐng)域的知識。干擾項生成模塊用于生成選擇題的干擾項，使用可能答案減去正確選項的方法生成干擾項，選擇題的質(zhì)量難以保證，難易程度無法估計。通過計算干擾項與正確選項之間的相似性，進一步選擇干擾項，可以控制選擇題的質(zhì)量以及難易程度。為了解決上述問題，生成高質(zhì)量的選擇題題庫，應(yīng)用基于圖的最小頂點覆蓋問題的相似性篩選方法對問題進行篩選，并進一步應(yīng)用基于語義距離的相似性計算方法對干擾項進行篩選，選擇適當難度的干擾項。

3 選擇題自動生成優(yōu)化

3.1 選擇題問題篩選

在本體中存在大量的語義相似的元組，這些元組將產(chǎn)生大量的相似問題。以Geography本體為例，如表1所示，其中x表示核心實例，將作為問題的正確選項，O為對象屬性，i為實例。表中數(shù)據(jù)為題干生成模板的SPARQL查詢結(jié)果，該模板由兩個三元組構(gòu)成。從表1可以看出，在同一問題生成模板下，本體中存在大量對象屬性O(shè)1、O2相同的相似元組，而這些相似元組將產(chǎn)生大量的相似問題。在用于測試時，相似的問題降低了測試的效率以及質(zhì)量。為了避免問題集中存在語義相似的問題，必須從相似的元組中只選擇一組具有代表性的元組來生成問題。

表1 本體中部分相似的三元組

根據(jù)兩個元組中謂詞之間的關(guān)系和元組中語義相似三元組的數(shù)目，可以計算出兩個元組的相似度得分如式（1）。

在式（1）中P（t）表示三元組t的屬性序列，X（P（t））表示滿足屬性序列P（t）的實例。S imil ari ty(t1，t2)是確定兩個三元組相似性的對稱函數(shù)。#S E(t1，t2)表示t1與t2中語義相似的三元組個數(shù)，Max(#t1，t2)表示取t1與t2中三元組個數(shù)的最大值。公式的第一部分給出了基于對應(yīng)元組中匹配謂詞的分數(shù)。當元組中謂詞的一對一對應(yīng)時，X（P（t1））和X（P（t2））變得相等。在公式的第二部分中，通過考慮匹配時屬性之間的子性質(zhì)、對稱關(guān)系和逆關(guān)系，計算了三元組的語義等價性。

根據(jù)上面給出的兩個元組相似性得分，構(gòu)造一個無向圖G=(V，E)，無向圖的頂點集為V={t|t∈S}，其中t為三元組，S為三元組集合，根據(jù)元組之間的相似性關(guān)系構(gòu)建無向圖的邊，無向圖的邊集為E={(t1，t2)|t1，t2∈S and S imi larity(t1，t2)≤c}，其中c為最小相似性得分閾值，元組間的相似性得分作為無向圖邊的權(quán)重。

選擇題問題篩選的主要思想是從大量相似的元組中獲得少量的相似性較低的、能夠代表整個本體的元組。因此，可以將問題的篩選轉(zhuǎn)換為求無向圖G的最小頂點覆蓋問題。圖的最小頂點覆蓋問題是指給定一個無向圖G=（V，E），找到其最小的頂點覆蓋集，使得每條邊至少有一個頂點存在于最小頂點覆蓋集中。在文獻［15］中，研究者通過使用JGraphT（https：//jgrapht.org）中提供的最小頂點覆蓋近似算法進行了問題的篩選。這種篩選方法在構(gòu)建圖時僅將元組間的相似性關(guān)系作為構(gòu)建邊的條件，隨機選擇滿足條件的節(jié)點，這使得所篩選問題集并未充分考慮到元組之間相似性對于最小頂點覆蓋集的影響，不能保證篩選后得到的元組具有代表性。為了提高結(jié)果的質(zhì)量，使問題能夠更好地代表整個本體，本文將元組之間的相似性得分作為無向圖邊的權(quán)重，在求無向圖的最小頂點覆蓋集的過程中，將權(quán)重的影響加入其中。

基于NUMVC（A Novel Local Search for Minimum Vertex Cover Problem）的相似性篩選算法將元組之間的相似性得分作為權(quán)重，并且加入頂點刪除策略，使得最小頂點覆蓋集的結(jié)果更加準確，算法的搜索效率更高。利用基于NUMVC的相似性篩選算法可以得到無向圖中最少的頂點，使得這些頂點具有較小的相似性，頂點更具有代表性。包含不同問題的問題集比包含相似問題的問題集更傾向于檢查更廣泛的知識。為了使一個問題集足夠小，檢查相同的知識，刪除相似類型的問題，在其中保留一個有代表性的問題。

算法1：基于NUMVC的相似性篩選算法

輸入：無向圖G=（V，E）

輸出：無向圖G=（V，E）的最小頂點覆蓋子集V’。

1.InitializeV'←?No-improve←0 rmv-num←α；

2.while not found min（V'）

3.if No-improve==βand rmv-num≠1

4. rmv-num--；

5.for i=0；i

6. remove vertex v

7.whileV'exist uncovered edges

8. add vertex v

9.Remove redundant vertices inV'to getV''

10.if|V''|<|V'|

11.V'←V''

12.No-improve←0；

13.else No-improve++；

14.return min（V'）

基于NUMVC的相似性篩選算法的算法時間復(fù)雜度包括以下兩個部分：計算頂點的相似性（O(S|V|)），查找圖的最小頂點覆蓋（O(N|V|)），其中S表示式（1），由此可得算法1的時間復(fù)雜度為O(S|V|+N|V|)。

表2 相似性篩選后的元組

表2給出了表1中數(shù)據(jù)使用基于NUMVC的相似性篩選算法篩選之后的數(shù)據(jù)（m<

3.2 干擾項難度控制

在問題難度控制方面，目前的主要方式是通過題干與正確選項的關(guān)聯(lián)性控制問題難度，然后利用干擾項進一步調(diào)整問題的整體難度，將干擾項作為問題難度控制的輔助。

本文考慮在同一個問題模板下，利用干擾項的難度直接控制問題的整體難度，忽略題干對于問題難度的影響，可以避免題干形式不統(tǒng)一、問題難以管理等問題。通過計算正確選項與干擾項的相似性，選擇對應(yīng)難度的干擾項，可以控制問題的整體難度，以生成高質(zhì)量且所需難度等級的選擇題。

干擾項是從問題的可能答案集合中減去正確答案而產(chǎn)生的。正確答案指的是本體中那些滿足題干中給出的條件的實例。如果通過上述操作得到空集或與所需的選項數(shù)相比較少的干擾項（d≤3），除了可能答案集合中的干擾項之外，可以選擇其他任何元組中的實例或數(shù)據(jù)類型值作為干擾項。

正確選項與干擾項相似度計算的主要方法是考慮二者之間的距離，其基本原理是：從本體結(jié)構(gòu)圖出發(fā)，相似程度較低的概念之間的距離就會越長。路程不同的兩個概念之間對于語義相似度計算的結(jié)果也會產(chǎn)生一定的影響甚至是誤差。為了避免這種影響與誤差的存在，在計算兩個概念之間的相似度時，可以充分利用另外一種對語義相似度計算有影響的因素，也就是兩個概念之間最近共同父節(jié)點深度。如果兩個本體概念之間的最近共同父節(jié)點的深度越淺，那就表示分類越不明確，進而可以說明繼承語義的信息越少，也就是兩個本體概念之間的相似度越低。式（2）和式（3）為根據(jù)語義距離和父節(jié)點深度計算正確選項與干擾項的相似性得分公式。

式（2）表示概念c1到c1與c2的最近公共父節(jié)點的最短路徑，mp（c2，RCPN（c1，c2））表示概念c2到c1與c2的最近公共父節(jié)點的最短路徑，RCPN（c1，c2）表示c1與c2的最近公共父節(jié)點。考慮到節(jié)點深度對相似性的影響，利用式（3）來計算正確選項與干擾項之間的相似性。式（3）為基于本體語義距離的正確選項與干擾項的相似度計算公式，其中d p(R C PN(c1，c2)，c1)表示概念對c1和c2的最近公共父節(jié)點，在概念c1所在本體結(jié)構(gòu)圖中的深度，max（dp（c1））表示概念c1的本體樹的最大深度。

基于式（2）和式（3）的計算結(jié)果，設(shè)計了一種干擾項難度控制算法，如算法2所示。通過輸入正確選項、干擾項集合以及問題難度等級，利用式（2）和式（3）分別計算正確選項與干擾項集合中干擾項d的相似度，將相似性得分作為干擾項的難度得分Dscore，結(jié)合對應(yīng)的難度等級，對Dscore進行判斷，獲取滿足難度等級的干擾項d。最后輸出干擾項d以及其難度得分Dscore。

干擾項難度控制算法通過節(jié)點之間的距離因素以及節(jié)點最近父節(jié)點因素的共同作用計算節(jié)點之間的相似性，使得相似性結(jié)果更加精確。

干擾項難度控制算法的算法時間復(fù)雜度包括以下兩個方面：計算選項之間的相似性（O(D||d+S|d|)），選擇對應(yīng)難度的干擾項（O(C|d|))），其中D表示式（2），S表示式（3），由此可得算法2的時間復(fù)雜度為O(D||d+S||d+C|d|)。

算法2：干擾項難度控制算法

輸入：key，一個實例（正確選項）

D，干擾項集合

Difficulty-level∈｛high，medium，low｝

輸出：d，干擾項，Dscore，難度得分

1.whileD≠?

2.for each instance d in D

3. countS ims d(c1，c2)

4. dscore←Simsd(c1，c2)

5. if Difficulty-level==hight

6.d={d|0.50≤d score<1}

7. if Difficulty-level==low

8.d={d|0≤d score<0.50}

9. if Diffaculty-level==medium

10.d={d|0.35≤d sc ore≤0.75}

11. Remove d in D to getD'

12.D←D'

13.return d andDscore

4 實驗評估

下面評價題干篩選方法以及干擾項難度控制方法的有效性，主要圍繞以下兩個方面來展開：1）測試基于NUMVC的相似性篩選算法對于題干篩選的可行性與有效性；2）測試干擾項難度控制算法在干擾項生成中的可行性與有效性。

本次實驗在如下環(huán)境中進行：Inter core i5 1.4Ghz CPU；4.0GB RAM，MasOS Catalina，而本體的解析通過調(diào)用JenaAPI（https：//jena.apache.org）實現(xiàn)。

4.1 問題篩選

實驗中使用的本體數(shù)據(jù)集由德克薩斯大學奧斯汀分校的Ray Mooney和他的團隊提供，數(shù)據(jù)集中包含三個OWL知識庫組成，三個OWL知識庫涉及三個不同的領(lǐng)域：地理信息（Geography）、工作信息（Job）以及餐廳信息（Restaurant）。如表3中的數(shù)據(jù)所示，表中第一行數(shù)據(jù)為本體名稱，第二行數(shù)據(jù)為本體中的對象屬性數(shù)目（Object properties），如表1和表2中的O1和O2，第三行為數(shù)據(jù)類型屬性的數(shù)目（Datatype properties），第四行為本體中元組總數(shù)（Total tuple count）。在本體中存在大量的元組，這些元組將生成難以管理、數(shù)量眾多的問題。

首先根據(jù)元組的屬性進行初步的篩選，篩選結(jié)果如表4所示。根據(jù)屬性對元組進行篩選的主要目的是將元組中那些不太可能用于測試的元組篩選掉，這些元組構(gòu)成的問題可能太過簡單或者太過難以回答。

表3 樣本本體的屬性與相應(yīng)的元組計數(shù)

表4 屬性篩選后本體的屬性與相應(yīng)的元組計數(shù)

在根據(jù)屬性進行初步篩選后，對剩余的元組分別使用文獻［15］中的算法和本文中的NUMVC算法進行相似性篩選，結(jié)果如表5所示，表中最后一行給出了元組的減少比例（TR）。從表5的對比結(jié)果可以看出，基于NUMVC的相似性篩選算法在對三個本體進行問題篩選操作時，分別比其他問題篩選方法多減少了15%、20%、10%的三元組數(shù)量，由此可見基于NUMVC的相似篩選算法在問題篩選方面有較為明顯的優(yōu)勢。

從大量的相似的元組中獲得數(shù)量較少具有代表性的元組，使用這些元組生成選擇題，使得問題集中問題的數(shù)量減少，更加易于管理，問題也更具有代表性。由于不同本體獲得的代表性元組數(shù)量不同，所以不同本體問題集中的問題數(shù)量也不同。

表5 問題篩選結(jié)果及對比結(jié)果

4.2 干擾項生成

在測試干擾項難度控制算法時，對輸入相應(yīng)問題難度等級，能否準確輸出對應(yīng)得分的干擾項進行了多次實驗。在表6～8中展示了從Geography本體中生成的三種不同難度等級的例題，展示了選擇題的難度得分以及干擾項的難度得分（Dscore）。如表6～8所示，根據(jù)對應(yīng)的問題難度等級，可以準確地選擇適當難度得分的干擾項，良好地控制問題的整體難度。

在表6中，設(shè)置選擇題的難度為medium，選擇三個難度得分為0.50的干擾項，使得問題的整體難度值為0.50，該問題的質(zhì)量中等，難易程度中等。在表7中，設(shè)置選擇題的難度為low，選擇難度得分為0.00的三個干擾項，使得問題的整體難度為0.00，該問題質(zhì)量較低，易于回答。在表8中，設(shè)置選擇題的難度為high，分別選擇難度得分為0.85、0.70、0.50三個干擾項，使得問題的整體難度為0.65，該問題的質(zhì)量較高，較為難以回答。

表6 Choose a geopolitical dependency，a member of exactly one sovereign state（Difficulty：0.50）

表7 Choose a nation（Difficulty：0.00）

表8 Choose the largest city in the United States（Difficulty：0.65）

5 結(jié)語

針對現(xiàn)有基于本體的選擇題自動方法中存在的問題，本文提出了一種生成高質(zhì)量選擇題的優(yōu)化方法。在控制問題數(shù)量以及問題質(zhì)量方面，提出了一種基于NUMVC的相似性問題篩選算法。算法將問題篩選轉(zhuǎn)化為對應(yīng)無向圖的最小頂點覆蓋問題，并將元組之間的相似性得分作為權(quán)重，加入頂點刪除策略，使得最小頂點覆蓋集的結(jié)果更加準確。在問題難度控制方面，提出了一種通過干擾項難度控制問題難度的方法。算法通過計算正確選項與干擾項的相似性，選擇對應(yīng)難度的干擾項，控制問題的整體難度，以生成高質(zhì)量且所需難度等級的選擇題，實驗結(jié)果表明，基于NUMVC的相似性篩選算法與干擾項難度控制算法能夠在一定程度上提高自動生成選擇題的質(zhì)量。