杜威銘　冉羽

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

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

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

1 ID3算法研究

1.1 ID3算法簡(jiǎn)介

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

1.2 ID3算法原理

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

1.3 ID3算法描述

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

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

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

Function Create_Tree（D ， S）

Begin

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

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

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

（4）if D=NULL then

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

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

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

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

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

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

（11）if Bvalue=NULL then

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

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

End

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

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

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

用p表示感冒，n表示未感冒，初始訓(xùn)練樣本感冒人數(shù)為12，未感冒人數(shù)為4，因此可求得分類(lèi)前訓(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)行決策樹(shù)的創(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決策樹(shù)的創(chuàng)建。

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

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

2 ID3改進(jìn)算法

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

3 總結(jié)與展望

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

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

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

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