C4.5決策樹(shù)法在網(wǎng)絡(luò)課程知識(shí)點(diǎn)個(gè)性化設(shè)計(jì)中的應(yīng)用

馬偉杰

（鄭州航空工業(yè)管理學(xué)院 計(jì)算機(jī)科學(xué)與應(yīng)用系，河南 鄭州 450015）

C4.5決策樹(shù)法在網(wǎng)絡(luò)課程知識(shí)點(diǎn)個(gè)性化設(shè)計(jì)中的應(yīng)用

馬偉杰

（鄭州航空工業(yè)管理學(xué)院 計(jì)算機(jī)科學(xué)與應(yīng)用系，河南 鄭州 450015）

決策樹(shù)是歸納學(xué)習(xí)和數(shù)據(jù)挖掘的重要方法，通常用來(lái)形成分類器和預(yù)測(cè)模型。對(duì)網(wǎng)絡(luò)課程知識(shí)點(diǎn)個(gè)性化設(shè)計(jì)中的大量數(shù)據(jù)，運(yùn)用數(shù)據(jù)挖掘算法中的決策樹(shù)C4.5算法對(duì)所給數(shù)據(jù)進(jìn)行處理，選取決策屬性，構(gòu)造決策樹(shù)，提取分類規(guī)則，獲取每一個(gè)知識(shí)點(diǎn)與不同類型的學(xué)生之間的關(guān)系。通過(guò)實(shí)驗(yàn)仿真發(fā)現(xiàn)，C4.5決策樹(shù)算法取得了較為理想的分類預(yù)測(cè)效果。

C4.5算法；決策樹(shù)；網(wǎng)絡(luò)課程；知識(shí)點(diǎn)個(gè)性化

一、引言

學(xué)生對(duì)網(wǎng)絡(luò)課程學(xué)習(xí)的個(gè)性特征差異主要表現(xiàn)在學(xué)生的專業(yè)基礎(chǔ)、學(xué)習(xí)興趣、學(xué)習(xí)傾向、課程知識(shí)點(diǎn)的類型、知識(shí)點(diǎn)難易度及學(xué)習(xí)材料的呈現(xiàn)方式等。如何根據(jù)學(xué)生對(duì)課程學(xué)習(xí)的個(gè)性特征差異發(fā)現(xiàn)課程知識(shí)點(diǎn)之間的聯(lián)系并生產(chǎn)相應(yīng)個(gè)性化學(xué)習(xí)環(huán)境，是一項(xiàng)重要研究課題。為此，筆者針對(duì)課程知識(shí)點(diǎn)個(gè)性化設(shè)計(jì)中的大量數(shù)據(jù)，運(yùn)用數(shù)據(jù)挖掘算法中的決策樹(shù)C4.5算法對(duì)所給數(shù)據(jù)進(jìn)行處理，選取決策屬性，構(gòu)造決策樹(shù)，提取分類規(guī)則，從而獲取每一個(gè)知識(shí)點(diǎn)與不同類型的學(xué)生的關(guān)系。

二、C4.5決策樹(shù)算法

C4.5算法是構(gòu)造決策樹(shù)分類器的一種有效算法，并最終可以形成產(chǎn)生式規(guī)則。C4.5算法的輸入是一張關(guān)系表，由若干不同的屬性及若干數(shù)據(jù)元組（稱為訓(xùn)練樣本）組成。屬性分為兩部分：一部分作為判定對(duì)象屬性（判定樹(shù)中的非葉節(jié)點(diǎn)），另一部分作為分類對(duì)象屬性（判定樹(shù)中的葉節(jié)點(diǎn)）。C4.5算法采用信息熵的方法，比較各個(gè)判定對(duì)象屬性的信息增益率的大小，選擇信息增益率最大的屬性進(jìn)行分類，遞歸生成一個(gè)判定樹(shù)。

設(shè)|S|為訓(xùn)練集S的樣本總數(shù)，共有m類樣本Ci（i=1，2，3，…，m），|Ci|為類Ci中的樣本數(shù)，設(shè)Pi=|Ci|/|S|是任意樣本屬于Ci的概率，訓(xùn)練樣本分類屬性的總信息熵E（S1，S2，…，Sm）的計(jì)算公式為：

設(shè)屬性A具有v個(gè)不同值{a1，a2，…，av}，可以用屬性A將S劃分為v個(gè)子集{S1，S2，…，Sv}，其中Sj包含S中這樣一些樣本，它們?cè)贏上具有值aj（j=1，2，…，v）。設(shè)|Sij|為Si類中Cj的樣本數(shù)，以屬性A為分類所需的期望熵E（A）的計(jì)算公式為：

屬性A相對(duì)于類別集合的信息增益Gain（C，A）的計(jì)算公式為：

屬性A相對(duì)于類別集合C的信息增益率GainRatio（C，A）的計(jì)算公式為：

上述描述中，假設(shè)對(duì)象屬性的值是離散的。如果對(duì)象屬性的值是連續(xù)的，則要經(jīng)過(guò)離散化處理，首先尋找該連續(xù)型屬性的最小值MIN和最大值MAX，再設(shè)置區(qū)間［MIN，MAX］的m個(gè)等分?jǐn)帱c(diǎn)Ai（i=1，2，…，m），分別為：

分別計(jì)算把［MIN，Ai］和［Ai，MAX］（i=1，2，…，m）作為區(qū)間時(shí)的信息增益值Gain（［MIN，MAX］，Ai），并進(jìn)行比較，選取信息增益值最大Ak的作為該連續(xù)屬性的斷點(diǎn)，把屬性值設(shè)置為［MIN，Ak］和［Ak，MAX］。

C4.5算法是一個(gè)循環(huán)、遞歸的過(guò)程，核心部分的描述如下：

/*參數(shù)：R表示判定對(duì)象屬性，C表示目標(biāo)屬性，S表示訓(xùn)練集*/

三、C4.5算法在高校獎(jiǎng)學(xué)金評(píng)定中的應(yīng)用

1.學(xué)習(xí)者模型及課程知識(shí)點(diǎn)屬性。

表1 數(shù)據(jù)轉(zhuǎn)換后的課程知識(shí)點(diǎn)信息特征集（部分）

中國(guó)現(xiàn)代遠(yuǎn)程教育標(biāo)準(zhǔn)體系 《學(xué)習(xí)者模型規(guī)范CELTS-11》為教育研究者提供了規(guī)范化的學(xué)生模型和數(shù)據(jù)，該規(guī)范指出學(xué)習(xí)者模型要包括個(gè)人信息、學(xué)業(yè)信息、偏好信息和績(jī)效信息等4個(gè)部分。其中個(gè)人信息是指學(xué)習(xí)者的基本注冊(cè)信息，如學(xué)號(hào)、姓名、性別、出生日期、聯(lián)系方式等；學(xué)業(yè)信息是指學(xué)習(xí)者的專業(yè)、年級(jí)、學(xué)習(xí)計(jì)劃等信息；偏好信息主要是記錄學(xué)習(xí)者在學(xué)習(xí)方面的偏好情況，如對(duì)學(xué)習(xí)材料媒體呈現(xiàn)形式的偏好，對(duì)教師的講授方式的偏好，對(duì)課程知識(shí)點(diǎn)學(xué)習(xí)方式的偏好等；績(jī)效信息主要是指學(xué)習(xí)者的學(xué)習(xí)效果。因此，被挖掘的課程設(shè)計(jì)知識(shí)點(diǎn)屬性主要由以下幾個(gè)部分組成：知識(shí)點(diǎn)編號(hào)（CNo），知識(shí)點(diǎn)類別（CNType）（A.概念、B.原理、C.事實(shí)、D.問(wèn)題、E.技能），知識(shí)點(diǎn)難度（CNDD）（A.容易、B.一般、C.難、D.很難），知識(shí)點(diǎn)掌握程度（CNGD）（A.識(shí)記、B.理解、C.應(yīng)用、D.分析、E.綜合、F.評(píng)價(jià)），知識(shí)點(diǎn)學(xué)習(xí)材料呈現(xiàn)方式（CNEM）（A.純文本、B.圖像、C.聲音、D.視頻），知識(shí)點(diǎn)講授方式（CNTeach）（A.單純理論講解、B.結(jié)合實(shí)例講解），知識(shí)點(diǎn)學(xué)習(xí)方式（CNLearn）（A.自學(xué)、B.合作學(xué)習(xí)、C.先自學(xué)后聽(tīng)課），績(jī)效（CNAC）（A.熟練掌握、B.基本掌握、C.基本了解）等。

2.數(shù)據(jù)準(zhǔn)備與預(yù)處理。

數(shù)據(jù)來(lái)自2008、2009級(jí)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)108名學(xué)生對(duì) 《計(jì)算機(jī)網(wǎng)絡(luò)》課程第3章至第9章共117個(gè)教學(xué)知識(shí)點(diǎn)，共5322條學(xué)習(xí)反饋信息。經(jīng)過(guò)數(shù)據(jù)預(yù)處理后，共有5220條記錄。為了后面對(duì)建立好的決策樹(shù)模型進(jìn)行評(píng)估預(yù)測(cè)，預(yù)留1/3的記錄作為測(cè)試數(shù)據(jù)，2/3的記錄數(shù)據(jù)作為建立決策樹(shù)模型的訓(xùn)練集。具體的數(shù)據(jù)信息如表1所示。

表1中的決策屬性有CNType、CNDD、CNGD、CNEM、CNTeach和CNLearn，類別屬性為CNAC，類別屬性的取值有3個(gè)：熟練掌握、基本掌握和基本了解。

3.構(gòu)造決策樹(shù)。

數(shù)據(jù)預(yù)處理后，開(kāi)始?xì)w納決策樹(shù)，此過(guò)程使用數(shù)據(jù)預(yù)處理得到的訓(xùn)練集。根據(jù)前述的C4.5算法，將屬性 CNType、CNDD、CNGD、CNEM、CNTeach和CNLearn作為算法的對(duì)象屬性，將屬性CNAC作為目標(biāo)屬性，利用信息增益率的定義將屬性進(jìn)行排列，具有最高信息增益率的屬性選作給定集合的測(cè)試屬性。創(chuàng)建一個(gè)根結(jié)點(diǎn)，并以該屬性標(biāo)記，對(duì)屬性的每個(gè)值創(chuàng)建分支，然后遞歸建樹(shù)，可構(gòu)造一棵決策樹(shù)，算法具體處理過(guò)程如下：

訓(xùn)練樣本數(shù)據(jù)集S中，共有3480個(gè)元組，其中類別屬性（屬性值熟練掌握、基本掌握和基本了解）每個(gè)屬性值所對(duì)應(yīng)的子集中元組個(gè)數(shù)分別為S1=1135，S2=1170，S3=1175。為了計(jì)算每一個(gè)決策屬性的信息增益，首先利用公式計(jì)算集合S分類的總信息熵：

然后計(jì)算每一個(gè)決策屬性的期望信息熵。

對(duì)屬性“知識(shí)點(diǎn)講授方式”，知識(shí)點(diǎn)講授方式=單純理論講解

因此“知識(shí)點(diǎn)講授方式”的信息增益為：

屬性“知識(shí)點(diǎn)講授方式”的信息增益率為：

同理得到屬性 “知識(shí)點(diǎn)類別”、“知識(shí)點(diǎn)難度”、“知識(shí)點(diǎn)掌握程度”、“知識(shí)點(diǎn)學(xué)習(xí)材料呈現(xiàn)方式”、“知識(shí)點(diǎn)學(xué)習(xí)方式”的信息增益律分別為：

由于屬性“知識(shí)點(diǎn)難度（CNDD）”具有最大的信息增益率值，故而選擇該屬性作為決策樹(shù)的根節(jié)點(diǎn)。對(duì)于每一個(gè)分支，重復(fù)上述步驟生成決策樹(shù)。如圖1所示。因篇幅有限，只畫(huà)出第一層次單位的決策樹(shù)。

4.分類規(guī)則提取。

從決策樹(shù)中提取熟練掌握、基本掌握和基本了解的規(guī)則。分類規(guī)則如下：

①if CNType=“A”and CNDD=“A”and CNGD=“C”and CNEM=“A”then CNAC=“A（熟練掌握）”。也就是說(shuō)，如果知識(shí)點(diǎn)類型為“概念”、知識(shí)點(diǎn)難度為“容易”、知識(shí)點(diǎn)掌握程度為“應(yīng)用”、知識(shí)點(diǎn)呈現(xiàn)方式為“純文本”，則學(xué)習(xí)效果為“熟練掌握”。

②if CNType=“C”and CNDD=“B”and CNGD=“C”and CNEM=“D”and CNTeach=“B”then CNAC=“B （基本掌握）”。也就是說(shuō)，如果知識(shí)點(diǎn)類型為“事實(shí)”、知識(shí)點(diǎn)難度為“一般”、知識(shí)點(diǎn)掌握程度為“應(yīng)用”、知識(shí)點(diǎn)呈現(xiàn)方式為“視頻”、講授方式為“結(jié)合實(shí)例講解”，則學(xué)習(xí)效果為“基本掌握”。

③if CNType=“E”and CNDD=“D”and CNGD=“E”and CNEM=“C”and CNTeach=“A”then CNAC=“C（基本了解）”。也就是說(shuō)，如果知識(shí)點(diǎn)類型為“技能”、知識(shí)點(diǎn)難度為“很難”、知識(shí)點(diǎn)掌握程度為“綜合”、知識(shí)點(diǎn)呈現(xiàn)方式為“聲音”、講授方式為“單純理論講解”，則學(xué)習(xí)效果為“基本了解”。

由以上規(guī)則可以看出，網(wǎng)絡(luò)學(xué)習(xí)者要想獲得較為理想的學(xué)習(xí)效果，網(wǎng)絡(luò)課程開(kāi)發(fā)者在進(jìn)行知識(shí)點(diǎn)個(gè)性化設(shè)計(jì)時(shí)，知識(shí)點(diǎn)類型應(yīng)該以“概念”為主、知識(shí)點(diǎn)應(yīng)該容易一些、多采用純文本方式去呈現(xiàn)知識(shí)點(diǎn)。

四、結(jié)束語(yǔ)

在目前網(wǎng)絡(luò)教育成為構(gòu)建終身學(xué)習(xí)體系，普及與提高全民素質(zhì)的重要手段和途徑的同時(shí)，將數(shù)據(jù)挖掘理論中的決策樹(shù)算法引入網(wǎng)絡(luò)教育核心的網(wǎng)絡(luò)課程的設(shè)計(jì)中，對(duì)網(wǎng)絡(luò)課程中知識(shí)點(diǎn)的數(shù)據(jù)進(jìn)行分析，以實(shí)現(xiàn)對(duì)知識(shí)點(diǎn)個(gè)性化設(shè)計(jì)的目的。實(shí)驗(yàn)表明應(yīng)用此數(shù)據(jù)挖掘算法構(gòu)造簡(jiǎn)單、能正確分類，處理速度較快。

［1］云玉屏，林克正.C4.5算法在冠狀造影數(shù)據(jù)處理中的應(yīng)用［J］.計(jì)算機(jī)工程與應(yīng)用，2008，（10）．

［2］尹幫治，謝鯤.高校獎(jiǎng)學(xué)金評(píng)定系統(tǒng)的設(shè)計(jì)研究［D］.大連：大連理工大學(xué)，2008．

［3］鄒競(jìng)，鄢創(chuàng)輝.決策樹(shù)C4.5算法在課程知識(shí)點(diǎn)個(gè)性化教學(xué)中的應(yīng)用［J］.長(zhǎng)江大學(xué)學(xué)報(bào)，2010，（9）．

［4］宋暉，張良均.C4.5決策樹(shù)法在空氣質(zhì)量評(píng)價(jià)中的應(yīng)用［J］.科學(xué)技術(shù)與工程，2011，（7）．

［5］吳陳，林炎鐘.C4.5算法在高校教師評(píng)價(jià)中的應(yīng)用研究［J］.信息技術(shù)，2010，（1）．

［6］David Baron.Style System Overview［DB/OL］.http：//www. mozilla.org/newlayout/doc/style-techtalk.html，2002-06.

［7］邵興江.數(shù)據(jù)挖掘在教育信息化中的應(yīng)用空間分析［EB/OL］. http：//www.Zjedu.org/xdjyjs/107/64781thm，2008-01-08.

［8］李楠，段隆振，陳萌.決策樹(shù)C4.5算法在數(shù)據(jù)挖掘中的分析及其應(yīng)用［J］.計(jì)算機(jī)與現(xiàn)代化，2008，（12）．

Application of C4.5 Algorithm on Personalized Knowledge Points of Web-based Course Decision

Ma Weijie
（Zhengzhou Institute of Aeronautic Industry Management，Zhengzhou，Henan，450015）

Decision tree is an important method of data mining and inductive learning and usually used to form classification and prediction model.The large amounts of data of Personalized knowledge points of Web-based Course decision，used the C4.5 decision tree algorithm to process，select decision attributes，construct a decision tree，classify rule extraction so as to obtain the relationship of knowledge points and students.Through the experiment discovery，the results of experiments demonstrated that C4.5 decision tree algorithm can obtain good results of classification.

C4.5 algorithm；decision tree；web-based course；personalized knowledge points

TP312.8

A

1671-2862（2012）03-0108-03

2012-02-15

鄭州航空工業(yè)管理學(xué)院教育教學(xué)科學(xué)研究基金項(xiàng)目（項(xiàng)目編號(hào)：2010103003）。

馬偉杰，男，河南鄭州人，碩士研究生，研究方向：網(wǎng)絡(luò)環(huán)境下的數(shù)據(jù)挖掘技術(shù)（Web Mining）。