王士霞

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

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

王士霞

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

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

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

隨著網(wǎng)絡(luò)開(kāi)放課程的普及和學(xué)習(xí)技術(shù)系統(tǒng)的發(fā)展,在線學(xué)習(xí)行為越來(lái)越多地發(fā)生在各種教育情境中,也給我們帶來(lái)了大量的學(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ù)被排在未來(lái)五年內(nèi)影響高等教育的六大信息技術(shù)的第一位[2].如何構(gòu)造高效的數(shù)據(jù)挖掘算法去發(fā)現(xiàn)和理解隱藏在數(shù)據(jù)背后的信息,成為學(xué)習(xí)分析技術(shù)中成為最核心的問(wèn)題.

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

1 C4.5決策樹(shù)算法

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

1.1 C4.5決策樹(shù)的建立

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

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

1.2 C4.5決策樹(shù)的剪枝

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

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

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

本文所使用的數(shù)據(jù)來(lái)自于新鄉(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í)行為分析模型,以此來(lái)評(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)生的各種訪問(wè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)行離散化的過(guò)程中,需要對(duì)所有劃分情況進(jìn)行預(yù)測(cè).當(dāng)訓(xùn)練集中連續(xù)型屬性數(shù)量較多且取值也較多時(shí),算法的計(jì)算量巨大,而影響了決策樹(shù)的生成效率.Fayyad等證明:無(wú)論用于學(xué)習(xí)的訓(xùn)練集中的數(shù)據(jù)有多少個(gè)類(lèi)別,不管類(lèi)別的分布如何,連續(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)造的分類(lèi)器將連續(xù)屬性進(jìn)行離散化預(yù)處理,得到待挖掘的輸入數(shù)據(jù).

2.3 生成決策樹(shù)及分類(lèi)規(guī)則

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

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

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

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

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

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

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

用于測(cè)試的樣本數(shù)據(jù)集為400個(gè),使用構(gòu)建的分析模型對(duì)測(cè)試數(shù)據(jù)集進(jìn)行評(píng)估,得到的分類(lèi)準(zhǔn)確率的結(jié)果如表2所示.通過(guò)對(duì)數(shù)據(jù)集的測(cè)試評(píng)估,總的預(yù)測(cè)分類(lèi)正確率達(dá)到87.80%.檢測(cè)結(jié)果表明,利用C4.5算法進(jìn)行數(shù)據(jù)挖掘所得到學(xué)習(xí)行為分析模型對(duì)未來(lái)數(shù)據(jù)樣本的分類(lèi)預(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),使用決策樹(shù)分類(lèi)方法中的C4.5算法進(jìn)行決策學(xué)習(xí)和規(guī)則提取,構(gòu)建了學(xué)習(xí)分析模型,預(yù)測(cè)學(xué)習(xí)結(jié)果.通過(guò)測(cè)試數(shù)據(jù)集的評(píng)估,得到了較為理想的分類(lèi)準(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]姚亞夫,邢留濤.決策樹(shù)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ù)挖掘與分析研究.