決策樹和随機森林
首先，明白兩個概念：Bagging和Boosting。兩者都是将現有的分類或者回歸算法組合在一起，行程一個更強大的分類器的一種方法。
Bagging(bootstrap aggregating)：
算法過程：
1、從原始樣本集中抽取訓練集。每輪從原始樣本集中使用Bootstraping的方法抽取n個訓練樣本（在訓練集中，有些樣本可能被多次抽取到，而有些樣本可能一次都沒有被抽中）。共進行k輪抽取，得到k個訓練集。（k個訓練集之間是互相獨立的）。
2、每次使用一個訓練集得到一個模型，k個訓練集共得到k個模型。（注：這裡并沒有具體的分類算法或回歸方法，我們可以根據具體問題采用不同的分類或回歸方法，如決策樹、感覺器等）。
3、對分類問題：将上步得到的k個模型采用投票的方式得到分類結果；對回歸問題，計算上述模型的均值作為最後的結果。（所有模型的重要性相同）。
Boosting：把弱分類器組合成強分類器。
核心思想：
1、在每一輪如何改變訓練資料的權值或機率分布？
通過提高那些在前一輪被弱分類器分錯樣例的權值，減小前一輪分對樣例的權值，來使得分類器對誤分的資料有較好的效果。
2、通過什麼方式來組合弱分類器？
通過加法模型将弱分類器進行線性組合，比如AdaBoost通過權重多數表決的方式，即增大錯誤率小的分類器的權值，同時減小錯誤率較大的分類器的權值。
提升樹通過拟合殘差的方式逐漸減小殘差，将每一步生成的模型疊加得到最終模型。
兩者差別：
1、樣本選擇：
Bagging：訓練集是在原始集中有放回選取的，從原始集中選出的各輪訓練集之間是獨立的。
Boosting：每一輪的訓練集不變，隻是訓練集中每個樣例在分類器中的權重發生變化。而權值是根據上一輪的分類結果進行調整。
2、樣例權重：
Bagging：使用均勻取樣，每個樣例的權重相等。
Boosting：根據錯誤率不斷調整樣例的權值，錯誤率越大則權重越大。
3、預測函數：
Bagging：所有預測函數的權重相等。
Boosting：每個弱分類器都有相應的權重，對于分類誤差小的分類器會有更大的權重。
4、并行計算：
Bagging：各個預測函數可以并行生成。
Boosting：各個預測函數隻能順序生成，因為後一個模型參數需要前一輪模型的結果。
總結：
1）Bagging + 決策樹 = 随機森林
2）AdaBoost + 決策樹 = 提升樹
3）Gradient Boosting + 決策樹 = GBDT
通過上面分析，我們大體了解了決策樹和随機森林之間的關系。
我們先來分析下決策樹。
決策樹
分類樹：
核心思想：在資料集中找到最優的特征，從該特征的值中選出最優的取值，根據這個值将資料集分成兩個子集，遞歸操作，直到滿足條件為止。
1、如何找最優特征？
常用的方法是根據資訊增益或者資訊增益率來尋找最優特征。
資訊增益是什麼？
首先，考慮熵，熵越大資料的不确定性就越高。決策樹的目的就是利用資料的一些規則來盡可能的降低資料集的不确定性。給定一批資料集，我們可以很容易得到它的不确定性(熵)。
然後，我們要想辦法降低這個不确定性，我們需要挖掘資料集中有用的特征，在某個特征的限制下，我們又能得到資料集的不确定性（這個其實就是書上的條件熵）。我們用兩次的值作差，這個結果的含義很明了，給定了這個特征，讓我們資料集的不确定性降低了多少，當然降低的越多這個特征肯定就越好了。而我們講了這麼多就是要找到那一個讓資料集不确定性降低最多的特征。我們認為這個特征是目前特征中最好的一個。
2、有了最優特征，為什麼還需要最有特征的最優值？
一般的二分類問題确實沒必要找最優值，但對于多分類問題，需要最優值。
分析一下：假如我們的某個最優特征有三個類别：我們如果不找就直接分為三個子節點了。這樣會出現一個問題，就是我們的這個分類對特征值會變得敏感，為什麼這麼說，我們來講一個很簡答的例子：我們平時考試規定了60分及格，這個控制對于大多數學生很好把控，因為就一個條件，相當于一個二分類。但是如果我們把條件控制嚴格一些，比如超過60分，不超過80分為優秀學生。這個控制很多學霸就不好控制了，對于多分類問題也是這個道理，如果我們一下子從父節點直接分了多個子節點，那麼我們的資料肯定會對這個控制很敏感，敏感就會導緻出錯。出錯不是我們希望看到的，是以我們建議對多分類問題找最優候選值來轉化為二分類問題，同樣多個二分類問題其實也是一個多分類問題，隻是多了幾個遞歸過程而已。
3、遞歸如何停止？
當我們檢測到資料的分類效果已經夠好了，我們其實就可以停止了。當然我們常用的是控制葉節點，比如控制葉節點的樣本數目，比如當某個子節點内樣本數目小于某一個指定值，我們就決定不再分了。還有葉節點的純度，我們規定葉節點樣本必須屬于同一類才停止，這也是一個停止條件。還有最大樹的深度，比如我們規定樹的最大深度為某一個值，當樹深度到達這個值我們也要停止。還有比如：分裂次數，最大特征數等等。可以自己靈活選擇和處理。
分類和度量
使用ID3和C4.5的分類樹
ID3算法其實就是我們一般所了解的決策樹算法，其基本步驟就是我們上面所講的步驟，這個算法的核心思想就是用資訊增益來選擇最優分類特征，資訊增益的公式上面也給出了，這個公式我們仔細分析一下會發現一個問題：我們需要找到 g(D,A) 最大的特征，對于一個資料集entropy(D)是給定的，也就是說我們需要 entropy(D,A) 最小，意思就是我們所選的特征是那些分完後子節點的純度最高的特征，什麼樣的特征分完後子節點的特征純度比較高(熵比較小)，該特征的子類别很多，即可取值很多的這一類特征。總結一下就是資訊增益偏向于去那些擁有很多子類的特征。這也是這個算法的一大緻命缺點，任何帶有主觀偏向性的算法都不是一個好的算法，當然ID3算法的另一個缺點也顯而易見，它隻能處理那些分類的特征，對于連續值特征毫無辦法（其實我們可以人為的把連續屬性給離散化，但是人為必然會導緻可能不準确）。
C4.5是對ID3算法的一個改進，主要改進點就是解決了ID3的幾個缺點。首先C4.5算法用的是資訊增益率來代替ID3中的資訊增益。從表達式可以看出來，這麼做其實就是弱化那些偏向，讓選擇最優特征時更加公平。可以處理連續值。
1、首先對于連續值屬性的值進行排序(A1,A2......An);
2、我們可以在每兩個值之間取一個點，用這個點就可以把該組連續值分為兩部分，比如我們去一個點a1(A1<a1<A2),則小于a1的部分（A1）大于a1的部分（A2......An）。但是這個a1好嗎？不知道呀！那我們loop一下所有這樣的a(共有n-1個)，每一個ai我們可以算出分裂前後的資訊增益率，然後我們求一個max即可。很簡單吧！思路很好，但是呀很顯然有個問題，時間開銷有點大。
3、缺失值的處理，ID3不能直接處理(需要我們人工處理，比如單獨指派或賦一個平均值)，C4.5給出了一個很優雅的方式，為什麼說優雅，這樣講吧！我們每一個特征的取值都有若幹個，根據訓練集每個可能的取值都有一個機率，我們用這個機率來表示這個确實值得可能取值。這樣就顯得很合理了。
C4.5各方面完勝ID3，是以C4.5一出現就被廣泛應用，後面為了解決這個算法的時間開銷問題，推出了這個算法的改進版C5.0。國外有一篇比較C4.5和C5.0性能的blog寫的很好，可以搜一下。大體上C5.0的速度是C4.5的10倍以上。
使用基尼指數的回歸樹
CART樹既可以用于分類問題也可以用于回歸問題，用于分類問題的思想和我們上面介紹的ID3，C4.5其實是一樣的，唯一的不同就是CART樹用的是基尼指數來确定最優劃分點的。
基尼指數:
基尼指數的通俗解釋就是：表示一件事物的不确定性，基尼指數越大不确定性越大。我們要找基尼指數小的特征，這樣的特征對于劃分資料集的準确性會更高(不确定性低嘛)
類似的有一個條件基尼指數：
對于回歸問題：
首先簡單描述一下決策樹處理回歸問題的流程：
對于一個資料集我們可以将其分為m個子區間(R1,R2......Rm)對于每一區間我們可以産生一個對應的輸出cm。對于一個給定的回歸樹我們用平方誤差來表示每個單元的損失，那麼我們每個單元的最優輸出就是使該單元的損失函數最小。
對于回歸問題，我們面臨的問題也是如何确定劃分點(決策樹的核心)。這裡CART樹的處理方式和C4.5處理連續變量的方式有點類似。
這裡我們必須強調一下，我們在使用決策樹尋找每一步的最優切分點時，常用的是貪心算法，貪心算法有一個問題就是局部最優，而不是全局最優。是以我們一定要記住，決策樹在選擇特征及切分點時考慮的是一個局部最優問題。
剪枝
決策樹的剪枝就是最大程度的保證泛化能力。
我們的優化目标就是保證樹的整體不确定性盡量低，同時樹模型的複雜度也要低。
思路，分析如何降低樹整體的損失函數：
1.減少第一部分樹的不确定性：我們可以增加一些特征，增加特征，意味着限制條件變強了，決策樹的分類效果自然而然的會變好。但是對于給定的資料集我們是很難再繼續添加新特征了，是以這個方式雖然可取但不可行。
2.減少第二部分樹的整體複雜度：我們需要對生成的樹進行剪枝。剪枝完後樹的規模剪小了，但是樹整體的不确定性可能會增大，這時我們就要尋找一個比較優雅的剪枝政策，在降低樹模型複雜度的情況下，盡量小的增加樹的不确定性。
上圖，所有葉子節點的熵權重求和得到誤差評價函數C(T)。
α 用來平衡誤差評價函數和樹的大小。
剪枝方法
第二種方式講解：
小寫的tr相當于把大寫Tr的大樹拆成一個小樹，是以小tr的誤差要大。
腦圖：
随機森林
次優樹是Gini指數評估的CART樹。不需要剪枝了，弄很多樹，對結果投票，通常樹的數目是奇數。
随機森林是一種應用很廣泛的方法。
随機森林不用交叉驗證。OOB錯誤率：oob誤分率是随機森林泛化誤差的一個無偏估計，它的結果近似于需要大量計算的k折交叉驗證。
具體步驟：對于已經生成的随機森林,用袋外資料測試其性能,假設袋外資料總數為O,用這O個袋外資料作為輸入,帶進之前已經生成的随機森林分類器,分類器會給出O個資料相應的分類,因為這O條資料的類型是已知的,則用正确的分類與随機森林分類器的結果進行比較,統計随機森林分類器分類錯誤的數目,設為X,則袋外資料誤差大小=X/O;這已經經過證明是無偏估計的,是以在随機森林算法中不需要再進行交叉驗證或者單獨的測試集來擷取測試集誤差的無偏估計。
腦圖：