基于二元模糊匹配的編程題智能評(píng)分方法

冷強(qiáng)奎，劉雨晴，秦玉平

(1.渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院，遼寧 錦州 121000；2.渤海大學(xué) 工學(xué)院，遼寧 錦州 121000)

0 引 言

在高校的工科專業(yè)中，C語言均被列為一門重要的必修基礎(chǔ)課程。由于學(xué)習(xí)人數(shù)眾多，對(duì)學(xué)生程序的人工評(píng)分需要教師付出大量勞動(dòng)，效率低下。并且學(xué)生提交程序后不能即時(shí)得到分?jǐn)?shù)反饋，這也影響學(xué)生期末階段的狀態(tài)。另外，人工評(píng)分還要受到評(píng)卷教師水平、經(jīng)驗(yàn)、個(gè)性甚至道德水準(zhǔn)的影響[1]，因此設(shè)計(jì)一種智能的自動(dòng)評(píng)分方法顯得十分重要。

目前，已經(jīng)存在一些自動(dòng)評(píng)分方法，主要包括三大類[2-3]：動(dòng)態(tài)測(cè)試方法、軟件質(zhì)量度量方法和源程序分析比較方法。動(dòng)態(tài)測(cè)試方法[4-5]是一種黑盒測(cè)試方法，在程序運(yùn)行期間通過構(gòu)造大量數(shù)據(jù)進(jìn)行飽和測(cè)試，并根據(jù)運(yùn)行結(jié)果與期望結(jié)果的差異來進(jìn)行評(píng)分。但這種方法所使用的飽和測(cè)試沒有理論上的保證，它往往更取決于測(cè)試人員的經(jīng)驗(yàn)。軟件質(zhì)量度量方法[6-7]是從靜態(tài)分析角度來進(jìn)行評(píng)分。該方法考慮，如果兩個(gè)程序使用相同的評(píng)分標(biāo)準(zhǔn)，并且得到的分?jǐn)?shù)相似，那么它們可能具有相似的結(jié)構(gòu)、數(shù)據(jù)流及控制流特征。然而，這對(duì)共用評(píng)分標(biāo)準(zhǔn)的制定提出了巨大的挑戰(zhàn)，即該標(biāo)準(zhǔn)既要能夠計(jì)算相似，又要準(zhǔn)確區(qū)分不同。第三類方法是源程序分析比較方法[8-11]，它克服了前兩類方法無法衡量學(xué)生程序與參考答案的接近程度的問題，并且能夠做到對(duì)程序進(jìn)行語句理解，因此具有不錯(cuò)的發(fā)展前景。

對(duì)于學(xué)生程序中的兩種極端情況，即無結(jié)果無源程序(空白卷)和編譯成功結(jié)果正確(滿分卷)，自動(dòng)評(píng)分系統(tǒng)是很容易就能夠判對(duì)的。因?yàn)橹灰獙?duì)編程題目進(jìn)行合理設(shè)置，總能夠得到分步驟的輸出結(jié)果(通常以文件形式寫入外存)，這樣就能夠精確檢測(cè)學(xué)生做題的步驟并防止直接寫外存。而對(duì)于編譯不通過或結(jié)果不正確的情況，評(píng)分過程則要復(fù)雜得多。文中要解決學(xué)生程序不完全正確下的自動(dòng)評(píng)分問題，使用二元模糊匹配模型將學(xué)生程序與參考答案進(jìn)行匹配，并根據(jù)匹配結(jié)果計(jì)算分?jǐn)?shù)。最后通過仿真實(shí)驗(yàn)來對(duì)該匹配模型進(jìn)行評(píng)測(cè)，以檢驗(yàn)其在不同情況下的評(píng)分能力。

1 一元結(jié)構(gòu)匹配

所謂一元結(jié)構(gòu)匹配，即首先要檢測(cè)學(xué)生程序與標(biāo)準(zhǔn)參考答案之間在結(jié)構(gòu)方面的相似程度。答案的結(jié)構(gòu)根據(jù)具體題目會(huì)略有不同，但通常分為主函數(shù)結(jié)構(gòu)與輔助函數(shù)結(jié)構(gòu)。每種結(jié)構(gòu)又包含若干個(gè)小項(xiàng)，具體如圖1所示。

圖1 結(jié)構(gòu)匹配示意圖

在檢測(cè)主函數(shù)的結(jié)構(gòu)時(shí)，重點(diǎn)考查學(xué)生程序中是否存在數(shù)據(jù)輸入、函數(shù)調(diào)用和結(jié)果輸出等三個(gè)方面的內(nèi)容。然后進(jìn)行輔助函數(shù)結(jié)構(gòu)的檢測(cè)，這個(gè)階段的檢測(cè)要比主函數(shù)結(jié)構(gòu)的檢測(cè)復(fù)雜一些，因?yàn)樗坏?xiàng)目是否存在，還要考查各項(xiàng)目的體量(即數(shù)量)問題。比如，既要檢查參數(shù)是否存在，還要檢查參數(shù)的個(gè)數(shù)。同樣的，也要檢查分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)的數(shù)量。

下面以題目“編程將一維整型數(shù)組IntArray逆置”為例，詳細(xì)解釋結(jié)構(gòu)匹配的操作過程。

試題分析：該題目的核心功能是逆置，而操作對(duì)象是一維整型數(shù)組IntArray。由于C語言的特點(diǎn)，當(dāng)參數(shù)為數(shù)組時(shí)，需要再添加輔助參數(shù)—數(shù)組的規(guī)模n，因此能夠確定形式參數(shù)由IntArray和n聯(lián)合組成。在教學(xué)過程中，教師通常要求學(xué)生程序風(fēng)格盡量模塊化，所以在該題目中可以實(shí)現(xiàn)輸入輸出功能的函數(shù)化。

參考答案：教師在給出試題的同時(shí)，也需要提供相應(yīng)的參考答案，并且為了評(píng)分更智能，通常會(huì)給出幾份參考答案。當(dāng)學(xué)生程序與其中的一份參考答案相匹配時(shí)，學(xué)生便會(huì)獲得相應(yīng)的分?jǐn)?shù)。對(duì)于“數(shù)組逆置”這個(gè)題目，可以提供的參考答案如圖2所示。

圖2 參考答案示意圖

學(xué)生程序：學(xué)生根據(jù)自身對(duì)題目的理解進(jìn)行自由程序設(shè)計(jì)。在程序結(jié)構(gòu)上可能會(huì)與參考答案存在一定的差異。例如，部分學(xué)生可能會(huì)認(rèn)為不需要寫輸入輸出函數(shù)，這部分功能在主函數(shù)中完成即可。部分學(xué)生認(rèn)為需要更多的變量聲明，才能表達(dá)清楚程序的功能。另外，學(xué)生還會(huì)存在程序設(shè)計(jì)習(xí)慣的問題，有的同學(xué)喜歡使用for循環(huán)，而另外的同學(xué)則喜歡使用while循環(huán)。因此，在檢測(cè)學(xué)生程序與參考答案之間的結(jié)構(gòu)相似性時(shí)，只需要檢查每種結(jié)構(gòu)是否存在以及體量問題，而對(duì)該結(jié)構(gòu)具體的表達(dá)則不必處理。學(xué)生提供的可能答案如圖3所示。

圖3 學(xué)生程序示意圖

主函數(shù)和輔助函數(shù)檢查完畢后，根據(jù)檢查結(jié)果給出結(jié)構(gòu)匹配的分?jǐn)?shù)。由于該匹配主要關(guān)注學(xué)生程序中是否存在相應(yīng)的結(jié)構(gòu)，而不關(guān)心這些結(jié)構(gòu)的先后順序和精確表達(dá)，因此稱這種匹配是模糊的。從結(jié)構(gòu)匹配的過程可以看出，它的操作很簡(jiǎn)單，只是對(duì)學(xué)生程序的一個(gè)初級(jí)評(píng)判，目的是快速確定學(xué)生程序中是否存在關(guān)鍵的采分點(diǎn)。

2 二元詞語匹配

在一元結(jié)構(gòu)匹配的基礎(chǔ)上，接下來要進(jìn)行關(guān)鍵的二元詞語匹配。它包含變量歸一化、詞頻統(tǒng)計(jì)、生成向量空間模型、相似度計(jì)算等幾個(gè)步驟，如圖4所示。

圖4 詞語匹配示意圖

變量歸一化：由于學(xué)生自定義的變量名與對(duì)應(yīng)試題無實(shí)質(zhì)性關(guān)聯(lián)，因此為了檢測(cè)學(xué)生程序中變量的類型和體量，對(duì)變量名作歸一化處理。具體的處理方法是“類型+序號(hào)”，比如在程序中第一個(gè)出現(xiàn)的雙精度浮點(diǎn)型變量，歸一化后的名稱為“double1”。

詞頻統(tǒng)計(jì)：變量歸一化后，可以對(duì)答案中出現(xiàn)的詞語進(jìn)行詞頻統(tǒng)計(jì)，以決定該詞的權(quán)重。這里的統(tǒng)計(jì)方法使用自然語言處理中的經(jīng)典方法，即詞頻-逆文檔頻率(term frequency - inverse document frequency，TF-IDF)[12-13]。對(duì)于某一特定文件中的詞ti來說，它的TF值計(jì)算公式如下：

(1)

ti的IDF值計(jì)算公式如下：

(2)

其中，|D|為語料庫中的文件總數(shù)，1+|{j:ti∈dj}|為包含詞ti的文件數(shù)目。

最終ti的詞頻可計(jì)算如下：

tf-idfi,j=tfi,j×idfi

(3)

TF-IDF表明詞的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時(shí)會(huì)隨著它在語料庫中出現(xiàn)的頻率成反比下降。目前的語料庫(即試題庫)中文件的數(shù)量為20，每個(gè)文件提供5套參考答案，因此|D|=100。

生成VSM：經(jīng)過詞頻統(tǒng)計(jì)得到詞的權(quán)重后，每個(gè)學(xué)生程序可以得到一個(gè)對(duì)應(yīng)的向量空間模型(vector space model，VSM)[14-15]。模型結(jié)構(gòu)如表1所示，S1～S5是對(duì)應(yīng)題目的參考答案，A為學(xué)生答案。

表1 向量空間模型

(4)

對(duì)于每個(gè)學(xué)生答案，要分別與5套參考答案進(jìn)行相似度匹配，最終的相似度取5次匹配的平均值。與一元結(jié)構(gòu)匹配類似，二元詞語匹配也不關(guān)心具體詞語的先后順序和是否為精確表達(dá)，因此它也是模糊的。

3 智能評(píng)分框架

圖5給出了整個(gè)評(píng)分系統(tǒng)的框架和流程。對(duì)于兩種極端情況，即空白卷和滿分卷，系統(tǒng)直接得出分?jǐn)?shù)。如果介于兩者之間，則需要進(jìn)行二元模糊匹配，進(jìn)行智能評(píng)分。

圖5 評(píng)分系統(tǒng)框架

4 仿真實(shí)驗(yàn)

實(shí)驗(yàn)中所用語料庫包含不同知識(shí)點(diǎn)的編程試題20套，每套試題配置5份參考答案，這樣語料庫規(guī)模為100。為了評(píng)估不同情況下該評(píng)分模型的有效性，從每套試題的參考答案中隨機(jī)抽取1份，然后對(duì)其進(jìn)行6種修改操作(modify operation，MO)，具體修改操作如表2所示。

表2 修改操作的種類

這樣得到了120份的模擬學(xué)生程序，然后使用二元模糊匹配模型對(duì)這些程序進(jìn)行評(píng)分，并將評(píng)分與人工評(píng)分進(jìn)行對(duì)比，最終得到了兩者之間的差值，如表3所示。

表3 智能評(píng)分與人工評(píng)分的差值(按百分計(jì)算)

從實(shí)驗(yàn)結(jié)果中可以看出，當(dāng)修改類型為MO1時(shí)，二元模糊匹配能夠得到與人工評(píng)分相類似的分?jǐn)?shù)。這是因?yàn)樵u(píng)分系統(tǒng)首先對(duì)學(xué)生程序進(jìn)行了歸一化預(yù)處理。當(dāng)修改類型為MO2、MO3、MO4時(shí)，智能評(píng)分與人工評(píng)分的差值也比較小，盡管一些結(jié)構(gòu)已經(jīng)進(jìn)行了替換，但在智能評(píng)分時(shí)，每個(gè)學(xué)生程序會(huì)對(duì)照5份參考答案，也就是說，結(jié)構(gòu)替換后，它可能與其中的某一份答案更加類似，從而提高了它的分?jǐn)?shù)。當(dāng)修改類型為MO5時(shí)，智能評(píng)分與人工評(píng)分則出現(xiàn)了較大的差值。原因在于，如果刪除操作去掉了重要詞語，那么勢(shì)必會(huì)對(duì)結(jié)果產(chǎn)生較大的影響。當(dāng)修改類型為MO6時(shí)，智能評(píng)分也距人工評(píng)分有較大的差距。這是因?yàn)樵黾拥娜哂嗾Z句影響了某些詞的權(quán)重，使得計(jì)算余弦相似時(shí)出現(xiàn)了偏差。

但總體來看，智能評(píng)分能夠?qū)W(xué)生程序進(jìn)行較為智能的檢測(cè)，克服了傳統(tǒng)方法只能評(píng)定有限個(gè)分類類型的缺陷，因此具有一定的現(xiàn)實(shí)意義。

5 結(jié)束語

提出了一種新的編程題自動(dòng)評(píng)分方法，稱為二元模糊匹配模型，其中第一元是結(jié)構(gòu)模糊匹配，第二元是詞語相似匹配。在120份修改測(cè)試集上的實(shí)驗(yàn)表明，該方法具有不錯(cuò)的性能。特別是當(dāng)學(xué)生程序與參考答案基本接近時(shí)，準(zhǔn)確率更高。在大規(guī)模評(píng)分場(chǎng)景中，該方法具有一定的現(xiàn)實(shí)意義。