杜 麗 英

(吉林建筑大學(xué)計算機(jī)科學(xué)與工程學(xué)院，長春 130118)

0 引言

隨著數(shù)據(jù)庫技術(shù)的不斷發(fā)展，信息系統(tǒng)已普及到各個應(yīng)用領(lǐng)域.在系統(tǒng)的業(yè)務(wù)處理過程中，通常將產(chǎn)生的相關(guān)數(shù)據(jù)存儲在數(shù)據(jù)庫中，在數(shù)據(jù)庫中存儲的這些大量數(shù)據(jù)背后往往隱藏著重要的信息，這些重要信息可以輔助制定營銷策略并指導(dǎo)企業(yè)的實(shí)際決策.從大量的數(shù)據(jù)中挖掘潛在信息的過程和技術(shù)就是數(shù)據(jù)挖掘.決策樹是數(shù)據(jù)挖掘中常用的算法，主要應(yīng)用于分類和預(yù)測，具有直觀且易于理解、效率高的特點(diǎn).構(gòu)造決策樹的算法有多種，其中ID3和C4.5算法是目前決策樹算法中最有影響力的算法.ID3算法是國際上產(chǎn)生最早的決策樹分類算法，是以信息增益為標(biāo)準(zhǔn)選擇決策屬性的，C4.5是在ID3算法的基礎(chǔ)上的優(yōu)化和改進(jìn)，以信息增益率作為選擇決策屬性的標(biāo)準(zhǔn)，并在ID3算法的基礎(chǔ)上增加了對連續(xù)型數(shù)據(jù)屬性的處理[1].

1 決策樹算法

在決策樹的算法中引入了信息論的方法，用熵來衡量非葉節(jié)點(diǎn)的信息量的大小.通過構(gòu)造一顆決策樹，對訓(xùn)練樣本所屬的類別進(jìn)行分類.決策樹中的非葉節(jié)點(diǎn)表示屬性，葉子節(jié)點(diǎn)表示樣本實(shí)例所屬類別.決策樹生成算法的輸入是一組帶有類別標(biāo)記的訓(xùn)練樣本集合，構(gòu)造輸出的結(jié)果是一棵二叉或多叉的樹.

1.1 相關(guān)概念

(1) 信息熵

1) 設(shè)S為含有n個訓(xùn)練樣本的數(shù)據(jù)集，將其劃分為m個不同的類，類別集合為{S1,S2,…,Si,…Sm},每個類含有的樣本數(shù)目為ni，pi=ni/n是類別Si出現(xiàn)的概率.將S劃分為m個類的信息熵或信息期望[2]為:

2) 計算非類別屬性A的信息期望或信息熵Entropy(A).屬性A為數(shù)據(jù)集的某一屬性，A的取值為a1,a2,…av,將S劃分為v個子集{D1,D2,…Dv},Dj為A=aj的樣本數(shù)據(jù)子集，Dj的樣本數(shù)為dj,Dj數(shù)據(jù)子集中屬于子集Si的樣本數(shù)為dij,屬于第i類的概率為pij,pij=dij/dj,子集Dj的信息期望為：

當(dāng)A=aj的樣本的概率為pj=dj/n，利用屬性A進(jìn)行分類的期望信息,即A的信息熵為：

(2) 信息增益

屬性A對樣本進(jìn)行分類提供的信息量叫做屬性A的信息增益，記為Gain(A).

Gain(A)=I-Entropy(A)

(3) 信息增益率

1.2 ID3算法描述

ID3算法由J.R.Quinlan在1986年提出，把信息熵作為選擇屬性判斷的標(biāo)準(zhǔn),對訓(xùn)練樣本集合進(jìn)行分類.在構(gòu)造決策樹過程中,選擇一個屬性對樣本進(jìn)行分類劃分,使子節(jié)點(diǎn)上樣本所屬類別大部分都相同.ID3算法以信息增益作為節(jié)點(diǎn)屬性的選擇標(biāo)準(zhǔn).在對每一個非葉節(jié)點(diǎn)進(jìn)行屬性判斷時，獲取其中信息熵值最小的一個屬性作為分裂節(jié)點(diǎn).熵值反映了系統(tǒng)信息的有序程度一種度量.如果一個節(jié)點(diǎn)上的樣本所屬類別均勻分布,則稱該節(jié)點(diǎn)熵值越大,反之熵值則越小.

使用ID3算法對訓(xùn)練樣本集合構(gòu)造決策樹的基本步驟如下：

(1) 創(chuàng)建根節(jié)點(diǎn)，對要分類的訓(xùn)練樣本集合開始建樹，確定候選的屬性列表；

(2) 如果訓(xùn)練樣本集合中的樣本類別相同，則當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)，并用訓(xùn)練樣本所屬的類別對葉子節(jié)點(diǎn)進(jìn)行標(biāo)識；

(3) 否則，依次計算當(dāng)前訓(xùn)練樣本集合中各個屬性的信息增益，選擇其中信息增益值最大的屬性作為分支節(jié)點(diǎn)判斷屬性；

(4) 對于選定的分支節(jié)點(diǎn)判斷屬性，根據(jù)屬性的不同取值建立相應(yīng)的節(jié)點(diǎn)分支，進(jìn)而在分支節(jié)點(diǎn)中對應(yīng)不同的訓(xùn)練樣本子集，將當(dāng)前使用屬性從候選屬性列表中清除；

(5) 重復(fù)步驟(2)～(4)，對各訓(xùn)練樣本子集進(jìn)行遞歸劃分，構(gòu)造決策樹分支.

通過不斷的循環(huán)處理,逐層對決策樹進(jìn)行細(xì)化,直到形成一個用于對訓(xùn)練樣本集合分類的完整決策樹.

ID3算法適合處理離散值的樣本數(shù)據(jù)，不能處理連續(xù)型屬性樣本,可有效地利用決策樹的樹形結(jié)構(gòu),提取容易理解的分類決策規(guī)則，對樣本實(shí)例進(jìn)行分類.ID3算法以信息增益作為選擇判斷屬性的標(biāo)準(zhǔn)，傾向于選擇取值較多的候選屬性，并且該算法對噪聲較敏感，容易導(dǎo)致樣本的錯誤分類.

1.3 C4.5算法描述

C4.5算法是由ID3發(fā)展而來的決策樹算法，主要應(yīng)用于客戶流失預(yù)測、提升銷售和營銷等方面.C4.5算法構(gòu)造決策樹時以信息增益率為標(biāo)準(zhǔn),選擇具有信息增益率最大值的屬性作為分類屬性[3].

使用C4.5算法構(gòu)造決策樹的基本步驟如下：

(1) 對訓(xùn)練樣本集合中連續(xù)型屬性數(shù)據(jù)進(jìn)行離散化預(yù)處理；

(2) 創(chuàng)建根節(jié)點(diǎn)，并確定當(dāng)前訓(xùn)練樣本集合中的節(jié)點(diǎn)屬性；

(3) 計算當(dāng)前樣本集合中的每個屬性的信息增益率，選取其中的最大值的屬性作為分支判斷屬性；

(4) 將當(dāng)前選定的屬性作為當(dāng)前節(jié)點(diǎn)，以該屬性的不同的屬性值作為該屬性節(jié)點(diǎn)的相應(yīng)分支，依據(jù)屬性的不同分支建立相應(yīng)的訓(xùn)練樣本子集，并建立相應(yīng)節(jié)點(diǎn)；

(5) 在每個節(jié)點(diǎn)對應(yīng)的樣本子集中，將當(dāng)前使用屬性從候選的判斷屬性列表中刪除；

(6) 隊列中每個節(jié)點(diǎn)，遞歸進(jìn)行(3)～(5)步驟，直到候選屬性列表為空；

(7) 為每個葉子節(jié)點(diǎn)標(biāo)識類別屬性.

使用C4.5算法建立決策樹的過程中，以信息增益率的最大值作為選擇判斷屬性的標(biāo)準(zhǔn)，可以避免高分枝屬性不會被選取，因?yàn)榉种μ鄷箾Q策樹過分地依賴某一屬性.通過構(gòu)建的決策樹，也可以提取決策規(guī)則，對訓(xùn)練樣本和新訓(xùn)練樣本進(jìn)行分類.

1.4 ID3算法和C4.5算法分析比較

ID3算法具有理論清晰、學(xué)習(xí)比較容易等特點(diǎn).ID3算法在建立決策樹的過程中以信息增益為標(biāo)準(zhǔn)，側(cè)重于取值較多的屬性,但有些情況下，有的屬性取值較多但并不一定是最優(yōu)的.使用ID3算法對訓(xùn)練樣本集合建立決策樹后，若在原有的訓(xùn)練集的基礎(chǔ)上增加新的訓(xùn)練樣本，必須重新構(gòu)造決策樹，導(dǎo)致一定的系統(tǒng)開銷[4].

C4.5算法是在繼承ID3算法優(yōu)點(diǎn)的基礎(chǔ)上擴(kuò)展而來的,比ID3算法的計算復(fù)雜度低，效率得到了提高.C4.5以信息增益率為標(biāo)準(zhǔn)選擇節(jié)點(diǎn)屬性,不會傾向于選擇屬性值較多的屬性，克服了ID3算法的缺陷，C4.5算法增加了可處理連續(xù)數(shù)值型的屬性，彌補(bǔ)了ID3算法只能處理離散型屬性數(shù)據(jù)的不足.構(gòu)造決策樹時，在選擇分支節(jié)點(diǎn)的屬性時，若某一屬性為離散型屬性，則處理方法和ID3算法相同，按照屬性的取值數(shù)進(jìn)行計算，若屬性為連續(xù)型屬性，則需要按照某種算法進(jìn)行離散化處理.

2 結(jié)語

決策樹算法在各領(lǐng)域中有著廣泛的應(yīng)用，ID3算法與C4.5算法是決策樹中最基本、經(jīng)典的算法.決策樹算法都有各自的優(yōu)點(diǎn)和缺點(diǎn).在實(shí)際工作中，可以根據(jù)數(shù)據(jù)樣本集的大小和樣本中數(shù)據(jù)類型特點(diǎn)選擇合適的算法.決策樹技術(shù)雖然有許多優(yōu)點(diǎn)，但I(xiàn)D3和C4.5算法都存在著不穩(wěn)定性的缺點(diǎn)，在精度上也都有待進(jìn)一步提高,如何改善決策樹的預(yù)測精度，使構(gòu)造的決策樹具有更好的分類效果，如何更好地簡化決策樹的方法,需要進(jìn)行更深入的研究.

參 考 文 獻(xiàn)

[1] 李 會,胡笑梅.決策樹中ID3算法與C4.5算法分析與比較[J].水電能源科學(xué)，2008,26(2):129-132.

[2] 黃 文.決策樹的經(jīng)典算法：ID3與C4.5[J].四川文理學(xué)院學(xué)報(自然科學(xué))，2007，17(5)：16-18.

[3] 劉耀南.C4.5算法的分析及應(yīng)用[J].東莞理工學(xué)院學(xué)報，2012,19(5):47-52.

[4] 于淑香.決策樹ID3算法的研究與應(yīng)用[J].沙洲職業(yè)工學(xué)院學(xué)報,2011,14(2):27-30.