鄭秀月

（福州黎明職業(yè)技術(shù)學(xué)院,福建 福州 350001）

1 C4.5算法介紹

C4.5算法是決策樹技術(shù)中較為典型的、應(yīng)用廣泛的分類算法，是ID3算法的提出者J.R Quinlan根據(jù)ID3算法存在的一些問題提出的一種改進算法[1]。C4.5不僅具備ID3算法的所有優(yōu)點，還可以處理離散類型、連續(xù)類型的屬性；在生成決策樹時，可以采用邊構(gòu)造樹邊剪枝或者完整的樹生成之后再進行剪枝的策略，也可以采用不同的剪枝技術(shù)如刪除子樹或結(jié)點的方法來避免生成不平衡的樹[2]。

2 C4.5算法的改進

2.1 C4.5算法的不足

C4.5算法中，在生成決策樹的過程中需要花大量的時間進行信息增長率的運算，對決策樹的生成效率產(chǎn)生了很大的影響。它與ID3算法一樣仍然是基于“貪心”策略的搜索方式，通過找到每棵子樹的最優(yōu)解，然后構(gòu)造出一棵完整的決策樹，這樣只能保證子樹是最優(yōu)的，最后生成的決策樹未必能達到整體最優(yōu)。

2.2 C4.5算法的改進

在C4.5算法中，計算分類及測試屬性的信息量時，涉及了對數(shù)運算，在進行數(shù)據(jù)挖掘時要反復(fù)地調(diào)用對數(shù)庫函數(shù)，造成計算復(fù)雜度大，時間成本高等問題。這里，針對信息量的計算方法提出了改進措施。

假設(shè)在樣本數(shù)據(jù)中，類“YES”的有m個，類“NO”的有n個，則該樣本分類屬性的信息量計算方法如公式(1-1)所示。

以A為測試屬性，假設(shè)A有p個不同的取值，則它的信息量計算方法如公式(1-2)所示。

根據(jù)高等數(shù)學(xué)中的泰勒公式、麥克勞林公式和等價無窮小的思想，可以知道當(dāng)x很小時，ln(1+x)≈x，因此可以得出如下公式(1-3)和公式(1-4)所示。

將公式(1-3)和(1-4)代入公式(1-2)可得如下公式(1-5)所示。

計算時，將公式(1-5)中的常數(shù)省略，得出如下公式(1-6)所示。

又因為屬性A對D的分裂信息量計算方法如公式(1-7)所示。

因此可以得出信息增益率如下公式 (1-8)所示。

3 利用改進的C4.5算法生成計算機等級考試成績的決策樹模型

3.1 確定數(shù)據(jù)挖掘?qū)ο蠛湍繕?/h3>

以福州某職業(yè)院校2019～2020學(xué)年計算機二級等級考試成績?yōu)檠芯繉ο?，隨機抽取了1 100名學(xué)生的成績。同時設(shè)計了一份問卷調(diào)查。希望對這兩份表格的分析挖掘，從中找出影響學(xué)生成績的因素，對今后教學(xué)工作的開展起到積極的指導(dǎo)作用。

3.2 數(shù)據(jù)采集

共收集了3張表格數(shù)據(jù)，分別為學(xué)生成績表、平時作業(yè)情況表和問卷調(diào)查表。其中學(xué)生成績表由準考證號、姓名、性別和成績等字段組成，數(shù)據(jù)由學(xué)院的教務(wù)處提供，成績?yōu)橛嬎銠C二級等級考試成績。平時作業(yè)完成情況表由準考證號、姓名、性別和平時上機作業(yè)完成情況等字段組成，數(shù)據(jù)由任課教師根據(jù)學(xué)生平時完成實驗的情況給出的統(tǒng)計表。問卷調(diào)查表由準考證號、姓名、對該門課程的興趣度、原有知識水平程度和課后復(fù)習(xí)鞏固時間等字段組成。

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

上述所收集的數(shù)據(jù)如果直接用于挖掘工作，會直接影響挖掘的結(jié)果，因此要對收集到的原始數(shù)據(jù)進行數(shù)據(jù)清理、數(shù)據(jù)表合成、數(shù)據(jù)轉(zhuǎn)換和數(shù)據(jù)降維等預(yù)處理。在數(shù)據(jù)轉(zhuǎn)換中將連續(xù)型的成績數(shù)據(jù)轉(zhuǎn)換為離散型的數(shù)據(jù)類型，將“成績”一欄用“是否通過”來標識，結(jié)果顯示“通過”或“未通過”。在數(shù)據(jù)降維中刪除對挖掘結(jié)果不產(chǎn)生影響的字段“姓名”和“性別”，保留能唯一標識一條記錄的字段“準考證號”即可。預(yù)處理后最終生成的數(shù)據(jù)表如下表1-1所示。

3.4 構(gòu)造成績“未通過”的決策樹模型

為了找出影響學(xué)生計算機等級二級考試成績不及格的因素，因此將表1-1中的成績“未通過”的記錄提取出來組成新的表格來建立決策樹：

表1 -1 學(xué)生成績分析表

3.4.1 計算每個屬性的信息量

在成績“未通過”的學(xué)生成績分析表，與“未通過”相關(guān)的屬性有“對該門課程的興趣度”、“原有知識水平程度”“平時上機作業(yè)完成情況”和“課后復(fù)習(xí)鞏固時間”。根據(jù)公式1-6分別求出每個屬性的信息量。

（1）計算屬性“對該門課程的興趣度”的信息量，該屬性共有三個屬性值，分別為“感興趣”“不感興趣”和“一般”，其樣本數(shù)分別為：“感興趣”的有305個，“不感興趣”的有245個，“一般”的有400個。

“感興趣”的305個樣本中，類“YES”的有215個，類“NO”的有90個，可以表示為（215，90），其信息量：

同理計算“不感興趣”的245個樣本中，其信息量info(0,245)=0；

“一般”的400個樣本中，其信息量info(175,225)=98.4375；

因此，屬性“對該門課程的興趣度”的信息量

info(興趣度,D)=63.443+98.4375=161.8805

（2）計算屬性“課后復(fù)習(xí)鞏固時間”的信息量，該屬性“大于2小時”“1-2小時”和“小于1小時”對應(yīng)的樣本數(shù)分別為165、340和445，分別計算他們的信息量為info(45,400)=40.449、info(200,140)=82.353、info(145,20)=17.576；

因此，屬性“課后復(fù)習(xí)鞏固時間”的信息量為：40.449+82.353+17.576=140.378

（3）計算屬性“原有知識水平程度”的信息量，該屬性共有三個屬性值，其對應(yīng)的樣本數(shù)分別為：“好”的有275個，“中”的有395個，“差”的有280個，分別計算他們的信息量為info(205,70)=52.182、info(160,235)=95.190、info(25,255)=22.77；

因此，屬性“原有知識水平程度”的信息量為：52.182+95.190+22.77=170.142

（4）計算屬性“平時上機作業(yè)完成情況”的信息量，該屬性共有三個值，其對應(yīng)的樣本數(shù)分別為：“優(yōu)”的有305個，“良”的有330個，“差”的有315個。別計算他們的信息量為info(290,15)=14.26、info(100,230)=69.697、info(2,315)=1.9873

因此，屬性“平時上機完成情況”的信息量為：14.26+69.697+1.9873=85.9443

3.4.2 根據(jù)公式1-7計算每個屬性的分裂信息量

屬性“對該門課程的興趣度”的分裂信息量為：

依次分別算出屬性“課后復(fù)習(xí)鞏固時間”“原有知識水平程度”“平時上機作業(yè)完成情況”的分裂信息量分別為：26278.421、32015.789、33373.421。

3.4.3 根據(jù)公式1-8計算各屬性的信息增益率

屬性“對該門課程的興趣度”的信息增益率為：

依次分別算出屬性“課后復(fù)習(xí)鞏固時間”“原有知識水平程度”“平時上機作業(yè)完成情況”的信息增益率分別為：0.99465、0.99468、0.99742。

3.4.4 選取信息增益率最大的屬性作為決策樹的根結(jié)點

綜上所述，“平時上機作業(yè)完成情況”屬性具有最大的信息增益率。因此將其作為測試屬性，用“平時作業(yè)”來標識，并對每個屬性值建立分支生成的決策樹。同理，對于各個分支節(jié)點用以上的方法進一步進行劃分，生成完整的決策樹

3.5 決策樹的剪枝

決策樹的剪枝，就是在單個葉子結(jié)點的期望錯誤率低于相應(yīng)子樹結(jié)點的期望錯誤率時，用該葉子結(jié)點來代替一整棵子樹[3]。目前，常用的決策樹剪枝算法主要有兩種即先剪枝方法和后剪枝方法[4]，對上述已生成的完整決策樹模型采用了“后剪枝”的方法，通過剪枝后生成的決策樹如下圖1所示。

圖1 決策樹

3.6 生成規(guī)則

決策樹算法很重要的一個優(yōu)點就是能夠直接生成以IF……THEN……語句的形式表示的規(guī)則，而且這種形式表示的規(guī)則易于被人們理解和接受[5]。從上面決策樹中提取的成績?yōu)椤拔赐ㄟ^”的規(guī)則有：

IF“平時作業(yè)”=“優(yōu)”AND“復(fù)習(xí)時間”=“小于1”AND“原有知識程度”=“中”AND“興趣度”=“一般”THEN“成績是否通過”=“未通過”；

IF“平時作業(yè)”=“優(yōu)”AND“復(fù)習(xí)時間”=“小于1”AND“原有知識程度”=“差”AND“興趣度”=“一般”THEN“成績是否通過”=“未通過”；

IF“平時作業(yè)”=“良”AND“原有知識程度”=“中”AND“興趣度”=“一般”AND“復(fù)習(xí)時間”=“小于1”THEN“成績是否通過”=“未通過”；

IF“平時作業(yè)”=“良”AND“原有知識程度”=“中”AND“興趣度”=“不感興趣”AND“復(fù)習(xí)時間”=“小于1”THEN“成績是否通過”=“未通過”；

IF“平時作業(yè)”=“良”AND“原有知識程度”=“中”AND“興趣度”=“不感興趣”AND“復(fù)習(xí)時間”=“大于1小于2”THEN“成績是否通過”=“未通過”；

IF“平時作業(yè)”=“差”THEN“成績是否通過”=“未通過”；

IF“平時作業(yè)”=“良”AND“原有知識程度”=“差”THEN“成績是否通過”=“未通過”；

從以上得出的分類規(guī)則可以看出，“平時上機作業(yè)完成情況”對考試是否通過影響很大?！罢n后復(fù)習(xí)鞏固時間”也在很大程度上影響著考試是否通過。因此，教師在教學(xué)過程中要注重學(xué)生的實際動手能力，對學(xué)生“平時上機作業(yè)完成情況”要即時的進行講評、反饋，即時解決學(xué)生在上機過程中遇到各種問題。同時要督促學(xué)生課后多花時間進行復(fù)習(xí)鞏固，加深印象，以此來提高等級考試的通過率。

3.7 挖掘結(jié)果的評估

將以上生成的學(xué)生成績是否通過的決策樹模型應(yīng)用于預(yù)留的用于測試的90條記錄，發(fā)現(xiàn)90條記錄中，利用圖3-1的決策樹對學(xué)生成績是否通過進行預(yù)測，發(fā)現(xiàn)錯誤的條數(shù)為5條，即正確率達到了94.4 %。同理分別對19級計算機專業(yè)和19級藝術(shù)設(shè)計專業(yè)的成績進行測試，正確率分別達到了93.2 %和95.2 %。

經(jīng)過測試，發(fā)現(xiàn)以上所生成的決策樹模型效果良好。

4 結(jié)語

本文主要運用改進的C4.5算法建立了學(xué)生成績是否通過的決策樹模型，產(chǎn)生分類規(guī)則并對挖掘結(jié)果進行了評價，分析了影響國家計算機二級等級考試通過率低的因素，以幫助教師更好地進行教學(xué)活動，提高等級考試的通過率。