決策樹ID3算法研究

杜威銘　冉羽

【摘 要】用于分類的數(shù)據(jù)挖掘技術(shù)的方法有很多，在這些方法中決策樹憑借其易理解、效率高等優(yōu)點(diǎn)而占有重要地位。ID3 算法是決策樹構(gòu)造方法中最為常用的實(shí)現(xiàn)方法，它在數(shù)據(jù)分類和預(yù)測領(lǐng)域得到廣泛應(yīng)用。本文重點(diǎn)總結(jié)了決策樹方法中的ID3算法的研究現(xiàn)狀，在詳細(xì)介紹ID3算法原理、算法性能的基礎(chǔ)上，總結(jié)了ID3算法以及給出了ID3算法的改進(jìn)算法。

【關(guān)鍵詞】數(shù)據(jù)挖掘；ID3算法；ID3優(yōu)化算法；決策樹

中圖分類號(hào)： TP181 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 緒論

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

1 ID3算法研究

1.1 ID3算法簡介

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

1.2 ID3算法原理

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

1.3 ID3算法描述

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

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

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

Function Create_Tree（D ， S）

Begin

（1）創(chuàng)建結(jié)點(diǎn)N；

（2）if S都在同一個(gè)類C then

（3）return N作為葉子結(jié)點(diǎn)，記為類C；

（4）if D=NULL then

（5）return N為葉子結(jié)點(diǎn)，記為S中最普通的類；

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

（7）標(biāo)記結(jié)點(diǎn)N為A；

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

（9）從結(jié)點(diǎn)N長出一個(gè)條件為A=value的分枝；

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

（11）if Bvalue=NULL then

（12）添加一個(gè)葉子結(jié)點(diǎn)，記為S中最普通的類；

（13）else 添加一個(gè)從Create_Tree（Bvalue，D–{A}）返回的結(jié)點(diǎn)。

End

1.4 ID3算法應(yīng)用實(shí)例

以表1數(shù)據(jù)為訓(xùn)練樣本集，介紹ID3算法如何生成一棵決策樹。

（1）信息熵的計(jì)算

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

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

（2）條件熵的計(jì)算

選擇屬性體溫作為劃分屬性，體溫的取值集為{正常，高，很高}，其中正常體溫人數(shù)為5，高體溫人數(shù)為6，很高體溫人數(shù)為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

此時(shí)可以算出用體溫屬性劃分訓(xùn)練集后熵的期望值為：

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

（3）信息增益的計(jì)算

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

Gain（流鼻涕）=0.5117bits

Gain（肌肉疼）=0.0038bits

Gain（頭疼）=0.0359bits

選擇具有最大信息增益的流鼻涕屬性作為根節(jié)點(diǎn)進(jìn)行決策樹的創(chuàng)建，引生出流鼻涕和不流鼻涕兩個(gè)分枝，在流鼻涕分枝，求得新劃分的信息增益：

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

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

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

選體溫作為流鼻涕分枝的結(jié)點(diǎn)，在不流鼻涕分枝，求得新劃分的信息增益：

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

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

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

我們發(fā)現(xiàn)存在相同的信息增益，則選擇分枝少的屬性作為不流鼻涕分枝的結(jié)點(diǎn)，即肌肉疼屬性。之后重復(fù)上訴步驟，完成下圖1決策樹的創(chuàng)建。

1.5 ID3算法優(yōu)缺點(diǎn)

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

2 ID3改進(jìn)算法

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

3 總結(jié)與展望

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

【參考文獻(xiàn)】

[1]Jiawei Han，Micheline Kamber. Datamining Concepts and Techniques 范明，孟小峰，譯.數(shù)據(jù)挖掘概念與技術(shù)，機(jī)械工業(yè)出版社，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]陳文偉.數(shù)據(jù)倉庫與數(shù)據(jù)挖掘教程.清華大學(xué)出版社， 2006-8.

[4]楊洋.決策樹ID3算法及其改進(jìn)[J].軟件導(dǎo)刊，2016，15（08）：46-48.

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

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