基于熵權-離差的GA-BP神經網絡編程能力評估方法

羅文劼， 李明杰， 肖梓良

(河北大學網絡空間安全與計算機學院，保定 071002)

教育數據挖掘(educational data mining，EDM)是運用教育學、計算機科學、心理學和統計學等多個學科理論和技術來解決教育研究與教學實踐中問題的一種方法[1]。隨著在線學習平臺的不斷發展，EDM已成為當前解決教育數據研究的熱點。EDM對教育相關數據進行分析與研究，主要應用有發現學習規律、分析學習特征及習慣、評估學習現狀、可視化、學習者建模、學習者表現預測、推薦系統和自適應系統等[1-2]。將教育系統積累的大量學習數據通過數據挖掘技術得到的客觀信息反饋，有利于學習者掌握自己的學習情況，同時，有助于教育者的教學管理。

在線評測系統(online judge，OJ)是對用戶提交的算法源代碼進行評測而設計的在線自動判題系統[3]。隨著ACM(國際計算機協會)國際大學程序設計競賽(ACM/ICPC)等程序設計競賽的普及，OJ系統也得到了快速的發展，為編程實戰提供了一種新的方式[4]。近些年來，中外很多高校擁有自己的OJ系統，如北京大學的POJ、浙江大學的ZOJ、古巴信息科學大學的COJ和俄國薩拉托夫國立大學的CodeForce等，OJ作為學習者編程訓練的平臺，對提高學習者的編程能力具有很重要的作用。

目前，中外已經有部分研究者使用數據挖掘技術對學習者的編程數據進行挖掘，從而預測學習者的成績和評估其編程能力水平。在國外的研究中，Watson等[5]基于分析編程學習過程中直接記錄的數據，介紹了一種Watwin的動態加權算法，通過對不同的特征進行加權來預測程序設計中的學生的成績；Sagar等[6]提出監督學習的方法來預測學習者的編程能力，揭示學習者編程學習的潛在趨勢，不僅可以幫助學習者實現自我認識，還可以幫助教育工作者評估學習者的學習進度；Carter等[7]通過學習分析編程狀態，根據編程過程中的編譯、調試以及編碼過程和測試特征構建統計模型，發現不同編程能力水平的學習者之間差異。在中國的研究中，石振強[8]分析了在線評測系統與學習者之間的交互方式，采用k-means聚類算法分析學習者的行為，建立學習者成績預測模型；張永梅等[9]采用模糊神經網絡設計實現程序設計能力的評價方法，王明艷[10]建立基于反向傳播(back propagation, BP)神經網絡的大學生編程能力動態評估模型，用模糊層次分析法確定各評估指標的權重，但是此方法具有主觀性和單一性，而且模糊邏輯與BP神經網絡的結合并沒有解決BP神經網絡求指標權重時容易陷入局部極小化的問題。

通過分析以上中外有關編程能力研究成果，針對OJ系統上缺乏對學習者編程能力的客觀反饋和只憑借最終成績評價學習者的方法單一化的問題，提出基于熵權法和離差最大化方法的遺傳算法優化BP(genetic algorithm-back propagation, GA-BP)神經網絡的編程能力評估方法，以 EDM 為基礎，采集并分析該系統上記錄學習者的歷史學習數據，提取學習者完成編程題目的正確數量、重復提交次數、程序評測結果[11]、程序調試時間[12]和成績5個指標來反映一個學習者的編程能力水平，用雙參數平衡熵權法和離差最大化的客觀組合賦權方法克服文獻[9-10]在評估學習者編程能力利用模糊層次分析法確定指標權重的主觀性和賦權方法單一化的問題，同時，利用GA隨機搜索最優解的優勢來避免BP神經網絡確定指標權重易陷入局部極小化的問題，構建GA-BP神經網絡評估模型，實現對學習者編程能力的客觀評估。

1 編程能力評估指標體系

1.1 概念的符號定義

(1)將學習者定義為u，編程題目定義為p。學習者集合為U={u1,u2,…,um}，編程題目集合為P={p1,p2,…,pn}，其中，m表示學習者的數量，n表示編程題目的數量。

(2)將學習者學習信息定義為S。設學習者u在題目p上的學習記錄由Sp(u)=[Su,p,0,Su,p,1,…,Su,p,l-1]T∈Rl表示，其中，所有學習者的學習信息都被存儲在SU×P×l中，可通過提取S中的特征形成評估學習者編程能力的指標體系I，I={X1,X2,…,Xq}，其中q為評估指標的個數。

(3)將學習者編程能力定義為B。設B={value}U×P表示所有學習者的編程能力評估值。其中，value描述通過計算S中所記錄學習者u在不同編程題目p上的各指標數據所得的綜合評估值。

1.2 評估指標的描述

OJ系統編程實戰數據量大，每個學習者在線編程學習的記錄S都形成記錄其隱性學習效果的載體，對學習者的歷史學習信息進行系統分析，并參考文獻[8，11-12]有關在線評測系統編程數據的研究，提取編程能力評估指標，首先對各指標進行描述，具體如下：

(1)調試題目時間Tdebug。將學習者u提交編程題目p的開始時間定義為Tstart，將最后一次修改結束后提交時間定義為Tend。

(1)

j=1,2,…,n

(2)正確提交數NAC。OJ的基本測試結果包括編譯錯誤(CE)[11]、運行錯誤(RTE)[11]、答案錯誤(WA)[11]、系統錯誤(SE)[11]、運行超時(TLE)[11]、運行超內存(MLE)[11]和評測成功(AC)[11]7種，評測結果result={CE,RTE,WA,SE,TLE,MLE,AC}，設

(2)

每個學習者的正確提交數NAC為

(3)

(3)錯誤類型數Nf-type。當η?result且AC?η時，

(4)

式(4)中: num(η)為η中元素的個數。

(4)重復提交次數rsubmit。設λ表示完成題目所提交的次數，則

(5)

(5)總成績Ts。設s表示學習者u完成題目pj的成績，則Ts為

(6)

由以上各指標組成的評估學習者編程能力指標體系I={X1,X2,X3,X4,X5}，然而各指標權重未知，需確定每個評估指標的權重。確定指標權重的方法有主觀賦權法、客觀賦權法和組合賦權法。主觀賦權法有Delphi法和層次分析法等，但是其具有主觀性，易受到人的知識結構和經驗能力的影響。客觀賦權法是對信息進行客觀的處理，主要有主成分分析法和熵權法等，但其計算結果難以解釋，而且單一的賦權法又具有一定的片面性。因此，提出熵權法和離差最大化的客觀組合賦權法，熵權法強調信息數據本身的重要程度，忽視了數據之間的聯系，而離差最大化方法只注重信息數據之間的關系，恰恰能夠彌補單一熵權法的這一不足，綜合考慮信息本身和信息之間的關系來確定各指標的權重，并引入雙參數來平衡二者之間的關系。

BP神經網絡具有自學能力、客觀性、非線性映射和求解率高的優點[13]，在綜合評價領域得到了廣泛的應用。但是BP神經網絡求權重容易形成局部極小化，GA具有全局搜索能力，能夠解決這一問題。所以，構建基于熵權法和離差最大化方法的GA-BP神經網絡編程能力評估模型，流程如圖1所示。

圖1 熵權-離差的GA-BP神經網絡流程

2 熵權-離差的GA-BP神經網絡評估模型

2.1 熵權法-離差最大化原理

熵權法(entropy weight method, EWM)是利用熵值來評估各指標的變異程度、確定指標的權重和度量數據所提供信息量大小的方法[14]。熵值越小，其所包含的不確定性越小，說明指標傳遞的有效信息量大，指標所占的權重越大，該指標在評估中的影響就越大；反之，指標的熵值越大，其所包含的不確定性越大，則該指標在評估中產生的影響就越小。

離差最大化方法(maximizing deviation method, MDM)是利用評估指標值的離散程度大小確定相應指標的權重[15]。對于指標的值之間若是有較大的差異，則說明該指標對最終的評估結果影響大，應該賦予該指標較大的權重；反之，對于指標的值之間若是有較小的差異，則賦予該指標較小的權重。

由于每個指標存在不同的量綱，在對評估指標的權重進行計算時，量綱的存在會影響各指標之間的比較，也不利于模型構建。所以，需要對指標進行無量綱的標準化處理，實現數據的大小能夠很直觀地表現被評估對象的優劣情況。評估的指標分為效益型指標和成本型指標，對應效益型指標的值越大越好，成本型指標的值則越小越好。

設原始評估矩陣R=(xij)m×q，對R標準化處理后得到矩陣R′=(bij)m×q。

對于效益型指標而言，有

(7)

對于成本性指標而言，有

(8)

式中:xij為第i個評估對象的第j個指標的值；bij表示歸一化后無量綱的標準數據。

熵權法-離差最大法求各指標的權重以及確定評估結果的過程如下。

2.1.1 構建評估矩陣

設有m個評估對象，q個評估指標，評估指標的綜合權重為w′=(w′1,w′2,…,w′q)。

(9)

2.1.2 熵權法確定各指標的權重

(1)對于各指標僅考慮信息本身的重要性，即從熵權法角度出發，根據熵的定義，確定各評估指標的熵值。

(10)

(11)

式中:j=1,2,…,q；0≤Hj≤1。

(2)指標Ij的信息熵為Hj，熵權法求得各指標權重為wj，具體計算公式為

(12)

2.1.3 離差最大化法求各指標權重

離差最大化方法只注重信息間的關系而忽略信息本身的關系。在滿足歸一化和權重約束原則的條件下，計算其權重，目標函數計算如(13)所示。

(13)

式(13)中：dev(bij,bkj)表示對于bj指標，評估對象bi和其他評估對象的離差；bij、bkj分別為第i個和第k個評估對象的第j個指標值；ωj為第j個評估指標的權重。

指標權重的選擇根據所有的評估對象的所有評估指標的總離差最大化的原則，建立如下線性規劃模型T：

(14)

利用拉格朗日函數求解T:

(15)

分別對ωj和ξ求偏導，最后得到模型最優解ω*。

(16)

歸一化處理后得ωj，即

(17)

2.1.4 綜合熵權法求得的指標權重w和離差最大化求得的指標權重ω，引入雙參數確定指標的綜合權重

首先，以歐氏距離確定二者間的距離，即

(18)

用雙參數表示修正后的實際權重w′,即

w′j=αwj+βωj

(19)

式(19)中:α和β分別表示熵權法和離差最大化方法權重偏好系數，且滿足以下約束條件：

d2(wj,ωj)=(α-β)2

(20)

α+β=1

(21)

式中:α≥0；β≥0。

2.1.5 確定綜合評估結果

學習者樣本的綜合評估值B為w′與R′的合成運算,即

(22)

2.2 GA-BP神經網絡

BP神經網絡是廣泛應用的神經網絡模型之一，該網絡的結構具有輸入層、隱藏層和輸出層。BP神經網絡的學習過程由正向傳播通過輸入層神經元把輸入網絡的信息經過隱藏層的計算傳向輸出層，而且每一層的神經元只對下一層的神經元的輸出狀態有影響[13]，若實際輸出值與期望值不符，則進行反向傳播，計算輸出誤差，將誤差信號從輸出層再傳向輸入層，此過程不斷修改連接每層神經元的權值和閾值，直至結果能夠實現網絡的預期效果，其結構如圖2所示。圖2中，X表示評估指標，Y表示輸出層神經元的輸出值，wij和wjk分別為連接輸入層到隱含層與隱含層到輸出層之間的權值。

BP算法雖然能夠擬合非線性關系和提高復雜問題求解精度，且對數據資料沒有嚴格的要求，但是網絡易陷入局部極小化，隨機賦予的權值和閾值也會使得網絡的收斂速度減慢。BP神經網絡存在的這些不足會對其應用造成一定的影響。

GA是一種全局優化隨機搜索算法，通過遺傳算子來模擬生物遺傳過程中的選擇、交叉和變異過程，從而獲得最優個體[13]。GA計算過程簡單，而且不依賴于問題本身，利用GA優化BP初始網絡的權值和閾值，收斂速度快，增強評估模型的準確性。

圖2 BP神經網絡結構

3 實驗設計與結果分析

3.1 數據來源

OJ現用于編程能力訓練、程序設計類課程的在線考核與測驗，為了保證數據的真實性和評估的客觀性，采用程序設計類實驗輔助教學平臺上120名學習者的編程實戰測驗數據為驗證實例，通過采集學習者提交編程題目的數據和評測信息，參照編程能力評估指標體系，對各指標值進行提取并進行數據預處理得到歸一化數據，并將前80名學習者樣本數據用于GA-BP神經網絡的訓練，其余樣本用于測試網絡的性能，利用GA-BP神經網絡模型得到各學習者編程能力評估值，并設計相應的能力評估等級，如表1所示。

表1 編程能力評估等級

3.2 構建GA-BP神經網絡模型

3.3 評估結果分析

通過熵權法和離差最大化法計算得出各評估指標的具體客觀權重，熵權法對應指標X1、X2、X3、X4和X5的權重分別為0.161 5、0.208 3、0.362 0、0.079 5和0.188 7，離差最大化法對應各指標權重分別為0.215 5、0.198 8、0.187 3、0.201 5和0.196 9，結合式(20)計算兩種方法綜合指標權重w′為0.182 6、0.204 6、0.293 9、0.127 1、0.191 9。在此基礎上，通過式(22)得到各學習者編程能力評估值，將評估值作為GA-BP神經網絡的期望輸出，用GA-BP神經網絡模型進行訓練，得到最接近期望輸出的評估模型，保存GA-BP神經網絡進行測試，將期望值與實際輸出值進行對比并計算二者之間的絕對誤差。測試結果和評估等級如表2所示。

表2 GA-BP神經網絡測試結果與誤差

由表2可知，GA-BP神經網絡的實際輸出和期望輸出值之間的最大絕對誤差值為0.006 8，最小值為0，誤差值很接近。因此，基于熵權和離差的GA-BP神經網絡模型能夠實現對學習者編程能力的評估。

3.4 模型評估性能對比分析

建立基于熵權和離差的GA-BP神經網絡訓練模型以及數據歸一化處理均采用MATLAB語言實現，并將該模型與單一BP神經網絡評估模型的實驗進行對比，用平均相對誤差(mean relative error,MRE)來評價模型的有效性。MRE的定義為

(23)

式(23)中:yi為期望輸出值；fi為實際輸出值。

通過實驗測試，基于熵權和離差的GA-BP神經網絡模型的MRE為0.34，單一BP神經網絡的MRE為0.69，GA-BP 神經網絡和單一BP 神經網絡的相對誤差曲線對比如圖3所示。

圖3 GA-BP與BP神經網絡相對誤差比較

由圖3可知，基于熵權和離差的GA-BP神經網絡的誤差小，評估結果更準確。

4 結論

(1)構建基于熵權和離差的GA-BP神經網絡編程能力評估模型，提取編程能力評估指標，采用熵權法和離差最大化法的客觀組合賦權法，減少了主觀因素的影響；同時，引入雙參數修正二者的權重以確定各指標的綜合權重，從而計算期望輸出，將其作為GA-BP神經網絡的期望輸出，優化了BP神經網絡求權重帶來的誤差。

(2) GA優化BP神經網絡的初始值和閾值，克服BP神經網絡求權重易陷入局部極小化的缺點，使得網絡的收斂速度加快，增強BP神經網絡的魯棒性，而且，與單一BP神經網絡的評估結果相比較，GA-BP神經網絡的評估誤差小。

(3)用熵權和離差的GA-BP神經網絡模型建立OJ上學習者編程能力評估模型，輸出值和期望值的誤差較小，可以實現對學習者編程能力的評估且評估結果更準確，能夠幫助學習者掌握自身編程能力水平；同時，為輔助高校教育教學管理和企業招聘優質人才提供參考。在今后的工作中將會考慮更多維度的信息在編程能力建模中的應用，并利用編程能力研究結果更準確地進行個性化推薦的研究。