曹歆雨+曹衛(wèi)權(quán)+李崢+孫金德

摘 要： 大學(xué)生在課程規(guī)劃方面有很高的自由度，這使得成績數(shù)據(jù)較不規(guī)整，研究者很難對學(xué)生的前序課程成績進(jìn)行有效分析、利用。已有的成績預(yù)測方法普遍未考慮學(xué)生前序課程成績殘缺的現(xiàn)象，從而導(dǎo)致預(yù)測準(zhǔn)確性不佳。提出一種基于K近鄰局部最優(yōu)重建的殘缺數(shù)據(jù)插補(bǔ)方法，該方法能夠有效抑制前序課程成績?nèi)笔︻A(yù)測模型精度的影響。實(shí)驗(yàn)表明，該方法的補(bǔ)全效果優(yōu)于已有的均值插補(bǔ)、GMM插補(bǔ)等方法，結(jié)合隨機(jī)森林模型實(shí)現(xiàn)了有效的成績預(yù)測，為學(xué)生成績管理、就業(yè)能力預(yù)警提供了客觀的參考。

關(guān)鍵詞： 成績預(yù)測； 缺失數(shù)據(jù)； 數(shù)據(jù)插補(bǔ)； 數(shù)據(jù)挖掘； 機(jī)器學(xué)習(xí)； 隨機(jī)森林模型

中圖分類號： TN911?34； TP391 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2018）06?0145?05

Abstract： College students have high freedom on their course planning， which makes the score data irregular and in disorder， and makes it difficult for researchers to effectively analyze and utilize students′ scores of foreword curriculums. The score missing phenomenon of students′ foreword curriculums is generally not considered in the existing score prediction methods， resulting in relatively low prediction accuracy. Therefore， a missing data imputation method based on local optimal reconstruction of k?nearest neighbors is proposed， which could effectively suppress the influence of foreword curriculum score missing on the accuracy of prediction model. The experimental results show that the completion effect of the proposed method outperforms that of the existing mean imputation method， GMM imputation method， and other methods. Effective score prediction is realized by combining with random forest model to provide an objective reference for students′ score management and early warning on students′ employability.

Keywords： score prediction； missing data； data imputation； data mining； machine learning； random forest model

0 引 言

高等教育問題是多年以來的社會熱點(diǎn)，從“精英教育”到“大眾教育”，高校擴(kuò)大招生規(guī)模，面臨著學(xué)生質(zhì)量參差不齊，就業(yè)形勢嚴(yán)峻等問題。如何準(zhǔn)確評估大學(xué)生的學(xué)業(yè)完成質(zhì)量，并進(jìn)一步實(shí)現(xiàn)學(xué)業(yè)退步預(yù)警、就業(yè)質(zhì)量預(yù)測等應(yīng)用，逐漸受到數(shù)據(jù)分析研究者的關(guān)注[1?4]。學(xué)生成績不僅是評估高校教學(xué)質(zhì)量的重要指標(biāo)，還與學(xué)生管理及就業(yè)指導(dǎo)密切相關(guān)。有效預(yù)測學(xué)生成績并及時(shí)進(jìn)行干預(yù)，可以為學(xué)生學(xué)習(xí)思想動態(tài)的引導(dǎo)和就業(yè)能力的評估提供重要的依據(jù)。

權(quán)小娟等基于985高校大學(xué)生的成績數(shù)據(jù)，分析了大學(xué)生成績的變化趨勢及城鄉(xiāng)差異[1]，分析結(jié)果具有一定的現(xiàn)實(shí)參考價(jià)值。但該文獻(xiàn)屬于描述性研究，僅分析了大學(xué)生群體成績發(fā)展規(guī)律，但并未給出有效的成績預(yù)測模型，故無法應(yīng)用于大學(xué)生個(gè)體的成績預(yù)測、預(yù)警。

龍鈞宇等人提出基于頻繁模式發(fā)掘大學(xué)科目之間的強(qiáng)關(guān)聯(lián)關(guān)系，并預(yù)測學(xué)生未來若干課程的成績[2]。該方法有兩方面的局限性：首先，強(qiáng)模式關(guān)聯(lián)方法決定了一門課程的成績僅由當(dāng)前的少數(shù)幾門成績甚至一門成績確定，限制了其預(yù)測準(zhǔn)確率的提升空間；其次，該預(yù)測方法將成績分為4個(gè)等級，無法對成績進(jìn)行精準(zhǔn)、量化預(yù)測。

陳勇將遺傳神經(jīng)網(wǎng)絡(luò)應(yīng)用于大學(xué)生成績分析[3]，實(shí)現(xiàn)了精確的分值預(yù)測，并引入遺傳算法來解決BP神經(jīng)網(wǎng)絡(luò)收斂速度慢、訓(xùn)練時(shí)間長的問題。然而該方法的實(shí)驗(yàn)并不完備，僅在16條成績數(shù)據(jù)上開展神經(jīng)網(wǎng)絡(luò)訓(xùn)練與預(yù)測，實(shí)驗(yàn)結(jié)果不具統(tǒng)計(jì)可信性，也沒有足夠豐富的實(shí)證分析來佐證其模型方法的推廣能力。

已有的相關(guān)研究重點(diǎn)集中在學(xué)生群體成績預(yù)測、個(gè)體成績基本趨勢分析等方面，面向?qū)W生個(gè)體成績的精確預(yù)測研究相對較少。學(xué)生先后所學(xué)課程間存在潛在關(guān)聯(lián)性[2]，但隨著高校教育寬口徑、多樣化理念的深入，學(xué)生的學(xué)習(xí)課程種類繁多且存在較大自主選擇空間，專業(yè)課選修等進(jìn)一步加大了學(xué)生所修課程的不確定性，很難保證同一專業(yè)所有學(xué)生均選修特定課程。此外，學(xué)生調(diào)整專業(yè)、缺考緩考等行為導(dǎo)致前序課程數(shù)據(jù)的缺失，給基于機(jī)器學(xué)習(xí)的成績預(yù)測方法帶來了極大的挑戰(zhàn)。已有研究工作中往往沒有考慮這一因素[3]。當(dāng)學(xué)生并未取得預(yù)測系統(tǒng)所關(guān)心的強(qiáng)關(guān)聯(lián)性課程成績時(shí)，將這種情況稱為數(shù)據(jù)殘缺。如何在學(xué)生成績數(shù)據(jù)存在不確定性殘缺的情況下，仍能基于已有的部分科目成績，推測其未來學(xué)業(yè)走勢，是本文的主要研究內(nèi)容。endprint

針對隨機(jī)殘缺數(shù)據(jù)，根據(jù)模型的精細(xì)程度，存在均值插補(bǔ)（Mean Imputation Method，MEI）[5]、GMM插補(bǔ)[6]、CMeans插補(bǔ)[7]等方法。本文提出一種基于KNN局部最優(yōu)重建的插補(bǔ)方法，并對比了不同插補(bǔ)方法對成績預(yù)測問題的增益，實(shí)驗(yàn)表明，該方法相比于已有插補(bǔ)方法更優(yōu)，能夠有效解決大學(xué)生自由選課情況下的成績預(yù)測問題。

1 數(shù)據(jù)預(yù)處理與問題分析

1.1 學(xué)生專業(yè)與主修課程

本文以四川師范大學(xué)2009—2012級共4屆本科生的全部成績數(shù)據(jù)為基礎(chǔ)，分析問題并驗(yàn)證所提出方法的有效性?；趯W(xué)生選課情況，按照選課人數(shù)比率，統(tǒng)計(jì)出各專業(yè)在每一學(xué)期的熱門課程，如表1所示。

在本文后續(xù)分析中，出于訓(xùn)練效率和“過學(xué)習(xí)”問題的考慮，針對任一學(xué)生，將只考慮其所在專業(yè)、對應(yīng)學(xué)期的熱門課程成績，而不考慮其他冷門課程的成績。

1.2 分學(xué)期成績預(yù)測及其可靠性

針對任一熱門課程[c]及其所在學(xué)期[pc]、專業(yè)[mc]，預(yù)測該課程成績的輸入特征變量包括如下課程集合對應(yīng)的成績：

[Ic=c′pc′

根據(jù)已有成績數(shù)據(jù)和式（1）所示的預(yù)測規(guī)則，構(gòu)建了大量的回歸型（以區(qū)別于分類型）機(jī)器學(xué)習(xí)任務(wù)[T] ，每項(xiàng)學(xué)習(xí)任務(wù)的目標(biāo)變量[y] 即學(xué)生在各學(xué)期熱門課程[c] 的成績[sc]，輸入變量[xn×1]為該學(xué)生在課程集合[Ic]中取得的成績。對于某學(xué)生未選修課程[c′∈Ic]的情況，則設(shè)置對應(yīng)的字段[sc′]為缺失項(xiàng)。

基于隨機(jī)森林算法[8]，對上述各學(xué)習(xí)任務(wù)進(jìn)行訓(xùn)練、預(yù)測，得出各機(jī)器學(xué)習(xí)任務(wù)的均方根誤差（Root Mean Squre Error，RMSE）。對所有RMSE估計(jì)一維概率密度[9]，得出RMSE的分布。

考慮到不同課程成績的分散程度不同，需采用式（2）計(jì)算各課程成績預(yù)測結(jié)果的相對均方根誤差，該數(shù)值越小表明預(yù)測效果越好。

[RRMSET=RMSETVarsc] （2）

定義1 根據(jù)[RRMSE] 指標(biāo)對所有的課程成績預(yù)測任務(wù)進(jìn)行排序，選出[RRMSE] 最小的部分課程集合[Cr]，稱為可預(yù)測課程。

基于學(xué)生已有的成績數(shù)據(jù)來預(yù)測[c∈Cr] 是有意義的；反之，預(yù)測[c′?Cr] 的誤差較大，不具參考價(jià)值。

1.3 數(shù)據(jù)殘缺問題

第1.2節(jié)測試得出的部分可預(yù)測課程及其數(shù)據(jù)缺失情況如表2所示。其中，對于可預(yù)測課程[c]，若其前序熱門課程[Ic]至少有一項(xiàng)無成績，則記錄該樣本為殘缺樣本。

由于其前序課程[Ic] 數(shù)量較多，因此對成績預(yù)測系統(tǒng)而言，數(shù)據(jù)缺失是普遍存在的現(xiàn)象，且數(shù)據(jù)集的殘缺情況相當(dāng)嚴(yán)重，缺失率普遍高達(dá)40%～50%。

2 數(shù)據(jù)插補(bǔ)與成績預(yù)測

K近鄰法（KNN）是一種更有效數(shù)據(jù)插補(bǔ)方法[10]：該方法對于殘缺樣本[xi]，基于其已知的部分分量[Ac]尋找[xi]在完整樣本集[Xc]中的KNN，然后利用k個(gè)近鄰點(diǎn)的均值或眾數(shù)來填充[xi]的未知字段[Am]。

2.1 KNN插補(bǔ)誤差分析

首先考慮[xi]僅包含一維未知分量[xji]的情況。假定可以尋找到[xji]的K近鄰（實(shí)際上[xji]在未知的情況下是無法搜索K近鄰的），基于k個(gè)近鄰點(diǎn)的均值來插補(bǔ)[xji]。設(shè)[xj?U0，1]，考慮完整樣本集[Xc] 的元素獨(dú)立同分布，則其第[m]個(gè)近鄰點(diǎn)與[xji]差值[zm=xjm-xji]的概率密度函數(shù)為：

[gmz=1Bm，N-m+1?1-Fz+F-zm-1? Fz-F-zN-mfz] （3）

式中：[F?]，[f?] 分別為隨機(jī)變量[xj-xji] 的概率分布函數(shù)和概率密度函數(shù)；[B?] 為Beta函數(shù)，如下：

[Bα，β=ΓαΓβΓα+β=α-1！β-1！α+β-1！] （4）

根據(jù)[gmz]可以求得利用KNN估計(jì)[xji]的均值偏移[Ezxji；k]以及方差[Varzxji；k]，進(jìn)而利用式（5）、式（6）得出KNN插補(bǔ)的總體均偏與方差。一般地，[k] 越小則[Varz；k]越小，插補(bǔ)效果越好。

[Ez；k=EEzxji；k] （5）

[Ez2；k=EEz2xji；k] （6）

通過蒙特卡洛法[11]仿真不同分布函數(shù)下KNN插補(bǔ)殘差，如圖1所示。

注意到，在[xj]服從不同概率分布時(shí)，KNN插補(bǔ)殘差隨著k值的增加總是呈現(xiàn)先降低后升高的趨勢。在k較小時(shí)，模型誤差[ε]主導(dǎo)插補(bǔ)殘差；在k較大時(shí)，則由較遠(yuǎn)的[zk，zk-1，…] 主導(dǎo)殘差。KNN插補(bǔ)方法[10]簡單地指定恒定的參數(shù)k，而未討論如何選擇最優(yōu)的k值使得插補(bǔ)殘差最小。

2.2 基于KNN局部線性重建的插補(bǔ)方法

針對待插補(bǔ)樣本[xi]，假設(shè)已經(jīng)基于其已知分量[Ac] 獲取了k個(gè)近鄰點(diǎn)，并將這些近鄰點(diǎn)按列拼接為矩陣[Pd×k]，其中[d]為已知分量的維數(shù)。為了解決最優(yōu)k值未知的問題，借鑒Kang等的最優(yōu)重建思想[10]，通過求解式（7）所示的凸優(yōu)化問題，賦予各近鄰點(diǎn)最優(yōu)權(quán)重[wk×1]。

[minwfw=12Pw-xAci2s.t. w0， w=1] （7）

上述優(yōu)化問題可以利用序列最小優(yōu)化（Sequential Minimal Optimization，SMO）實(shí)現(xiàn)快速求解。設(shè)優(yōu)化問題的對偶變量為[αk×1]和[β1×1]，分別對應(yīng)不等式約束和等式約束，則該問題對應(yīng)的Lagrange函數(shù)為：

[Lw，α，β=12Pw-xAci2-αTw-β1Tws.t. α0] （8）

對應(yīng)的KKT條件為：

[?L?w=PTPw-PTx-α-1?β=0] （9）

[1Tw=0] （10）

[αiwi=0， i=1，2，…，k] （11）

采用數(shù)值解法，求得滿足式（9）～式（11）所定義KKT條件的解即為式（7）的最優(yōu)解。

圖1 插補(bǔ)誤差與近鄰點(diǎn)數(shù)量的關(guān)系

Fig. 1 Relationship between imputation errors and

numbers of neighbor points

在本小節(jié)描述的算法中，對任意變量[v]，[vm]表示該變量第[m]輪迭代的取值，[vi]表示向量的第[i]個(gè)元素，[vi→]，[vi↓]分別表示矩陣的第[i]個(gè)行、列向量。

利用SMO算法的思想，一次迭代僅優(yōu)化[w]的兩維分量，同時(shí)結(jié)合式（9）～式（11）的KKT條件，設(shè)計(jì)最優(yōu)權(quán)重的快速求解算法，具體步驟如下。

1） 查詢?nèi)我黄茐氖剑?）～式（11）KKT條件的分量[wi]，并隨機(jī)選取另一分量[wj]，若未找到[wi]則優(yōu)化終止；

2） 限制[wm+1i+wm+1j=wmi+wmj=C]，限制其他[wm+1l≠i，j]保持不變；

3） 采用解析法優(yōu)化函數(shù)[fwm+1i]；

4） 將最優(yōu)解[wm+1i]限制在區(qū)間[0， C]；

5） 更新[w]，[β]，[α]等，進(jìn)入下一輪迭代。

為了保證上述算法可復(fù)現(xiàn)，需要分別在步驟1）明確如何確定破壞KKT條件的[wi]，在步驟3）明確如何優(yōu)化函數(shù)[fwm+1i]，在步驟5）明確如何更新[β]與[α]。

在定義的KKT條件中，式（9）通過步驟5）強(qiáng)制滿足，式（10）通過步驟2）強(qiáng)制滿足，因此在步驟1）中，可以通過僅檢查[αiwi>ε]來確定[wi]。其中[ε]為極小量，如[10-6]，使得算法穩(wěn)定。

當(dāng)按照步驟2）約束[wj]及其他分量時(shí)，目標(biāo)函數(shù)簡化為式（12）定義的一維二次函數(shù)，式中的[?]為常向量，在每次迭代時(shí)更新。

[2fw=l=1kPl↓wl-xAci2=Pi↓-Pj↓wi+?2] （12）

無約束條件下，最小化上述一維函數(shù)，可得步驟3）的最優(yōu)[wi]，如下：

[w*i=-Pi↓-Pj↓-2Pi↓-Pj↓T?] （13）

最后，按照式（9）～式（11）的KKT條件更新[α]和[β]。采用上述解法有兩項(xiàng)顯著優(yōu)點(diǎn)：一是求解速度更快；二是當(dāng)[P]非列滿秩，回避內(nèi)點(diǎn)法的矩陣奇異問題。

2.3 成績預(yù)測流程

結(jié)合本文第2.2節(jié)的數(shù)據(jù)插補(bǔ)方法，提出圖2所示的成績預(yù)測流程。

3 實(shí)證分析

3.1 數(shù)據(jù)準(zhǔn)備與評估準(zhǔn)則

本節(jié)以四川師范大學(xué)2009—2012級共4屆本科生的成績數(shù)據(jù)，驗(yàn)證所提出方法的有效性。參照第1.2節(jié)的做法，根據(jù)學(xué)生專業(yè)、選課情況、非插補(bǔ)條件下成績先驗(yàn)預(yù)測結(jié)果，選出各專業(yè)學(xué)生對應(yīng)的共17項(xiàng)可預(yù)測課程，其中部分可預(yù)測課程已在表2中列出。以待預(yù)測課程為因變量、以該課程對應(yīng)的前序課程為自變量、以課程對應(yīng)專業(yè)全體學(xué)生為樣本集合，最終構(gòu)成多項(xiàng)成績預(yù)測任務(wù)。

針對每項(xiàng)預(yù)測任務(wù)，分別采用MEI插補(bǔ)[5]、GMM插補(bǔ)[6]、CMeans插補(bǔ)[7]、和本文方法對數(shù)據(jù)進(jìn)行補(bǔ)全，并采用多種機(jī)器學(xué)習(xí)方法預(yù)測目標(biāo)課程成績，取各種機(jī)器學(xué)習(xí)方法預(yù)測RMSE的平均值作為數(shù)據(jù)插補(bǔ)方法的性能評估準(zhǔn)則。本節(jié)采用的機(jī)器學(xué)習(xí)方法包括IBK、決策表、線性回歸、M5P、隨機(jī)森林等預(yù)測模型，每種數(shù)據(jù)插補(bǔ)方法和預(yù)測模型分別重復(fù)試驗(yàn)30次，并取均值作為性能度量，以保證實(shí)驗(yàn)結(jié)果的統(tǒng)計(jì)可信性。

3.2 插補(bǔ)效果對比

對比不同插補(bǔ)方法對學(xué)生成績?nèi)笔顩r的插補(bǔ)效果，如圖3所示。其中，缺失率從0%～50%不等。

注意到，若直接舍棄含缺失項(xiàng)的樣本，隨著缺失率的增加，RMSE指標(biāo)呈線性增長。對比不同的數(shù)據(jù)插補(bǔ)策略，本文提出的KNN插補(bǔ)方法能夠在多項(xiàng)成績預(yù)測任務(wù)中取得最佳的補(bǔ)全效果，較好地解決了學(xué)生成績數(shù)據(jù)中普遍存在的不確定殘缺問題。

3.3 機(jī)器學(xué)習(xí)算法對比

基于第3.1節(jié)的實(shí)驗(yàn)設(shè)置，對比不同預(yù)測模型的預(yù)測精度，結(jié)果如圖4所示，其中所有預(yù)測模型默認(rèn)采用本文KNN插補(bǔ)方法對成績數(shù)據(jù)進(jìn)行了補(bǔ)全。

對比圖4發(fā)現(xiàn)，隨機(jī)森林模型相比于其他預(yù)測模型精度更高。同時(shí)，得益于精準(zhǔn)的數(shù)據(jù)插補(bǔ)方法，隨機(jī)森林模型的預(yù)測誤差隨缺失率增長緩慢，結(jié)合兩種方法預(yù)測學(xué)生成績是一種可行的技術(shù)思路。

4 結(jié) 語

本文針對高校學(xué)生成績預(yù)測預(yù)警問題，分析了不同課程間的關(guān)聯(lián)強(qiáng)度。由于學(xué)生選課自由度較高，學(xué)生部分前序課程普遍面臨著成績?nèi)笔У默F(xiàn)象。針對這一問題提出了基于KNN局部線性重建的插補(bǔ)方法來補(bǔ)全原始數(shù)據(jù)，該方法解決了KNN參數(shù)選擇的問題，具有較好的穩(wěn)定性。實(shí)驗(yàn)結(jié)果表明，結(jié)合本文的KNN插補(bǔ)策略和隨機(jī)森林模型，能夠?qū)崿F(xiàn)高校學(xué)生未來成績的準(zhǔn)確預(yù)測，為基于數(shù)據(jù)驅(qū)動的現(xiàn)代化學(xué)生管理提供可靠的參考。

參考文獻(xiàn)

[1] 權(quán)小娟，朱曉文.大學(xué)生學(xué)習(xí)成績變化趨勢及其影響因素的實(shí)證研究[J].復(fù)旦教育論壇，2016，14（5）：45?51.

QUAN Xiaojuan， ZHU Xiaowen. The changing trend in college students academic achievement and its influential factors： an empirical analysis [J]. Fudan education forum， 2016， 14（5）： 45?51.

[2] 龍鈞宇.基于壓縮矩陣Apriori算法的高校學(xué)生成績相關(guān)性分析研究[J].現(xiàn)代電子技術(shù)，2014，37（24）：47?51.

LONG Junyu. Research on correlation analysis of college student′s achievements based on Apriori algorithm with compressed matrix [J]. Modern electronics technique， 2014， 37（24）： 47?51.

[3] 陳勇.基于遺傳神經(jīng)網(wǎng)絡(luò)成績預(yù)測的研究與實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù)，2016，39（5）：96?100.

CHEN Yong. Research and implementation of result prediction based on genetic neural network [J]. Modern electronics technique， 2016， 39（5）： 96?100.

[4] 葉苗.大數(shù)據(jù)分析大學(xué)生就業(yè)率估計(jì)模型仿真[J].計(jì)算機(jī)仿真，2016，33（11）：183?186.

YE Miao. Big data analysis of college students′ employment rate estimation model simulation [J]. Computer simulation， 2016， 33（11）： 183?186.

[5] LEE T， CAI L. Alternative multiple imputation inference for mean and covariance structure modeling [J]. Journal of educational & behavioral statistics， 2012， 37（6）： 675?702.

[6] YAN Xiaobo， XIONG Weiqing， HU Liang， et al. Missing value imputation based on Gaussian mixture model for the Internet of Things [J]. Mathematical problems in engineering， 2015（3）： 1?8.

[7] TANG J， ZHANG G， WANG Y， et al. A hybrid approach to integrate fuzzy C?means based imputation method with genetic algorithm for missing traffic volume data estimation [J]. Transportation research part C： emerging technologies， 2015， 51（1）： 29?40.

[8] BREIMAN L. Random forests [J]. Machine learning， 2011， 45（1）： 5?32.

[9] NAGLER T， CZADO C. Evading the curse of dimensionality in multivariate kernel density estimation with simplified vines [J/OL]. [2018?01?27]. https：//arxiv.org/pdf/1503.03305v1.pdf.

[10] KANG P. Locally linear reconstruction based missing value imputation for supervised learning [J]. Neurocomputing， 2013， 118（11）： 65?78.

[11] JANSSEN H. Monte?carlo based uncertainty analysis： sampling efficiency and sampling convergence [J]. Reliability engineering & system safety， 2013， 109（2）： 123?132.

[12] WITTEN I H， FRANK E， HALL M A. Data mining： practical machine learning tools and techniques [M]. Beijing： China Machine Press， 2005.endprint