决策树基础梳理
1.信息論基礎(chǔ)
1.1.熵
熵是信息的關(guān)鍵度量，通常指一條信息中需要傳輸或者存儲(chǔ)一個(gè)信號(hào)的平均比特?cái)?shù)。熵衡量了預(yù)測(cè)隨機(jī)變量的不確定度，不確定性越大熵越大。
針對(duì)隨機(jī)變量XX，其信息熵的定義如下：
信息熵是信源編碼中，壓縮率的下限。當(dāng)我們使用少于信息熵的信息量做編碼，那么一定有信息的損失。
1.2.聯(lián)合熵
聯(lián)合熵是一集變量之間不確定的衡量手段。
1.3.條件熵
條件熵描述變量Y在變量X確定的情況下，變量Y的熵還剩多少。
聯(lián)合熵和條件熵的關(guān)系是：
1.4.信息增益
信息增益在決策樹(shù)算法中是用來(lái)選擇特征的指標(biāo)，信息增益越大，則這個(gè)特征的選擇性越好，在概率中定義為：待分類(lèi)的集合的熵和選定某個(gè)特征的條件熵之差（這里只的是經(jīng)驗(yàn)熵或經(jīng)驗(yàn)條件熵，由于真正的熵并不知道，是根據(jù)樣本計(jì)算出來(lái)的），公式如下：
1.5.基尼不純度
基尼不純度：將來(lái)自集合的某種結(jié)果隨機(jī)應(yīng)用于某一數(shù)據(jù)項(xiàng)的預(yù)期誤差率。?
- （1）顯然基尼不純度越小，純度越高，集合的有序程度越高，分類(lèi)的效果越好；
- （2）基尼不純度為 0 時(shí)，表示集合類(lèi)別一致；
- （3）基尼不純度最高（純度最低）時(shí)，
?
?
?
?
?
2.ID3算法
2.1原理
ID3算法的核心是在決策樹(shù)各個(gè)結(jié)點(diǎn)上應(yīng)用信息增益準(zhǔn)則選擇特征，遞歸地構(gòu)建決策樹(shù)。具體方法是：從根結(jié)點(diǎn)開(kāi)始，對(duì)結(jié)點(diǎn)計(jì)算所有可能的特征的信息增益，選擇信息增益最大的特征作為結(jié)點(diǎn)的特征，由該特征的不同取值建立子結(jié)點(diǎn)；再對(duì)子結(jié)點(diǎn)遞歸地調(diào)用以上方法，構(gòu)建決策樹(shù)；直到所有特征的信息增益均很小或沒(méi)有特征可以選擇為止。最后得到一個(gè)決策樹(shù)，ID3相當(dāng)于用極大似然法進(jìn)行概率模型的選擇
2.2過(guò)程
1.決策樹(shù)開(kāi)始時(shí)，作為一個(gè)單個(gè)節(jié)點(diǎn)（根節(jié)點(diǎn)）包含所有訓(xùn)練樣本集
2.若一個(gè)節(jié)點(diǎn)的樣本均為同一類(lèi)別，則該節(jié)點(diǎn)就成為葉節(jié)點(diǎn)并標(biāo)記為該類(lèi)別。否則算法將采用信息熵（成為信息增益）作為啟發(fā)指示來(lái)幫助選擇合適的（分支）屬性，以便將樣本集劃分為若干自己。選擇能夠最好地講樣本分類(lèi)的屬性。該屬性成為該節(jié)點(diǎn)的“測(cè)試”或“判定”屬性。在算法中，所有屬性均為離散值，若有取連續(xù)值的屬性，必須首先將其離散化。
3.對(duì)測(cè)試屬性的每個(gè)已知的值，創(chuàng)建一個(gè)分支，并據(jù)此劃分樣本
4.算法使用同樣的過(guò)程，遞歸的形成每個(gè)劃分上的樣本判定樹(shù)。一旦一個(gè)屬性出現(xiàn)在一個(gè)節(jié)點(diǎn)上，就不必考慮該節(jié)點(diǎn)的任何后代
遞歸劃分步驟僅當(dāng)下列條件之一成立時(shí)立即停止：
1.給定節(jié)點(diǎn)的所有樣本屬于同一類(lèi)
2.沒(méi)有剩余屬性可以用來(lái)進(jìn)一步劃分樣本。在此情況下，使用多數(shù)表決，講給定的節(jié)點(diǎn)轉(zhuǎn)換成樹(shù)葉，并用樣本中的多數(shù)所在的類(lèi)標(biāo)記它。另外，可以存放節(jié)點(diǎn)樣本的類(lèi)分布。
3.分支test_attribute=a(i),沒(méi)有樣本。在這種情況下，以samples中的多數(shù)類(lèi)創(chuàng)建一個(gè)樹(shù)葉。
2.3優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
理論清晰，算法簡(jiǎn)單，很有實(shí)用價(jià)值的示例學(xué)習(xí)算法；
計(jì)算時(shí)間是例子個(gè)數(shù)、特征屬性個(gè)數(shù)、節(jié)點(diǎn)個(gè)數(shù)之積的線(xiàn)性函數(shù)，總預(yù)測(cè)準(zhǔn)確率較令人滿(mǎn)意
缺點(diǎn)：
存在偏向問(wèn)題，各特征屬性的取值個(gè)數(shù)會(huì)影響互信息量的大小；
特征屬性間的相關(guān)性強(qiáng)調(diào)不夠，是單變?cè)惴?#xff1b;
對(duì)噪聲較為敏感，訓(xùn)練數(shù)據(jù)的輕微錯(cuò)誤會(huì)導(dǎo)致結(jié)果的不同；魯棒性
結(jié)果隨訓(xùn)練集記錄個(gè)數(shù)的改變而不同，不便于進(jìn)行漸進(jìn)學(xué)習(xí)
3.C4.5
3.1原理
C4.5算法是用于生成決策樹(shù)的一種經(jīng)典算法，是ID3算法的一種延伸和優(yōu)化。
C4.5算法采用PEP(Pessimistic Error Pruning)剪枝法
C4.5算法通過(guò)信息增益率選擇分裂屬性。
?? 屬性A的“分裂信息”(split information)：、
?
其中，訓(xùn)練數(shù)據(jù)集S通過(guò)屬性A的屬性值劃分為m個(gè)子數(shù)據(jù)集，|Sj||Sj|表示第j個(gè)子數(shù)據(jù)集中樣本數(shù)量，|S||S|表示劃分之前數(shù)據(jù)集中樣本總數(shù)量。
?? 通過(guò)屬性A分裂之后樣本集的信息增益：
?
?? 通過(guò)屬性A分裂之后樣本集的信息增益率：
?
??通過(guò)C4.5算法構(gòu)造決策樹(shù)時(shí)，信息增益率最大的屬性即為當(dāng)前節(jié)點(diǎn)的分裂屬性，隨著遞歸計(jì)算，被計(jì)算的屬性的信息增益率會(huì)變得越來(lái)越小，到后期則選擇相對(duì)比較大的信息增益率的屬性作為分裂屬性。
3.2過(guò)程
?
3.3優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
（1）通過(guò)信息增益率選擇分裂屬性，克服了ID3算法中通過(guò)信息增益傾向于選擇擁有多個(gè)屬性值的屬性作為分裂屬性的不足；
（2）能夠處理離散型和連續(xù)型的屬性類(lèi)型，即將連續(xù)型的屬性進(jìn)行離散化處理；
（3）構(gòu)造決策樹(shù)之后進(jìn)行剪枝操作；
（4）能夠處理具有缺失屬性值的訓(xùn)練數(shù)據(jù)。
缺點(diǎn)：
（1）算法的計(jì)算效率較低，特別是針對(duì)含有連續(xù)屬性值的訓(xùn)練樣本時(shí)表現(xiàn)的尤為突出。
（2）算法在選擇分裂屬性時(shí)沒(méi)有考慮到條件屬性間的相關(guān)性，只計(jì)算數(shù)據(jù)集中每一個(gè)條件屬性與決策屬性之間的期望信息，有可能影響到屬性選擇的正確性。
4.CART分類(lèi)樹(shù)
4.1原理
Classification And Regression Tree(CART)是決策樹(shù)的一種，并且是非常重要的決策樹(shù)，屬于Top Ten Machine Learning Algorithm。顧名思義，CART算法既可以用于創(chuàng)建分類(lèi)樹(shù)（Classification Tree），也可以用于創(chuàng)建回歸樹(shù)（Regression Tree）、模型樹(shù)（Model Tree），兩者在建樹(shù)的過(guò)程稍有差異。前文“機(jī)器學(xué)習(xí)經(jīng)典算法詳解及Python實(shí)現(xiàn)–決策樹(shù)（Decision Tree）”詳細(xì)介紹了分類(lèi)決策樹(shù)原理以及ID3、C4.5算法，本文在該文的基礎(chǔ)上詳述CART算法在決策樹(shù)分類(lèi)以及樹(shù)回歸中的應(yīng)用。?
創(chuàng)建分類(lèi)樹(shù)遞歸過(guò)程中，CART每次都選擇當(dāng)前數(shù)據(jù)集中具有最小Gini信息增益的特征作為結(jié)點(diǎn)劃分決策樹(shù)。ID3算法和C4.5算法雖然在對(duì)訓(xùn)練樣本集的學(xué)習(xí)中可以盡可能多地挖掘信息，但其生成的決策樹(shù)分支、規(guī)模較大，CART算法的二分法可以簡(jiǎn)化決策樹(shù)的規(guī)模，提高生成決策樹(shù)的效率。對(duì)于連續(xù)特征，CART也是采取和C4.5同樣的方法處理。為了避免過(guò)擬合(Overfitting)，CART決策樹(shù)需要剪枝。預(yù)測(cè)過(guò)程當(dāng)然也就十分簡(jiǎn)單，根據(jù)產(chǎn)生的決策樹(shù)模型，延伸匹配特征值到最后的葉子節(jié)點(diǎn)即得到預(yù)測(cè)的類(lèi)別。?
創(chuàng)建回歸樹(shù)時(shí)，觀(guān)察值取值是連續(xù)的、沒(méi)有分類(lèi)標(biāo)簽，只有根據(jù)觀(guān)察數(shù)據(jù)得出的值來(lái)創(chuàng)建一個(gè)預(yù)測(cè)的規(guī)則。在這種情況下，Classification Tree的最優(yōu)劃分規(guī)則就無(wú)能為力，CART則使用最小剩余方差(Squared Residuals Minimization)來(lái)決定Regression Tree的最優(yōu)劃分，該劃分準(zhǔn)則是期望劃分之后的子樹(shù)誤差方差最小。創(chuàng)建模型樹(shù)，每個(gè)葉子節(jié)點(diǎn)則是一個(gè)機(jī)器學(xué)習(xí)模型，如線(xiàn)性回歸模型
CART算法的重要基礎(chǔ)包含以下三個(gè)方面：?
（1）二分(Binary Split)：在每次判斷過(guò)程中，都是對(duì)觀(guān)察變量進(jìn)行二分。?
CART算法采用一種二分遞歸分割的技術(shù)，算法總是將當(dāng)前樣本集分割為兩個(gè)子樣本集，使得生成的決策樹(shù)的每個(gè)非葉結(jié)點(diǎn)都只有兩個(gè)分枝。因此CART算法生成的決策樹(shù)是結(jié)構(gòu)簡(jiǎn)潔的二叉樹(shù)。因此CART算法適用于樣本特征的取值為是或非的場(chǎng)景，對(duì)于連續(xù)特征的處理則與C4.5算法相似。?
（2）單變量分割(Split Based on One Variable)：每次最優(yōu)劃分都是針對(duì)單個(gè)變量。?
（3）剪枝策略：CART算法的關(guān)鍵點(diǎn)，也是整個(gè)Tree-Based算法的關(guān)鍵步驟。?
剪枝過(guò)程特別重要，所以在最優(yōu)決策樹(shù)生成過(guò)程中占有重要地位。有研究表明，剪枝過(guò)程的重要性要比樹(shù)生成過(guò)程更為重要，對(duì)于不同的劃分標(biāo)準(zhǔn)生成的最大樹(shù)(Maximum Tree)，在剪枝之后都能夠保留最重要的屬性劃分，差別不大。反而是剪枝方法對(duì)于最優(yōu)樹(shù)的生成更為關(guān)鍵。
4.2過(guò)程
CART假設(shè)決策樹(shù)是二叉樹(shù)，內(nèi)部結(jié)點(diǎn)特征的取值為“是”和“否”，左分支是取值為“是”的分支，右分支是取值為“否”的分支。這樣的決策樹(shù)等價(jià)于遞歸地二分每個(gè)特征，將輸入空間即特征空間劃分為有限個(gè)單元，并在這些單元上確定預(yù)測(cè)的概率分布，也就是在輸入給定的條件下輸出的條件概率分布。
CART算法由以下兩步組成：
1.決策樹(shù)生成：基于訓(xùn)練數(shù)據(jù)集生成決策樹(shù)，生成的決策樹(shù)要盡量大；?決策樹(shù)剪枝：用驗(yàn)證數(shù)據(jù)集對(duì)已生成的樹(shù)進(jìn)行剪枝并選擇最優(yōu)子樹(shù)，這時(shí)損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)。
2.CART決策樹(shù)的生成就是遞歸地構(gòu)建二叉決策樹(shù)的過(guò)程。CART決策樹(shù)既可以用于分類(lèi)也可以用于回歸。本文我們僅討論用于分類(lèi)的CART。對(duì)分類(lèi)樹(shù)而言，CART用Gini系數(shù)最小化準(zhǔn)則來(lái)進(jìn)行特征選擇，生成二叉樹(shù)。 CART生成算法如下：
輸入：訓(xùn)練數(shù)據(jù)集D，停止計(jì)算的條件：?
輸出：CART決策樹(shù)。
根據(jù)訓(xùn)練數(shù)據(jù)集，從根結(jié)點(diǎn)開(kāi)始，遞歸地對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行以下操作，構(gòu)建二叉決策樹(shù)：
設(shè)結(jié)點(diǎn)的訓(xùn)練數(shù)據(jù)集為D，計(jì)算現(xiàn)有特征對(duì)該數(shù)據(jù)集的Gini系數(shù)。此時(shí)，對(duì)每一個(gè)特征A，對(duì)其可能取的每個(gè)值a，根據(jù)樣本點(diǎn)對(duì)A=a的測(cè)試為“是”或 “否”將D分割成D1和D2兩部分，計(jì)算A=a時(shí)的Gini系數(shù)。?
在所有可能的特征A以及它們所有可能的切分點(diǎn)a中，選擇Gini系數(shù)最小的特征及其對(duì)應(yīng)的切分點(diǎn)作為最優(yōu)特征與最優(yōu)切分點(diǎn)。依最優(yōu)特征與最優(yōu)切分點(diǎn)，從現(xiàn)結(jié)點(diǎn)生成兩個(gè)子結(jié)點(diǎn)，將訓(xùn)練數(shù)據(jù)集依特征分配到兩個(gè)子結(jié)點(diǎn)中去。?
對(duì)兩個(gè)子結(jié)點(diǎn)遞歸地調(diào)用步驟l~2，直至滿(mǎn)足停止條件。?
生成CART決策樹(shù)。?
算法停止計(jì)算的條件是結(jié)點(diǎn)中的樣本個(gè)數(shù)小于預(yù)定閾值，或樣本集的Gini系數(shù)小于預(yù)定閾值（樣本基本屬于同一類(lèi)），或者沒(méi)有更多特征。
五.連續(xù)特征和離散特征處理
?
六.剪枝 模型評(píng)估
由于決策樹(shù)的建立完全是依賴(lài)于訓(xùn)練樣本，因此該決策樹(shù)對(duì)訓(xùn)練樣本能夠產(chǎn)生完美的擬合效果。但這樣的決策樹(shù)對(duì)于測(cè)試樣本來(lái)說(shuō)過(guò)于龐大而復(fù)雜，可能產(chǎn)生較高的分類(lèi)錯(cuò)誤率。這種現(xiàn)象就稱(chēng)為過(guò)擬合。因此需要將復(fù)雜的決策樹(shù)進(jìn)行簡(jiǎn)化，即去掉一些節(jié)點(diǎn)解決過(guò)擬合問(wèn)題，這個(gè)過(guò)程稱(chēng)為剪枝。
??剪枝方法分為預(yù)剪枝和后剪枝兩大類(lèi)。預(yù)剪枝是在構(gòu)建決策樹(shù)的過(guò)程中，提前終止決策樹(shù)的生長(zhǎng)，從而避免過(guò)多的節(jié)點(diǎn)產(chǎn)生。預(yù)剪枝方法雖然簡(jiǎn)單但實(shí)用性不強(qiáng)，因?yàn)楹茈y精確的判斷何時(shí)終止樹(shù)的生長(zhǎng)。后剪枝是在決策樹(shù)構(gòu)建完成之后，對(duì)那些置信度不達(dá)標(biāo)的節(jié)點(diǎn)子樹(shù)用葉子結(jié)點(diǎn)代替，該葉子結(jié)點(diǎn)的類(lèi)標(biāo)號(hào)用該節(jié)點(diǎn)子樹(shù)中頻率最高的類(lèi)標(biāo)記。后剪枝方法又分為兩種，一類(lèi)是把訓(xùn)練數(shù)據(jù)集分成樹(shù)的生長(zhǎng)集和剪枝集；另一類(lèi)算法則是使用同一數(shù)據(jù)集進(jìn)行決策樹(shù)生長(zhǎng)和剪枝。常見(jiàn)的后剪枝方法有CCP(Cost Complexity Pruning)、REP(Reduced Error Pruning)、PEP(Pessimistic Error Pruning)、MEP(Minimum Error Pruning)。
PEP(Pessimistic Error Pruning)剪枝法??
PEP剪枝法由Quinlan提出，是一種自上而下的剪枝法，根據(jù)剪枝前后的錯(cuò)誤率來(lái)判定是否進(jìn)行子樹(shù)的修剪，因此不需要單獨(dú)的剪枝數(shù)據(jù)集。
對(duì)于一個(gè)葉子節(jié)點(diǎn)，它覆蓋了n個(gè)樣本，其中有e個(gè)錯(cuò)誤，那么該葉子節(jié)點(diǎn)的錯(cuò)誤率為其中0.5為懲罰因子（懲罰因子一般取值為0.5）。?
?? 對(duì)于一棵子樹(shù)，它有L個(gè)葉子節(jié)點(diǎn)，那么該子樹(shù)的誤判率為：
其中，ei表示子樹(shù)第i個(gè)葉子節(jié)點(diǎn)錯(cuò)誤分類(lèi)的樣本數(shù)量，ni表示表示子樹(shù)第i個(gè)葉子節(jié)點(diǎn)中樣本的總數(shù)量。
?? 假設(shè)一棵子樹(shù)錯(cuò)誤分類(lèi)一個(gè)樣本取值為1，正確分類(lèi)一個(gè)樣本取值為0，那么子樹(shù)的誤判次數(shù)可以認(rèn)為是一個(gè)伯努利分布，因此可以得到該子樹(shù)誤判次數(shù)的均值和標(biāo)準(zhǔn)差：
?
?? 把子樹(shù)替換成葉子節(jié)點(diǎn)后，該葉子節(jié)點(diǎn)的誤判率為：
?
?
其中，
?
?
?? 同時(shí)，該葉子結(jié)點(diǎn)的誤判次數(shù)也是一個(gè)伯努利分布，因此該葉子節(jié)點(diǎn)誤判次數(shù)的均值為：
?? 剪枝的條件為：
?
滿(mǎn)足剪枝條件時(shí)，則將所得葉子節(jié)點(diǎn)替換該子樹(shù)，即為剪枝操作。
CCP（代價(jià)復(fù)雜度）剪枝法
代價(jià)復(fù)雜度選擇節(jié)點(diǎn)表面誤差率增益值最小的非葉子節(jié)點(diǎn)，刪除該非葉子節(jié)點(diǎn)的左右子節(jié)點(diǎn)，若有多個(gè)非葉子節(jié)點(diǎn)的表面誤差率增益值相同小，則選擇非葉子節(jié)點(diǎn)中子節(jié)點(diǎn)數(shù)最多的非葉子節(jié)點(diǎn)進(jìn)行剪枝。
可描述如下：
令決策樹(shù)的非葉子節(jié)點(diǎn)為。
a）計(jì)算所有非葉子節(jié)點(diǎn)的表面誤差率增益值?
b）選擇表面誤差率增益值最小的非葉子節(jié)點(diǎn)（若多個(gè)非葉子節(jié)點(diǎn)具有相同小的表面誤差率增益值，選擇節(jié)點(diǎn)數(shù)最多的非葉子節(jié)點(diǎn)）。
c）對(duì)進(jìn)行剪枝
表面誤差率增益值的計(jì)算公式：
?
其中：
表示葉子節(jié)點(diǎn)的誤差代價(jià)，?，?為節(jié)點(diǎn)的錯(cuò)誤率，?為節(jié)點(diǎn)數(shù)據(jù)量的占比；
表示子樹(shù)的誤差代價(jià)，?，?為子節(jié)點(diǎn)i的錯(cuò)誤率，?表示節(jié)點(diǎn)i的數(shù)據(jù)節(jié)點(diǎn)占比；
表示子樹(shù)節(jié)點(diǎn)個(gè)數(shù)。
算例：
下圖是其中一顆子樹(shù)，設(shè)決策樹(shù)的總數(shù)據(jù)量為40。
該子樹(shù)的表面誤差率增益值可以計(jì)算如下：
?
求出該子樹(shù)的表面錯(cuò)誤覆蓋率為 ，只要求出其他子樹(shù)的表面誤差率增益值就可以對(duì)決策樹(shù)進(jìn)行剪枝。
七.sklearn參數(shù)詳解
https://blog.csdn.net/young_gy/article/details/69666014?
?https://blog.csdn.net/u014688145/article/details/53212112?
https://blog.csdn.net/yjt13/article/details/72794557?
https://blog.csdn.net/zhihua_oba/article/details/70632622
?https://blog.csdn.net/e15273/article/details/79648502
轉(zhuǎn)載于:https://www.cnblogs.com/Sugar-Chl/p/10121953.html
總結(jié)
- 上一篇： Volatile 关键字 内存可见性
- 下一篇： windows 10占用cpu和内存过高