人工智能之決策樹(shù)

1、1. 決策樹(shù)基本概念2. 信息論基礎(chǔ)3. 應(yīng)用實(shí)例及ID3算法4. 決策樹(shù)總結(jié)5. 一些思考目錄生活中的決策樹(shù)1(Decision Tree)1.決策樹(shù)基本概念 A decision tree is a flowchart-like structure in which each internal node represents a test on an attribute (e.g. whether a coin flip comes up heads or tails), each branch represents the outcome of the test, and each le

2、af node represents a class label (decision taken after computing all attributes). The paths from root to leaf represent classification rules. 決策樹(shù)是一種類(lèi)似于流程圖的結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)代表一個(gè)屬性上的“測(cè)試”（例如，一個(gè)硬幣的翻轉(zhuǎn)是正面還是反面），每個(gè)分支代表測(cè)試的結(jié)果，每個(gè)葉節(jié)點(diǎn)代表一個(gè)類(lèi)標(biāo)簽（在計(jì)算所有屬性之后做出的決定）。從根到葉子的路徑表示分類(lèi)規(guī)則。定義1.決策樹(shù)基本概念生活中的決策樹(shù)2(Decision Tree)屬性測(cè)試屬性測(cè)試決定決定

3、分支 構(gòu)建決策樹(shù)的關(guān)鍵問(wèn)題： 1. 以何種屬性進(jìn)行測(cè)試 2. 以何種順序進(jìn)行測(cè)試 3. 何時(shí)做出決定1.決策樹(shù)基本概念 連接主義者認(rèn)為，機(jī)器學(xué)習(xí)分為監(jiān)督學(xué)習(xí)，無(wú)監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)。監(jiān)督學(xué)習(xí)就是訓(xùn)練樣本帶有屬性標(biāo)簽。監(jiān)督學(xué)習(xí)又可分為“回歸”和“分類(lèi)”問(wèn)題。 機(jī)器學(xué)習(xí)中的分類(lèi)技術(shù)一般是用一種學(xué)習(xí)算法確定分類(lèi)模型，該模型可以很好地?cái)M合類(lèi)標(biāo)號(hào)和屬性集之間的映射關(guān)系。 常用的分類(lèi)算法包括：決策樹(shù)分類(lèi)法、邏輯回歸分類(lèi)法、神經(jīng)網(wǎng)絡(luò)、支持向量級(jí)、樸素貝葉斯分類(lèi)方法等。機(jī)器學(xué)習(xí)中的決策樹(shù)（1/2）1.決策樹(shù)基本概念 在機(jī)器學(xué)習(xí)中，決策樹(shù)是一個(gè)帶有標(biāo)簽的監(jiān)督式學(xué)習(xí)預(yù)測(cè)模型，代表的是對(duì)象屬性與對(duì)象值之間的一種映射關(guān)

4、系。算法ID3，C4.5和C5.0是基于信息學(xué)理論中熵的理論而設(shè)計(jì)的。 相比大多數(shù)分類(lèi)算法，如 kNN 等，決策樹(shù)易于理解和實(shí)現(xiàn)，使用者無(wú)需了解很多背景知識(shí)。它能夠?qū)?shù)據(jù)集合進(jìn)行分析，挖掘其中蘊(yùn)含的知識(shí)信息。機(jī)器學(xué)習(xí)中的決策樹(shù)（2/2）1.決策樹(shù)基本概念 決策樹(shù)算法采用自上至下遞歸建樹(shù)的技術(shù)，該算法的產(chǎn)生源于CLS系統(tǒng)，即概念學(xué)習(xí)系統(tǒng)。決策樹(shù)算法發(fā)展歷史(1/2)1.決策樹(shù)基本概念 1980年，戈登V.卡斯創(chuàng)建CHAID（卡方自動(dòng)交叉檢驗(yàn)） 1979年，J.R. Quinlan 給出ID3算法，在1983年和1986年進(jìn)行總結(jié)和簡(jiǎn)化 1986年，Schlimmer 和Fisher 于對(duì)ID3進(jìn)

5、行改造，使決策樹(shù)可以遞增式生成，得到ID4算法。 1988年，Utgoff 在ID4基礎(chǔ)上提出了ID5學(xué)習(xí)算法 1993年，Quinlan 進(jìn)一步發(fā)展了ID3算法，改進(jìn)成C4.5算法。 另一類(lèi)決策樹(shù)算法為CART，與C4.5不同的是，CART的決策樹(shù)由二元邏輯問(wèn)題生成，每個(gè)樹(shù)節(jié)點(diǎn)只有兩個(gè)分枝，分別包括學(xué)習(xí)實(shí)例的正例與反例決策樹(shù)算法發(fā)展歷史(2/2)1.決策樹(shù)基本概念決策樹(shù)重要概念1.決策樹(shù)基本概念 信息的大小可以度量么？ 信息量的大小與概率有關(guān)！ 概率越小，信息量越大。出現(xiàn)概率為0，信息量無(wú)窮大 概率越大，信息量越小。出現(xiàn)概率為1，信息量為0.信息量2. 信息論基礎(chǔ)1948年10月，香農(nóng)在貝爾

6、系統(tǒng)技術(shù)學(xué)報(bào)上發(fā)表論文A Mathematical Theory of Communication，首次建立通訊過(guò)程的數(shù)學(xué)模型，成為現(xiàn)代信息論研究的開(kāi)端。香農(nóng)理論的重要特征是熵（entropy）的概念，他證明熵與信息內(nèi)容的不確定程度有等價(jià)關(guān)系。信息論2. 信息論基礎(chǔ)消息 發(fā)生后所含有的信息量，反映了消息 發(fā)生前的不確定性：信息量ixix譬如袋子里有紅球和黑球，取紅球譬如袋子里有紅球和黑球，取紅球的概率的概率為為0.4，取黑球的概率為，取黑球的概率為0.6。取出紅球的信息量取出紅球的信息量為為1.322，取出黑球的取出黑球的信息量信息量0.737。2. 信息論基礎(chǔ)1( )loglog( )( )

7、iiiI xP xP x 熵 (entropy) 這一詞最初來(lái)源于熱力學(xué)。1948年，克勞德愛(ài)爾伍德香農(nóng)將熱力學(xué)中的熵引入信息論，所以也被稱(chēng)為香農(nóng)熵 (Shannon entropy)，信息熵 (information entropy)。表示系統(tǒng)的不確定性。 公式：信息熵)(log)()(1log)()(212iniiiixpxpxpExIEXH譬如袋子里有紅球和黑球，取紅球譬如袋子里有紅球和黑球，取紅球的概率的概率為為0.4，取黑球的概率為，取黑球的概率為0.6。取出紅球的信息量取出紅球的信息量為為1.322，取出黑球的取出黑球的信息量信息量0.737。取出。取出1個(gè)球的加權(quán)個(gè)球的加權(quán)平均信

8、息量為平均信息量為1.322*0.4+0.737*0.6。思考：什么情況下，熵最大？思考：什么情況下，熵最大？2. 信息論基礎(chǔ) 條件熵H(X|Y)表示在已知隨機(jī)變量Y的條件下隨機(jī)變量X的不確定性。H(X|Y)，其實(shí)質(zhì)是給定Y情況下X條件概率分布的熵，對(duì)Y的數(shù)學(xué)期望： 條件熵2. 信息論基礎(chǔ)21(|) ()|-(|)log(|)njjijijiH X YyE I XYyP xyP xy1(|)()(|)mjjjH X YP yH X Yy條件熵和互信息量2. 信息論基礎(chǔ)互信息量，又稱(chēng)信息增益11(; )()(|)( ,)=( ,)log()( ) ()mnijijjiijI X YH XH X

9、YP x yP x yP x P y Y代表性別，取值為男和女；X代表穿著，取值為裙子和褲子。信息增益計(jì)算實(shí)例男男女女裙子褲子0.40.6注意：注意：H（Y/X）代表已知某人穿著，其性別的不確定性）代表已知某人穿著，其性別的不確定性2. 信息論基礎(chǔ)求信息增益：求信息增益：I(X;Y)=H(Y)-H（Y/X）首先計(jì)算條件熵2. 信息論基礎(chǔ)Step1：計(jì)算信息熵Step2：計(jì)算給定X條件下，Y條件概率的熵Step3：Y條件概率的熵值對(duì)X求數(shù)學(xué)期望其次計(jì)算信息增益2. 信息論基礎(chǔ)互信息量，也就是隨機(jī)變量X對(duì)隨機(jī)變量Y的信息增益 ID3由Ross Quinlan在1

10、986年提出。其核心是根據(jù)“最大信息熵增益”原則選擇劃分當(dāng)前數(shù)據(jù)集的最好特征，減少數(shù)據(jù)的熵(混亂度)。 ID3是一種貪心算法：1）從根結(jié)點(diǎn)(root node)開(kāi)始，對(duì)結(jié)點(diǎn)計(jì)算所有可能的特征的信息增益，選擇信息增益最大的特征作為節(jié)點(diǎn)的特征。2）由該特征的不同取值建立子節(jié)點(diǎn)，再對(duì)子節(jié)點(diǎn)遞歸地調(diào)用以上方法，構(gòu)建決策樹(shù)；直到所有特征的信息增益均很小或沒(méi)有特征可以選擇為止；3）最后得到一個(gè)決策樹(shù)。 每次選取的分割數(shù)據(jù)的特征都是當(dāng)前的最佳選擇，并按照該特征的所有取值來(lái)切分，也就是說(shuō)如果一個(gè)特征有4種取值，數(shù)據(jù)將被切分4份。ID3算法簡(jiǎn)介3. 應(yīng)用實(shí)例及ID3算法ID3算法偽代碼ID年齡年齡有工作有工作有

11、房子有房子信貸情況信貸情況類(lèi)別類(lèi)別(是否是否放貸放貸)1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否應(yīng)用實(shí)例：是否放貸的決策樹(shù)對(duì)特征進(jìn)行標(biāo)注（預(yù)處理）對(duì)特征進(jìn)行標(biāo)注（預(yù)處理）年齡：0代表青年，1代表中年，2代表老年；有工作：0代表否，1代表是；有自己的房子：0代表否，1代表是；信貸情況：0代表一般，1代表好，2代表非常好；類(lèi)別(是否給貸款)：no代表否，yes代表是。3. 應(yīng)用實(shí)例及ID3算法信

12、息熵計(jì)算公式采用頻率替代概率。數(shù)據(jù)集D為是否放貸的類(lèi)別，Ck代表該類(lèi)別的某一取值的出現(xiàn)頻率，如不放貸出現(xiàn)的頻次特征A有n種取值，H(Di)代表在A屬性的第i個(gè)取值下，D的條件概率熵H(D/Ai)信息增益，即特征A對(duì)D的信息增益注意：要計(jì)算所有特征（屬性）A、B、C的信息增益，選擇信息增益最大的特征作為節(jié)點(diǎn)；然后以該節(jié)點(diǎn)的取值為分支，在剩余的特征（屬性）中選取信息增益最大的特征作為子節(jié)點(diǎn)3. 應(yīng)用實(shí)例及ID3算法 https:/ 三個(gè)源文件： ent.py 計(jì)算數(shù)據(jù)集D類(lèi)別的信息熵 entgain.py 分別計(jì)算各個(gè)特征對(duì)計(jì)算數(shù)據(jù)集D類(lèi)別的信息增益 id3.py ID3算法Python程序展示3

13、. 應(yīng)用實(shí)例及ID3算法 決策樹(shù)生成算法遞歸的產(chǎn)生決策樹(shù)，直到不能繼續(xù)下去為止，這樣產(chǎn)生的樹(shù)往往對(duì)訓(xùn)練數(shù)據(jù)的分類(lèi)很準(zhǔn)確，但對(duì)未知測(cè)試數(shù)據(jù)的分類(lèi)缺沒(méi)有那么精確，即會(huì)出現(xiàn)過(guò)擬合現(xiàn)象。過(guò)擬合產(chǎn)生的原因在于在學(xué)習(xí)時(shí)過(guò)多的考慮如何提高對(duì)訓(xùn)練數(shù)據(jù)的正確分類(lèi)，從而構(gòu)建出過(guò)于復(fù)雜的決策樹(shù)，解決方法是考慮決策樹(shù)的復(fù)雜度，對(duì)已經(jīng)生成的樹(shù)進(jìn)行簡(jiǎn)化。 剪枝（剪枝（pruning）：）：從已經(jīng)生成的樹(shù)上裁掉一些子樹(shù)或葉節(jié)點(diǎn)，并將其根節(jié)點(diǎn)或父節(jié)點(diǎn)作為新的葉子節(jié)點(diǎn)，從而簡(jiǎn)化分類(lèi)樹(shù)模型。 實(shí)現(xiàn)方式：實(shí)現(xiàn)方式：極小化決策樹(shù)整體的損失函數(shù)或代價(jià)函數(shù)來(lái)實(shí)現(xiàn)決策樹(shù)剪枝3. 應(yīng)用實(shí)例及ID3算法損失函數(shù)定義(1/2)Ntk代表t個(gè)葉子

14、上的第k種類(lèi)型個(gè)數(shù)3. 應(yīng)用實(shí)例及ID3算法損失函數(shù)定義(2/2)3. 應(yīng)用實(shí)例及ID3算法 C4.5是Ross Quinlan在1993年在ID3的基礎(chǔ)上改進(jìn)而提出的。ID3采用的信息增益度量存在一個(gè)缺點(diǎn)，它一般會(huì)優(yōu)先選擇有較多屬性值的Feature,因?yàn)閷傩灾刀嗟腇eature會(huì)有相對(duì)較大的信息增益?(信息增益反映的給定一個(gè)條件以后不確定性減少的程度,必然是分得越細(xì)的數(shù)據(jù)集確定性更高,也就是條件熵越小,信息增益越大)。為了避免這個(gè)不足C4.5中是用信息增益比率(gain ratio)來(lái)作為選擇分支的準(zhǔn)則。信息增益比率通過(guò)引入一個(gè)被稱(chēng)作分裂信息(Split information)的項(xiàng)來(lái)懲罰

15、取值較多的Feature。除此之外，C4.5還彌補(bǔ)了ID3中不能處理特征屬性值連續(xù)的問(wèn)題。但是，對(duì)連續(xù)屬性值需要掃描排序，會(huì)使C4.5性能下降，有興趣可以參考博客。C4.5算法簡(jiǎn)介3. 應(yīng)用實(shí)例及ID3算法信息增益比率定義3. 應(yīng)用實(shí)例及ID3算法 1.決策樹(shù)又叫判定樹(shù)，是一種基本的分類(lèi)與回歸方法。 2.優(yōu)點(diǎn)：可讀性強(qiáng)，分類(lèi)速度快，容易轉(zhuǎn)換成if-then分類(lèi)規(guī)則 3.通常分為3個(gè)步驟：特征（屬性）選擇、決策樹(shù)的生成、決策樹(shù)的修剪。 4.特征選擇即選擇分裂屬性，又叫屬性選擇度量，把數(shù)據(jù)劃分成較小的分區(qū)。 5.決策樹(shù)的生成又叫決策樹(shù)學(xué)習(xí)或者決策樹(shù)歸納。 6.決策樹(shù)生成時(shí)采用貪心（即非回溯的、局部

16、最優(yōu)的）方法，以自頂向下遞歸的分治方式構(gòu)造，只考慮局部最優(yōu)。 7.決策樹(shù)修剪時(shí)遞歸地從樹(shù)的葉節(jié)點(diǎn)向上回縮，考慮全局最優(yōu)。 8.決策算法之間的差別包括在創(chuàng)建樹(shù)時(shí)如何選擇屬性和用于剪枝的機(jī)制。 9.決策算法主要為：ID3算法，C4.5算法和CART算法。決策樹(shù)總結(jié)(1/2)4. 決策樹(shù)總結(jié) 10.ID3算法和算法和C4.5算法只有決策樹(shù)的生成，沒(méi)有對(duì)決策樹(shù)進(jìn)行剪枝。算法只有決策樹(shù)的生成，沒(méi)有對(duì)決策樹(shù)進(jìn)行剪枝。CART算法包括決策樹(shù)的剪枝。算法包括決策樹(shù)的剪枝。 11.在在進(jìn)行特征選擇時(shí)，各個(gè)算法采用的選擇分裂準(zhǔn)則不同進(jìn)行特征選擇時(shí)，各個(gè)算法采用的選擇分裂準(zhǔn)則不同:ID3算法使用信息增益準(zhǔn)則，選擇信

17、息增益最大(熵最小)的特征作為分裂屬性。C4.5算法使用信息增益比準(zhǔn)則，選擇信息增益比最大的特征作為分裂屬性。CART算法使用基尼指數(shù)準(zhǔn)則，選擇基尼指數(shù)最小的特征作為分裂屬性。 12.以以信息增益準(zhǔn)則劃分訓(xùn)練數(shù)據(jù)集的特征時(shí)，偏向于選擇屬性取值較多的作為分裂屬性；信息增益比信息增益準(zhǔn)則劃分訓(xùn)練數(shù)據(jù)集的特征時(shí)，偏向于選擇屬性取值較多的作為分裂屬性；信息增益比準(zhǔn)則調(diào)整了這種偏倚，但它傾向于產(chǎn)生不平衡的劃分，其中一個(gè)分區(qū)比其他分區(qū)小得多；基尼指數(shù)準(zhǔn)則準(zhǔn)則調(diào)整了這種偏倚，但它傾向于產(chǎn)生不平衡的劃分，其中一個(gè)分區(qū)比其他分區(qū)小得多；基尼指數(shù)準(zhǔn)則也是偏向于多值屬性，并且當(dāng)類(lèi)的數(shù)量很大時(shí)會(huì)有困難。也是偏向于多值

18、屬性，并且當(dāng)類(lèi)的數(shù)量很大時(shí)會(huì)有困難。 13.所有所有的屬性選擇度量都具有某種偏倚。的屬性選擇度量都具有某種偏倚。 14.決策樹(shù)決策樹(shù)歸納時(shí)的時(shí)間復(fù)雜度一般隨樹(shù)的高度指數(shù)增加。因此，傾向于產(chǎn)生較淺的樹(shù)（如多路劃分而歸納時(shí)的時(shí)間復(fù)雜度一般隨樹(shù)的高度指數(shù)增加。因此，傾向于產(chǎn)生較淺的樹(shù)（如多路劃分而不是二元?jiǎng)澐郑┑亩攘靠赡芨扇?。但是，較淺的樹(shù)趨向于具有大量樹(shù)葉和較高的準(zhǔn)確率。不是二元?jiǎng)澐郑┑亩攘靠赡芨扇?。但是，較淺的樹(shù)趨向于具有大量樹(shù)葉和較高的準(zhǔn)確率。 15.信息信息增益的度量標(biāo)準(zhǔn)：熵。熵越大，隨機(jī)變量的不確定性就越大，分類(lèi)能力就越低增益的度量標(biāo)準(zhǔn)：熵。熵越大，隨機(jī)變量的不確定性就越大，分類(lèi)能力就

19、越低.決策樹(shù)總結(jié)(2/2)4. 決策樹(shù)總結(jié) 10.ID3算法和算法和C4.5算法只有決策樹(shù)的生成，沒(méi)有對(duì)決策樹(shù)進(jìn)行剪枝。算法只有決策樹(shù)的生成，沒(méi)有對(duì)決策樹(shù)進(jìn)行剪枝。CART算法包括決策樹(shù)的剪枝。算法包括決策樹(shù)的剪枝。 11.在在進(jìn)行特征選擇時(shí)，各個(gè)算法采用的選擇分裂準(zhǔn)則不同進(jìn)行特征選擇時(shí)，各個(gè)算法采用的選擇分裂準(zhǔn)則不同:ID3算法使用信息增益準(zhǔn)則，選擇信息增益最大(熵最小)的特征作為分裂屬性。C4.5算法使用信息增益比準(zhǔn)則，選擇信息增益比最大的特征作為分裂屬性。CART算法使用基尼指數(shù)準(zhǔn)則，選擇基尼指數(shù)最小的特征作為分裂屬性。 12.以以信息增益準(zhǔn)則劃分訓(xùn)練數(shù)據(jù)集的特征時(shí)，偏向于選擇屬性取值較多的作為分裂屬性；信息增益比信息增益準(zhǔn)則劃分訓(xùn)練數(shù)據(jù)集的特征時(shí)，偏向于選擇屬性取值較多的作為分裂屬性；信息增益比準(zhǔn)則調(diào)整了這種偏倚，但它傾向于產(chǎn)生不平衡的劃分，其中一個(gè)分區(qū)比其他分區(qū)小得多；基尼指數(shù)準(zhǔn)則準(zhǔn)則調(diào)整了這種偏倚，但它傾向于產(chǎn)生不平