C4.5算法在高校計(jì)算機(jī)等級(jí)考試成績分析中的研究

程代娣（安徽警官職業(yè)學(xué)院，安徽合肥230031）

?

C4.5算法在高校計(jì)算機(jī)等級(jí)考試成績分析中的研究

程代娣
（安徽警官職業(yè)學(xué)院，安徽合肥230031）

摘要：針對(duì)目前高校計(jì)算機(jī)等級(jí)考試持續(xù)過低的現(xiàn)狀，應(yīng)用決策樹C4.5算法對(duì)安徽警官職業(yè)學(xué)院計(jì)算機(jī)等級(jí)考試成績數(shù)據(jù)進(jìn)行深入分析和研究，對(duì)預(yù)處理后的數(shù)據(jù)進(jìn)行挖掘并建立決策樹分類模型，由決策樹產(chǎn)生分類規(guī)則，找出影響計(jì)算機(jī)等級(jí)成績潛在的主導(dǎo)因素，從而為進(jìn)一步提高高校計(jì)算機(jī)等級(jí)考試通過率提供參考依據(jù).

關(guān)鍵詞：數(shù)據(jù)挖掘；決策樹；C4.5算法；計(jì)算機(jī)等級(jí)考試；成績分析

全國計(jì)算機(jī)等級(jí)考試在我院舉辦多年，教務(wù)成績管理系統(tǒng)中積累了大量的計(jì)算機(jī)二級(jí)考試Access成績.然而，一直以來這些成績主要為師生提供查詢、統(tǒng)計(jì)和排序等功能，無法挖掘出隱含在其背后對(duì)教學(xué)決策有價(jià)值的信息.基于二級(jí)通過率普遍過低的現(xiàn)象，迫切需要采用新的數(shù)據(jù)分析技術(shù)對(duì)海量的成績數(shù)據(jù)進(jìn)行分析，從中提取隱含的和有價(jià)值的資源.文中將決策樹C4.5算法引入到計(jì)算機(jī)等級(jí)考試成績分析中，從頂層進(jìn)行具體分析，找出影響計(jì)算機(jī)等級(jí)考試成績潛在的關(guān)鍵因素，為教師指明教學(xué)方向和教學(xué)重點(diǎn)，從而進(jìn)一步提高計(jì)算機(jī)等級(jí)考試的通過率.

1　決策樹C4.5算法

數(shù)據(jù)挖掘就是從海量的數(shù)據(jù)中找出隱含的有價(jià)值信息［1］.數(shù)據(jù)挖掘技術(shù)是一種新數(shù)據(jù)分析方法，它既能實(shí)現(xiàn)對(duì)歷史數(shù)據(jù)進(jìn)行有效管理和查找，又能實(shí)現(xiàn)不同但關(guān)聯(lián)數(shù)據(jù)之間的隱含關(guān)系，并能對(duì)海量數(shù)據(jù)進(jìn)行深層次的分析和挖掘，利用獲取的有價(jià)值信息預(yù)測(cè)將來發(fā)展方向，現(xiàn)實(shí)更快速和更理性化地做出正確的決策.決策樹是數(shù)據(jù)挖掘主要的算法，應(yīng)用十分廣泛.本文采用C4.5決策樹算法，將最終分類結(jié)果用圖形化樹形結(jié)構(gòu)表示出來，并構(gòu)建IF-THEN模式的分類規(guī)則.

1.1C4.5算法原則

采取信息熵原理構(gòu)建決策樹是C4.5算法的關(guān)鍵原則，即通過計(jì)算各個(gè)屬性信息增益率確定分類屬性，分類測(cè)試屬性由全部非類別屬性的最大信息增益率來決定［2］，自上而下遞歸地生成決策樹子結(jié)點(diǎn)分支來構(gòu)建決策樹［3］.決策樹初型構(gòu)建、決策樹修剪優(yōu)化和生成IF-THEN分類規(guī)則是C4.5算法的主要構(gòu)建流程.

1.2C4.5算法基本理論方法

信息增益是指期望信息或者信息熵的有效減少量，用來衡量一個(gè)屬性區(qū)分?jǐn)?shù)據(jù)樣本的能力［4］.在樹的每個(gè)結(jié)點(diǎn)上確定當(dāng)前結(jié)點(diǎn)的測(cè)試屬性的方法是計(jì)算具有最大信息增益的屬性.

定義1設(shè)s個(gè)樣本集是S，設(shè)定類標(biāo)號(hào)屬性具有n個(gè)不同值，定義n個(gè)不同類Ci（i可為1，2，…，n），設(shè)定Si是類Ci中樣本個(gè)數(shù)，那么，對(duì)于已知給定的樣本分類所需的信息熵為［4］：

其中，任意樣本Ci的概率是Pi=Si/S.

定義2假定屬性B賦予K個(gè)不同值｛b1，b2,…，bk｝.樣本集S被屬性B分割成k個(gè)小子集｛S1，S2，…, Sk｝；其中，S中有這樣一些樣本被Sj包含：樣本在B上具有值bj.假定確定B作為分類測(cè)試屬性，那么，由包含集合S的結(jié)點(diǎn)構(gòu)建出來的分枝對(duì)應(yīng)于這些子集.設(shè)子集Sj中類Ci的樣本個(gè)數(shù)為Sij［4］.按照由B劃分成子集的熵由以下公式給出：

對(duì)于一個(gè)給定S樣本集的Sj子集，

其中，sj中的樣本屬于類Ci的概率為

樣本集S屬性B的信息增益由以下公式得出：

信息增益比例的計(jì)算公式為：

其中分裂信息Spliti（B）定義為：

2　C4.5算法在計(jì)算機(jī)二級(jí)考試Access成績中應(yīng)用

用C4．5算法分析計(jì)算機(jī)二級(jí)考試Access課程的成績，找出影響計(jì)算機(jī)等級(jí)成績潛在的主導(dǎo)因素.

2.1數(shù)據(jù)收集

本文數(shù)據(jù)來源于安徽警官職業(yè)學(xué)院近3年來學(xué)生信息，數(shù)據(jù)由兩部分組成，一部分來自教務(wù)平臺(tái)的二級(jí)Access成績表，主要包括學(xué)號(hào)、姓名、性別、身份證號(hào)碼、專業(yè)和等級(jí)考試成績；另一部分來自學(xué)生調(diào)查表，包括學(xué)號(hào)、感興趣程度、是否按時(shí)完成作業(yè)、教學(xué)效果評(píng)價(jià)、每周上機(jī)時(shí)數(shù)和是否通過，共采集了550條記錄.Access成績表和學(xué)生調(diào)查表合成最終的分析數(shù)據(jù)集，將550條記錄數(shù)據(jù)集分成兩個(gè)部分：一是訓(xùn)練數(shù)據(jù)集410條記錄，二是測(cè)試數(shù)據(jù)集140條記錄.

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

在現(xiàn)實(shí)世界大數(shù)據(jù)庫中，初始數(shù)據(jù)并不總是完整的，數(shù)據(jù)預(yù)處理可以保證數(shù)據(jù)挖掘所需數(shù)據(jù)集的質(zhì)量.它主要包括數(shù)據(jù)集成、屬性歸約、數(shù)據(jù)清理三個(gè)環(huán)節(jié).

2.2.1數(shù)據(jù)集成

將多個(gè)不同數(shù)據(jù)源中的異構(gòu)數(shù)據(jù)利用數(shù)據(jù)約束和完整性方法融合存儲(chǔ)到一個(gè)完整統(tǒng)一的數(shù)據(jù)庫里.將上述收集來的二級(jí)Access成績表和學(xué)生調(diào)查表數(shù)據(jù)通過學(xué)號(hào)合并成一個(gè)表用于數(shù)據(jù)分析.

2.2.2數(shù)據(jù)歸約

收集的大量分析數(shù)據(jù)存在很多屬性，并不是每個(gè)屬性都與數(shù)據(jù)挖掘任務(wù)息息相關(guān).數(shù)據(jù)歸約的目的為了獲取比原始數(shù)據(jù)小的屬性集，新的數(shù)據(jù)集不影響數(shù)據(jù)挖掘結(jié)果.主要采取兩種方法.一是屬性的刪除.應(yīng)選取具有代表性的特征信息，通過二級(jí)Access成績表中可以看出，“學(xué)號(hào)”“身份證號(hào)碼”“姓名”和“專業(yè)”等屬性是多余的，因此必須刪除.二是屬性的泛化.屬性泛化是指把與數(shù)據(jù)挖掘任務(wù)相關(guān)的屬性從具體的概念值抽象到較高概念層的過程.根據(jù)屬性泛化原理，泛化合成表中的“等級(jí)成績”，該屬性采用百分制，具有不同的取值，可將其泛化為：通過（＞=60）和不通過（＜60）.通過對(duì)計(jì)算機(jī)等級(jí)考試成績的調(diào)查和研究，數(shù)據(jù)進(jìn)行如下處理：將“是否感興趣”分為“是”和“否”兩類；將“按時(shí)完成作業(yè)”分為“是”和“否”兩類；將“每周上機(jī)時(shí)數(shù)”分為“＜4”和“＞4”兩類；將“教學(xué)評(píng)價(jià)”屬性分為“優(yōu)秀”和“一般”兩類；“成績”分為“通過”和“不通過”兩類.

2.3數(shù)據(jù)清理

在有些情況下，C4．5算法可供使用的數(shù)據(jù)某些屬性的值為空或無法給出，本項(xiàng)目在C4.5算法的基礎(chǔ)上提出了兩種處理缺少屬性值的改進(jìn)措施.方法一是賦予結(jié)點(diǎn)n所對(duì)應(yīng)的訓(xùn)練集中該屬性的最常見值；方法二采用忽略元組法，直接丟棄含空缺值的元組.在本案例中采用元組直接忽略方法.經(jīng)過數(shù)據(jù)清理，共有400條有效數(shù)據(jù)記錄，10條噪音數(shù)據(jù)記錄.最終形成的樣本分布數(shù)據(jù)如表1［5］.

表1　樣本分布數(shù)據(jù)

2.4決策樹構(gòu)建與剪枝

以表1中的訓(xùn)練樣本集為例，采用C4.5算法構(gòu)建決策樹：

第1步：計(jì)算已知樣本分類屬性的信息熵.

表1中，樣本大小400個(gè)，125個(gè)為類“通過”的樣本大小，275個(gè)為類“不通過”的樣本大?。?］.首先用公式1計(jì)算I（S1，S2）；

第2步：計(jì)算每個(gè)屬性值所劃分的子集信息熵.

（1）屬性“是否感興趣”的子集信息熵的計(jì)算.

“是否感興趣”=“是”，95個(gè)數(shù)據(jù)樣本是類“通過”，類“不通過”有10個(gè)數(shù)據(jù)樣本，用公式3計(jì)算出：

“是否感興趣”=“否”，有30個(gè)樣本類“通過”，有265樣本是類“不通過”，由公式3計(jì)算出：

同理，計(jì)算“按時(shí)完成作業(yè)”屬性的子集信息熵.

計(jì)算“教學(xué)評(píng)價(jià)”屬性的子集信息熵.

計(jì)算“每周上機(jī)學(xué)時(shí)”屬性的子集信息熵.

第3步：計(jì)算所有屬性信息期望.

根據(jù)公式2，4個(gè)屬性期望信息計(jì)算如下：

第4步：計(jì)算所有屬性信息增益.

根據(jù)公式4，4個(gè)屬性信息增益計(jì)算如下：

第5步：每個(gè)屬性的分裂信息計(jì)算.

根據(jù)公式6，4個(gè)屬性的分裂信息計(jì)算如下：

第6步：每個(gè)屬性的信息增益率計(jì)算.

根據(jù)公式5，4個(gè)屬性信息熵計(jì)算如下：

第7步：確定決策樹的根結(jié)點(diǎn).

由上面的計(jì)算結(jié)果和C4.5算法原理可知，分類測(cè)試屬性確定為“是否感興趣”.同時(shí)建立該決策樹根結(jié)點(diǎn)，屬性標(biāo)記“是否感興趣”，對(duì)于每個(gè)測(cè)試屬性所取的值，分別引出一個(gè)相應(yīng)分支，其他樣本屬性也按照這種方法來劃分和構(gòu)建［5］.

第8步：按照上面的方法進(jìn)一步劃分分枝結(jié)點(diǎn)，為了防止訓(xùn)練數(shù)據(jù)過度和減低訓(xùn)練時(shí)間，對(duì)于過小比例的數(shù)據(jù)可忽略，在這里我們采用事后修剪法對(duì)決策樹進(jìn)行修剪，最后形成的一棵成績決策樹，如圖1所示.

圖1　計(jì)算機(jī)二級(jí)成績決策樹

2.5提取分類規(guī)則

可用IF-THEN分類規(guī)則從根結(jié)點(diǎn)、分支到葉子結(jié)點(diǎn)進(jìn)行表述，生成可理解的分類規(guī)則如下：

IF是否感興趣=“是”AND按時(shí)完成作業(yè)=“是”AND每周上機(jī)學(xué)時(shí)＞4THEN成績=“通過”

IF是否感興趣=“是”AND按時(shí)完成作業(yè)=“是”AND每周上機(jī)學(xué)時(shí)＜4THEN成績=“不通過”

IF感興趣=“是”AND按時(shí)完成作業(yè)=“否”AND每周上機(jī)學(xué)時(shí)＞4 AND教學(xué)評(píng)價(jià)=“優(yōu)秀”THEN成績=“通過”

IF是否感興趣=“是”AND按時(shí)完成作業(yè)=“否”AND每周上機(jī)學(xué)時(shí)＞4 AND教學(xué)評(píng)價(jià)=“一般”THEN成績=“不通過”

IF是否感興趣=“是”AND按時(shí)完成作業(yè)=“否”AND每周上機(jī)學(xué)時(shí)＜4”THEN成績=“不通過”

IF是否感興趣=“否”AND按時(shí)完成作業(yè)=“是”AND教學(xué)評(píng)價(jià)=“優(yōu)秀”AND每周上機(jī)學(xué)時(shí)＞4 THEN成績=“通過”

IF是否感興趣=“否”AND按時(shí)完成作業(yè)=“是”AND教學(xué)評(píng)價(jià)=“優(yōu)秀”AND每周上機(jī)學(xué)時(shí)＜4 THEN成績=“不通過”

IF是否感興趣=“否”AND按時(shí)完成作業(yè)=“是”AND教學(xué)評(píng)價(jià)=“一般”THEN成績=“不通過”

IF是否感興趣=“否”AND按時(shí)完成作業(yè)=“否”THEN成績=“不通過”.

2.6結(jié)論分析

通過對(duì)計(jì)算機(jī)等級(jí)考試成績決策樹的分析，得出以下結(jié)論：是否感興趣、按時(shí)完成作業(yè)、每周上機(jī)學(xué)時(shí)、教學(xué)評(píng)價(jià)分別在不同程度上影響計(jì)算機(jī)等級(jí)考試成績，其中學(xué)習(xí)興趣影響最大.要提高計(jì)算機(jī)等級(jí)考試的通過率，首先要激發(fā)學(xué)生的學(xué)習(xí)興趣，其次要按時(shí)完成作業(yè)，第三要加強(qiáng)上機(jī)實(shí)踐練習(xí)時(shí)數(shù)，最后要教師提高教學(xué)水平和方法.

3　結(jié)束語

文中分析了數(shù)據(jù)挖掘技術(shù)C4.5算法，并應(yīng)用C4.5算法對(duì)計(jì)算機(jī)二級(jí)考試成績進(jìn)行了深層次分析，構(gòu)建決策樹，挖掘出影響計(jì)算機(jī)等級(jí)成績潛在的主導(dǎo)因素，及時(shí)反饋到教師教學(xué)和學(xué)生學(xué)習(xí)中，為高校計(jì)算機(jī)等級(jí)考試改革提供有利的數(shù)據(jù)支持，從而進(jìn)一步提高計(jì)算機(jī)等級(jí)考試的通過率.

參考文獻(xiàn)：

［1］苗苗苗.數(shù)據(jù)挖掘中海量數(shù)據(jù)處理算法的研究與實(shí)現(xiàn)［D］.西安：西安建筑科技大學(xué)，2012.

［2］呂瑞雪.基于決策樹的中學(xué)生成績挖掘與分析［D］.呼和浩特：內(nèi)蒙古大學(xué)，2010.

［3］羅后平.數(shù)據(jù)挖掘在市場(chǎng)營銷中的應(yīng)用［J］.商業(yè)研究，2003（23）：139-140.

［4］紀(jì)希禹.數(shù)據(jù)挖掘技術(shù)應(yīng)用實(shí)例［M］北京：機(jī)械工業(yè)出版社，2009：34-36.

［5］程代娣.決策樹在高職院校畢業(yè)生就業(yè)工作中應(yīng)用研究［D］.合肥：安徽大學(xué)，2010.

Research on the Application of Algorithm C4.5 in the Analysis of College Students′Score of Computer Rank Examination

CHENG Daidi
（Anhui Vocational College of Police Officers，230031，Hefei，Anhui，China）

Abstract：This paper，adopting decision tree algorithm，focuses on analyzing and researching students′com?puter rank examination scores from Anhui Vocational College of Police Officers.It aims at finding out the dominant factors that affect the results of computer rank examination and offering effective and supportive da?ta for educational department and teachers with the purpose of improving teaching quality of the college，by applying algorithm C4.5 to mine the data preprocessed and to build classification model of decision tree to develop classification rules.

Key words：data mining；decision tree；algorithm C4.5；computer rank examination；the analysis of students′score

作者簡介：程代娣（1978-），女，安徽宣城人，碩士，講師，研究方向：數(shù)據(jù)庫技術(shù)與網(wǎng)站開發(fā).

基金項(xiàng)目：2015年度安徽省高等學(xué)校自然科學(xué)研究項(xiàng)目（12219zrkx2015B04）

收稿日期：2015-11-02

中圖分類號(hào)：TP 318

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：2095-0691（2016）01-0012-05