1.總概述
決策樹(desicion tree)是一種樹形結構，其中每個内部節點表示在一個屬性上的測試，每個分支代表一個測試輸出，每個葉節點代表一個類别。
決策樹以執行個體為基礎進行歸納學習。其采用自上而下的遞歸方式，基本思路是以資訊熵為度量構造一棵熵值下降最快的樹，到葉子節點時熵值應該下降為零。此時每個葉節點中包含的執行個體都為同一類。
2.資訊熵
2.1 熵
熵 (entropy) 這一概念來源于熱力學，是混亂程度的度量。
而資訊熵(information entropy)這一概念在1948年被引入，旨在幫助人們度量一個資訊。資訊量的度量就等于其不确定性的大小。資訊熵的大小與這條資訊的确定性成反比。
2.2 條件熵
(x,y)發生的熵減去(x)發生的熵，即為在x條件下，y發生的熵。
條件熵的推導公式如下：
若想了解更多有關機器學習中的熵、條件熵、交叉熵以及相對熵，可以跳轉機器學習中的熵。
3.決策樹
3.1 資訊增益
資訊增益表示得知特征A的資訊使得使得類X的資訊的不确定度減少的程度。資訊增益G(D,A)定義為集合D的資訊熵H(D)與給定特征條件A下的條件熵H(D,A)之差。這也被稱為特征A與資料集D的互資訊。
資訊增益的計算方法如下：
3.2 基尼系數
基尼系數(gini coefficient/index )計算方法如下：
若想對基尼系數有更多的了解，可前往基尼系數。
3.3 資訊增益率
3.4 決策樹學習算法
3.4.1 ID3
使用資訊增益/互資訊G(D,A)來進行特征選擇。
ID3算法所采用的度量标準就是我們前面所提到的“資訊增益”。當屬性a的資訊增益最大時，則意味着用a屬性劃分，其所獲得的“純度”提升最大。我們所要做的，就是找到資訊增益最大的屬性。
3.4.2 C4.5
使用資訊增益率來進行特征選擇。
實際上，資訊增益準則對于可取值數目較多的屬性會有所偏好，為了減少這種偏好可能帶來的不利影響，C4.5決策樹算法不直接使用資訊增益，而是使用“資訊增益率”來選擇最優劃分屬性。
需要注意的是，增益率準則對可取值數目較少的屬性有所偏好。是以一般這樣選取劃分屬性：先從候選屬性中找出資訊增益高于平均水準的屬性，再從中選擇增益率最高的。
3.4.3 CART
CART(classification and regression train)，使用基尼系數來進行特征選擇。
一個屬性的資訊增益(率)/基尼系數越大，表明屬性對樣本的熵的減少的能力更強，這個屬性使得一個資料由不确定變為确定的能力更強。
3.5 損耗函數
損耗函數的推導過程可參見損耗函數。
3.6 過拟合
決策樹對于訓練資料能夠有很好的分類能力，但對未知的測試資料卻未必能有很好的分類能力，即決策樹很有可能産生過拟合的現象。
針對過拟合的現象，有以下兩種解決方法。
3.6.1 剪枝
3.6.1.1 概述
三種算法的剪枝過程算法相同，差別僅僅在于對于目前樹的評價标準不同。
3.6.1.2 總體思路
由完全樹T0開始進行剪枝，剪枝部分結點得到T1，再次剪枝部分結點得到T2，不斷重複剪枝部分結點，直至僅剩樹根的樹Tk。
在驗證資料集上對這k個樹分别評價，選擇損失函數最小的數Ta。
3.6.1.3 剪枝系數的确定
葉節點越多，決策樹也就越複雜，損失也就越大。
當α=0時，未剪枝的決策樹損失最小。當α=+∞時，單根結點的決策樹損失最小。
假設此時對以r為根的子樹進行剪枝，剪枝後，隻保留r本身而删掉所有的葉子。
此時剪枝後的損耗函數：
剪枝前的損耗函數：
令二者相等，可得：
此時α即為結點r的剪枝系數。
3.6.1.4 剪枝算法
對于給定的決策樹T0：
計算所有内部結點的剪枝系數；
查找剪枝系數最小的結點，剪枝得到決策樹Tk；
重複上述兩個步驟，知道決策樹隻剩下一個結點；
可以得到決策樹序列T0T1T2…Tk；
使用驗證樣本集選擇最優子樹，其選擇标準可以選用損耗函數。
3.6.2 随機森林
随機森林具體内容見下文。
4.Bagging和随機森林
4.1 Bagging的政策
Bagging(bootstrap aggregation)的政策如下：
從樣本集中有重複地選取出n個樣本；
在所有屬性上，對這個n個樣本建立分類器(ID3、C4.5、CART、logistic回歸、SVM等等)；
重複上述兩步m次，即獲得了m個分類器；
将資料放在這m個分類器上，最後根據這m個分類器的投票結果，決定資料屬于哪一類。
4.2 随機森林
随機森林在Bagging的基礎上做了一部分修改。其政策如下：
在樣本集中用bootstrap采樣選取n個樣本；
從所有屬性中随機選擇k個屬性，選擇最佳分割屬性作為節點建立CART決策樹；
重複以上兩步m次，即建立了m棵CART決策樹；
這m棵CART決策樹形成了随機森林，通過投票表決結果，來決定資料屬于哪一類。
4.3 随機森林與決策樹的關系
使用決策樹作為基本分類器，采用Bagging的政策，所形成的總分類器為“随機森林”；但是使用SVM、logistic回歸等其他分類器，采用Bagging的政策，所形成的總分類器也被叫做“随機森林”。
5.代碼實踐
5.1 随機森林分類
import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl
from sklearn import tree
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
def iris_type(s):#為了友善之後資料預處理
it = {b'Iris-setosa': 0, b'Iris-versicolor': 1, b'Iris-virginica': 2}
return it[s]
# 花萼長度、花萼寬度，花瓣長度，花瓣寬度
iris_feature = u'花萼長度', u'花萼寬度', u'花瓣長度', u'花瓣寬度'
if __name__ == "__main__":
mpl.rcParams['font.sans-serif'] = [u'SimHei']
mpl.rcParams['axes.unicode_minus'] = False
path = '8.iris.data' # 資料檔案路徑
data = np.loadtxt(path, dtype=float, delimiter=',', converters={4: iris_type})
x, y = np.split(data, (4,), axis=1)
# 為了可視化，僅使用前兩列特征
x = x[:, :2]
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size=0.3, random_state=1)
# 決策樹參數估計
model = Pipeline([
('ss', StandardScaler()),
('DTC', DecisionTreeClassifier(criterion='entropy', max_depth=3))])
model = model.fit(x_train, y_train)
y_test_hat = model.predict(x_test) # 測試資料
#畫決策樹圖
f = open('.\\iris_tree.dot', 'w')
tree.export_graphviz(model.get_params('DTC')['DTC'], out_file=f)
f.close()
N, M = 100, 100 # 橫縱各采樣多少個值
x1_min, x1_max = x[:, 0].min(), x[:, 0].max() # 第0列的範圍
x2_min, x2_max = x[:, 1].min(), x[:, 1].max() # 第1列的範圍
t1 = np.linspace(x1_min, x1_max, N)
t2 = np.linspace(x2_min, x2_max, M)
x1, x2 = np.meshgrid(t1, t2) # 生成網格采樣點
x_show = np.stack((x1.flat, x2.flat), axis=1) # 測試點
cm_light = mpl.colors.ListedColormap(['#A0FFA0', '#FFA0A0', '#A0A0FF'])
cm_dark = mpl.colors.ListedColormap(['g', 'r', 'b'])
y_show_hat = model.predict(x_show) # 預測值
y_show_hat = y_show_hat.reshape(x1.shape) # 使之與輸入的形狀相同
plt.figure(facecolor='w')
plt.pcolormesh(x1, x2, y_show_hat, cmap=cm_light) # 預測值的顯示
plt.scatter(x_test[:, 0], x_test[:, 1], c=y_test.ravel(), edgecolors='k', s=100, cmap=cm_dark, marker='o') # 測試資料
plt.scatter(x[:, 0], x[:, 1], c=y.ravel(), edgecolors='k', s=40, cmap=cm_dark) # 全部資料
plt.xlabel(iris_feature[0], fontsize=15)
plt.ylabel(iris_feature[1], fontsize=15)
plt.xlim(x1_min, x1_max)
plt.ylim(x2_min, x2_max)
plt.grid(True)
plt.title(u'鸢尾花資料的決策樹分類', fontsize=17)
plt.show()
# 訓練集上的預測結果
y_test = y_test.reshape(-1)
print (y_test_hat)
print (y_test)
result = (y_test_hat == y_test) # True則預測正确，False則預測錯誤
acc = np.mean(result)
print ('準确度: %.2f%%' % (100 * acc))
# 過拟合：錯誤率
depth = np.arange(1, 15)
err_list = []
for d in depth:
clf = DecisionTreeClassifier(criterion='entropy', max_depth=d)
clf = clf.fit(x_train, y_train)
y_test_hat = clf.predict(x_test) # 測試資料
result = (y_test_hat == y_test) # True則預測正确，False則預測錯誤
err = 1 - np.mean(result)
err_list.append(err)
print (d, ' 錯誤率: %.2f%%' % (100 * err))
plt.figure(facecolor='w')
plt.plot(depth, err_list, 'ro-', lw=2)
plt.xlabel(u'決策樹深度', fontsize=15)
plt.ylabel(u'錯誤率', fontsize=15)
plt.title(u'決策樹深度與過拟合', fontsize=17)
plt.grid(True)
plt.show()
5.2 随機森林回歸
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor
if __name__ == "__main__":
N = 100
x = np.random.rand(N) * 6 - 3 # [-3,3)
x.sort()
y = np.sin(x) + np.random.randn(N) * 0.05
x = x.reshape(-1, 1) # 轉置後，得到N個樣本，每個樣本都是1維的
reg = DecisionTreeRegressor(criterion='mse', max_depth=9)
dt = reg.fit(x, y)
x_test = np.linspace(-3, 3, 50).reshape(-1, 1)
y_hat = dt.predict(x_test)
plt.plot(x, y, 'r*', linewidth=2, label='Actual')
plt.plot(x_test, y_hat, 'g-', linewidth=2, label='Predict')
plt.legend(loc='upper left')
plt.grid()
plt.show()
# 比較決策樹的深度影響
depth = [2, 4, 6, 8, 10]
clr = 'rgbmy'
reg = [DecisionTreeRegressor(criterion='mse', max_depth=depth[0]),
DecisionTreeRegressor(criterion='mse', max_depth=depth[1]),
DecisionTreeRegressor(criterion='mse', max_depth=depth[2]),
DecisionTreeRegressor(criterion='mse', max_depth=depth[3]),
DecisionTreeRegressor(criterion='mse', max_depth=depth[4])]
plt.plot(x, y, 'k^', linewidth=2, label='Actual')
x_test = np.linspace(-3, 3, 50).reshape(-1, 1)
for i, r in enumerate(reg):
dt = r.fit(x, y)
y_hat = dt.predict(x_test)
plt.plot(x_test, y_hat, '-', color=clr[i], linewidth=2, label='Depth=%d' % depth[i])
plt.legend(loc='upper left')
plt.grid()
plt.show()