基于語義相似性的選擇題自動生成優化方法

溫雪峰 崔仙姬 張俊星

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

1 引言

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

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

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

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

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

2 基于本體的選擇題自動生成系統框架

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

圖1 選擇題自動生成系統

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

3 選擇題自動生成優化

3.1 選擇題問題篩選

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

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

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

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

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

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

基于NUMVC（A Novel Local Search for Minimum Vertex Cover Problem）的相似性篩選算法將元組之間的相似性得分作為權重，并且加入頂點刪除策略，使得最小頂點覆蓋集的結果更加準確，算法的搜索效率更高。利用基于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的相似性篩選算法的算法時間復雜度包括以下兩個部分：計算頂點的相似性（O(S|V|)），查找圖的最小頂點覆蓋（O(N|V|)），其中S表示式（1），由此可得算法1的時間復雜度為O(S|V|+N|V|)。

表2 相似性篩選后的元組

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

3.2 干擾項難度控制

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

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

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

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

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

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

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

干擾項難度控制算法的算法時間復雜度包括以下兩個方面：計算選項之間的相似性（O(D||d+S|d|)），選擇對應難度的干擾項（O(C|d|))），其中D表示式（2），S表示式（3），由此可得算法2的時間復雜度為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）測試干擾項難度控制算法在干擾項生成中的可行性與有效性。

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

4.1 問題篩選

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

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

表3 樣本本體的屬性與相應的元組計數

表4 屬性篩選后本體的屬性與相應的元組計數

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

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

表5 問題篩選結果及對比結果

4.2 干擾項生成

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

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

表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 結語

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