決策樹算法在實(shí)踐教學(xué)中的應(yīng)用研究?

陰亞芳 孫朝陽(yáng)

1 引言

近年來(lái)，數(shù)據(jù)挖掘技術(shù)是學(xué)術(shù)界關(guān)注的一個(gè)熱點(diǎn)領(lǐng)域，決策樹算法作為數(shù)據(jù)挖掘中一個(gè)經(jīng)典算法，因?yàn)槠漭敵鼋Y(jié)果易于解釋和理解［1］，已被廣泛地應(yīng)用到教學(xué)管理、科學(xué)實(shí)驗(yàn)、金融業(yè)和商業(yè)決策等各個(gè)領(lǐng)域。西安郵電大學(xué)為使畢業(yè)生能夠適應(yīng)信息化社會(huì)不斷發(fā)展的要求，不斷地探索提高實(shí)踐課程教學(xué)效果的路徑。本文采用數(shù)據(jù)挖掘技術(shù)，以西安郵電大學(xué)2015-2016-02學(xué)期數(shù)字邏輯電路實(shí)驗(yàn)課的調(diào)查數(shù)據(jù)為樣本，借助weka數(shù)據(jù)挖掘工具，建立決策樹模型，提取分類規(guī)則，挖掘出出重要的教學(xué)指導(dǎo)意見，為我校改善實(shí)踐課程教學(xué)效果尋找更加科學(xué)的方法，使教學(xué)管理工作不再僅僅基于經(jīng)驗(yàn)和直覺，而是基于數(shù)據(jù)和分析做出的決策。

2 決策樹算法

2.1 決策樹算法的介紹

發(fā)展到今天，決策樹分類算法已經(jīng)有很多，比較著名的有ID3算法、C4.5算法、CART算法、CHAID算法等，ID3是所有決策樹算法的基礎(chǔ)，由Quinlan于1986年提出［2］，該算法采用信息增益作為屬性度量的標(biāo)準(zhǔn)。Quinlan在ID3算法的基礎(chǔ)上做了改進(jìn)，于1993年又提出了C4.5算法［3］，C4.5算法相對(duì)于ID3算法主要的優(yōu)點(diǎn)有：采用信息增益率作為屬性度量的標(biāo)準(zhǔn)，克服了ID3算法容易偏向于取值較多的候選屬性的不足，并且可以對(duì)連續(xù)型的屬性值進(jìn)行分類處理等［4］。

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

設(shè)樣本數(shù)據(jù)集T有m個(gè)類別，T={t1,t2,…tm}，訓(xùn)練樣本中某個(gè)屬性A有n種取值，A={a1,a2,…an}，根據(jù)屬性A把訓(xùn)練樣本劃分為T'={t2',…,tn'}，可以求出訓(xùn)練樣本的信息期望為［5］

其中

屬性A對(duì)訓(xùn)練樣本劃分的信息熵為

其中表示樣本中包含類別tj的概率。

屬性A對(duì)訓(xùn)練樣本劃分的信息增益為

以上是ID3算法的核心理論，C4.5算法用信息增益率作為屬性度量的標(biāo)準(zhǔn)，屬性A信息增益率的表達(dá)方式為

同理計(jì)算出其他屬性的信息增益率，選擇信息增益率最大的屬性作為決策樹根節(jié)點(diǎn)，用同樣的方法遞歸下去，計(jì)算出各層的節(jié)點(diǎn)。

3 基于決策樹算法建立模型并提取分類規(guī)則

weka是一個(gè)開源的數(shù)據(jù)挖掘軟件，由懷卡托大學(xué)的weka小組用Java語(yǔ)言開發(fā)［6］，它集合了大量能承擔(dān)數(shù)據(jù)挖掘任務(wù)的機(jī)器學(xué)習(xí)算法，如分類分析、聚類分析、關(guān)聯(lián)分析等，并且在新的交互式界面上可視化，是現(xiàn)今最完備的數(shù)據(jù)挖掘工具之一［7］。因?yàn)镮D3和C4.5算法構(gòu)造決策樹的思路基本相同，所以我們僅以C4.5算法建立決策樹模型為例，運(yùn)用weka里的C4.5和ID3分類器對(duì)樣本分類預(yù)測(cè)，并計(jì)算出分類預(yù)測(cè)的準(zhǔn)確率，最后提取出“IF-THEN”分類規(guī)則［8］。

3.1 建立決策樹模型

數(shù)據(jù)來(lái)源是西安郵電大學(xué)2015-2016-02學(xué)期實(shí)踐課程的調(diào)查數(shù)據(jù)，因?yàn)槿５臄?shù)據(jù)量很大，包括各個(gè)學(xué)院，各門課程，所以選擇了電子工程學(xué)院具有代表性的必修實(shí)驗(yàn)課：數(shù)字邏輯電路實(shí)驗(yàn)課的調(diào)查數(shù)據(jù)，作為訓(xùn)練樣本。實(shí)踐課程調(diào)查表的數(shù)據(jù)結(jié)構(gòu)如表1所示。

表1 學(xué)情問卷調(diào)查指標(biāo)表

從表1中可以看出，“對(duì)該實(shí)驗(yàn)課”是教學(xué)效果評(píng)價(jià)的結(jié)果，即分類屬性，包括三個(gè)屬性值：A希望多開（簡(jiǎn)化為“甲”）、B保持現(xiàn)狀（簡(jiǎn)化為“乙”）、C建議燒開或取消（簡(jiǎn)化為“丙”）。與教學(xué)效果相關(guān)的八個(gè)因素（屬性）分別是：是否明確本實(shí)驗(yàn)?zāi)康模ê?jiǎn)化為“G1”）、是否預(yù)習(xí)本實(shí)驗(yàn)課（簡(jiǎn)化為“G2”）、完成本實(shí)驗(yàn)是否有困難（簡(jiǎn)化為“G3”）、對(duì)該課程是否有興趣（簡(jiǎn)化為“G4”）、能否及時(shí)提交實(shí)驗(yàn)報(bào)告（簡(jiǎn)化為“G5”）、覺得該實(shí)驗(yàn)是否有收獲（簡(jiǎn)化為“G6”）、是否滿意老師的指導(dǎo)（簡(jiǎn)化為“G7”）、是否滿意現(xiàn)有的實(shí)驗(yàn)（簡(jiǎn)化為“G8”），每個(gè)因素又對(duì)應(yīng)具體的評(píng)價(jià)內(nèi)容（屬性值），共有23個(gè)屬性值，這些評(píng)價(jià)內(nèi)容幾乎反映了教學(xué)工作中的各個(gè)細(xì)節(jié)，當(dāng)然學(xué)生進(jìn)行評(píng)價(jià)時(shí)，個(gè)別學(xué)生可能不想?yún)⑴c評(píng)價(jià)，或者隨意亂評(píng)，這就使數(shù)據(jù)樣本失去了客觀性和準(zhǔn)確性，造成了離群的數(shù)據(jù)。但這只是個(gè)別情況，絕大多數(shù)的學(xué)生還是會(huì)根據(jù)實(shí)際情況，給予客觀的評(píng)價(jià)，所以，得到的調(diào)查數(shù)據(jù)是客觀的、可靠的。

我們對(duì)數(shù)據(jù)進(jìn)行噪聲處理，再通過(guò)數(shù)據(jù)類型轉(zhuǎn)換，使之符合我們數(shù)據(jù)挖掘的要求。100個(gè)樣本數(shù)據(jù)中類“甲”38個(gè)樣本數(shù)，類“乙”36個(gè)，類“丙”26個(gè)，根據(jù)式（1）計(jì)算出分類屬性的信息期望

再依次計(jì)算樣本集中各個(gè)測(cè)試屬性的期望、熵、信息增益、信息增益率。

對(duì)于G1（是否明確本實(shí)驗(yàn)的目的）=“A”，共有44個(gè)樣本，類“甲”有15個(gè)，類“乙”有16個(gè)，類“丙”有13個(gè)。由式（1），可以得出G1=“A”的期望如下

同樣根據(jù)式（1），計(jì)算出G1=“B”、G1=“C”的期望為

由式（2）可以得出由G1的屬性值劃分S的信息熵

由式（3）可以得出由G1的屬性值劃分S的信息增益

由式（4）可以得出由G1的屬性值劃分S的信息增益率

按照上面步驟可以得出其他測(cè)試屬性的信息增益率分別為

Gainratio(G2)=0.037；Gainratio(G3)=0.004；

Gainratio(G4)=0.293；Gainratio(G5)=0.024；

Gainratio(G6)=0.032；Gainratio(G7)=0.005；

Gainratio(G8)=0.015。

比較上面8個(gè)測(cè)試屬性的信息增益率的值，可知G4的最大，依據(jù)C4.5算法屬性選擇度量的標(biāo)準(zhǔn)，我們選擇具有最大信息增益率的G4作為根節(jié)點(diǎn)，根據(jù)G4的3個(gè)屬性值，再依據(jù)上面產(chǎn)生根節(jié)點(diǎn)的方法計(jì)算出各個(gè)分支的下一層節(jié)點(diǎn)，這樣遞歸下去，直至每個(gè)分枝的節(jié)點(diǎn)都分裂完畢，停止樹的生長(zhǎng)［9］。為防止“過(guò)擬合”，對(duì)生成的樹進(jìn)行剪枝處理［10］，最終的決策樹模型如圖1所示。

圖1 基于C4.5建立的決策樹模型

由圖1可以看出位于最上面的根節(jié)點(diǎn)是“G4”屬性，從根節(jié)點(diǎn)開始，順著每個(gè)分支繼續(xù)向下，直到每一個(gè)葉節(jié)點(diǎn)，形成一條路徑，在路徑中，節(jié)點(diǎn)越靠上的屬性，其作用也就越重要。

3.2 模型評(píng)估

我們運(yùn)用weka里的C4.5（J48）和ID3分類器構(gòu)造決策樹模型，由于兩種算法的步驟一樣，這里我們僅把weka-C4.5生成的可視化模型［11］給出，如圖2所示。

與圖1比較，借助weka所生成的模型與我們采用C4.5算法所建立的模型完全吻合?；趙eka-C4.5輸出頁(yè)面中的Confusion Matrix矩陣如圖3所示。

圖2 基于weka-C4.5建立的決策樹模型

圖3 C4.5分類結(jié)果

矩陣第一行表示類別屬性為甲的樣本共有38個(gè)，被正確分類的有30個(gè)，8個(gè)被誤判為乙；第二行表示類別屬性為乙的樣本共有36個(gè)，有27個(gè)被正確分類，6個(gè)被誤判為甲，3個(gè)被誤判為丙；第三行表示類別屬性為丙的樣本總共有26個(gè)，有23個(gè)被正確分類，1個(gè)被誤判為甲，2個(gè)被誤判為乙；樣本被正確分類的比例為（30+27+23）/100=80%，對(duì)角線上的值越大，說(shuō)明決策樹模型分類預(yù)測(cè)得越好［12］?；趙eka-ID3輸出的Confusion Matrix矩陣如圖4所示，準(zhǔn)確率為（30+24+17）/100=71%。C4.5和ID3算法訓(xùn)練樣本的準(zhǔn)確率分別為80%和71%，所以采用C4.5算法能更好地為我們探索提高實(shí)踐課程的教學(xué)效果的路徑提供決策支持。

圖4 ID3分類結(jié)果

3.3 提取分類規(guī)則

為了更好地解釋和分析結(jié)果，結(jié)合圖1和圖2，我們可以提取出下面的分類規(guī)則：

規(guī)則一：IF G4=“A”AND G7=“A”THEN 類=“甲”。

規(guī)則二：IF G4=“A”AND G7=“B”THEN 類=“甲”。

規(guī)則三：IF G4=“A”AND G7=“C”THEN 類=“乙”。

規(guī)則四：IF G4=“B”AND G2=“A”AND G3=“A”THEN 類=“甲”。

規(guī)則五：IF G4=“B”AND G2=“A”AND G3=“B”ANDG5=“A”THEN 類=“丙”。

規(guī)則六：IF G4=“B”AND G2=“A”AND G3=“B”ANDG5=“A”THEN 類=“乙”。

規(guī)則七：IF G4=“B”AND G2=“A”AND G3=“B”ANDG5=“C”THEN 類=“乙”。

規(guī)則八：IF G4=“B”AND G2=“A”AND G3=“C”THEN 類=“乙”。

規(guī)則九：IF G4=“B”AND G2=“B”THEN 類=“乙”。

規(guī)則十：IF G4=“C”AND G2=“A”AND G5=“A”ANDG6=“A”THEN 類=“甲”。

規(guī)則十一：IF G4=“C”AND G2=“A”AND G5=“A”ANDG6=“B”THEN 類=“乙”。

規(guī)則十二：IF G4=“C”AND G2=“A”AND G5=“B”ANDG3=“A”ANDG7=“A”THEN 類=“乙”。

規(guī)則十三 IF G4=“C”AND G2=“A”AND G5=“B”ANDG3=“A”ANDG7=“B”THEN 類=“丙”。

規(guī)則十四：IF G4=“C”AND G2=“A”AND G5=“B”ANDG3=“B”ANDG1=“A”THEN 類=“乙”。

規(guī)則十五：IF G4=“C”AND G2=“A”AND G5=“B”ANDG3=“B”ANDG1=“B”THEN 類=“甲”。

規(guī)則十六：IF G4=“C”AND G2=“A”AND G5=“B”ANDG3=“C”THEN 類=“丙”。

規(guī)則十七：IF G4=“C”AND G2=“A”AND G5=“C”THEN 類=“丙”。

規(guī)則十八：IFG4=“C”AND G2=“B”THEN 類=“丙”。

4 結(jié)果分析

數(shù)據(jù)挖掘結(jié)果分析：在生成的決策樹模型圖中，節(jié)點(diǎn)越靠上，其作用也就越重要。最上面的根節(jié)點(diǎn)是G4，可見“對(duì)該實(shí)驗(yàn)課是否有興趣”這一屬性是學(xué)生對(duì)實(shí)踐課程教學(xué)效果評(píng)價(jià)的關(guān)鍵因素，結(jié)合圖1和表1我們可以得出如下結(jié)論：

1）對(duì)于G4=“A”這一分支，結(jié)合規(guī)則1～ 3可以看出，“是否滿意老師的指導(dǎo)”所占的作用次之，這兩個(gè)作用可以直接得出學(xué)生對(duì)課程的整體評(píng)價(jià)，所以，老師激發(fā)學(xué)生的學(xué)習(xí)興趣很重要，其次，在教學(xué)過(guò)程中，老師多收集學(xué)生對(duì)該課程的建議，及時(shí)改善教學(xué)內(nèi)容，這樣才能取得較滿意的教學(xué)效果。

2）對(duì)于G4=“B”這一分支，在圖1中，從上到下節(jié)點(diǎn)的順序是：G2、G3、G5，所以這三個(gè)因素的重要性依次為“預(yù)習(xí)實(shí)驗(yàn)”、“完成本實(shí)驗(yàn)是否有困難”，“能夠按時(shí)提交實(shí)驗(yàn)報(bào)告”，結(jié)合規(guī)則4～9可以看出，老師可以采取措施監(jiān)督學(xué)生完成實(shí)驗(yàn)預(yù)習(xí)，比如寫預(yù)習(xí)報(bào)告，然后設(shè)置難度適中的課后作業(yè)，保證學(xué)生按時(shí)提交實(shí)驗(yàn)報(bào)告，可以取得良好的教學(xué)效果。

3）對(duì)于G4=“C”這一分支，即對(duì)實(shí)驗(yàn)課沒有興趣，卻做課前預(yù)習(xí)的同學(xué)，結(jié)合圖1和規(guī)則10、11可以看出，“能否按時(shí)提交實(shí)驗(yàn)報(bào)告”，“覺得該實(shí)驗(yàn)是否有收獲”兩個(gè)因素對(duì)課程評(píng)價(jià)的也有一定的影響，由規(guī)則12～16，可以看出因素重要性的順序依次是：“能否及時(shí)提交實(shí)驗(yàn)報(bào)告”、“完成本實(shí)驗(yàn)是否有困難”，最后是“是否滿意老師的指導(dǎo)”和“是否明確實(shí)驗(yàn)?zāi)康摹?。?guī)則17表明：有13個(gè)學(xué)生做了預(yù)習(xí)，卻不交實(shí)驗(yàn)報(bào)告。

5 結(jié)語(yǔ)

用C4.5分類算法針對(duì)數(shù)字邏輯電路實(shí)踐課程調(diào)查數(shù)據(jù)建立決策樹模型，預(yù)測(cè)的準(zhǔn)確率為80%，得出的教學(xué)建議具有很大參考價(jià)值和可靠的理論依據(jù)，把決策樹算法與我們具體的調(diào)查數(shù)據(jù)相結(jié)合，不僅可以進(jìn)行分類預(yù)測(cè)，也可以發(fā)現(xiàn)新的問題，比如規(guī)則17表明，有13個(gè)學(xué)生做了預(yù)習(xí)卻不交實(shí)驗(yàn)報(bào)告，這不是小數(shù)目，應(yīng)該引起我們的注意，很可能是實(shí)驗(yàn)內(nèi)容不夠豐富，實(shí)驗(yàn)有難度，還可以通過(guò)和學(xué)生面對(duì)面的談話，來(lái)了解具體原因，從而為我們的實(shí)踐教學(xué)提供決策支持。但是我們對(duì)決策樹的應(yīng)用研究還是比較淺的，比如形成的分類規(guī)則中，哪些規(guī)則是比較重要的，遇到更復(fù)雜類型的數(shù)據(jù)怎么改進(jìn)等等，需要我們做更深的研究。

［1］張棪，曹健.面向大數(shù)據(jù)分析的決策樹算法［J］.計(jì)算機(jī)科學(xué)，2016，43（z1）：1.

ZHANGYan，CAOJian.Decision Tree Algorithms for Big Data Analysis［J］.Computer Science，2016，43（z1）：1.

［2］李麗芳.學(xué)生評(píng)教數(shù)據(jù)知識(shí)挖掘方法應(yīng)用研究［D］.廣州：華南理工大學(xué)，2015.

LI Lifang.The Application Research of Knowledge Mining Algorithm Based on the Teaching Data of Student'Evaluation［D］.Guangzhou：South China University Of Technology，2015.

［3］范明，孟小峰.數(shù)據(jù)挖掘概念與技術(shù)［M］.第3版.北京：機(jī)械工業(yè)出版社，2012：76-77.

FAN Ming，MENG Xiaofeng.Data Mining Concepts and Techniques Third Edition［M］.Beijing：Machine Press，2012：76-77.

［4］譚俊璐，武建華.基于決策樹規(guī)則的分類算法研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（5）：1-2.

TAN Junlu，WU Jianhua.Classification algorithm of rule based on decision-tree［J］.Computer Engineering and Desing，2010，31（5）：1-2.

［5］周劍鋒，陽(yáng)愛民，劉吉財(cái).基于改進(jìn)的C4.5算法的網(wǎng)絡(luò)流量分類算法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（5）：71-74.

ZHOU Jianfeng，YANG Aimin，LIU Jicai.Traffic classification approach based on improved C4.5 algorithm［J］.Computer Engineering and Applications，2012，48（5）：71-74.

［6］Bramer M.Principles of Date Mining［M］.London Springer，2013：121-136.

［7］姚亞夫，邢留濤.決策樹C4.5連續(xù)屬性分割閾值算法改進(jìn)及應(yīng)用［J］.中南大學(xué)學(xué)報(bào)，2011，42（12）：3772-3776.

YAO Yafu，XING Liutao.Improvement of C4.5 decision tree continuous attributes segmentation threshold algorithm and its application［J］.Journal of Central South University of Technology，2011，42（12）：3772-3776.

［8］李孝偉，陳福才，李紹梅.基于分類規(guī)則的C4.5決策樹改進(jìn)算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（12）：4321-4325.

LIXiaowei，CHENFucai，LIShaomei.Improved C4.5 decision tree algorithm based on classification rules［J］.Computer Engineering and Design，2013，34（12）：4321-4325.

［9］劉鵬，姚正，尹俊杰.一種有效的C4.5改進(jìn)模型［J］.清華大學(xué)學(xué)報(bào)，2006，46（S1）：996-1001.

LIU Peng，YAO Zheng，YIN Junjie.Improved decision tree of C4.5［J］.Tsinghua Science and Technology，2006，46（S1）：996-1001.

［10］Thakur D，Markandaiah N，Raj D S.Re optimization of ID3 and C4.5 decision tree［C］//International Conference on Computer and Communication Tecnology，2010：448-450.

［11］楊哲，李領(lǐng)治，紀(jì)其進(jìn)，等.基于最短劃分距離的網(wǎng)絡(luò)流量決策樹分類方法［J］.通信學(xué)報(bào)，2012，33（3）：90-102.

YANG Zhe，LI Lingzhi，JI Qijin，et al.Network traffic classification using decision tree based on minimum partition distance［J］.Journal of Communication，2012，33（3）：90-102.

［12］Aggarwal C C，Reddy C K.Data Classification：Algorithms and Application［C］//CRCPress，2014：43-44.