決策樹C4.5算法分析及其在多媒體網絡教學評價中的應用

王新華,焦玉琳,馮先強

(1.商丘職業技術學院,河南 商丘 476000; 2.武漢理工大學,湖北 武漢 410076)

決策樹C4.5算法分析及其在多媒體網絡教學評價中的應用

王新華1,2,焦玉琳1,馮先強1

(1.商丘職業技術學院,河南 商丘 476000; 2.武漢理工大學,湖北 武漢 410076)

C4.5算法是決策樹學習的核心算法,與ID3算法相比, C4.5算法是ID3算法的改進,并繼承了ID3算法的全部優點,文章給出了決策樹構造思想和C4.5決策樹學習算法,并將其應用于多媒體網絡教學評價之中,采用C4.5決策樹算法對教學評價數據進行預處理,選取決策屬性,實現挖掘算法并抽取規則知識,C4.5算法能夠更好地修正ID3的剪枝算法,并將多媒體網絡教學評價進行分類,算法簡單且生成速度快,通過生成的決策樹,生成可理解的規則.

決策樹;C4.5；多媒體；網絡教學；評價

近幾年國內外，數據挖掘廣闊的應用前景得到了商業圈及眾多學者的認可，在信息產業界也引起了振蕩，通過數據挖掘將有大量的數據轉換為專用的信息.數據挖掘根據模式的作用可分為分類、回歸、聚類、時間、序列等.分類在數據分析方法中是最重要的，解決的方法也很多，其中決策樹是最深入的、應用最廣泛的方法之一[1]56.

在當今互聯網時代，多媒體網絡教學已應用十分廣泛，但多媒體網絡教學評價的研究有所滯后，對多媒體進行網絡教學評價中科學、客觀、準確的總結不足[2]46.多媒體網絡教學評價具有一定的復雜性、模糊性及多因素性，如何正確地反映出問題，總結出優勢是當前的迫切任務和課題.本文利用決策樹C4.5算法，對數據進行挖掘來研究多媒體網絡教學的評價問題.

1 數據挖掘決策樹算法

在數據挖掘方法中，決策樹算法是解決實際問題的常用方法之一，在數據挖掘模式中，分類是把數據項映射到一個定義類的過程，由相應的類和輸入的屬性值向量構成.分類器是一個在其他屬性已知的樣本下預測另一個屬性的模型[3]87-90.

在數據中來生成分類器最有效的方法是生成決策樹.而生成決策樹的算法主要有6種，即ID3算法、C4.5算法、算法IBLE算法、CHAID算法、Cs算法、CART(分類與回歸樹)[4]46-50.C4.5算法是一種簡而易懂的決策樹算法，它是在ID3的基礎上進行一定的完善，彌補了ID3中的不足，采用了信息增益率來作為屬性選擇的衡量標準，進行決策節點屬性的選擇，但算法的基本方法與工作流相同，這也是決策樹算法的基本思想[5]125-126.

決策屬性信息增益算法在C4.5中：

設事例樣本類標號Ci，i=i,…,n,事例集合為T，則信息熵為：

|T|—帶表事例集T的樣本個數，frequ(Ci,T)—表示事例集合T中事例屬于類Ci的數目.

假設選擇y個不同值的屬性w，則條件熵可表示為：

|Ti|—基于屬性w的某個值的子樹中每一類例子的數目.

則信患增益即互信息為:

Gain(W)=info(T)-Ew

C4.5采用標準化處理程序中，當有很多不同屬性值，采用啟發式搜索方法最有效，信息增益率(gainratio)方法具有更好的信息增益的屬性[6]946-948.但也會導致最大信息增益gain屬性W作為擴展屬性來分枝.信息增益率被定義為：

式中

是利用屬性W的值對數據進行挖掘，分枝計算出潛在信息.

在選擇相應的錯誤率上C4.5采用了信息增益率作為分枝準則.信息增益率與分支產生的有用信息成正比.分枝包中含有的信息越多，信息增益率越大.

2 樹修剪

基本的決策樹算法是沒有去噪聲的，構造生成的決策樹完全同訓練樣本相同.修剪的核心技術就是克服噪聲，使決策樹簡單易理解.

決策樹采用分而治之策略, 自上而下的生成過程, 與此同時降低算法的時間復雜度, 忽視各類樣本的總體分布對噪聲的敏感性.可以非常準確地反映一個完整的決策樹訓練樣本數據集的特征數據[7]39-42.

但是,不能用于新數據的分類和預測,會出現過匹配或過時適應數據.當這個模型應用到新的測試集將導致不準確的預測，所以一個完整的決策樹結構還應該包括決策樹剪枝.決策樹剪枝就是避免決策樹過度擬合.

樹修剪有兩種常用的修剪方法:

1)預剪枝：就是指預先確定最大深度的決策樹生長，過大過小都會抑制它的生長，同時也無法實現新數據的預測或準確分類.

2)后剪枝：即在充分生長的基礎上允許決策樹在T規則下,剪去沒有代表性的分枝或葉節點.根據檢測和訓練樣本集對目標變量精度進行計算修剪[8]20-21.

3 決策樹C4.5算法

將多媒體網絡教學評價分為6項體系指標，即J1(教學方法)、J2(教學態度)、J3(教學質量)、J4(教學效益)、J5(教學效率)、J6(教學評價).如表1所示.A代表評分為90～100，B代表評分為80～89，C代表評分為70～79，D代表60～69，E代表評分小于60分，F代表評分小于40分，J6為結論.

表1 多媒體網絡教學評價指標體系

訓練樣本數據集S中，共有10個元組，有6個類別分別是優秀、良好、中等、一般、較差、非常差，對多媒體網絡教學評價方法，采用數據挖掘是為了使教學水平得到提高，這里我們選用優、良、中、及格進行分析，此4個對應類別的子集元素個數分別為：r1=4,r2=2,r3=3,r4=1.

為計算決策屬性信息增益，這里先計算期望信息量：

則單個期望信息量計算：

以J1為例：

E(SA)=0.9183

E(SB)=1.5

E(SC)=0

E(SD)=1

Gain(S,J1)=I(r1,r2,r3,r4)-E(S,J1)=1.8465-1.0755=0.771

因此,屬性J1的信息增益率為

Ratio(J1)=Gain(J1)/E(S,J1)=0.771/1.0755=0.7169

同理可得:

Ratio(J2)=Gain(J2)/E(S,J2)=1.0465/0.8=1.3081

Ratio(J3)=Gain(J3)/E(S,J3)=0.8465/1=0.8645

Ratio(J4)=Gain(J4)/E(S,J4)=0.9135/0.9510=0.9606

Ratio(J5)=Gain(J5)/E(S,J5)=0.989/0.8755=1.1296

由上述計算結果可知J2屬性中具有最大的信息增益比.最后所構造的判定樹如圖1所示.

4 決策結論描述

由圖1所得C4.5算法構造多媒體網絡教學評價決策樹，可方便快捷地提取決策樹描述從根節點到葉節點所有路徑都對應相應的決策規則.

描述如下所示:

1)if(A2=C)thenA6=中等

2)if(A2=D)thenA6=及格

3)if(A2=A&&A3=A)thenA6=優秀

4)if(A2=A&&A3=B&&A4=B)thenA6=良好

5)if(A2=A&&A3=B&&A4=A)thenA6=優秀

6)if(A2=B&&A3=A)thenA6=優秀

7)if(A2=B&&A3=B)thenA6=良好

8)if(A2=B&&A3=C)thenA6=中等

5 結論

決策樹是數據挖掘中一個常用的算法工具,數據挖掘是一種新的數據分析技術,本文研究了分類方法中常見的C4.5決策樹算法,C4.5算法是在ID3的基礎上改進而成的,它更好地修正了ID3的剪枝算法,并對高分支屬性、數值型屬性和含空缺值屬性的整理有了系統的描述,C4.5決策樹算法簡單而且生成速度也比較快,通過生成的決策樹,可以生成可理解的規則.在決策樹中可以大致地判斷出屬性之間的相對重要性.決策樹C4.5算法分析應用在多媒體網絡教學評價中，將更好地為網絡教學服務，科學客觀地評價，使多媒體網絡教學評價技術更上一個臺階.

[1] Han Jiawei,Kanber Micheline .數據挖掘概念與技術[M].北京:機械工業出版社,2002.

[2] 戴 南.基于決策樹的分類方法研究[D].南京:南京師范大學,2003.

[3] 李雄飛,李 軍.數據挖掘與知識發現[M].北京:高等教育出版社,2003.

[4] 張云濤,龔 玲.數據挖掘原理與技術[M].北京:電子工業出版社,2000.

[5] 王中輝,魯來鳳.決策樹在教學評價中的應用[J].甘肅科技，2006(3).

[6] 范 潔,楊岳湘,溫 璞.C4.5算法在在線學習行為評估系統中的應用[J].計算機工程與設計，2006(3).

[7] 彭松波,何文秀.決策樹在高校就業管理系統中的應用研究[J].中原工學院學報，2006(8).

[8] 谷 瓊,朱 莉,蔡之華,袁紅星.基于決策樹技術的高校研究生信息庫數據挖掘研究[J].電子技術應用，2005(7).

[責任編輯 冰 竹]

Decision-Tree C4.5 Algorithm Analysis and Its Application in Multimedia Network Teaching Appraisal

WANG Xinhua1，2, JIAO Yulin1, FENG Xianqiang1

(1.ShangqiuPolytechnic,Shangqiu476000,China;2.WuhanUniversityofTechnology,Wuhan430063,China)

The C4.5 algorithm is the decision tree study core algorithm. Compared with ID3 algorithm, C4.5 algorithm is an improved ID3 algorithm, and it inherited the entire ID3 algorithm's merit. This article has given the decision tree structure thought and the C4.5 decision tree study algorithm, and applies it during the multimedia network teaching appraisal. The paper uses the C4.5 decision tree algorithm to preprocess the data and chooses the decision attributes first, then draws the rules, which shows that what attributes determine the classification of the multimedia network teaching appraisal. The results of data mining indicate that the algorithm can classify the teaching appraisal data properly and get some valuable information for decision making.

decision-tree; C4.5; multimedia; network teaching; appraisal

2015-09-07

河南省重大科技攻關計劃項目(項目編號：142102110028)

王新華(1970- ),男,河南商丘人，商丘職業技術學院副教授，在讀博士，主要從事智能控制與節能技術研究。

1671-8127(2015)05-0016-04

TP18

A