決策樹ID3算法研究

杜威銘　冉羽

【摘 要】用于分類的數據挖掘技術的方法有很多，在這些方法中決策樹憑借其易理解、效率高等優點而占有重要地位。ID3 算法是決策樹構造方法中最為常用的實現方法，它在數據分類和預測領域得到廣泛應用。本文重點總結了決策樹方法中的ID3算法的研究現狀，在詳細介紹ID3算法原理、算法性能的基礎上，總結了ID3算法以及給出了ID3算法的改進算法。

【關鍵詞】數據挖掘；ID3算法；ID3優化算法；決策樹

中圖分類號： TP181 文獻標識碼： A 文章編號： 2095-2457（2018）11-0145-002

DOI：10.19694/j.cnki.issn2095-2457.2018.11.062

【Abstract】There are many methods used to categorize data mining techniques， in which decision trees play an important role by virtue of their ease of understanding and efficiency. ID3 algorithm is the most commonly used method in decision tree construction method， which is widely used in the field of data classification and prediction. This paper focuses on the research status of ID3 algorithm in decision tree method. Based on the detailed introduction of ID3 algorithm principle， application example and algorithm performance， this paper summarizes the ID3 algorithm and the improved algorithm of ID3 algorithm.

【Key words】Data mining； ID3 algorithm； ID3 optimization algorithm； Decision tree

0 緒論

隨著軟硬件技術的發展，數據庫技術也經歷了多次演變，在信息數據量劇增的環境下，對于海量的數據以及數據背后的隱藏信息，我們期望通過更高層次的方法，尋找出模型與規則，幫助我們利用數據進行分析與決策。因此，數據挖掘技術應運而生并越發受人重視，高校、研究所與公司在該方面的研究也做了很大的投入。決策樹[1]方法作為數據挖掘中的一種重要的方法，也受到了諸多關注。下面將介紹決策樹方法中的ID3[2]（Interactive Dichotomic Version 3）算法。

1 ID3算法研究

1.1 ID3算法簡介

J·Ross Quinlan等人在1986年提出ID3算法。其核心是“信息熵”，在創建決策樹的過程中，依次查詢樣本集合中的每個屬性，選取出具有最大信息增益值的屬性，將該屬性作為測試屬性與劃分標準。通過該標準將原始數據集合劃分成多個更純的子集，并在每個子集中重復這個過程，直到分支子集中的所有樣本無法繼續分割，即樣例屬性屬于同一類別，此時一棵決策樹便創建完成。

1.2 ID3算法原理

ID3算法原理包含了信息論[3]中的信息熵和信息增益。信息熵作為屬性類別的不純性度量，熵值越高屬性的純度越低，反之越高。信息增益通過信息熵相減求得，它反映了該屬性特征在總體數據集中的重要程度。信息增益和信息熵分別有以下數學定義[4]：

1.3 ID3算法描述

下面給出ID3算法的偽代碼描述：

輸入：離散型決策屬性集合D和樣本集合S。

輸出：函數Create_Tree（D ， S）返回一棵決策樹。

Function Create_Tree（D ， S）

Begin

（1）創建結點N；

（2）if S都在同一個類C then

（3）return N作為葉子結點，記為類C；

（4）if D=NULL then

（5）return N為葉子結點，記為S中最普通的類；

（6）選擇D中擁有最大信息增益的屬性A；

（7）標記結點N為A；

（8）for each A中的未知值value

（9）從結點N長出一個條件為A=value的分枝；

（10）設Bvalue是S中A=value的樣本子集；

（11）if Bvalue=NULL then

（12）添加一個葉子結點，記為S中最普通的類；

（13）else 添加一個從Create_Tree（Bvalue，D–{A}）返回的結點。

End

1.4 ID3算法應用實例

以表1數據為訓練樣本集，介紹ID3算法如何生成一棵決策樹。

（1）信息熵的計算

用p表示感冒，n表示未感冒，初始訓練樣本感冒人數為12，未感冒人數為4，因此可求得分類前訓練集的信息熵：

H（X）=I（p，n）=-（12/16）log2（12/16）-（4/16）log2（4/16）=0.8113bits

（2）條件熵的計算

選擇屬性體溫作為劃分屬性，體溫的取值集為{正常，高，很高}，其中正常體溫人數為5，高體溫人數為6，很高體溫人數為5，則有：

體溫正常：p1=3，n1=2，I（p1，n1）=0.9710bits

體溫高：p2=3，n2=2，I（p2，n2）=0.6500bit

體溫很高：p3=3，n3=2，I（p3，n3）=0.7219bits

此時可以算出用體溫屬性劃分訓練集后熵的期望值為：

E（體溫）=（5/16）I（p1，n1）+（6/16）I（p2，n2）+（5/16）I（p3，n3）=0.7728bits

（3）信息增益的計算

Gain（體溫）=0.8113-E（體溫）=0.0385bits，同理可求得：

Gain（流鼻涕）=0.5117bits

Gain（肌肉疼）=0.0038bits

Gain（頭疼）=0.0359bits

選擇具有最大信息增益的流鼻涕屬性作為根節點進行決策樹的創建，引生出流鼻涕和不流鼻涕兩個分枝，在流鼻涕分枝，求得新劃分的信息增益：

Gain（流鼻涕，體溫）=0.1992bits

Gain（流鼻涕，肌肉疼）=0.0924bits

Gain（流鼻涕，頭疼）=0.1379bits

選體溫作為流鼻涕分枝的結點，在不流鼻涕分枝，求得新劃分的信息增益：

Gain（不流鼻涕，體溫）=0.0157bits

Gain（不流鼻涕，肌肉疼）=0.0157bits

Gain（不流鼻涕，頭疼）=0.0032bits

我們發現存在相同的信息增益，則選擇分枝少的屬性作為不流鼻涕分枝的結點，即肌肉疼屬性。之后重復上訴步驟，完成下圖1決策樹的創建。

1.5 ID3算法優缺點

通過ID3算法的偽代碼描述與實際使用，我們可以發現ID3算法是一種采用自頂向下、貪婪策略的算法。其優勢主要有以下3點：①自頂向下的搜索方式降低了搜索次數，提升了分類速度。②ID3算法原理清晰，算法思路簡單易懂，易于實現。③由于決策樹在創建的過程中都使用目前的訓練樣本，而不是根據獨立的訓練樣本遞增的做出判斷，在很大程度上降低了對個別訓練樣本錯誤的敏感性[5]。ID3算法不足主要有以下四點：①ID3算法對噪聲數據相對敏感。②ID3算法循環調用過程中會產生大量的對數運算，隨著樣本集合、屬性以及屬性取值個數的增加，對數運算次數將會大大增加，從而降低了ID3算法的運算效率，產生了極大的時間開銷。③ID3算法在建樹過程中不進行回溯導致生成的決策樹節點只是局部最優的，相對于全局，往往不是我們所期待的結果，即如多值偏向所得結果并不總是最優結果。④ID3只能分類離散型數據，對于非離散型數據需要經過預處理才能使用。

2 ID3改進算法

由于ID3算法的不足與局限性，J·Ross Quinlan于1993年對原算法進行了改進并提出了C4.5算法。該算法將信息增益率作為劃分標準，解決了ID3算法無法處理連續特征屬性的問題，同時降低了計算的復雜度，提升了分類效率。研究者還提出了如下改進算法：基于分類矩陣的ID3算法改進、基于粗糙集的ID3算法改進、基于粒計算的ID3算法改進等、基于相關系數的決策樹優化算法、基于神經網絡的分類改進算法、基于樸素貝葉斯與ID3算法的決策樹分類、粗糙模糊決策樹歸納算法等[6]。

3 總結與展望

隨著決策樹分類法再次受到人們重視，并被廣泛的研究和使用。作為決策樹中經典算法，ID3 算法使用信息增益作為分割標準，憑借其分類速度快、實現方式簡單等優點，成為了具有適用與研究價值的示例學習算法與知識獲取的有效工具。目前，ID3應用領域廣，如醫學中的病癥分類預測和基因與高分子序列分析、商業活動中的市場分析和人力資源管理、教育行業中的成績分析、高校管理等。同時，研究者們也在不斷對ID3算法進行優化與改進，提升了分類效率，獲得了更好的分類結果。在當前大數據技術背景下，會有更多ID3改進算法被提出，ID3算法也會在更多的領域得到應用。

【參考文獻】

[1]Jiawei Han，Micheline Kamber. Datamining Concepts and Techniques 范明，孟小峰，譯.數據挖掘概念與技術，機械工業出版社，2001.

[2]Quinlan J R. Induction of decision trees" Machine Learning[J]. in Data：Goals and General Description of the IN L.EN System." in， 1986：257--264.

[3]陳文偉.數據倉庫與數據挖掘教程.清華大學出版社， 2006-8.

[4]楊洋.決策樹ID3算法及其改進[J].軟件導刊，2016，15（08）：46-48.

[5]李華.基于決策樹ID3算法的改進研究[D].電子科技大學，2009.

[6]楊霖，周軍，梅紅巖，杜晶鑫.ID3改進算法研究[J].軟件導刊，2017，16（08）：21-24.