宗曉萍，陶澤澤

(河北大學 電子信息工程學院，河北 保定 071002)

大數(shù)據(jù)時代的到來，使海量的數(shù)據(jù)資源在各個領域彰顯其優(yōu)勢，驅(qū)動著其運營和管理模式的創(chuàng)新.教育數(shù)據(jù)挖掘(educational data mining,簡稱EDM)是指利用不斷發(fā)展的數(shù)據(jù)挖掘技術和方法，分析、探索特定教育環(huán)境中的各類數(shù)據(jù)，挖掘出有價值的信息，幫助學校和教師更好地了解學生的學習、成長過程，為教育者、學習者、管理者等提供參考與建議[1]，以改善其學習環(huán)境，提高學習效率.近年來，隨著信息技術與教學的深度融合，特別是慕課、翻轉(zhuǎn)課堂、混合式教學等新興教學模式的發(fā)展，使教育數(shù)據(jù)挖掘被越來越多的研究者所關注[2].

學生在線學習行為的分類和預測是目前教育數(shù)據(jù)挖掘及應用所研究的重要內(nèi)容之一[3].眾多的國內(nèi)外學者建立不同的預測模型，通過分析網(wǎng)絡在線學習數(shù)據(jù)，預測其學習效果，并對學習過程進行干預與評估.研究學習預警中常用的經(jīng)典方法包括譜聚類法[4]、貝葉斯網(wǎng)絡理論[5]、過程表現(xiàn)度量法[6]、C4.5算法[7]、多個模型比較法[8]等.Mayilvaganan等[9]通過實驗發(fā)現(xiàn)K-近鄰(K-NN)算法在學習預警中是一個非常有效的方法.K-NN算法原理簡單且容易實現(xiàn)，當面對海量數(shù)據(jù)時，具有明顯的優(yōu)勢.但是該算法存在一些較大的缺點：首先K-近鄰算法的K值和距離度量的方式通常是根據(jù)個人經(jīng)驗來選擇，給分類結果帶來了一定的影響.同時，在計算待測樣本與訓練樣本之間的距離時，所有的特征擁有等效的地位，而在實際應用中，每個特征對分類結果所起的重要程度不同，分為重要特征、次要特征和冗余特征.這樣往往容易導致樣本間的距離會被許多的冗余特征所控制,產(chǎn)生維度災難.因此，特征選擇決定著分類的時間效率及預測結果的準確性.

針對以上問題，本文提出了改進的K-近鄰算法以及在學生預警中的應用.針對傳統(tǒng)K-NN算法存在的問題,首先利用網(wǎng)格搜索和交叉驗證相結合的方法對模型參數(shù)進行優(yōu)選,其次，計算每一個特征的基尼增益來確定特征的重要程度，并且引入縮放因子放大和縮小權重系數(shù),并且根據(jù)權重系數(shù)將特征劃分為重要特征、次要特征和冗余特征,在計算歐氏距離時引入權重系數(shù),使各個特征的作用受其權重系數(shù)的約束.通過實驗對比，改進后的K-近鄰算法(DT-K-NN)比傳統(tǒng)K-NN算法在模型分數(shù)上有了極大的提高.

1 K-近鄰算法

K-近鄰(K-nearest neighbors,K-NN)是一種基本的機器學習算法，其本質(zhì)源于相似理論，相當于一種用于樣本分類的非參數(shù)方法[10].K-NN在分類預測時，一般采用多數(shù)表決法，即依據(jù)距離度量公式計算出離待測樣本最近的K個樣本數(shù)據(jù).通過投票法來得到這K個樣本數(shù)據(jù)的類別，那么該待測樣本被劃分為投票數(shù)量多的那一類別,其中，距離的度量主要有歐氏距離、曼哈頓距離.

1)根據(jù)個人經(jīng)驗給定K的值.

2)計算新數(shù)據(jù)到每個訓練樣本的距離(p=1為曼哈頓距離，p=2為歐氏距離)

.

(1)

對求得的所有距離按照從小到大進行排序，越小代表越相似.

3)在n個距離值中取前K個樣本數(shù)據(jù)對應的分類標簽.

4)統(tǒng)計K個數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類標簽作為新數(shù)據(jù)的分類.

2 K-NN算法的改進

2.1 基于網(wǎng)格搜索和交叉驗證的參數(shù)尋優(yōu)

根據(jù)K-近鄰算法原理可知，超參數(shù)K和距離度量參數(shù)p對模型的預測效果有很大的影響.網(wǎng)格搜索法(grid search,GS)是處理有約束非線性極值問題的一種數(shù)字規(guī)劃法，也可以稱其為枚舉搜索法.它將K與p組成的參數(shù)空間等距劃分為若干網(wǎng)絡，根據(jù)枚舉網(wǎng)絡交叉點處的全部參數(shù)組合，計算出其對應訓練模型的分數(shù)，直到遍歷網(wǎng)格平面的每一個交叉點，找到訓練分數(shù)最大的參數(shù)組合，即為最優(yōu)參數(shù).同時，網(wǎng)格搜索法對2個參數(shù)進行尋優(yōu)時，可以確保搜索解是劃分網(wǎng)格中的全局最優(yōu)解，消除了個人經(jīng)驗法確定參數(shù)時帶來的龐大誤差[11].

另外，訓練數(shù)據(jù)對參數(shù)組合的性能評價有一定的影響，當選取的訓練集不一樣時，同一組(k,p)所對應的K-NN預測模型的擬合性一般會發(fā)生改變.為了模型的泛化和推廣，本文在網(wǎng)格搜索中引入K-fold交叉驗證法，對每一組(k，p)的性能進行評價.通過網(wǎng)格搜索和K-fold交叉驗證相結合的方法對K-NN的模型參數(shù)k、p進行尋優(yōu)，其步驟如下：

1)網(wǎng)格坐標的建立.令a=[1,2,…，11,12]，b=[1,2]，步長為1，可知模型參數(shù)的網(wǎng)格交叉點(k,p).其中k=αi,i=1,2,…，11,12.p=bj,j=1,2.另外，αi代表a中的第i個元素，bj表示b中的第j個元素.

2)將訓練集均分為K個子集，K的取值往往為4～10，以保證測試樣本遠小于訓練樣本.此外，本文令K=10，因為10倍的交叉驗證會有較好的效果[12].

3)針對網(wǎng)格中每一組參數(shù)(k，p)，隨機取一個子集作為測試集，剩下的K-1個子集作為訓練集，訓練模型后對測試集進行預測，統(tǒng)計訓練模型的分數(shù).

圖1 網(wǎng)格參數(shù)優(yōu)化過程Fig.1 Grid parameter optimization process

4)取另外一個子集為測試集，再將其余K-1個子集看作訓練集，再次計算訓練模型的分數(shù)，直到對每一個子集都進行一次模型評分后，取K組訓練模型分數(shù)的平均值作為該組(k，p)的最終訓練模型分數(shù).

5)取另外一個參數(shù)組合(k，p)，重復步驟2)～4)，依次計算出網(wǎng)格中每個參數(shù)組合下的模型分數(shù)，通過對比選出最大的平均訓練模型分數(shù)，其對應的參數(shù)組合就是網(wǎng)格區(qū)間內(nèi)最優(yōu)的參數(shù)組合.本文選取的最優(yōu)參數(shù)組合為(k=4，p=2).

通過網(wǎng)格搜索與交叉驗證相結合的方法，當訓練模型的平均分數(shù)最大時所對應的參數(shù)為最優(yōu)參數(shù).避免了個人經(jīng)驗法在選取參數(shù)時對K-NN模型分數(shù)帶來重大的影響，同時，在很大程度上減少了訓練樣本的抽取隨機性對模型擬合性能的影響.在結果展示方面呈現(xiàn)等間距的網(wǎng)格搜索結果.如圖1，其高度代表訓練模型的分數(shù).

2.2 特征選擇和特征權重的確定

在傳統(tǒng)的K-NN算法中，每個特征對分類的貢獻是同等重要的.但在實際應用中，每個特征對分類的貢獻是不相同的，一部分起重要作用，另一部分則起次要作用或者沒有起作用.例如，當預測學生的成績時，學生的學習時間、課堂缺勤次數(shù)是重要特征，而性別、身體健康狀況為次要特征，而身高、體重等特征對成績預測基本無關.為了突出重要特征的作用，消除冗余特征對預測結果的干擾，必須找出每個特征的貢獻程度并以此進行特征選擇.本文對貢獻比較大的特征進行適當?shù)脑龃螅瑢ω暙I比較小的特征進行適當?shù)臏p小，此外把沒有貢獻的特征刪除掉.另外為了確定每個特征的貢獻程度，本文引入了基尼系數(shù)和基尼增益的概念，并利用基尼增益來確定每個特征的重要性，并引入縮放因子確定所選特征的最終重要程度.

2.3 基尼增益的計算[13-14]

在決策樹的生成中，獲得信息量的度量方法是從反方向來定義的：如果一種劃分能使數(shù)據(jù)的“不確定性”減少的多，則該劃分能獲得更多的信息.其信息量可以使用其基尼系數(shù)來度量.y的基尼系數(shù)定義為

(2)

對于具體的、隨機變量y生成的數(shù)據(jù)集D= {y1,y2,…,yN}而言，在實際中一般會選擇經(jīng)驗基尼系數(shù)來估計

(3)

假設y的取值空間為{c1,c2,…,ck}，pk表示y取Ck的概率：pk=p(y=Ck)；|Ck|代表由y中類別為ck的樣本數(shù)，|D|代表D的總樣本數(shù)(即|D|=N).

,

(4)

其中

(5)

可以用經(jīng)驗條件基尼系數(shù)來進行估計

,

(6)

公式中的|Djk|代表著Dj中第k類樣本的個數(shù).基尼增益則自然地定義為

G(y,A)=Gini(y)-Gini(y|A).

(7)

2.4 利用基尼增益確定特征的貢獻程度

在本文中,基尼增益比較大的特征稱為主要特征，基尼增益比較小的特征稱為次要特征，沒有獲得基尼增益的特征稱為冗余特征.依據(jù)每一個特征基尼增益的大小，建立一個向量βj(特征權重系數(shù))來表達每個特征的貢獻程度.基尼增益很小的特征對應的權重比較小，較大的特證對應的權重比較大[16].根據(jù)特征的重要程度再進行特征選擇，選出權重比較大的特征.

假設每個訓練樣本有m個特征，計算各個特征的基尼增益，得到一個基尼增益向量[G1,G2,…，Gm].

利用基尼增益向量算出特征權重系數(shù)

(8)

其中，j=(1,2,…,m).ln(e+Gj)為權重系數(shù)縮放因子，如果基尼增益較小時，它會稍微壓縮特征權重系數(shù).如果基尼增益較大時，它稍微放大特征權重系數(shù).所以，通過權重系數(shù)優(yōu)化后的歐氏距離公式為

(9)

2.5 改進的K-近鄰算法

假設有一個帶有標簽的數(shù)據(jù)集x有n個樣本，每個樣本有h個特征.

第1步：利用網(wǎng)格搜索和交叉驗證法找出最優(yōu)的超參數(shù)k和距離度量方式.

第2步：在決策樹生成中，利用基尼系數(shù)和基尼增益算出每個特征的重要程度[G1,G2,…,Gm].

第3步：利用基尼增益向量算出最終特征權重系數(shù).

(10)

第4步：計算新數(shù)據(jù)到每個訓練樣本的歐氏距離

(11)

對求得的所有距離按照從小到大進行排序，越小代表越相似.

第5步：在n個距離值中取前k個樣本數(shù)據(jù)對應的分類標簽.

第6步：統(tǒng)計k個數(shù)據(jù)中出現(xiàn)次數(shù)最多的分類標簽作為新數(shù)據(jù)的分類.

3 實驗方法和結果

3.1 實驗數(shù)據(jù)

3.1.1 Student Performance數(shù)據(jù)集

“Student Performance”為UCI提供的公開數(shù)據(jù).該數(shù)據(jù)集提供了2個不同學科的成績:數(shù)學(mat)和葡萄牙語(por),一共包含1 044個學生，與學生成績有關的特征一共32個.但是目標特征G3與特征G2和G1有很強的相關性.其中，G1和G2是前2個學期的成績，G3是最終期末成績.G1、G2、G3的分數(shù)是0～20，本文設定了新的目標列G，G為G1、G2、G3的平均值，將目標列G分成3類(合格、優(yōu)秀、不及格).

3.1.2 情緒管理課程數(shù)據(jù)集

此數(shù)據(jù)來源于河北大學網(wǎng)絡教學平臺于2017年下半年開設的《情緒管理》這門課程的數(shù)據(jù)，收集到的原始數(shù)據(jù)共有624個學生數(shù)據(jù)，數(shù)據(jù)包括7種學習行為：課程視頻得分(50%)、課程視頻進度、課程測驗得分(20%)、課程測驗進度、考試得分(30%)、討論數(shù)、訪問數(shù)、任務點完成百分比.另外，按照學生的綜合成績將學生的成績劃分為3個等級(合格、優(yōu)秀、不及格).

3.2 特征預處理

數(shù)據(jù)預處理已經(jīng)成為教育大數(shù)據(jù)實現(xiàn)過程中的關鍵步驟，它直接影響著最后的結果.在實際中收集來的數(shù)據(jù)是不干凈的、模糊的而且冗余的.為了提高算法的效率，必須通過數(shù)據(jù)預處理來提供準確、干凈和簡潔的數(shù)據(jù).在這2個數(shù)據(jù)集中，有幾個特征的記錄都是非數(shù)字的.通常情況下，學習算法期望輸入是數(shù)字的，這要求非數(shù)字的特征(稱為類別變量)被轉(zhuǎn)換.轉(zhuǎn)換類別變量的一種流行的方法是使用獨熱編碼方案.獨熱編碼為每一個非數(shù)字特征的每一個可能的類別創(chuàng)建一個“虛擬”變量.例如，學生的性別特征sex有2個取值female或者male.把這個特征編碼成sex_female和sex_male，詳細的轉(zhuǎn)換方法見表1.

表1 非數(shù)值特征轉(zhuǎn)化為數(shù)值特征

3.3 評價指標

考慮到該研究的實質(zhì)，即決定哪些學生需要進行干預.在這種情況下，往往更關心失敗學生的正確分類，而這些學生正是想要關注的對象，而不是通過學生的標簽[17].如：一個通過學生被貼上失敗學生的標簽，這不是一個令人擔憂的問題，因為老師們只是花了一點額外的時間來驗證這個學生，實際上并不是一個有風險的學生.然而，一個被貼上通過標簽的失敗學生將會是一個更大的問題，因為老師們會跳過他們，而那個學生可能會錯過一個干預的機會.因此，在所有實際上失敗的學生中，成功預測出失敗的學生是非常重要的，使用Fβ作為評價指標，這樣能夠同時考慮精準率和召回率，尤其是，當β=0.5時，更多的強調(diào)召回率(即更加關注失敗學生的正確分類)，簡寫為F0.5.

在所有預測有風險的學生中，實際上有風險的學生的比例，簡稱精準率

在所有實際上有風險的學生中，成功預測有風險的學生的百分比，簡稱召回率

精準率和召回率的平衡

公式中的TP代表低分的學生被判為有風險；FP代表高分的學生被判為有風險；FN代表低分的學生被判為沒有風險.

3.4 模型分數(shù)對比

在時間效率上，改進的K-近鄰算法對訓練集做了預處理.通過基尼增益進行特征選擇，選出了基尼增益最大的前幾個特征.通過特征選擇減少了特征的數(shù)量，大大節(jié)省了計算時間和空間.

在分類的精確度上，首先利用網(wǎng)格搜索和交叉驗證相結合的方法對模型參數(shù)進行優(yōu)選，其次，在計算歐式距離時引入了權重系數(shù)βi，使每個特征受到權重系數(shù)的約束，使模型的分數(shù)明顯提高.

當訓練集分別為總數(shù)據(jù)集的40%、60%、80%時，比較了改進的K-NN算法(DT-K-NN)、個人經(jīng)驗法K=5時的傳統(tǒng)K-NN算法以及最優(yōu)參數(shù)下其他常用機器學習算法(隨機森林、樸素貝葉斯、決策樹、支持向量機(SVM)等).在Student Performance數(shù)據(jù)集和情緒管理數(shù)據(jù)集上，改進的K-近鄰算法比傳統(tǒng)K-NN算法在F0.5分數(shù)上提高了約7%,并且稍微高于其他機器學習算法，實驗結果見表2和表3.

表2 在Student Performance數(shù)據(jù)集上不同算法的F0.5分數(shù)

表3 在情緒管理數(shù)據(jù)集上不同算法的F0.5分數(shù)

4 結語

本文給出了一種改進的K-NN算法及其在學習預警中的應用，首先利用網(wǎng)格搜索和交叉驗證相結合的方法對模型參數(shù)進行優(yōu)選，避免了個人經(jīng)驗法在選取參數(shù)時，對K-NN的模型分數(shù)帶來的影響.另外，通過計算每一個特征的基尼增益來確定特征的權重系數(shù)并進行特征選擇,并且根據(jù)權重系數(shù)將特征劃分為重要特征、次要特征和冗余特征,在計算歐氏距離時引入權重系數(shù),使各個特征的作用受其權重系數(shù)的約束，顯著地提高了預測的準確率.最后，本文采用了F0.5分數(shù)作為評價指標，因為在學習預警中往往更加關注失敗學生的正確分類.本文提出的學生預警方法可用于對學生在線學習結果的預測，根據(jù)預測結果及時對有風險的學生進行干預.但在改進算法的實現(xiàn)步驟中，缺乏對關鍵步驟的理論分析，如關鍵步驟的代價分析，算法復雜度分析等，后續(xù)還需要對其中某些技術難題進行更深入的研究.