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

?

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

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

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

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

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

1　決策樹C4.5算法

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

1.1C4.5算法原則

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

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

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

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

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

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

對于一個給定S樣本集的Sj子集，

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

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

信息增益比例的計算公式為：

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

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

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

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

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

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

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

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

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

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

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

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

在有些情況下，C4．5算法可供使用的數(shù)據(jù)某些屬性的值為空或無法給出，本項目在C4.5算法的基礎(chǔ)上提出了兩種處理缺少屬性值的改進(jìn)措施.方法一是賦予結(jié)點n所對應(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步：計算已知樣本分類屬性的信息熵.

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

第2步：計算每個屬性值所劃分的子集信息熵.

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

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

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

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

計算“教學(xué)評價”屬性的子集信息熵.

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

第3步：計算所有屬性信息期望.

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

第4步：計算所有屬性信息增益.

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

第5步：每個屬性的分裂信息計算.

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

第6步：每個屬性的信息增益率計算.

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

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

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

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

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

2.5提取分類規(guī)則

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

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

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

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

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

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

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

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

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

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

2.6結(jié)論分析

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

3　結(jié)束語

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

參考文獻(xiàn)：

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

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

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

［4］紀(jì)希禹.數(shù)據(jù)挖掘技術(shù)應(yīng)用實例［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ā).

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

收稿日期：2015-11-02

中圖分類號：TP 318

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

文章編號：2095-0691（2016）01-0012-05