作者 |?我是韓小琦

鏈接 |?https://zhuanlan.zhihu.com/p/44666694

4.1 試證明對于不含沖突數據(即特征向量完全相同但標記不同)的訓練集，必存在與訓練集一致(即訓練誤差為 0) 的決策樹。

答：

從原書p74的圖4.2的決策樹學習的基本算法可以看出，生成一個葉節點有三種情況：

1、節點下樣本??全屬于同一類樣本??，則將當前節點作為??類葉節點。

2、屬性集??，或者樣本在當前屬性集上取值相同。即特征用完了（當只剩最后一個特征時，進一步分裂，只能將各取值設立葉節點，標記為樣本最多的類別。），或者的樣本在??上取值都相同（感覺這里貌似和第 一條重復了）。這時取??中最多的類作為此節點的類別標記。

3、在某一節點上的屬性值??，樣本為空，即沒有樣本在屬性??上取值為??。同樣取??中最多的類作為此節點的類別標記。

在這道題中，目標是找出和訓練集一致的決策樹，所以不必考慮第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.py

import pandas as pd import numpy as npdef 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_valuedown_part_train = X_train.loc[:, tree_.feature_name] < tree_.split_valueup_part_val = X_val.loc[:, tree_.feature_name] >= tree_.split_valuedown_part_val = X_val.loc[:, tree_.feature_name] < tree_.split_valueup_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_subtreedown_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_subtreetree_.high = max(up_subtree.high, down_subtree.high) + 1tree_.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 = -1tree_.leaf_num = 0is_all_leaf = True # 判斷當前節點下，所有子樹是否都為葉節點for key in tree_.subtree.keys():this_part_train = X_train.loc[:, tree_.feature_name] == keythis_part_val = X_val.loc[:, tree_.feature_name] == keytree_.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].hightree_.leaf_num += tree_.subtree[key].leaf_numif not tree_.subtree[key].is_leaf:is_all_leaf = Falsetree_.high = max_high + 1if 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_valuedown_part_train = X_train.loc[:, tree_.feature_name] < tree_.split_valueup_part_val = X_val.loc[:, tree_.feature_name] >= tree_.split_valuedown_part_val = X_val.loc[:, tree_.feature_name] < tree_.split_valueup_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_subtreedown_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_subtreetree_.high = max(up_subtree.high, down_subtree.high) + 1tree_.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 = -1tree_.leaf_num = 0for key in tree_.subtree.keys():this_part_train = X_train.loc[:, tree_.feature_name] == keythis_part_val = X_val.loc[:, tree_.feature_name] == keytree_.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].hightree_.leaf_num += tree_.subtree[key].leaf_numtree_.high = max_high + 1return tree_def set_leaf(leaf_class, tree_):# 設置節點為葉節點tree_.is_leaf = True # 若劃分前正確率大于劃分后正確率。則選擇不劃分，將當前節點設置為葉節點tree_.leaf_class = leaf_classtree_.feature_name = Nonetree_.feature_index = Nonetree_.subtree = {}tree_.impurity = Nonetree_.split_value = Nonetree_.high = 0 # 重新設立高 和葉節點數量tree_.leaf_num = 1def 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_trainval_split = feature_valmajority_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] # 返回準確率

treeCreate.py 和 treePlotter.py 見上面鏈接。

生成決策樹如下：

4.4 試編程實現基于基尼指數進行劃分選擇的決策樹算法，為表 4.2 中數據生成預剪枝、后剪枝決策樹并與未剪枝決策樹進行比較.

答：

https://github.com/han1057578619/MachineLearning_Zhouzhihua_ProblemSets/tree/master/ch4--%E5%86%B3%E7%AD%96%E6%A0%91/4.3-4.4

未剪枝、后剪枝、預剪枝生成決策樹分別如下，總體來說后剪枝會相比于預剪枝保留更多的分支。

有兩個需要注意的地方。一個是在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 treePlottteriris = 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.9 試將 4.4.2 節對缺失值的處理機制推廣到基尼指數的計算中去.

答：

這道題相對簡單。使用書中式4.9、4.10、4.11有，對于原書中4.5式可以推廣為：

?

屬性a的基尼指數可推廣為：

4.10 從網上下載或自己編程實現任意一種多變量決策樹算法，并觀察其在西瓜數據集 3.0 上產生的結果

答：

待補充。

---

推薦閱讀

（點擊標題可跳轉閱讀）

干貨 | 公眾號歷史文章精選

我的深度學習入門路線

我的機器學習入門路線圖

重磅！

AI有道年度技術文章電子版PDF來啦！

掃描下方二維碼，添加?AI有道小助手微信，可申請入群，并獲得2020完整技術文章合集PDF（一定要備注：入群?+ 地點 + 學校/公司。例如：入群+上海+復旦。?

長按掃碼，申請入群

（添加人數較多，請耐心等待）

?

最新 AI 干貨，我在看?

總結

以上是生活随笔為你收集整理的周志华《机器学习》课后习题解析（第四章）：决策树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。