張凌菁 西南大學(xué)

引言：在信息化時(shí)代，數(shù)據(jù)資源量呈現(xiàn)一種指數(shù)爆炸的狀態(tài),對(duì)數(shù)據(jù)資源進(jìn)行挖掘，可幫助人們從數(shù)據(jù)庫(kù)中提取感興趣的信息、規(guī)律從而有效地利用數(shù)據(jù)信息。分類算法數(shù)據(jù)挖掘中最常用的一種數(shù)據(jù)計(jì)算方法就是決策樹(shù)算法，是依據(jù)現(xiàn)有的數(shù)據(jù)資源，而建立的一種預(yù)測(cè)模型。ID3算法是根據(jù)決策樹(shù)的反饋對(duì)信息進(jìn)行分類的算法，該算法根據(jù)增益的信息，運(yùn)用從上而下的策略建立決策樹(shù)。這種信息增益可以度量出某個(gè)屬性對(duì)樣本集合分類的好壞。因?yàn)樗惴ú捎昧诵畔⒃鲆?，所以它建立的決策樹(shù)規(guī)模比較小，便于查詢。

1.算法基本原理

ID3算法主要依賴于決策樹(shù)的建立，由J.Ross.Quinlan在1986年創(chuàng)建。ID3是根據(jù)信息的增益效果，采用自上而下的貪心策略對(duì)決策樹(shù)進(jìn)行組建，它的增益決策屬性分類判別能力根據(jù)信息增益來(lái)度量，從而選擇決策結(jié)點(diǎn)屬性，并將建樹(shù)的方法應(yīng)用于一個(gè)迭代的模型中。ID3算法的核心就是分裂分裂之后信息增益最大的屬性，期望的信息越小，信息的增益就會(huì)越大。

1.1 基本定義

ID3算法根據(jù)每個(gè)屬性的分裂后的信息增益，如果信息增益高就是好屬性，以信息增益最高的屬性作為劃分的標(biāo)準(zhǔn)，之后對(duì)這個(gè)過(guò)程重復(fù)運(yùn)算，直到生成一個(gè)能完美分類訓(xùn)練樣例的決策樹(shù)之后結(jié)束運(yùn)算。

設(shè)S代表s個(gè)數(shù)據(jù)樣本的集合，有 m個(gè)不同的值類標(biāo)號(hào)屬性，定義m個(gè)不同的類Ci,其中i［1，m］,設(shè)Si是類Ci中的樣本個(gè)數(shù)。

設(shè)想A選測(cè)試屬性，設(shè) 子集為 中屬于Ci類別的樣本個(gè)數(shù)。利用屬性A對(duì)當(dāng)前樣本集合進(jìn)行劃分所需要的公式為：

E(A) 如果計(jì)算結(jié)果越小，就代表其子集劃分的效果越好。而對(duì)子集Sj來(lái)說(shuō),它的信息為：

或：

加入利用A樣本集合劃分當(dāng)前節(jié)點(diǎn)分支之后獲得的信息增益為：Gain(A) = I( S1 …. . Sm )－E(A)

根據(jù)屬性A 的取值來(lái)對(duì)樣本進(jìn)行集合劃分之后，得到的熵的減少量就是Gain(A)。Gain(A) 越大就說(shuō)明了測(cè)試屬性A對(duì)結(jié)果劃分分類所需的信息量比較小。所以應(yīng)該作為分類屬性出現(xiàn)。

1.2 基本思想為

(1)決策樹(shù)中每一個(gè)非葉結(jié)點(diǎn)對(duì)應(yīng)著一個(gè)非類別屬性，樹(shù)枝代表這個(gè)屬性的值。一個(gè)葉節(jié)點(diǎn)代表從樹(shù)根到葉節(jié)點(diǎn)之間的路徑對(duì)應(yīng)記錄所屬的類別屬性值。

(2)每個(gè)非葉結(jié)點(diǎn)都與具有最大信息量屬性的非類別屬性相關(guān)聯(lián)。

(3)采用信息增益的方法選擇樣本分類屬性。

度量某個(gè)屬性對(duì)樣本集合分類的好壞程度依賴于信息增益，采用了信息增益后的ID3算法建立的決策樹(shù)規(guī)模比較小，所以查詢速度比較快，在ID3決策樹(shù)歸納方法之中通常采用信息增益的方法確定每個(gè)節(jié)點(diǎn)采用到合適屬性，這樣選擇具有很高的信息增益效果，以此來(lái)作為當(dāng)前節(jié)點(diǎn)的測(cè)試屬性，這樣對(duì)之后劃分訓(xùn)練樣本子集所需要的信息就比較小?；蛘哒f(shuō)，用這種屬性對(duì)當(dāng)前節(jié)點(diǎn)所含的樣本進(jìn)行劃分，所得到的樣本中不同類別的混合程度是最低的，因此采用這樣的信息論方法有效地減少了不同對(duì)象分類所需要的次數(shù)，這樣得到的決策樹(shù)也最為簡(jiǎn)單。

2.算法的優(yōu)缺點(diǎn)與改進(jìn)

2.1 ID3算法存在的優(yōu)點(diǎn)

（1）運(yùn)算清晰簡(jiǎn)明,構(gòu)造的決策樹(shù)平均深度較小,直觀、易于理解

（2）分類速度較快,適合處理大規(guī)模問(wèn)題

（3）每次都使用了全體訓(xùn)練樣本，能有效降低個(gè)別噪聲數(shù)據(jù)的影響

（4）很好地處理離散型屬性值

2.2 ID3算法存在的缺點(diǎn)

（1）ID3算法在對(duì)根節(jié)點(diǎn)和各內(nèi)部節(jié)點(diǎn)中的分支屬性進(jìn)行選擇時(shí)，采用的標(biāo)準(zhǔn)是信息的增益量。傾向于選擇取值較多的屬性是信息增益的一大缺點(diǎn)。

（2）ID3算法具有局限性，它只能對(duì)離散型屬性的數(shù)據(jù)進(jìn)行分析。

（3）在對(duì)決策樹(shù)空間進(jìn)行遍歷的時(shí)候，ID3算法只會(huì)對(duì)單一的當(dāng)前假設(shè)實(shí)現(xiàn)維護(hù)。它無(wú)法進(jìn)一步對(duì)其訓(xùn)練樣例進(jìn)行增加，因此在每次增加實(shí)例的時(shí)候都要放棄前面的決策樹(shù)

（4）算法在搜索的過(guò)程中是不能回溯的，無(wú)論是樹(shù)的哪一層都要對(duì)屬性進(jìn)行選擇和檢測(cè)

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

經(jīng)過(guò)上述分析ID3算法的局限性可表示為：

①在整個(gè)環(huán)節(jié)當(dāng)中存在著繁瑣的對(duì)數(shù)運(yùn)算，公式計(jì)算復(fù)雜度倍增，不僅影響ID3 算法執(zhí)行的效率，還造成極大的時(shí)間開(kāi)銷。

②存在不合理的多值偏向缺陷。

由此，提出的改進(jìn)方法是：對(duì)ID3算法公式進(jìn)行改進(jìn)，化簡(jiǎn)信息熵的運(yùn)算過(guò)程，再通過(guò)對(duì)泰勒公式和麥克勞林公式的運(yùn)用，消除log對(duì)數(shù)運(yùn)算，只需要對(duì)函數(shù)進(jìn)行有限次四則運(yùn)算，同時(shí)根據(jù)粗糙集理論知識(shí)，將重要度、關(guān)聯(lián)度的概念引入到算法中以調(diào)整系數(shù)，最后會(huì)根據(jù)一個(gè)綜合評(píng)價(jià)指數(shù)來(lái)對(duì)屬性進(jìn)行選擇，用來(lái)作為決策樹(shù)生成的劃分結(jié)點(diǎn)。具體方法為：

（1）針對(duì)ID3原始算法存在的問(wèn)題，提出一種改進(jìn)后的決策樹(shù)算法。在新的算法中設(shè)定測(cè)試樣本集為U，樣本集包含的記錄數(shù)為D，樣本屬性個(gè)數(shù)為M, 關(guān)聯(lián)度為K，調(diào)整系數(shù)為5（0 < 51），樣本子集分組數(shù)的最大度量為1，綜合評(píng)價(jià)指數(shù)為NO，其中調(diào)整系數(shù)n，綜合評(píng)價(jià)指數(shù)N=K+n（關(guān)聯(lián)度不為0的時(shí)候使用），多次對(duì)多值取向問(wèn)題進(jìn)行精確改進(jìn)，避免大數(shù)據(jù)掩蓋小數(shù)據(jù)的情況發(fā)生，從而提高了算法的效率和精確度。改進(jìn)后的算法執(zhí)行步驟如下：先對(duì)要進(jìn)行決策樹(shù)生成的測(cè)試樣本集進(jìn)行確定選擇，根據(jù)不同的屬性對(duì)樣本集中的記錄數(shù)據(jù)進(jìn)行分組，得到以編號(hào)為集合的分組記錄

（2）計(jì)算按照屬性進(jìn)行分組后的各分組記錄中的最大度值

（3）根據(jù)粗糙集論中關(guān)于對(duì)屬性重要度知識(shí)的描述，計(jì)算樣本集屬性的關(guān)聯(lián)度K值

（4）根據(jù)第2步得到的最大度量1值及本次分組樣本集包含的記錄數(shù)D，計(jì)算各屬性對(duì)應(yīng)的調(diào)整系數(shù)值

（5）計(jì)算各屬性對(duì)應(yīng)的綜合評(píng)價(jià)指數(shù)NO

（6）由上一步得到的綜合評(píng)價(jià)指數(shù)N來(lái)進(jìn)行判斷，究竟選擇哪一個(gè)屬性作為結(jié)點(diǎn)進(jìn)行進(jìn)一步的劃分。

（7）重復(fù)上述步驟直到所有的葉子結(jié)點(diǎn)都?xì)w屬同一個(gè)類別時(shí)，結(jié)束結(jié)點(diǎn)的劃分工作，這樣就得到了分類決策樹(shù)，并提取分類規(guī)則。

3.算法的應(yīng)用

為了進(jìn)一步對(duì)ID3改進(jìn)算法進(jìn)行詳細(xì)描述，下面以學(xué)生成績(jī)表中的測(cè)試樣本集來(lái)簡(jiǎn)單說(shuō)明新算法的挖掘過(guò)程。

ID Name Class Math English LinearA History Policy Total 120305 BOB 3 89 94 91 86 86 446 120203 Chenli 2 99 92 86 89 92 458 120104 Dube 1 86 63 88 86 73 396 120301 Fuqi 3 98 71 59 95 58 381 120306 Jixiang 3 94 89 87 95 93 458 120206 Lgus 2 56 84 65 78 90 373 120204 Loids 2 92 96 95 91 92 466 120201 Atdlp 2 77 96 93 92 93 451 120103 Kare 1 85 99 92 92 48 416

過(guò)程如下：

1.第一先利用屬性對(duì)測(cè)試樣本集中記錄按班級(jí)進(jìn)行統(tǒng)計(jì)分組，并計(jì)算出樣本子集分組數(shù)最大度量1：

U ／班級(jí) = { 1、4、5 }、 { 2、6、7}、{3、9}

U / 是否及格 = {4、6、9 }、{ 1、2、3、5、7、8}

U / 單科第一 ={ 2、9、7、4、5、5、8 }、{ 1、3、6、9}

U / 總分 400 以上={1、2、5、7、8、9}、{3、4、6}

U / 檢驗(yàn)標(biāo)志= {1}{2}{3}{4}{5}{6}{7}{8}{9}

I/ 檢驗(yàn)標(biāo)志=1

3.計(jì)算各調(diào)整系數(shù)：

e/合格率=41/45=0.911

e/一班合格率=9/10=0.9

e/二班合格率=19/20=0.95

e/三班合格率=13/15=0.867

e/優(yōu)秀率=34/45=0.756

e/一班優(yōu)秀率=7/10=0.7

e/二班優(yōu)秀率=16/20=0.8

e/三班優(yōu)秀率=11/15=0.733

4.計(jì)算各屬性對(duì)應(yīng)的綜合評(píng)價(jià)指數(shù)：根據(jù)公式N：K + n計(jì)算各位同學(xué)的綜合評(píng)價(jià)指數(shù)。

如：Loids=5/5=1（優(yōu)秀）

5.由上一步得到的綜合評(píng)價(jià)指數(shù)N，以此為依據(jù)來(lái)對(duì)哪一個(gè)屬性作為結(jié)點(diǎn)進(jìn)行選擇，并進(jìn)一步的劃分。

6.決策樹(shù)為：

結(jié)論：本文研究了決策樹(shù)分類算法ID3，并通過(guò)對(duì)該算法的描述、改進(jìn)以及作用于高校學(xué)生成績(jī)的特征數(shù)據(jù)等步驟深化。新的算法，提高了決策樹(shù)的生成速度和精度。復(fù)雜查詢已有的數(shù)據(jù)，進(jìn)而提供更一層的數(shù)據(jù)分析功能，相信實(shí)踐改進(jìn)得到的結(jié)果將更有參考價(jià)值與應(yīng)用價(jià)值。