王士霞

(新鄉(xiāng)醫(yī)學(xué)院臨床技能培訓(xùn)中心,河南新鄉(xiāng)453003)

基于決策樹的在線學(xué)習(xí)行為分析

王士霞

(新鄉(xiāng)醫(yī)學(xué)院臨床技能培訓(xùn)中心,河南新鄉(xiāng)453003)

利用決策樹算法出色的數(shù)據(jù)分析能力和直觀易懂的結(jié)果展示等特點(diǎn),采用C4.5算法挖掘?qū)W生在線學(xué)習(xí)行為與學(xué)習(xí)效果的歷史數(shù)據(jù).為避免決策樹“過擬合”問題,在已生成的決策樹上采用PEP方法進(jìn)行剪枝,并構(gòu)建學(xué)習(xí)分析模型.最后,利用建立的分析模型對(duì)測(cè)試數(shù)據(jù)集進(jìn)行評(píng)估,得到了較為理想的分類預(yù)測(cè)結(jié)果.學(xué)習(xí)分析模型的創(chuàng)建為科學(xué)、合理地評(píng)估學(xué)生在線學(xué)習(xí)行為提供了有效的方法和手段,同時(shí)也給教學(xué)設(shè)計(jì)和課件開發(fā)提供了參考性建議.

數(shù)據(jù)挖掘;決策樹;C4.5;在線學(xué)習(xí)行為

隨著網(wǎng)絡(luò)開放課程的普及和學(xué)習(xí)技術(shù)系統(tǒng)的發(fā)展,在線學(xué)習(xí)行為越來越多地發(fā)生在各種教育情境中,也給我們帶來了大量的學(xué)習(xí)行為數(shù)據(jù).如何利用海量的大數(shù)據(jù)提高學(xué)習(xí)效果,輔助在線教學(xué)日益成為教育者和學(xué)習(xí)者共同關(guān)注的話題,由此,學(xué)習(xí)分析技術(shù)應(yīng)運(yùn)而生.在新媒體聯(lián)盟發(fā)布的《2013年地平線報(bào)告》中[1],學(xué)習(xí)分析(Learning Analysis)技術(shù)被排在未來五年內(nèi)影響高等教育的六大信息技術(shù)的第一位[2].如何構(gòu)造高效的數(shù)據(jù)挖掘算法去發(fā)現(xiàn)和理解隱藏在數(shù)據(jù)背后的信息,成為學(xué)習(xí)分析技術(shù)中成為最核心的問題.

決策樹(Decision Tree)起源于概念學(xué)習(xí)系統(tǒng)CLS(Concept Learning System),它從一系列無規(guī)則、無次序的事例中推理出決策樹表示形式并形成相應(yīng)的分類規(guī)則[3],是從數(shù)據(jù)中生成分類和預(yù)測(cè)器的一種快速、有效的方法.C4.5算法[4]是Quilan于1993年提出來的,它改進(jìn)了ID3算法的不足,引入了新的方法和功能,如:提出了連續(xù)屬性的離散化處理方法;通過信息增益比例的計(jì)算來選擇特征屬性,使其適用于缺少特征值的訓(xùn)練樣本的情況,同時(shí)解決了信息增益偏向于選擇特征取值較多的問題;在決策樹構(gòu)造過程中或者構(gòu)造完成之后,為避免樹的過度擬合使用相應(yīng)的修剪技術(shù);引入K交叉驗(yàn)證用來選取局部最優(yōu)解.該算法因其具有較高的算法精度、較強(qiáng)的適應(yīng)性等特點(diǎn)得到了廣泛應(yīng)用.本文通過對(duì)學(xué)生在線學(xué)習(xí)行為進(jìn)行監(jiān)控,采用決策樹分類算法C4.5對(duì)獲得的學(xué)習(xí)行為數(shù)據(jù)進(jìn)行評(píng)估,挖掘分析在線學(xué)習(xí)行為與學(xué)習(xí)效果之間的內(nèi)在聯(lián)系,實(shí)現(xiàn)學(xué)習(xí)過程的智能評(píng)價(jià),為學(xué)習(xí)者合理安排在線學(xué)習(xí)提供指導(dǎo)性意見.

1 C4.5決策樹算法

C4.5是機(jī)器學(xué)習(xí)算法中的一種分類預(yù)測(cè)算法,其總體框架可以分為兩步:第一步是基于訓(xùn)練數(shù)據(jù)集構(gòu)建分類預(yù)測(cè)模型,包括建樹(Tree Building)和剪枝(Tree Pruning)兩個(gè)階段組成;第二步是將測(cè)試數(shù)據(jù)集應(yīng)用于該模型,輸出分類預(yù)測(cè)結(jié)果.其中第一步建立用于分類預(yù)測(cè)的決策樹模型是最重要的工作.

1.1 C4.5決策樹的建立

設(shè)訓(xùn)練數(shù)據(jù)集T的類標(biāo)號(hào)屬性具有m個(gè)不同值,定義m個(gè)不同類Ci(i =1,2,...,m).其中某屬性A有v個(gè)不同值,屬性將集合T劃分為v個(gè)子集{T1,T2,...,Tv}.屬性A的信息增益可表示為

C4.5決策樹形成算法通過遞歸的過程由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵決策樹,算法C4.5 FormTree(T,A)的偽代碼如下,其中,T表示樣本集,候選屬性集用T_attributeList表示.

1.2 C4.5決策樹的剪枝

C4.5決策樹的剪枝策略的主要目的是避免決策樹過擬合(Overfitting)樣本.通常采用的策略是后剪枝方法[5],即在已生成過擬合決策樹上進(jìn)行剪枝,對(duì)那些置信度不夠的子樹節(jié)點(diǎn)用葉節(jié)點(diǎn)來替代.悲觀剪枝(PEP,Pessimistic Error Pruning)方法采用自頂向下的剪枝策略,使它與其他方法相比效率更高、速度更快而被廣泛使用.

PEP為了提高對(duì)測(cè)試集合的預(yù)測(cè)可靠性,對(duì)誤差估計(jì)進(jìn)行了連續(xù)性校正.對(duì)于訓(xùn)練集數(shù)據(jù)生成的原始樹T,若

2 基于C4.5決策樹的在線學(xué)習(xí)行為分析方法

本文所使用的數(shù)據(jù)來自于新鄉(xiāng)醫(yī)學(xué)院網(wǎng)絡(luò)教學(xué)綜合平臺(tái)2014年《計(jì)算機(jī)基礎(chǔ)》課程所采集的學(xué)生在線學(xué)習(xí)行為數(shù)據(jù),共1 200條.采用保持法隨機(jī)將此數(shù)據(jù)集的2/3作為訓(xùn)練數(shù)據(jù)集,其余的1/3作為測(cè)試數(shù)據(jù)集.應(yīng)用C4.5算法對(duì)學(xué)生在線學(xué)習(xí)行為數(shù)據(jù)進(jìn)行挖掘分析,找出學(xué)習(xí)行為與學(xué)習(xí)評(píng)價(jià)結(jié)果之間的聯(lián)系,生成表達(dá)式規(guī)則,構(gòu)建學(xué)習(xí)行為分析模型,以此來評(píng)估學(xué)生在線學(xué)習(xí)行為,評(píng)價(jià)模型如圖1所示.

圖1 學(xué)習(xí)行為分析模型Fig.1 Analysis model of learning behavior

2.1 學(xué)習(xí)行為特征數(shù)據(jù)的提取

新鄉(xiāng)醫(yī)學(xué)院所使用的網(wǎng)絡(luò)教學(xué)平臺(tái)為我們采集了學(xué)習(xí)者使用學(xué)習(xí)平臺(tái)產(chǎn)生的各種訪問及交互信息,如果所有行為數(shù)據(jù)均參與計(jì)算,將會(huì)大大降低分析的效率.考慮到課程特點(diǎn)及數(shù)據(jù)項(xiàng)之間存在依賴關(guān)系,選擇提取以下數(shù)據(jù)建立學(xué)習(xí)行為特征數(shù)據(jù)庫(kù):用戶識(shí)別(ID)、進(jìn)入課程次數(shù)(LOGS)、課程討論區(qū)發(fā)帖次數(shù)(POSTS)、閱讀課程教學(xué)材料次數(shù)(READS)、上交作業(yè)次數(shù)(WORKS)、在線時(shí)長(zhǎng)(TIME)、考試成績(jī)(GRADE),表1為部分輸入數(shù)據(jù).

表1 部分輸入數(shù)據(jù)Tab.1 Part of the input data

2.2 數(shù)據(jù)預(yù)處理

C4.5算法作為對(duì)ID3算法的改進(jìn),增加了將連續(xù)型屬性進(jìn)行離散化的功能:

(1)將節(jié)點(diǎn)上的數(shù)據(jù)樣本按照屬性的取值進(jìn)行排序,將該連續(xù)型屬性的最小值賦值給MIN,其最大值賦值給MAX;

(2)生成區(qū)間[MIN,MAX]中的N個(gè)等分?jǐn)帱c(diǎn),它們分別是

(3)分別計(jì)算把[MIN,Ai]和(Ai,MAX](i=1,2,...,N)作為區(qū)間值時(shí)的Gain值;

(4)選擇其中Gain值最大的分割閾值作為屬性Ak的最佳分割閾值,把屬性值設(shè)置為[MIN,Ak]和(Ak, MAX]兩個(gè)區(qū)間值.

上述連續(xù)型屬性進(jìn)行離散化的過程中,需要對(duì)所有劃分情況進(jìn)行預(yù)測(cè).當(dāng)訓(xùn)練集中連續(xù)型屬性數(shù)量較多且取值也較多時(shí),算法的計(jì)算量巨大,而影響了決策樹的生成效率.Fayyad等證明:無論用于學(xué)習(xí)的訓(xùn)練集中的數(shù)據(jù)有多少個(gè)類別,不管類別的分布如何,連續(xù)型屬性的最佳分割點(diǎn)總是在邊界點(diǎn)處[6].根據(jù)Fayyad的邊界點(diǎn)原理,姚亞夫等改進(jìn)了原有算法,只在連續(xù)屬性分界點(diǎn)處的少數(shù)幾個(gè)分割點(diǎn)中選擇最佳分割閾值[7],從而提升了C4.5算法處理連續(xù)屬性的性能,本文利用姚亞夫構(gòu)造的分類器將連續(xù)屬性進(jìn)行離散化預(yù)處理,得到待挖掘的輸入數(shù)據(jù).

2.3 生成決策樹及分類規(guī)則

生成決策樹的具體計(jì)算過程如下:

(1)依次計(jì)算每個(gè)屬性的信息增益以及信息增益率.

(2)選取信息增益率最大,且信息增量不低于所有屬性平均值的屬性作為測(cè)試屬性.從上述計(jì)算結(jié)果可知,READS屬性具有最高的信息增益率,以該屬性作為節(jié)點(diǎn),屬性的每一個(gè)分布引出一個(gè)分支,據(jù)此再劃分樣本.如果節(jié)點(diǎn)中所有樣本都在同一個(gè)類,則該節(jié)點(diǎn)成為樹葉.

(3)對(duì)劃分的每個(gè)子數(shù)據(jù)集遞歸執(zhí)行(1)-(2).當(dāng)子集中再無屬性可供劃分,或數(shù)據(jù)記錄在主屬性上的取值相同時(shí)停止,從而形成完全決策樹.

為避免決策樹“過擬合”問題,在已生成的決策樹上采用PEP方法進(jìn)行剪枝,得到最終的決策樹模型.從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每條路徑創(chuàng)建一條規(guī)則,以IF-THEN形式形成分類規(guī)則,將決策樹轉(zhuǎn)化為等價(jià)的規(guī)則集合.

2.4 模型正確性評(píng)估

構(gòu)建此模型的目的是對(duì)學(xué)生的在線學(xué)習(xí)行為進(jìn)行預(yù)測(cè)分析.因此,利用生成的分類模型進(jìn)行準(zhǔn)確性評(píng)估,對(duì)測(cè)試數(shù)據(jù)集中的未知數(shù)據(jù)進(jìn)行預(yù)測(cè),通過比較測(cè)試結(jié)果與實(shí)際情況相吻合的程度來判斷該決策樹是否有效.

用于測(cè)試的樣本數(shù)據(jù)集為400個(gè),使用構(gòu)建的分析模型對(duì)測(cè)試數(shù)據(jù)集進(jìn)行評(píng)估,得到的分類準(zhǔn)確率的結(jié)果如表2所示.通過對(duì)數(shù)據(jù)集的測(cè)試評(píng)估,總的預(yù)測(cè)分類正確率達(dá)到87.80%.檢測(cè)結(jié)果表明,利用C4.5算法進(jìn)行數(shù)據(jù)挖掘所得到學(xué)習(xí)行為分析模型對(duì)未來數(shù)據(jù)樣本的分類預(yù)測(cè)正確率能夠達(dá)到基本要求.

表2 測(cè)試數(shù)據(jù)集評(píng)估結(jié)果Tab.2 Evaluation results of test data set

3 小結(jié)

本文根據(jù)學(xué)生在線學(xué)習(xí)行為數(shù)據(jù)的特點(diǎn),使用決策樹分類方法中的C4.5算法進(jìn)行決策學(xué)習(xí)和規(guī)則提取,構(gòu)建了學(xué)習(xí)分析模型,預(yù)測(cè)學(xué)習(xí)結(jié)果.通過測(cè)試數(shù)據(jù)集的評(píng)估,得到了較為理想的分類準(zhǔn)確率,為進(jìn)一步研究在線學(xué)習(xí)分析技術(shù)提供了有效的方法和手段.

[1]JohnsonL,AdamsS,CumminsM.TheNMCHorizonReport:2013HigherEducationEdition[R].Austin,Texas:TheNewMediaConsortium.

[2]Siemens G.1stInternational conference on learning analytics and knowledge 2011[EB/OL].(2010-07-12)[2014-10-15]. https://tekri.athabascau.ca/analytics/about.

[3]Quinlan J R.Induction of decision trees[J].Machine Learning,1986,1:81-106.

[4]Thakur D,Markandaiah N,Raj D S.Re optimization of ID3 and C4.5 decision tree[C].International Conference on Computer and Communication Technology,2010:448-450.

[5]Kantardzic M.Data mining:Concepts models,and algorithms[M].New York:John Wiley and IEEE Press,2003:139-164.

[6]FayyadUM,IraniKB.Onthehandlingofcontinuous-valueattributesindecisiontreegeneration[J].MachineLearning,1992,8(1):87-102.

[7]姚亞夫,邢留濤.決策樹C4.5連續(xù)屬性分割閾值算法改進(jìn)及其應(yīng)用[J].中南大學(xué)學(xué)報(bào):自然科學(xué)版,2011,42(12):3772-3776.

（責(zé)任編輯：盧奇）

Behavior analysis of online learning based on the decision trees

WANG Shixia
(Department of Clinical Skills Training Centre,Xinxiang Medical University,Xinxiang 453003,China)

Along with the continuous popularization of online learning,online learning,like a treasure behavior,is hidden in the Network platform.A reasonable mining technology was need to discover and use it.Based on the characteristics of the decision tree like algorithm good data analysis ability and intuitive result display,the C4.5 algorithm was used to explore the historical data of students'online learning behavior and learning efficiency in this paper.In order to avoid the over fitting problem of the decision tree,the decision tree that has been generated using method of PEP was pruned,and construct learning analysis model.Finally,the test data was evaluated by using the established analytical model,and obtained the comparatively ideal classification forecast result.The establishment of the learning analysis model provides an effective method and means for the scientific and reasonable assessment of students'online learning behavior,but also provides a reference for teaching design and courseware development.

data mining;decision tree;C4.5;online learning behavior

TP393.08

：A

：1008-7516（2015）05-0067-04

10.3969/j.issn.1008-7516.2015.05.014

2015-07-06

河南省教育廳人文社會(huì)科學(xué)研究項(xiàng)目(2015-GH-089)

王士霞(1977-),女,河南新鄉(xiāng)人,實(shí)驗(yàn)師.主要從事數(shù)據(jù)挖掘與分析研究.