一、概論

C4.5主要是在ID3的基礎上改進，ID3選擇（屬性）樹節點是選擇信息增益值最大的屬性作為節點。而C4.5引入了新概念“信息增益率”,C4.5是選擇信息增益率最大的屬性作為樹節點。

二、信息增益

以上公式是求信息增益率（ID3的知識點）

三、信息增益率

信息增益率是在求出信息增益值在除以。

例如下面公式為求屬性為“outlook”的值：

四、C4.5的完整代碼

from numpy import *from scipy import *from math import logimport operator#計算給定數據的香濃熵：def calcShannonEnt(dataSet): numEntries = len(dataSet)  labelCounts = {} #類別字典（類別的名稱為鍵，該類別的個數為值） for featVec in dataSet:  currentLabel = featVec[-1]   if currentLabel not in labelCounts.keys(): #還沒添加到字典里的類型   labelCounts[currentLabel] = 0;  labelCounts[currentLabel] += 1; shannonEnt = 0.0  for key in labelCounts: #求出每種類型的熵  prob = float(labelCounts[key])/numEntries #每種類型個數占所有的比值  shannonEnt -= prob * log(prob, 2) return shannonEnt; #返回熵#按照給定的特征劃分數據集def splitDataSet(dataSet, axis, value): retDataSet = []  for featVec in dataSet: #按dataSet矩陣中的第axis列的值等于value的分數據集  if featVec[axis] == value:  #值等于value的，每一行為新的列表（去除第axis個數據）   reducedFeatVec = featVec[:axis]   reducedFeatVec.extend(featVec[axis+1:])    retDataSet.append(reducedFeatVec)  return retDataSet #返回分類后的新矩陣#選擇最好的數據集劃分方式def chooseBestFeatureToSplit(dataSet):  numFeatures = len(dataSet[0])-1 #求屬性的個數 baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0; bestFeature = -1  for i in range(numFeatures): #求所有屬性的信息增益  featList = [example[i] for example in dataSet]   uniqueVals = set(featList) #第i列屬性的取值（不同值）數集合  newEntropy = 0.0   splitInfo = 0.0;  for value in uniqueVals: #求第i列屬性每個不同值的熵*他們的概率   subDataSet = splitDataSet(dataSet, i , value)    prob = len(subDataSet)/float(len(dataSet)) #求出該值在i列屬性中的概率   newEntropy += prob * calcShannonEnt(subDataSet) #求i列屬性各值對于的熵求和   splitInfo -= prob * log(prob, 2);  infoGain = (baseEntropy - newEntropy) / splitInfo; #求出第i列屬性的信息增益率  print infoGain;   if(infoGain > bestInfoGain): #保存信息增益率最大的信息增益率值以及所在的下表（列值i）   bestInfoGain = infoGain    bestFeature = i  return bestFeature #找出出現次數最多的分類名稱def majorityCnt(classList):  classCount = {}  for vote in classList:   if vote not in classCount.keys(): classCount[vote] = 0   classCount[vote] += 1  sortedClassCount = sorted(classCount.iteritems(), key = operator.itemgetter(1), reverse=True) return sortedClassCount[0][0] #創建樹def createTree(dataSet, labels):  classList = [example[-1] for example in dataSet]; #創建需要創建樹的訓練數據的結果列表（例如最外層的列表是[N, N, Y, Y, Y, N, Y]） if classList.count(classList[0]) == len(classList): #如果所有的訓練數據都是屬于一個類別，則返回該類別  return classList[0];  if (len(dataSet[0]) == 1): #訓練數據只給出類別數據（沒給任何屬性值數據），返回出現次數最多的分類名稱  return majorityCnt(classList); bestFeat = chooseBestFeatureToSplit(dataSet); #選擇信息增益最大的屬性進行分（返回值是屬性類型列表的下標） bestFeatLabel = labels[bestFeat] #根據下表找屬性名稱當樹的根節點 myTree = {bestFeatLabel:{}} #以bestFeatLabel為根節點建一個空樹 del(labels[bestFeat]) #從屬性列表中刪掉已經被選出來當根節點的屬性 featValues = [example[bestFeat] for example in dataSet] #找出該屬性所有訓練數據的值（創建列表） uniqueVals = set(featValues) #求出該屬性的所有值得集合（集合的元素不能重復） for value in uniqueVals: #根據該屬性的值求樹的各個分支  subLabels = labels[:]   myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels) #根據各個分支遞歸創建樹 return myTree #生成的樹#實用決策樹進行分類def classify(inputTree, featLabels, testVec):  firstStr = inputTree.keys()[0]  secondDict = inputTree[firstStr]  featIndex = featLabels.index(firstStr)  for key in secondDict.keys():   if testVec[featIndex] == key:    if type(secondDict[key]).__name__ == 'dict':     classLabel = classify(secondDict[key], featLabels, testVec)    else: classLabel = secondDict[key]  return classLabel #讀取數據文檔中的訓練數據（生成二維列表）def createTrainData(): lines_set = open('../data/ID3/Dataset.txt').readlines() labelLine = lines_set[2]; labels = labelLine.strip().split() lines_set = lines_set[4:11] dataSet = []; for line in lines_set:  data = line.split();  dataSet.append(data); return dataSet, labels#讀取數據文檔中的測試數據（生成二維列表）def createTestData(): lines_set = open('../data/ID3/Dataset.txt').readlines() lines_set = lines_set[15:22] dataSet = []; for line in lines_set:  data = line.strip().split();  dataSet.append(data); return dataSetmyDat, labels = createTrainData() myTree = createTree(myDat,labels) print myTreebootList = ['outlook','temperature', 'humidity', 'windy'];testList = createTestData();for testData in testList: dic = classify(myTree, bootList, testData) print dic