關注公眾號：
用Python學機器學習
，獲取更多更新。
樹模型是機器學習中比較基礎同時應用很廣泛的一大類模型，不僅包括單一的決策樹模型，而且還有整合演算法如隨機森林等等，甚至時下比較流行的xgboost模型也是主要以樹模型為基礎評估器的。接下來的幾篇文章，我們陸續推送樹模型相關演算法，除了介紹樹模型的理論之外，我們將重點放在如何透過numpy庫來實現相關的演算法，在每篇文章的結束，我們都會編寫出我們自己的演算法實現程式。本文主要介紹樹模型中的分類樹——ID3演算法。
分類樹主要用來解決分類問題，本質上是基於特徵變數對資料進行分類。你可以認為它是if-then規則的集合，也可以認為是定義特徵變數空間與因變數空間的條件機率分佈。這樣的描述可能比較抽象，我們舉一個不太恰當的例子。比如要判斷一個人是男性還是女性，我們需要基於這個人的特徵去判斷，這些特徵可以有頭髮、喉結、胸圍等。首先我們可能先看這個人喉結是否突出，我們可能認為喉結沒有突出的是女性，喉結突出的個體中我們再根據頭髮長短進行判斷，頭髮長的為女性，頭髮短的為男性。
上面的例子已經道出了決策樹演算法的基本思想和流程：1）特徵選擇。所謂特徵選擇就是在一堆特徵變數中依次選出對分類最有用的變數，例如說為什麼上面例子中是先用喉結判斷，後用頭髮判斷，而不是相反，這裡面一定有相關演算法；2）決策樹生成。選擇好特徵變數之後，就可以建立一套if-then規則集，用圖形來呈現就是表現為一棵樹，建好樹之後，我們就可以用這棵樹對未知資料的類別進行判斷；3）決策樹剪枝。我們建立的樹可能過於龐大，增大了誤判的機率，需要進行修剪。例如上面例子中喉結突出的個體，我們可能直接就可以判斷為男性，而不必再用頭髮長短來判斷，因為從生理上看，主要還是男性的喉結才會突出。
ID3決策樹因為提出較早，並沒有完備的決策樹剪枝策略，所以這篇文章我們先不進行進行介紹，有關決策樹剪枝相關演算法我們會在下一篇介紹C4。5演算法時再進行闡述。接下來的介紹從特徵選擇，決策樹生成、預測三部分來展開。
特徵選擇
特徵是機器學習中自變數的別名。特徵選擇就是在一系列自變數中選擇出對分類最有用的變數。分類樹中ID3演算法使用資訊增益進行特徵選擇，想要理解資訊增益，需要先理解一些概念。
資訊量
在資訊理論中，資訊是可以量化的，這個量化指標被稱為資訊量。一個隨機事件的資訊量被定義為機率的負對數，或者說是機率倒數的對數：
例如，明天下雨的機率是0。5，那麼這句話的資訊量就是1。從公式上看，機率越大的事情，資訊量越小，反之，機率越小的事情，資訊量越大。這是符合我們直覺的。
熵entropy
資訊量測量的是一個隨機事件包含的資訊大小。實際上我們更想知道一次隨機試驗的資訊量，這用熵來定義：
這裡的H（X）表示的就是隨機變數X的熵，也就是說，如果一個隨機試驗有k種可能的取值，這個隨機試驗的熵就等於k個隨機事件資訊量的數學期望。由於機率通常用樣本的頻率來估計，實際上計算的熵通常被稱為經驗熵。
還可以從另一個角度來理解熵，熵描述了隨機變數的純度或不確定性。試想一枚硬幣在打造時質地不夠均勻，在一次拋硬幣的隨機試驗中出現正面向上的機率為0。99，反面向上的機率為0。01。那麼我們隨便擲一次硬幣，會出現怎樣的結果，其不確定性是很低的（99%的機率是出現正面），等價說法是純度很高或資訊量很低（因為我們幾乎可以認為一次試驗肯定出現正面）。相反，如果硬幣的質地均勻，正反面出現的機率都是0。5，那麼一次拋硬幣試驗結果的不確定性就變很高，或者說純度很低或資訊量很大。
def entropy（x）： “”“ 計算經驗熵，熵被定義為資訊量的加權平均，權重為機率。 ：param x：numpy陣列 ：return： 經驗熵，一個標量 ”“” # 將ndarray陣列轉化為列表 x = list（x） # 估計x的機率分佈 x_p = np。array（［x。count（i）/len（x） for i in set（x）］） # 計算熵 return -np。sum（［p*np。log2（p） for p in x_p］）
條件熵
分類樹中，相較於熵，我們更感興趣的是條件熵，也就是在已知某個隨機變數的前提下，計算另一個隨機變數的熵：
很顯然，條件熵評估了一個隨機變數X對另一個隨機變數Y資訊量的影響程度。
def con_entropy（x，y）： “”“ 計算條件熵 ：param x： 一維陣列 ：param y： 一維陣列 ：return： 返回x條件下y的熵 ”“” # 取出x中的不重複值 x_uni = np。unique（x） # 取出不同的x中的所有y熵來計算條件熵 con_ent = 0 for i in x_uni： y_new = y［x == i］ y_ent = entropy（y_new） con_ent += len（y_new）*y_ent/len（x） return con_ent
ID3演算法正是藉助熵和條件熵來計算資訊增益，接下來我們介紹資訊增益。
ID3演算法特徵選擇標準——資訊增益
資訊增益的定義很簡單，也很直觀：
很顯然，資訊增益衡量了已知隨機變數X後，隨機變數Y的資訊量減少的程度，減少的越多，說明了在對Y分類過程中，隨機變數X提供了越多的資訊，我們就應該選擇這個變數。
def info_gain（x，y）： “”“ 計算資訊增益，ID3演算法使用 ：param x： 一個一維列表或陣列 ：param y： 一個一維列表或陣列 ：return： 返回資訊增益 ”“” return entropy（y）-con_entropy（x，y）
決策樹生成
決策樹的生成就是一個重複地呼叫特徵選擇的過程。在ID3演算法中，我們首先遍歷所有特徵變數，計算每個特徵變數的資訊增益，將資訊增益最大的特徵變數作為樹模型的根節點，根據根節點特徵變數的不同取值，發出樹枝，對於每條樹枝所包含的樣本再次呼叫特徵選擇過程，選擇出最佳特徵建立子節點，重複上述過程一直到：當前節點包含的所有樣本都屬於同一個類別（無需分類），或者已經沒有特徵變數可供使用，或者當前樣本中每一個特徵變數的取值都相同（無法分類）。
根據上面的思想，用程式設計來實現其實就是一個遞迴呼叫的問題。接下來，我們用numpy來實現這一遞迴演算法。
用python來程式設計，最主要就是設計類。初步考慮，我們的程式中應該至少包括兩個類，一個類用來描述樹的結構，即樹有哪些節點，以及每個節點所包含的資訊。特別的，我們需要知道每個節點尤其是葉子節點樣本中因變數的機率分佈，我們還需要知道每個節點有哪些子節點。只有知道了這些資訊，我們才能對未知資料進行分類。
class Nodes（object）： def __init__（self ，n_sample=None ，entro=None ，children_nodes=None ，best_feature=None ，class_prob=None）： “”“ 儲存節點的資訊，包括當前節點的樣本量，標籤的經驗熵，最佳分割特徵，子節點等。 Parameters —————— n_sample ： 當前節點樣本量。 entro ： 當前節點因變數的熵 children_nodes ： 當前節點的子節點 best_feature ： 當前節點使用的特徵索引 class_prob ： 當前節點因變數的機率分佈 Returns ————- None。 ”“” self。n_sample = n_sample self。entro = entro self。children_nodes = children_nodes self。best_feature = best_feature self。class_prob = class_prob
另一個類就是模型類了，參考sklearn的思想，我們可以設計一個fit方法來擬合模型，fit方法內部可以遞迴呼叫特徵選擇過程來建樹：
class DTClassifier（object）： def __init__（self， criterion=‘c4。5’）： self。criterion = criterion if self。criterion == ‘c4。5’： self。func = info_gain_rate elif self。criterion == ‘id3’： self。func = info_gain else： raise ValueError def fit（self，X，y）： # 首先例項化建立一個根節點物件 self。root_node = Nodes（） self。__plant_tree（X，y，self。root_node） def __plant_tree（self，X，y，node）： rows，cols = X。shape # 記錄當前節點樣本量 node。n_sample = rows # 記錄當前節點標籤的熵 node。entro = entropy（y） # 記錄當前節點標籤的機率分佈 node。class_prob = {i： list（y）。count（i）/len（y） for i in np。unique（y）} # 如果當前節點中所有樣本屬於同一個類別，就跳出遞迴過程 if len（np。unique（y））==1： return # 如果當前節點中每一個特徵中取值都相同，就跳出遞迴過程 if np。sum（［len（np。unique（x［：，i］）） for i in range（cols）］）==cols： return # 迴圈特徵，找出最佳特徵 best_index = None best_gain = 0 for col_i in range（cols）： curr_gain = self。func（X［：，col_i］， y） if curr_gain ！= None and curr_gain > best_gain： best_gain = curr_gain best_index = col_i # 記錄最佳特徵的索引 node。best_feature = best_index # 記錄當前節點的子節點，是一個字典物件，字典的key是當前節點的不同取值，value是一個節點物件 node。children_nodes = {} # 選擇資訊增益或資訊增益率最大的特徵，用來生成子節點 x_best = X［：，best_index］ x_best_uni = np。unique（x_best） # 將樣本拆分到每個子節點中，並在子節點中遞迴建樹 for i in x_best_uni： x_new = X［x_best==i］ y_new = y［x_best==i］ node。children_nodes［i］ = Nodes（） self。__plant_tree（x_new，y_new，node。children_nodes［i］）
預測
建好決策樹模型後，就可以用這個決策樹模型對未知分類的樣本進行預測了。預測的方法很簡單，就是遍歷模型根節點屬性，一直到葉子節點，然後基於葉子結點中標籤或者因變數的機率分佈得到當前樣本屬於各類的機率，將當前樣本歸於機率最大的類別。這裡我們設計兩個函式，函式
pred_prob
可以返回樣本屬於各個類的機率，方法
pred
返回樣本屬於哪個類別。
class DTClassifier（object）： def __init__（self， criterion=‘c4。5’）： self。criterion = criterion if self。criterion == ‘c4。5’： self。func = info_gain_rate elif self。criterion == ‘id3’： self。func = info_gain else： raise ValueError def fit（self，X，y）： # 首先例項化建立一個根節點物件 self。root_node = Nodes（） self。__plant_tree（X，y，self。root_node） def __plant_tree（self，X，y，node）： rows，cols = X。shape # 記錄當前節點樣本量 node。n_sample = rows # 記錄當前節點標籤的熵 node。entro = entropy（y） # 記錄當前節點標籤的機率分佈 node。class_prob = {i： list（y）。count（i）/len（y） for i in np。unique（y）} # 如果當前節點中所有樣本屬於同一個類別，就跳出遞迴過程 if len（np。unique（y））==1： return # 如果當前節點中每一個特徵中取值都相同，就跳出遞迴過程 if np。sum（［len（np。unique（x［：，i］）） for i in range（cols）］）==cols： return # 迴圈特徵，找出最佳特徵 best_index = None best_gain = 0 for col_i in range（cols）： curr_gain = self。func（X［：，col_i］， y） if curr_gain ！= None and curr_gain > best_gain： best_gain = curr_gain best_index = col_i # 記錄最佳特徵的索引 node。best_feature = best_index # 記錄當前節點的子節點，是一個字典物件，字典的key是當前節點的不同取值，value是一個節點物件 node。children_nodes = {} # 選擇資訊增益或資訊增益率最大的特徵，用來生成子節點 x_best = X［：，best_index］ x_best_uni = np。unique（x_best） # 將樣本拆分到每個子節點中，並在子節點中遞迴建樹 for i in x_best_uni： x_new = X［x_best==i］ y_new = y［x_best==i］ node。children_nodes［i］ = Nodes（） self。__plant_tree（x_new，y_new，node。children_nodes［i］） def predict（self，x）： results = self。predict_prob（x） pred = ［］ for i in range（len（results））： p = max（results［i］，key=lambda k ： results［i］［k］） pred。append（p） return pred def predict_prob（self，x）： # 獲取輸入資料的行數目 rows = x。shape［0］ # 定義一個列表，用來儲存結果 results = ［］ # 遍歷每一行資料，檢索葉子節點，拿到葉子結點中標籤的機率分佈。 for i in range（rows）： result = self。__search_leaf_node（x［i］，self。root_node） results。append（result） return results def __search_leaf_node（self，x，node）： # 如果輸入節點的子節點為None，說明當前節點為葉子節點，那麼就從葉子節點中拿到標籤的機率分佈，這裡定義為一個字典。 if node。children_nodes is None： result = {i：node。class_prob。get（i，0） for i in self。root_node。class_prob。keys（）} return result # 如果輸入的節點的子節點不為None，說明有子節點，當前節點還不是葉子結點。 else： # 那麼就進入當前節點的子節點 curr_node = node。children_nodes［x［node。best_feature］］ # 遞迴，直到找到葉子結點 return self。__search_leaf_node（x， curr_node）
接下來，我們使用周志華《機器學習》76頁的西瓜資料集為例，驗證一下上面的id3演算法。首先先擬合模型：
# 建立資料集>>>x = np。array（［［‘青綠’， ‘蜷縮’， ‘濁響’， ‘清晰’， ‘凹陷’， ‘硬滑’］， ［‘烏黑’， ‘蜷縮’， ‘沉悶’， ‘清晰’， ‘凹陷’， ‘硬滑’］， ［‘烏黑’， ‘蜷縮’， ‘濁響’， ‘清晰’， ‘凹陷’， ‘硬滑’］， ［‘青綠’， ‘蜷縮’， ‘沉悶’， ‘清晰’， ‘凹陷’， ‘硬滑’］， ［‘淺白’， ‘蜷縮’， ‘濁響’， ‘清晰’， ‘凹陷’， ‘硬滑’］， ［‘青綠’， ‘稍蜷’， ‘濁響’， ‘清晰’， ‘稍凹’， ‘軟沾’］， ［‘烏黑’， ‘稍蜷’， ‘濁響’， ‘稍糊’， ‘稍凹’， ‘軟沾’］， ［‘烏黑’， ‘稍蜷’， ‘濁響’， ‘清晰’， ‘稍凹’， ‘硬滑’］， ［‘烏黑’， ‘稍蜷’， ‘沉悶’， ‘稍糊’， ‘稍凹’， ‘硬滑’］， ［‘青綠’， ‘硬挺’， ‘清脆’， ‘清晰’， ‘平坦’， ‘軟沾’］， ［‘淺白’， ‘硬挺’， ‘清脆’， ‘模糊’， ‘平坦’， ‘硬滑’］， ［‘淺白’， ‘蜷縮’， ‘濁響’， ‘模糊’， ‘平坦’， ‘軟沾’］， ［‘青綠’， ‘稍蜷’， ‘濁響’， ‘稍糊’， ‘凹陷’， ‘硬滑’］， ［‘淺白’， ‘稍蜷’， ‘沉悶’， ‘稍糊’， ‘凹陷’， ‘硬滑’］， ［‘烏黑’， ‘稍蜷’， ‘濁響’， ‘清晰’， ‘稍凹’， ‘軟沾’］， ［‘淺白’， ‘蜷縮’， ‘濁響’， ‘模糊’， ‘平坦’， ‘硬滑’］， ［‘青綠’， ‘蜷縮’， ‘沉悶’， ‘稍糊’， ‘稍凹’， ‘硬滑’］］）>>>y = np。array（［‘是’，‘是’，‘是’，‘是’，‘是’，‘是’，‘是’，‘是’，‘否’，‘否’，‘否’，‘否’，‘否’，‘否’，‘否’，‘否’，‘否’］）>>>dt = DTClassifier（criterion=‘id3’）>>>dt。fit（x， y）# 根節點是按照文理進行劃分的>>>dt。root_node。children_nodes{‘模糊’： <__main__。Nodes at 0x20bb11ad820>， ‘清晰’： <__main__。Nodes at 0x20bb11addc0>， ‘稍糊’： <__main__。Nodes at 0x20bb11ad940>}# 稍糊子節點的子節點為空，說明已經是葉子節點了>>>dt。root_node。children_nodes［‘模糊’］。children_nodes# 稍糊子節點又按照觸感進行劃分>>>dt。root_node。children_nodes［‘稍糊’］。children_nodes{‘硬滑’： <__main__。Nodes at 0x20bb11adf70>， ‘軟沾’： <__main__。Nodes at 0x20bb11adeb0>}# 清晰子節點又按照根蒂進行劃分>>>dt。root_node。children_nodes［‘清晰’］。children_nodes{‘硬挺’： <__main__。Nodes at 0x20bb117fdf0>， ‘稍蜷’： <__main__。Nodes at 0x20bb117f490>， ‘蜷縮’： <__main__。Nodes at 0x20bb117fe20>}# 稍蜷子節點劃分出兩個分支，一個是烏黑，一個是青綠，書中此處似乎有誤>>>dt。root_node。children_nodes［‘清晰’］。children_nodes［‘稍蜷’］。children_nodes{‘烏黑’： <__main__。Nodes at 0x20bb117f310>， ‘青綠’： <__main__。Nodes at 0x20bb117faf0>}>>>dt。root_node。n_sample17>>>dt。root_node。class_prob{‘否’： 0。5294117647058824， ‘是’： 0。47058823529411764}
然後我們輸入兩條資料來預測一下類別：
>>>x1 = np。array（［［‘青綠’，‘蜷縮’，‘濁響’，‘清晰’，‘凹陷’，‘硬滑’］， ［‘烏黑’，‘稍蜷’，‘濁響’，‘清晰’，‘凹陷’，‘軟沾’］］）>>>prob = dt。predict_prob（x1）>>>prob［{‘否’： 0， ‘是’： 1。0}， {‘否’： 1。0， ‘是’： 0}］>>>class_ = dt。predict（x1）>>>class_［‘是’， ‘否’］
兩個樣本中，一個被預測為好瓜，一個為壞瓜。
