機器學習（四）：C4.5決策樹（基礎篇）
相關的決策樹文章：
- 機器學習（四）ID3決策樹
- 機器學習（四）CART分類樹
- 機器學習（四）CART回歸樹
- 機器學習（四）決策樹繪圖
- 機器學習（四）剪枝技術
問題一：為什麼要使用C4.5決策樹？
前面我們介紹了ID3決策樹,ID3決策樹有一個很大的缺點：資訊增益反映了給定一個條件下以後不确定減少的程度，必然是分得越細的資料集确定性越高，也就是條件熵越小，資訊增益越大。但是這樣下來隻能處理離散型屬性，并且傾向于選擇取值較多的屬性。而C4.5采用的是資訊增益率來作為分支的準則。很好的解決了這一缺點。在平時運用上，C4.5要多于ID3.
問題二：C4.5如何進行分支？
資訊增益率是C4.5決策樹進行分支的一個很重要的名額。在之前的學習中，我們了解了香農熵，和資訊增益，那麼什麼是資訊增益率？
資訊增益的定義：
C a i n r a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) Cain_{ratio}(D,a) = \frac{Gain(D,a)}{IV(a)} Cainratio(D,a)=IV(a)Gain(D,a)
其中：
I V ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ l o g 2 ∣ D v ∣ ∣ D ∣ IV(a)=-\displaystyle\sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|} IV(a)=−v=1∑V∣D∣∣Dv∣log2∣D∣∣Dv∣
分子很簡單，分子為資訊增益（可參考ID3決策樹（基礎篇））
分母為屬性a的熵，成為屬性a的”固有值“。屬性a的可能取值數目越多（即V越大），則IV(a)的值通常會越大。
需要注意的是：增益率準則對可取值數目較少的屬性有偏好，是以，C4.5算法不是直接選擇資訊增益率最大的候選劃分屬性，而是使用了一個啟發式：先從候選劃分屬性中找出資訊增益率高于平均水準的屬性，再從中選擇增益率最高的。
代碼實作
C4.5決策樹的代碼與ID3的代碼實作差别不大：隻需要更改部分函數即可：
# -*- coding: utf-8 -*-
"""
決策樹C4.5的實作
"""
from math import log
import operator
import pandas as pd
import plotTrees
def majorityCnt(classList):
"""
找到最大頻繁向量（多數表決器）
:param classList:訓練集
:return:最大值
"""
classCounts = {}
for value in classList: #周遊訓練集中的每一個變量
if (value not in classCounts.keys()): #如果變量不在清單中
classCounts[value] = 0 #建立一個字典的鍵
classCounts[value] += 1 #數量加一
sortedClassCount = sorted(classCounts.items(), key=operator.itemgetter(1), reverse=True) #排序
return sortedClassCount[0][0] #輸出第一個，即最大值
def splitDataSet(dataSet, axis, value):
"""
以靠指定列的指定值來劃分資料集，比如劃分西瓜瓜皮形狀為橢圓的資料集
:param axis: 索引列，即形狀
:param value: 索引列的特定值，即橢圓
:return:
"""
retDataSet = []
for festdataVal in dataSet:
if festdataVal[axis] == value:
reducedFeatVal = festdataVal[:axis] #這兩行去掉索引列
reducedFeatVal.extend(festdataVal[axis+1:])
retDataSet.append(reducedFeatVal)
return retDataSet
def calcShannonEnt(columnIndex, dataSet):
"""
計算香農熵
:param dataSet:
:return:
"""
numEntries = len(dataSet) #獲得資料集的長度
labelCounts = {} #計算标簽的字典
for featDataVal in dataSet:
currentLabels = featDataVal[columnIndex] #取最後一個标簽值
if currentLabels not in labelCounts.keys(): #判斷有沒有在标簽裡面
labelCounts[currentLabels] = 0
labelCounts[currentLabels] += 1
shannonEnt = 0.0
for key in labelCounts.keys(): #key有幾個周遊幾次
prob = labelCounts[key]/float(numEntries) #計算頻率
shannonEnt -= prob*log(prob, 2)
return shannonEnt
def chooseBestFeatureToSplitOfFurther(dataSet):
"""
選擇資訊增益率最大的特征值
:param dataSet:資料集
:return:
"""
numFeatures = len(dataSet[0]) - 1 # 看資料集而定，資料中如果最後一行為标簽，則删去
baseEntropy = calcShannonEnt(-1, dataSet) # 計算所有資料集的香農熵
bestFeaturesindex = 0 # 最佳特征的索引
bestInfoGainRatio = 0.0 # 最佳資訊熵
for i in range(numFeatures): # 有幾個特征值循環幾次
featEntropy = calcShannonEnt(i, dataSet)
featList = [] # 特征值清單
for example in dataSet: # 獲得這個列的值
featList.append(example[i])
uniqueVals = set(featList) # 相同的資料并沒有意義，去重
newEntropy = 0.0 # 新資訊熵
for value in uniqueVals: # 得到該列的特征值
subDataSet = splitDataSet(dataSet, i, value) # 劃分資料集
prob = len(subDataSet) / float(len(dataSet)) # 權重或者條件機率
newEntropy += prob * calcShannonEnt(-1, subDataSet) # 計算資訊增益後面的條件經驗熵
infoGain = baseEntropy - newEntropy # 計算資訊增益
if featEntropy == 0.0 :
infoGainRatio = 0.0
else:
infoGainRatio = infoGain/float(featEntropy)
if infoGainRatio > bestInfoGainRatio: # 更改最大經驗熵
bestInfoGainRatio = infoGainRatio
bestFeaturesindex = i
return bestFeaturesindex # 輸出最大經驗熵的索引
def diferFeature(dataSet, label):
numFeatures = len(dataSet[0]) - 1 # 看資料集而定，資料中如果最後一行為标簽，則删去
baseEntropy = calcShannonEnt(-1, dataSet) # 計算所有資料集的香農熵
sumEntropy = 0.0
featureEntropy = []
dellabel = []
retDataSet = dataSet
label1 = label.copy()
for i in range(numFeatures): # 有幾個特征值循環幾次
featList = [] # 特征值清單
for example in dataSet: # 獲得這個列的值
featList.append(example[i])
uniqueVals = set(featList) # 相同的資料并沒有意義，去重
newEntropy = 0.0 # 新資訊熵
for value in uniqueVals: # 得到該列的特征值
subDataSet = splitDataSet(dataSet, i, value) # 劃分資料集
prob = len(subDataSet) / float(len(dataSet)) # 權重或者條件機率
newEntropy += prob * calcShannonEnt(-1, subDataSet) # 計算資訊增益後面的條件經驗熵
infoGain = baseEntropy - newEntropy # 計算資訊增益
featureEntropy.append(infoGain)
sumEntropy += infoGain
averageEntropy = sumEntropy/numFeatures
for i in range(numFeatures):
if featureEntropy[i]<averageEntropy:
dellabel.append(labels[i])
label.append('jieguo')
for i in range(len(dellabel)):
label1.remove(dellabel[i])
retDataSet = pd.DataFrame(retDataSet, columns=label)
retDataSet = retDataSet.drop(dellabel, axis=1)
retDataSet = retDataSet.values.tolist()
return retDataSet, label1
def createTree(dataSet, label):
"""
建立樹
:param dataSet:
:param label:
:return:
"""
classList = [] #獲得每一個标簽
for classVal in dataSet:
classList.append(classVal[-1])
if classList.count(classList[0]) == len(classList): #如果全部标簽都相同
return classList[0] #傳回該标簽
if len(dataSet[0]) == 1: #如果一列隻有一個特征
return majorityCnt(classList)
#dataSet, label = self.diferFeature(dataSet, label)
#擷取最優的索引值
bestFeatureIndex = chooseBestFeatureToSplitOfFurther(dataSet)
#擷取最優索引值的名稱
bestFeatureLabel = label[bestFeatureIndex]
mytree = {bestFeatureLabel:{}} #建立根節點
del(label[bestFeatureIndex]) #删去用過的最優節點
bestFeature = [] #最優的特征
for example in dataSet:
bestFeature.append(example[bestFeatureIndex])
uniquesVal = set(bestFeature) #最優特征的種類
for val in uniquesVal:
subLabel = label[:] #建立個子标簽
mytree[bestFeatureLabel][val] = createTree(splitDataSet(dataSet, bestFeatureIndex, val), subLabel) #遞歸
return mytree
def classify( inputTree, featLable, testVec):
"""
擷取分類的結果（算法的使用器）
:param inputTree:決策樹字典
:param featLable: 标簽清單
:param testVec: 測試向量
:return:
"""
#擷取根節點的名稱，并且把根節點變成清單
firstSide = list(inputTree.keys())
#根節點名稱string類型
firstStr = firstSide[0]
#獲得根節點對應得子節點
secondDict = inputTree[firstStr]
#獲得子節點在标簽清單得索引
featIndex = featLable.index(firstStr)
#獲得測試向量的值
key = testVec[featIndex]
#擷取樹幹向量後的變量
valueOfFeat = secondDict[key]
#判斷是子結點還是葉子節點：子結點就回調分類函數，葉子結點就是分類結果
if isinstance(valueOfFeat, dict):
classLabel = classify(valueOfFeat, featLable, testVec)
else:
classLabel = valueOfFeat
return classLabel
def storeTree(inputTree, filename):
#寫入檔案
import pickle
fw = open(filename, 'wb+')
pickle.dump(inputTree,fw)
fw.close()
def grabTree(filename):
#讀取數
import pickle
fr = open(filename, 'rb')
return pickle.load(fr)
if __name__ == "__main__":
#因為資料集尋找比較複雜，是以采用自己随機建立數組
dataSet = [[1, 1, 3, 4, 2, 3, 'yes'],
[0, 1, 3, 3, 6, 3, 'yes'],
[1, 0, 4, 3, 6, 4, 'no'],
[0, 1, 2, 4, 2, 3, 'no'],
[0, 0, 3, 3, 2, 4, 'no']]
labels = ['no surfacing', 'flippers', 'table', 'type', '1', '2']
#複制
label1 = labels.copy()
#建立樹
mytree = createTree(dataSet, label1)
print(mytree)
#使用樹的操作
a = classify(mytree, labels, [0,1, 3, 4])
print(a)
plotTrees.createPlot(mytree)
我們來看看結果：
可以很好的看出，生成了我麼想要的決策樹。以及測試結果出現的答案。