基于改進CART算法的M-learning過程中知識掌握程度預測

唐 立，李六杏

（安徽經濟管理學院 信息工程系，安徽 合肥 230031）

M-learning是moblie learing的簡稱，通常被譯成移動學習，它是指利用智能終端設備 （如手機、PDA等）進行的遠程學習［1］.隨著移動計算機技術不斷地發展，移動智能終端設備幾乎是每個人必有的設備，M-learning的學習方式是現代教育發展新的階段，它越來越多地受到國家和教育界的重視.在《國家中長期教育改革和發展規劃綱要（2010-2020年）》的指導下，M-learning作為教學輔助越來越多地被應用在高校的教學系統平臺上，如翻轉課堂，基于M-learning實驗平臺，基于MOOC的M-learning平臺等［2］.M-learning的出現，試圖把傳統的“教-學”模式改變成“學-教”模式，目的是為了提倡個性化教學，把教學精確服務到個人，使得教學效果大幅提高.而使用數據挖掘技術對M-learning進行挖掘分析，試圖通過數據挖掘發現一些規律，預測學習效果，為個性化教學提供可靠的依據，采用先學后教即“學-教”模式，精準地把教學服務落實在每一個受教育者的身上［3］.

數據挖掘技術在教學中的應用相當廣泛，有很多專家和學者發表過相關的學術論文，如：攀妍妍將ID3決策樹算法用于對學生在線學習信息的挖掘，找出影響學生學習效果的分類規則［4］；范潔把C4.5算法應用更在在線學習行為評估系統中［5］；謝修娟運用Fayyad和數學等價無窮小改進C4.5，提高運算速度，應用于E-learning教學輔助系統中［6］；趙強利提出基于選擇性集成的增量學習的在線學習模型，針對監督學習和分類問題，提出處理集成問題的相關算法［7］；董彩云在教學系統中用關聯規則挖掘算法，找出影響學生學習興趣因素［8］.

在學習和參考了多位學者研究成果前提之下，根據M-learning實際情況，把CART算法進行改進，構建一個以M-learning過程數據預測知識掌握程度的分類決策樹模型，用于對學生知識掌握程度的預測，目的是為個性化教學提供依據，把更有針對性的教學服務于學生.

1 CART算法的概述

CART（Classification And Regression Tree）是一種二叉樹形式的決策樹算法，二叉樹算法只把每個非葉節點引申為兩個分支，它的結構比ID3和C4.5算法結構更簡潔，易于理解.CART構樹原理，先對樣本數據進行二元分割成兩個子集，對子集再分割，自頂向下不斷遞歸生成樹，直至分支差異結果不再顯著下降，分支沒有意義了，則樹建成.由此可以看出決策樹生長的核心是確定分枝標準，對于CART算法來說，它的分枝標準是從眾多分組變量中找到最佳分割點，其方式就是用Gini指標來表示數據純度.

1.1 Gini指標

Gini指標是樣本雜質度量方法，假設一個樣本共有G個類，那么節點L的Gini不純度可以定義為：

其中pg為樣本點屬于第g類的概率.直觀來看，Gini指標反映了數據集中隨機抽取兩個樣本，其類別標記不一樣的概率，也就是Gini越小，當前數據純度就越高.

假設集合L在A條件下分成L1和L2，那么集合L的Gini指標定義為：

在劃分屬性時，選擇使得劃分后Gini指標最小的屬性為最優屬性，并以此為分支準則建樹.

1.2 連續屬性與離散屬性處理方法

（1）對于離散屬性.CART算法對離散屬性分各值的不同組合，按不同組合將其分到樹的左右兩枝，對所產生的樹進行Gini指標判定，從而找出最優組合項.如果只有兩個值，那么就只有一種組合；如果是多屬性（X1,X2,X3），則會產生（X1,X2）和 X3、（X1,X3）和 X2、（X3,X2）和 X1的 3 種組合.這是因為 CART 遵循著二元分割特性.對于n個屬性，可以分出（2n-2）/2種組合情況.

（2）對于連續屬性.CART算法對連續屬性，先進行屬性按值排序，分別取相鄰兩個值的平均值作為分割點，二分成左右兩樹，計算Gini指標，判定最佳分割點.對于連續屬性分割一般運算量都比較大，本文后面章節將進一步介紹.

1.3 分類決策樹建立步驟

S1：計算已有樣本L的Gini指標值，利用公式（1）選擇最小Gini指標作為決策樹的根節點.

S2：整理樣本集合的所有的子集組合，對于離散屬性，計算所有子集得出最小Gini指數，對于連續屬性，進行最佳分割閥值離散化.

S3：對連續屬性每一特征A，對它可能取值a，可以劃分A≥a與A

S4：找出對應Gini指標最小Gini（L，A）的最優切分特征及取值，并判斷是否切分停止條件，否，則輸出最優切分點.

S5：遞歸調用S1-S4.

S6：生成CART決策樹.

S7：防止模型過擬合，利用損失矩陣剪枝法進行剪枝，簡化決策樹.

2 改進的CART算法

傳統CART算法在處理連續屬性離散劃分過程比較復雜，運算量比較大，同時對小量樣本數據的預測精度比較低.為了彌補這些不足，本文提出首先利用Fayyad邊界點判定定理減少CART算法對連續屬性最優閥值運算量，然后用GB算法把弱預測器迭代成強預測器，提高小量樣本數據預測準確度.

2.1 改進運算速度

傳統CART算法在對連續屬性離散化時，先樣本L所有的屬性按值要進行排序，如得到L1，L2，L3，…，Ln，然后對每個相連的屬性值的平均數進行分割，這樣就對L的N個屬性值產生了N-1個分割點，最后對每個分割點進行計算Gini指標值，得到最小的Gini值的屬性就是L的最佳分割點.經常遇到連續數據值的個數是非常大的，會產生大量的分割點，使得運算量變大，減低了決策樹生成的效率.利用Fayyad邊界點判定優化連續數據值分割次數，提高對連續屬性離散化的效率.

Fayyad邊界定理［9］，首先將樣本集L按照連續屬性值X進行升序排序，假設存在相鄰的數據L1，L2，只要滿足 X（L1）

邊界定理表明，對于連續屬性劃分分割閥值點，是找出兩個相鄰且不容類別的邊界點上，然后計算出前后兩個相鄰點的屬性平均值.例如對樣本數據L按X屬性升序排序{L1，L2，L3，…，L10}，進行Fayyad邊界劃分分割閥值點，只需要5次分割值點運算Gini值.而傳統CART算法的連續屬性處理方法，則需要對數據L進行9次分割值點運算Gini值.可以看出利用Fayyad減少分割值點運算次數.

2.2 改進CART預測精度

傳統的CART算法本身就是一種大樣本統計方法，對異常數據抗干擾性強，泛化能力強，但是遇到一些樣本量相對比較小時，模型就顯得不穩定，容易忽視一些小量數據，形成弱預測器，造成預測錯誤.本文提出GB算法，能夠使CART算法重復利用小量樣本數據，集成多個弱預測器生成強預測器，建立更為穩定的預測，從而提高了CART預測精確度.

GB算法是一種解決分類問題的機器學習算法，它是屬于Booting算法的一個分支.其原理是，首先對每組樣本賦予相同的權重，通過對一組樣本訓練建立一個弱預測器；其次利用弱預測器進行預測，對預測結果進行樣本權重調整.如果預測精度較高，降低樣本權重，如果預測精度低了，則增加樣本權重.最后，把不斷訓練和權重調整過程中的一系列預測器和權重值集成形成強預測器，從而提高預測精確度［10］.

算法具體如下：

間劃分為迭代次數為k的不同區域為S1t,S2t，S3t,…,Skt，其中T為迭代次數，CART葉子數為K.

首先對模型初始化：

然后計算偽殘差：

計算 Zt(a)的系數 γkt：

最后更新模型：

從GB集成CART算法中看出，GB算法就是建立的每一個弱預測器都在上一個弱預測器損失函數 L（b，F（a））的梯度方向，這樣使得模型不斷更新和改進［11］.

3 基于改進CART算法的M-learning

3.1 樣本數據

M-learning過程是學生對基礎知識認識和掌握的過程，從學生用戶進入系統，相關數據就會產生，系統后臺收集學生學習數據，存儲在用戶信息庫中，然后再從信息庫中提取學生學習數據進行預測分析.本文數據來源是通過M-learning對《Flash設計》課程中第五章節遮罩層的學習行為數據，因為條件有限，只對一個班級68位學生進行數據采集，所以只能對共計68條少數據量用以建立決策樹模型和預測測試.目的是預測通過M-learning學生對相關知識點掌握程度，數據通過5個維度來衡量知識的掌握程度［12-13］，分別是：STG：學習當前章節知識的學習時長；SCG：對當前章節知識的重復學習次數；STR：儲備知識的學習時長，即之前章節學習時長；LPR：儲備知識的學習在線測試成績；PEG：當前章節知識的考試成績.最后我們通過課堂測試和完成項目程度綜合測評知識的掌握程度UNS，它有4個水平，即Very Low、Low、Middle、High.數據見表 1.

表1 預處理后的部分數據

為了保證數據的完整和一致性，對數據進行如下處理：

（1）時間數據是比較復雜的，而實際得到的數據大多數以秒為單位，導致運算數據量增大.通過測試，在不影響精確度的前提下，我歸化時間為分鐘.因為時間太精細對于構建知識掌握程序模型并沒有意義，同時這樣大大降低數據復雜度.

（2）對于在線成績數據缺失問題，為了保證精確度，將其數據過濾掉.

（3）學生在操作學習平臺軟件時可能出現異常操作，對重復學習次數設定閥值，出現學習次數超過閥值，或者單位時間內出現的學習次數過多等異常情況，進行及時篩除，排除數據異常.

3.2 建立CART決策樹模型

對表2中46組數據建立Fayyad-GB-CART模型，對其余22組數據進行模型驗證.使用Python程序進行實驗，首先對表2連續屬性Fayyad分割，以STG，SCG，STR，LPR，PEG為條件屬性，UNS為決策屬性，建立GB-CART模型決策樹模型.在此同時依據混淆矩陣法剪枝，修剪一些干擾枝，防止過于擬合，得到更簡單的決策樹.決策樹的建立運用if-then形式表示分類規則，其形式如同：

（1）If STG<19&&SCG<2&&… then UNS=Very Low

（2）If 20==2&&72

（3）If STG>=30&&STR>=91&&PEG>=92&&… then UNS=High

…….

3.3 改進算法的有效評估

為了方便分析，利用改進的CART建立好模型后，和傳統的CART建立好模型，在本實驗中對其余22組數據進行預測測試，獲取預測的UNS等級，與實際情況的準確率比照見表2.改進的CART算法每類預測明顯精確度比傳統的CART算法要高很多.

表2 傳統CART與改進CART預測準確率比較

Fayyad-GB-CART模型建立中，對模型迭代次數設定為46，通過不斷迭代更新模型的精確度.對UNS等級為Middle分類的迭代次數與精確度的關系見圖1.

圖1 Middle等級的迭代次數與精確度

隨著迭代次數提升，精確度也隨之緩慢提高.對于小樣本數據通過Fayyad-GB-CART迭代是可以提升其精確度的.改進的CART算法建立的模型具有有效性，可靠性和準確性.

3.4 系統中知識點掌握程度預測

把決策樹算法運用到M-learning教學輔助中，可以根據學生M-learning過程中的學習行為和成績數據，較為準確地預測學生對知識點掌握程度，首先可以及時預警告學生，讓他做出自我調整.其次教師依據統計整個班級預測情況及時準確地更正課堂教學計劃.例如整個班級知識點掌握預測普遍LOW等級，這時課堂上教師就要把原計劃項目化制作修改為知識點鞏固教學.最后教師可以針對個別學生情況，線上或課堂進行個性化輔導.

4 結語

Fayyad邊界法減少CART算法分割閥值點運算次數，GB算法提高了小量樣本數據的精確度，本文集合Fayyad邊界和GB算法，改進了CART算法在連續屬性和小樣本數據特殊情況下的使用，并使之運用在M-learning教學輔助中，以《FLASH設計》中遮罩層知識掌握程度做實驗，對采集的68條數據進行建模并預測，實驗證明改進的CART算法不僅速度有所提高，精確度也提高很多，但是依然還存在一些不足.

（1）GB算法下CART模型建立提高了預測精確度，但模型計算量隨著迭代次數而增加，迭代次數的權重設置是一個需要進一步研究的點.

（2）改進的CART算法大多針對小樣本數據量給建立帶來不穩定性而提出的，遇到的情況是屬于特殊情況下采用的方法，只針對小數據效果明顯.如何改進大數據量的運算精確度將是下一步需要研究.