下題來源于筆者學校的《模式識別與機器學習》課程的作業題，本文將通過使用NumPy處理數學運算，Pandas處理數據集，Graphviz實現決策樹可視化等Python庫來實現決策樹算法及其格式化。

導入用到的Python庫：

import numpy as np
import pandas as pd
from graphviz import Digraph

將數據集整理為DataFrame對象。數據集中除“好瓜”一欄表示類別外，其他欄均為屬性和屬性值：

data = pd.DataFrame({
"好瓜" : ['是', '是', '是', '是', '是', '是', '是', '是', '否', '否', '否', '否', '否', '否', '否', '否', '否'], 
"色澤" : ['青綠', '烏黑', '烏黑', '青綠', '淺白', '青綠', '烏黑', '烏黑', '烏黑', '青綠', '淺白', '淺白', '青綠', '淺白', '烏黑', '淺白', '青綠'], 
"根蒂" : ['蜷縮', '蜷縮', '蜷縮', '蜷縮', '蜷縮', '稍蜷', '稍蜷', '稍蜷', '稍蜷', '硬挺', '硬挺', '蜷縮', '稍蜷', '稍蜷', '稍蜷', '蜷縮', '蜷縮'], 
"敲聲" : ['濁響', '沉悶', '濁響', '沉悶', '濁響', '濁響', '濁響', '濁響', '沉悶', '清脆', '清脆', '濁響', '濁響', '沉悶', '濁響', '濁響', '沉悶'], 
"紋理" : ['清晰', '清晰', '清晰', '清晰', '清晰', '清晰', '稍糊', '清晰', '稍糊', '清晰', '模糊', '模糊', '稍糊', '稍糊', '清晰', '模糊', '稍糊'], 
"觸感" : ['硬滑', '硬滑', '硬滑', '硬滑', '硬滑', '軟粘', '軟粘', '硬滑', '硬滑', '軟粘', '硬滑', '軟粘', '硬滑', '硬滑', '軟粘', '硬滑', '硬滑'], 
"含糖量" : [0.46, 0.376, 0.264, 0.318, 0.215, 0.237, 0.149, 0.211, 0.091, 0.267, 0.057, 0.099, 0.161, 0.198, 0.37, 0.042, 0.103]
})

創建節點類和邊類：

class Node:def __init__(self, feature = None, cls = None, data = None):self.feature = feature #若為非葉節點，使用self.feature存儲該節點的分類屬性self.cls = cls #若為葉節點，使用self.cls存儲該節點的分類結果self.data = data #儲存分至該節點的樣本class edge:def __init__(self, start = None, end = None):self.start = start #父節點self.end = end #子節點

使用全局變量列表和字典分別存儲決策樹的各節點和邊，其中邊的存儲格式為edge_dict[邊的屬性值]=邊 。

由于數據集中含有屬性值為連續值的屬性，需使用二分法來處理。使用全局變量best_mid_point 來存儲最佳二分點：

node_list = []
edge_dict = {} #屬性值作為有向邊字典的索引
best_mid_point = 0

決策樹學習基本算法如下圖所示：

筆者使用信息增益作為劃分標準，將其應用至決策樹學習基本算法中，計算各屬性的信息增益，取信息增益最大者為最優劃分屬性。

根據屬性對數據集劃分后的信息增益的定義如下：

其中，表示經驗熵：

表示