4.1 試證明對于不含沖突資料(即特征向量完全相同但标記不同)的訓練集，必存在與訓練集一緻(即訓練誤差為 0) 的決策樹。
答：
從原書p74的圖4.2的決策樹學習的基本算法可以看出，生成一個葉節點有三種情況：
在這道題中，目标是找出和訓練集一緻的決策樹，是以不必考慮第3點，從1、2情況來看出決策樹中樹枝停止“生長”生成葉節點隻會在樣本屬于同一類或者所有特征值都用完的時候，那麼可能導緻葉節點标記與實際訓練集不同時隻會發生在特征值都用完的情況（同一節點中的樣本，其路徑上的特征值都是完全相同的），而由于訓練集中沒有沖突資料，那每個節點上訓練誤差都為0。
4.2 試析使用"最小訓練誤差"作為決策樹劃分選擇準則的缺陷。
這道題暫時沒想出答案。在網上找了其他的答案，都是認為會造成過拟合，沒給出具體證明。而我的了解決策樹本身就是容易過拟合的，就算使用資訊增益或者基尼指數等，依舊容易過拟合，至于使用“最小訓練誤差”會不會“更容易”過拟合暫時沒了解明白。
待填坑。
4.3 試程式設計實作基于資訊熵進行劃分選擇的決策樹算法，并為表 4.3 中資料生成一棵決策樹。
因為資料集的原因，資料量比較小，在選擇劃分屬性的時候會出現特征的資訊增益或者資訊增益率相同的情況。所有生成的決策樹和書中可能不一緻。并且在生成葉節點時，會出現兩類數量一直的情況，這時候葉節點就随機設定一個分類了。
代碼實作了以資訊增益、增益率、基尼指數劃分準則。下面一道題（4.4）也是用相同的代碼。另外畫圖的代碼是主要參考《機器學習實戰》決策樹那一章畫圖源碼。
有些地方代碼有點亂，比如進行剪枝的部分就有大量重複代碼；并且預剪枝部分可以在生成決策樹的時候實作，減少計算量。以後有機會再優化一下。
代碼在：
https://github.com/han1057578619/MachineLearning_Zhouzhihua_ProblemSets/tree/master/ch4--%E5%86%B3%E7%AD%96%E6%A0%91/4.3-4.4 pruning.pyimport pandas as pd
import numpy as np
def post_pruning(X_train, y_train, X_val, y_val, tree_=None):
if tree_.is_leaf:
return tree_
if X_val.empty: # 驗證集為空集時，不再剪枝
return tree_
most_common_in_train = pd.value_counts(y_train).index[0]
current_accuracy = np.mean(y_val == most_common_in_train) # 目前節點下驗證集樣本準确率
if tree_.is_continuous:
up_part_train = X_train.loc[:, tree_.feature_name] >= tree_.split_value
down_part_train = X_train.loc[:, tree_.feature_name] < tree_.split_value
up_part_val = X_val.loc[:, tree_.feature_name] >= tree_.split_value
down_part_val = X_val.loc[:, tree_.feature_name] < tree_.split_value
up_subtree = post_pruning(X_train[up_part_train], y_train[up_part_train], X_val[up_part_val],
y_val[up_part_val],
tree_.subtree['>= {:.3f}'.format(tree_.split_value)])
tree_.subtree['>= {:.3f}'.format(tree_.split_value)] = up_subtree
down_subtree = post_pruning(X_train[down_part_train], y_train[down_part_train],
X_val[down_part_val], y_val[down_part_val],
tree_.subtree['< {:.3f}'.format(tree_.split_value)])
tree_.subtree['< {:.3f}'.format(tree_.split_value)] = down_subtree
tree_.high = max(up_subtree.high, down_subtree.high) + 1
tree_.leaf_num = (up_subtree.leaf_num + down_subtree.leaf_num)
if up_subtree.is_leaf and down_subtree.is_leaf:
def split_fun(x):
if x >= tree_.split_value:
return '>= {:.3f}'.format(tree_.split_value)
else:
return '< {:.3f}'.format(tree_.split_value)
val_split = X_val.loc[:, tree_.feature_name].map(split_fun)
right_class_in_val = y_val.groupby(val_split).apply(
lambda x: np.sum(x == tree_.subtree[x.name].leaf_class))
split_accuracy = right_class_in_val.sum() / y_val.shape[0]
if current_accuracy > split_accuracy: # 若目前節點為葉節點時的準确率大于不剪枝的準确率，則進行剪枝操作——将目前節點設為葉節點
set_leaf(pd.value_counts(y_train).index[0], tree_)
else:
max_high = -1
tree_.leaf_num = 0
is_all_leaf = True # 判斷目前節點下，所有子樹是否都為葉節點
for key in tree_.subtree.keys():
this_part_train = X_train.loc[:, tree_.feature_name] == key
this_part_val = X_val.loc[:, tree_.feature_name] == key
tree_.subtree[key] = post_pruning(X_train[this_part_train], y_train[this_part_train],
X_val[this_part_val], y_val[this_part_val], tree_.subtree[key])
if tree_.subtree[key].high > max_high:
max_high = tree_.subtree[key].high
tree_.leaf_num += tree_.subtree[key].leaf_num
if not tree_.subtree[key].is_leaf:
is_all_leaf = False
tree_.high = max_high + 1
if is_all_leaf: # 若所有子節點都為葉節點，則考慮是否進行剪枝
right_class_in_val = y_val.groupby(X_val.loc[:, tree_.feature_name]).apply(
lambda x: np.sum(x == tree_.subtree[x.name].leaf_class))
split_accuracy = right_class_in_val.sum() / y_val.shape[0]
if current_accuracy > split_accuracy: # 若目前節點為葉節點時的準确率大于不剪枝的準确率，則進行剪枝操作——将目前節點設為葉節點
set_leaf(pd.value_counts(y_train).index[0], tree_)
return tree_
def pre_pruning(X_train, y_train, X_val, y_val, tree_=None):
if tree_.is_leaf: # 若目前節點已經為葉節點，那麼就直接return了
return tree_
if X_val.empty: # 驗證集為空集時，不再剪枝
return tree_
# 在計算準确率時，由于西瓜資料集的原因，好瓜和壞瓜的數量會一樣，這個時候選擇訓練集中樣本最多的類别時會不穩定（因為都是50%），
# 導緻準确率不穩定，當然在數量大的時候這種情況很少會發生。
most_common_in_train = pd.value_counts(y_train).index[0]
current_accuracy = np.mean(y_val == most_common_in_train)
if tree_.is_continuous: # 連續值時，需要将樣本分割為兩部分，來計算分割後的正确率
split_accuracy = val_accuracy_after_split(X_train[tree_.feature_name], y_train,
X_val[tree_.feature_name], y_val,
split_value=tree_.split_value)
if current_accuracy >= split_accuracy: # 目前節點為葉節點時準确率大于或分割後的準确率時，選擇不劃分
set_leaf(pd.value_counts(y_train).index[0], tree_)
else:
up_part_train = X_train.loc[:, tree_.feature_name] >= tree_.split_value
down_part_train = X_train.loc[:, tree_.feature_name] < tree_.split_value
up_part_val = X_val.loc[:, tree_.feature_name] >= tree_.split_value
down_part_val = X_val.loc[:, tree_.feature_name] < tree_.split_value
up_subtree = pre_pruning(X_train[up_part_train], y_train[up_part_train], X_val[up_part_val],
y_val[up_part_val],
tree_.subtree['>= {:.3f}'.format(tree_.split_value)])
tree_.subtree['>= {:.3f}'.format(tree_.split_value)] = up_subtree
down_subtree = pre_pruning(X_train[down_part_train], y_train[down_part_train],
X_val[down_part_val],
y_val[down_part_val],
tree_.subtree['< {:.3f}'.format(tree_.split_value)])
tree_.subtree['< {:.3f}'.format(tree_.split_value)] = down_subtree
tree_.high = max(up_subtree.high, down_subtree.high) + 1
tree_.leaf_num = (up_subtree.leaf_num + down_subtree.leaf_num)
else: # 若是離散值，則變量所有值，計算分割後正确率
split_accuracy = val_accuracy_after_split(X_train[tree_.feature_name], y_train,
X_val[tree_.feature_name], y_val)
if current_accuracy >= split_accuracy:
set_leaf(pd.value_counts(y_train).index[0], tree_)
else:
max_high = -1
tree_.leaf_num = 0
for key in tree_.subtree.keys():
this_part_train = X_train.loc[:, tree_.feature_name] == key
this_part_val = X_val.loc[:, tree_.feature_name] == key
tree_.subtree[key] = pre_pruning(X_train[this_part_train], y_train[this_part_train],
X_val[this_part_val],
y_val[this_part_val], tree_.subtree[key])
if tree_.subtree[key].high > max_high:
max_high = tree_.subtree[key].high
tree_.leaf_num += tree_.subtree[key].leaf_num
tree_.high = max_high + 1
return tree_
def set_leaf(leaf_class, tree_):
# 設定節點為葉節點
tree_.is_leaf = True # 若劃分前正确率大于劃分後正确率。則選擇不劃分，将目前節點設定為葉節點
tree_.leaf_class = leaf_class
tree_.feature_name = None
tree_.feature_index = None
tree_.subtree = {}
tree_.impurity = None
tree_.split_value = None
tree_.high = 0 # 重新設立高 和葉節點數量
tree_.leaf_num = 1
def val_accuracy_after_split(feature_train, y_train, feature_val, y_val, split_value=None):
# 若是連續值時，需要需要按切分點對feature 進行分組，若是離散值，則不用處理
if split_value is not None:
def split_fun(x):
if x >= split_value:
return '>= {:.3f}'.format(split_value)
else:
return '< {:.3f}'.format(split_value)
train_split = feature_train.map(split_fun)
val_split = feature_val.map(split_fun)
else:
train_split = feature_train
val_split = feature_val
majority_class_in_train = y_train.groupby(train_split).apply(
lambda x: pd.value_counts(x).index[0]) # 計算各特征下樣本最多的類别
right_class_in_val = y_val.groupby(val_split).apply(
lambda x: np.sum(x == majority_class_in_train[x.name])) # 計算各類别對應的數量
return right_class_in_val.sum() / y_val.shape[0] # 傳回準确率 
4.4 試程式設計實作基于基尼指數進行劃分選擇的決策樹算法，為表 4.2 中資料生成預剪枝、後剪枝決策樹并與未剪枝決策樹進行比較.
未剪枝、後剪枝、預剪枝生成決策樹分别如下，總體來說後剪枝會相比于預剪枝保留更多的分支。
有兩個需要注意的地方。一個是在4.3中說過的，因為劃分屬性的資訊增益或者基尼指數相同的原因，這個時候選擇哪一個屬性作為劃分屬性都是對的，生成決策樹和書中不一緻是正常的（書中第一個節點為“臍部”）。另外資料量這麼小的情況下，常常會出現剪枝前後準确率不變的情況，原書中也提到這種情況通常要進行剪枝的，但是這道題中若進行剪枝，會出現隻有一個葉節點的情況。為了畫圖好看點...是以都不無論在預剪枝還是後剪枝中，這種情況都會采取不剪枝政策。參考原書P82。
經過測試，在未剪枝的情況下，驗證集上準确率為0.2857；後剪枝準确率為0.5714；預剪枝也為0.5714。
未剪枝
後剪枝
預剪枝
4. 5 試程式設計實作基于對率回歸進行劃分選擇的決策樹算法，并為表 4.3 中資料生成一棵決策樹.
這個沒實作。一種思路就是拟合對率回歸後，從所有特征中選擇一個
值最高的一個特征值，即權重最高的一個特征值作為劃分選擇，但是沒想好對于One-hot之後的特征權重怎麼計算，比如“色澤”有三種取值“烏黑”、“青綠”、“淺白”，在One-hot之後會有三個特征，那麼最後“色澤”這個特征的權重應該是取平均值？以後有機會....也不填坑。
4.6 試選擇 4 個 UCI 資料集，對上述 3 種算法所産生的未剪枝、預剪枝、後剪枝決策樹進行實驗比較，并進行适當的統計顯著性檢驗.
隻拿sklearn中自帶的iris資料集試了一下剪枝後的準确率，發現不同随機數種子（使得資料集劃分不同）導緻最後驗證集的準确率變化挺大。
統計顯著性檢驗沒實作。
https://github.com/han1057578619/MachineLearning_Zhouzhihua_ProblemSets/tree/master/ch4--%E5%86%B3%E7%AD%96%E6%A0%91/4.6'''
treeCreater 和 treePlotter 代碼見 ch4/4.3-4.4
資料量不大，不同的随機數種子，測試集的準确率變化較大
'''
import pandas as pd
from sklearn import datasets
from sklearn.model_selection import train_test_split
import numpy as np
import treeCreater
import treePlottter
iris = datasets.load_iris()
X = pd.DataFrame(iris['data'], columns=iris['feature_names'])
y = pd.Series(iris['target_names'][iris['target']])
# 取三個樣本為測試集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=15)
# 剩下120個樣本中，取30個作為剪枝時的驗證集
X_train, X_val, y_train, y_val = train_test_split(X_train, y_train, test_size=0.25, random_state=15)
# 不剪枝
tree_no_pruning = treeCreater.DecisionTree('gini')
tree_no_pruning.fit(X_train, y_train, X_val, y_val)
print('不剪枝：', np.mean(tree_no_pruning.predict(X_test) == y_test))
# treePlottter.create_plot(tree_no_pruning.tree_)
# 預剪枝
tree_pre_pruning = treeCreater.DecisionTree('gini', 'pre_pruning')
tree_pre_pruning.fit(X_train, y_train, X_val, y_val)
print('預剪枝：', np.mean(tree_pre_pruning.predict(X_test) == y_test))
# treePlottter.create_plot(tree_pre_pruning.tree_)
# 後剪枝
tree_post_pruning = treeCreater.DecisionTree('gini', 'post_pruning')
tree_post_pruning.fit(X_train, y_train, X_val, y_val)
print('後剪枝：', np.mean(tree_post_pruning.predict(X_test) == y_test))
# treePlottter.create_plot(tree_post_pruning.tree_) 4.7 圖 4.2 是一個遞歸算法，若面臨巨量資料，則決策樹的層數會很深，使用遞歸方法易導緻"棧"溢出。試使用"隊列"資料結構，以參數MaxDepth 控制樹的最大深度，寫出與圖 4.2 等價、但不使用遞歸的決策樹生成算法.
主要思路每一次循環周遊一層下節點(除去葉節點)，為每一個節點生成子節點，将非葉節點入隊；用參數L儲存每一層有多少個節點。下一次循環執行同樣的步驟。直至所有的節點都葉節點，此時隊列為空。具體如下：
輸入：訓練集D = {(x1, y1), (x2, y2)...(xm, ym)};
屬性集A = {a1, a2... ad};
最大深度MaxDepth = maxDepth
過程：函數TreeDenerate(D, A, maxDepth)
生成三個隊列，NodeQueue、DataQueue、AQueue分别儲存節點、資料、和剩餘屬性集;
2生成節點Node_root;
3: if A為空 OR D上樣本都為同一類别:
4: 将Node_root标記為葉節點，其标記類别為D中樣本最多的類;
5: return Node_root;
6: end if
7: 将Node入隊NodeQueue; 将D入隊 DataQueue; 将A入隊AQueue;
8: 初始化深度depth=0;
9: 初始化L = 1; # L用于記錄每一層有多少非葉節點。
10: while NodeQueue 非空:
11: L* = 0
12: for _ in range(L): # 周遊目前L個非葉節點
13: NodeQueue 出隊Node; DataQueue出隊D; AQueue 出隊A;
14: 從A中選擇一個最優劃分屬性a*;
15: for a* 的每一個值 a*v do:
16: 建立一個node*，并将node*連接配接為Node的一個分支;
17: 令 Dv表示為D中在a*上取值為a*v的樣本子集;
18: if Dv為空:
19: 将node*标記為葉節點，其标記類别為D中樣本最多的類;
20: continue;
21: end if
22: if A\{a*}為空 OR Dv上樣本都為同一類别 OR depth == maxDepth:
23: 将node*标記為葉節點，其标記類别為Dv中樣本最多的類;
24: continue;
25: end if
26: 将node*入隊NodeQueue; 将Dv入隊 DataQueue; 将A\{a*} 入隊AQueue;
27: L* += 1; # 用于計算在第depth+1 層有多少個非葉節點
28: L = L*;
29: depth += 1;
30: return Node_root;
輸入以Node_root為根節點的一顆決策樹 4.8 試将決策樹生成的深度優先搜尋過程修改為廣度優先搜尋，以參數MaxNode控制樹的最大結點數，将題 4.7 中基于隊列的決策樹算法進行改寫。對比題 4.7 中的算法，試析哪種方式更易于控制決策樹所需存儲不超出記憶體。
4.7寫的算法就是廣度優先搜尋的。這道題将MaxNode改為MaxDepth，隻需要改幾個地方。有一點需要注意的地方，就是在給一個節點生成子節點時（19-32行），可能造成節點數大于最大值的情況，比如某屬性下有3種取值，那麼至少要生成3個葉節點，這個時候節點總數可能會超過最大值，這時最終節點數可能會是MaxNode+2。
至于兩種算法對比。個人了解當資料特征值，各屬性的取值較多時，形成的決策樹會趨于較寬類型的樹，這時使用廣度優先搜尋更容易控制記憶體。若屬性取值較少時，深度優先搜尋更容易控制記憶體。
對4.7中修改如下：
輸入：訓練集D = {(x1, y1), (x2, y2)...(xm, ym)};
屬性集A = {a1, a2... ad};
最大深度MaxNode = maxNode
過程：函數TreeDenerate(D, A, maxNode)
1: 生成三個隊列，NodeQueue、DataQueue、AQueue分别儲存節點、資料、和剩餘屬性集;
2: 生成節點Node_root;
3: if A為空 OR D上樣本都為同一類别:
4: 将Node_root标記為葉節點，其标記類别為D中樣本最多的類;
5: return Node_root;
6: end if
7: 将Node入隊NodeQueue; 将D入隊 DataQueue; 将A入隊AQueue;
8: 初始化深度numNode=1;
9: 初始化L = 1; # L用于記錄每一層有多少非葉節點。
10: while NodeQueue 非空:
11: L* = 0
12: for _ in range(L): # 周遊目前L個非葉節點
13: NodeQueue 出隊Node; DataQueue出隊D; AQueue 出隊A;
14: if numNode >= maxNode:
15: 将Node标記為葉節點，其标記類别為D中樣本最多的類;
16: continue;
17: end if;
18: 從A中選擇一個最優劃分屬性a*;
19: for a* 的每一個值 a*v do:
20: numNode+=1
21: 生成一個node*，并将node*連接配接為Node的一個分支;
22: 令 Dv表示為D中在a*上取值為a*v的樣本子集;
23: if Dv為空:
24: 将node*标記為葉節點，其标記類别為D中樣本最多的類;
25: continue;
26: end if
27: if A\{a*}為空 OR Dv上樣本都為同一類别:
28: 将node*标記為葉節點，其标記類别為Dv中樣本最多的類;
29: continue;
30: end if
31: 将node*入隊NodeQueue; 将Dv入隊 DataQueue; 将A\{a*} 入隊AQueue;
32: L* += 1; # 用于計算在第depth+1 層有多少個非葉節點
33: end if;
34: L = L*;
35: return Node_root; 4.10 從網上下載下傳或自己程式設計實作任意一種多變量決策樹算法，并觀察其在西瓜資料集 3.0 上産生的結果
待補充。