人工智能之決策樹(shù)_第1頁(yè)
人工智能之決策樹(shù)_第2頁(yè)
人工智能之決策樹(shù)_第3頁(yè)
人工智能之決策樹(shù)_第4頁(yè)
人工智能之決策樹(shù)_第5頁(yè)
已閱讀5頁(yè),還剩28頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

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)生不平

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論