ID3算法原理及應(yīng)用

1、ID3算法的應(yīng)用研究摘要決策樹算法是數(shù)據(jù)挖掘領(lǐng)域的核心分類算法之一，其中ID3算法是最為經(jīng)典的決 策樹算法。ID3算法理論清晰、使用簡(jiǎn)單、學(xué)習(xí)能力較強(qiáng)，且構(gòu)造的決策樹平均深 度較小，分類速度較夬特別適合處理大規(guī)模的學(xué)習(xí)問(wèn)題，目前已得到廣泛應(yīng)用。本 文對(duì)ID3算法進(jìn)行了詳細(xì)的描述,介紹了其算法的基本原理、開展近況、及其具 體運(yùn)用。引言分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。分類技術(shù)一般是用一 種學(xué)習(xí)算法確定分類模型，該模型可以很好地?cái)M合輸入數(shù)據(jù)中類標(biāo)號(hào)和屬性集之 間的聯(lián)系。依據(jù)學(xué)習(xí)算法可以建立能夠準(zhǔn)確地預(yù)測(cè)未知樣本類標(biāo)號(hào)的模型。分類 方法的實(shí)例包括：決策樹分類法、基于規(guī)那么的分類法、

2、神經(jīng)網(wǎng)絡(luò)、支持向量級(jí)、 樸素貝葉斯分類方法等。相對(duì)于其他幾種算法而言，ID3算法理論清晰，算法簡(jiǎn) 單，是很有實(shí)用價(jià)值的實(shí)例學(xué)習(xí)算法，計(jì)算時(shí)間是例子個(gè)數(shù)、特征屬性個(gè)數(shù)、節(jié) 點(diǎn)個(gè)數(shù)屬性之積的線性函數(shù)，總預(yù)測(cè)準(zhǔn)確率較高，針對(duì)屬性選擇問(wèn)題，是決策樹 學(xué)習(xí)方法中最具影響和最為典型的算法。因此本文將詳細(xì)介紹該算法。算法基本原理在ID3決策樹歸納方法中，通常是使用信息增益方法來(lái)幫助確定生成每個(gè)節(jié)點(diǎn)時(shí) 所應(yīng)采用的合適屬性。這樣就可以選擇具有最高信息增益（燧減少的程度最大） 的屬性最為當(dāng)前節(jié)點(diǎn)的測(cè)試屬性，以便對(duì)之后劃分的訓(xùn)練樣本子集進(jìn)行分類所需 要的信息最小，也就是說(shuō)，利用該屬性進(jìn)行當(dāng)前（節(jié)點(diǎn)所含）樣本集合劃分

3、，將 會(huì)使得所產(chǎn)生的樣本子集中的“不同類別的混合程度”降為最低。因此，采用這 樣一種信息論方法將有效減少對(duì)象分來(lái)所需要的次數(shù)，從而確保所產(chǎn)生的決策樹 最為簡(jiǎn)單。設(shè)E = Fl XF2 X-XFn是n維有窮向量空間，其中鳥是有窮離散符號(hào)集,E中的元素 = 匕，匕叫做例子,其中匕，j = l,2,，n。設(shè)PE和NE是E的F兩個(gè)例子集，分別叫正例集和反例集。假設(shè)向量空間E中的正例集PE和反例集NE的大小分別為p和n ,ID3基于以下 兩個(gè)假設(shè)：（1）在向量空間E上的一棵正確決策樹，對(duì)任意例子的分類概率同E 中的正、反例的概率一致；（2） 一棵決策樹能對(duì)一例子做出正確類別判斷所需的信息量為：I (p,

4、 n) =-log2log2-p+n p+n p+n如果以屬性A作為決策樹的根，A具有v個(gè)值（匕，%，V，它將E分為v個(gè)子 集（片,2,，紇），假設(shè)中含有Pi個(gè)正例和4個(gè)反例，子集用的信息焙為I (Pi, 4),以屬性A為根分類后的信息燧為:(%) = Z=1因此，以A為根的信息增益是Gain (A)=I (p, n) - E(A) 。 ID3選擇使Gain (A)最大(即E(A)最小)的屬性作為根結(jié)點(diǎn)。對(duì)4的不同的取值對(duì)應(yīng)的E的v個(gè)子集耳遞歸調(diào)用上述過(guò)程，生成4的子結(jié)點(diǎn)，鳥，82,，與。ID3的基本原理是基于兩類分類問(wèn)題，但很容易擴(kuò)展到多類。設(shè)樣本集S共 有C類樣本，每類樣本數(shù)為pi , (

5、 i=1 , 2 , 3 ,c)。假設(shè)以屬性A作為決策樹 的根，A具有V個(gè)值匕，匕，匕，它將E分成V個(gè)子集四,生，紇，假設(shè) 片中含有j類樣本的個(gè)數(shù)為4,j = 1,2,c那么，子集與的信息量是1(g)。*log 以A為根分類的信息烯為：選擇屬性4使E(A)最小,信息增益也將增大。理想的決策樹分成3種：(1)葉節(jié)點(diǎn)數(shù)最小，(2)葉節(jié)點(diǎn)深度最??；(3)葉節(jié)點(diǎn) 數(shù)量最少且葉子結(jié)點(diǎn)深度最小。決策樹的好壞,不僅影響分類的效率,而且還影響 分類的準(zhǔn)確率。人們?yōu)榱藢で筝^優(yōu)的解，不得不尋求各種啟發(fā)式的方法。有的采 用基于屬性相關(guān)性的啟發(fā)式函數(shù);有的對(duì)生成的決策樹進(jìn)行剪枝處理;有的那么擴(kuò) 充決策樹,形成決策圖。

6、如今普遍采用的是優(yōu)化算法,基本思想:首先用ID3選擇屬性F1,建立樹T1,左、 右子樹的屬性分別為F2, F3,再以F2, F3為根,重建樹T2, T3;較Tl, T2, T3的結(jié)點(diǎn)個(gè) 數(shù),選擇結(jié)點(diǎn)最少的樹。對(duì)于選擇定樹的兒子結(jié)點(diǎn)采用同樣的方法遞歸建樹。盡 管作者用一個(gè)實(shí)驗(yàn)證明能建立理想的決策樹，但算法有較大的弱點(diǎn)：時(shí)間開銷太 大,因?yàn)槊窟x擇一個(gè)新的屬性,算法都需要建立3棵決策樹,從中選優(yōu)。算法的開展近況ID3算法的缺點(diǎn)：可能會(huì)收斂于局部最優(yōu)解而喪失全局最優(yōu)解，因?yàn)樗且环N自 頂向下貪心算法，逐個(gè)地考慮訓(xùn)練例，而不能使用新例步進(jìn)式地改進(jìn)決策樹，同 時(shí)它是一種單一變量決策樹算法，表達(dá)復(fù)雜概念時(shí)非

7、常困難；信息增益的方法往 往偏向于選擇取值較多的屬性；連續(xù)性的字段比擬難預(yù)測(cè)；當(dāng)類別太多時(shí)，錯(cuò)誤 可能就會(huì)增加的比擬快；只適合解決屬性值為離散變量的問(wèn)題；抗噪性差，比例 較難控制。后來(lái)又出現(xiàn)了 ID3算法的增量版本ID4算法和ID5算法，它們相對(duì)于小的數(shù)據(jù)集 很有效率。ID4學(xué)習(xí)算法：在每個(gè)可能的決策樹結(jié)點(diǎn)創(chuàng)造一系列表，每個(gè)表由全 部未檢測(cè)屬性值和每個(gè)值的正例和反例數(shù)組構(gòu)成，當(dāng)處理一個(gè)新例時(shí)，每個(gè)屬性 值的正例和反例遞增計(jì)量，也就是遞增概念歸納。ID4算法優(yōu)點(diǎn)：選擇性的利用 了原有規(guī)那么集和決策表，使樹結(jié)構(gòu)規(guī)那么，搜索和匹配速度很快。但它規(guī)那么前件集 中，樣本正確識(shí)別率低，對(duì)不確定性處理能力差

8、。ID5算法拋棄了舊的檢測(cè)屬性 下面的子樹，從下面選出檢測(cè)屬性形成樹。它具有學(xué)習(xí)能力強(qiáng)，保證生成和ID3 相同的判定樹，使用樹結(jié)構(gòu)、搜索匹配速度快；但上拉復(fù)雜度高，判定生成樹代 價(jià)高，規(guī)那么前件集中，樣本識(shí)別率低，對(duì)不確定性記錄處理能力差。由于ID3算 法在實(shí)際應(yīng)用中存在一些問(wèn)題，于是Quilan提出了 C4.5算法以及后來(lái)的C5.0算 法，嚴(yán)格上說(shuō)C4.5只能是ID3的一個(gè)改進(jìn)算法。C4.5算法繼承了 ID3算法的優(yōu)點(diǎn), 并在以下幾方面對(duì)ID3算法進(jìn)行了改進(jìn)：用信息增益率來(lái)選擇屬性，克服了用信 息增益選擇屬性時(shí)偏向選擇取值多的屬性的缺乏；在樹構(gòu)造過(guò)程中進(jìn)行剪枝；能 夠完成對(duì)連續(xù)屬性的離散化處

9、理；能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。但C4.5在構(gòu)造 樹的過(guò)程中，需要對(duì)數(shù)據(jù)集進(jìn)行屢次的順序掃描和排序，因而導(dǎo)致算法的低效。 此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無(wú)法在內(nèi)存容納時(shí) 程序無(wú)法運(yùn)行。此外，很多計(jì)算機(jī)的愛(ài)好者也對(duì)ID3算法和C4.5算法提出了各種各樣的改進(jìn)方 法，在此本文就不一一列舉了。算法的具體應(yīng)用實(shí)例由于ID3算法的簡(jiǎn)潔和強(qiáng)大之處，它已經(jīng)廣泛的應(yīng)用在數(shù)據(jù)挖掘和人工智能 中，在這里本文就通過(guò)考察某校學(xué)生的學(xué)習(xí)狀況為例，來(lái)展示ID3算法的一個(gè)實(shí) 際應(yīng)用。此例假定要按某校學(xué)生學(xué)習(xí)成績(jī)好壞這個(gè)概念對(duì)一個(gè)集合進(jìn)行分類,該 集合中用來(lái)描述學(xué)生的屬性有性格、父母教育程度和性別。

10、性格的取值為外向、 內(nèi)向。父母教育程度取值為良好、中等和差。性別的取值為男生、女生。例子集 中共有12名學(xué)生,如表2所示。在類別一欄,將正例即“學(xué)習(xí)成績(jī)好”的學(xué)生用“好” 標(biāo)出，反例即“學(xué)生成績(jī)差”的學(xué)生用“差”標(biāo)出。表2某學(xué)校學(xué)生的例子集這些例子一開始全部包含在根結(jié)點(diǎn)中，為了找出當(dāng)前的最正確劃分屬性,先須 根據(jù)信息論中的公式計(jì)算訓(xùn)練實(shí)例集Es的皤值。那么根節(jié)點(diǎn)的燧值為：性格父母教育程度性別類別l/l、61c661c61Entropy(Es) = - - log 2 - - - log 2 = l下面分別計(jì)算例子集中各個(gè)屬性的信息贏取值。對(duì)屬性“性格”來(lái)說(shuō)，分外 向和內(nèi)向兩個(gè)分支。當(dāng)V = “

11、外向”時(shí)，有4名“外向”小學(xué)生是“學(xué)習(xí)成績(jī)好” 的，有2名“外向”小學(xué)生是“學(xué)習(xí)成績(jī)差”的。因此， TOC o 1-5 h z 4422Entropy IE,性格,外向）二7 log 2 - 不 log 2 = 0.9183當(dāng)v = 內(nèi)向時(shí)，有2名“內(nèi)向”小學(xué)生是“學(xué)習(xí)成績(jī)好”的，有4名“內(nèi) 向”小學(xué)生是“學(xué)習(xí)成績(jī)差”的。因此，4422Entropy（EM 內(nèi)向）=一7log2 -log2 - = 0.9183o2+4 o2+4所以根據(jù)“性格”屬性來(lái)進(jìn)行例子集分類的信息贏取值為：Gain （Es,性格）=Entropy （Es） -Entropy （Esv,格）二1-（,*0.9183+,*0

12、.9183 戶 0.0817同理，對(duì)“父母教育程度”來(lái)說(shuō)來(lái)ain（Es,父母教育程度）=0.4591 ;對(duì)“性別”來(lái)說(shuō):Gain（ Es,性別）=0。因?yàn)镚ain （ Es，性別） Gain （ Es，性格） Gain （ Es ,父母教育程度） 可以看出以“父母教育程度”這個(gè)屬性進(jìn)行例子集分類的信息贏取值最大，于是 “父母教育程度”就被選為用于劃分的屬性,得到如以下圖所示的決策樹。父母教育程度良良良 , , , 向向向向向向向 / 外內(nèi)一 良 / Y L/好好修 女男男女fE tE 匕 IE4- W2 4- 4-女男男女 fa1 匚 , , , , 中中中中差,好 差 差J外向，差, 內(nèi)向，

13、差, Q外向，差,女女男男按“父母教育程度”劃分后的決策樹現(xiàn)在必須根據(jù)所提供的信息進(jìn)一步分析“父母教育程度”為“中”或“差” 的小學(xué)生的“學(xué)習(xí)成績(jī)好壞”，因此必須對(duì)“中”和“差”兩個(gè)分支的實(shí)例組成 的例子集（共8個(gè)例子）重復(fù)上述計(jì)算過(guò)程。這里簡(jiǎn)化計(jì)算過(guò)程,算出:Gain（Es, 性格）=0.3113 和Gain（Es,性別）=0.2045。因?yàn)镚ain （ Es，性別） Gain （ Es，性格），所以用屬性“性格”作第二 步劃分,于是得到如以下圖所示的決策樹。父母教育程度好 差好 差中中中請(qǐng) - 內(nèi) N女男男女差生生 女男向向Lr k 夕夕良良良良中中向向按“性格”作第二次劃分后的決策樹現(xiàn)在只有“父母教育程度”為“中”和“差”的“外向”小學(xué)生還沒(méi)有明確 類別，它們要用屬性“性別”來(lái)進(jìn)一步劃分。最終得到的決策樹如以下圖所示。, , , , 向向向向 丙外內(nèi)困良良良良女男男女中中生生 女男父母教育程度向性別一男生號(hào)一男生鰭外向，中，男生：好外向，中，女生：差物卜向，差，男生：差外向，差，女生：好最終得到的決策樹IF父母教育程度=“良”THEN學(xué)習(xí)成績(jī)=“好”IF父母教育程度=中AND性格二“內(nèi)向THEN學(xué)習(xí)成績(jī)=“差”IF父母教育程度=“差” AND性格二“內(nèi)向THEN學(xué)習(xí)成績(jī)=“差”IF父母教育程度二“中 AND性格二“外向 AND性別=“女生”THEN學(xué)習(xí)