人工智能之決策樹

決策樹2021/6/271決策樹基本概念信息論基礎(chǔ)應(yīng)用實(shí)例及ID3算法決策樹總結(jié)一些思考目錄2021/6/272生活中的決策樹1(DecisionTree)決策樹基本概念2021/6/273Adecisiontreeisaflowchart-likestructureinwhicheachinternalnoderepresentsa"test"onanattribute(e.g.whetheracoinflipcomesupheadsortails),eachbranchrepresentstheoutcomeofthetest,andeachleafnoderepresentsaclasslabel(decisiontakenaftercomputingallattributes).Thepathsfromroottoleafrepresentclassificationrules.決策樹是一種類似于流程圖的結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)代表一個(gè)屬性上的“測(cè)試”（例如，一個(gè)硬幣的翻轉(zhuǎn)是正面還是反面），每個(gè)分支代表測(cè)試的結(jié)果，每個(gè)葉節(jié)點(diǎn)代表一個(gè)類標(biāo)簽（在計(jì)算所有屬性之后做出的決定）。從根到葉子的路徑表示分類規(guī)則。定義決策樹基本概念2021/6/274生活中的決策樹2(DecisionTree)屬性測(cè)試屬性測(cè)試決定決定分支構(gòu)建決策樹的關(guān)鍵問題：1.以何種屬性進(jìn)行測(cè)試2.以何種順序進(jìn)行測(cè)試3.何時(shí)做出決定決策樹基本概念2021/6/275連接主義者認(rèn)為，機(jī)器學(xué)習(xí)分為監(jiān)督學(xué)習(xí)，無監(jiān)督學(xué)習(xí)和強(qiáng)化學(xué)習(xí)。監(jiān)督學(xué)習(xí)就是訓(xùn)練樣本帶有屬性標(biāo)簽。監(jiān)督學(xué)習(xí)又可分為“回歸”和“分類”問題。機(jī)器學(xué)習(xí)中的分類技術(shù)一般是用一種學(xué)習(xí)算法確定分類模型，該模型可以很好地?cái)M合類標(biāo)號(hào)和屬性集之間的映射關(guān)系。常用的分類算法包括：決策樹分類法、邏輯回歸分類法、神經(jīng)網(wǎng)絡(luò)、支持向量級(jí)、樸素貝葉斯分類方法等。機(jī)器學(xué)習(xí)中的決策樹（1/2）決策樹基本概念2021/6/276在機(jī)器學(xué)習(xí)中，決策樹是一個(gè)帶有標(biāo)簽的監(jiān)督式學(xué)習(xí)預(yù)測(cè)模型，代表的是對(duì)象屬性與對(duì)象值之間的一種映射關(guān)系。算法ID3，C4.5和C5.0是基于信息學(xué)理論中熵的理論而設(shè)計(jì)的。相比大多數(shù)分類算法，如kNN等，決策樹易于理解和實(shí)現(xiàn)，使用者無需了解很多背景知識(shí)。它能夠?qū)?shù)據(jù)集合進(jìn)行分析，挖掘其中蘊(yùn)含的知識(shí)信息。機(jī)器學(xué)習(xí)中的決策樹（2/2）決策樹基本概念2021/6/277決策樹算法采用自上至下遞歸建樹的技術(shù)，該算法的產(chǎn)生源于CLS系統(tǒng)，即概念學(xué)習(xí)系統(tǒng)。決策樹算法發(fā)展歷史(1/2)決策樹基本概念2021/6/2781980年，戈登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)行改造，使決策樹可以遞增式生成，得到ID4算法。1988年，Utgoff在ID4基礎(chǔ)上提出了ID5學(xué)習(xí)算法1993年，Quinlan進(jìn)一步發(fā)展了ID3算法，改進(jìn)成C4.5算法。另一類決策樹算法為CART，與C4.5不同的是，CART的決策樹由二元邏輯問題生成，每個(gè)樹節(jié)點(diǎn)只有兩個(gè)分枝，分別包括學(xué)習(xí)實(shí)例的正例與反例決策樹算法發(fā)展歷史(2/2)決策樹基本概念2021/6/279決策樹重要概念決策樹基本概念2021/6/2710信息的大小可以度量么？信息量的大小與概率有關(guān)！概率越小，信息量越大。出現(xiàn)概率為0，信息量無窮大概率越大，信息量越小。出現(xiàn)概率為1，信息量為0.信息量2.信息論基礎(chǔ)2021/6/27111948年10月，香農(nóng)在《貝爾系統(tǒng)技術(shù)學(xué)報(bào)》上發(fā)表論文《AMathematicalTheoryofCommunication》，首次建立通訊過程的數(shù)學(xué)模型，成為現(xiàn)代信息論研究的開端。香農(nóng)理論的重要特征是熵（entropy）的概念，他證明熵與信息內(nèi)容的不確定程度有等價(jià)關(guān)系。信息論2.信息論基礎(chǔ)2021/6/2712消息發(fā)生后所含有的信息量，反映了消息發(fā)生前的不確定性：信息量譬如袋子里有紅球和黑球，取紅球的概率為0.4，取黑球的概率為0.6。取出紅球的信息量為1.322，取出黑球的信息量0.737。2.信息論基礎(chǔ)2021/6/2713熵(entropy)這一詞最初來源于熱力學(xué)。1948年，克勞德·愛爾伍德·香農(nóng)將熱力學(xué)中的熵引入信息論，所以也被稱為香農(nóng)熵(Shannonentropy)，信息熵(informationentropy)。表示系統(tǒng)的不確定性。公式：信息熵譬如袋子里有紅球和黑球，取紅球的概率為0.4，取黑球的概率為0.6。取出紅球的信息量為1.322，取出黑球的信息量0.737。取出1個(gè)球的加權(quán)平均信息量為1.322*0.4+0.737*0.6。思考：什么情況下，熵最大？2.信息論基礎(chǔ)2021/6/2714條件熵H(X|Y)表示在已知隨機(jī)變量Y的條件下隨機(jī)變量X的不確定性。H(X|Y)，其實(shí)質(zhì)是給定Y情況下X條件概率分布的熵，對(duì)Y的數(shù)學(xué)期望：條件熵2.信息論基礎(chǔ)2021/6/2715條件熵和互信息量2.信息論基礎(chǔ)互信息量，又稱信息增益2021/6/2716Y代表性別，取值為男和女；X代表穿著，取值為裙子和褲子。信息增益計(jì)算實(shí)例男女裙子0.20.50.7褲子0.20.10.30.40.6注意：H（Y/X）代表已知某人穿著，其性別的不確定性2.信息論基礎(chǔ)求信息增益：I(X;Y)=H(Y)-H（Y/X）2021/6/2717首先計(jì)算條件熵2.信息論基礎(chǔ)Step1：計(jì)算信息熵Step2：計(jì)算給定X條件下，Y條件概率的熵Step3：Y條件概率的熵值對(duì)X求數(shù)學(xué)期望2021/6/2718其次計(jì)算信息增益2.信息論基礎(chǔ)互信息量，也就是隨機(jī)變量X對(duì)隨機(jī)變量Y的信息增益2021/6/2719ID3由RossQuinlan在1986年提出。其核心是根據(jù)“最大信息熵增益”原則選擇劃分當(dāng)前數(shù)據(jù)集的最好特征，減少數(shù)據(jù)的熵(混亂度)。ID3是一種貪心算法：1）從根結(jié)點(diǎn)(rootnode)開始，對(duì)結(jié)點(diǎn)計(jì)算所有可能的特征的信息增益，選擇信息增益最大的特征作為節(jié)點(diǎn)的特征。2）由該特征的不同取值建立子節(jié)點(diǎn)，再對(duì)子節(jié)點(diǎn)遞歸地調(diào)用以上方法，構(gòu)建決策樹；直到所有特征的信息增益均很小或沒有特征可以選擇為止；3）最后得到一個(gè)決策樹。每次選取的分割數(shù)據(jù)的特征都是當(dāng)前的最佳選擇，并按照該特征的所有取值來切分，也就是說如果一個(gè)特征有4種取值，數(shù)據(jù)將被切分4份。ID3算法簡(jiǎn)介3.應(yīng)用實(shí)例及ID3算法2021/6/2720ID3算法偽代碼2021/6/2721ID年齡有工作有房子信貸情況類別(是否放貸)1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否應(yīng)用實(shí)例：是否放貸的決策樹對(duì)特征進(jìn)行標(biāo)注（預(yù)處理）年齡：0代表青年，1代表中年，2代表老年；有工作：0代表否，1代表是；有自己的房子：0代表否，1代表是；信貸情況：0代表一般，1代表好，2代表非常好；類別(是否給貸款)：no代表否，yes代表是。3.應(yīng)用實(shí)例及ID3算法2021/6/2722信息熵計(jì)算公式采用頻率替代概率。數(shù)據(jù)集D為是否放貸的類別，Ck代表該類別的某一取值的出現(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算法2021/6/2723/c406495762/article/details/75663451?utm_source=blogxgwz5三個(gè)源文件：ent.py計(jì)算數(shù)據(jù)集D類別的信息熵entgain.py分別計(jì)算各個(gè)特征對(duì)計(jì)算數(shù)據(jù)集D類別的信息增益id3.pyID3算法Python程序展示3.應(yīng)用實(shí)例及ID3算法2021/6/2724決策樹生成算法遞歸的產(chǎn)生決策樹，直到不能繼續(xù)下去為止，這樣產(chǎn)生的樹往往對(duì)訓(xùn)練數(shù)據(jù)的分類很準(zhǔn)確，但對(duì)未知測(cè)試數(shù)據(jù)的分類缺沒有那么精確，即會(huì)出現(xiàn)過擬合現(xiàn)象。過擬合產(chǎn)生的原因在于在學(xué)習(xí)時(shí)過多的考慮如何提高對(duì)訓(xùn)練數(shù)據(jù)的正確分類，從而構(gòu)建出過于復(fù)雜的決策樹，解決方法是考慮決策樹的復(fù)雜度，對(duì)已經(jīng)生成的樹進(jìn)行簡(jiǎn)化。剪枝（pruning）：從已經(jīng)生成的樹上裁掉一些子樹或葉節(jié)點(diǎn)，并將其根節(jié)點(diǎn)或父節(jié)點(diǎn)作為新的葉子節(jié)點(diǎn)，從而簡(jiǎn)化分類樹模型。實(shí)現(xiàn)方式：極小化決策樹整體的損失函數(shù)或代價(jià)函數(shù)來實(shí)現(xiàn)決策樹剪枝3.應(yīng)用實(shí)例及ID3算法2021/6/2725損失函數(shù)定義(1/2)Ntk代表t個(gè)葉子上的第k種類型個(gè)數(shù)3.應(yīng)用實(shí)例及ID3算法2021/6/2726損失函數(shù)定義(2/2)3.應(yīng)用實(shí)例及ID3算法2021/6/2727

C4.5是RossQuinlan在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中是用信息增益比率(gainratio)來作為選擇分支的準(zhǔn)則。信息增益比率通過引入一個(gè)被稱作分裂信息(Splitinformation)的項(xiàng)來懲罰取值較多的Feature。除此之外，C4.5還彌補(bǔ)了ID3中不能處理特征屬性值連續(xù)的問題。但是，對(duì)連續(xù)屬性值需要掃描排序，會(huì)使C4.5性能下降，有興趣可以參考博客。C4.5算法簡(jiǎn)介3.應(yīng)用實(shí)例及ID3算法2021/6/2728信息增益比率定義3.應(yīng)用實(shí)例及ID3算法2021/6/27291.決策樹又叫判定樹，是一種基本的分類與回歸方法。2.優(yōu)點(diǎn)：可讀性強(qiáng)，分類速度快，容易轉(zhuǎn)換成if-then分類規(guī)則3.通常分為3個(gè)步驟：特征（屬性）選擇、決策樹的生成、決策樹的修剪。4.特征選擇即選擇分裂屬性，又叫屬性選擇度量，把數(shù)據(jù)劃分成較小的分區(qū)。5.決策樹的生成又叫決策樹學(xué)習(xí)或者決策樹歸納。6.決策樹生成時(shí)采用貪心（即非回溯的、局部最優(yōu)的）方法，以自頂向下遞歸的分治方式構(gòu)造，只考慮局部最優(yōu)。7.決策樹修剪時(shí)遞歸地從樹的葉節(jié)點(diǎn)向上回縮，考慮全局最優(yōu)。8.決策算法之間的差別包括在創(chuàng)建樹時(shí)如何選擇屬性和用于剪枝的機(jī)制。9.決策算法主要為：ID3算法，C4.5算法和CART算法。決策樹總結(jié)(1/2)4.決策樹總結(jié)2021/6/273010.ID3算法和C4.5算法只有決策樹的生成，沒有對(duì)決策樹進(jìn)行剪枝。CART算法包括決策樹的剪枝。11.在進(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)則調(diào)整了這種偏倚，但它傾向于產(chǎn)生不平衡的劃分，其中一個(gè)分區(qū)比其他分區(qū)小得多；基尼指數(shù)準(zhǔn)則也是偏向于多值屬性，并且當(dāng)類的數(shù)量很大時(shí)會(huì)有困難。13.所有的屬性選擇度量都具有某種偏倚。14.決策樹歸納時(shí)的時(shí)間復(fù)雜度一般隨樹的高度指數(shù)增加。因此，傾向于產(chǎn)生較淺的樹（如多路劃分而不是二元?jiǎng)澐郑┑亩攘靠赡芨扇?。但是，較淺的樹趨向于具有大量樹葉和較高的準(zhǔn)確率。15.信息增益的度量標(biāo)準(zhǔn)：熵。熵越大，隨機(jī)變量的不確定性就越大，分類能力就越低.決策樹總結(jié)(2/2)4.決策樹總結(jié)2021/6/273110.ID3算法和C4.5算法只有決策樹的生成，沒有對(duì)決策樹進(jìn)行剪枝。CART算法包括決策樹的剪枝。11.在進(jìn)行特征選擇時(shí)，各個(gè)算法采用的選擇分裂準(zhǔn)則不同:ID3算法使用信息增益準(zhǔn)則，選擇信息增益最大(熵最小)的特征作為分裂屬性。C4.5