唐 立，李六杏

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

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

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

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

1 CART算法的概述

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

1.1 Gini指標(biāo)

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

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

假設(shè)集合L在A條件下分成L1和L2，那么集合L的Gini指標(biāo)定義為：

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

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

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

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

1.3 分類決策樹建立步驟

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

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

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

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

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

S6：生成CART決策樹.

S7：防止模型過擬合，利用損失矩陣剪枝法進(jìn)行剪枝，簡(jiǎn)化決策樹.

2 改進(jìn)的CART算法

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

2.1 改進(jìn)運(yùn)算速度

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

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

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

2.2 改進(jìn)CART預(yù)測(cè)精度

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

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

算法具體如下：

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

首先對(duì)模型初始化：

然后計(jì)算偽殘差：

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

最后更新模型：

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

3 基于改進(jìn)CART算法的M-learning

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

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

表1 預(yù)處理后的部分?jǐn)?shù)據(jù)

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

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

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

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

3.2 建立CART決策樹模型

對(duì)表2中46組數(shù)據(jù)建立Fayyad-GB-CART模型，對(duì)其余22組數(shù)據(jù)進(jìn)行模型驗(yàn)證.使用Python程序進(jìn)行實(shí)驗(yàn)，首先對(duì)表2連續(xù)屬性Fayyad分割，以STG，SCG，STR，LPR，PEG為條件屬性，UNS為決策屬性，建立GB-CART模型決策樹模型.在此同時(shí)依據(jù)混淆矩陣法剪枝，修剪一些干擾枝，防止過于擬合，得到更簡(jiǎn)單的決策樹.決策樹的建立運(yùn)用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 改進(jìn)算法的有效評(píng)估

為了方便分析，利用改進(jìn)的CART建立好模型后，和傳統(tǒng)的CART建立好模型，在本實(shí)驗(yàn)中對(duì)其余22組數(shù)據(jù)進(jìn)行預(yù)測(cè)測(cè)試，獲取預(yù)測(cè)的UNS等級(jí)，與實(shí)際情況的準(zhǔn)確率比照見表2.改進(jìn)的CART算法每類預(yù)測(cè)明顯精確度比傳統(tǒng)的CART算法要高很多.

表2 傳統(tǒng)CART與改進(jìn)CART預(yù)測(cè)準(zhǔn)確率比較

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

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

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

3.4 系統(tǒng)中知識(shí)點(diǎn)掌握程度預(yù)測(cè)

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

4 結(jié)語

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

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

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