目录

1. 决策树基本概念

2. 决策树类别

3. 构建决策树

3.1 选择最优特征

3.1.1 信息熵

3.1.2 信息增益

3.2 决策树的生成

3.3 剪枝

1. 决策树基本概念

决策树就是一棵树，可解释性强，可用if-then规则解释，易让人理解。决策树的生成是一个递归的过程，一颗决策树包含一个根节点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶子结点的路径对应了一个判定测试序列。下图是以买电脑为例构造的决策树。

2. 决策树类别

ID3决策树：用信息增益来判断当前节点应该用什么特征来构建决策树。选择信息增最高的进行划分，容易偏向于取值较多的特征C4.5决策树：用的是增益率，容易偏向于取值较少的特征CART决策树：分类和回归都能做，基尼系数越小越好

3. 构建决策树

3.1 选择最优特征

再讲选择最优特征前先补充我们需要用到的信息熵和信息增益，这二个也是进行最优特征选取的关键所在。

3.1.1 信息熵

决策树学习的关键在于如何选择最优特征进行划分，这时候就要用到信息增益，什么是信息增益呢？在划分数据集之前之后信息发生的变化成为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。先来看看信息熵（information entropy）的定义：假如当前样本集D中第k类样本所占的比例为， 为类别的总数（对于二元分类来说，k=2）。则样本集的信息熵为：

信息熵的相关代码如下：

# -*- coding: UTF-8 -*-from math import logdef calcShannonEnt(dataSet):numEntires = len(dataSet) #返回数据集的行数labelCounts = {} #保存每个标签(Label)出现次数的字典for featVec in dataSet: #对每组特征向量进行统计currentLabel = featVec[-1]#提取标签(Label)信息if currentLabel not in labelCounts.keys(): #如果标签(Label)没有放入统计次数的字典,添加进去labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1#Label计数shannonEnt = 0.0 #信息熵for key in labelCounts: #计算信息熵prob = float(labelCounts[key]) / numEntires #选择该标签(Label)的概率shannonEnt -= prob * log(prob, 2) #利用公式计算return shannonEnt #返回信息熵def createDataSet():dataSet =[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]labels = ['no surfacing', 'flippers'] # 分类属性return dataSet,labels #返回数据集和分类属性if __name__ == '__main__':dataSet, features = createDataSet()print(dataSet)print(calcShannonEnt(dataSet))

代码运行结果如下图所示，代码是先打印训练数据集，然后打印计算的信息熵H(D)：

3.1.2 信息增益

最优特征的选取需要看信息增益，信息增益是相对于特征而言的，信息增益越大，特征对最终的分类结果影响也就越大，我们就应该选择对最终分类结果影响最大的那个特征作为我们的分类特征，就是选择信息增益最大的属性。假定属性a有 V个可能的取值，如果使用特征 a来对数据集D进行划分，则会产生V个分支结点， 其中第v（小v）个结点包含了数据集D中所有在特征a上取值为的样本总数，记为。因此可以根据上面信息熵的公式计算出信息熵，再考虑到不同的分支结点所包含的样本数量不同，给分支节点赋予权重，即样本数越多的分支节点的影响越大，因此，能够计算出特征a对样本集D进行划分所获得的“信息增益”:

下面是计算信息增益，选择最优特征的代码。 在找到最优特征之前我们需要用splitDataSet()函数对数据集进行划分，循环计算信息熵和splitDataSet()函数，找到最好的特征划分方式。

# -*- coding: UTF-8 -*-from math import log"""函数说明:计算给定数据集的信息熵"""def calcShannonEnt(dataSet):numEntires = len(dataSet) #返回数据集的行数labelCounts = {} #保存每个标签(Label)出现次数的字典for featVec in dataSet: #对每组特征向量进行统计currentLabel = featVec[-1]#提取标签(Label)信息if currentLabel not in labelCounts.keys(): #如果标签(Label)没有放入统计次数的字典,添加进去labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1#Label计数shannonEnt = 0.0 #信息熵for key in labelCounts: #计算信息熵prob = float(labelCounts[key]) / numEntires #选择该标签(Label)的概率shannonEnt -= prob * log(prob, 2) #利用公式计算return shannonEnt #返回信息熵"""函数说明:创建测试数据集"""def createDataSet():dataSet =[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]labels = ['no surfacing', 'flippers'] # 分类属性return dataSet,labels #返回数据集和分类属性"""函数说明:按照给定特征划分数据集Parameters:dataSet - 待划分的数据集axis - 划分数据集的特征value - 需要返回的特征的值Returns:无"""def splitDataSet(dataSet, axis, value): retDataSet = []#创建返回的数据集列表for featVec in dataSet: #遍历数据集if featVec[axis] == value:reducedFeatVec = featVec[:axis]#去掉axis特征reducedFeatVec.extend(featVec[axis+1:])#将符合条件的添加到返回的数据集retDataSet.append(reducedFeatVec)return retDataSet #返回划分后的数据集"""函数说明:选择最优特征Parameters:dataSet - 数据集Returns:bestFeature - 信息增益最大的(最优)特征的索引值"""def chooseBestFeatureToSplit(dataSet):numFeatures = len(dataSet[0]) - 1#特征数量baseEntropy = calcShannonEnt(dataSet) #计算数据集的信息熵bestInfoGain = 0.0 #信息增益bestFeature = -1#最优特征的索引值for i in range(numFeatures):#遍历所有特征#获取dataSet的第i个所有特征featList = [example[i] for example in dataSet]uniqueVals = set(featList)#创建set集合{},元素不可重复newEntropy = 0.0 #经验条件熵for value in uniqueVals:#计算信息增益subDataSet = splitDataSet(dataSet, i, value) #subDataSet划分后的子集prob = len(subDataSet) / float(len(dataSet)) #计算子集的概率newEntropy += prob * calcShannonEnt(subDataSet)#根据公式计算经验条件熵infoGain = baseEntropy - newEntropy #信息增益print("第%d个特征的增益为%.3f" % (i, infoGain)) #打印每个特征的信息增益if (infoGain > bestInfoGain): #计算信息增益bestInfoGain = infoGain#更新信息增益，找到最大的信息增益bestFeature = i #记录信息增益最大的特征的索引值return bestFeature #返回信息增益最大的特征的索引值if __name__ == '__main__':dataSet, features = createDataSet()print("最优特征索引值:" + str(chooseBestFeatureToSplit(dataSet)))

3.2 决策树的生成

决策树是不断地递归生成的，那何时我们才能结束递归呢？递归有两个终止条件：第一个停止条件是所有的类标签完全相同，则直接返回该类标签；第二个停止条件是使用完了所有特征，仍然不能将数据划分仅包含唯一类别的分组，即特征不够用，无法简单地返回唯一的类标签，这里挑选出现数量最多的类别作为返回值。代码如下：

# -*- coding: UTF-8 -*-from math import logimport operator"""函数说明:计算给定数据集的信息熵"""def calcShannonEnt(dataSet):numEntires = len(dataSet) #返回数据集的行数labelCounts = {} #保存每个标签(Label)出现次数的字典for featVec in dataSet: #对每组特征向量进行统计currentLabel = featVec[-1]#提取标签(Label)信息if currentLabel not in labelCounts.keys(): #如果标签(Label)没有放入统计次数的字典,添加进去labelCounts[currentLabel] = 0labelCounts[currentLabel] += 1#Label计数shannonEnt = 0.0 #信息熵for key in labelCounts: #计算信息熵prob = float(labelCounts[key]) / numEntires #选择该标签(Label)的概率shannonEnt -= prob * log(prob, 2) #利用公式计算return shannonEnt #返回信息熵"""函数说明:创建测试数据集"""def createDataSet():dataSet =[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]labels = ['no surfacing', 'flippers'] # 分类属性return dataSet,labels #返回数据集和分类属性"""函数说明:按照给定特征划分数据集Parameters:dataSet - 待划分的数据集axis - 划分数据集的特征value - 需要返回的特征的值Returns:无"""def splitDataSet(dataSet, axis, value): retDataSet = []#创建返回的数据集列表for featVec in dataSet: #遍历数据集if featVec[axis] == value:reducedFeatVec = featVec[:axis]#去掉axis特征reducedFeatVec.extend(featVec[axis+1:])#将符合条件的添加到返回的数据集retDataSet.append(reducedFeatVec)return retDataSet #返回划分后的数据集"""函数说明:选择最优特征Parameters:dataSet - 数据集Returns:bestFeature - 信息增益最大的(最优)特征的索引值"""def chooseBestFeatureToSplit(dataSet):numFeatures = len(dataSet[0]) - 1#特征数量baseEntropy = calcShannonEnt(dataSet) #计算数据集的信息熵bestInfoGain = 0.0 #信息增益bestFeature = -1#最优特征的索引值for i in range(numFeatures):#遍历所有特征#获取dataSet的第i个所有特征featList = [example[i] for example in dataSet]uniqueVals = set(featList)#创建set集合{},元素不可重复newEntropy = 0.0 #经验条件熵for value in uniqueVals:#计算信息增益subDataSet = splitDataSet(dataSet, i, value) #subDataSet划分后的子集prob = len(subDataSet) / float(len(dataSet)) #计算子集的概率newEntropy += prob * calcShannonEnt(subDataSet)#根据公式计算经验条件熵infoGain = baseEntropy - newEntropy #信息增益print("第%d个特征的增益为%.3f" % (i, infoGain)) #打印每个特征的信息增益if (infoGain > bestInfoGain): #计算信息增益bestInfoGain = infoGain#更新信息增益，找到最大的信息增益bestFeature = i #记录信息增益最大的特征的索引值return bestFeature #返回信息增益最大的特征的索引值"""函数说明:统计classList中出现此处最多的元素(类标签)Parameters:classList - 类标签列表Returns:sortedClassCount[0][0] - 出现此处最多的元素(类标签)"""def majorityCnt(classList):classCount = {}for vote in classList:#统计classList中每个元素出现的次数if vote not in classCount.keys():classCount[vote] = 0 classCount[vote] += 1sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True) #根据字典的值降序排序return sortedClassCount[0][0] #返回classList中出现次数最多的元素"""函数说明:创建决策树Parameters:dataSet - 训练数据集labels - 分类属性标签featLabels - 存储选择的最优特征标签Returns:myTree - 决策树"""def createTree(dataSet, labels, featLabels):classList = [example[-1] for example in dataSet] #取分类标签(是否放贷:yes or no)if classList.count(classList[0]) == len(classList): #如果类别完全相同则停止继续划分return classList[0]if len(dataSet[0]) == 1:#遍历完所有特征时返回出现次数最多的类标签return majorityCnt(classList)bestFeat = chooseBestFeatureToSplit(dataSet)#选择最优特征bestFeatLabel = labels[bestFeat] #最优特征的标签featLabels.append(bestFeatLabel)myTree = {bestFeatLabel:{}}#根据最优特征的标签生成树del(labels[bestFeat])#删除已经使用特征标签featValues = [example[bestFeat] for example in dataSet] #得到训练集中所有最优特征的属性值uniqueVals = set(featValues) #去掉重复的属性值for value in uniqueVals:#遍历特征，创建决策树。 myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), labels, featLabels)return myTreeif __name__ == '__main__':dataSet, labels = createDataSet()featLabels = []myTree = createTree(dataSet, labels, featLabels)print(myTree)

运行结果：

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

如果看这个结果显示不太舒服的话，可以使用Matplotlib绘制决策树或者使用Graphviz显示决策树。下面是使用Matplotlib绘制决策树的代码，只需要在上面代码开头加上 import相关的包并在结尾加入以下代码即可显示。

# -*- coding: UTF-8 -*-from matplotlib.font_manager import FontPropertiesimport matplotlib.pyplot as pltfrom math import logimport operator#结尾处加上下面的代码"""函数说明:获取决策树叶子结点的数目Parameters:myTree - 决策树Returns:numLeafs - 决策树的叶子结点的数目"""def getNumLeafs(myTree):numLeafs = 0 #初始化叶子firstStr = next(iter(myTree)) #python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0]secondDict = myTree[firstStr] #获取下一组字典for key in secondDict.keys():if type(secondDict[key]).__name__=='dict':#测试该结点是否为字典，如果不是字典，代表此结点为叶子结点numLeafs += getNumLeafs(secondDict[key])else: numLeafs +=1return numLeafs"""函数说明:获取决策树的层数Parameters:myTree - 决策树Returns:maxDepth - 决策树的层数"""def getTreeDepth(myTree):maxDepth = 0 #初始化决策树深度firstStr = next(iter(myTree)) #python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0]secondDict = myTree[firstStr] #获取下一个字典for key in secondDict.keys():if type(secondDict[key]).__name__=='dict':#测试该结点是否为字典，如果不是字典，代表此结点为叶子结点thisDepth = 1 + getTreeDepth(secondDict[key])else: thisDepth = 1if thisDepth > maxDepth: maxDepth = thisDepth #更新层数return maxDepth"""函数说明:绘制结点Parameters:nodeTxt - 结点名centerPt - 文本位置parentPt - 标注的箭头位置nodeType - 结点格式Returns:无"""def plotNode(nodeTxt, centerPt, parentPt, nodeType):arrow_args = dict(arrowstyle="<-") #定义箭头格式font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14) #设置中文字体createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction', #绘制结点xytext=centerPt, textcoords='axes fraction',va="center", ha="center", bbox=nodeType, arrowprops=arrow_args, FontProperties=font)"""函数说明:标注有向边属性值Parameters:cntrPt、parentPt - 用于计算标注位置txtString - 标注的内容Returns:无"""def plotMidText(cntrPt, parentPt, txtString):xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0] #计算标注位置 yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)"""函数说明:绘制决策树Parameters:myTree - 决策树(字典)parentPt - 标注的内容nodeTxt - 结点名Returns:无"""def plotTree(myTree, parentPt, nodeTxt):decisionNode = dict(boxstyle="sawtooth", fc="0.8")#设置结点格式leafNode = dict(boxstyle="round4", fc="0.8") #设置叶结点格式numLeafs = getNumLeafs(myTree) #获取决策树叶结点数目，决定了树的宽度depth = getTreeDepth(myTree)#获取决策树层数firstStr = next(iter(myTree))#下个字典 cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff) #中心位置plotMidText(cntrPt, parentPt, nodeTxt) #标注有向边属性值plotNode(firstStr, cntrPt, parentPt, decisionNode)#绘制结点secondDict = myTree[firstStr]#下一个字典，也就是继续绘制子结点plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD#y偏移for key in secondDict.keys(): if type(secondDict[key]).__name__=='dict': #测试该结点是否为字典，如果不是字典，代表此结点为叶子结点plotTree(secondDict[key],cntrPt,str(key))#不是叶结点，递归调用继续绘制else:#如果是叶结点，绘制叶结点，并标注有向边属性值plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalWplotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD"""函数说明:创建绘制面板Parameters:inTree - 决策树(字典)Returns:无"""def createPlot(inTree):fig = plt.figure(1, facecolor='white') #创建figfig.clf()#清空figaxprops = dict(xticks=[], yticks=[])createPlot.ax1 = plt.subplot(111, frameon=False, **axprops) #去掉x、y轴plotTree.totalW = float(getNumLeafs(inTree)) #获取决策树叶结点数目plotTree.totalD = float(getTreeDepth(inTree)) #获取决策树层数plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0; #x偏移plotTree(inTree, (0.5,1.0), '')#绘制决策树plt.show() #显示绘制结果if __name__ == '__main__':dataSet, labels = createDataSet()featLabels = []myTree = createTree(dataSet, labels, featLabels)print(myTree) createPlot(myTree)

最后我们可以看到可视化的决策树：

3.3 剪枝

剪枝是为了防止决策树过拟合现象，分别有预剪枝和后剪枝。

预剪枝：在决策树生成过程中，在划分节点时，若该节点没提高其在验证集上的准确率，则不进行划分

后剪枝：先生成一棵完整的决策树，再从底往上对非叶节点考察进行剪枝

4 sklearn实现决策树

以乳腺癌数据集为例：

import numpy as npfrom sklearn.datasets import load_breast_cancerfrom sklearn.model_selection import cross_val_scorefrom sklearn.tree import DecisionTreeClassifierdt = load_breast_cancer()clf = DecisionTreeClassifier(criterion='entropy')score = cross_val_score(clf,dt.data,dt.target,cv=5)print(np.mean(score))