1.算法
從這部分開始承粤，我們來講解機器學習中最實用暴区，效率高且效果好的決策器集成類的算法。
RF辛臊、GBR仙粱、Adboost是三個最經典的集成類算法，所謂集成類算法彻舰，就是集成了一些弱學習器的結果伐割，綜合輸出一個更為可靠的結果。舉個例子來說，如果有一位不知道從哪里來的天氣學家突然告訴你，馬上就要洪水海嘯沮榜，世界末日了，你在相信這位科學家的言論之前硬霍，肯定會先考量一下他是個瘋子的可能性有多大。但假如這時候世界各國都出現(xiàn)了很多的天氣學家笼裳，每一個天氣學家的語言须尚、學術背景、研究方法都不同侍咱，但這些天氣學家都告訴你耐床，馬上就要洪水海嘯，地震龍卷風楔脯，世界末日了撩轰，這時，我們顯然不得不考慮這個言論的可能性了昧廷。
當然在我們學習如何綜合判斷不同天氣學家的意見之前堪嫂，我們首先需要培養(yǎng)出不同的天氣學家出來，也就是我們這一節(jié)介紹的集成算法中的三種常見弱學習器（決策樹）木柬。
1.1 信息論基礎知識
1.信息量
信息量是衡量系統(tǒng)中某種結果發(fā)生時所攜帶的信息大小皆串，可以理解為某個事件發(fā)生的概率大小，當某件事發(fā)生的概率越小但發(fā)生了之后眉枕，所攜帶的信息量越大恶复，其實這與我們的直觀感受是相符合的，我們會覺得火箭發(fā)射失敗的消息所包含的信息量很大速挑，因為其發(fā)生概率很邪怠；
信息量公式：
1姥宝、p（x）是事件x發(fā)生的概率
2翅萤、用對數是為了計算方便！
3腊满、為何前面有負號套么？?因為信息量與概率成反比培己，倒數的對數，負號可以提前胚泌！
4省咨、底數為何是2？是其他的也行诸迟！
2.信息熵
信息熵與信息量茸炒，是系統(tǒng)與個體的關系愕乎。信息熵是研究系統(tǒng)各種可能結果及其每種結果發(fā)生的概率與整個系統(tǒng)的混亂度的關系阵苇。當一個系統(tǒng)的各種可能性相等的時候，該系統(tǒng)最為混亂（無序）感论，其信息熵也是最大的绅项。反之，如果一個系統(tǒng)中某個結果概率很大比肄，其他結果概率很小快耿，則該系統(tǒng)的信息熵較小，該系統(tǒng)較為明確（有序）芳绩！
例如：假如天氣預報告訴我們：明天我市天氣可能是晴天掀亥，也有可能是多云，還有可能是小雨或者大雨妥色，四種可能概率皆為25%搪花，這個系統(tǒng)十分混亂，顯然我們沒有得出什么有效信息嘹害；但如果天氣預報這樣告訴我們：明天我市天氣為多云撮竿，概率為95%，這個系統(tǒng)顯然有序得多笔呀，我們知道明天需要帶傘出門幢踏。
問題來了，上面講的系統(tǒng)有序程度许师，是一種主觀的感覺房蝉。能不能用數學的方法來量化一個系統(tǒng)的有序程度呢？
前面提到了信息量的概念微渠，能否用一個系統(tǒng)的所有可能結果發(fā)生時所攜帶的信息量的總和來衡量該系統(tǒng)的混亂程度呢惨驶？
還是以天氣預報為例，該系統(tǒng)有四種結果：晴天敛助，多云粗卜，小雨和大雨，若按照信息量之和來衡量混亂度纳击，那么其混亂度的值為各個結果發(fā)生概率之倒數续扔，再取對數并求和攻臀。
這種方式可行嗎？不可行纱昧！因為概率極小的結果會對最終的結果影響很大刨啸，但是現(xiàn)實中，極小的結果對混亂度并無多大影響识脆。
明天95%的概率是多云设联。如果我們再加上一個結果，下冰雹Ｗ莆妗＠肜！其概率為萬分之一悉稠。對這個系統(tǒng)的混亂度會有什么影響呢宫蛆？
現(xiàn)實中增加了這個可能并沒有影響我們對明天的判斷。然而的猛，如果用信息量直接求和來衡量混亂度的話耀盗，下冰雹這個結果增加后，系統(tǒng)的混亂度大大增加了卦尊，因為其發(fā)生的概率太小叛拷，導致整個系統(tǒng)的信息量之和明顯增大。
所以岂却，這種方法不夠完善忿薇，我們需要改進一下：
用每個結果的信息量與其發(fā)生概率加權，再求和淌友，最終得到的值便可以有效地衡量整個系統(tǒng)的混亂程度煌恢，值越大，越為混亂震庭！
我們用這種方法來算一下天氣預報系統(tǒng)的混亂度：
混亂度?=?-0.95*log(0.95) -? 0.02*log(0.02) -? 0.01*log(0.01) -? 0.01*log(0.01)?
算出來的值就可以科學地衡量一個系統(tǒng)的混亂度了瑰抵。各位觀眾可以做一個實驗，在各種結果概率相等時器联，該值最大二汛；而若是存在某個結果概率接近1的時候，該值趨向最胁ν亍肴颊！
講了那么多，我們還是沒有提到信息學知識與決策樹之間的聯(lián)系渣磷。不要著急婿着，我們先來看這樣一張圖：
這是一位姑娘在擇偶時的考慮過程，事實上這個過程就是一棵決策樹，黃色部分是輸入的特征竟宋。假設我們已經知道這位姑娘對一些男生的選擇情況提完，也就是我們已經有了一些訓練樣本，我們需要根據不同的特征劃分這位姑娘選擇某位輸入對象的可能性丘侠，而劃分的依據就是我們前面所介紹的信息學知識徒欣。
假設在數據D中有k個類別，其中第i個類別數據在總數據中占有率為pi蜗字，則熵的計算公式為：
3. 信息增益
當我們使用某一特征A對數據分類后打肝，系統(tǒng)的混亂度會減小（因為數據數據有所劃分）挪捕。此時的熵也會減小粗梭，假設特征A有m個類別，其計算公式為：
那么分類前后熵減小的差值就是信息增益：
我們一一計算所有變量的信息增益担神，選擇信息增益最大的那個變量作為此分類節(jié)點楼吃，由此便引出了我們介紹的第一個決策樹：ID3
1.2 ID3
我們現(xiàn)在已經了解了不同特征分類節(jié)點的劃分依據始花，那么如何劃分的具體過程還是不明朗妄讯，接下來我們使用一個具體事例來介紹，只要拿出紙筆跟著算一遍即可酷宵，這個過程不涉及任何復雜的公式亥贸。
我們設定一組貸款數據如下：
我們將通過年齡、是否有工作浇垦、是否有房子和信貸情況四個自變量來區(qū)分貸款的審批結果炕置。
第一層
總體信息熵：
計算年齡A1的信息熵：
則A1的信息增益為：
按照此方法，
由此可見男韧，我們將使用變量A3：是否有房子來作為第一分類特征朴摊。
第二層
A3 = “是"時數據如下：
發(fā)現(xiàn)他們的貸款審批結果都是"是”，其熵等于0此虑，可以作為葉節(jié)點甚纲。
A3 = "否"時數據如下：
此時的總體信息熵：
至此不需要在計算Gain(A4)了，因為A2已經將數據完全劃分開了朦前。
在本數據集中介杆，A1和A4對于數據的劃分沒有作用。
所得樹圖：
在樹圖中韭寸，（1/2/8/9/10/14）（3/4/13）（5/6/7/11/12/15）是三個葉節(jié)點春哨，代表了三個分類好的子集；其他非葉節(jié)點表示的是邏輯判斷恩伺。
一般而言赴背，我們都需要對樹進行剪枝。因為我們劃分枝葉的根據是熵增，只要有熵增就需要分枝凰荚，這樣會很有可能造成過擬合的情況耸三。我們將在后續(xù)介紹剪枝操作。
ID3的缺點
ID3算法的缺點在于：用信息增益選擇屬性時偏向于選擇分枝比較多的屬性值浇揩，即取值多的屬性仪壮。
所以，我們使用信息增益比來代替信息增益胳徽，以削弱這種情況积锅。此算法也即是C4.5算法。
1.3 C4.5
在上一篇介紹ID3算法文章中养盗，我們指出ID3算法采用信息增益作為標準缚陷，缺點在于會偏向分類更多的自變量，并且不能處理連續(xù)值往核。
在本文中箫爷，我們將介紹C4.5算法，采用信息增益比代替信息增益聂儒，從而減小某一自變量分類個數的影響虎锚。
我們假設使用的數據集為D，待計算的自變量為A衩婚，g(D,A)則信息增益比為：
其中窜护，
與ID3比較，我們只是更換了劃分標準非春，計算方法沒什么變化柱徙，我們同樣拿一個實例來介紹，請拿出紙筆仔細算一遍：
經計算奇昙，（信息增益的詳細計算過程在上一節(jié)中）护侮；
下面計算自變量A1的信息增益比，
同理可得
一般而言储耐，我們還是要選擇一個信息增益比最大的變量羊初。但是，采用信息增益比也有缺點弧岳，即它會偏向于分類較少的變量凳忙。
我們總結一下：
ID3算法使用的是信息增益，它偏向于分類較多的變量禽炬；
C4.5算法使用的是信息增益比涧卵，它偏向于分類較少的變量。
為了克服這些問題腹尖，我們采取如下方式：首先計算信息增益和信息增益比柳恐，然后選取信息增益在平均值以上的那些變量，最后在這些變量中選擇信息增益比最大的變量。
例如：在上面的實例中乐设，我們發(fā)現(xiàn)變量A2,A3,A4的信息增益在平均值以上讼庇。然后，我們就在A2,A3,A4三個變量中選擇信息增益比最大的變量近尚。
1.4 CART
正如之前所說蠕啄，ID3/C4.5/CART算法的區(qū)別在于選擇特征作為判斷節(jié)點時的數據純度函數（標準）不同。ID3算法使用的是信息增益戈锻，C4.5算法使用的是信息增益比歼跟，CART算法使用的是基尼系數(GINI)。
1. 算法思想
CART算法是一種二分遞歸分割方法格遭，把當前樣本劃分為兩個子樣本哈街，不斷遞歸分割使得生成的每個非葉子結點都有兩個分支。所以拒迅，CART算法生成的決策樹是一個二叉樹骚秦。由于二叉樹的每個節(jié)點的選擇都只有“是”和“否”兩種，所以即使一個節(jié)點下需要多分類璧微，也是把數據分成兩部分作箍。
假設數據有共n個自變量（維度），y是其標簽往毡。算法步驟為：
那么我們按照怎樣的順序選擇變量呢蒙揣？CART算法使用的標準是GINI系數靶溜。
2. GINI系數
總體內包含的類別越雜亂开瞭，GINI指數就越大。這個概念跟熵的概念很相似罩息。
假設pi為某一類別所占總體的概率嗤详，共有n類，則GINI系數定義：
當我們按照變量A對數據集D進行分類時瓷炮，假設變量A將數據D分成了m類葱色，則劃分后的GINI系數為：
此時，GINI系數的增加值為：
我們依次計算每一個變量的基尼系數增加值Δ娘香，并選取最大的那個變量劃分數據集苍狰。
3. 計算實例
整個數據的GINI系數為：
當按照?A3是否有房子（二分類）?來劃分，GINI系數增加值的計算過程：
那么：
當按照 A1年齡（三分類） 來劃分烘绽，GINI系數增加值的計算過程：
由于CART算法本質上是一個二叉樹淋昭，所以我們要將數據分成一下三種情況：
{青年} ，{中年安接，老年}翔忽；
{中年}， {青年，老年}歇式；
{老年}驶悟， {青年，中年}
這里材失，我們以{青年} 痕鳍，{中年，老年}為例計算GINI系數增加值
那么
之后在依次計算剩下兩種分組的GINI系數增加值龙巨。
綜上： 雖然在原始數據中只有4個分類额获，但是在計算GINI系數增加值時，需要計算（3+1+1+3）中分組可能恭应。（即A1和A4有三個分類抄邀，即有三種劃分情況；A2和A3只有兩個分類昼榛，即有一種劃分情況）境肾。
按照這種計算方式依次計算，每次都選取GINI系數增加最大的劃分可能胆屿，直至數據沒有在劃分的可能或者數據已經完全分開奥喻。
值得注意的是，當數據是連續(xù)型時非迹，我們將數據從小到大排列环鲤，去相鄰兩個取值的均值作為劃分點。例如憎兽，數據為(60,70,80,90)冷离，我們分別取65，75纯命，85作為劃分點西剥，并且計算劃分之后的GINI增加值。
4. 缺失值處理
上文說到亿汞，模型對于缺失值的處理會分為兩個子問題：
如何在特征值缺失的情況下進行劃分特征的選擇瞭空？
選定該劃分特征，模型對于缺失該特征值的樣本該進行怎樣處理疗我？
對于問題 1咆畏，CART 一開始嚴格要求分裂特征評估時只能使用在該特征上沒有缺失值的那部分數據，在后續(xù)版本中吴裤，CART 算法使用了一種懲罰機制來抑制提升值旧找，從而反映出缺失值的影響（例如，如果一個特征在節(jié)點的 20% 的記錄是缺失的嚼摩，那么這個特征就會減少 20% 或者其他數值）钦讳。
對于問題 2矿瘦，CART 算法的機制是為樹的每個節(jié)點都找到代理分裂器，無論在訓練數據上得到的樹是否有缺失值都會這樣做愿卒。在代理分裂器中缚去，特征的分值必須超過默認規(guī)則的性能才有資格作為代理（即代理就是代替缺失值特征作為劃分特征的特征），當 CART 樹中遇到缺失值時琼开，這個實例劃分到左邊還是右邊是決定于其排名最高的代理易结，如果這個代理的值也缺失了，那么就使用排名第二的代理柜候，以此類推搞动，如果所有代理值都缺失，那么默認規(guī)則就是把樣本劃分到較大的那個子節(jié)點渣刷。代理分裂器可以確保無缺失訓練數據上得到的樹可以用來處理包含確實值的新數據鹦肿。
1.5 剪枝算法
當我們輸入的原始數據有較多的變量時，通過決策樹算法生成的決策樹可能會非常的龐大辅柴。這樣的一顆決策樹在訓練集上有很好的表現(xiàn)箩溃，但是在測試集上的表現(xiàn)往往不甚理想，這樣的問題也被叫做過擬合問題碌嘀。面對這樣的問題涣旨，我們一般所采用的方法是對決策樹進行剪枝操作。
決策樹的剪枝
顧名思義股冗，樹的剪枝就是剪掉樹的一些枝葉霹陡，考慮大決策樹的枝代表著邏輯判斷，也代表著分類后的子集止状。決策樹的剪枝就是刪掉一些不必要的邏輯判斷烹棉，并且將子集合并。這樣確實會造成在訓練集上子集不純的現(xiàn)象导俘，但是因為我們最終目標是模型在測試集上的效果峦耘，所以犧牲在訓練集上的效果換取解決測試集的過擬合問題這樣的做法也是值得的。決策樹剪枝可以分為兩類旅薄，一類是預剪枝，一類是后剪枝泣崩。
剪枝算法不詳細介紹原理少梁，感興趣的可以自行查找資料。
預剪枝
預剪枝就是在生成決策樹的同時進行剪枝矫付。正常決策樹的生成是只要有信息增益就要進行分支凯沪。預剪枝就是設定一個閾值，只有在信息增益大于這個閾值的時候（也即是在分類后的信息混亂程度減小程度大于一定標準的時候）才進行分類买优。如果在信息增益過小的情況下妨马，即使存在信息增益的現(xiàn)象挺举，也不會對其進行分支。預剪枝的思想比較簡單烘跺，但在實際應用中湘纵，預剪枝的表現(xiàn)并不是很好。所以滤淳，目前我們基本都是使用后剪枝方法梧喷。
后剪枝
后剪枝就是在決策樹構造完成后進行剪枝汹碱。剪枝的過程是對擁有相同父節(jié)點的一組節(jié)點進行檢查配猫，如果將其合并蝉稳，熵增小于某一閾值饱狂，那么這一組節(jié)點可以合并一個節(jié)點屯阀。如果將其合并后熵增大于這個閾值序宦，那么說明將其分枝是合理的婶熬。后剪枝就是刪除一些子樹两疚，然后用其葉節(jié)點代替派歌。這個葉節(jié)點代表的子集不一定都是“純”的笔喉。那么，這個葉子節(jié)點所標識的類別通過大多數原則確定硝皂。大多數原則就是指這個葉節(jié)點所代表的子集中大多數的類別來表示這個葉節(jié)點常挚。
常見的后剪枝算法
錯誤率降低剪枝法
錯誤率降低剪枝法(Reduced-Error Pruning)簡稱REP方法。
悲觀剪枝法
悲觀剪枝法(Pessimistic Error Pruning)簡稱PEP方法稽物。
代價復雜度剪枝法
代價復雜度算法(Cost-Complexity Pruning)簡稱為CCP算法奄毡。
2.比較
ID3的缺點：
ID3 沒有剪枝策略，容易過擬合贝或；
信息增益準則對可取值數目較多的特征有所偏好吼过，類似“編號”的特征其信息增益接近于 1；
只能用于處理離散分布的特征咪奖；
沒有考慮缺失值盗忱。
C4.5 相對于 ID3 的缺點對應有以下改進方式：
引入悲觀剪枝策略進行后剪枝；
引入信息增益率作為劃分標準羊赵；
將連續(xù)特征離散化趟佃，假設 n 個樣本的連續(xù)特征 A 有 m 個取值，C4.5 將其排序并取相鄰兩樣本值的平均數共 m-1 個劃分點昧捷，分別計算以該劃分點作為二元分類點時的信息增益闲昭，并選擇信息增益最大的點作為該連續(xù)特征的二元離散分類點；
對于缺失值的處理可以分為兩個子問題：
問題一：在特征值缺失的情況下進行劃分特征的選擇靡挥？（即如何計算特征的信息增益率）
問題二：選定該劃分特征序矩，對于缺失該特征值的樣本如何處理？（即到底把這個樣本劃分到哪個結點里）
針對問題一跋破，C4.5 的做法是：對于具有缺失值特征簸淀，用沒有缺失的樣本子集所占比重來折算瓶蝴；
針對問題二，C4.5 的做法是：將樣本同時劃分到所有子節(jié)點租幕，不過要調整樣本的權重值舷手，其實也就是以不同概率劃分到不同節(jié)點中。
C4.5 的缺點
剪枝策略可以再優(yōu)化令蛉；
C4.5 用的是多叉樹聚霜，用二叉樹效率更高；
C4.5 只能用于分類珠叔；
C4.5 使用的熵模型擁有大量耗時的對數運算蝎宇，連續(xù)值還有排序運算；
C4.5 在構造樹的過程中祷安，對數值屬性值需要按照其大小進行排序姥芥，從中選擇一個分割點，所以只適合于能夠駐留于內存的數據集汇鞭，當訓練集大得無法在內存容納時凉唐，程序無法運行。
CART 在 C4.5 的基礎上進行了很多提升：
C4.5 為多叉樹霍骄，運算速度慢台囱，CART 為二叉樹，運算速度快读整；
C4.5 只能分類簿训，CART 既可以分類也可以回歸；
CART 使用 Gini 系數作為變量的不純度量米间，減少了大量的對數運算强品；
CART 采用代理測試來估計缺失值，而 C4.5 以不同概率劃分到不同節(jié)點中屈糊；
CART 采用“基于代價復雜度剪枝”方法進行剪枝的榛，而 C4.5 采用悲觀剪枝方法。
最后通過總結的方式對比下 ID3逻锐、C4.5 和 CART 三者之間的差異夫晌。
除了之前列出來的劃分標準、剪枝策略谦去、連續(xù)值確實值處理方式等之外慷丽，我再介紹一些其他差異：
劃分標準的差異：ID3 使用信息增益偏向特征值多的特征，C4.5 使用信息增益率克服信息增益的缺點鳄哭，偏向于特征值小的特征，CART 使用基尼指數克服 C4.5 需要求 log 的巨大計算量纲熏，偏向于特征值較多的特征妆丘。
使用場景的差異：ID3 和 C4.5 都只能用于分類問題锄俄，CART 可以用于分類和回歸問題；ID3 和 C4.5 是多叉樹勺拣，速度較慢奶赠，CART 是二叉樹，計算速度很快药有；
樣本數據的差異：ID3 只能處理離散數據且缺失值敏感毅戈，C4.5 和 CART 可以處理連續(xù)性數據且有多種方式處理缺失值；從樣本量考慮的話愤惰，小樣本建議 C4.5苇经、大樣本建議 CART。C4.5 處理過程中需對數據集進行多次掃描排序宦言，處理成本耗時較高扇单，而 CART 本身是一種大樣本的統(tǒng)計方法，小樣本處理下泛化誤差較大 奠旺；
樣本特征的差異：ID3 和 C4.5 層級之間只使用一次特征蜘澜，CART 可多次重復使用特征；
剪枝策略的差異：ID3 沒有剪枝策略响疚，C4.5 是通過悲觀剪枝策略來修正樹的準確性鄙信，而 CART 是通過代價復雜度剪枝。
3.鏈接
隨機森林通俗演義
分類算法 -- 決策樹ID3算法
https://blog.csdn.net/weixin_43216017/article/details/87474045
分類算法 -- 決策樹C4.5算法
https://blog.csdn.net/weixin_43216017/article/details/87609780
分類算法 -- 決策數CART算法
https://blog.csdn.net/weixin_43216017/article/details/87617727
CART 分類與回歸樹
http://www.reibang.com/p/b90a9ce05b28
決策樹的剪枝：REP/PEP/CCP算法
https://blog.csdn.net/weixin_43216017/article/details/87534496
【機器學習】決策樹（上）——ID3忿晕、C4.5装诡、CART（非常詳細）
