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

唐 立，李六杏

（安徽經(jīng)濟管理學院 信息工程系，安徽 合肥 230031）

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

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

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

1 CART算法的概述

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

1.1 Gini指標

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

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

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

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

1.2 連續(xù)屬性與離散屬性處理方法

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

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

1.3 分類決策樹建立步驟

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

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

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

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

S5：遞歸調(diào)用S1-S4.

S6：生成CART決策樹.

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

2 改進的CART算法

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

2.1 改進運算速度

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

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

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

2.2 改進CART預測精度

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

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

算法具體如下：

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

首先對模型初始化：

然后計算偽殘差：

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

最后更新模型：

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

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

3.1 樣本數(shù)據(jù)

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

表1 預處理后的部分數(shù)據(jù)

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

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

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

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

3.2 建立CART決策樹模型

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

（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建立好模型后，和傳統(tǒng)的CART建立好模型，在本實驗中對其余22組數(shù)據(jù)進行預測測試，獲取預測的UNS等級，與實際情況的準確率比照見表2.改進的CART算法每類預測明顯精確度比傳統(tǒng)的CART算法要高很多.

表2 傳統(tǒng)CART與改進CART預測準確率比較

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

圖1 Middle等級的迭代次數(shù)與精確度

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

3.4 系統(tǒng)中知識點掌握程度預測

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

4 結語

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

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

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