決策樹ID3算法及其改進

楊洋

摘 要：介紹了數(shù)據(jù)挖掘的相關(guān)概念，數(shù)據(jù)挖掘中決策樹ID3算法的相關(guān)概念以及信息增益和信息熵概念。通過實例介紹了ID3算法的主要內(nèi)容，指出了ID3算法的不足及改進之處。針對該實例提出ID3算法的一種改進算法——MIND算法，并通過MIND算法重新計算實例內(nèi)容。最后通過實例分析將改進算法與ID3算法進行對比，證明了改進算法的有效性。

關(guān)鍵詞關(guān)鍵詞：數(shù)據(jù)挖掘；決策樹；ID3算法；MIND算法

DOIDOI：10.11907/rjdk.161585

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2016）008-0046-03

0 引言

ID3算法屬于決策樹算法當中的一種，它是通過把實例從根結(jié)點排列到某個葉子結(jié)點來對實例進行分析，葉子結(jié)點即為實例所屬的分類[1]。決策樹上的每一個結(jié)點就是對該實例某一個屬性的測試，并且該結(jié)點的每一個后繼分支對應(yīng)著該屬性的一個可能值。分類從根節(jié)點開始，對所有的實例通過所選屬性進行分割，屬性的選擇采用最高信息增益法。停止分割的條件是：沒有屬性可以再對實例進行分割，或者結(jié)點上的實例都屬于同一目標屬性類別。ID3算法主要針對屬性選擇問題，是決策樹學習方法中最為典型的算法，該方法使用信息增益度選擇測試屬性。

MIND算法可以作為ID3算法的一種改進算法，其算法思想更方便考慮每一個概化數(shù)據(jù)元組。MIND算法是一種典型的決策樹構(gòu)造方法的構(gòu)造分類器，是采用數(shù)據(jù)庫中用戶定義的函數(shù)UDF發(fā)現(xiàn)分類規(guī)則的算法，也就是在決策樹的每一層，為每個屬性建立一張維度表，用來存放各個屬性的取值屬于哪個類別及結(jié)點編號，其優(yōu)點是通過采用UDF實現(xiàn)決策樹的構(gòu)造過程使得分類算法易于與數(shù)據(jù)庫系統(tǒng)集成。

1 數(shù)據(jù)挖掘

數(shù)據(jù)挖掘這個概念于1989年提出 [2]，指從大量模糊的、有噪聲的、不完全的、隨機的數(shù)據(jù)中挖掘出有價值的信息。隨著信息技術(shù)的發(fā)展，大數(shù)據(jù)技術(shù)廣泛應(yīng)用，數(shù)據(jù)挖掘發(fā)揮著越來越重要的作用。在數(shù)據(jù)挖掘中人們對 “啤酒與尿布”的經(jīng)典案例津津樂道：在美國超市，研究人員發(fā)現(xiàn)啤酒和尿布的銷量總成某種特殊的關(guān)聯(lián)關(guān)系，原來當父親來到超市給孩子買尿布時，總會捎帶啤酒。根據(jù)這個發(fā)現(xiàn)，超市工作人員特意將啤酒和尿布這兩個看似毫不相干的商品擺放在一起，于是這兩種商品的銷量增大，為超市帶來可觀收益。這個小小例子足以說明數(shù)據(jù)挖掘的重要性。

數(shù)據(jù)挖掘遵循一定步驟：首先要確定業(yè)務(wù)對象，然后是數(shù)據(jù)準備工作，在數(shù)據(jù)準備工作中有數(shù)據(jù)選擇、數(shù)據(jù)預(yù)處理、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)挖掘、結(jié)果分析和知識同化這些步驟，如圖1所示。

2 決策樹ID3算法基本原理

2.1 信息增益與信息熵概念

信息增益和信息熵是ID3算法中最重要的兩個概念，簡單來說，在ID3算法中，信息增益最大的節(jié)點屬性作為劃分標準，信息熵是當獲取信息時，將不確定的內(nèi)容轉(zhuǎn)為確定內(nèi)容，因此信息伴著不確定性，分別有以下數(shù)學定義：

其中，Gain值越大，說明選擇測試屬性對分類提供的信息越多。

信息熵：已知隨機樣本的集合T中的樣本個數(shù)為a，有n個互不相同的值為類別屬性，即可得到n個類別 Mi （i=1，2，…，n）。假設(shè)Mi的樣本個數(shù)為ai，則某一樣本分類需要的數(shù)學期望為：

在上述公式中，pi為樣本集合中Mi的概率值，可以用aia計算得出，對數(shù)底數(shù)可以為任何數(shù)，不同的取值對應(yīng)了熵的不同單位，通常取2。

2.2 ID3算法實現(xiàn)

下面給出一個實例。表1是不同年齡、收入、性別的人群對于買車或者不買車的一個訓練數(shù)據(jù)集。

對于給定的行，類標號屬性為買車，計數(shù)表示年齡、收入、性別在該行上具有給定值的元組數(shù)。首先計算決策屬性的熵，根據(jù)信息增益與信息熵的公式可知，設(shè)買車的人數(shù)為S1，不買車的人數(shù)為S2，P1為樣本中買車的概率值，P2為樣本中不買車的概率值，總?cè)藬?shù)為148，可知

S1=94，S2=54

P1=94/148，P2=54/148I（S1，S2）=I（94，54）=-P1log2P1-P2log2P2=0.9388

條件屬性一共有3個，年齡、收入、性別，分別計算這3個條件屬性的信息增益，以計算年齡的信息熵與信息增益為例。年齡分青年、中年、老年3個組。青年買的人數(shù)為22，所占比例為22/38，不買的人數(shù)為16，所占比例為16/38，則青年的信息熵為-0.58log20.58-0.42log20.42=0.9832。同理可得中年的信息熵為0.971，老年的信息熵為0.242。

青年所占整體人數(shù)比重為38/148=0.26，中年所占整體人數(shù)的比重為60/148=0.41，老年所占整體人數(shù)的比重為50/148=0.33。

則年齡的平均期望為：

E（年齡）=0.26*0.9832+0.41*0.971+0.33*0.242=0.7336

年齡的信息增益為：

G（年齡）=0.9388-0.7336=0.2052

同理可算出收入的信息增益為0.6628，性別的信息增益為0.3858，可知收入的信息增益是最大的，因此選擇性別為決策樹的根結(jié)點，如圖2所示。

找到了根結(jié)點后，其它葉子結(jié)點的尋找過程與根結(jié)點的尋找過程一樣。

3 決策樹ID3算法的改進算法

3.1 ID3算法的不足

雖然ID3算法理解簡單，使用方便，適用于處理大規(guī)模的學習問題，但是ID3算法并不適應(yīng)所有的數(shù)據(jù)挖掘和機器學習問題， ID3算法效率較低。下面歸納出ID3算法的不足之處：

（1） 因為ID3算法為一種貪心算法，即在對問題求解時，總是做出目前狀況下的最好選擇。換句話說，在算法過程中，不從整體最優(yōu)上加以考慮，算法選擇只是某種意義上的局部最優(yōu)解。因此，ID3算法的決策樹搜索是無回溯的，很有可能在得到局部最優(yōu)解后丟失了全局最優(yōu)解。

（2） ID3算法只能處理離散屬性，對于連續(xù)值的屬性，必須首先對其進行離散化處理才能投入使用。比如年齡屬性就是一個連續(xù)值屬性，在ID3算法中對這種連續(xù)值屬性是無法進行計算的，必須先將年齡屬性離散化才能進行下一步計算。

（3） ID3的決策樹計算中，每個葉子節(jié)點都必須要有屬性值才能進行計算，但是并不是每個節(jié)點都必須擁有屬性值，如果樣本的某個屬性缺少對應(yīng)的屬性值，那么ID3算法計算將無法繼續(xù)，只能對缺省值進行賦值才能繼續(xù)計算。

3.2 ID3改進算法實現(xiàn)

由ID3算法可知，生成決策樹的關(guān)鍵是找到根結(jié)點，ID3算法是計算各個屬性的信息熵和信息增益來尋找根結(jié)點的。下面介紹ID3算法的一種改進算法——MIND算法，通過計算各個屬性的基尼系數(shù)來尋找到根結(jié)點以及葉子結(jié)點。

基尼系數(shù)或譯堅尼系數(shù)，是20世紀初由意大利經(jīng)濟學家基尼根據(jù)勞倫斯曲線所定義的判斷收入分配公平程度的指標。 基尼系數(shù)是一個比例數(shù)值，在0和1之間，是國際上用來綜合考察居民內(nèi)部收入分配差異狀況的一個重要指標。我們可以利用基尼系數(shù)的思想來計算屬性的分配程度，從而選擇決策樹的根結(jié)點。

MIND算法具體操作：將各個屬性按類別分成不同的小樹。

因為買/不買為類標號屬性，因此令S1（買）=94，S2（不買）=54。

計算年齡屬性的基尼系數(shù)，已知青年中買的人數(shù)為22，不買的人數(shù)為16，因此記為青（22，16），中年中買的人數(shù)為24，不買的人數(shù)為36，因此記為中（24，36），老年中買的人數(shù)為48，不買的人數(shù)為2，因此記為老（48，2）。

Gini（青）=1-[（2238）2+（1638）2]=0.488

Gini（中）=1-[（2460）2+（3660）2]=0.48

Gini（老）=1-[（4850）2+（250）2]=0.0768

由上式可知，年齡屬性的基尼系數(shù)為

Gini（年齡）=38148×0.488+60148×0.48+50148×0.0768=0.346

計算收入屬性的基尼系數(shù)：已知低收入中買的人數(shù)為2，不買的人數(shù)為34，因此記為低（2，34）；中收入中買的人數(shù)為12，不買的人數(shù)為20，因此記為中（12，20）；高收入中買的人數(shù)為80，不買的人數(shù)為0，因此記為高（80，0）。計算得：Gini（低）=0.105，Gini（中）=0.469，Gini（高）=0，Gini（收入）=0.127。

計算性別屬性的基尼系數(shù)：已知男性中買的人數(shù)為50，不買的人數(shù)為34，因此記為男（50，34）；女性中買的人數(shù)為44，不買的人數(shù)為20，因此記為女（44，20）。計算得：Gini（男）=0.482，Gini（女）=0.43，Gini（性別）=0.46。

由上述計算可知，收入的基尼系數(shù)是最小的，因此選擇收入作為決策樹的根結(jié)點，這個結(jié)論與ID3算法一樣。根結(jié)點決策樹與圖2一致。

4 結(jié)語

本文利用一種新的MIND算法對ID3算法進行改進，從而實現(xiàn)尋找到?jīng)Q策樹根結(jié)點的簡便計算方法。新算法引入基尼系數(shù)概念，可以適當減少非重要屬性的信息量，相應(yīng)減少ID3算法對取值較多的屬性依賴性，使整個運算更加獨立，從而改善分類規(guī)則和結(jié)果。

參考文獻：

[1]譚建豪，章兢，黃耀，等. 數(shù)據(jù)挖掘技術(shù)[M].北京：中國水利水電出版社，2009：16-148.

[2]DAVIDSON IAN，TAYI GIRI. Data preparation using data quality matrices for classification mining[J]. European Journal of Operational Research，2009， 197（2）：764-772.

[3]朱付寶，霍曉齊，徐顯景. 基于粗糙集的ID3決策樹算法改進[J].鄭州輕工業(yè)學院學報：自然科學版，2015，30（1）：50-54.

[4]王小巍，蔣玉明.決策樹ID3算法的分析與改進[J].計算機工程與設(shè)計，2011，32（9）：3070-3072.

（責任編輯：杜能鋼）