1、決策樹回歸算法核心思想
1.1、決策樹結構回顧
決策樹的典型結構如下圖所示：
主流的決策樹算法有：
- ID3：基于資訊增益來選擇分裂屬性（每步選擇資訊增益最大的屬性作為分裂節點，樹可能是多叉的）。
- C4.5：基于資訊增益率來選擇分裂屬性（每步選擇資訊增益率最大的屬性作為分裂節點，樹可能是多叉的）。
- CART：基于基尼系數來建構決策樹（每步要求基尼系數最小，樹是二叉的）。其中：CART樹全稱Classification And Regression Tree，即可以用于分類，也可以用于回歸，這裡指的回歸樹就是 CART 樹，ID3和C4.5不能用于回歸問題。
具體如下圖：
2、回歸樹算法原理
回歸樹的建構核心問題：
- 如何選擇劃分點？
- 如何決定樹中葉節點的輸出值？
假設X和Y分别為輸入和輸出變量，并且Y是連續變量，給定訓練資料集D,考慮如何生成回歸樹。
一個回歸樹對應着輸入空間（即特征空間）的一個劃分以及在劃分的單元上的輸出值。假設已将輸入空間劃分為M個單元 R1,R2,…RM ，并且在每個單元 Rm上有一個固定的輸出值 Cm ，于是回歸樹模型可以表示為：
當輸入空間的劃分确定時，可以用平方誤差：
來表示回歸樹對于訓練資料的預測誤差；用平方誤差最小的準則求解每個單元上的最優輸出值。易知，單元Rm上的 Cm的最優值 C^m 是Rm上的所有輸入執行個體 Xi對應的輸出 Yi 的均值，即：
2.1問題1：怎樣對輸入空間進行劃分？即如何選擇劃分點？
CART回歸樹采用啟發式的遞歸二分方法對輸入空間進行劃分，「自頂向下的貪婪式遞歸方案」，指的是每一次的劃分，隻考慮目前最優，而不回頭考慮之前的劃分
選擇第j個變量 X^j 和它取的值s，作為切分變量（splitting variable）和切分點（splitting point），并定義兩個區域：
和
然後尋找最優切分變量j和最優切分點s。具體地，求解：
對固定輸入變量j可以找到最優切分點s。
2.2、問題2：如何決定樹中葉節點的輸出值？
用標明的最優切分變量j和最優切分點s劃分區域并決定相應的輸出值：
和
周遊所有輸入變量，找到最優的切分變量j，構成一個對（j, s）。依此将輸入空間劃分為兩個區域。接着，對每個區域重複上述劃分過程，直到滿足停止條件為止。這樣就生成一顆回歸樹。這樣的回歸樹通常稱為最小二乘回歸樹（least squares regression tree）。 如果已将輸入空間劃分為M個區域R1,R2,…Rm，并且在每個區域Rm上有一個固定的輸出值C^m，于是回歸樹模型可以表示為：
2.3 算法流程
3、回歸樹案例
本示例來源于李航著的《統計學習方法》第5章決策樹習題中的5.2題。已知如圖3所示的訓練資料，試用平方誤差損失準則生成一個二叉回歸樹。
尋找最優切分變量j和最優切分點s的方法為：
其中，
和
例如，取s=1。此時 R1={1} ， R2={2,3,4,5,6,7,8,9,10} ，這兩個區域的輸出值分别為：
C1=4.50
C2=1/9(4.75+4.91+5.34+5.80+7.05+7.90+8.23+8.70+9.00)=6.85
根據上面的計算方法，可以得到下表：
把 C1,C2 的值代入到均方差中，如下：
C(1)=0+{(4.75−6.85)^2+(4.91−6.85)^2+(5.34−6.85)^2+(5.80−6.85)^2+(7.05−6.85)^2+(7.90−6.85)^2+(8.23−6.85)^2+(8.70−6.85)^2+(9.00−6.85)^2}=22.65
同理，可以獲得下表：
顯然取s=5時，m(s)最小。是以，第一個最優切分變量為j=5.8、最優切分點為s=5。
3.1、用標明的（j，s）劃分區域，并決定輸出值：
兩個劃分的區域分别是： R1={1,2,3,4,5},R2={6,7,8,9,10} 。輸出值用公式：
和
得到 C1=5.06,C2=8.18 。
3.2、對兩個子區域繼續調用算法流程中的步驟（1），（2）
對 R1 繼續進行劃分：
取切分點分别為：[1, 2, 3, 4, 5]，則各個區域的輸出值c如下表：
計算m(s)：
s=3時，m(3)最小。 之後的遞歸過程同上，我就不在贅述啦！最後，如下圖所示給出完整的二叉回歸樹：
4.、關于回歸樹的若幹問題
4.1、CART實作分類樹與回歸樹的差別？
CART分類樹是一種二分遞歸分割的技術，分割方法采用基于最小距離的基尼指數估計函數，将目前的樣本集分為兩個子樣本集，使得生成的的每個非葉子節點都有兩個分支。是以，CART算法生成的決策樹是結構簡潔的二叉樹。
CART分類樹是針對目标變量是離散型變量，通過二叉樹将資料進行分割成離散類的方法。而回歸樹則是針對目标變量是連續性的變量，通過選取最優分割特征的某個值，然後資料根據大于或者小于這個值進行劃分進行樹分裂最終生成回歸樹。
4.2、樹形結構為什麼不需要歸一化？
因為數值縮放不影響分裂點位置，對樹模型的結構不造成影響。 按照特征值進行排序的，排序的順序不變，那麼所屬的分支以及分裂點就不會有不同。而且，樹模型是不能進行梯度下降的，因為建構樹模型（回歸樹）尋找最優點時是通過尋找最優分裂點完成的，是以樹模型是階躍的，階躍點是不可導的，并且求導沒意義，也就不需要歸一化。
4.3、既然樹形結構（如決策樹、RF）不需要歸一化，那為何非樹形結構比如Adaboost、SVM、LR、KNN、K-Means之類則需要歸一化？
對于線性模型，特征值差别很大時，運用梯度下降的時候，損失等高線是橢圓形，需要進行多次疊代才能到達最優點。 但是如果進行了歸一化，那麼等高線就是圓形的，促使SGD往原點疊代，進而導緻需要的疊代次數較少。
4.4、決策樹如何剪枝？
決策樹的剪枝基本政策有預剪枝 (Pre-Pruning)和後剪枝 (Post-Pruning)。
- 預剪枝：其中的核心思想就是，在每一次實際對結點進行進一步劃分之前，先采用驗證集的資料來驗證如果劃分是否能提高劃分的準确性。如果不能，就把結點标記為葉結點并退出進一步劃分；如果可以就繼續遞歸生成節點。
- 後剪枝：後剪枝則是先從訓練集生成一顆完整的決策樹，然後自底向上地對非葉結點進行考察，若将該結點對應的子樹替換為葉結點能帶來泛化性能提升，則将該子樹替換為葉結點。
在第3節回歸樹的示例中，我沒有對生成的二叉回歸樹進行剪枝，感興趣的同學可以自己嘗試實作預剪枝和後剪枝，來避免生成的二叉回歸樹過拟合。
5.、代碼實作
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor
from sklearn import linear_model
# Data set
x = np.array(list(range(1, 11))).reshape(-1, 1)
y = np.array([4.50, 4.75, 4.91, 5.34, 5.80, 7.05, 7.90, 8.23, 8.70, 9.00]).ravel()
# Fit regression model
model1 = DecisionTreeRegressor(max_depth=1)
model2 = DecisionTreeRegressor(max_depth=3)
model3 = linear_model.LinearRegression()
model1.fit(x, y)
model2.fit(x, y)
model3.fit(x, y)
# Predict
X_test = np.arange(0.0, 10.0, 0.01)[:, np.newaxis]
y_1 = model1.predict(X_test)
y_2 = model2.predict(X_test)
y_3 = model3.predict(X_test)
# Plot the results
plt.figure()
plt.scatter(x, y, s=20, edgecolor="black",
c="darkorange", label="data")
plt.plot(X_test, y_1, color="cornflowerblue",
label="max_depth=1", linewidth=2)
plt.plot(X_test, y_2, color="yellowgreen", label="max_depth=3", linewidth=2)
plt.plot(X_test, y_3, color='red', label='liner regression', linewidth=2)
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()