一、决策树的基本概念
顾名思义，决策树就是一棵树，一颗决策树包含一个根节点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶子结点的路径对应了一个判定测试序列。下面直接上个图，让大家看下决策树是怎样决策的（以二元分类为例），图中给定一个样例（表中数据）决策树的决策过程：

通过上述例子，构建过程的关键步骤是选择分裂属性，即年龄、长相、收入、公务员这4个属性的选择先后次序。分裂属性是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能的“纯”，即每个子集尽量都属于同一分类项。
二、决策树算法
1.信息增益
信息增益基于香浓的信息论，它找出的属性R具有这样的特点：以属性R分裂前后的信息增益比其他属性最大。这里信息的定义如下：
假定离散属性 有 个可能的取值，如果使用特征 来对数据集D进行划分，则会产生V个分支结点， 其中第v（小v）个结点包含了数据集D中所有在特征 上取值为 的样本总数，记为。因此可以根据上面信息熵的公式计算出信息熵，再考虑到不同的分支结点所包含的样本数量不同，给分支节点赋予权重，即样本数越多的分支节点的影响越大，因此，能够计算出特征 对样本集D进行划分所获得的“信息增益”:

一般而言，信息增益越大，则表示使用特征 对数据集划分所获得的“纯度提升”越大。所以信息增益可以用于决策树划分属性的选择，其实就是选择信息增益最大的属性，ID3算法就是采用的信息增益来划分属性。

在计算后，特征“色泽”的信息增益为

同理可以计算出其他特征的信息增益：

部分使用训练算法（使用的信息增益）

from math import log
import operator"""
函数说明：计算给定数据集的经验熵（香农熵）
Parameters：dataSet：数据集
Returns：shannonEnt：经验熵
Modify：2018-03-12"""
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：无
Returns：dataSet：数据集labels：分类属性
Modify：2018-03-13"""
def createDataSet():# 数据集dataSet=[[0, 0, 0, 0, 0， 0， 'no'],[0, 0, 0, 1, 0， 0， 'no'],[0, 1, 0, 1, 0， 1， 'yes'],[0, 1, 1, 0, 0， 1， 'yes'],[0, 0, 0, 0, 0， 1， 'no'],[1, 0, 0, 0, 1， 0， 'no'],[1, 0, 0, 1, 1， 0， 'no'],[1, 1, 1, 1, 0， 1， 'yes'],[1, 0, 1, 2, 1， 0， 'yes'],[1, 0, 1, 2, 0， 0， 'yes'],[2, 0, 1, 2, 1， 1， 'yes'],[2, 0, 1, 1, 2， 0， 'yes'],[2, 1, 0, 1, 0， 1， 'yes'],[2, 1, 0, 2, 1， 1， 'yes'],[2, 0, 0, 0, 1， 1， 'no']]#分类属性labels=['色泽','根蒂','敲声','纹理','脐部','触感']#返回数据集和分类属性return dataSet,labels"""
函数说明：按照给定特征划分数据集Parameters：dataSet:待划分的数据集axis：划分数据集的特征value：需要返回的特征值
Returns：无
Modify：2018-03-13"""
def splitDataSet(dataSet,axis,value):#创建返回的数据集列表retDataSet=[]#遍历数据集for featVec in dataSet:if featVec[axis]==value:#去掉axis特征reduceFeatVec=featVec[:axis]#将符合条件的添加到返回的数据集reduceFeatVec.extend(featVec[axis+1:])retDataSet.append(reduceFeatVec)#返回划分后的数据集return retDataSet"""
函数说明：计算给定数据集的经验熵（香农熵）
Parameters：dataSet：数据集
Returns：shannonEnt：信息增益最大特征的索引值
Modify：2018-03-13"""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"""
函数说明：统计classList中出现次数最多的元素（类标签）
Parameters：classList：类标签列表
Returns：sortedClassCount[0][0]：出现次数最多的元素（类标签）
Modify：2018-03-13"""
def majorityCnt(classList):classCount={}#统计classList中每个元素出现的次数for vote in classList:if vote not in classCount.keys():classCount[vote]=0classCount[vote]+=1#根据字典的值降序排列sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)return sortedClassCount[0][0]"""
函数说明：创建决策树Parameters:dataSet：训练数据集labels：分类属性标签featLabels：存储选择的最优特征标签
Returns：myTree：决策树
Modify：2018-03-13"""
def createTree(dataSet,labels,featLabels):#取分类标签（是否放贷：yes or no）classList=[example[-1] for example in dataSet]#如果类别完全相同，则停止继续划分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]#去掉重复的属性值uniqueVls=set(featValues)#遍历特征，创建决策树for value in uniqueVls: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)

结果

第0个特征的增益为0.083
第1个特征的增益为0.324
第2个特征的增益为0.420
第3个特征的增益为0.363
第0个特征的增益为0.252
第1个特征的增益为0.918
第2个特征的增益为0.474

2.信息增益率

信息增益比的定义为：

其中

属性 的“固有值”，属性 的可能取值数目越多（即V越大），则的值通常会越大。例如还是对西瓜数据集，IV(触感）=0.874(v=2)，IV(色泽)=1.580（V=3），IV（编号）=4.088（V=17）。但增益率也可能产生一个问题就是，对可取数值数目较少的属性有所偏好。因此，C4.5算法并不是直接选择使用增益率最大的候选划分属性，而是使用了一个启发式算法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益率最高的。

• C4.5的生成算法

与ID3算法相似，但是做了改进，将信息增益比作为选择特征的标准。

递归构建决策树：从数据集构造决策树算法所需的子功能模块工作原理如下：得到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此可能存在大于两个分支的数据集划分，第一次划分之后，数据将被向下传递到树分支的下一个节点，在此节点在此划分数据，因此可以使用递归的原则处理数据集。

3.基尼指数
基尼指数（Gini index）也可以用于选择划分特征，像CART（classification and regression tree）决策树（分类和回归都可以用）就是使用基尼指数来选择划分特征。基尼值可表示为：

反应了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此，
越小，则数据集D的纯度越高。则属性 a的基尼指数定义为：

信息增益 vs 信息增益比

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

既然这两个都可以表示数据的不确定性，不纯度。那么这两个有什么区别那？

Gini 指数的计算不需要对数运算，更加高效；
Gini 指数更偏向于连续属性，熵更偏向于离散属性。
公式的总结：
1、信息增益

信息熵：

分裂后的信息熵：

信息增益的定义为分裂前后，两个信息量只差：

2.增益比率

分裂比率：

增益比率定义为信息增益与分裂信息的比率：

3.基尼指数

分裂前的基尼指数：

属性R分裂后的基尼系数为：

Gini®增量最大的属性作为最佳分裂属性