一、基本流程
首先，什么是决策树。
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表示一个特征或属性，叶节点表示一个类。
根据课件所说，决策树分类的思想就好像是找对象，现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
决策过程中提出的每个判定问题都是对某个属性的“测试”
每个测试的结果或是导出最终结论，或者导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内
从根结点到每个叶结点的路径对应了一个判定测试序列
决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树
决策树的结点情况：
（1）当前结点包含的样本全部属于同一类别C：
（2）当前属性集为空，或所有样本在所有属性上取值相同：
（3）当前结点包含的样本集合为空：
无需划分，叶子节点标记为类别C
当前结点标记为叶子节点，类别=该结点所含样本最多的类别
当前结点标记为叶子节点，类别=该结点的父节点所含样本最多的类别
决策树基本流程的结果图：
二、决策树的构造
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程。这一过程对应着对特征空间的划分，也对应着决策树的构建。
1） 开始：构建根节点，将所有训练数据都放在根节点，选择一个最优特征，按着这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
2） 如果这些子集已经能够被基本正确分类，那么构建叶节点，并将这些子集分到所对应的叶节点去。
3）如果还有子集不能够被正确的分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的节点，如果递归进行，直至所有训练数据子集被基本正确的分类，或者没有合适的特征为止。
4）每个子集都被分到叶节点上，即都有了明确的类，这样就生成了一颗决策树。
创建分支的伪代码 createBranch() 如下图所示：
检测数据集中每个子项是否属于同一类：
If so return 类标签：
Else
寻找划分数据集的最好特征
划分数据集
创建分支节点
for 每个划分的子集
调用函数createBranch()并增加返回结果到分支节点中
return 分支节点
其次使用决策树需要以下的过程：
收集数据：可以使用任何方法。比如想构建一个相亲系统，我们可以从媒婆那里，或者通过参访相亲对象获取数据。根据他们考虑的因素和最终的选择结果，就可以得到一些供我们利用的数据了。
准备数据：收集完的数据，我们要进行整理，将这些所有收集的信息按照一定规则整理出来，并排版，方便我们进行后续处理。
分析数据：可以使用任何方法，决策树构造完成之后，我们可以检查决策树图形是否符合预期。
训练算法：这个过程也就是构造决策树，同样也可以说是决策树学习，就是构造一个决策树的数据结构。
测试算法：使用经验树计算错误率。当错误率达到了可接收范围，这个决策树就可以投放使用了。
使用算法：此步骤可以使用适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。
三、信息增益
划分数据集的大原则是：将无序数据变得更加有序，但是各种方法都有各自的优缺点，信息论是量化处理信息的分支科学，在划分数据集前后信息发生的变化称为信息增益，获得信息增益最高的特征就是最好的选择，所以必须先学习如何计算信息增益，集合信息的度量方式称为香农熵，或者简称熵。
希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类，即当新的客户提出贷款申请时，根据申请人的特征利用决策树决定是否批准贷款申请。
特征选择就是决定用哪个特征来划分特征空间。比如，我们通过上述数据表得到两个可能的决策树，分别由两个不同特征的根结点构成。
图 (a) 所示的根结点的特征是年龄，有3个取值，对应于不同的取值有不同的子结点。
图 (b) 所示的根节点的特征是工作，有2个取值，对应于不同的取值有不同的子结点。两个决策树都可以从此延续下去。
问题是：究竟选择哪个特征更好些？这就要求确定选择特征的准则。
直观上，如果一个特征具有更好的分类能力，或者说，按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。
信息增益就能够很好地表示这一直观的准则。
什么是信息增益呢？在划分数据集之前之后信息发生的变化成为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。
熵定义为信息的期望值，如果待分类的事物可能划分在多个类之中，则符号 xi的信息定义为：l(x i)=−log 2p(x i)
其中，p ( x i ) p(x_i)p(x i)是选择该分类的概率。
其中，n nn为分类数目，熵越大，随机变量的不确定性就越大。
当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。
什么叫由数据估计？比如有10个数据，一共有两个类别，A类和B类。其中有7个数据属于A类，则该A类的概率即为十分之七。
其中有3个数据属于B类，则该B类的概率即为十分之三。浅显的解释就是，这概率是我们根据数据数出来的。
我们定义贷款申请样本数据表中的数据为训练数据集D，则训练数据集D的经验熵为H(D)，|D|表示其样本容量，及样本个数。
设有K个类Ck，k = 1,2,3,···,K，|Ck|为属于类Ck的样本个数，这经验熵公式可以写为：
根据此公式计算经验熵H(D)，分析贷款申请样本数据表中的数据。最终分类结果只有两类，即放贷和不放贷。根据表中的数据统计可知，在15个数据中，9个数据的结果为放贷，6个数据的结果为不放贷。所以数据集D的经验熵H(D)为：
经过计算可知，数据集D的经验熵H(D)的值为0.971。
在理解信息增益之前，要明确---条件熵
信息增益表示得知特征 X 的信息而使得类Y的信息不确定性减少的程度。
条件熵 H ( Y ∣ X ) H(Y|X)H(Y∣X) 表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵 (conditional entropy) H(Y|X)，定义X给定条件下Y的条件概率分布的熵对X的数学期望：
H(Y|X)=\sum_{i=1}^n piH(Y|X=x_i)
其中，p_i=P(X=x_i)
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的分别为经验熵和经验条件熵，此时如果有0概率，令 0log0=0
信息增益：信息增益是相对于特征而言的。所以，特征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的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D的经验熵之比：
gR(D,A)= H(D)g/(D,A)
四、生成决策树
1.ID3算法
ID3算法的核心是在决策树各个结点上对应信息增益准则选择特征，递归地构建决策树。
具体方法是：
1）从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征。
2）由该特征的不同取值建立子节点，再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止；
3）最后得到一个决策树。
ID3相当于用极大似然法进行概率模型的选择
算法步骤：
分析：
上面已经求得，特征A3（有自己的房子）的信息增益最大，所以选择A3为根节点的特征
它将训练集D划分为两个子集D1（A3取值为“是”）D2（A3取值为“否”）
由于D1只有同一类的样本点，所以它成为一个叶结点，结点的类标记为“是”。
对D2则需要从特征A1(年龄)，A2(有工作)和A4(信贷情况)中选择新的特征，计算各个特征的信息增益：
g(D2,A1)=H(D2)−H(D2∣A1)=0.251
g(D2,A2)=H(D2)−H(D2∣A2)=0.918
g(D2,A3)=H(D2)−H(D2∣A3)=0.474
根据计算，选择信息增益最大的A2作为节点的特征，由于其有两个取值可能，所以引出两个子节点：
①对应“是”（有工作），包含三个样本，属于同一类，所以是一个叶子节点，类标记为“是”
②对应“否”（无工作），包含六个样本，输入同一类，所以是一个叶子节点，类标记为“否”
这样就生成一个决策树，该树只用了两个特征（有两个内部节点），生成的决策树如下图所示：
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]=0
labelCounts[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, '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:待划分的数据集
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]=0
classCount[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 myTree
if name=='main':
dataSet,labels=createDataSet()
featLabels=[]
myTree=createTree(dataSet,labels,featLabels)
print(myTree)
结果：