基于PTA平臺(tái)的編程能力評(píng)估算法

申曉倩，林曉霞，李環(huán)宇，徐燕妮

（山東科技大學(xué)智能裝備學(xué)院，泰安 271000）

0 引言

PTA（programming test assessment）是由浙江大學(xué)主導(dǎo)，杭州百騰教育科技有限公司管理運(yùn)營(yíng)的程序設(shè)計(jì)類(lèi)輔助教學(xué)平臺(tái)［1］。當(dāng)前，PTA平臺(tái)被越來(lái)越多的高校和機(jī)構(gòu)采用，截止目前，該平臺(tái)注冊(cè)用戶近400 萬(wàn)，由1086 所高校共創(chuàng)，9100 多位優(yōu)秀教師建設(shè)，近28 萬(wàn)道高質(zhì)量題目供學(xué)習(xí)、練習(xí)。平臺(tái)覆蓋百余門(mén)課程，支持20萬(wàn)人同時(shí)在線，在平臺(tái)上，教師可以創(chuàng)建自己的班級(jí)、創(chuàng)建自己的題目集、布置作業(yè)等。PTA 平臺(tái)支持多種編程語(yǔ)言，如C、C++、Java等。它提供了豐富的題庫(kù)，包括基礎(chǔ)算法、數(shù)據(jù)結(jié)構(gòu)、網(wǎng)絡(luò)編程、操作系統(tǒng)等方面的題目，以及各種比賽和練習(xí)題目。學(xué)生可以通過(guò)PTA平臺(tái)直接提交代碼，進(jìn)行在線編譯、運(yùn)行和評(píng)測(cè)。PTA 平臺(tái)旨在提供一個(gè)高效、公平、準(zhǔn)確的評(píng)測(cè)環(huán)境，評(píng)測(cè)結(jié)果會(huì)及時(shí)反饋給學(xué)生，幫助練習(xí)者及時(shí)發(fā)現(xiàn)問(wèn)題、糾正錯(cuò)誤，幫助學(xué)生提高編程能力和解決問(wèn)題的能力。

數(shù)據(jù)挖掘技術(shù)是一種利用自動(dòng)或半自動(dòng)的手段挖掘出隱藏在海量數(shù)據(jù)中的對(duì)我們研究有用的信息的技術(shù)。數(shù)據(jù)挖掘技術(shù)包括分類(lèi)、聚類(lèi)、關(guān)聯(lián)規(guī)則、異常檢測(cè)等方法。其中，分類(lèi)是將數(shù)據(jù)分成多個(gè)類(lèi)別的過(guò)程，聚類(lèi)是將數(shù)據(jù)分成多個(gè)相似的組的過(guò)程，關(guān)聯(lián)規(guī)則是尋找數(shù)據(jù)之間的相關(guān)性，異常檢測(cè)是檢測(cè)與預(yù)期結(jié)果不符合的數(shù)據(jù)。

在數(shù)據(jù)挖掘技術(shù)的應(yīng)用中，需要使用到各種算法和工具。這些算法可以用于關(guān)聯(lián)、預(yù)測(cè)等，例如，決策樹(shù)、神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)等算法［2］通常用于分類(lèi)和預(yù)測(cè)；K-means、DBSCAN等是常見(jiàn)的用于聚類(lèi)的算法；可以用于關(guān)聯(lián)規(guī)則挖掘的算法包括Apriori、FP-growth 等算法。同時(shí)，在進(jìn)行數(shù)據(jù)挖掘的過(guò)程中，還需要熟悉經(jīng)常使用到的各種數(shù)據(jù)挖掘工具，如RapidMiner、KNIME等。

本文采用數(shù)據(jù)挖掘的相關(guān)技術(shù)，借助PTA平臺(tái)對(duì)高校學(xué)生的編程能力進(jìn)行評(píng)估。

1 數(shù)據(jù)清洗

從PTA 平臺(tái)采集完數(shù)據(jù)后，需要對(duì)采集到的學(xué)生學(xué)習(xí)記錄數(shù)據(jù)進(jìn)行處理，去除無(wú)效數(shù)據(jù)、異常數(shù)據(jù)，并對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化，使得數(shù)據(jù)可以被后續(xù)的算法所使用。數(shù)據(jù)處理過(guò)程中需要注意數(shù)據(jù)的質(zhì)量和準(zhǔn)確性，以確保數(shù)據(jù)的可靠性和有效性，避免對(duì)后續(xù)的數(shù)據(jù)分析和模型構(gòu)建產(chǎn)生干擾。

（1）處理異常數(shù)據(jù)。主要是對(duì)成績(jī)單數(shù)據(jù)進(jìn)行清洗，對(duì)缺失數(shù)據(jù)進(jìn)行處理，在Navicat 中利用篩選功能處理數(shù)據(jù)，成績(jī)單中“缺考”的學(xué)生記錄直接刪除，對(duì)于試題總分缺失的學(xué)生記錄，用該套試題的學(xué)生得分平均值補(bǔ)充；練習(xí)試題通常分為選擇題、判斷題、函數(shù)題以及編程題，若某一類(lèi)型題目得分?jǐn)?shù)據(jù)缺失，不采取將該條數(shù)據(jù)刪除的方法，而是用該條樣本的其他題型的平均得分進(jìn)行填補(bǔ)，本文使用均值插補(bǔ)法［3］，均值插補(bǔ)的原理是用待插補(bǔ)數(shù)據(jù)集的所有非缺失部分的均值替代每個(gè)缺失值，從而得到完整的數(shù)據(jù)集，避免大量數(shù)據(jù)的損失。

（2）進(jìn)行數(shù)據(jù)規(guī)約［4］。主要是通過(guò)減少特征維數(shù)和數(shù)據(jù)規(guī)模的方式去掉一些不重要的信息，本文刪除了用戶組、姓名等與研究無(wú)關(guān)的變量，留下與編程能力相關(guān)度較高的特征作為評(píng)價(jià)指標(biāo)，分別為耗時(shí)、總分、選擇題得分、判斷題得分、編程題得分和試題難度系數(shù)。

（3）數(shù)據(jù)標(biāo)準(zhǔn)化。是將數(shù)據(jù)進(jìn)行無(wú)綱量化，使處理后的數(shù)據(jù)度量相同，將學(xué)生數(shù)據(jù)轉(zhuǎn)換為統(tǒng)一的標(biāo)準(zhǔn)格式，以方便后續(xù)算法進(jìn)行處理和分析，為了實(shí)現(xiàn)評(píng)估數(shù)據(jù)的集中和便于觀察，對(duì)選擇的數(shù)據(jù)進(jìn)行歸一化處理。本文用minmax 方法［5］歸一化指標(biāo)數(shù)據(jù)，將數(shù)據(jù)的取值范圍規(guī)范到［0，1］，便于處理和計(jì)算，提高指標(biāo)數(shù)據(jù)間的可比性。

2 定義和處理數(shù)據(jù)集

2.1 定義數(shù)據(jù)集

建立基礎(chǔ)知識(shí)掌握情況集，確定基礎(chǔ)知識(shí)掌握程度集，該程度集在面對(duì)不同的學(xué)生對(duì)象時(shí)，可以靈活掌握。本文為方便起見(jiàn)，將程度集分為三個(gè)等級(jí)，不掌握、半掌握和完全掌握，分別用［0，0.2］、［0.2，0.6］和［0.6，1］與這三個(gè)等級(jí)對(duì)應(yīng)，具體見(jiàn)表1。編程實(shí)踐能力評(píng)價(jià)等級(jí)分為強(qiáng)、較強(qiáng)、一般、弱、很弱五個(gè)等級(jí)，由于數(shù)據(jù)經(jīng)過(guò)歸一化處理后評(píng)價(jià)指標(biāo)都介于［0，1］，所以評(píng)價(jià)等級(jí)也在［0，1］，規(guī)定區(qū)間［0.80，1.00］、（0.60，0.80］、（0.40，0.60］、（0.20，0.40］、（0，0.20］分別與上述評(píng)價(jià)等級(jí)一一對(duì)應(yīng)［6］。規(guī)定編程實(shí)踐能力評(píng)語(yǔ)集為V={}強(qiáng),較強(qiáng),一般,弱,很弱，見(jiàn)表2。在定義指標(biāo)集之前，首先確定評(píng)價(jià)指標(biāo)，根據(jù)規(guī)約后得到對(duì)學(xué)生學(xué)習(xí)狀況評(píng)估有較重要影響的指標(biāo)，即選擇題得分、判斷題得分、函數(shù)題得分、編程題得分、總分、耗時(shí)，及試題難度系數(shù)七個(gè)評(píng)價(jià)指標(biāo)。以客觀題得分情況來(lái)表示基礎(chǔ)知識(shí)掌握情況，客觀題有選擇題和判斷題，以函數(shù)題和編程題作為評(píng)估編程實(shí)踐能力的評(píng)價(jià)指標(biāo)。

表1 基礎(chǔ)知識(shí)掌握程度評(píng)價(jià)等級(jí)

表2 編程實(shí)踐能力評(píng)價(jià)等級(jí)

在研究規(guī)定評(píng)價(jià)指標(biāo)集S={S1,S2,S3,S4,S5,S6,S7}其中S1是總分，S2是耗時(shí)，S3表示判斷題得分，S4是選擇題得分，S5是函數(shù)題得分，S6是編程題得分，S7是試題難度系數(shù)。規(guī)定指標(biāo)權(quán)重集為Ws=[W1,W2,W3,W4,W5,W6,W7] 。定義指標(biāo)權(quán)重集后，接下來(lái)就需要計(jì)算指標(biāo)權(quán)重。

2.2 計(jì)算評(píng)價(jià)指標(biāo)權(quán)重

指標(biāo)權(quán)重的計(jì)算采用熵權(quán)法，這是根據(jù)某一指標(biāo)的變異程度進(jìn)行權(quán)重分配的方法。根據(jù)熵值進(jìn)行指標(biāo)權(quán)重計(jì)算時(shí)，如果指標(biāo)的熵值較小，則表明其變異程度大，其權(quán)重也就越大。

2.2.1 求各個(gè)指標(biāo)的信息熵

本文經(jīng)過(guò)數(shù)據(jù)預(yù)處理后，有72個(gè)評(píng)價(jià)對(duì)象，7 個(gè)評(píng)價(jià)指標(biāo)，設(shè)原始評(píng)價(jià)矩陣歸一化后的評(píng)價(jià)指標(biāo)矩陣其中xij表示第i個(gè)對(duì)象的第j個(gè)評(píng)價(jià)指標(biāo)的值，bij是歸一化后無(wú)量綱的第i個(gè)對(duì)象的第j個(gè)評(píng)級(jí)指標(biāo)。根據(jù)信息熵的概念，可得公式（1）和公式（2）。

根據(jù)公式計(jì)算可得pij矩陣，局部矩陣展示如圖1所示。

圖1 局部矩陣示意

通過(guò)公式計(jì)算得到7個(gè)評(píng)價(jià)指標(biāo)的信息熵為H1= 0.876，H2= 0.802，H3= 0.902，H4= 0.898，H5= 0.7591，H6= 0.7107，H7= 0.9034。

2.2.2 計(jì)算各個(gè)指標(biāo)的權(quán)重

根據(jù)以上信息熵的公式，計(jì)算得到7個(gè)指標(biāo)的信息熵值后，采用公式（3）計(jì)算可得到權(quán)重，公式（3）如下：

其中，j= 1,2,3,4,5,6,7并且

通過(guò)計(jì)算得到評(píng)估指標(biāo)權(quán)重的具體值，見(jiàn)表3。

表3 評(píng)估指標(biāo)權(quán)值

3 BP神經(jīng)網(wǎng)絡(luò)模型結(jié)構(gòu)的確立

本文是通過(guò)訓(xùn)練BP 神經(jīng)網(wǎng)絡(luò)模型［7］來(lái)評(píng)估學(xué)生的編程能力，要確定BP 神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)，就需要確定三層的節(jié)點(diǎn)數(shù)。針對(duì)該系統(tǒng)，輸入層有7 個(gè)神經(jīng)元，輸出層有2 個(gè)神經(jīng)元，因此，確定隱含層的節(jié)點(diǎn)個(gè)數(shù)是明確BP 神經(jīng)網(wǎng)絡(luò)模型結(jié)構(gòu)的關(guān)鍵，對(duì)于隱含層節(jié)點(diǎn)個(gè)數(shù)的計(jì)算通常采用經(jīng)驗(yàn)公式（4）：

其中，l表示隱含層節(jié)點(diǎn)個(gè)數(shù)，n為輸入層節(jié)點(diǎn)數(shù)，m為輸出層節(jié)點(diǎn)數(shù)，α為［1，10］之間的常數(shù)。

通過(guò)公式（4）可得該隱含層節(jié)點(diǎn)個(gè)數(shù)取值范圍為［4，14］，采用試湊法對(duì)不同數(shù)量的隱含層神經(jīng)元個(gè)數(shù)進(jìn)行測(cè)試，最終得到最佳隱含層神經(jīng)元個(gè)數(shù)是9。即確定了該神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)為輸入層節(jié)點(diǎn)數(shù)為7，隱含層節(jié)點(diǎn)數(shù)為9，輸出層節(jié)點(diǎn)數(shù)為2，因此，確定7-9-2 型BP 神經(jīng)網(wǎng)絡(luò)。如圖2所示，建立了BP神經(jīng)網(wǎng)絡(luò)模型［8］。

圖2 BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

4 確定隱含層函數(shù)

本文采用tansig 函數(shù)和logsig 函數(shù)分別作隱含層的傳輸函數(shù)和輸出層的轉(zhuǎn)移函數(shù)，如式（5）和（6）所示：

輸入層到隱含層函數(shù)如式（7）和（8）所示：

其中，xi表示輸入層中第i個(gè)神經(jīng)元的輸入，wij表示輸入層中第i個(gè)神經(jīng)元和隱含層第j個(gè)神經(jīng)元之間的連接權(quán)值，netj是指隱含層第j個(gè)神經(jīng)元的輸入，yj表示隱含層第j個(gè)神經(jīng)元的輸出。

隱含層到輸出層函數(shù)如式（9）和（10）所示:

其中，vj表示隱含層第j個(gè)神經(jīng)元與輸出層神經(jīng)元之間的連接權(quán)值，O1是輸出層神經(jīng)元的輸出，net1表示輸出層神經(jīng)元的輸入。

5 BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練

該系統(tǒng)模型訓(xùn)練的流程［9］如下：首先，輸入訓(xùn)練樣本，本文選取了7 套題，共500 條記錄，以400 條編程數(shù)據(jù)為訓(xùn)練樣本，100 條數(shù)據(jù)作為測(cè)試樣本。然后，設(shè)置網(wǎng)絡(luò)參數(shù)，初始最大迭代次數(shù)設(shè)置為40000，目標(biāo)誤差為1e-004，訓(xùn)練樣本數(shù)據(jù)進(jìn)行學(xué)習(xí)，通過(guò)不斷調(diào)整網(wǎng)絡(luò)權(quán)值和閥值，使得評(píng)估模型達(dá)到一個(gè)穩(wěn)定的狀態(tài)，當(dāng)神經(jīng)網(wǎng)絡(luò)達(dá)到目標(biāo)誤差或者達(dá)到最大迭代次數(shù)時(shí)訓(xùn)練可以結(jié)束。

在進(jìn)行模型訓(xùn)練之前，首先要確定綜合評(píng)價(jià)值，通過(guò)公式（11）計(jì)算綜合評(píng)價(jià)值，將其作為期望輸出。

采用絕對(duì)誤差來(lái)測(cè)量神經(jīng)網(wǎng)絡(luò)輸出的真實(shí)值與預(yù)期值之間的偏差，絕對(duì)誤差是真實(shí)值與預(yù)期值之間差的絕對(duì)值，通過(guò)對(duì)比兩者之間的絕對(duì)誤差，編程實(shí)踐能力測(cè)試結(jié)果和評(píng)價(jià)等級(jí)見(jiàn)表4。

表4 BP神經(jīng)網(wǎng)絡(luò)測(cè)試結(jié)果與誤差

由表4 可知，該系統(tǒng)BP 神經(jīng)網(wǎng)絡(luò)的真實(shí)值與預(yù)期值的最大絕對(duì)誤差為0.0072，最小值為0.0000，誤差值十分接近，能夠比較準(zhǔn)確地對(duì)學(xué)生編程能力進(jìn)行評(píng)估。因此，采用基于熵權(quán)的BP 神經(jīng)網(wǎng)絡(luò)模型對(duì)學(xué)生學(xué)習(xí)狀況進(jìn)行評(píng)估是可行的。

6 結(jié)語(yǔ)

本研究采用了BP 神經(jīng)網(wǎng)絡(luò)算法，神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)為7-9-2 型，可以對(duì)學(xué)生的學(xué)習(xí)狀況進(jìn)行分類(lèi)和預(yù)測(cè)，幫助教師和學(xué)生對(duì)學(xué)習(xí)狀況準(zhǔn)確評(píng)估，對(duì)教育信息化發(fā)展具有現(xiàn)實(shí)意義。即學(xué)生總得分、選擇題得分、判斷題得分、函數(shù)題得分、編程題得分被賦予權(quán)重后，可以得到準(zhǔn)確的評(píng)估結(jié)果，這些與學(xué)習(xí)狀況評(píng)估都有關(guān)系。該系統(tǒng)的評(píng)估結(jié)果可以為教師和學(xué)生提供有價(jià)值的參考信息。教師可以根據(jù)該評(píng)估系統(tǒng)準(zhǔn)確了解學(xué)生的學(xué)習(xí)狀況和問(wèn)題，從而有針對(duì)性地為學(xué)生提供建設(shè)性建議，真正起到幫助學(xué)生提高學(xué)習(xí)效果和成績(jī)的作用。當(dāng)然學(xué)生也可以通過(guò)結(jié)果了解自己的編程能力，為下一步深入學(xué)習(xí)做好計(jì)劃。