基于改進(jìn)C4.5的E-learning教學(xué)輔助系統(tǒng)的研究與實(shí)現(xiàn)①

謝修娟， 李香菊， 操鳳平， 孫 麗

(東南大學(xué)成賢學(xué)院計(jì)算機(jī)工程系，江蘇 南京 210000)

0 引 言

E-learning (Electronic Learning)，譯作"數(shù)字化學(xué)習(xí)"，是指學(xué)生利用網(wǎng)絡(luò)學(xué)習(xí)平臺(tái)上的數(shù)字化學(xué)習(xí)資源,進(jìn)行自主學(xué)習(xí)的一種全新式以學(xué)生為主體的學(xué)習(xí)方式[1]。在《國家中長期教育改革和發(fā)展規(guī)劃綱要(2010-2020年》的指揮棒作用下[2]，越來越多的高校開始使用E-learning平臺(tái)，將其作為傳統(tǒng)課堂教學(xué)的輔助系統(tǒng)，形成線下學(xué)習(xí)與線上學(xué)習(xí)融為一體的混合式學(xué)習(xí)[3]。使用數(shù)據(jù)挖掘技術(shù)對在線學(xué)習(xí)過程進(jìn)行學(xué)習(xí)分析，以提高在線學(xué)習(xí)的效率，被排在目前影響高校教育的六大信息技術(shù)的首位[4]。

孫玉榮等人采用關(guān)聯(lián)規(guī)則技術(shù)對學(xué)生在線學(xué)習(xí)歷史數(shù)據(jù)進(jìn)行分析，得到學(xué)習(xí)行為間的關(guān)聯(lián)[5]；梁燕紅用web日志挖掘技術(shù)，找出訪問頻度高的知識點(diǎn)網(wǎng)頁，并挖掘出知識點(diǎn)之間的訪問序列，從而了解學(xué)生的學(xué)習(xí)需求趨勢[6]；針對監(jiān)督學(xué)習(xí)和分類問題，趙強(qiáng)利提出選擇性集成與增量學(xué)習(xí)相結(jié)合的在線學(xué)習(xí)模型，利用模式挖掘技術(shù)解決選擇性集成問題，并給出相關(guān)算[7]；攀妍妍將ID3決策樹算法用于對學(xué)生在線學(xué)習(xí)信息的挖掘，找出影響學(xué)生學(xué)習(xí)效果的分類規(guī)則[8]；武靖娜提出了一個(gè)針對大規(guī)模分布式網(wǎng)絡(luò)學(xué)習(xí)機(jī)的數(shù)據(jù)挖掘應(yīng)用程序的通用框架，并基于局部學(xué)習(xí)者間的關(guān)系研究了一種高效的在線學(xué)習(xí)算法[9]。

在借鑒和參考多位學(xué)者研究成果的基礎(chǔ)上，在自構(gòu)建的E-learning教輔系統(tǒng)中，引入改進(jìn)后的C4.5決策樹算法，對采集到的學(xué)生學(xué)習(xí)行為數(shù)據(jù)進(jìn)行挖掘，構(gòu)建“學(xué)習(xí)行為-學(xué)習(xí)效果”間的決策樹模型，并運(yùn)用此模型對參與在線學(xué)習(xí)的學(xué)生的課程學(xué)習(xí)效果進(jìn)行預(yù)測，一是便于學(xué)生能夠及時(shí)發(fā)現(xiàn)自身學(xué)習(xí)的不足之處，盡快調(diào)整學(xué)習(xí)行為，二是幫助教師及時(shí)發(fā)現(xiàn)課程學(xué)習(xí)中的一些問題學(xué)生，早期介入和引導(dǎo)。

1 C4.5算法及其改進(jìn)

1.1 C4.5算法

C4.5算法由ID3算法改進(jìn)而來。相較于ID3算法，第一，C4.5算法能夠處理連續(xù)屬性，第二，用信息增益率代替信息增益進(jìn)行選擇屬性，有效避免ID3算法在確定分支時(shí)容易傾向于取值較多的屬性的情況發(fā)生[10～12]。C4.5算法[13]的具體步驟如下：

已知數(shù)據(jù)源樣本集D={D1，D2，…，Dn}，D被分為k類，記為類標(biāo)號集合C={C1，C2,…，Ck}，D中每個(gè)樣本用一包含p項(xiàng)屬性的屬性向量(A1，A2,…，Ap)來表示，其中任意一個(gè)屬性Ai(0≤i≤p) ，假設(shè)有v個(gè)不同取值。

Step1：對數(shù)據(jù)源樣本集進(jìn)行預(yù)處理，保證每個(gè)屬性變量都是離散型取值，若存在連續(xù)性屬性變量，則按照step8中的操作進(jìn)行；

Step2：計(jì)算樣本集D對分類C的平均信息熵Entropy(D)； Step3：計(jì)算任意的離散屬性Ai(0≤i≤p)，劃分樣本集D的信息熵EntropyA(D)；

Step4：計(jì)算每個(gè)屬性Ai對樣本集D的信息增益Gain(A)，即Ai對D進(jìn)行劃分前后信息熵的差；

Step5：計(jì)算每個(gè)屬性Ai對樣本集D的信息增益率GainRation(A)，其等于信息增益與分割信息量(SplitInfoA(D) )的商；

Step6：選取信息增益率最大的屬性作為決策樹的根節(jié)點(diǎn)，根節(jié)點(diǎn)的每一個(gè)不同取值對應(yīng)一個(gè)分支，遞歸地執(zhí)行Step2- Step5，選擇分支中信息增益率最大的屬性作為子節(jié)點(diǎn)，以此類推，直至每個(gè)分支的屬性取值相同，得到葉結(jié)點(diǎn)，從而完成決策樹的構(gòu)建；

Step7：根據(jù)構(gòu)造的決策樹提取分類規(guī)則，對新的數(shù)據(jù)集進(jìn)行分類預(yù)測；

Step8：C4.5算法處理連續(xù)屬性時(shí)，首先，將連續(xù)屬性的取值按照從小到大排序，得到屬性的值序列{Av1，Av2，…，Avn}，取相鄰兩個(gè)屬性值之間的中點(diǎn)作為分割閾值點(diǎn)，值序列{Av1，Av2，…，Avn}有n個(gè)屬性值，共生成n-1個(gè)分割閾值點(diǎn)，每個(gè)閾值點(diǎn)將數(shù)據(jù)集劃分為大于閾值和小于等于閾值的兩個(gè)子集，然后計(jì)算每個(gè)閾值點(diǎn)的信息增益，選擇信息增益最大的閾值點(diǎn)作為最佳分割閾值點(diǎn)，最后計(jì)算最佳分割閾值點(diǎn)的信息增益率，并將其作為該屬性的信息增益率，跳轉(zhuǎn)至step6。

1.2 C4.5算法改進(jìn)

C4.5算法在處理連續(xù)屬性時(shí)，需要對n-1個(gè)分隔閾值點(diǎn)分別計(jì)算其信息增益，這一過程中涉及到大量的對數(shù)函數(shù)運(yùn)算，由此預(yù)見，當(dāng)樣本集中連續(xù)屬性數(shù)量比較多，而每個(gè)連續(xù)屬性的取值又比較多，算法的計(jì)算工作量相當(dāng)之繁重，從而影響算法的執(zhí)行效率。為此，提出兩點(diǎn)改進(jìn)措施，第一，運(yùn)用Fayyad邊界點(diǎn)判定原理[14]，減少分割閾值點(diǎn)的判定數(shù)量；第二，利用基于泰勒公式和麥克勞林公式得到的等價(jià)無窮小理論，將對數(shù)運(yùn)算用線性運(yùn)算代替，降低計(jì)算復(fù)雜度。

Fayyad定理：若T使得E(A，T，S)最小，則T是一邊界點(diǎn)，其中，A是屬性，S為屬性的值集合，E表示平均信息熵，T為某一分割閾值點(diǎn)。

邊界定理表明，對于連續(xù)屬性A，離散化后的最佳分割閾值點(diǎn)必定出現(xiàn)在兩個(gè)相鄰且不同類別的邊界點(diǎn)處。算法中具體做法是：將某一連續(xù)屬性的所有取值按照升序排列，然后找出導(dǎo)致類標(biāo)號發(fā)生變化的點(diǎn)，計(jì)算前后兩個(gè)相鄰點(diǎn)的屬性平均值，作為分割閾值點(diǎn)。例如下面的屬性/類別數(shù)據(jù)：

上述14組數(shù)據(jù)，如果用傳統(tǒng)C4.5算法中的連續(xù)屬性處理方法，共得到13個(gè)分割閾值點(diǎn)，而運(yùn)用Fayyad定理，得到7個(gè)分割閾值點(diǎn)(一條分割線代表一個(gè)點(diǎn))。 可見，當(dāng)相同類標(biāo)號集中在一起時(shí)，此方法能大大減少分割閾值點(diǎn)的個(gè)數(shù)，最壞情況下，相鄰的兩兩類標(biāo)號均不同，此時(shí)分割閾值點(diǎn)的個(gè)數(shù)與傳統(tǒng)方法得到的個(gè)數(shù)相當(dāng)。

此外，還運(yùn)用數(shù)學(xué)等價(jià)無窮小理論改進(jìn)算法，下面來驗(yàn)證該方法的可行性。為簡單起見，假設(shè)樣本集D僅有兩個(gè)類別，用P和N表示分別D中屬于正例和反例的記錄個(gè)數(shù)，那么該樣本集能作出正確分類所需要的信息熵為：

根據(jù)等價(jià)無窮小理論，當(dāng)x很小時(shí)，有l(wèi)n(1+x)≈x，因此上述式子可簡化為：

(1)

任意一個(gè)屬性A，有v個(gè)不同取值，它將樣本集D劃分為D1，D2，…，DV共v個(gè)子集，假設(shè)每個(gè)子集Di中含有Pi個(gè)正例和Ni個(gè)反例，則子集Di的信息熵為：

采用同公式(6)相同的處理方法，得到：

(2)

某個(gè)屬性有v個(gè)不同取值，第i個(gè)取值對應(yīng)的樣本記錄個(gè)數(shù)為PSi，該值外其它取值對應(yīng)的樣本數(shù)據(jù)被劃到另一個(gè)類，樣本記錄個(gè)數(shù)記為NSi，則該屬性的分割信息量為：

化簡后得到：

(3)

改進(jìn)的C4.5算法在計(jì)算信息熵以及分割信息量時(shí)，采用僅包含四則混合運(yùn)算的公式(1)～(3)，而且實(shí)際運(yùn)算中，可將公式中的常數(shù)部分忽略，如“2”，“l(fā)n2”，因?yàn)閷ν活悢?shù)據(jù)作相同倍數(shù)變化對于判定結(jié)果沒有影響，如此一來，相較于傳統(tǒng)算法的大量對數(shù)運(yùn)算，計(jì)算復(fù)雜度大大降低，算法的執(zhí)行效率大大提高。

2 基于改進(jìn)C4.5算法的E-learning教輔系統(tǒng)

2.1 系統(tǒng)體系結(jié)構(gòu)設(shè)計(jì)

系統(tǒng)體系結(jié)構(gòu)如圖1所示，一切學(xué)習(xí)/教學(xué)活動(dòng)都是通過用戶接口登錄后進(jìn)行，“數(shù)據(jù)采集和預(yù)處理”模塊負(fù)責(zé)收集并處理學(xué)生的在線學(xué)習(xí)數(shù)據(jù)，存儲(chǔ)至用戶信息庫。“決策分析”模塊再從庫中提取學(xué)習(xí)行為數(shù)據(jù)進(jìn)行預(yù)測分析。

圖1 系統(tǒng)體系結(jié)構(gòu)圖

2.2 構(gòu)造決策樹模型

2.2.1 數(shù)據(jù)采集與預(yù)處理

實(shí)驗(yàn)的數(shù)據(jù)是E-learning中2016 -2017年第1學(xué)期的《C語言程序設(shè)計(jì)》課程的學(xué)生在線學(xué)習(xí)數(shù)據(jù)，共計(jì)900條。參與挖掘的在線學(xué)習(xí)行為屬性項(xiàng)有5個(gè)：在線總時(shí)長(Time)、在線單元測試的平均成績(UnitScore)、在線單元測試的次數(shù)(UnitCount)、BBS的參與次數(shù)(BBS)、作業(yè)提交次數(shù)(Work)。將教務(wù)系統(tǒng)中調(diào)取得到的課程期末成績(Grade)作為度量學(xué)習(xí)效果的類別項(xiàng)，成績使用等級制，分別為A(100-80)，B(70-79)，C(60-69)，D(<60)。表1為經(jīng)過處理后的部分?jǐn)?shù)據(jù)。

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

由于數(shù)據(jù)采集來源和渠道的多樣性，導(dǎo)致存在有些學(xué)生成績?nèi)笔У膯栴}，為保證數(shù)據(jù)的完整性和一致性，在數(shù)據(jù)預(yù)處理階段需要處理缺失值，處理的方法包括：

(1) 如果是因?yàn)槿笨蓟蚓徔荚驅(qū)е鲁煽內(nèi)笔?，將用補(bǔ)考成績替換缺失值，實(shí)在找不到可替代的值，將其置為0或者不及格。

(2) 對于存在多次補(bǔ)考、重考的學(xué)生，選擇第一次有效成績，替換缺失值；

(3) 如果學(xué)生因?yàn)檩z學(xué)或者轉(zhuǎn)專業(yè)原因?qū)е鲁煽內(nèi)笔?，那么這些學(xué)生的數(shù)據(jù)將被過濾掉，因?yàn)樗麄兊臄?shù)據(jù)對于構(gòu)建學(xué)生成績模型沒有意義。

2.2.2 構(gòu)造決策樹模型并導(dǎo)出分類規(guī)則

上述的900條數(shù)據(jù)中，抽取其中的三分之二作為訓(xùn)練樣本集，三分之一作為測試樣本集，對600條訓(xùn)練集數(shù)據(jù)應(yīng)用改進(jìn)后的C4.5算法構(gòu)建決策樹模型，并使用if-then形式表示分類規(guī)則，從樹根到葉的每條路徑對應(yīng)一條規(guī)則，記為：if Cond1 && Cond2 &&…&& Condn then Class C[15]，其中if部分稱為規(guī)則前件，是若干屬性值的合取，then部分稱為規(guī)則后件，對應(yīng)所屬的類別。導(dǎo)出分類規(guī)則的具體做法是：從樹的根節(jié)點(diǎn)出發(fā)，沿著某條路徑上的每個(gè)屬性值對應(yīng)規(guī)則前件的一個(gè)合取項(xiàng)，葉子節(jié)點(diǎn)則為規(guī)則的后件。本次實(shí)驗(yàn)共得到23條“學(xué)習(xí)行為-學(xué)習(xí)效果”的分類規(guī)則，形如：

(1) if time >43 then A

(2)if 20=8 then B

(3)if 20=95 then A

……

2.2.3 改進(jìn)算法的有效性評估

為驗(yàn)證分類模型的準(zhǔn)確性，本實(shí)驗(yàn)中將對剩下的300條測試集中的學(xué)習(xí)行為樣本數(shù)據(jù)進(jìn)行預(yù)測，獲得其成績等級，并通過驗(yàn)證測試結(jié)果與實(shí)際情況相吻合的程度來計(jì)算分類預(yù)測準(zhǔn)確率，測試結(jié)果如表2所示。

表2 準(zhǔn)確性評估結(jié)果

從表2的測試評估結(jié)果得知，總的預(yù)測準(zhǔn)確率為87.83%，具有很好的預(yù)測效果，因此能夠利用改進(jìn)的C4.5算法挖掘得到的“學(xué)習(xí)行為-學(xué)習(xí)效果”分類模型，對未來在線學(xué)習(xí)的學(xué)生的課程學(xué)習(xí)效果進(jìn)行預(yù)測。

2.3 E-learni ng系統(tǒng)中學(xué)習(xí)效果的預(yù)測

融入決策樹技術(shù)的E-learning教輔系統(tǒng)能夠?qū)φn程學(xué)習(xí)效果提前預(yù)測，如圖2所示。參與某課程學(xué)習(xí)的學(xué)生能夠根據(jù)現(xiàn)有的在線學(xué)習(xí)行為預(yù)測課程最終的成績，同時(shí)課程任課教師能夠預(yù)測所帶班級所有學(xué)生的課程成績。對于預(yù)測結(jié)果不理想的學(xué)生，可以根據(jù)系統(tǒng)提示信息，如：在線學(xué)習(xí)時(shí)間不足，BBS參與少，作業(yè)提交次數(shù)少等，作出學(xué)習(xí)方法的自我調(diào)整，或者由教師加以個(gè)性化輔導(dǎo)。

圖2 學(xué)習(xí)效果預(yù)測

3 結(jié) 語

基于Fayyad邊界點(diǎn)判定原理和數(shù)學(xué)的等價(jià)無窮小理論，對傳統(tǒng)決策樹C4.5算法進(jìn)行了優(yōu)化，優(yōu)化后的算法在處理連續(xù)屬性時(shí)能減少分割閾值點(diǎn)的個(gè)數(shù)，以及用加減乘除運(yùn)算代替?zhèn)鹘y(tǒng)算法中大量的對數(shù)運(yùn)算，并將改進(jìn)后的C4.5算法應(yīng)用于E-learning教輔系統(tǒng)的成績預(yù)測分析中，以《C語言程序設(shè)計(jì)》課程為例，對采集到的900條學(xué)生歷史學(xué)習(xí)數(shù)據(jù)，進(jìn)行分類建模，得出能夠有效識別學(xué)生學(xué)習(xí)行為并預(yù)測學(xué)生未來成績的決策樹模型，這些信息在后續(xù)教學(xué)和學(xué)習(xí)中有非常重要的參考價(jià)值。融入了學(xué)習(xí)效果預(yù)測機(jī)制的E-learning教輔系統(tǒng)，在課程教學(xué)和學(xué)習(xí)實(shí)踐中有廣闊的發(fā)展空間，一方面，教師能夠根據(jù)學(xué)生的在線學(xué)習(xí)數(shù)據(jù)，隨時(shí)預(yù)測本門課程的學(xué)習(xí)效果，以盡早發(fā)現(xiàn)問題學(xué)生，另一方面，學(xué)習(xí)者自身在學(xué)習(xí)過程中，利用預(yù)測的數(shù)據(jù)及時(shí)發(fā)現(xiàn)問題，從而及時(shí)調(diào)整學(xué)習(xí)方法等。

[1] 黃海. 高校數(shù)字化學(xué)習(xí)建設(shè)和應(yīng)用推廣研究——以中山大學(xué)數(shù)字化學(xué)習(xí)“115”模式為例[J]. 現(xiàn)代教育技術(shù), 2013, 23(4):56-63.

[2] 袁貴仁. 國務(wù)院關(guān)于實(shí)施《國家中長期教育改革和發(fā)展規(guī)劃綱要(2010—2020年)》工作情況的報(bào)告[C].第十一屆全國人民代表大會(huì)常務(wù)委員會(huì)第二十四次會(huì)議,2012:58-65.

[3] 陳瑞增. 信息化環(huán)境下高?；旌鲜綄W(xué)習(xí)探索與實(shí)踐[D]. 湖北:華中師范大學(xué), 2014.

[4] Siemens G.1st International conference on learning analytics and knowledge 2011.https://tekri.athabascau.ca/analytics/about.

[5] 孫玉榮, 羅立宇, 黃慧華. 數(shù)據(jù)挖掘在網(wǎng)絡(luò)教學(xué)中的應(yīng)用[J]. 現(xiàn)代教育技術(shù), 2009, 19(6):104-106.

[6] 梁燕紅. Web數(shù)據(jù)挖掘技術(shù)在網(wǎng)絡(luò)教學(xué)中的應(yīng)用[J]. 科技信息, 2011(22).

[7] 趙強(qiáng)利. 基于選擇性集成的在線機(jī)器學(xué)習(xí)關(guān)鍵技術(shù)研究[D]. 國防科學(xué)技術(shù)大學(xué), 2010.

[8] 樊妍妍. ID3決策樹算法對教學(xué)輔助系統(tǒng)的優(yōu)化[J]. 齊齊哈爾大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016(1):85-89.

[9] 武靖娜, 楊姝, 王劍輝. 一種分布式大數(shù)據(jù)挖掘的快速在線學(xué)習(xí)算法[J]. 沈陽師范大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 34(1):100-104.

[10] 徐鵬, 林森. 基于C4.5決策樹的流量分類方法[J]. 軟件學(xué)報(bào), 2009, 20(10):2692-2704.

[11] 劉興文, 王典洪, 陳分雄. 一種基于變精度粗糙集的C4.5決策樹改進(jìn)算法[J]. 計(jì)算機(jī)應(yīng)用研究, 2011, 28(10):3649-3651.

[12] 苗煜飛, 張霄宏. 決策樹C4.5算法的優(yōu)化與應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用, 2015,51(13):255-258.

[13] Quinlan J R.C4.5：Program for machine learning[M].San Marteo：Morgan-Kaufmann Publishers，1993.

[14] Fayyad U M, Irani K B. On the handling of continuous-value attributes in decision tree generation[J]. Machine Learning, 1992,8(1): 87-102.

[15] 范潔, 楊岳湘, 溫璞. C4.5算法在在線學(xué)習(xí)行為評估系統(tǒng)中的應(yīng)用[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2006, 27(6):946-948.