改進(jìn)的ID3算法在遠(yuǎn)程教學(xué)系統(tǒng)中的應(yīng)用

王建偉，王 鑫，許憲東，李慧君，黑 龍

(黑龍江工程學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150050)

改進(jìn)的ID3算法在遠(yuǎn)程教學(xué)系統(tǒng)中的應(yīng)用

王建偉，王 鑫，許憲東，李慧君，黑 龍

(黑龍江工程學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150050)

當(dāng)前，遠(yuǎn)程教學(xué)系統(tǒng)缺少智能性，不能提供個(gè)性化教學(xué)，引入ID3算法后可以根據(jù)學(xué)習(xí)者的特征對其分類，從而實(shí)現(xiàn)對不同學(xué)習(xí)者的針對性教學(xué)。然而傳統(tǒng)的決策樹ID3算法存在多值傾向的問題，選擇分裂屬性不符合客觀事實(shí)。運(yùn)用一種基于灰色關(guān)聯(lián)分析的修正因子屬性選擇方法予以改進(jìn)，對取值較多但灰色關(guān)聯(lián)度低的屬性，在計(jì)算其信息增益時(shí)通過灰色關(guān)聯(lián)度的正弦值作為修正因子，克服傳統(tǒng)ID3算法的不足。將改進(jìn)的ID3算法引入到遠(yuǎn)程教學(xué)系統(tǒng)中，可以更好地對學(xué)習(xí)者進(jìn)行分類以實(shí)現(xiàn)智能化導(dǎo)學(xué)。

ID3算法；決策樹；灰色關(guān)聯(lián)度；修正因子；遠(yuǎn)程教學(xué)系統(tǒng)

傳統(tǒng)的遠(yuǎn)程教學(xué)系統(tǒng)通常以系統(tǒng)本身為中心，只能對不同的學(xué)生提供完全相同的學(xué)習(xí)材料和學(xué)習(xí)任務(wù)，缺乏智能性[1]。而數(shù)據(jù)挖掘技術(shù)可以從遠(yuǎn)程教學(xué)系統(tǒng)的海量數(shù)據(jù)中發(fā)現(xiàn)一些潛在的、有價(jià)值的規(guī)律,這無疑為智能化、個(gè)性化的網(wǎng)上學(xué)習(xí)提供了強(qiáng)有力的支持[2]。針對傳統(tǒng)網(wǎng)上學(xué)習(xí)系統(tǒng)的弊端，本文使用決策樹ID3算法根據(jù)學(xué)習(xí)者考試成績對其分類，實(shí)現(xiàn)智能化導(dǎo)學(xué)。但由于ID3算法存在著一些缺陷，故在原有算法基礎(chǔ)上加以改進(jìn)成為GBID算法，算法改進(jìn)后無論從算法效率還是分類的精確性上都得到了很大改善，從而更好地實(shí)現(xiàn)遠(yuǎn)程教學(xué)系統(tǒng)的智能性。

1 ID3算法分析

ID3算法是Quinlan在1986年提出的一種基于信息熵的決策樹學(xué)習(xí)算法。信息熵是信息的量化度量，而信息增益是兩個(gè)信息熵的差，代表在消除不確定性后獲得的信息量[3]。ID3算法實(shí)際上就是一個(gè)貪心算法，它采用由上而下、分而治之的遞歸方式來構(gòu)造決策樹。該算法的核心是[4]：在決策樹各級節(jié)點(diǎn)上選擇屬性的時(shí)候，通過計(jì)算信息增益來選擇最佳的分裂屬性。首先選擇信息增益值最大的屬性作為根節(jié)點(diǎn)，然后根據(jù)此根節(jié)點(diǎn)的不同取值創(chuàng)建分支，同時(shí)也對應(yīng)著一個(gè)被劃分的子集，再對各子集遞歸調(diào)用ID3算法來建立決策樹的節(jié)點(diǎn)分支直至整個(gè)決策樹生成。

ID3算法的具體描述如下[5]：假設(shè)S是s個(gè)數(shù)據(jù)樣本集合。假定類標(biāo)號屬性具有n個(gè)不同的值,定義n個(gè)不同類Ci(i=1,…,n)。設(shè)Si是類Ci中的樣本數(shù)。對一個(gè)給定的樣本分類所需要的期望信息給出公式為

(1)

式中：Pi是任意一個(gè)樣本屬于Ci的概率,并用Si/s估計(jì)。

設(shè)屬性A具有k個(gè)不同值{a1,a2,…,ak}，用屬性A將S劃分為k個(gè)子集{S1,S2,…,Sk}，其中,Sj包含S中這樣一些樣本,他們在A上具有值aj。如果把A選則為測試屬性(最好的分裂屬性),則這些子集對應(yīng)于由包含集合S的節(jié)點(diǎn)生長出來的分枝。Sij是子集Sj中類Ci的樣本數(shù)。根據(jù)由A劃分成子集的熵或期望信息給出公式[6]

(2)

(3)

Gain(A)=I(s1,s2,…,sn)-E(A).

(4)

Gain(A)是由于知道了屬性A的值而導(dǎo)致的熵的期望壓縮。通過該算法計(jì)算每個(gè)屬性的信息增益。將具有最高信息增益的屬性選作給定集合S的分裂屬性。創(chuàng)建一個(gè)節(jié)點(diǎn),并以該屬性標(biāo)記,對屬性的每個(gè)值創(chuàng)建分枝,并據(jù)此劃分樣本[7]。

作為決策樹的一個(gè)經(jīng)典構(gòu)造算法，ID3算法的優(yōu)點(diǎn)在于：搜索空間是完全的假設(shè)空間，目標(biāo)函數(shù)必在搜索空間中，不存在無解的危險(xiǎn)；算法的基礎(chǔ)理論比較清晰，在屬性選擇時(shí)利用了信息增益的概念；決策樹的每個(gè)分支都對應(yīng)一個(gè)分類規(guī)則，可以生成容易理解的IF-THEN分類規(guī)則，因此，產(chǎn)生的分類規(guī)則直觀性強(qiáng)，易于理解。但是通過近些年國內(nèi)外學(xué)者對ID3算法的研究也發(fā)現(xiàn)了一些不足：計(jì)算信息增益時(shí)傾向于選擇具有多值的屬性，這樣不太合理，因?yàn)樵诤芏嗲闆r下取值較多的屬性并不總是最優(yōu)的屬性；在構(gòu)造樹的過程中，需要多次自上而下對數(shù)據(jù)集的排序和掃描，因而導(dǎo)致算法的處理效率較低[8]。

2 基于灰色關(guān)聯(lián)分析的修正因子

灰色關(guān)聯(lián)分析是指對一個(gè)系統(tǒng)發(fā)展變化態(tài)勢的定量描述和比較的方法，其基本思想是通過確定參考數(shù)據(jù)列和若干個(gè)比較數(shù)據(jù)列的幾何形狀相似程度來判斷其聯(lián)系是否緊密，它反映了曲線間的關(guān)聯(lián)程度[9]。首先求得兩者的關(guān)聯(lián)系數(shù)，由關(guān)聯(lián)系數(shù)得到關(guān)聯(lián)度，再按照關(guān)聯(lián)度的大小進(jìn)行排序、分析，得出結(jié)論。灰色關(guān)聯(lián)分析通過一定的方法，找到系統(tǒng)中兩個(gè)因素變化的態(tài)勢來判斷它們之間的關(guān)聯(lián)程度。如果兩者變化同步程度高，則可以認(rèn)為兩者關(guān)聯(lián)較大；反之，則兩者關(guān)聯(lián)度較小。因此，灰色關(guān)聯(lián)分析對于一個(gè)系統(tǒng)發(fā)展變化態(tài)勢提供了量化的度量，非常適合動(dòng)態(tài)的歷程分析[10]。根據(jù)灰色關(guān)聯(lián)分析的方法來計(jì)算特征屬性與分類屬性的關(guān)聯(lián)度并取其正弦值作為修正因子，重新計(jì)算ID3算法中屬性的Gain值，通過這樣的方式來解決ID3算法中的多值偏向問題。使用灰色關(guān)聯(lián)分析的方法計(jì)算修正因子的方法如下：設(shè)訓(xùn)練數(shù)據(jù)集T有樣本個(gè)數(shù)為n，類別屬性記為C，特征屬性為m個(gè)且分別記為Xi(i=1,2,3,…，m)，則按照灰色系統(tǒng)理論，比較各屬性之間的關(guān)系，計(jì)算兩者的關(guān)聯(lián)度。為此，假設(shè)n個(gè)樣本的類別屬性值構(gòu)成一灰色序列：C={C(1),C(2),…，C(n)};n個(gè)樣本的各特征屬性值也構(gòu)成一個(gè)灰色序列:Xi={Xi(1),Xi(2),…,Xi(n)}(i=1,2,…,m)。則特征屬性序列Xi與類別屬性序列C在第k個(gè)點(diǎn)(樣本)的灰色關(guān)聯(lián)系數(shù)定義為

(5)

(6)

灰色關(guān)聯(lián)分析是將各因素統(tǒng)一放在一個(gè)系統(tǒng)中進(jìn)行比較和分析，因此,它考慮了各因素之間的相關(guān)性，比系統(tǒng)分析中常用的因素兩兩對比法更合理、更科學(xué)?？紤]到系統(tǒng)中類別屬性序列曲線與特征屬性序列曲線的緊密程度可用灰色關(guān)聯(lián)度的大小來描述，即灰色關(guān)聯(lián)度最小的特征屬性對系統(tǒng)類別屬性的影響也最?。环粗?，灰色關(guān)聯(lián)度大的特征屬性對系統(tǒng)類別屬性的影響相對要大。所以，對于取值較多但灰色關(guān)聯(lián)度較小的特征屬性對分類結(jié)果影響不大，顯然也不是最優(yōu)屬性。另外，考慮到正弦函數(shù)的曲線變化比較緩和，對信息增益因子修正不會(huì)出現(xiàn)過度的問題。因此，本文引入灰色關(guān)聯(lián)度的正弦值作為ID3算法的修正因子進(jìn)行改進(jìn)。

3 改進(jìn)的ID3算法

改進(jìn)算法GBID的具體流程是：

1)計(jì)算各特征屬性與類別屬性之間的灰色關(guān)聯(lián)度，并將它們排序；

2)對取值較多的屬性通過灰色關(guān)聯(lián)度判斷是否最優(yōu)，從而確定是否降低它的信息增益；

3)對取值較多但灰色關(guān)聯(lián)度低的屬性，在計(jì)算其信息增益時(shí)通過灰色關(guān)聯(lián)度的正弦值作為修正因子，而其它屬性計(jì)算信息增益時(shí)修正因子設(shè)為0。

公式為

(7)

式中：CF(A)為屬性A的修正因子，定義為

(8)

顯然，0

Gain1(A)=I(s1,s2,…,sn)-E1(A).

(9)

GBID算法的描述如下：

算法：GBID(Sample_set，Attribute_set)

輸入：由多個(gè)屬性描述的訓(xùn)練樣本集Sample_set；候選屬性集Attribute_set。

輸出：一棵決策樹。

Begin

如果 Sample_set為空

則返回null；創(chuàng)建結(jié)點(diǎn)L；

如果結(jié)點(diǎn)L中的所有樣本均屬于同一類C

則返回L作為葉結(jié)點(diǎn)，并以類C為標(biāo)記；

如果 Attribute_set為空

則返回L作為葉結(jié)點(diǎn)，并以Sample_set中最普通的類標(biāo)記；

根據(jù)式(4)計(jì)算出Attribute_set中每個(gè)屬性的信息增益，并選擇出信息增益最大的屬性A和取值個(gè)數(shù)最多的屬性B;

如果A=B，該條件成立說明選擇信息增益最大和取值個(gè)數(shù)最多的屬性作為測試屬性易產(chǎn)生多值偏向問題，需要用修正因子降低該屬性的信息增益;

則根據(jù)式(8)來計(jì)算該屬性的修正因子；

再根據(jù)式(9)重新計(jì)算該屬性的信息增益；

否則該屬性的修正系數(shù)為0，信息增益最大的屬性不是取值個(gè)數(shù)最多屬性，選擇該屬性作為分裂屬性不會(huì)產(chǎn)生多值偏向問題，不需要用修正系數(shù)降低該屬性信息增益；

從Attribute_set中選擇出信息增益最大的屬性Splitting _Attribute作為分裂屬性；

標(biāo)記結(jié)點(diǎn)L為Splitting _Attribute；

For Each Splitting_Attribute中的已知ai(i=1,2,…,m)；

m為Splitting _Attribute的取值個(gè)數(shù)∥根據(jù)Splitting _Attribute的取值劃分Sample_set

根據(jù)Splitting _Attribute=ai，從結(jié)點(diǎn)L產(chǎn)生相應(yīng)分支表示測試條件；

設(shè)Si(i=1,2,…,m)為Splitting _Attribute=ai所獲得的樣本集；

如果Si為空,

則加上一個(gè)葉結(jié)點(diǎn)，并標(biāo)記為Sample_set中最普通的類；

否則加上GBID(Attribute_set,Splitting _Attribute)返回的結(jié)點(diǎn)；

End

4 利用GBID算法為學(xué)習(xí)者分類

下面以具體實(shí)驗(yàn)說明GBID算法的應(yīng)用。

學(xué)習(xí)者考試成績的特征屬性課程類型A,B,C，量化為{0,1,2}；在線學(xué)習(xí)時(shí)間可分為較短、適中、較長，量化為{0,1,2}；試卷難度為難、易，量化為{0,1}；溝通能力為強(qiáng)、弱，量化為{0,1}；分類屬性考試成績以80分為界，大于80分為好，小于80分為不好，量化為{0,1}。根據(jù)訓(xùn)練集樣本數(shù)據(jù)，依次根據(jù)式(6)計(jì)算各特征屬性與分類屬性的灰色關(guān)聯(lián)度，結(jié)果為r(課程類型)=0.52，r(在線學(xué)習(xí)時(shí)間)=0.72，r(試卷難度)=0.78，r(溝通能力)=0.56，然后計(jì)算上述屬性信息增益，可得Gain(課程類型)=0.481 6，Gain(在線學(xué)習(xí)時(shí)間)=0.027 5，Gain(試卷難度)=0.058 8，Gain(溝通能力)=0.036 8，因?yàn)檎n程類型的信息增益最大、取值個(gè)數(shù)最多但灰色關(guān)聯(lián)度最低，所以需要用修正因子降低其信息增益，設(shè)定修正因子CF(課程類型)為sin(0.52)=0.496 8，而其它屬性的信息增益設(shè)定為0，則GBID算法與ID3算法的比較如表1所示。

表1 GBID算法對考試成績各屬性信息增益的影響

由表1可以看出，ID3算法確定決策樹的根節(jié)點(diǎn)時(shí)，選擇信息增益最大的課程類型作為分裂屬性，顯然這與客觀事實(shí)不符。而GBID算法在確定根節(jié)點(diǎn)時(shí)，選擇試卷難度作為分裂屬性，符合客觀事實(shí)，避免了多值但非最優(yōu)屬性的課程類型成為分裂屬性。

5 結(jié)束語

在遠(yuǎn)程教學(xué)系統(tǒng)中，利用GBID算法根據(jù)學(xué)習(xí)者考試成績進(jìn)行分類，克服了ID3算法多值傾向問題，使分類更加符合客觀規(guī)律，以此為依據(jù)為不同的學(xué)習(xí)者提供不同的教學(xué)策略，真正實(shí)現(xiàn)針對每一個(gè)學(xué)習(xí)者的智能化導(dǎo)學(xué)。

[1]王鑫,王建偉,鐘玉峰,等.個(gè)性化遠(yuǎn)程教學(xué)平臺中數(shù)據(jù)挖掘技術(shù)的應(yīng)用[J]. 黑龍江工程學(xué)院學(xué)報(bào)：自然科學(xué)版，2010(24):72-74.

[2]Jiawei Han,Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)[M].北京：機(jī)械工業(yè)出版社，2003:15-17.

[3]孫衛(wèi)強(qiáng).決策樹方法在遠(yuǎn)程教育輔助教學(xué)中的應(yīng)用研究[D].廣州：中山大學(xué)，2010:22-25.

[4]陶靈姣,孫繼銀,李智.遠(yuǎn)程教育考試成績分析決策樹的構(gòu)造方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2006(3):37-39.

[5]高紅建,謝如鶴,李韓娟.決策分析模型評估客運(yùn)服務(wù)質(zhì)量的研究[J].黑龍江工程學(xué)院學(xué)報(bào)：自然科學(xué)版，2003(2):48-51.

[6]孟迎,馮麗輝,趙鐵軍.基于決策樹的漢語基本名詞短語識別[J].黑龍江工程學(xué)院學(xué)報(bào):自然科學(xué)版，2004，6(2):1-4.

[7] 楊鴻賓.數(shù)據(jù)挖掘在個(gè)性化網(wǎng)絡(luò)教學(xué)平臺中的應(yīng)用研究[D].北京：首都師范大學(xué)，2005:36-38.

[8]屠宏,吳宏江.數(shù)據(jù)挖掘在網(wǎng)絡(luò)學(xué)習(xí)者學(xué)習(xí)特征分析系統(tǒng)中的應(yīng)用[J].遠(yuǎn)程教育雜志，2004(5):16-18.

[9]陳登科,胡翠華.數(shù)據(jù)挖掘技術(shù)在遠(yuǎn)程教育中的應(yīng)用[J].情報(bào)科學(xué),2003,4(4):18-20.

ApplicationofimprovedID3algorithmtodistanceeducationsystem

WANG Jian-wei1,WANG Xin1,XU Xian-dong1, LI Hui-jun1, HEI Long1

(College of Computer Science and Technology, Heilongjiang Institute of Technology, Harbin 150050, China)

Currently,the distance education system is lack of intelligence and cannot provide personalized teaching which can be classified according to the feature of different learners after introducing ID3 algorithm in order to realize the targeted teaching to different learners.There are multi-valued problems in the traditional decision tree algorithm ID3, and split attribute selecting does not conform to the objective facts.A feature selection method of correction factor is used based on grey relational analysis. The grey correlation sine value is selected as a correction factor when calculating the information gain for the properties of low value but more grey correlation degree to overcome the deficiency of the traditional ID3 algorithm.The introduction of improved ID3 algorithm can classify learners better to achieve intelligent tutoring.

ID3 algorithm；decision tree；grey correlation degree；correction factor；distance education system

2013-06-25

黑龍江省自然科學(xué)基金項(xiàng)目(F201224)

王建偉(1978-)，男,講師,研究方向:遠(yuǎn)程教育;數(shù)據(jù)挖掘.

TP312

A

1671-4679(2014)01-0067-04

郝麗英]