目錄
1.樹的生成算法（分類樹、回歸樹）
2.特征處理（連續型特征、非二值特征）
3.類别不均衡問題的處理
4.剪枝問題（預剪枝、後剪枝）
本文通過僞代碼級别的描述，詳細說明樹的生成算法。更多内容歡迎點贊和收藏，後續持續補充
分類樹的生成算法
在不考慮剪枝問題的情況下，分類樹的損失函數是對所有的葉子結點的熵求和，這個值越小說明對樣本的分類越精确。由于葉子結點包含的樣本數量不同，采用樣本數量作為權重。
采用貪心算法來進行樹的建構，這裡以ID3為例，來建構分類決策樹。
ID3算法：
輸入：訓練集D，特征集A
輸出：決策樹T
步驟：
（1）初始化，将D視為一個根結點node，指派給決策樹T
（2）檢查是否滿足退出疊代的條件，如果滿足，則退出，輸出決策樹T；如果不滿足，繼續執行步驟3
（3）計算特征集A中每個特征對于訓練集D的資訊增益，選擇資訊增益最大的特征α
（4）以特征α的取值為标準，将集合D分成多個子集合Di，并生成多個子結點subnode，分别以node為父結點
（5）以子集Di為訓練集，{A-α}為特征集分别調用步驟2-5
其中，退出條件包括
（1）樹的層數大于門檻值
結點的深度可以了解為結點與決策樹跟結點的距離，如根結點的子結點的深度為1，因為這些結點與跟結點的距離為1，子結點的深度要比父結點的深度大1。決策樹的深度是所有葉子結點的最大深度，當深度到達指定的上限大小時，停止分裂。
（2）樹的葉結點的熵的和小于門檻值
由上述可知，熵和基尼值的大小表示資料的複雜程度，當熵或者基尼值過小時，表示資料的純度比較大，如果熵或者基尼值小于一定程度數，結點停止分裂。
（3）所有特征已經使用完畢，不能再繼續分裂
被動式停止分裂的條件，當已經沒有可分的屬性時，直接将目前結點設定為葉子結點。
（4）結點的資料樣本小于門檻值
當結點的資料量小于一個指定的數量時，不繼續分裂。兩個原因：一是資料量較少時，再做分裂容易強化噪聲資料的作用；二是降低樹生長的複雜性。提前結束分裂一定程度上有利于降低過拟合的影響。
（5）葉結點的資料樣本全部屬于一個分類
被動式停止分裂的條件，當資料樣本無法繼續分類時，直接将目前結點設定為葉子結點。
在ID3的基礎上，将分類标準改成資訊增益率就是CD4.5算法，将分類标準改為基尼系數就是CART算法。（1）ID3最大的問題是容易出現過拟合。這個跟選取資訊增益作為分類标準有關。
如果一個特征的可取值數目多，這個特征的資訊增益較大。舉一個例子，“uid”的特征的條件熵為0，因而資訊增益最大。
（2）CD4.5解決了過拟合的問題。部分原因是選擇資訊增益率作為分類标準。
資訊增益率增加了特征固有值作為懲罰項，改善了選擇資訊增益為标準帶來的問題。
（3）CART樹的生成效率最高，一方面是因為選擇基尼系數作為分類标準，基尼系數将對數運算變成了乘數運算，提高計算效率；另一方面是因為CART是二叉樹，簡化了決策樹規模。
回歸樹的生成算法
如果預測變量是連續型的，則生成回歸決策樹。
CART回歸樹為回歸決策樹。CART回歸樹的損失函數是平方誤差，表示為 Loss(y,f(x))=(f(x)−y)^2。
一個回歸樹分叉對應着輸入空間（即特征空間）的一個劃分以及在劃分單元上的輸出值。
假如我們有n個特征，每個特征有si(i∈(1,n))個取值，我們通過周遊找到每個特征j的劃分點的值s，使得損失函數取最小值。描述該過程的公式如下：
其中，損失函數定義為平方損失函數 Loss(y,f(x))=(f(x)−y)^2
CART回歸樹生成算法：
輸入：訓練集D
輸出：回歸樹f(x)
步驟：
（1）周遊所有的變量，所有的切分點，找到最優解（j，s）使得損失函數取到最小值
（2）用標明的對(j,s)劃分區域并計算相應的輸出值，輸出值取值為空間Rm中所有值的平均數。
（3）繼續對兩個子區域調用步驟1，直至滿足停止條件（比如葉子結點的樣本數少于某個門檻值）。
（4）将輸入空間劃分為M個區域R1,R2,...Rm生成決策樹：