C4.5算法在計(jì)算機(jī)等級(jí)考試管理中的應(yīng)用

鄭秀月

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

1 C4.5算法介紹

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

2 C4.5算法的改進(jìn)

2.1 C4.5算法的不足

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

2.2 C4.5算法的改進(jìn)

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

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

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

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

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

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

又因?yàn)閷傩訟對(duì)D的分裂信息量計(jì)算方法如公式(1-7)所示。

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

3 利用改進(jìn)的C4.5算法生成計(jì)算機(jī)等級(jí)考試成績(jī)的決策樹(shù)模型

3.1 確定數(shù)據(jù)挖掘?qū)ο蠛湍繕?biāo)

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

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

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

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

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

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

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

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

3.4.1 計(jì)算每個(gè)屬性的信息量

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.5 決策樹(shù)的剪枝

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

圖1 決策樹(shù)

3.6 生成規(guī)則

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

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

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

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

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

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

IF“平時(shí)作業(yè)”=“差”THEN“成績(jī)是否通過(guò)”=“未通過(guò)”；

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

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

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

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

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

4 結(jié)語(yǔ)

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