目录

决策树的构造

决策树的一般流程

信息增益 

编写代码计算经验熵

利用代码计算信息增益

划分数据集

选择最好的数据集划分方式 

信息增益率

基尼系数 

ID3、C4.5、CART的区别

信息增益 vs 信息增益比

 gini指数 vs 熵

决策树的可视化 

 总结

---

决策树的构造

决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。（1） 开始：构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。

（2）如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。

（3）如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如果递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。

（4）每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。

决策树的特点：

• 优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
• 缺点：可能会产生过度匹配的问题
• 适用数据类型：数值型和标称型

决策树的一般流程

首先：确定当前数据集上的决定性特征，为了得到该决定性特征，必须评估每个特征，完成测试之后，原始数据集就被划分为几个数据子集，这些数据子集会分布在第一个决策点的所有分支上，如果某个分支下的数据属于同一类型，则当前无序阅读的垃圾邮件已经正确的划分数据分类，无需进一步对数据集进行分割，如果不属于同一类，则要重复划分数据子集，直到所有相同类型的数据均在一个数据子集内。

创建分支的伪代码createBranch()如下图所示：

If so return 类标签：
Else寻找划分数据集的最好特征划分数据集创建分支节点for 每个划分的子集调用函数createBranch()并增加返回结果到分支节点中return 分支节点

使用决策树做预测需要以下过程：

收集数据：可以使用任何方法。比如想构建一个相亲系统，我们可以从媒婆那里，或者通过参访相亲对象获取数据。根据他们考虑的因素和最终的选择结果，就可以得到一些供我们利用的数据了。
准备数据：收集完的数据，我们要进行整理，将这些所有收集的信息按照一定规则整理出来，并排版，方便我们进行后续处理。
分析数据：可以使用任何方法，决策树构造完成之后，我们可以检查决策树图形是否符合预期。
训练算法：这个过程也就是构造决策树，同样也可以说是决策树学习，就是构造一个决策树的数据结构。
测试算法：使用经验树计算错误率。当错误率达到了可接收范围，这个决策树就可以投放使用了。
使用算法：此步骤可以使用适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。 

信息增益 

划分数据集的大原则是：将无序数据变得更加有序，但是各种方法都有各自的优缺点，信息论是量化处理信息的分支科学，在划分数据集前后信息发生的变化称为信息增益，获得信息增益最高的特征就是最好的选择，所以必须先学习如何计算信息增益，集合信息的度量方式称为香农熵，或者简称熵。

熵定义为信息的期望值，如果待分类的事物可能划分在多个类之中，则符号的信息定义为：

 

其中，是选择该分类的概率。为了计算熵，我们需要计算所有类别所有可能值所包含的信息期望值，通过下式得到： 

 其中，n nn为分类数目，熵越大，随机变量的不确定性就越大。

信息增益：信息增益是相对于特征而言的。所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即：

        g(D,A)=H(D)−H(D∣A)

一般地，熵H(D)与条件熵H(D|A)之差成为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。

信息增益值的大小相对于训练数据集而言的，并没有绝对意义，在分类问题困难时，也就是说在训练数据集经验熵大的时候，信息增益值会偏大，反之信息增益值会偏小，使用信息增益比可以对这个问题进行校正，这是特征选择的另一个标准。

信息增益比：特征A与训练数据集D的信息增益比g -R ( D , A )定义为其信息增g(D,A)与训练数据集D的经验熵之比： 

gR​(D,A)=H(D)g/(D,A)​

编写代码计算经验熵

自我奖励样品表

ID	时间	有时间	做有意义的事	心情是否愉悦	结果
1	早上	否	否	一般	否
2	早上	否	否	好	否
3	早上	是	否	好	是
4	早上	是	是	一般	是
5	早上	否	否	一般	否
6	中午	否	否	一般	否
7	中午	否	否	好	否
8	中午	是	是	好	是
9	中午	是	是	非常好	是
10	中午	否	是	非常好	是
11	晚上	否	是	非常好	是
12	晚上	否	是	好	是
13	晚上	是	否	好	是
14	晚上	是	否	非常好	是
15	晚上	否	否	一般	否

在编写代码之前，我们先对数据集进行属性标注。

• 时间：0代表早上，1代表中午，2代表老年晚上
• 有时间：0代表否，1代表是；
• 做有意义的事：0代表否，1代表是；
• 心情是否愉悦：0代表一般，1代表好，2代表非常好；
• 结果：no代表否，yes代表是。

创建数据集，计算经验熵的代码如下：

from math import log"""
函数说明：创建测试数据集
Parameters：无
Returns：dataSet：数据集labels：分类属性
"""
def creatDataSet():# 数据集dataSet=[[0, 0, 0, 0, 'no'],[0, 0, 0, 1, 'no'],[0, 1, 0, 1, 'yes'],[0, 1, 1, 0, 'yes'],[0, 0, 0, 0, 'no'],[1, 0, 0, 0, 'no'],[1, 0, 0, 1, 'no'],[1, 1, 1, 1, 'yes'],[1, 0, 1, 2, 'yes'],[1, 0, 1, 2, 'yes'],[2, 0, 1, 2, 'yes'],[2, 0, 1, 1, 'yes'],[2, 1, 0, 1, 'yes'],[2, 1, 0, 2, 'yes'],[2, 0, 0, 0, 'no']]#分类属性labels=['时间','有时间','做有意义的事','心情是否愉悦']#返回数据集和分类属性return dataSet,labels"""
函数说明：计算给定数据集的经验熵（香农熵）
Parameters：dataSet：数据集
Returns：shannonEnt：经验熵
"""
def calcShannonEnt(dataSet):#返回数据集行数numEntries=len(dataSet)#保存每个标签（label）出现次数的字典labelCounts={}#对每组特征向量进行统计for featVec in dataSet:currentLabel=featVec[-1]                     #提取标签信息if currentLabel not in labelCounts.keys():   #如果标签没有放入统计次数的字典，添加进去labelCounts[currentLabel]=0labelCounts[currentLabel]+=1                 #label计数shannonEnt=0.0                                   #经验熵#计算经验熵for key in labelCounts:prob=float(labelCounts[key])/numEntries      #选择该标签的概率shannonEnt-=prob*log(prob,2)                 #利用公式计算return shannonEnt                                #返回经验熵#main函数
if __name__=='__main__':dataSet,features=creatDataSet()print(dataSet)print(calcShannonEnt(dataSet))

最终的到结果：

第0个特征的增益为0.083
第1个特征的增益为0.324
第2个特征的增益为0.420
第3个特征的增益为0.363
第0个特征的增益为0.252
第1个特征的增益为0.918
第2个特征的增益为0.474
{'做有意义的事': {0: {'有时间': {0: 'no', 1: 'yes'}}, 1: 'yes'}}

利用代码计算信息增益

from math import log"""
函数说明：创建测试数据集
Parameters：无
Returns：dataSet：数据集labels：分类属性
"""
def creatDataSet():# 数据集dataSet=[[0, 0, 0, 0, 'no'],[0, 0, 0, 1, 'no'],[0, 1, 0, 1, 'yes'],[0, 1, 1, 0, 'yes'],[0, 0, 0, 0, 'no'],[1, 0, 0, 0, 'no'],[1, 0, 0, 1, 'no'],[1, 1, 1, 1, 'yes'],[1, 0, 1, 2, 'yes'],[1, 0, 1, 2, 'yes'],[2, 0, 1, 2, 'yes'],[2, 0, 1, 1, 'yes'],[2, 1, 0, 1, 'yes'],[2, 1, 0, 2, 'yes'],[2, 0, 0, 0, 'no']]#分类属性labels=['时间','有时间','做有意义的事','心情是否愉悦']#返回数据集和分类属性return dataSet,labels"""
函数说明：计算给定数据集的经验熵（香农熵）
Parameters：dataSet：数据集
Returns：shannonEnt：经验熵
"""
def calcShannonEnt(dataSet):#返回数据集行数numEntries=len(dataSet)#保存每个标签（label）出现次数的字典labelCounts={}#对每组特征向量进行统计for featVec in dataSet:currentLabel=featVec[-1]                     #提取标签信息if currentLabel not in labelCounts.keys():   #如果标签没有放入统计次数的字典，添加进去labelCounts[currentLabel]=0labelCounts[currentLabel]+=1                 #label计数shannonEnt=0.0                                   #经验熵#计算经验熵for key in labelCounts:prob=float(labelCounts[key])/numEntries      #选择该标签的概率shannonEnt-=prob*log(prob,2)                 #利用公式计算return shannonEnt                                #返回经验熵"""
函数说明：计算给定数据集的经验熵（香农熵）
Parameters：dataSet：数据集
Returns：shannonEnt：信息增益最大特征的索引值
"""
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]#创建set集合{}，元素不可重复uniqueVals = set(featList)#经验条件熵newEntropy = 0.0#计算信息增益for value in uniqueVals:#subDataSet划分后的子集subDataSet = splitDataSet(dataSet, i, value)#计算子集的概率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"""
函数说明：按照给定特征划分数据集
Parameters：dataSet：待划分的数据集axis：划分数据集的特征value：需要返回的特征的值
Returns：shannonEnt：经验熵
"""
def splitDataSet(dataSet,axis,value):retDataSet=[]for featVec in dataSet:if featVec[axis]==value:reducedFeatVec=featVec[:axis]reducedFeatVec.extend(featVec[axis+1:])retDataSet.append(reducedFeatVec)return retDataSet#main函数
if __name__=='__main__':dataSet,features=creatDataSet()# print(dataSet)# print(calcShannonEnt(dataSet))print("最优索引值："+str(chooseBestFeatureToSplit(dataSet)))

最终结果：

第0个特征的增益为0.083
第1个特征的增益为0.324
第2个特征的增益为0.420
第3个特征的增益为0.363
最优索引值：2

对比我们自己计算的结果，发现结果正确！最优特征的索引值为2，也就是特征A3(做有意义的事）。

划分数据集

分类算法除了需要测量信息熵，还需要划分数据集，度量划分数据集的熵，以便判断当前是否正确的划分了数据集：

# 代码功能：划分数据集
def splitDataSet(dataSet,axis,value): #传入三个参数：待划分的数据集，划分数据集的特征，需要返回的特征的值retDataSet = [] #由于参数的链表dataSet我们拿到的是它的地址，也就是引用，直接在链表上操作会改变它的数值，所以我们新建一格链表来做操作for featVec in dataSet:if featVec[axis] == value: #如果某个特征和我们指定的特征值相等#除去这个特征然后创建一个子特征reduceFeatVec = featVec[:axis]reduceFeatVec.extend(featVec[axis+1:])#将满足条件的样本并且经过切割后的样本都加入到我们新建立的样本中retDataSet.append(reduceFeatVec)return retDataSet

选择最好的数据集划分方式 

def chooseBestFeatureToSplit(dataSet):# 获取我们样本集中的某一个样本的特征数（因为每一个样本的特征数是相同的，相当于这个代码就是我们可以作为分类依据的所有特征个数）我们的样本最后一列是样本所属的类别，所以要减去类别信息，在我们的例子中特征数就是2numFeatures = len(dataSet[0])-1#计算样本的初始香农熵baseEntropy = calcShannonEnt(dataSet)#初始化最大信息增益bestInfoGain =0.0#最佳划分特征bestFeature = -1for i in range(numFeatures):featList = [sample[i] for sample in dataSet] # 我们首先遍历整个数据集，首先得到第一个特征值可能的取值，然后把它赋值给一个链表，我们第一个特征值取值是[1,1,1,0,0],其实只有【1,0】两个取值uniqueVals = set(featList)newEntropy = 0.0for value in uniqueVals: #uniqueVals中保存的是我们某个样本的特征值的所有的取值的可能性subDataSet = splitDataSet(dataSet,i,value)prob = len(subDataSet)/float(len(dataSet))newEntropy += prob * calcShannonEnt(subDataSet)infoGain = baseEntropy - newEntropy# 计算出信息增益if(infoGain > bestInfoGain):bestInfoGain = infoGainbestFeature = ireturn bestFeature

信息增益率

鉴于信息增益的不足，我们希望对信息增益的计算做出一些调整，即：当特征值种类较多时，大幅度降低其重要性。调整后的信息增益，我们叫做信息增益率。

增益率：增益率是用前面的信息增益Gain(D, a)和属性a对应的"固有值"(intrinsic value)的比值来共同定义的。

1. Gain_Ratio 表示信息增益率
2. IV 表示特征的信息熵
3. 特征的信息增益 ➗ 特征的信息熵

 a. 如果某个特征的特征值种类较多，则其信息熵值就越大。即：特征值种类越多，除以的系数就越大。
b. 如果某个特征的特征值种类较小，则其信息熵值就越小。即：特征值种类越小，除以的系数就越小。

基尼系数 

基尼系数：表示在样本集合中一个随机选中的样本被分错的概率
基尼系数 = 样本被选中的概率 * 样本被分错的概率
基尼系数的性质与信息熵一样：度量随机变量的不确定度的大小；
G 越大，数据的不确定性越高；
G 越小，数据的不确定性越低；
G = 0，数据集中的所有样本都是同一类别；
分类问题中，假设D有K个类，样本点属于第k类的概率为pk, 则概率 分布的基尼值定义为：

 给定数据集D，属性a的基尼指数定义为：

ID3、C4.5、CART的区别

一、ID3
熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。

信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 **。也就是说，用属性 a 来划分训练集，得到的结果中纯度比较高。

ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。

二、C4.5

C4.5 克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。

C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。

三、CART

CART 与 ID3，C4.5 不同之处在于 CART 生成的树必须是二叉树。也就是说，无论是回归还是分类问题，无论特征是离散的还是连续的，无论属性取值有多个还是两个，内部节点只能根据属性值进行二分。

CART 的全称是分类与回归树。从这个名字中就应该知道，CART 既可以用于分类问题，也可以用于回归问题。

回归树中，使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化了平方误差。

要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。

分类树种，使用 Gini 指数最小化准则来选择特征并进行划分；

Gini 指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是，基尼指数是为了最小化误分类的概率。

信息增益 vs 信息增益比

之所以引入了信息增益比，是由于信息增益的一个缺点。那就是：信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项，解决了这个问题。

 gini指数 vs 熵

• Gini 指数的计算不需要对数运算，更加高效；
• Gini 指数更偏向于连续属性，熵更偏向于离散属性。

决策树的可视化 

决策树可视化的实现是利用在Matplotlib的代码实现的

from math import log
import operator
from matplotlib.font_manager import FontProperties
import matplotlib.pyplot as plt
"""
函数说明：获取决策树叶子节点的数目Parameters：myTree：决策树
Returns：numLeafs：决策树的叶子节点的数目
"""
def getNumLeafs(myTree):numLeafs=0firstStr=next(iter(myTree))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)if __name__=='__main__':dataSet,labels=createDataSet()featLabels=[]myTree=createTree(dataSet,labels,featLabels)print(myTree)

 

 总结

决策树算法主要包括三个部分：特征选择、树的生成、树的剪枝。常用算法有 ID3、C4.5、CART。决策树的生成。通常是利用信息增益最大、信息增益比最大、Gini 指数最小作为特征选择的准则。从根节点开始，递归的生成决策树。相当于是不断选取局部最优特征，或将训练集分割为基本能够正确分类的子集。决策树学习可能创建一个过于复杂的树，并不能很好的预测数据。也就是过拟合。修剪机制（现在不支持），设置一个叶子节点需要的最小样本数量，或者数的最大深度，可以避免过拟合。传统决策树算法基于启发式算法，例如贪婪算法，即每个节点创建最优决策。这些算法不能产生一个全家最优的决策树。对样本和特征随机抽样可以降低整体效果偏差。