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

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

改進的ID3算法在遠程教學系統(tǒng)中的應(yīng)用

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

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

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

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

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

1 ID3算法分析

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

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

(1)

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

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

(2)

(3)

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

(4)

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

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

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

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

(5)

(6)

灰色關(guān)聯(lián)分析是將各因素統(tǒng)一放在一個系統(tǒng)中進行比較和分析，因此,它考慮了各因素之間的相關(guān)性，比系統(tǒng)分析中常用的因素兩兩對比法更合理、更科學?？紤]到系統(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ù)的曲線變化比較緩和，對信息增益因子修正不會出現(xiàn)過度的問題。因此，本文引入灰色關(guān)聯(lián)度的正弦值作為ID3算法的修正因子進行改進。

3 改進的ID3算法

改進算法GBID的具體流程是：

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

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

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

公式為

(7)

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

(8)

顯然，0

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

(9)

GBID算法的描述如下：

算法：GBID(Sample_set，Attribute_set)

輸入：由多個屬性描述的訓練樣本集Sample_set；候選屬性集Attribute_set。

輸出：一棵決策樹。

Begin

如果 Sample_set為空

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

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

則返回L作為葉結(jié)點，并以類C為標記；

如果 Attribute_set為空

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

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

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

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

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

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

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

標記結(jié)點L為Splitting _Attribute；

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

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

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

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

如果Si為空,

則加上一個葉結(jié)點，并標記為Sample_set中最普通的類；

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

End

4 利用GBID算法為學習者分類

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

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

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

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

5 結(jié)束語

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

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

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

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

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

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

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

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

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

[9]陳登科,胡翠華.數(shù)據(jù)挖掘技術(shù)在遠程教育中的應(yīng)用[J].情報科學,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

黑龍江省自然科學基金項目(F201224)

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

TP312

A

1671-4679(2014)01-0067-04

郝麗英]