ID3的基本思想和算法分析

1、第1章決策樹方法在數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)挖掘的應(yīng)用中，分類是一種非常重要的方法分類的概念是在已有數(shù)據(jù)的基礎(chǔ)上學(xué)會(huì)一個(gè)分類函數(shù)或構(gòu)造出一個(gè)分類模型（即我們通常所說(shuō)的分類器(Classifier）該函數(shù)或模型能夠把數(shù)據(jù)庫(kù)中的數(shù)據(jù)紀(jì)錄映射到給定類別中的某一個(gè)，從而可以應(yīng)用于數(shù)據(jù)預(yù)測(cè)分類的主要算法有：貝葉斯算法、決策樹算法（如ID3、C4.5等）、規(guī)則推導(dǎo)、人工神經(jīng)網(wǎng)絡(luò)、最近鄰算法、支持向量機(jī)等等這些算法在許多現(xiàn)實(shí)數(shù)據(jù)集合上可以做比較精確的數(shù)據(jù)預(yù)測(cè)，為人們的生活、生產(chǎn)、學(xué)習(xí)、研究提供了有效的途徑其中決策樹算法具有良好的可解釋性，在實(shí)踐中的應(yīng)用最為廣泛決策樹分類算法的一個(gè)典型代表就是ID3算法1.1 概述1.1

2、.1 學(xué)習(xí)的相關(guān)概念分類是在一個(gè)作為輸入的訓(xùn)練集合上學(xué)會(huì)一個(gè)分類函數(shù)或構(gòu)造出一個(gè)分類模型，即我們通常所說(shuō)的分類器(Classifier)，然后利用它對(duì)數(shù)據(jù)集合中沒(méi)有類標(biāo)的實(shí)例指派最適合的類標(biāo)。分類是在一個(gè)作為輸入的訓(xùn)練集合上學(xué)會(huì)一個(gè)分類函數(shù)或構(gòu)造出一個(gè)分類模型，即我們通常所說(shuō)的分類器(Classifier)，然后利用它對(duì)數(shù)據(jù)集合中沒(méi)有類標(biāo)的實(shí)例指派最適合的類標(biāo)分類用于預(yù)測(cè)數(shù)據(jù)對(duì)象的類別如可以構(gòu)造一個(gè)分類模型來(lái)對(duì)銀行貸款進(jìn)行風(fēng)險(xiǎn)評(píng)估（安全或危險(xiǎn)）機(jī)器學(xué)習(xí)、專家系統(tǒng)、統(tǒng)計(jì)學(xué)和神經(jīng)生物學(xué)等領(lǐng)域的研究人員已經(jīng)提出了許多具體的分類方法，如貝葉斯方法、決策樹、規(guī)則推導(dǎo)、人工神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、基于實(shí)例的

3、方法等訓(xùn)練集合是由一組數(shù)據(jù)實(shí)例構(gòu)成，每個(gè)實(shí)例是一個(gè)由有關(guān)字段組成的特征向量，這些字段被稱為屬性（Attribute），用于分類的屬性被叫做類標(biāo)，類標(biāo)屬性也就是訓(xùn)練集合的類別標(biāo)記一個(gè)具體的實(shí)例形式可以表示為(a1, a2, , an, c), 其中ai (i=1, 2, , n) 表示屬性字段值，c 表示類標(biāo)給定訓(xùn)練數(shù)據(jù)集合D=x1, x2 , , xn, 分類任務(wù)的目標(biāo)是對(duì)數(shù)據(jù)集合D進(jìn)行分析，確定一個(gè)映射函數(shù)f: (A1, A2, , An)C ，使得對(duì)任意的未知類別的實(shí)例xi=(a1, a2 , , an)可標(biāo)以適當(dāng)?shù)念悩?biāo)*訓(xùn)練集合是構(gòu)造分類器的基礎(chǔ)訓(xùn)練集合是包含一些屬性的一個(gè)數(shù)據(jù)庫(kù)表格，其

4、中的一個(gè)屬性被制定為分類標(biāo)簽標(biāo)簽屬性的類型一般要求是離散的，且標(biāo)簽屬性的可能值的數(shù)目越少越好（最好是兩或三個(gè)值）標(biāo)簽值的數(shù)目越少，構(gòu)造出來(lái)的分類器的錯(cuò)誤率越低訓(xùn)練集合是由一組數(shù)據(jù)實(shí)例構(gòu)成，每個(gè)實(shí)例是一個(gè)由有關(guān)字段組成的特征向量，這些字段被稱為屬性（Attribute），用于分類的屬性被叫做類標(biāo)，類標(biāo)屬性也就是訓(xùn)練集合的類別標(biāo)記。一個(gè)具體的實(shí)例形式可以表示為(a1, a2, , an, c), 其中ai (i=1, 2, , n) 表示屬性字段值，c 表示類標(biāo)。給定訓(xùn)練數(shù)據(jù)集合D=x1, x2 , , xn，分類任務(wù)的目標(biāo)是對(duì)數(shù)據(jù)集合D進(jìn)行分析，確定一個(gè)映射函數(shù)f: (A1, A2, , An)

5、C ，使得對(duì)任意的未知類別的實(shí)例xi=(a1, a2 , , an)可標(biāo)以適當(dāng)?shù)念悩?biāo)*。監(jiān)督學(xué)習(xí)和非監(jiān)督學(xué)習(xí)的區(qū)別機(jī)器學(xué)習(xí)方法分為有監(jiān)督的學(xué)習(xí)和無(wú)監(jiān)督的學(xué)習(xí)有監(jiān)督的學(xué)習(xí)需要給出不同類別的實(shí)例作為訓(xùn)練實(shí)例，由這些訓(xùn)練實(shí)例得到類的描述，然后給新的測(cè)試實(shí)例匹配類標(biāo)無(wú)監(jiān)督的學(xué)習(xí)是在給定實(shí)例集合上，根據(jù)其內(nèi)容，在無(wú)先驗(yàn)知識(shí)的條件下，將實(shí)例分成有意義的類其中有監(jiān)督的學(xué)習(xí)從學(xué)習(xí)過(guò)程的任務(wù)實(shí)施方式上可以分成兩種極端的情況，即急切式學(xué)習(xí)策略和懶惰式學(xué)習(xí)策略急切式學(xué)習(xí)策略在分類器訓(xùn)練階段就建立將待分類實(shí)例映射到其預(yù)測(cè)類標(biāo)上的一個(gè)有清晰假設(shè)的分類器學(xué)習(xí)的過(guò)程是在訓(xùn)練數(shù)據(jù)集合上建立分類器的過(guò)程，它同分類過(guò)程是相分離的

6、一般的決策樹算法就是典型的代表而懶惰式學(xué)習(xí)算法沒(méi)有建立清晰的假設(shè)，分類過(guò)程就是利用訓(xùn)練集合將給定實(shí)例與其類標(biāo)匹配起來(lái)的過(guò)程，學(xué)習(xí)過(guò)程和學(xué)習(xí)結(jié)果的應(yīng)用過(guò)程是同時(shí)進(jìn)行的采用急切式學(xué)習(xí)策略的分類器，即對(duì)于給定的訓(xùn)練實(shí)例集合，在訓(xùn)練階段就建立好一個(gè)分類器，在分類階段直接地使用該分類器來(lái)給一個(gè)待分類實(shí)例分類Fridman等的TAN分類器就是一種采用急切式學(xué)習(xí)策略的分類器采用懶惰式學(xué)習(xí)策略的分類器，在訓(xùn)練階段不建立一個(gè)清晰的假設(shè)，而在分類階段使用訓(xùn)練集合來(lái)將給定實(shí)例與其類標(biāo)匹配起來(lái)，即在分類時(shí)利用訓(xùn)練集合和測(cè)試實(shí)例建立分類規(guī)則為該測(cè)試實(shí)例來(lái)分類LBR分類器就是采用了一種完全懶惰的學(xué)習(xí)方法；基于實(shí)例的分類也

7、采用了懶惰式學(xué)習(xí)策略一般來(lái)講，對(duì)于同一種模型技術(shù)，急切式學(xué)習(xí)策略在效率上大大優(yōu)于懶惰式學(xué)習(xí)策略，而懶惰式學(xué)習(xí)策略在分類精確度上優(yōu)于急切式學(xué)習(xí)策略為了使分類器在能夠在效率和分類精確度上都達(dá)到令人滿意的水平，可以對(duì)上述兩種學(xué)習(xí)策略進(jìn)行研究，對(duì)同一種分類模型找到一個(gè)采用急切式學(xué)習(xí)策略和懶惰式學(xué)習(xí)策略的平衡點(diǎn)這是分類器研究的一個(gè)突破點(diǎn)，也是本文的研究點(diǎn)之一分類的概念分類是在一個(gè)作為輸入的訓(xùn)練集合上學(xué)會(huì)一個(gè)分類函數(shù)或構(gòu)造出一個(gè)分類模型，即我們通常所說(shuō)的分類器(Classifier)，然后利用它對(duì)數(shù)據(jù)集合中沒(méi)有類標(biāo)的實(shí)例指派最適合的類標(biāo)訓(xùn)練集合是由一組數(shù)據(jù)實(shí)例構(gòu)成，每個(gè)實(shí)例是一個(gè)由有關(guān)字段組成的特征向量，

8、這些字段被稱為屬性（Attribute），用于分類的屬性被叫做類標(biāo)，類標(biāo)屬性也就是訓(xùn)練集合的類別標(biāo)記一個(gè)具體的實(shí)例形式可以表示為(a1, a2, , an, c), 其中ai (i=1, 2, , n) 表示屬性字段值，c 表示類標(biāo)給定訓(xùn)練數(shù)據(jù)集合D=x1, x2 , , xn，分類任務(wù)的目標(biāo)是對(duì)數(shù)據(jù)集合D進(jìn)行分析，確定一個(gè)映射函數(shù)f: (A1, A2, , An)C ，使得對(duì)任意的未知類別的實(shí)例xi=(a1, a2 , , an)可標(biāo)以適當(dāng)?shù)念悩?biāo)*18訓(xùn)練集合是構(gòu)造分類器的基礎(chǔ)訓(xùn)練集合是包含一些屬性的一個(gè)數(shù)據(jù)庫(kù)表格，其中的一個(gè)屬性被制定為分類標(biāo)簽標(biāo)簽屬性的類型一般要求是離散的，且標(biāo)簽屬性的可

9、能值的數(shù)目越少越好（最好是兩或三個(gè)值）標(biāo)簽值的數(shù)目越少，構(gòu)造出來(lái)的分類器的錯(cuò)誤率越低分類用于預(yù)測(cè)數(shù)據(jù)對(duì)象的類別如可以構(gòu)造一個(gè)分類模型來(lái)對(duì)銀行貸款進(jìn)行風(fēng)險(xiǎn)評(píng)估（安全或危險(xiǎn)）機(jī)器學(xué)習(xí)、專家系統(tǒng)、統(tǒng)計(jì)學(xué)和神經(jīng)生物學(xué)等領(lǐng)域的研究人員已經(jīng)提出了許多具體的分類方法，如貝葉斯方法、決策樹、規(guī)則推導(dǎo)、人工神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、基于實(shí)例的方法等1.1.2 監(jiān)督學(xué)習(xí)機(jī)器學(xué)習(xí)方法分為有監(jiān)督的學(xué)習(xí)和無(wú)監(jiān)督的學(xué)習(xí)有監(jiān)督的學(xué)習(xí)需要給出不同類別的實(shí)例作為訓(xùn)練實(shí)例，由這些訓(xùn)練實(shí)例得到類的描述，然后給新的測(cè)試實(shí)例匹配類標(biāo)無(wú)監(jiān)督的學(xué)習(xí)是在給定實(shí)例集合上，根據(jù)其內(nèi)容，在無(wú)先驗(yàn)知識(shí)的條件下，將實(shí)例分成有意義的類其中有監(jiān)督的學(xué)習(xí)從學(xué)習(xí)

10、過(guò)程的任務(wù)實(shí)施方式上可以分成兩種極端的情況，即急切式學(xué)習(xí)策略和懶惰式學(xué)習(xí)策略急切式學(xué)習(xí)策略在分類器訓(xùn)練階段就建立將待分類實(shí)例映射到其預(yù)測(cè)類標(biāo)上的一個(gè)有清晰假設(shè)的分類器學(xué)習(xí)的過(guò)程是在訓(xùn)練數(shù)據(jù)集合上建立分類器的過(guò)程，它同分類過(guò)程是相分離的一般的決策樹算法就是典型的代表而懶惰式學(xué)習(xí)算法沒(méi)有建立清晰的假設(shè)，分類過(guò)程就是利用訓(xùn)練集合將給定實(shí)例與其類標(biāo)匹配起來(lái)的過(guò)程，學(xué)習(xí)過(guò)程和學(xué)習(xí)結(jié)果的應(yīng)用過(guò)程是同時(shí)進(jìn)行的采用急切式學(xué)習(xí)策略的分類器，即對(duì)于給定的訓(xùn)練實(shí)例集合，在訓(xùn)練階段就建立好一個(gè)分類器，在分類階段直接地使用該分類器來(lái)給一個(gè)待分類實(shí)例分類Fridman等的TAN分類器就是一種采用急切式學(xué)習(xí)策略的分類器采用

11、懶惰式學(xué)習(xí)策略的分類器，在訓(xùn)練階段不建立一個(gè)清晰的假設(shè)，而在分類階段使用訓(xùn)練集合來(lái)將給定實(shí)例與其類標(biāo)匹配起來(lái)，即在分類時(shí)利用訓(xùn)練集合和測(cè)試實(shí)例建立分類規(guī)則為該測(cè)試實(shí)例來(lái)分類LBR分類器就是采用了一種完全懶惰的學(xué)習(xí)方法；基于實(shí)例的分類也采用了懶惰式學(xué)習(xí)策略一般來(lái)講，對(duì)于同一種模型技術(shù)，急切式學(xué)習(xí)策略在效率上大大優(yōu)于懶惰式學(xué)習(xí)策略，而懶惰式學(xué)習(xí)策略在分類精確度上優(yōu)于急切式學(xué)習(xí)策略為了使分類器在能夠在效率和分類精確度上都達(dá)到令人滿意的水平，可以對(duì)上述兩種學(xué)習(xí)策略進(jìn)行研究，對(duì)同一種分類模型找到一個(gè)采用急切式學(xué)習(xí)策略和懶惰式學(xué)習(xí)策略的平衡點(diǎn)這是分類器研究的一個(gè)突破點(diǎn)，也是本文的研究點(diǎn)之一應(yīng)用變量類型和術(shù)

12、語(yǔ)的相關(guān)規(guī)定得到學(xué)習(xí)問(wèn)題規(guī)范的數(shù)學(xué)表達(dá)-統(tǒng)計(jì)學(xué)習(xí)基礎(chǔ)第二章1.1.3 學(xué)習(xí)問(wèn)題實(shí)例介紹可在以后發(fā)現(xiàn)實(shí)際應(yīng)用例子時(shí)再寫這部分。股票數(shù)據(jù)分析、臨床數(shù)據(jù)診斷應(yīng)用、垃圾郵件的判別-相關(guān)論文在金融方面，銀行和金融機(jī)構(gòu)往往持有大量的關(guān)于客戶的，各種服務(wù)的以及交易事務(wù)的數(shù)據(jù)，并且這些數(shù)據(jù)通常比較完整，可靠和高質(zhì)量，這大大方便了系統(tǒng)化的數(shù)據(jù)分析和數(shù)據(jù)挖掘在銀行中，數(shù)據(jù)挖掘被用來(lái)建模，預(yù)測(cè)，識(shí)別偽造信用卡，估計(jì)風(fēng)險(xiǎn)，進(jìn)行趨勢(shì)分析，效益分析，顧客分析等在此領(lǐng)域運(yùn)用數(shù)據(jù)挖掘，可以進(jìn)行貸款償付預(yù)測(cè)和客戶信用政策分析，以調(diào)整貸款發(fā)放政策，降低經(jīng)營(yíng)風(fēng)險(xiǎn)信用卡公司可以應(yīng)用數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則來(lái)識(shí)別欺詐比如銀行想知道顧客源在

13、什么樣的優(yōu)惠后可以來(lái)開新賬戶，什么條件下顧客可能會(huì)注銷已有的賬戶例如，我們想預(yù)測(cè)信用卡欺詐行為，可以通過(guò)計(jì)算機(jī)算法分析信用卡用戶的購(gòu)買習(xí)慣，從而認(rèn)識(shí)客戶的模式，并分辨出偏離模式的信用卡盜用行為使用上面的模型和方法，該學(xué)習(xí)的過(guò)程首先需要有一個(gè)訓(xùn)練階段，提供正反兩面方面的偏離例子用挖掘程序來(lái)訓(xùn)練訓(xùn)練之后，算法應(yīng)能推導(dǎo)出合法交易的定義，并能預(yù)測(cè)一個(gè)新的交易是合法的還是非法的智能數(shù)據(jù)挖掘利用了廣泛的高質(zhì)量的機(jī)器學(xué)習(xí)算法，它能夠在應(yīng)付大量數(shù)據(jù)的同時(shí)，又保證理想的響應(yīng)時(shí)間，使得市場(chǎng)分析，風(fēng)險(xiǎn)預(yù)測(cè)，欺詐管理，客戶關(guān)系管理和競(jìng)爭(zhēng)優(yōu)勢(shì)分析等應(yīng)用成為可以在醫(yī)療領(lǐng)域中，成堆的電子數(shù)據(jù)可能已放在那兒很多年了，比如病人

14、，癥狀，發(fā)病時(shí)間，發(fā)病頻率以及當(dāng)時(shí)的用藥種類，劑量，住院時(shí)間等在藥物實(shí)驗(yàn)中，可能有很多種不同的組合，每種若加以實(shí)驗(yàn)，則成本太大，決策樹方法可以被用來(lái)大減少實(shí)驗(yàn)次數(shù)這種方法已被許多大的制藥公司所采用生物醫(yī)學(xué)的大量研究大都集中在DNA數(shù)據(jù)的分析上人類大約有105個(gè)基因，幾乎是不計(jì)其數(shù)因此，數(shù)據(jù)挖掘成為DNA分析中的強(qiáng)力工具，如：對(duì)DNA序列間的相似搜索和比較；應(yīng)用關(guān)聯(lián)分析對(duì)同時(shí)出現(xiàn)的基因序列的識(shí)別；應(yīng)用路徑分析發(fā)現(xiàn)在疾病不同階段的致病基因等電信業(yè)已經(jīng)迅速?gòu)膯渭兊奶峁┦性捄烷L(zhǎng)途服務(wù)變?yōu)榫C合電信服務(wù)，如語(yǔ)音，傳真，移動(dòng)電話，電子郵件，互聯(lián)網(wǎng)接入服務(wù)電信市場(chǎng)的競(jìng)爭(zhēng)也變得越來(lái)越激烈和全方位化利用數(shù)據(jù)挖掘來(lái)

15、幫助理解商業(yè)行為，對(duì)電信數(shù)據(jù)的多維分析，檢測(cè)非典型的使用模式以尋找潛在的盜用者，分析用戶一系列的電信服務(wù)使用模式來(lái)改進(jìn)服務(wù)，根據(jù)地域分布疏密性找出最急需建立網(wǎng)點(diǎn)的位置，確定電信模式，捕捉盜用待業(yè)，更好的利用資源和提高服務(wù)質(zhì)量是非常必要的借助數(shù)據(jù)挖掘，可以減少很多損失，保住顧客1.2 信息論基礎(chǔ)主要把所涉及的信息論進(jìn)行較系統(tǒng)介紹，注意要舉例說(shuō)明。為了尋找對(duì)樣本進(jìn)行分類的最優(yōu)方法，我們要做的工作就是使對(duì)一個(gè)樣本分類時(shí)需要問(wèn)的問(wèn)題最少（即樹的深度最?。┮虼耍覀冃枰撤N函數(shù)據(jù)來(lái)衡量哪些問(wèn)題將提供最為平衡的劃分，信息增益就是這樣的函數(shù)之一1.2.1信息和熵的概念那么信息熵的定義為：設(shè)是訓(xùn)練樣本集，它包

16、含n 個(gè)類別的樣本，這些類別分別用C1, C2, ,Cn, 表示，若給定的概率分布Pi=（P1, P2, Pn ）表示Ci的概率，則由該分布傳遞的信息量稱為P的信息熵，記為：屬性A相對(duì)實(shí)例集合S的信息增益gain(S,A)定義為：1.2.2 信息增益的概念與其他度量方式信息增益用來(lái)衡量熵的期望減少值，因此使用屬性A相對(duì)實(shí)例集合S進(jìn)行的劃分獲得的信息增益gain(S, A)定義為：gain(S, A)是指因?yàn)橹缹傩訟的值后導(dǎo)致的熵的期望壓縮gain(S, A)越大，說(shuō)明選擇測(cè)試屬性A對(duì)分類提供的信息越多因?yàn)殪卦叫〈砉?jié)點(diǎn)越純，按照信息增益的定義，信息增益越大，熵的減小量也越大，節(jié)點(diǎn)就趨向于更純

17、因此，可以對(duì)每個(gè)屬性按照它們的信息增益大小排序，獲得最大信息增益的屬性被選擇為分支屬性1.2.3 雜度函數(shù)及相關(guān)概念數(shù)據(jù)挖掘原理與算法、信息論相關(guān)書籍！1.3 決策樹算法1.3.1 決策樹基本算法概述決策樹算法是一種常用的數(shù)據(jù)挖掘算法，它是從機(jī)器學(xué)習(xí)領(lǐng)域中逐漸發(fā)展起來(lái)的一種分類函數(shù)逼近方法決策樹學(xué)習(xí)的基本算法是貪心算法，采用自頂向下的遞歸方式構(gòu)造決策樹目前利用決策樹進(jìn)行數(shù)據(jù)分類的方法已經(jīng)被深入地研究，并且形成了許多決策樹算法決策樹算法的分類模型是一棵有向無(wú)環(huán)樹，除了根節(jié)點(diǎn)以外，決策樹的每個(gè)節(jié)點(diǎn)有且僅有一個(gè)父節(jié)點(diǎn)每個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)一個(gè)類標(biāo)號(hào)，它的值就是使用決策樹對(duì)未知樣本分類的類標(biāo)號(hào)的值每個(gè)內(nèi)部節(jié)點(diǎn)

18、都對(duì)應(yīng)一個(gè)分支方案，它包括用于節(jié)點(diǎn)分裂的屬性和分支的判斷規(guī)則q訓(xùn)練樣本的屬性分為數(shù)值屬性和分類屬性，數(shù)值屬性的取值范圍是一個(gè)連續(xù)的區(qū)間，比如實(shí)數(shù)集；而分類屬性的取值范圍則是離散值的集合，比如屬性性別的取值范圍就是集合男，女如果屬性是數(shù)值屬性，那么q的形式是S是的取值范圍（）的子集在數(shù)學(xué)上可以對(duì)決策樹分類器作如下表述：給定樣本集，其中的樣本屬性c個(gè)類別，用i表示中屬于第i類的樣本集定義一個(gè)指標(biāo)集1, 2數(shù)學(xué)公式之中數(shù)字與標(biāo)點(diǎn)符號(hào)要使用英文“半角”標(biāo)點(diǎn)符號(hào)（隨后加空格）。, , c和一個(gè)的非空子集的集合1, 2, b我們可以令當(dāng)ii時(shí)，ii一個(gè)廣義決策規(guī)則f就是到的一個(gè)映射（記為f：）若f把第i類

19、的某個(gè)樣本映射到包含i的那個(gè)子集Ik中，則識(shí)別正確設(shè)Q（, ）是由樣本集和指標(biāo)集所形成的所有可能的映射的集合，則Q（, ）可表示為由（ai, i）所組成的集合，元素（ai, i）稱為一個(gè)節(jié)點(diǎn)，ai是該節(jié)點(diǎn)上表征這種映射的參數(shù)，ii1, i2, 是該節(jié)點(diǎn)上指標(biāo)集i的非空子集的集合令ni和nj是T（, ）的兩個(gè)元素，其中、若則稱ni為nj的父節(jié)點(diǎn)，或稱nj為ni的子節(jié)點(diǎn)設(shè)Q（, ，）是節(jié)點(diǎn)的有限集，且nB中沒(méi)有一個(gè)元素是n的父節(jié)點(diǎn)，則稱n是的根節(jié)點(diǎn)當(dāng)Q（, ，）滿足下列條件時(shí)，它就是一個(gè)決策樹分類器(1)中有一個(gè)并且只有一個(gè)根節(jié)點(diǎn)(2)設(shè)ni和nj是中的兩個(gè)不同元素，則(3)對(duì)于每一個(gè)iI，中存在

20、一個(gè)節(jié)點(diǎn)且中有一個(gè)元素是i（與它對(duì)應(yīng)的n的子節(jié)點(diǎn)叫葉節(jié)點(diǎn)，又稱終止節(jié)點(diǎn)）1.3.2 決策樹生成算法概述通用的自頂向下構(gòu)建決策樹的算法決策樹的深度優(yōu)先構(gòu)建算法輸入：節(jié)點(diǎn)，訓(xùn)練數(shù)據(jù)集，分支指標(biāo)輸出：以節(jié)點(diǎn)為根節(jié)點(diǎn)的基于數(shù)據(jù)集，分支指標(biāo)的決策樹Procedure make_tree(N, D, SI) 初始化根節(jié)點(diǎn)在中計(jì)算，求解節(jié)點(diǎn)的分支方案；If(節(jié)點(diǎn)滿足分支條件)選擇最好的分支方案將分為1，2；創(chuàng)建的子節(jié)點(diǎn)1，2；make_tree(N1, D1, SI)make_tree(N, D, SI)endifend1.3.3 決策樹修剪算法介紹在樹的構(gòu)建階級(jí)生成的決策樹依賴于訓(xùn)練樣本，因此它可能存在對(duì)

21、訓(xùn)練樣本的過(guò)度適應(yīng)問(wèn)題例如，訓(xùn)練樣本中的噪聲數(shù)據(jù)和統(tǒng)計(jì)波動(dòng)可能會(huì)使決策樹產(chǎn)生不必要的分支，從而導(dǎo)致在使用決策樹模型對(duì)觀察樣本實(shí)施分類時(shí)出錯(cuò)為了避免這種錯(cuò)誤，需要對(duì)決策樹進(jìn)行修剪，除去不必要的分支給定一個(gè)假設(shè)空間H，假設(shè)hH，如果存在假設(shè)hH，在訓(xùn)練樣本集上h的分類錯(cuò)誤率比h小，但在整個(gè)樣本空間上h的分類錯(cuò)誤率比h小，則稱假設(shè)h過(guò)度適應(yīng)訓(xùn)練樣本集剪枝用于解決過(guò)度適應(yīng)的問(wèn)題剪枝的原則包括：（）奧卡姆剃刀原則如無(wú)必要，勿增實(shí)體即在與觀察相容的情況下，就當(dāng)選擇最簡(jiǎn)單的一個(gè)；（）決策樹越小就越容易理解，其存儲(chǔ)與傳輸?shù)拇鷥r(jià)也就越?。唬ǎQ策樹越復(fù)雜，節(jié)點(diǎn)越多，每個(gè)節(jié)點(diǎn)包含的訓(xùn)練樣本個(gè)數(shù)越少，則支持每個(gè)節(jié)點(diǎn)

22、的假設(shè)的樣本個(gè)數(shù)就越少，可能導(dǎo)致決策樹在測(cè)試集上的分類錯(cuò)誤率越大但決策樹過(guò)小也會(huì)導(dǎo)致錯(cuò)誤率較大，因此，需要在樹的大小與正確之間尋找均衡點(diǎn)常用的剪枝技術(shù)有預(yù)剪枝（pre-pruning）和后剪枝（post-pruning）兩種預(yù)剪枝技術(shù)限制決策樹的過(guò)度生長(zhǎng)（如CHAID ID3家族的ID3 C4.5算法等），后剪枝技術(shù)則是待決策樹生成后再進(jìn)行剪枝（如CART算法等）預(yù)剪枝：最直接的預(yù)剪枝方法是事先限定決策樹的最大生長(zhǎng)高度，使決策樹不能過(guò)度生長(zhǎng)這種停止標(biāo)準(zhǔn)一般能夠取得比較好的效果不過(guò)指定樹高度的方法要求用戶對(duì)數(shù)據(jù)的取值分布有較為清晰的把握，而且需對(duì)參數(shù)值進(jìn)行反復(fù)嘗試，否則無(wú)法給出一個(gè)較為合理的樹高

23、度閾值更普遍的作法是采用統(tǒng)計(jì)意義下的2檢驗(yàn)，信息增益等度量，評(píng)價(jià)每次節(jié)點(diǎn)分裂對(duì)系統(tǒng)性能的增益如果節(jié)點(diǎn)分裂的增益值小于預(yù)先給定的閾值，則不對(duì)該節(jié)點(diǎn)進(jìn)行擴(kuò)展如果在最好的擴(kuò)展增益都小于閾值，即使有些節(jié)點(diǎn)的樣本不屬于同一類，算法也可以終止選取閾值是困難的，閾值較高可能導(dǎo)致決策樹過(guò)于簡(jiǎn)化，而閾值較低可能對(duì)決策樹的化簡(jiǎn)不夠充分預(yù)剪枝存在的視野效果的問(wèn)題在相同的標(biāo)準(zhǔn)下，當(dāng)前的擴(kuò)展不滿足標(biāo)準(zhǔn)，但進(jìn)一步的擴(kuò)展有可能滿足標(biāo)準(zhǔn)采用預(yù)剪枝的算法有可能過(guò)早地停止決策樹的構(gòu)造，但由于不必生成完整的決策樹，算法的效率很高，適合應(yīng)用于大規(guī)模問(wèn)題后剪枝：后剪枝技術(shù)允許決策樹過(guò)度生長(zhǎng)，然后根據(jù)一定的規(guī)則，剪去決策樹中那些不具有一

24、般代表性的葉節(jié)點(diǎn)或分支后剪枝算法有自上而下的和自下而上的兩種剪枝策略自下而上的算法首先從最底層的內(nèi)節(jié)點(diǎn)開始剪枝，剪去滿足一定條件的內(nèi)節(jié)點(diǎn)，在生成的新決策上遞歸調(diào)用這個(gè)算法，直到?jīng)]有要可以剪枝的節(jié)點(diǎn)為止自上而下的算法是從根節(jié)點(diǎn)開始向下逐個(gè)考慮節(jié)點(diǎn)的剪枝問(wèn)題，只要節(jié)點(diǎn)滿足剪枝的條件就進(jìn)行剪枝決策樹修剪的基本算法：Prune_tee（節(jié)點(diǎn)）If（節(jié)點(diǎn)為葉節(jié)點(diǎn)）返回C(t)+1minCost1=prune_tree(N1)minCost2=prune_tree(N2)minCostN=minC(t)+1， Csplit(N)+1+minCost1+minCost2；if(minCostN= =C(t)

25、+1)將的子節(jié)點(diǎn)和從決策樹中修剪掉；返回minCostN在算法中，t為屬于節(jié)點(diǎn)的所有訓(xùn)練樣本，C(t)和Csplit(N)分別為將作為葉節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)本構(gòu)建決策樹的代價(jià)，算法的基本思想就是要使構(gòu)建決策樹的總代價(jià)最小計(jì)算C(t)的公式為其中，n 為t 中樣本的個(gè)數(shù)，k 為t 中樣本的類別數(shù)，ni為t 中屬于類i 的樣本數(shù)計(jì)算Csplit(N)要分為兩種情況：（）當(dāng)節(jié)點(diǎn)的分支屬性為連續(xù)屬性時(shí)，Csplit(N)log2a+log2(v-1)（）當(dāng)節(jié)點(diǎn)的分支屬性為離散屬性時(shí)，Csplit(N)log2a+log2(2 v-2)其中，a 為決策樹中用于節(jié)點(diǎn)分裂的屬性的個(gè)數(shù)，v是分支屬性可能取值的個(gè)數(shù)目

26、前，決策樹修剪策略主要有三種：代價(jià)復(fù)雜度修剪（cost-complexity pruning），悲觀修剪（pressimistic pruning）和基于最小描述長(zhǎng)度（minimum description length, MDL）原理的修剪悲觀修剪是非曲直uinlan在1987年提出的，該方法將所有的樣本用于樹的構(gòu)建和修剪，但是這種方法產(chǎn)生的樹太大，并且有時(shí)候精度不高代價(jià)復(fù)雜修剪使用了獨(dú)立的樣本用于修剪，這種策略適用于訓(xùn)練樣本比較多的情況在訓(xùn)練樣本數(shù)目較少的情況下，需要將所有的樣本既用于樹的構(gòu)建，又用于樹的修剪，基于MDL原理的修剪是使用較多并且效果較好的方法基于MDL原理的決策樹算法有兩個(gè)

27、部分：一是決定數(shù)據(jù)編碼代價(jià)和模型編碼代價(jià)的編碼模式，包括數(shù)據(jù)編碼和模型編碼；二是比較各個(gè)子樹，確定是否剪枝的算法MDL修剪過(guò)程是一個(gè)自底向上的遞歸過(guò)程修剪算法：Pruning_the_tree(t) If t is a leaf node then Return cleaf=1; /cleaf is the cost of a leaf node Else Let cleaf be errors plus 1; /see option(1) If the split attribute is a numeric attribute Ltest=1 Else Count the number o

28、f such tests used in the tree (say n); Ltest=log2(n); Cboth=1+ltest+pruning_the_tree(t.leftchild)+pruning_the_tree(t.rightchild); If cleaf<cboth Prune cboth children of ts, and convert t into a leaf; Return cleaf; Else Return cboth1.4 決策樹ID3每個(gè)大節(jié)與小節(jié)之間要有一段文字說(shuō)明本大節(jié)打算講述的內(nèi)容（與寫作安排或意義）等。1.4.1 ID3的基本概念和相關(guān)

29、信息論定義在數(shù)據(jù)倉(cāng)庫(kù)和數(shù)據(jù)挖掘的應(yīng)用中，分類是一種非常重要的方法分類的概念是在已有數(shù)據(jù)的基礎(chǔ)上學(xué)會(huì)一個(gè)分類函數(shù)或構(gòu)造出一個(gè)分類模型，即我們通常所說(shuō)的分類器(Classifier）該函數(shù)或模型能夠把數(shù)據(jù)庫(kù)中的數(shù)據(jù)紀(jì)錄映射到給定類別中的某一個(gè)，從而可以應(yīng)用于數(shù)據(jù)預(yù)測(cè)分類的主要算法有：貝葉斯算法、決策樹算法（如ID3、C4.5等）、規(guī)則推導(dǎo)、人工神經(jīng)網(wǎng)絡(luò)、最近鄰算法、支持向量機(jī)等等這些算法在許多現(xiàn)實(shí)數(shù)據(jù)集合上可以做比較精確的數(shù)據(jù)預(yù)測(cè)，為人們的生活、生產(chǎn)、學(xué)習(xí)、研究提供了有效的途徑其中決策樹算法具有良好的可解釋性，在實(shí)踐中的應(yīng)用最為廣泛決策樹分類算法的一個(gè)典型代表就是ID3算法ID3算法是基于信息論（

30、Information Theory）的方法給定一個(gè)記錄的集合，每個(gè)記錄都有相同的結(jié)構(gòu)，并且每個(gè)記錄是由若干個(gè)成對(duì)的屬性值組成的這些屬性代表記錄所屬的類別ID3需要解決的問(wèn)題是構(gòu)造一個(gè)決策樹，從而可以由非類別的屬性值正確地預(yù)測(cè)出類別屬性的值ID3算法可以分為兩個(gè)階段，一是建立決策樹階段，一是利用決策樹給實(shí)例分類的階段在ID3算法建立決策樹的過(guò)程中，可以遞歸地進(jìn)行：首先，選擇一個(gè)屬性作為根節(jié)點(diǎn)，并為每一個(gè)可能的屬性值生成一個(gè)分支這樣，把實(shí)例集合劃分成多個(gè)子集合，該屬性的每一個(gè)值劃分為一個(gè)子集合現(xiàn)在對(duì)每一個(gè)分支重復(fù)以上的過(guò)程，過(guò)程中使用的實(shí)例集合是屬于該分支的實(shí)例如果在一個(gè)節(jié)點(diǎn)的所有實(shí)例屬于相同的

31、類，則停止擴(kuò)展那一部分子樹這樣ID3的所建立的決策樹中每一個(gè)非葉子節(jié)點(diǎn)對(duì)應(yīng)著一個(gè)非類別屬性，與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)；每個(gè)葉節(jié)點(diǎn)代表從樹根到葉節(jié)點(diǎn)之間的路徑所對(duì)應(yīng)的記錄所屬的類別屬性值在ID3建立決策樹的過(guò)程中，一個(gè)重要的環(huán)節(jié)就是分裂屬性的選擇選擇分裂屬性時(shí)ID3中采用了信息增益的標(biāo)準(zhǔn)1.4.2 ID3算法基于ID3的基本思想，ID3的具體算法是：Function ID3R：一個(gè)非類別屬性集合；C：類別屬性；S：一個(gè)訓(xùn)練集返回一個(gè)決策樹BeginIf S為空，返回一個(gè)值為丟失值的單個(gè)節(jié)點(diǎn)；If S是由其值均為相同類別屬性值的記錄組成，返回一個(gè)帶有該值的單個(gè)節(jié)點(diǎn)；If R為空，則

32、返回一個(gè)單節(jié)點(diǎn)，其值為在S的記錄中找出的頻率最高的類別屬性值；將R中屬性之間具有最大gain(D,S)值的屬性賦給D；將屬性D的值賦給djj=1,2,m;將分別由對(duì)應(yīng)于D的值為dj的記錄組成的S的子集賦給sjj=1,2,m ;返回一棵樹，其根標(biāo)記為D，樹枝標(biāo)記為d1,d2,dm;再分別構(gòu)造以下樹：ID3（R-D,C,S1）,ID3（R-D,C,S2）,ID3（R-D,C,S1）;End ID31.4.3一個(gè)實(shí)例的具體分析下面就以有關(guān)天氣問(wèn)題的數(shù)據(jù)為例仔細(xì)介紹一下信息增益的概念和最佳分裂屬性的選擇過(guò)程有關(guān)天氣問(wèn)題的數(shù)據(jù)如表一所示：outlook(類型)temperature(溫度)humidit

33、y(濕度)windy(風(fēng))play(玩)sunnyhothighFalsenosunnyhothighTruenoovercasthothighFalseyesrainymildhighFalseyesrainycoolnormalFalseyesrainycoolnormalTruenoovercastcoolnormalTrueyessunnymildhighFalsenosunnycoolnormalFalseyesrainymildnormalFalseyessunnymildnormalTrueyesovercastmildhighTrueyesovercasthotnormalFa

34、lseyesrainymildhighTrueno一個(gè)屬性的信息增益是由于使用這個(gè)屬性分割實(shí)例而導(dǎo)致的期望熵降低例如，屬性A相對(duì)實(shí)例集合S的信息增益Gain(S,A)定義為：對(duì)表一中的各非類別屬性計(jì)算信息增益的過(guò)程如下：1計(jì)算總的信息熵信息熵的定義為：若給定的概率分布P=（P1,P2,Pn），則由該分布傳遞的信息量稱為P的信息熵，記為：在沒(méi)有建立決策樹之前，訓(xùn)練實(shí)例集合包括9個(gè)yes和5個(gè)no節(jié)點(diǎn)，相應(yīng)總的信息熵為info(9, 5) = 0.940 bits2計(jì)算以outlook屬性為根節(jié)點(diǎn)的樹分裂后各個(gè)節(jié)點(diǎn)的平均信息熵如圖以outlook屬性為根節(jié)點(diǎn)建立的樹為：編號(hào)與名稱（所有）考慮一下每

35、個(gè)節(jié)點(diǎn)的實(shí)例數(shù)目，我們計(jì)算一下他們的平均信息值；第一個(gè)和第三個(gè)節(jié)點(diǎn)有5個(gè)實(shí)例，第二個(gè)節(jié)點(diǎn)有4個(gè)，第三個(gè)節(jié)點(diǎn)有5個(gè)：info(2, 3, 4, 0, 3, 2) = (5 / 14) ×0.971 + (4 / 14) × 0 + (5 / 14) × 0.971 = 0.693 bits3計(jì)算屬性outlook的信息獲得gain(outlook) = info(9, 5) - info(2, 3, 4, 0, 3, 2) = 0.940 - 0.693 = 0.247 bits，4重復(fù)上述步驟，得到temperature、humidity和windy的信息獲得分別

36、為：gain(temperature) = 0.029 bitsgain(humidity) = 0.152 bitsgain(windy) = 0.048 bits，計(jì)算出各個(gè)非類別屬性的信息獲得后，我們由此來(lái)選擇信息獲得最大的屬性作為分裂屬性，由上述計(jì)算結(jié)果可以看出屬性outlook的信息獲得最大，則選擇其作為分裂屬性來(lái)建立決策樹然后我們繼續(xù)遞歸下去，圖二表明當(dāng)outlook = sunny時(shí)，可能在節(jié)點(diǎn)產(chǎn)生一個(gè)更深的分支很明顯，還依照outlook（觀看）屬性來(lái)劃分下一層分支得不到任何新的東西，所以只考慮其它三個(gè)屬性他們各自的信息獲得值是gain(temperature) = 0.571

37、 bitsgain(humidity) = 0.971 bitsgain(windy) = 0.020 bits，所以我們選擇humidity（濕度）作為這個(gè)點(diǎn)的劃分屬性，沒(méi)有必要作進(jìn)一步的劃分了，這個(gè)分支結(jié)束繼續(xù)用同樣的方法得到圖三的weather（天氣）數(shù)據(jù)的決策樹理想的情況是當(dāng)所有葉子節(jié)點(diǎn)是純潔的時(shí)候過(guò)程結(jié)束即，他們所包含的實(shí)例屬于同一類然而，也許不可能達(dá)到這種狀態(tài)，因?yàn)橛锌赡苡幸粋€(gè)實(shí)例集合，包含兩個(gè)實(shí)例，有同樣的屬性集合，但屬于不同的類，誰(shuí)也不能保證這種情況不發(fā)生，所以當(dāng)數(shù)據(jù)不能繼續(xù)劃分時(shí)就停止這樣就會(huì)在運(yùn)用分類器給實(shí)例分類時(shí)出現(xiàn)有未分實(shí)例的現(xiàn)象上述過(guò)程是在ID3算法中建立決策樹的過(guò)程

38、，建立好決策樹后就可以利用些決策樹給實(shí)例進(jìn)行分類分類過(guò)程是根據(jù)待分實(shí)例在所建決策樹中找到與其匹配的類屬性值的過(guò)程在程序設(shè)計(jì)中上也可以通過(guò)遞歸來(lái)實(shí)現(xiàn)下面以實(shí)例（sunny，hot，high，F(xiàn)alse）為例說(shuō)明一下其分類過(guò)程：待分實(shí)例的在根節(jié)點(diǎn)outlook屬性上的值為sunny，所以沿outlook=sunny路徑，將實(shí)例分到以humidity屬性為根節(jié)點(diǎn)的子樹上待分實(shí)例的在當(dāng)前根節(jié)點(diǎn)humidity屬性上的值為high，而 humidity=high路徑對(duì)應(yīng)的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，此葉子節(jié)點(diǎn)對(duì)應(yīng)的類屬性值為no，因?yàn)橐训饺~子節(jié)點(diǎn)所以待分實(shí)例的類屬性值就為no1.4.4 ID3算法的不足及決策樹學(xué)習(xí)

39、中常見問(wèn)題（偏置、過(guò)度擬合、連續(xù)值屬性和確實(shí)屬性的處理）-機(jī)器學(xué)習(xí)1.5 決策樹學(xué)習(xí)的改進(jìn)算法C4.5類似于ID3基本思想和算法分析C4.5算法是一個(gè)里程碑式的決策樹算法，是迄今為止在實(shí)踐中應(yīng)用最為廣泛的機(jī)器學(xué)習(xí)方法。它所采用的是分而治之策略其構(gòu)造決策樹的核心思想是貪心算法，它采用自上而下遞歸地各個(gè)擊破方式構(gòu)造決策樹。決策樹生成的難點(diǎn)主要有如何處理連續(xù)值屬性，如何處理缺省值，如何修剪決策樹。J48是在weka實(shí)驗(yàn)平臺(tái)下它的具體實(shí)現(xiàn)程序1.5 實(shí)用的決策樹學(xué)習(xí)算法C C4.5算法的工作流程首先介紹算法，然后再說(shuō)明各種特定問(wèn)題。C4.5算法構(gòu)造決策樹的核心思想是貪心算法，它采用自上

40、而下遞歸地各個(gè)擊破方式構(gòu)造決策樹。開始時(shí)，所有的屬性都在根結(jié)點(diǎn)，這些屬性都是種類字段（如果是連續(xù)的，將其離散化），所有記錄用所選屬性遞歸的進(jìn)行分裂，屬性的選擇是基于一個(gè)統(tǒng)計(jì)的度量，然后把這個(gè)過(guò)程遞歸到每個(gè)子樹，當(dāng)一個(gè)結(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一個(gè)類別或者沒(méi)有屬性可以再用于對(duì)數(shù)據(jù)進(jìn)行分裂時(shí)停止分裂。決策樹生成之后，對(duì)樹剪枝以處理過(guò)分適應(yīng)（Over-fitting）的問(wèn)題。（以下文字的標(biāo)題有待確定）C4.5分類器使用最大信息增益來(lái)選擇連續(xù)型屬性的閾值，它使得對(duì)結(jié)果劃分中的樣本分類所需的信息量最小，并反映劃分的最小隨機(jī)性或“不純性”。設(shè)是s個(gè)數(shù)據(jù)樣本的集合，假定類標(biāo)屬性有m個(gè)不同值，定義了m個(gè)不同類ci

41、 ( i=1, 2， , m )設(shè)Si是類ci中的樣本數(shù)。對(duì)一個(gè)給定的樣本分類所需的期望信息由下式給出其中Pi是任意樣本屬于Ci概率，并用Si/S估計(jì)設(shè)連續(xù)值屬性A的閾值為a，可以用閾值a將S劃分為2個(gè)子集：S1=樣本|屬性值A(chǔ)的取值 a，S2=樣本|屬性值A(chǔ)的取值 a。設(shè)Sij是子集Sj中類Ci的樣本數(shù)。根據(jù)由a劃分成子集合的熵或期望信息由下式給出對(duì)于給定的子集Sj(j=1, 2)其中，Pij=Sij/Sj是Sj中的樣本屬于類Ci的概率。則屬性在閾值a上的信息增益為 換言之，gain(A)由于知道屬性A的閾值a而導(dǎo)致的熵期望壓縮。在現(xiàn)實(shí)數(shù)據(jù)集合里，屬性值缺損的現(xiàn)象很常見。處理缺損值的一個(gè)簡(jiǎn)單

42、辦法就是刪除有缺損值的實(shí)例。另外一種方法是用一個(gè)簡(jiǎn)單值代替缺損屬性值。C4.5算法保留有缺損值的實(shí)例，采取的方法是：當(dāng)使用這個(gè)屬性值有缺損的屬性時(shí)，按照分裂分支下的訓(xùn)練實(shí)例數(shù)的比率將有缺損值的實(shí)例分成一定比率的碎片23, 25。分而治之構(gòu)造決策樹C4.5構(gòu)造決策樹采取的方法是分而治之遞歸地構(gòu)造：首先，計(jì)算候選屬性的信息熵比率和增益比率，選擇一個(gè)最佳屬性（增益比率最大）作為根節(jié)點(diǎn)，并為每一個(gè)可能的屬性值生成一個(gè)分支這樣，把實(shí)例集合劃分成多個(gè)子集合（大小為屬性值的數(shù)目或者為2），該屬性的每一個(gè)值對(duì)應(yīng)一個(gè)子集合現(xiàn)在對(duì)每一個(gè)分支重復(fù)以上的過(guò)程，過(guò)程中使用的實(shí)例集合是屬于那個(gè)分支的實(shí)例集合如果在一個(gè)節(jié)點(diǎn)

43、的所有實(shí)例屬于相同的類或者小于葉子節(jié)點(diǎn)限制的最少的實(shí)例數(shù)，則停止擴(kuò)展那一部分子樹處理連續(xù)值屬性（有例子可以單獨(dú)作為一小節(jié)。）大多數(shù)真實(shí)數(shù)據(jù)集合都包含連續(xù)值屬性。針對(duì)連續(xù)值屬性C4.5采取的方法是二路分裂。C4.5按連續(xù)值屬性值升序排列數(shù)據(jù)集合的實(shí)例。順序取兩兩連續(xù)值屬性值的中點(diǎn)作為一個(gè)分裂點(diǎn)，可以把數(shù)據(jù)集合分裂為兩個(gè)子集合。如果連續(xù)值屬性有n個(gè)值，所以有n-1個(gè)可以作為分裂點(diǎn)的位置。依照這n-1個(gè)分裂點(diǎn)可以計(jì)算出n-1個(gè)信息熵值，找出其中最大值。將小于并且最接近信息熵最大的分裂點(diǎn)值，且存在于數(shù)據(jù)集合的屬性值定為最終分裂點(diǎn)值。例如：包含連續(xù)值屬性的天氣數(shù)據(jù)集合（ weather.arff）如表當(dāng)

44、溫度(temperature) 屬性作為分裂屬性考慮時(shí)，C4.5首先按溫度(temperature) 屬性值升序排列數(shù)據(jù)集合的實(shí)例。溫度(temperature) 屬性值和類屬性(play)值的對(duì)應(yīng)關(guān)系如下表：646568697071727580818385YesNoYesYesYesNoNoYesYesNoNoYesYesNo溫度(temperature) 屬性有12個(gè)值，所以有11個(gè)可以作為分裂點(diǎn)的位置(例如：以值71和值72的中值作為分裂的分水嶺，則可以按>71.5和<71.5將天氣數(shù)據(jù)集合分裂為兩個(gè)子集合)。依照這11個(gè)分裂點(diǎn)可以計(jì)算出11個(gè)信息熵值，找出其中最大值。假定求

45、出的最大信息熵的分裂點(diǎn)為71.5，J48仍然將小于并且最接近71.5，且存在于數(shù)據(jù)集合的屬性值71定為分裂點(diǎn)值采用枚舉型屬性和連續(xù)值屬性作為分裂屬性的不同之處，除了在于連續(xù)值屬性的分裂都是兩路分裂，而枚舉型屬性的分裂是多路分裂外，枚舉型屬性在決策樹里從根到葉子的任一條路徑上被作為分裂屬性只能是一次，而連續(xù)值屬性可以被利用多次，只需要每次的分裂點(diǎn)不同就可以。但是這樣做導(dǎo)致生成的決策樹的深度大為增加，可理解性差，不易于理解。解決的辦法是可以采取連續(xù)值屬性多路分裂，但是難于實(shí)現(xiàn)。也可以先調(diào)用離散化程序預(yù)處理連續(xù)值屬性，然后再建立決策樹。選擇最佳分裂屬性決策樹分類器的核心問(wèn)題是在樹的每個(gè)節(jié)點(diǎn)上選取最佳

46、分裂屬性。最佳的分裂屬性應(yīng)該是分類能力最好的屬性。信息增益就是用來(lái)形容給定的屬性區(qū)分訓(xùn)練實(shí)例的能力。J48就是利用信息增益在增長(zhǎng)樹的每一步中選取最佳分裂屬性。一個(gè)屬性的信息增益是由于使用這個(gè)屬性分割實(shí)例而導(dǎo)致的期望熵降低。J48算法計(jì)算每一個(gè)候選屬性的信息增益，接著計(jì)算增益比率，然后選擇增益比率最高的那個(gè)屬性作為最佳分裂屬性。例如：一個(gè)屬性的信息增益是由于使用這個(gè)屬性分割實(shí)例而導(dǎo)致的期望熵降低。例如，屬性A相對(duì)實(shí)例集合S的信息增益Gain(S,A)定義為：例如，屬性outlook相對(duì)與天氣數(shù)據(jù)集合的信息增益Gain(S,outlook)為：SunnyRainyOvercast Yes 2226

47、No123634512J48算法計(jì)算每一個(gè)候選屬性的信息增益，接著計(jì)算增益比率SplitInfo(S,outlook)是信息量。1.5.1 處理修改小節(jié)編號(hào)。未知值的訓(xùn)練樣本、處理缺省值的方式處理缺省值（可以考慮加一個(gè)例題C4.5.doc）沒(méi)有處理未知值的訓(xùn)練樣本在實(shí)際生活的數(shù)據(jù)集合里，屬性值缺省的現(xiàn)象很常見。處理缺省值的一個(gè)簡(jiǎn)單辦法就是刪除有缺省值的實(shí)例。但是含有缺省值的實(shí)例通常提供了很多信息。有時(shí)候值缺省的屬性在決策中不起作用，所以在這種情況下它同其他沒(méi)有缺省值的實(shí)例一樣好。C4.5采取的方法是當(dāng)使用這個(gè)缺省屬性作為分裂屬性時(shí)，按照分裂分支下的訓(xùn)練實(shí)例數(shù)的比例將有缺省值的實(shí)例分成一定比例的

48、碎片。1.5.3 實(shí)基于的最好不要提及weka!所以就有適當(dāng)修改下面所使用的數(shù)據(jù)結(jié)構(gòu)的名字，并且在使用之前加以說(shuō)明。一個(gè)實(shí)例的具體分析有關(guān)天氣問(wèn)題的數(shù)據(jù)如表所示：（該實(shí)例有待修改完善）Outlook(類型)temperature(溫度)humidity(濕度)windy(風(fēng))play(玩)Sunny8585FALSENoSunny8090TRUENoOvercast8386FALSEYesRainy7096FALSEYesRainy6880FALSEYesRainy6570TRUENoOvercast6465TRUEYesSunny7295FALSENoSunny6970FALSEYesRai

49、ny7580FALSEYesSunny7570TRUEYesOvercast7290TRUEYesOvercast8175FALSEYesRainy7191TRUENo一計(jì)算Outlook屬性的分裂信息熵增益以及增益率：currentMGain()=0.24674981977443902currentModel0.gainRatio()=0.15642756242117511計(jì)算temperature屬性的分裂信息熵增益以及增益率：currentMGain()=-0.18108904235959222currentModel1.gainRatio()=0

50、.0計(jì)算humidity屬性的分裂信息熵增益以及增益率：currentMGain()=-0.04868985021320138currentModel2.gainRatio()=0.0計(jì)算windy屬性的分裂信息熵增益以及增益率：currentMGain()=0.04812703040826933currentModel3.gainRatio()=0.048848615511520685選擇信息上增益率最大的作為分裂節(jié)點(diǎn)，因此這次選擇的是屬性下標(biāo)簽為0的屬性作為分裂節(jié)點(diǎn)，也就是上表所示的outlook屬性作為分裂節(jié)點(diǎn)二其中選擇最佳分裂節(jié)點(diǎn)后的數(shù)據(jù)集為：說(shuō)

51、明：localInstances0為outlook=sunny，localInstances為outlook=overcast，localInstances2為outlook=rainylocalInstances0=sunny,75,70,TRUE,yessunny,69,70,FALSE,yessunny,85,85,FALSE,nosunny,80,90,TRUE,nosunny,72,95,FALSE,nolocalInstances1=overcast,64,65,TRUE,yesovercast,81,75,FALSE,yesovercast,83,86,FALSE,yesover

52、cast,72,90,TRUE,yeslocalInstances2=rainy,65,70,TRUE,norainy,75,80,FALSE,yesrainy,68,80,FALSE,yes,rainy,71,91,TRUE,norainy,70,96,FALSE,yes如圖以outlook屬性為根節(jié)點(diǎn)建立的樹為：然后依次在此基礎(chǔ)上繼續(xù)向下遞歸分裂數(shù)據(jù)構(gòu)造決策樹：outlook=sunny在localInstances0上構(gòu)建決策樹的過(guò)程及其相應(yīng)的輸出結(jié)果：（outlook=sunny）Outlook屬性的分裂信息熵增益以及增益率：currentMGain()=0.0cu

53、rrentModel0.gainRatio()=0.0temperature屬性的分裂信息熵增益以及增益率：currentMGain()=0.21997309402197512currentModel1.gainRatio()=0.22655436360850295humidity屬性的分裂信息熵增益以及增益率：currentMGain()=0.7709505944546688currentModel2.gainRatio()=0.7940162958421904windy屬性的分裂信息熵增益以及增益率：currentMGain()=

54、0.019973094021975158currentModel3.gainRatio()=0.020570659450693245要選擇信息上增益率最大的作為分裂節(jié)點(diǎn)，因此這次選擇的是屬性下標(biāo)簽為2的屬性作為分裂節(jié)點(diǎn)，也就是上表所示的humidity屬性作為分裂節(jié)點(diǎn)；此時(shí)將數(shù)據(jù)集分成兩份：localInstances0（humidity<=70）和localInstances1 （humidity>=70）(采用二路分裂的方法，上面講過(guò))localInstances0=sunny,75,70,TRUE,yessunny,69,70,FALSE,yeslocalInstances1=sunny,85,85,FALSE,nosun