0x00 內(nèi)容
決策樹：決策樹、信息熵、基尼系數(shù)、CART
實(shí)踐：代碼實(shí)現(xiàn)決策樹
0x01 決策樹
決策樹的建模思路是盡可能模擬人做決策的過程。幾乎沒有任何抽象，完全通過生成決策規(guī)則來解決分類和回歸問題。它的運(yùn)行機(jī)制能很直接地被翻譯成人類語言，因此在學(xué)術(shù)上被歸為白盒模型（white box model）。
1.1 決策樹
決策樹的思想，類似于利用選擇做決策的過程。它是類似流程圖的結(jié)構(gòu)，其中每個(gè)內(nèi)部節(jié)點(diǎn)表示一個(gè)測試功能，即類似做出決策的過程（動作），每個(gè)葉節(jié)點(diǎn)都表示一個(gè)類標(biāo)簽，即在計(jì)算所有特征之后做出的決定（結(jié)果）。標(biāo)簽和分支表示導(dǎo)致這些類標(biāo)簽的功能的連接。從根到葉的路徑表示分類規(guī)則。
用決策樹分類：從根節(jié)點(diǎn)開始，對實(shí)例的某一特征進(jìn)行測試，根據(jù)測試結(jié)果將實(shí)例分配到其子節(jié)點(diǎn)，此時(shí)每個(gè)子節(jié)點(diǎn)對應(yīng)著該特征的一個(gè)取值，如此遞歸的對實(shí)例進(jìn)行測試并分配，直到到達(dá)葉節(jié)點(diǎn)，最后將實(shí)例分到葉節(jié)點(diǎn)的類中。
1.2 決策樹與條件概率
決策樹表示給定特征條件下，類的條件概率分布，這個(gè)條件概率分布表示在特征空間的劃分上，將特征空間根據(jù)各個(gè)特征值不斷進(jìn)行劃分，就將特征空間分為了多個(gè)不相交的單元，在每個(gè)單元定義了一個(gè)類的概率分布，這樣，這條由根節(jié)點(diǎn)到達(dá)葉節(jié)點(diǎn)的路徑就成了一個(gè)條件概率分布。
假設(shè)X表示特征的隨機(jī)變量，Y表示類的隨機(jī)變量，那么這個(gè)條件概率可以表示為P(Y|X)，其中X取值于給定劃分下單元的集合，Y取值于類的集合。各葉結(jié)點(diǎn)（單元）上的條件概率往往偏向某一個(gè)類。根據(jù)輸入的測試樣本，由路徑找到對應(yīng)單元的各個(gè)類的條件概率，并將該輸入測試樣本分為條件概率最大的一類中，就可以完成對測試樣本的分類。
0x02 決策樹的學(xué)習(xí)
2.1 學(xué)習(xí)本質(zhì)
決策樹學(xué)習(xí)本質(zhì)上是從訓(xùn)練數(shù)據(jù)集中歸納出一組分類規(guī)則。與訓(xùn)練數(shù)據(jù)集不相矛盾的決策樹（即能對訓(xùn)練數(shù)據(jù)進(jìn)行正確分類的決策樹）可能是0個(gè)或多個(gè)。我們需要找到一個(gè)與訓(xùn)練數(shù)據(jù)矛盾較小的決策樹，同時(shí)具有很好的泛化能力。
另一個(gè)角度看，決策樹學(xué)習(xí)是由訓(xùn)練數(shù)據(jù)集估計(jì)條件概率模型?；谔卣骺臻g劃分的類的條件概率模型有無窮多個(gè)。我們選擇的條件概率模型應(yīng)該不僅對訓(xùn)練數(shù)據(jù)有很好地?cái)M合，而且對未知數(shù)據(jù)有很好地預(yù)測。
2.2 決策樹損失函數(shù)
決策樹學(xué)習(xí)的損失函數(shù)通常是正則化的極大似然函數(shù)。決策樹學(xué)習(xí)的策略是以損失函數(shù)為目標(biāo)函數(shù)的最小化。（關(guān)于極大似然函數(shù)：極大似然法是屬于數(shù)理統(tǒng)計(jì)范疇，旨在由果溯因。把“極大似然估計(jì)”拆成三個(gè)詞：極大（最大的概率）、似然（看起來是這個(gè)樣子的）、估計(jì)（就是這個(gè)樣子的），連起來就是：大概率看起來是這樣的，那就是這樣。）
當(dāng)損失函數(shù)確定以后，學(xué)習(xí)問題就變?yōu)樵趽p失函數(shù)意義下選擇最優(yōu)決策樹的問題。因?yàn)閺乃锌赡艿臎Q策樹中選取最優(yōu)決策樹是NP完全問題，所以現(xiàn)實(shí)中決策樹學(xué)習(xí)算法通常采用啟發(fā)式方法，近似求解這一最優(yōu)化問題。這樣得到的決策樹是次最優(yōu)的。
0x03 決策樹的構(gòu)建
決策樹通常有三個(gè)步驟：
????特征選擇
????決策樹的生成
????決策樹的修剪
決策樹學(xué)習(xí)的算法通常是一個(gè)遞歸地選擇最優(yōu)特征，并根據(jù)該特征對訓(xùn)練數(shù)據(jù)進(jìn)行分割，使得對各個(gè)子數(shù)據(jù)集有一個(gè)最好的分類的過程。這一過程對應(yīng)著對特征空間的劃分，也對應(yīng)著決策樹的構(gòu)建。
這一過程對應(yīng)著對特征空間的劃分，也對應(yīng)著決策樹的構(gòu)建。
? ? 1.開始：構(gòu)建根節(jié)點(diǎn)，將所有訓(xùn)練數(shù)據(jù)都放在根節(jié)點(diǎn)，選擇一個(gè)最優(yōu)特征，按照這一特征將訓(xùn)練數(shù)據(jù)集分割成子集，使得各個(gè)子集有一個(gè)在當(dāng)前條件下最好的分類。
? ? 2.如果這些子集已經(jīng)能夠被基本正確分類，那么構(gòu)建葉節(jié)點(diǎn)，并將這些子集分到所對應(yīng)的葉子節(jié)點(diǎn)去。
? ? 3.如果還有子集不能夠被正確的分類，那么就對這些子集選擇新的最優(yōu)特征，繼續(xù)對其進(jìn)行分割，構(gòu)建相應(yīng)的節(jié)點(diǎn)，如此遞歸進(jìn)行，直至所有訓(xùn)練數(shù)據(jù)子集被基本正確的分類，或者沒有合適的特征為止。
? ? 4.每個(gè)子集都被分到葉節(jié)點(diǎn)上，即都有了明確的類，這樣就生成了一顆決策樹。
以上方法就是決策樹學(xué)習(xí)中的特征選擇和決策樹生成，這樣生成的決策樹可能對訓(xùn)練數(shù)據(jù)有很好的分類能力，但對未知的測試數(shù)據(jù)卻未必有很好的分類能力，即可能發(fā)生過擬合現(xiàn)象。我們需要對已生成的樹自下而上進(jìn)行剪枝，將樹變得更簡單，從而使其具有更好的泛化能力。具體地，就是去掉過于細(xì)分的葉結(jié)點(diǎn)，使其回退到父結(jié)點(diǎn)，甚至更高的結(jié)點(diǎn)，然后將父結(jié)點(diǎn)或更高的結(jié)點(diǎn)改為新的葉結(jié)點(diǎn)，從而使得模型有較好的泛化能力。
決策樹生成和決策樹剪枝是個(gè)相對的過程，決策樹生成旨在得到對于當(dāng)前子數(shù)據(jù)集最好的分類效果(局部最優(yōu))，而決策樹剪枝則是考慮全局最優(yōu)，增強(qiáng)泛化能力。
0x04 小結(jié)&問題
決策樹是一個(gè)非參數(shù)的決策算法，決策樹可以解決分類問題，且天然支持多分類問題。決策樹也可以解決回歸問題，按照樹的路徑追蹤到葉子結(jié)點(diǎn)，最終葉子節(jié)點(diǎn)對應(yīng)一個(gè)數(shù)值，且回歸問題的結(jié)果是一個(gè)具體的數(shù)值，就可以落在葉子結(jié)點(diǎn)的所有樣本的平均值，作為回歸的預(yù)測結(jié)果。
并且決策樹具有非常好的可解釋性。在構(gòu)建決策樹，首先找到一個(gè)維度，然后在維度上找到一個(gè)閾值。然后以這個(gè)維度的這個(gè)閾值為依據(jù)進(jìn)行劃分。
0x05?信息熵
5.1信息熵
信息熵表示隨機(jī)變量的不確定度。對于一組數(shù)據(jù)來說，越隨機(jī)、不確定性越高，信息熵越大；不確定性越低，信息熵越小。信息熵表示隨機(jī)變量的不確定度。對于一組數(shù)據(jù)來說，越隨機(jī)、不確定性越高，信息熵越大；不確定性越低，信息熵越小。
計(jì)算熵，需要計(jì)算所有類別所有可能值所包含的信息期望值，著名的香農(nóng)公式：
0x06?條件熵
條件熵與信息熵不同，條件熵是數(shù)學(xué)期望，而不是變量的不確定性。
條件熵意思是按一個(gè)新的變量的每個(gè)值對原變量進(jìn)行分類。然后在每一個(gè)小類里面，都計(jì)算一個(gè)小熵，然后每一個(gè)小熵乘以各個(gè)類別的概率，然后求和。
所謂小類，就是不包含當(dāng)前所選特征的其他維度，即當(dāng)前的特征是給定的條件，在其他維度下求熵，是條件下的。各類別的概率，是當(dāng)前這個(gè)小類別下的樣本量除以總的樣本量。
0x07 信息增益
在劃分?jǐn)?shù)據(jù)集前后信息發(fā)生的變化稱為信息增益，獲得信息增益最高的特征就是最好的選擇。
信息增益就是：以某特征劃分?jǐn)?shù)據(jù)集前后的熵的差值。
（在計(jì)算過程中，使用所有特征劃分?jǐn)?shù)據(jù)集D，得到多個(gè)特征劃分?jǐn)?shù)據(jù)集D的信息增益（列表）。從這些信息增益中選擇最大的，因而當(dāng)前結(jié)點(diǎn)的劃分特征便是使信息增益最大的劃分所使用的特征。對于待劃分的數(shù)據(jù)集D，其經(jīng)驗(yàn)熵H(D)是不變的，但是劃分之后得到的條件熵H(D|A)是變化的（特征A的選擇不同）。）
條件熵H(D|A)越小，說明使用此特征劃分得到的子集的不確定性越?。ㄒ簿褪羌兌仍礁撸?，因?yàn)榈玫降男畔⒃鲆婢驮酱?。說明在決策樹構(gòu)建的過程中我們總是希望集合往最快到達(dá)純度更高的子集合方向發(fā)展，因此我們總是選擇使得信息增益最大的特征來劃分當(dāng)前數(shù)據(jù)集D。
信息增益偏向取值較多的特征。
原因：當(dāng)特征的取值較多時(shí)，根據(jù)此特征劃分更容易得到純度更高的子集，因此劃分之后的熵更低，由于劃分前的熵是一定的，因此信息增益更大，因此信息增益比較偏向取值較多的特征。
0x08 信息增益率
選取信息增益大的特征，可以得到更好的劃分。但因?yàn)樾畔⒃鲆?b>偏向于選擇取值較多的特征，容易過擬合。
在信息增益的基礎(chǔ)之上乘上一個(gè)懲罰參數(shù)，對樹分支過多的情況進(jìn)行懲罰，抵消了特征變量的復(fù)雜程度，避免了過擬合的存在。
8.1 信息增益率
信息增益比本質(zhì)：是在信息增益的基礎(chǔ)之上乘上一個(gè)懲罰參數(shù)。
信息增益比 = 懲罰參數(shù) * 信息增益
懲罰參數(shù)，是數(shù)據(jù)集D以特征A作為隨機(jī)變量的熵的倒數(shù)，即：將特征A取值相同的樣本劃分到同一個(gè)子集中（之前所說數(shù)據(jù)集的熵是依據(jù)類別進(jìn)行劃分的）。
信息增益比的缺點(diǎn)是：偏向取值較少的特征。原因：當(dāng)特征取值較少時(shí)HA(D)的值較小，因此其倒數(shù)較大，因而信息增益比較大。因而偏向取值較少的特征。
基于以上特點(diǎn)，在使用增益信息比時(shí)，并不是直接選擇信息增益率最大的特征，而是現(xiàn)在候選特征中找出信息增益高于平均水平的特征，然后在這些特征中再選擇信息增益率最高的特征。
0x09?基尼系數(shù)
9.1 基尼系數(shù)的定義
基尼系數(shù)（Gini），也被稱為基尼不純度，表示在樣本集合中一個(gè)隨機(jī)選中的樣本被分錯(cuò)的概率。
9.2 基尼指數(shù)
一般來說，我們在使用中，用某個(gè)特征劃分樣本集合只有兩個(gè)集合（CART）：
????1.等于給定的特征值的樣本集合D1
????2.不等于給定的特征值的樣本集合D2
這樣就可以對擁有多個(gè)取值的特征的二值處理。對于上述的每一種劃分，都可以計(jì)算出基于劃分特征=某個(gè)特征值將樣本集合D劃分為兩個(gè)子集的純度。因而對于一個(gè)具有多個(gè)取值（超過2個(gè)）的特征，需要計(jì)算以每一個(gè)取值作為劃分點(diǎn)，對樣本D劃分之后子集的純度Gini(D,Ai)，(其中Ai表示特征A的可能取值)。然后從所有的可能劃分的Gini(D,Ai)中找出Gini指數(shù)最小的劃分，這個(gè)劃分的劃分點(diǎn)，便是使用特征A對樣本集合D進(jìn)行劃分的最佳劃分點(diǎn)。
0x10 特征選擇
特征選擇也就是選擇最優(yōu)劃分屬性，從當(dāng)前數(shù)據(jù)的特征中選擇一個(gè)特征作為當(dāng)前節(jié)點(diǎn)的劃分標(biāo)準(zhǔn)。代碼參考（3.決策樹3: 特征選擇之尋找最優(yōu)劃分?）
10.1 信息增益最優(yōu)劃分
10.2 信息增益率最優(yōu)劃分
10.3 基尼系數(shù)最優(yōu)劃分
0x11 ID3算法
ID3算法是一種分類預(yù)測算法，算法以信息論中的“信息增益”為基礎(chǔ)。核心是通過計(jì)算每個(gè)特征的信息增益，每次劃分選取信息增益最高的屬性為劃分標(biāo)準(zhǔn)，遞歸地構(gòu)建決策樹。
11.1 構(gòu)造
ID3相當(dāng)于用極大似然法進(jìn)行概率模型的選擇。具體方法是：
? ? 1.從根結(jié)點(diǎn)(root node)開始，對結(jié)點(diǎn)計(jì)算所有可能的特征的信息增益，選擇信息增益最大的特征作為結(jié)點(diǎn)的特征。
? ? 2.由該特征的不同取值建立子節(jié)點(diǎn)，再對子結(jié)點(diǎn)遞歸地調(diào)用以上方法，構(gòu)建決策樹；直到所有特征的信息增益均很小或沒有特征可以選擇為止；
? ? 3.最后得到一個(gè)決策樹。
從ID3的構(gòu)建樹過程而言，它可以看成使用貪心算法得到近似最優(yōu)的一顆決策樹，它無法保證是最優(yōu)的。
11.2 優(yōu)缺點(diǎn)
相對于其他數(shù)據(jù)挖掘算法，決策樹在以下幾個(gè)方面擁有優(yōu)勢：
? ? 1.決策樹易于理解和實(shí)現(xiàn). 人們在通過解釋后都有能力去理解決策樹所表達(dá)的意義。
? ? 2.對于決策樹，數(shù)據(jù)的準(zhǔn)備往往是簡單或者是不必要的 . 其他的技術(shù)往往要求先把數(shù)據(jù)一般化，比如去掉多余的或者空白的屬性。
? ? 3.能夠同時(shí)處理數(shù)據(jù)型和常規(guī)型屬性。其他的技術(shù)往往要求數(shù)據(jù)屬性的單一。
? ? 4.是一個(gè)白盒模型如果給定一個(gè)觀察的模型，那么根據(jù)所產(chǎn)生的決策樹很容易推出相應(yīng)的邏輯表達(dá)式。
? ? 5.易于通過靜態(tài)測試來對模型進(jìn)行評測。表示有可能測量該模型的可信度。
? ? 6.在相對短的時(shí)間內(nèi)能夠?qū)Υ笮蛿?shù)據(jù)源做出可行且效果良好的結(jié)果
ID3算法可用于劃分標(biāo)準(zhǔn)稱型數(shù)據(jù)，但存在一些問題：
? ? 1.沒有剪枝過程，為了去除過渡數(shù)據(jù)匹配的問題，可通過裁剪合并相鄰的無法產(chǎn)生大量信息增益的葉子節(jié)點(diǎn);
? ? 2.信息增益的方法偏向選擇具有大量值的屬性，也就是說某個(gè)屬性特征索取的不同值越多，那么越有可能作為分裂屬性，這樣是不合理的；
? ? 3.只可以處理離散分布的數(shù)據(jù)特征
? ? 4.ID3算法只考慮了樹的生成，即盡可能的是模型擬合當(dāng)前訓(xùn)練數(shù)據(jù)集，所以該算法生成的樹容易過擬合。
0x12?C4.5算法
C4.5算法是數(shù)據(jù)挖掘十大算法之一，它是對ID3算法的改進(jìn)，相對于ID3算法主要有以下幾個(gè)改進(jìn)
????1.用信息增益比來選擇屬性
? ? 2.在決策樹的構(gòu)造過程中對樹進(jìn)行剪枝
? ? 3.對非離散數(shù)據(jù)也能處理
? ? 4.能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理
C4.5算法與ID3算法過程相似，僅在特征選擇時(shí)，使用信息增益比作為特征選擇準(zhǔn)則。
0x13?小結(jié)
一、ID3：
熵表示的是數(shù)據(jù)中包含的信息量大小。熵越小，數(shù)據(jù)的純度越高，也就是說數(shù)據(jù)越趨于一致，這是我們希望的劃分之后每個(gè)子節(jié)點(diǎn)的樣子。
信息增益 = 劃分前熵 - 劃分后熵。信息增益越大，則意味著使用屬性 a 來進(jìn)行劃分所獲得的 “純度提升” 越大 。也就是說，用屬性 a 來劃分訓(xùn)練集，得到的結(jié)果中純度比較高。
ID3 僅僅適用于二分類問題。ID3 僅僅能夠處理離散屬性。
二、C4.5：
C4.5 克服了 ID3 僅僅能夠處理離散屬性的問題，以及信息增益偏向選擇取值較多特征的問題，使用信息增益比來選擇特征。信息增益比 = 信息增益 / 劃分前熵 選擇信息增益比最大的作為最優(yōu)特征。
C4.5 處理連續(xù)特征是先將特征取值排序，以連續(xù)兩個(gè)值中間值作為劃分標(biāo)準(zhǔn)。嘗試每一種劃分，并計(jì)算修正后的信息增益，選擇信息增益最大的分裂點(diǎn)作為該屬性的分裂點(diǎn)。
三、信息增益 vs 信息增益比：
之所以引入了信息增益比，是由于信息增益的一個(gè)缺點(diǎn)。那就是：信息增益總是偏向于選擇取值較多的屬性。信息增益比在此基礎(chǔ)上增加了一個(gè)罰項(xiàng)，解決了這個(gè)問題。
0x14 剪枝
當(dāng)訓(xùn)練數(shù)據(jù)量大、特征數(shù)量較多時(shí)構(gòu)建的決策樹可能很龐大，這樣的決策樹用來分類是否好？答案是否定的。
決策樹是依據(jù)訓(xùn)練集進(jìn)行構(gòu)建的，為了盡可能正確地分類訓(xùn)練樣本，結(jié)點(diǎn)劃分過程將不斷重復(fù)，有時(shí)會造成決策樹分支過多。這就可能會把訓(xùn)練樣本學(xué)的“太好”了，以至于把訓(xùn)練集自身的一些特點(diǎn)當(dāng)作所有數(shù)據(jù)都具有的一般性質(zhì)而導(dǎo)致過擬合。因此可主動去掉一些分支來降低過擬合風(fēng)險(xiǎn)。
決策樹非常容易產(chǎn)生過擬合，實(shí)際所有非參數(shù)學(xué)習(xí)算法，都非常容易產(chǎn)生過擬合。因此，對于決策樹的構(gòu)建還需要最后一步，即決策樹的修剪。兩個(gè)目的：降低復(fù)雜度，解決過擬合。
決策樹的修剪，也就是剪枝操作，主要分為兩種：
預(yù)剪枝（Pre-Pruning）
后剪枝（Post-Pruning）
14.1?預(yù)剪枝
預(yù)剪枝是指在決策樹生成過程中，對每個(gè)節(jié)點(diǎn)在劃分前先進(jìn)行估計(jì)，若當(dāng)前節(jié)點(diǎn)的劃分不能帶來決策樹泛化性能的提升，則停止劃分并將當(dāng)前節(jié)點(diǎn)標(biāo)記為葉節(jié)點(diǎn)。
那么所謂的“決策樹泛化性能”如何來判定呢？這就可以使用性能評估中的留出法，即預(yù)留一部分?jǐn)?shù)據(jù)用作“驗(yàn)證集”以進(jìn)行性能評估。
預(yù)剪枝使得決策樹的很多分支都沒有“展開”，這不僅降低了過擬合的風(fēng)險(xiǎn)，還顯著減少了決策樹的訓(xùn)練時(shí)間開銷和測試時(shí)間開銷。但是，另一方面，因?yàn)轭A(yù)剪枝是基于“貪心”的，所以，雖然當(dāng)前劃分不能提升泛化性能，但是基于該劃分的后續(xù)劃分卻有可能導(dǎo)致性能提升，因此預(yù)剪枝決策樹有可能帶來欠擬合的風(fēng)險(xiǎn)。
14.2 后剪枝
后剪枝是先從訓(xùn)練集生成一顆完整的決策樹，然后自底向上地對非葉節(jié)點(diǎn)進(jìn)行考察，若將該節(jié)點(diǎn)對應(yīng)的子樹完全替換為葉節(jié)點(diǎn)能帶來決策樹繁花性的提升，則將該子樹替換為葉節(jié)點(diǎn)。
14.3 總結(jié)
對比預(yù)剪枝和后剪枝，能夠發(fā)現(xiàn)，后剪枝決策樹通常比預(yù)剪枝決策樹保留了更多的分支，一般情形下，后剪枝決策樹的欠擬合風(fēng)險(xiǎn)小，泛華性能往往也要優(yōu)于預(yù)剪枝決策樹。但后剪枝過程是在構(gòu)建完全決策樹之后進(jìn)行的，并且要自底向上的對樹中的所有非葉結(jié)點(diǎn)進(jìn)行逐一考察，因此其訓(xùn)練時(shí)間開銷要比未剪枝決策樹和預(yù)剪枝決策樹都大得多。
（代碼參考：5.決策樹5：剪枝與sklearn中的決策樹? 0x04 sklearn中的剪枝處理）
0x15 CART算法
15.1 CART算法
CART算法：Classification And Regression Tree。顧名思義，CART算法既可以用于創(chuàng)建分類樹（Classification Tree），也可以用于創(chuàng)建回歸樹（Regression Tree）、模型樹（Model Tree），兩者在建樹的過程稍有差異。既可以解決分類問題，也可以解決回歸問題。根據(jù)某一個(gè)維度d和某一個(gè)閾值v進(jìn)行二分，得到的決策樹是二叉樹。
ID3中使用了信息增益選擇特征，增益大優(yōu)先選擇。C4.5中，采用信息增益比選擇特征，減少因特征值多導(dǎo)致信息增益大的問題。CART分類樹算法使用基尼系數(shù)來代替信息增益比，基尼系數(shù)代表了模型的不純度，基尼系數(shù)越小，不純度越低，特征越好。這和信息增益（比）相反。
15.2 CART作為分類樹
CART作為分類樹時(shí)，特征屬性可以是連續(xù)類型也可以是離散類型，但觀察屬性(即標(biāo)簽屬性或者分類屬性)必須是離散類型。
15.2.1 對離散特征和連續(xù)特征的處理
15.2.1.1 離散特征
CART分類樹算法對離散值的處理，采用的思路：不停的二分離散特征。
在ID3、C4.5，特征A被選取建立決策樹節(jié)點(diǎn)，如果它有3個(gè)類別A1,A2,A3，我們會在決策樹上建立一個(gè)三叉點(diǎn)，這樣決策樹是多叉樹。
CART采用的是不停的二分。會考慮把特征A分成{A1}和{A2,A3}、{A2}和{A1,A3}、{A3}和{A1,A2}三種情況，找到基尼系數(shù)最小的組合。
比如{A2}和{A1,A3}，然后建立二叉樹節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)是A2對應(yīng)的樣本，另一個(gè)節(jié)點(diǎn)是{A1,A3}對應(yīng)的樣本。**由于這次沒有把特征A的取值完全分開，各分支下的子數(shù)據(jù)集必須依舊包含該特征，該連續(xù)特征在接下來的樹分支過程中可能依舊起著決定性作用。后面還有機(jī)會對子節(jié)點(diǎn)繼續(xù)選擇特征A劃分A1和A3。這和ID3、C4.5不同，在ID3或C4.5的一顆子樹中，離散特征只會參與一次節(jié)點(diǎn)的建立。
15.2.1.2 連續(xù)特征
CART分類樹算法對連續(xù)值的處理，思想和C4.5相同，都是將連續(xù)的特征離散化。唯一區(qū)別在選擇劃分點(diǎn)時(shí)，C4.5是信息增益比，CART是基尼系數(shù)。
具體思路：m個(gè)樣本的連續(xù)特征A有m個(gè)，從小到大排列a1,a2,......,am，則CART取相鄰兩樣本值的平均數(shù)做劃分點(diǎn)，一共取m-1個(gè)，其中第i個(gè)劃分點(diǎn)Ti表示為：Ti=(ai+ai+1)/2。分別計(jì)算以這m-1個(gè)點(diǎn)作為二元分類點(diǎn)時(shí)的基尼系數(shù)。選擇基尼系數(shù)最小的點(diǎn)為該連續(xù)特征的二元離散分類點(diǎn)。比如取到的基尼系數(shù)最小的點(diǎn)為at，則小于at的值為類別1，大于at的值為類別2，這樣就做到了連續(xù)特征的離散化。另外，對于連續(xù)屬性先進(jìn)行排序（升序），只有在決策屬性（即分類發(fā)生了變化）發(fā)生改變的地方才需要切開，這可以顯著減少運(yùn)算量。
注意的是，與ID3、C4.5處理離散屬性不同的是，如果當(dāng)前節(jié)點(diǎn)為連續(xù)屬性，則該屬性在后面還可以參與子節(jié)點(diǎn)的產(chǎn)生選擇過程。
15.3 CART作為回歸樹
15.3.1 回歸問題思路
當(dāng)數(shù)據(jù)擁有眾多特征并且特征之間關(guān)系十分復(fù)雜時(shí)，構(gòu)建全局模型的想法就顯得太難了，也略顯笨拙。而且，實(shí)際生活中很多問題都是非線性的，不可能使用全局線性模型來擬合任何數(shù)據(jù)。一種可行的方法是將數(shù)據(jù)集切分成很多份易建模的數(shù)據(jù)，然后利用線性回歸技術(shù)來建模。如果首次切分后仍然難以擬合線性模型就繼續(xù)切分。在這種切分方式下，樹結(jié)構(gòu)和回歸法就相當(dāng)有用。
回歸樹的目標(biāo)是連續(xù)數(shù)據(jù)，樹被用來預(yù)測目標(biāo)變量的值是多少。
CART回歸樹和CART分類樹的建立類似，區(qū)別在于樣本的輸出，如果樣本輸出是離散值，這是分類樹；樣本輸出是連續(xù)值，這是回歸樹。分類樹的輸出是樣本的類別，回歸樹的輸出是一個(gè)實(shí)數(shù)。
并且分類樹采用基尼系數(shù)的大小度量特征各個(gè)劃分點(diǎn)的優(yōu)劣。而回歸樹采用最小化均方差和進(jìn)行最優(yōu)劃分特征的選擇，對于劃分特征A，劃分點(diǎn)s兩邊的數(shù)據(jù)集D1和D2，求出使D1和D2各自集合的均方差最小，同時(shí)D1和D2的均方差之和最小，對應(yīng)的特征和特征值劃分點(diǎn)。
其中：C1為D1數(shù)據(jù)集的樣本輸出均值，C2為D2數(shù)據(jù)集的樣本輸出均值。
對于決策樹建立后做預(yù)測的方式，CART分類樹采用該葉子節(jié)點(diǎn)里概率最大的類別作為當(dāng)前節(jié)點(diǎn)的預(yù)測類別。回歸樹輸出不是類別，采用葉子節(jié)點(diǎn)的均值或者中位數(shù)來預(yù)測輸出結(jié)果。
15.3.2 CART剪枝
由于決策樹算法很容易對訓(xùn)練集過擬合，而導(dǎo)致泛化能力差，為了解決這個(gè)問題，我們需要對CART樹進(jìn)行剪枝，來增加決策樹的泛化能力。CART采用的辦法是后剪枝法。
CART樹的剪枝算法可以概括為兩步：
? ? 1.從原始決策樹生成各種剪枝效果的決策樹
? ? 2.用交叉驗(yàn)證來檢驗(yàn)剪枝后的預(yù)測能力，選擇泛化預(yù)測能力最好的剪枝后的樹作為最終的CART樹。
可以采用交叉驗(yàn)證策略，上面我們計(jì)算出了每個(gè)子樹是否剪枝的閾值α，如果我們把所有的節(jié)點(diǎn)是否剪枝的值α都計(jì)算出來，然后分別針對不同的α所對應(yīng)的剪枝后的最優(yōu)子樹做交叉驗(yàn)證。這樣就可以選擇一個(gè)最好的α，有了這個(gè)α，我們就可以用對應(yīng)的最優(yōu)子樹作為最終結(jié)果。
參考閱讀：
7.
