人工智能之決策樹

1、1. 決策樹基本概念2. 信息論基礎(chǔ)3. 應(yīng)用實例及ID3算法4. 決策樹總結(jié)5. 一些思考目錄生活中的決策樹1(Decision Tree)1.決策樹基本概念 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. 決策樹是一種類似于流程圖的結(jié)構(gòu)，其中每個內(nèi)部節(jié)點代表一個屬性上的“測試”（例如，一個硬幣的翻轉(zhuǎn)是正面還是反面），每個分支代表測試的結(jié)果，每個葉節(jié)點代表一個類標(biāo)簽（在計算所有屬性之后做出的決定）。從根到葉子的路徑表示分類規(guī)則。定義1.決策樹基本概念生活中的決策樹2(Decision Tree)屬性測試屬性測試決定決定

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

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

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

6、系統(tǒng)技術(shù)學(xué)報上發(fā)表論文A Mathematical Theory of Communication，首次建立通訊過程的數(shù)學(xué)模型，成為現(xiàn)代信息論研究的開端。香農(nóng)理論的重要特征是熵（entropy）的概念，他證明熵與信息內(nèi)容的不確定程度有等價關(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) 這一詞最初來源于熱力學(xué)。1948年，克勞德愛爾伍德香農(nóng)將熱力學(xué)中的熵引入信息論，所以也被稱為香農(nóng)熵 (Shannon entropy)，信息熵 (information entropy)。表示系統(tǒng)的不確定性。 公式：信息熵)(log)()(1log)()(212iniiiixpxpxpExIEXH譬如袋子里有紅球和黑球，取紅球譬如袋子里有紅球和黑球，取紅球的概率的概率為為0.4，取黑球的概率為，取黑球的概率為0.6。取出紅球的信息量取出紅球的信息量為為1.322，取出黑球的取出黑球的信息量信息量0.737。取出。取出1個球的加權(quán)個球的加權(quán)平均信

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

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

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

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

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

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

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

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

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

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

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

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