關注公眾號：
用Python學機器學習
，更多更新等著您。
上一篇文章，我們已經介紹了決策樹的ID3演算法，並編寫了一個實現決策樹ID3演算法的程式。實際中，ID3演算法應用並不多，C4。5才是應用較多的分類樹演算法。究其原因在於ID3演算法存在以下幾個缺點：1）傾向於選擇類別較多的特徵變數作為分割屬性；2）無法處理連續變數；3）無法處理缺失值；4）沒有完備的剪枝策略。C4。5演算法在這四個方面做出了改進，這篇文章我們就來學習一下。關於剪枝策略，我們留到下一篇文章來介紹，這篇文章我們主要介紹C4。5對前三個問題的改進。
資訊增益的改進
ID3演算法使用資訊增益進行特徵選擇，這導致演算法傾向於選擇類別較多的特徵變數作為分割屬性。針對這一缺點，C4。5演算法提出一種新的特徵選擇演算法——資訊增益率。資訊增益率的定義如下：
其中
IV被稱為特徵的固有值，其實就是特徵的熵，資訊增益率可以簡單的理解為資訊增益除以特徵的熵。也就是評估特徵的單位熵帶來的資訊增益的變化。程式設計如下：
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］）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_entdef info_gain（x，y）： “”“ 計算資訊增益，ID3演算法使用 ：param x： 一個一維列表或陣列 ：param y： 一個一維列表或陣列 ：return： 返回資訊增益 ”“” return entropy（y）-con_entropy（x，y）def info_gain_rate（x，y）： “”“ 計算資訊增益率，C4。5演算法使用 ：param x： 一個一維列表或陣列 ：param y： 一個一維列表或陣列 ：return： 返回資訊增益率 ”“” if entropy（x） ！= 0： return info_gain（x，y）/entropy（x） else： return 0
處理連續變數
對於連續變數，C4。5演算法提出使用二分法進行解決。其基本思想為，首先取出連續特徵中的不重複值，並按照升序進行排列。在排序後的資料中取相鄰資料點的中點（平均數）作為該連續特徵的分割點，這樣可以將樣本分為兩個類別。遍歷所有中點，並計算以該中點為分割點時的資訊增益，取資訊增益最大的中點作為分割點對連續特徵進行劃分。程式設計如下：
def bin（x，y）： “”“ 連續變數離散化 ：param x： x為一維陣列 ：return： 返回與x等長度的分箱結果 ”“” # 拿到一維陣列中不重複值 x_uni = np。unique（x） # 獲取分割點 x_split = （x_uni［0：-1］+x_uni［1：］）/2 best_gain = 0 best_split = 0 # 遍歷分割點，計算資訊增益 for i in x_split： x_i = np。zeros_like（x） print（i） x_i［x>i］ = 1 x_i［x 處理缺失值 關於如何處理缺失值，其實需要面對兩個問題： 如何計算資訊增益或資訊增益率？前面在介紹計算資訊增益或資訊增益率時，是基於樣本無缺失值的情況的，如果樣本有缺失值，是否需要將缺失值考慮在內呢？ 缺失樣本應該劃分到哪個子節點？例如上一篇文章我們的例子中，在判斷一個人的性別時，我們首先選擇的是喉結，根據喉結劃分兩個子節點，即有喉結和無喉結。如果當前一個樣本的在喉結這個變數上為缺失值時，究竟應該將其劃分到有喉結的分支還是無喉結的分支呢？ 對於第一個問題，C4。5演算法的處理思路很簡單，演算法首先會給每一個樣本賦予一個權重 ，初始權重通常為1。然後會計算出當前特徵上，無缺失值樣本所佔的比例，令為ρ。 這裡的 表示的是無缺失值樣本集合， 表示的是全樣本集合。很顯然公式計算的是無缺失樣本集合中樣本權重求和除以全樣本集中樣本權重的求和。 緊接著，演算法會計算無缺失值樣本的資訊增益： 這裡我們參照周志華《機器學習》對公式做統一的說明。 計算的是特徵變數a在無缺失值樣本 上的資訊增益， 表示的是無缺失值樣本 上計算的資訊熵，我們假定特徵變數a有1，2。。。，v，。。。V個類別， 表示的是在無缺失值樣本中第v個類別的資訊熵，而第v個類別的機率分佈計算如下： 這表明第v個類別的機率分佈等於第v個類別中所有樣本的樣本權重求和，然後除以無缺失值樣本中所有樣本的樣本權重求和。 資訊熵的計算公式也發生了變化： 這裡我們其實假定了因變數或者說標籤的類別有1，2，。。。k，。。。y個類別。這裡 的為： 因變數的機率分佈同樣也發生了變化，上一篇文章中機率使用頻率來估計的，現在是用樣本權重來估計的。計算好了上面的結果後，就可以計算全樣本的資訊增益了： 這就是C4。5在計算資訊增益上給出的解決方案。簡單的說，有兩點變化，第一點就是全樣本的資訊增益等於無缺失值樣本的比例乘以用無缺失值樣本計算的資訊增益，第二點是機率的計算發生了變化，這導致在計算資訊熵、條件熵以及資訊增益上都發生了變化，新的演算法中機率是使用樣本權重來估計的，而不是樣本頻率。與資訊增益相同，計算資訊增益率時同樣會乘以無缺失樣本的比例。接下來我們程式設計實現這一演算法： 首先我們先編寫計算熵的程式如下： def entropy（x，weight=None）： “”“ 計算經驗熵，熵被定義為資訊量的加權平均 Parameters —————— x ： 一維ndarray陣列 weight ： 樣本權重 Returns ————- 經驗熵 ”“” length = len（x） if weight is None： weight = np。array（［1。0］*length） # 計算權重和，後面用來的估計機率 weight_sum = np。sum（weight） # 計算機率分佈 x_p = ［np。sum（weight［np。where（x==i）］）/weight_sum for i in set（x）］ # 計算熵 return -np。sum（［p*np。log2（p） for p in x_p］） 然後再編寫計算條件熵的程式 def con_entropy（x，y，weight=None）： “”“ 計算條件熵 Parameters —————— x ： 一維ndarray陣列 y ： 一維ndarray陣列 weight ： 樣本權重 Returns ————- 條件經驗熵 ”“” length = len（y） if weight is None： weight = np。array（［1］*length） # 計算權重和，後面用來的估計機率 weight_sum = np。sum（weight） con_ent=0 # 迴圈x的每一個取值，計算y的熵 for x_i in np。unique（x）： # 拿到x_i對應的y y_new = y［x==x_i］ # 拿到x_i對應的樣本權重 weight_new = weight［x == x_i］ # 計算x_i的機率分佈 x_i_prob = np。sum（weight_new）/weight_sum # 計算x_i下y的條件熵 y_new_ent = entropy（y_new，weight_new） # 條件熵求和 con_ent += x_i_prob*y_new_ent return con_ent 然後是資訊增益： def info_gain（x，y，weight=None）： “”“ 計算資訊增益 Parameters —————— x ： 一維ndarray陣列 y ： 一維ndarray陣列 weight ： 樣本權重 Returns ————- 資訊增益 ”“” # 計算陣列的長度 length = len（y） # 如果未輸入權重，則權重為1 if weight is None： weight = np。array（［1］*length） # 計算資訊增益 return entropy（y）-con_entropy（x， y，weight） 資訊增益率 def info_gain_rate（x，y，weight=None）： “”“ Parameters —————— x ： 一維ndarray陣列 y ： 一維ndarray陣列 weight ： 樣本權重 Returns ————- 資訊增益率 ”“” length = len（y） if weight is None： weight = np。array（［1］*length） # 特徵的固有值可能為0，如果為0，我們令資訊增益率返回0 if entropy（x） ！= 0： return info_gain（x， y，weight）/entropy（x，weight） else： return 0 以上完成了特徵選擇演算法的程式設計實現，接下來我們解決第二個問題：缺失樣本應該劃分到哪個子節點？對於這個問題，C4。5演算法的做法是缺失樣本以不同的機率劃分到不同的子節點中，這裡的機率計算公式為。也就是說缺失樣本會劃分到所有的子節點中，只不過在不同子節點中有不同的權重。下面我們在上一節的基礎上程式設計來實現這一過程。這裡設計了兩個類： class Nodes（object）： def __init__（self ，n_sample=None ，entro=None ，children_nodes=None ，best_feature=None ，class_prob=None）： self。n_sample=n_sample self。entro=entro self。children_nodes=children_nodes self。best_feature=best_feature self。class_prob=class_prob 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，weight=None）： # 建立根節點物件 self。root_node = Nodes（） length = len（y） if weight is None： weight = np。array（［1。0］*length） # 開始種樹 self。__plant_tree（X，y，self。root_node，weight） def __plant_tree（self，X，y，node，weight=None）： # 記錄當前節點的行數目和列數目 rows，cols = X。shape weight_sum = np。sum（weight） # 記錄當前節點的樣本量 node。n_sample = rows # 記錄當前節點的熵 node。entro=entropy（y，weight） # 記錄當前節點標籤的機率分佈 node。class_prob={key： np。sum（weight［y==key］）/weight_sum for key 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_col = None best_gain = 0 for col in range（cols）： x_col = X［：，col］ # 特徵上無缺失值的索引 i_nonan = ~np。isnan（x_col） # 無缺失索引所佔的比例 nonan_prob = np。sum（weight［i_nonan］）/weight_sum curr_gain = self。func（x_col［i_nonan］，y［i_nonan］，weight［i_nonan］）*nonan_prob if curr_gain>best_gain： best_gain = curr_gain best_col = col # 記錄節點的最佳索引 node。best_feature=best_col # 記錄節點的子節點 node。children_nodes = {} # 拿到最佳分支特徵的資料 x_best = X［：，best_col］ # 最佳特徵上非缺失值的索引 nonan_i = ~np。isnan（x_best） # for i in np。unique（x_best［nonan_i］）： i_prob = np。sum（weight［x_best==i］）/np。sum（weight［nonan_i］） X_new = X［（x_best==i）+（~nonan_i）］ y_new = y［（x_best==i）+（~nonan_i）］ weight_new = weight［（x_best==i）+（~nonan_i）］ nan_new = np。isnan（X_new［：，best_col］） weight_new［nan_new］ = weight_new［nan_new］*i_prob node。children_nodes［i］ = Nodes（） self。__plant_tree（X_new， y_new， node。children_nodes［i］，weight_new） 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） 預測 以上，我們完成了C4。5演算法主要程式的設計（不包括剪枝策略），接下來，我們使用資料驗證一下模型。資料來源於周志華《機器學習》86頁，西瓜資料集2。0α。資料情況如下： >>>a = np。array（［［np。nan， ‘蜷縮’， ‘濁響’， ‘清晰’， ‘凹陷’， ‘硬滑’］， ［‘烏黑’， ‘蜷縮’， ‘沉悶’， ‘清晰’， ‘凹陷’， np。nan］， ［‘烏黑’， ‘蜷縮’， np。nan， ‘清晰’， ‘凹陷’， ‘硬滑’］， ［‘青綠’， ‘蜷縮’， ‘沉悶’， ‘清晰’， ‘凹陷’， ‘硬滑’］， ［np。nan， ‘蜷縮’， ‘濁響’， ‘清晰’， ‘凹陷’， ‘硬滑’］， ［‘青綠’， ‘稍蜷’， ‘濁響’， ‘清晰’， np。nan， ‘軟沾’］， ［‘烏黑’， ‘稍蜷’， ‘濁響’， ‘稍糊’， ‘稍凹’， ‘軟沾’］， ［‘烏黑’， ‘稍蜷’， ‘濁響’， np。nan， ‘稍凹’， ‘硬滑’］， ［‘烏黑’， np。nan， ‘沉悶’， ‘稍糊’， ‘稍凹’， ‘硬滑’］， ［‘青綠’， ‘硬挺’， ‘清脆’， np。nan， ‘平坦’， ‘軟沾’］， ［‘淺白’， ‘硬挺’， ‘清脆’， ‘模糊’， ‘平坦’， np。nan］， ［‘淺白’， ‘蜷縮’， np。nan， ‘模糊’， ‘平坦’， ‘軟沾’］， ［np。nan， ‘稍蜷’， ‘濁響’， ‘稍糊’， ‘凹陷’， ‘硬滑’］， ［‘淺白’， ‘稍蜷’， ‘沉悶’， ‘稍糊’， ‘凹陷’， ‘硬滑’］， ［‘烏黑’， ‘稍蜷’， ‘濁響’， ‘清晰’， np。nan， ‘軟沾’］， ［‘淺白’， ‘蜷縮’， ‘濁響’， ‘模糊’， ‘平坦’， ‘硬滑’］， ［‘青綠’， np。nan， ‘沉悶’， ‘稍糊’， ‘稍凹’， ‘硬滑’］］）>>>b = np。array（［‘是’，‘是’，‘是’，‘是’，‘是’，‘是’，‘是’，‘是’，‘否’，‘否’，‘否’，‘否’，‘否’，‘否’，‘否’，‘否’，‘否’］） 我們需要將特徵先編碼一下： “”“烏黑1；青綠2；淺白3蜷縮1；稍蜷2；硬挺3濁響1；沉悶2；清脆3清晰1；稍糊2；模糊3凹陷1；稍凹2；平坦3硬滑1；軟沾2”“”>>>a = np。array（［［np。nan， 1， 1， 1， 1， 1］， ［1， 1， 2， 1， 1， np。nan］， ［1， 1， np。nan， 1， 1， 1］， ［2， 1， 2， 1， 1， 1］， ［np。nan， 1， 1， 1， 1， 1］， ［2， 2， 1， 1， np。nan， 2］， ［1， 2， 1， 2， 2， 2］， ［1， 2， 1， np。nan， 2， 1］， ［1， np。nan， 2， 2， 2， 1］， ［2， 3， 3， np。nan， 3， 2］， ［3， 3， 3， 3， 3， np。nan］， ［3， 1， np。nan， 3， 3， 2］， ［np。nan， 2， 1， 2， 1， 1］， ［3， 2， 2， 2， 1， 1］， ［1， 2， 1， 1， np。nan， 2］， ［3， 1， 1， 3， 3， 1］， ［2， np。nan， 2， 2， 2， 1］］） 然後呼叫模型： >>>dt = DTClassifier（criterion=‘C4。5’）>>>dt。fit（a， b） 然後是預測： >>>a1 = np。array（［［2，1，1，1，1，1］， ［1，2，1，1，1，2］］）>>>prob = dt。predict_prob（a1）>>>prob［{‘否’： 0， ‘是’： 1。0}， {‘否’： 1。0， ‘是’： 0}］>>>class_ = dt。predict（a1）>>>class_［‘是’， ‘否’］ 一個被預測為好瓜，一個為壞瓜。 下一篇文章，我們介紹C4。5演算法的剪枝策略，敬請關注。
