監督學習-分類-決策樹
決策樹使用樹形分支結構分類事物
例：
- 小麗找對象，要求：高、帥、富
- 小明找對象，要求：美美美
if height >= 172:
if hansom = '帥':
if rich >= 5000000:
print('小哥哥我晚上有空！')
else:
print('加個微信吧！')
else:
print('孩子放學了，我該做飯去了！')
else:
print('呵呵，洗澡去了！')
構造二叉樹結構的兩個名額：
- 在什麼地方分支（特征的先後次序，執行效率不同）
- 分支的門檻值定多數合适？
所謂的決策樹算法，就是通過資料自動學習出二叉樹的分支次元順序和每個分支的門檻值
與一般的分支結構不同，決策樹的分支條件（特征次元、門檻值）通過訓練得到，而非手動構造
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
決策樹skicit-learn實作
1：擷取資料，特征工程，樣本資料（特征和标簽）
iris = load_iris()
# iris
X = iris['data'][:, 2:]
y = iris['target']
# X
2：将樣本資料分為訓練集和測試集
為友善可視化了解，隻取第2和第3列兩維特征
from sklearn.model_selection import train_test_split
3：算法：建立分類器
- 調包，調用不同分類器
- 調參，調節超參數
from sklearn.tree import DecisionTreeClassifier
# 建立空分類器
# my_classifier = DecisionTreeClassifier()
my_classifier = DecisionTreeClassifier(max_depth=2, criterion='entropy', random_state=42)
# # max_depth最大深度，entropy資訊熵算法，随機種子
my_classifier
DecisionTreeClassifier(class_weight=None, criterion='entropy', max_depth=2,
max_features=None, max_leaf_nodes=None,
min_impurity_decrease=0.0, min_impurity_split=None,
min_samples_leaf=1, min_samples_split=2,
min_weight_fraction_leaf=0.0, presort=False,
random_state=42, splitter='best')
4：訓練：用訓練集（特征和标簽）訓練分類器
DecisionTreeClassifier(class_weight=None, criterion='entropy', max_depth=2,
max_features=None, max_leaf_nodes=None,
min_impurity_decrease=0.0, min_impurity_split=None,
min_samples_leaf=1, min_samples_split=2,
min_weight_fraction_leaf=0.0, presort=False,
random_state=42, splitter='best')
5:預測：使用測試集（特征）預測标簽
predictions = my_classifier.predict(X_test)
predictions
array([0, 0, 0, 0, 0, 2, 1, 0, 2, 1, 1, 0, 1, 1, 2, 0, 1, 2, 2, 0, 2, 2,
2, 1, 0, 2, 1, 1, 1, 1, 0, 0, 2, 1, 0, 0, 2, 0, 2, 1, 2, 1, 0, 0,
2])
predictions.shape
(45,)
6：用測試集自帶的标簽和預測的标簽比較，評價分類器的準确率
from sklearn.metrics import accuracy_score
0.9555555555555556
決策樹原理可視化
# 繪圖函數，不用寫，直接調用
def plot_decision_boundary(model, axis):
x0, x1 = np.meshgrid(
np.linspace(axis[0], axis[1], int((axis[1]-axis[0])*100)).reshape(-1, 1),
np.linspace(axis[2], axis[3], int((axis[3]-axis[2])*100)).reshape(-1, 1),
)
X_new = np.c_[x0.ravel(), x1.ravel()]
y_predict = model.predict(X_new)
zz = y_predict.reshape(x0.shape)
from matplotlib.colors import ListedColormap
custom_cmap = ListedColormap(['#EF9A9A','#FFF59D','#90CAF9'])
plt.contourf(x0, x1, zz, cmap=custom_cmap)
plot_decision_boundary(my_classifier, axis=[0.5, 7.5, 0, 3])
plt.scatter(X[y==0, 0], X[y==0, 1])
plt.scatter(X[y==1, 0], X[y==1, 1])
plt.scatter(X[y==2, 0], X[y==2, 1])
<matplotlib.collections.PathCollection at 0x134be1d0>
[外鍊圖檔轉存失敗(img-RkKTIih7-1566998078176)(output_21_1.png)]
下面代碼，生成可視化檔案的庫：graphviz需要安裝，不同環境安裝方式不同
- 可以使用 export_graphviz 導出器以 Graphviz 格式導出決策樹
- 如果你是用 conda 來管理包，那麼安裝 graphviz 二進制檔案和 python 包可以用以下指令安裝：
# Conda安裝庫指令
conda install python-graphviz
注：網絡問題可能需要翻牆
pdf檔案是在整個 iris 資料集上訓練的決策樹樹的 graphviz 導出示例，其結果被儲存在 iris_xxx.pdf 中:
- iris_entropy.pdf
- iris_gini.pdf
生成文檔中：
- gini值為目前節點系統基尼系數
- entropy值為目前節點系統熵值
- samples值為此分支節點下還有多少值待拆分
- values值為待拆分值的分類
import graphviz
from sklearn.tree import export_graphviz
# # 基尼系數算法
# dot_data = export_graphviz(my_classifier, out_file=None)
# graph = graphviz.Source(dot_data)
# graph.render("iris_gini")
# # 資訊熵算法
# dot_data = export_graphviz(my_classifier, out_file=None)
# graph = graphviz.Source(dot_data)
# graph.render("iris_entropy")
用下面測試資料人工模拟決策樹分類過程
模拟時，data的下标是0，1，2，3，target的結果是0，1，2
(array([1.4, 0.2]), array([4.5, 1.5]), array([5.9, 2.1]))
(0, 1, 2)
決策樹原理
- 每個分支節點在哪個特征次元劃分？
- 某個特征次元在什麼值劃分？
根據某一特征次元下的某一門檻值進行二分，劃分後使得整個系統資訊熵降低
資訊熵
資訊熵：不确定性的度量
- 封閉系統，不确定性越高，熵值越大，越混亂
- 封閉系統，不确定性越低，熵值越小，越規律
資訊熵公式：$ H=-\sum ^{k}{i=1}p{i}\log \left( p_{i}\right) $
- 解釋：一個封閉系統中，有k類資訊，每類資訊的比例為p
資訊、能量、物質三者是可以互相轉換的
例：鸢尾花資料集，共有3類鸢尾花，每類鸢尾花所占比例為1/3，p1/p2/p3都等于1/3，本系統熵值為：
$ H= -\dfrac {1}{3}\cdot \log \left( \dfrac {1}{3}\right) -\dfrac {1}{3}\cdot \log \left( \dfrac {1}{3}\right) -\dfrac {1}{3}\cdot \log \left( \dfrac {1}{3}\right) =1.0986 $
1.584962500721156
例：一個封閉系統，三種花所占比例為：1/10、2/10、7/10，本系統熵值為：
1.1567796494470395
例：一個封閉系統，三種花所占比例為：1, 0, 0，本系統熵值為：
-0.0
1.58 - 1.15 # 資訊增益，傳入一條資訊到封閉空間，導緻空間熵值下降，下降數就是資訊量
# 原封閉系統，熵值最大就是1.58，最小是0
0.43000000000000016
資訊熵圖像
- 設系統分兩類，一類比例為x，則另一類比例為1-x
- 代入資訊熵公式：H = -x*log(x)-(1-x)*log(1-x)
def en(x):
return -x * np.log2(x) - (1-x) * np.log2(1-x)
x = np.linspace(0.01, 0.99, 200) # 對數的底大于0且不等于1
x
plt.plot(x, en(x)) # x軸為分類的比例，y軸為熵值
plt.xticks(np.arange(10)*0.1)
plt.grid(linewidth=0.2)
plt.show()
[外鍊圖檔轉存失敗(img-112FJKKi-1566998078184)(output_38_0.png)]
結論：2分類系統中，類别比例0.5的，熵值最大，不确定性最高
使用資訊熵尋找最優劃分
- 周遊特征資料下所有可劃分特征次元和所有取值
- 當劃分一種特征一個值後，系統熵值降到最低，此特征下的此值就是本分支節點
- 繼續用分割後熵值不為0的特征資料劃分下一分支節點，循環往複
- 直到整個系統熵降到最低
手寫決策樹算法
使用資訊熵作為名額劃分資料為不同類别
from collections import Counter
# 計算系統總資訊熵的流程
y
Counter(y)
res = 0
for i in Counter(y).values():
print(i)
p = i / len(y) # 每類值出現的機率
res += -p * np.log2(p)
res
50
50
50
1.584962500721156
# 劃分類别函數
def split(X, y, d, value): # 特征，标簽，次元，門檻值
index_a = X[:, d] <= value # 布爾索引
index_b = X[:, d] > value
# 傳回被劃分後的兩類資料(特征和标簽)
return X[index_a], X[index_b], y[index_a], y[index_b]
# 計算資訊熵的函數
def entropy(y):
counter = Counter(y)
res = 0.0
for i in counter.values():
p = i / len(y) # 每類值出現的機率
res += -p * np.log2(p)
return res
# 尋找最佳次元和門檻值，讓每次劃分後系統資訊熵下降最大（資訊熵最低）
def try_split(X, y):
best_entropy = float('inf') # 系統拆分後的總資訊熵，設為正無窮大
best_d, best_v = -1, -1 # 劃分次元和本次元下的劃分門檻值
# 周遊特征列
# d的取值為0， 1，總共隻有2兩列，0代表花瓣長1代表花瓣寬
for d in range(X.shape[1]): # 周遊特征資料X最外維的值（周遊所有特征列）
# 周遊特征行（取每兩行 特征值的中間值）
sorted_index = np.argsort(X[:, d]) # 排序特征行（d列的所有行）
for i in range(1, len(X)): #
x1 = X[sorted_index[i - 1], d] # 本列特征值i- 1
x2 = X[sorted_index[i], d]
if x1 != x2: # 如果相等則沒有劃分價值，跳過代碼
v = (x1 + x2) / 2 # 候選門檻值
# 資料用本次元和門檻值劃分為left和right兩部分
X_l, X_r, y_l, y_r = split(X, y, d, v)
# 本門檻值劃分後的系統熵值
e = entropy(y_l) + entropy(y_r)
if e < best_entropy: # 如果切分後的新系統熵值更小，更新參數
best_entropy, best_d, best_v = e, d, v
return best_entropy, best_d, best_v
try_split(X, y)
(1.0, 0, 2.45)
best_entropy, best_d, best_v = try_split(X_train, y_train)
print('最低系統資訊熵為：', best_entropy)
print('最佳劃分次元為：', best_d)
print('本次元最佳劃分門檻值為：', best_v)
最低系統資訊熵為： 1.0
最佳劃分次元為： 0
本次元最佳劃分門檻值為： 2.45
# 第一次劃分後的結果
X1_l, X1_r, y1_l, y1_r = split(X_train, y_train, best_d, best_v)
X1_l.shape, X1_r.shape, y1_l.shape, y1_r.shape
((33, 2), (72, 2), (33,), (72,))
# 檢視劃分後的左側标簽，資訊熵為0，說明完全劃分完畢
entropy(y1_l), entropy(y1_r) # 右側熵不為0，有待繼續劃分
(0.0, 1.0)
# 繼續劃分右側資料
best_entropy2, best_d2, best_v2 = try_split(X1_r, y1_r)
print('最低系統資訊熵為：', best_entropy2)
print('最佳劃分次元為：', best_d2)
print('本次元最佳劃分門檻值為：', best_v2)
最低系統資訊熵為： 0.5898925289094291
最佳劃分次元為： 0
本次元最佳劃分門檻值為： 4.75
# 第二次劃分
X2_l, X2_r, y2_l, y2_r = split(X1_r, y1_r, best_d2, best_v2)
X2_l.shape, X2_r.shape, y2_l.shape, y2_r.shape
((34, 2), (38, 2), (34,), (38,))
(0.19143325481419343, 0.3984592740952357)
系統分支熵值仍不為0，還可繼續劃分，略
剛才的運算構造的決策樹為：
if X[0] <= 2.45:
X_left_en = 0.0
print('第一種鸢尾花，分類完畢')
else:
if X[0] <= 4.75:
left_en = 0.191
print('第二種鸢尾花')
else:
right_en = 0.398
print('第三種鸢尾花')
基尼系數
基尼系數公式： G = 1 − ∑ i = 1 k p i 2 G=1-\sum_{i=1}^{k} p_{i} 2 G=1−∑i=1kpi2
例：三種鸢尾花，比例都為1/3，基尼系數為： G = 1 − ( 1 3 ) 2 − ( 1 3 ) 2 − ( 1 3 ) 2 = 0.6666 G=1-\left(\frac{1}{3}\right)^{2}-\left(\frac{1}{3}\right)^{2}-\left(\frac{1}{3}\right)^{2}=0.6666 G=1−(31)2−(31)2−(31)2=0.6666
0.6666666666666665
例：三種花，比例為：1/10，2/10，7/10，基尼系數為：
0.4600000000000001
例：三種花，比例為：1,0,0，基尼系數為：
基尼系數圖像
- 設系統分兩類，一類比例為x，則另一類比例為1-x
- 代入資訊熵公式： G = 1 − ( x 2 + ( 1 − x ) ∗ 2 ) = − 2 x 2 + 2 x G=1-\left(x^2+(1-x)* 2\right)=-2x^2+2x G=1−(x2+(1−x)∗2)=−2x2+2x# 抛物線
def gini(x):
return 1 - (x ** 2 + (1-x) ** 2)
x = np.linspace(0.01, 0.99, 200) # 對數的底大于0且不等于1
x
plt.plot(x, gini(x)) # x軸為分類的比例，y軸為熵值
plt.xticks(np.arange(10)*0.1)
plt.grid(linewidth=0.2)
plt.show()
[外鍊圖檔轉存失敗(img-lOdBZ28k-1566998078187)(output_61_0.png)]
def en(x):
return -x * np.log2(x) - (1-x) * np.log2(1-x)
def gini(x):
return 1 - (x ** 2 + (1-x) ** 2)
x = np.linspace(0.01, 0.99, 200) # 對數的底大于0且不等于1
plt.plot(x, en(x), color='r', alpha=0.8, label='en') # x軸為分類的比例，y軸為熵值
plt.plot(x, gini(x)+0.5, color='g', alpha=0.8, label='gini')
plt.xticks(np.arange(10)*0.1)
plt.grid(linewidth=0.2)
plt.legend()
<matplotlib.legend.Legend at 0x531c748>
[外鍊圖檔轉存失敗(img-Yh21dqip-1566998078191)(output_62_1.png)]
基尼系數和資訊熵比較
- 資訊熵計算比基尼系數更慢（對數運算）
- sklearn預設基尼系數
- 二者差異較小，大部分資料下優劣相當
決策樹作為一個算法類别，有很多不同實作
- ID3
- 隻能做分類，分支為二分或多分
- 使用資訊增益做分隔
- C4.5
- 隻能做分類，分支為二分或多分
- 使用資訊增益比來分特征（懲罰了值類别特别多的特征）
- C5.0
- C4.5的性能提升版
- CART
- Classification And Regression Tree，分類和回歸樹
- 能做分類也能做回歸（可以用分類後值的機率作為回歸結果）
- 分支為二叉樹
- 使用基尼系數來分特征
sklearn内的決策樹算法實作為CART算法的最優版本
決策樹剪枝：對一些參數進行平衡
剪去枝幹，讓樹變小，目的是：
- 降低複雜度
- 解決過拟合
過拟合和模型精确度是一對互相沖突的名額：
- 拟合程度越低，模型預測越不精确
- 精确度越高，越容易過拟合
- 二者需要取得平衡，在适度拟合的前提下，模型預測達到最精确
選擇模型的标準：如果兩個模型精度一樣，效率也一樣，選擇更簡單那個
- 奧卡姆剃刀原理
- 如無必要，勿增實體
科學思維：車庫裡的龍
import numpy as np
import matplotlib.pyplot as plt
# 生成非線性測試資料
from sklearn import datasets
X, y = datasets.make_moons(noise=0.25, random_state=666) # 噪點參數0.25
X[:5]
array([[ 1.09760106, 0.85766164],
[-0.01322635, 0.07455881],
[-0.48210848, 0.86080586],
[-0.91727991, 0.82195148],
[-0.84571072, 0.61547083]])
y
array([1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0,
1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1,
1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0,
0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0,
0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0], dtype=int64)
plt.scatter(X[y==0, 0], X[y==0, 1])
plt.scatter(X[y==1, 0], X[y==1, 1])
<matplotlib.collections.PathCollection at 0x53864e0>
[外鍊圖檔轉存失敗(img-Lp7ACHtZ-1566998078196)(output_67_1.png)]
預設參數訓練模型
from sklearn.tree import DecisionTreeClassifier
dt_clf = DecisionTreeClassifier()
dt_clf.fit(X, y)
DecisionTreeClassifier(class_weight=None, criterion='gini', max_depth=None,
max_features=None, max_leaf_nodes=None,
min_impurity_decrease=0.0, min_impurity_split=None,
min_samples_leaf=1, min_samples_split=2,
min_weight_fraction_leaf=0.0, presort=False,
random_state=None, splitter='best')
# 預設參數訓練模型可視化
plot_decision_boundary(dt_clf, axis=[-1.5, 2.5, -1.0, 1.5])
# axis為橫軸和衆軸的範圍
plt.scatter(X[y==0,0], X[y==0,1])
plt.scatter(X[y==1,0], X[y==1,1])
# 分支規則太細，過拟合明顯
<matplotlib.collections.PathCollection at 0x5468128>
[外鍊圖檔轉存失敗(img-8LB320kK-1566998078208)(output_70_1.png)]
# 設分支最大深度為2（值越小越不容易過拟合）
# 分割兩次，每次都限制最大和最小範圍
dt_clf2 = DecisionTreeClassifier(max_depth=2)
dt_clf2.fit(X, y)
plot_decision_boundary(dt_clf2, axis=[-1.5, 2.5, -1.0, 1.5])
plt.scatter(X[y==0,0], X[y==0,1])
plt.scatter(X[y==1,0], X[y==1,1])
<matplotlib.collections.PathCollection at 0xfd38be0>
[外鍊圖檔轉存失敗(img-7iaWO4DJ-1566998078215)(output_71_1.png)]
# 節點至少有x個樣本資料才會繼續分支（值越高越不容易過拟合）
dt_clf3 = DecisionTreeClassifier(min_samples_split=10)
dt_clf3.fit(X, y)
plot_decision_boundary(dt_clf3, axis=[-1.5, 2.5, -1.0, 1.5])
plt.scatter(X[y==0,0], X[y==0,1])
plt.scatter(X[y==1,0], X[y==1,1])
<matplotlib.collections.PathCollection at 0xfbe3198>
[外鍊圖檔轉存失敗(img-wBIJ2scR-1566998078218)(output_72_1.png)]
# 葉子節點至少應該有x個樣本資料（最終節點内最少樣本數，越大越不容易過拟合）
dt_clf4 = DecisionTreeClassifier(min_samples_leaf=6)
dt_clf4.fit(X, y)
plot_decision_boundary(dt_clf4, axis=[-1.5, 2.5, -1.0, 1.5])
plt.scatter(X[y==0,0], X[y==0,1])
plt.scatter(X[y==1,0], X[y==1,1])
<matplotlib.collections.PathCollection at 0xfc56710>
[外鍊圖檔轉存失敗(img-KcplM0NA-1566998078223)(output_73_1.png)]
# 最多有多少個葉子節點（越少越不容易過拟合）
dt_clf5 = DecisionTreeClassifier(max_leaf_nodes=4)
dt_clf5.fit(X, y)
plot_decision_boundary(dt_clf5, axis=[-1.5, 2.5, -1.0, 1.5])
plt.scatter(X[y==0,0], X[y==0,1])
plt.scatter(X[y==1,0], X[y==1,1])
<matplotlib.collections.PathCollection at 0xfcc6c88>
[外鍊圖檔轉存失敗(img-B1ps3gwm-1566998078228)(output_74_1.png)]
# # 更多參數見文檔
# help(DecisionTreeClassifier)
決策樹解決回歸問題
from sklearn import datasets
X = boston.data
y = boston.target
# X
X.shape
(506, 13)
array([24. , 21.6, 34.7, 33.4, 36.2, 28.7, 22.9, 27.1, 16.5, 18.9])
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=666)
from sklearn.tree import DecisionTreeRegressor
dt_reg = DecisionTreeRegressor()
dt_reg.fit(X_train, y_train) # 訓練
DecisionTreeRegressor(criterion='mse', max_depth=None, max_features=None,
max_leaf_nodes=None, min_impurity_decrease=0.0,
min_impurity_split=None, min_samples_leaf=1,
min_samples_split=2, min_weight_fraction_leaf=0.0,
presort=False, random_state=None, splitter='best')
array([27.1, 50. , 20.4, 34.9, 21.6, 21.1, 17.8, 20.5, 28.5, 16.7, 8.8,
23.9, 22.9, 16.7, 22.9, 26.4, 32.5, 18.4, 14.1, 30.1, 23.3, 10.4,
10.2, 48.3, 27.5, 15. , 21.2, 13.4, 36.1, 32.2, 43.1, 9.5, 31.5,
17.8, 22.6, 22.4, 36. , 32.5, 23.1, 13.3, 24. , 20.6, 26.6, 16.8,
24.1, 10.2, 30.1, 34.9, 24.4, 22.7, 24.6, 23.3, 50. , 16.8, 21.4,
18.8, 21.7, 15.2, 14.1, 15.6, 20.9, 20.4, 28. , 14.9, 14.3, 10.4,
22.4, 24. , 23.8, 20.3, 5.6, 31.5, 18.2, 14.9, 46. , 22.4, 5.6,
23.8, 19. , 32.7, 28.4, 22. , 10.2, 30.1, 36.1, 19.4, 23.3, 24.3,
19.7, 50. , 15.6, 34.6, 24.6, 32.5, 19.5, 13.3, 29.8, 23.3, 13.3,
16.3, 17.8, 16.1, 24.8, 14.1, 17.7, 23.1, 16.1, 21.7, 22.6, 23.1,
48.3, 20.5, 22.4, 5.6, 22.2, 24.4, 17.8, 13.3, 33.2, 16.8, 21.9,
20.3, 25.1, 12.3, 10.4, 33.4, 12.7])
1.0
0.5883659617972887
決策樹的局限
- 分類邊界橫平豎直，不能如實反映資料真實分隔情況
- 對某些邊界值很敏感，資料一點小改變會導緻結果發生很大變化
決策樹的優勢：
- 結果具有可解釋性
- 決策樹模型之前的差異性大，模型多樣化，最适合做內建學習
實際工作中，決策樹一般不單獨使用，而是和轉為內建算法中的随機森林，更好的應用
![jdk1.7+Eclipse+Maven3.5+Hadoop2.7.3建構hadoop項目[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)