決策樹3: 特徵選擇之尋找最優劃分
- 2019 年 12 月 23 日
- 筆記
0x00 前言
決策樹演算法的三個步驟：特徵選擇、決策樹生成、決策樹剪枝。其中特徵選擇要解決的核心問題就是：
- 每個節點在哪個維度上做劃分？
- 某個維度在哪個值上做劃分？
劃分的依據是： 要讓數據劃分成兩部分之後，系統整體的資訊熵降低。
具體方法是： 對所有的劃分可行性進行搜索。下一篇我們模擬在一個節點上進行搜索，找到一個節點上資訊熵的最優劃分。
那麼問題來了： 我們如何找到各個特徵/節點上的最優劃分呢？
0x01 資訊熵的最優劃分
1.1 模擬貸款申請
現在我們以銀行貸款申請業務為例，模擬四個特徵，分別是：年齡、有工作、有房子、信貸情況。
下面就通過程式碼實現，找到當前應該在哪個特徵維度上的哪個值進行最優劃分：
1.2 程式碼實現
import numpy as npfrom collections import Counterfrom math import log # 每列：['年齡','有工作','有自己的房子','信貸情況','是否申請貸款']dataSet=np.array([[0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 1, 0, 1, 1], [0, 1, 1, 0, 1], [0, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 1, 0], [1, 1, 1, 1, 1], [1, 0, 1, 2, 1], [1, 0, 1, 2, 1], [2, 0, 1, 2, 1], [2, 0, 1, 1, 1], [2, 1, 0, 1, 1], [2, 1, 0, 2, 1], [2, 0, 0, 0, 0]])featList = ['年齡','有工作','有自己的房子','信貸情況'] """函數說明：計算給定標籤的經驗熵（資訊熵）Parameters： y：使用標籤y計算資訊熵，，此時傳遞y是多維數組 計算資訊熵需要每種類別出現的概率p，因此傳入包含分類資訊的標籤yReturns： entropy：經驗熵"""def calEntropy(y): # 計數器，統計y中所有類別出現的次數 # 扁平化，將嵌套的多維數組變成一維數組 counter = Counter(y.flatten()) entropy = 0 for num in counter.values(): p = num / len(y) entropy += -p * log(p) return entropy """函數說明：根據傳遞進來的特徵維度及值，將數據劃分為2類Parameters： X,y,featVec,value：特徵向量、標籤、特徵維度、值Returns： 返回劃分為兩類的後的數據"""def split(X, y, featVec, value): # 使用維度featVect上的value，將數據劃分成左右兩部分 # 得到的布爾向量，傳入array中做索引，即可找出滿足條件的相應數據（布爾屏蔽） index_a = (X[:,featVec] <= value) index_b = (X[:,featVec] > value) return X[index_a], X[index_b], y[index_a], y[index_b] """函數說明：尋找最優劃分Parameters： X,y：特徵向量、標籤Returns： 返回最優熵，以及在哪個維度、哪個值進行劃分"""def try_split(X, y): # 搞一個熵的初始值：正無窮 best_entropy = float('inf') best_featVec = -1 # 特徵向量 best_value = -1 # 遍歷每一個特徵維度（列） for featVec in range(X.shape[1]): # 然後需要找到每個特徵維度上的劃分點。 # 找出該維度上的每個兩個樣本點的中間值，作為候選劃分點。 # 為了方便尋找候選劃分點，可以對該維度上的數值進行排序， # argsort函數返回的是數組值從小到大的索引值（不打亂原來的順序） sort_index = np.argsort(X[:,featVec]) for i in range(1, len(X)): if X[sort_index[i-1], featVec] != X[sort_index[i], featVec]: value = (X[sort_index[i-1], featVec] + X[sort_index[i], featVec]) / 2 X_l, X_r, y_l, y_r = split(X, y, featVec, value) # 要求最優劃分，需要看在此劃分下得到的兩個分類數據集的熵之和是否是最小的 entropy = calEntropy(y_l) + calEntropy(y_r) if entropy < best_entropy: best_entropy, best_featVec, best_value = entropy, featVec, value return best_entropy, best_featVec, best_value best_entropy, best_featVec, best_value = try_split(X, y)print("最優熵：", best_featVec)print("在哪個維度熵進行劃分：", best_featVec)print("在哪個值上進行劃分：", best_value)
輸出：最優熵：0.6365141682948128在哪個維度熵進行劃分：2在哪個值上進行劃分：0.5
也就是說，根據窮舉各個欄位上的最優熵，可以得知，在第3個特徵（有自己的房子）上，以0.5為閾值進行分類，可以得到最小熵。
0x02 資訊增益&資訊增益率最優劃分
2.1 資訊增益最優劃分實現
PS:下面的程式碼是都是乾貨，多讀讀注釋，看懂了就理解透徹了
import numpy as npfrom collections import Counterfrom math import log # 每列：['年齡','有工作','有自己的房子','信貸情況','是否申請貸款']，其中'是否申請貸款'是labeldataSet=np.array([[0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 1, 0, 1, 1], [0, 1, 1, 0, 1], [0, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 1, 0], [1, 1, 1, 1, 1], [1, 0, 1, 2, 1], [1, 0, 1, 2, 1], [2, 0, 1, 2, 1], [2, 0, 1, 1, 1], [2, 1, 0, 1, 1], [2, 1, 0, 2, 1], [2, 0, 0, 0, 0]])X = dataSet[:,:4]y = dataSet[:,-1:]strs = ['年齡','有工作','有自己的房子','信貸情況','是否申請貸款'] """函數說明：計算經驗熵Parameters： dataSet：樣本數據集DReturns： entory：經驗熵"""def calEntropy(dataSet): #返回數據集行數 numEntries=len(dataSet) #保存每個標籤（label）出現次數的字典：<label:出現次數> labelCounts={} #對每組特徵向量進行統計 for featVec in dataSet: #提取標籤資訊 currentLabel=featVec[-1] #如果標籤沒有放入統計次數的字典，添加進去 if currentLabel not in labelCounts.keys(): labelCounts[currentLabel]=0 #label計數 labelCounts[currentLabel]+=1 entory=0.0 #計算經驗熵 for key in labelCounts: #選擇該標籤的概率 prob=float(labelCounts[key])/numEntries #利用公式計算 entory-=prob*log(prob,2) return entory """函數說明：得到當前特徵條件下的小類的所有樣本集合（即不包含當前特徵的特徵樣本集）Parameters： dataSet：樣本數據集D curtFeatIndex：當前用來劃分數據集的特徵A的位置 categories：特徵A所有可能分類的集合Returns： otherFeatSets：不包含當前特徵的特徵樣本集"""def currentConditionSet(dataSet, curtFeatIndex, categroy): otherFeatSets = [] # 對於數據集中的所有特徵向量，拋去當前特徵後拼接好的集合 for featVec in dataSet: if featVec[curtFeatIndex] == categroy: otherFeatSet = np.append(featVec[:curtFeatIndex],featVec[curtFeatIndex+1:]) otherFeatSets.append(otherFeatSet) return otherFeatSets """函數說明：在選擇當前特徵的條件下，計算熵，即條件熵Parameters： dataSet：樣本數據集D curtFeatIndex：當前用來劃分數據集的特徵A的位置 categories：特徵A所有可能分類的集合Returns： conditionalEnt：返回條件熵"""def calConditionalEnt(dataSet, curtFeatIndex, categories): conditionalEnt = 0 # 對於每一個分類，計算選擇當前特徵的條件下條件熵 # 比如在選擇「年齡」這一特徵下，共有「老中青」三個小分類 for categroy in categories: # 得到當前特徵條件下的小類的所有樣本集合，即不包含當前特徵的特徵樣本集 # 如得到在選擇「青年」這個小類下一共有5個樣本，且不包含「年齡」這一特徵 cdtSetCategroy = currentConditionSet(dataSet, curtFeatIndex, categroy) # 計算當前特徵條件下的小分類，佔總分類的比例 prob = len(cdtSetCategroy) / float(dataSet.shape[0]) # 累加得到條件熵 conditionalEnt += prob * calEntropy(cdtSetCategroy) return conditionalEnt """函數說明：計算資訊增益Parameters： baseEntropy：劃分樣本集合D的熵是為H(D)，即基本熵 dataSet：樣本數據集D curtFeatIndex：當前用來劃分數據集的特徵A的位置Returns： infoGain：資訊增益值"""def calInfoGain(baseEntropy,dataSet,curtFeatIndex): conditionalEnt = 0.0 # categories是所有特徵向量中當前特徵的對應值的set集合（去重複） # 相當於該特徵一共有幾種分類，如「年齡」這一特徵，分為「老中青」三類 categories = set(dataSet[:,curtFeatIndex]) # 計算劃分後的數據子集（給定特徵A的情況下，數據集D）的條件熵（經驗條件熵）H(D|A) conditionalEnt = calConditionalEnt(dataSet,curtFeatIndex,categories) # 計算資訊增益：g(D,A)=H(D)−H(D|A) infoGain = baseEntropy - conditionalEnt #列印每個特徵的資訊增益 print("第%d個特徵的增益為%.3f" % (curtFeatIndex, infoGain)) return infoGain """函數說明：尋找最優劃分Parameters： dataSet：數據集Returns： 列印最優劃分結果"""def optimalPartition(dataSet): bestInfoGain = -1 # 最佳資訊增益初始值 bestFeatVec = -1 # 最佳劃分的特徵向量 # 劃分前樣本集合D的熵H(D)，即基本熵 baseEntropy = calEntropy(dataSet) # 遍歷每一個特徵維度（列），得到基於當前特徵劃分的資訊增益 for curtFeatIndex in range(dataSet.shape[1]-1): # 計算資訊增益 infoGain = calInfoGain(baseEntropy, dataSet, curtFeatIndex) # 選取最優資訊增益的劃分 if (infoGain > bestInfoGain): #更新資訊增益，找到最大的資訊增益 bestInfoGain = infoGain #記錄資訊增益最大的特徵的索引值 bestFeatVec = curtFeatIndex print("最佳的劃分為第%d個特徵，是」%s「，資訊增益為%.3f" % (bestFeatVec,featList[bestFeatVec],bestInfoGain)) return bestFeatVec optimalPartition(dataSet)
輸出：
第0個特徵的增益為0.083第1個特徵的增益為0.324第2個特徵的增益為0.420第3個特徵的增益為0.363最佳的劃分為第2個特徵，是」有自己的房子「，資訊增益為0.420
2.2 資訊增益率最優劃分實現
根據資訊增益率的定義，對上面的程式碼進行改造，可以得到資訊增益率的最優選擇實現
"""函數說明：計算懲罰參數，資訊增益g(D,A)與訓練數據集D關於特徵A的值的熵HA(D)之比Parameters： dataSet：樣本數據集D curtFeatIndex：當前用來劃分數據集的特徵A的位置 categories：特徵A所有可能分類的集合Returns： conditionalEnt：懲罰參數"""def calPenaltyPara(dataSet, curtFeatIndex, categories): penaltyItem = 1 # 對於每一個分類，計算選擇當前特徵的條件下條件熵 # 比如在選擇「年齡」這一特徵下，共有「老中青」三個小分類 for categroy in categories: # 得到當前特徵條件下的小類的所有樣本集合，即不包含當前特徵的特徵樣本集 # 如得到在選擇「青年」這個小類下一共有5個樣本，且不包含「年齡」這一特徵 cdtSetCategroy = currentConditionSet(dataSet, curtFeatIndex, categroy) # 計算當前特徵條件下的小分類，佔總分類的比例 prob = len(cdtSetCategroy) / float(dataSet.shape[0]) # 累加得到懲罰項 penaltyItem += -prob * log(prob,2) return penaltyItem """函數說明：計算資訊增益率（懲罰參數 * 資訊增益）Parameters： baseEntropy：劃分樣本集合D的熵是為H(D)，即基本熵 dataSet：樣本數據集D curtFeatIndex：當前用來劃分數據集的特徵A的位置Returns： infoGain：資訊增益值"""def calInfoGainRate(baseEntropy,dataSet,curtFeatIndex): infoGainRate = 0.0 # 計算資訊增益 infoGain = calInfoGain(baseEntropy,dataSet,curtFeatIndex) # 得到該特徵的所有分類 categories = set(dataSet[:,curtFeatIndex]) # 計算懲罰項 penaltyItem = calPenaltyPara(dataSet, curtFeatIndex, categories) # 計算資訊增益率 infoGainRatio = infoGain / penaltyItem #列印每個特徵的資訊增益率 print("第%d個特徵的增益率為%.3f" % (curtFeatIndex, infoGainRatio)) return infoGainRatio """函數說明：尋找最優劃分Parameters： dataSet：數據集Returns： 列印最優劃分結果"""def optimalPartition(dataSet): bestInfoGainRatio = 0.0 # 最佳資訊增益率初始值 bestFeatVec = -1 # 最佳劃分的特徵向量 # 劃分前樣本集合D的熵H(D)，即基本熵 baseEntropy = calEntropy(dataSet) # 遍歷每一個特徵維度（列），得到基於當前特徵劃分的資訊增益 for curtFeatIndex in range(dataSet.shape[1]-1): # categories是所有特徵向量中當前特徵的對應值的set集合（去重複） # 相當於該特徵一共有幾種分類，如「年齡」這一特徵，分為「老中青」三類 #categories = set(dataSet[:,curtFeatIndex]) # 計算資訊增益率 infoGainRatio = calInfoGainRate(baseEntropy, dataSet, curtFeatIndex) # 選取最優資訊增益率的劃分 if (infoGainRatio > bestInfoGainRatio): #更新資訊增益率，找到最大的資訊增益率 bestInfoGainRatio = infoGainRatio #記錄資訊增益率最大的特徵的索引值 bestFeatVec = curtFeatIndex print("最佳的劃分為第%d個特徵，是」%s「，資訊增益率為%.3f" % (bestFeatVec,strs[bestFeatVec],bestInfoGainRatio)) return optimalPartition(dataSet)
輸出：
第0個特徵的增益率為0.032第1個特徵的增益率為0.169第2個特徵的增益率為0.213第3個特徵的增益率為0.141最佳的劃分為第2個特徵，是」有自己的房子「，資訊增益率為0.213
0x03 基尼係數最優劃分
3.1 基尼係數最優劃分實現
"""函數說明：計算基尼係數Parameters： y：使用標籤y計算資訊熵，此時傳遞y是多維數組Returns： entropy：經驗熵"""def calGini(y): # 計數器，統計y中所有類別出現的次數 # 扁平化，將嵌套的多維數組變成一維數組 counter = Counter(y.flatten()) gini = 1 for num in counter.values(): p = num / len(y) gini -= p ** 2 return gini """函數說明：尋找最優劃分Parameters： X,y：特徵向量、標籤Returns： 返回最優熵，以及在哪個維度、哪個值進行劃分"""def try_split(X, y): # 搞一個基尼係數的初始值：正無窮 bestGini = float('inf') bestFeatVec = -1 # 特徵向量 bestValue = -1 # 遍歷每一個特徵維度（列） for featVec in range(X.shape[1]): # 然後需要找到每個特徵維度上的劃分點。 # 找出該維度上的每個兩個樣本點的中間值，作為候選劃分點。 # 為了方便尋找候選劃分點，可以對該維度上的數值進行排序， # argsort函數返回的是數組值從小到大的索引值（不打亂原來的順序） sort_index = np.argsort(X[:,featVec]) for i in range(1, len(X)): if X[sort_index[i-1], featVec] != X[sort_index[i], featVec]: value = (X[sort_index[i-1], featVec] + X[sort_index[i], featVec]) / 2 X_l, X_r, y_l, y_r = split(X, y, featVec, value) # 要求最優劃分，需要看在此劃分下得到的兩個分類數據集的熵之和是否是最小的 gini = calGini(y_l) + calGini(y_r) if gini < bestGini: bestGini, bestFeatVec, bestValue = gini, featVec, value return bestGini, bestFeatVec, bestValue bestGini, bestFeatVec, bestValue = try_split(X, y)print("最優基尼係數：", bestGini)print("在哪個維度上進行劃分：", bestFeatVec)print("在哪個值上進行劃分：", bestValue)
輸出：
最優基尼係數：0.4444444444444445在哪個維度上進行劃分：2在哪個值上進行劃分：0.5
0xFF 總結
結合概念，好好看程式碼。程式碼研究明白，你就悟了！加油吧少年！
