1.决策树概念
决策树是通过一系列if-then规则对数据进行分类的过程，他提供一种在什么条件下会得到什么值的类似规则方法，决策树分为分类树和回归树，分类树对离散变量最决策树，回归树对连续变量做决策树。
如果不考虑效率等，那么样本所有特征的判断级联起来终会将某一个样本分到一个类终止块上。实际上，样本所有特征中有一些特征在分类时起到决定性作用，决策树的构造过程就是找到这些具有决定性作用的特征，根据其决定性程度来构造一个倒立的树–决定性作用最大的那个特征作为根节点，然后递归找到各分支下子数据集中次大的决定性特征，直至子数据集中所有数据都属于同一类。所以，构造决策树的过程本质上就是根据数据特征将数据集分类的递归过程，我们需要解决的第一个问题就是，当前数据集上哪个特征在划分数据分类时起决定性作用。
为了找到决定性的特征、划分出最好的结果，我们必须评估数据集中蕴含的每个特征，寻找分类数据集的最好特征。完成评估之后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个分支下的数据属于同一类型，则则该分支处理完成，称为一个叶子节点，即确定了分类。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。如何划分数据子集的算法和划分原始数据集的方法相同，直到所有具有相同类型的数据均在一个数据子集内（叶子节点）。
2.决策树的构造过程
一般包含三个部分
1、特征选择：特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准（信息增益id3、信息增益率c4.5、基尼cart），从而衍生出不同的决策树算法。
2、决策树生成： 根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。 树结构来说，递归结构是最容易理解的方式。
3、剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。
3：决策树的优缺点
决策树适用于数值型和标称型（离散型数据，变量的结果只在有限目标集中取值），能够读取数据集合，提取一些列数据中蕴含的规则。在分类问题中使用决策树模型有很多的优点，决策树计算复杂度不高、便于使用、而且高效，决策树可处理具有不相关特征的数据、可很容易地构造出易于理解的规则，而规则通常易于解释和理解。决策树模型也有一些缺点，比如处理缺失数据时的困难、过度拟合以及忽略数据集中属性之间的相关性等。
| ID3算法 |
C4.5算法 |
CART算法（Classification and Regression Tree） |
| 以信息增益为准则选择信息增益最大的属性。 2）ID3只能对离散属性的数据集构造决策树。 |
以信息增益率为准则选择属性；在信息增益的基础上对属性有一个惩罚，抑制可取值较多的属性，增强泛化性能。 1）在树的构造过程中可以进行剪枝，缓解过拟合； 2）能够对连续属性进行离散化处理（二分法）； 3）能够对缺失值进行处理； |
顾名思义，可以进行分类和回归，可以处理离散属性，也可以处理连续的。 |
4.ID3
ID3算法由Ross Quinlan发明，建立在“奥卡姆剃刀”的基础上：越是小型的决策树越优于大的决策树（be simple简单理论）。ID3算法中根据信息论的信息增益评估和选择特征，每次选择信息增益最大的特征做判断模块。ID3算法可用于划分标称型数据集，没有剪枝的过程，为了去除过度数据匹配的问题，可通过裁剪合并相邻的无法产生大量信息增益的叶子节点（例如设置信息增益阀值）。使用信息增益的话其实是有一个缺点，那就是它偏向于具有大量值的属性–就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性，而这样做有时候是没有意义的，另外ID3不能处理连续分布的数据特征，于是就有了C4.5算法。CART算法也支持连续分布的数据特征。
信源含有的信息量是信源发出的所有可能消息的平均不确定性，香农把信源所含有的信息量称为熵，是指每个符号所含有的信息量（自信息）的统计平均。
若X是一个离散随机变量，概率分布为
，那么X的熵为 :
一个随机变量的熵越大，其不确定性就越大，（不管是先验熵，后验熵，还是条件熵都是这样的）正确的估计其值的可能性就越小，越是不确定的随机变量越是需要更大的信息量来确定其值。
设有随机变量(X,Y),其联合概率分布为：
条件熵H(Y|X) 表示已知随机变量X的条件下随机变量Y的不确定性。
信息增益表示得知特征X的信息而使得Y的信息不确定性减少的程度。特征A对训练集D的信息增益
，定义为集合D的经验熵
与特征A给定条件下D的经验条件熵
ID3算法逻辑，《统计学习方法》李航，P63-64页：
根据ID3算法逻辑，Python实现代码如下：
calcShannonEnt()函数，计算传入数据的信息增益，其实就是根据传入数据最后一列y标签列进行统计计算概率，最后累加（注意经验熵前面带有负号）。
# 计算传入数据的信息增益
def calcShannonEnt(dataSet):
# 获得y中分类标签的唯一值
y_lables = np.unique(dataSet[: , -1])
y_counts=len(dataSet) # y总数据条数
y_p={} # y中每一个分类的概率，字典初始化为空，y分类数是不定的，按字典存储更方便取值
for y_lable in y_lables:
y_p[y_lable]=len(dataSet[dataSet[:, -1]==y_lable])/y_counts # y中每一个分类的概率（其实就是频率）
shannonEnt=0.0
for key in y_p.keys():
shannonEnt-=y_p[key]*np.log2(y_p[key])
return shannonEnt
chooseBestFeature()函数，按传入数据集，计算各列x的信息增益(ID3)或信息增益率(C4.5)，C4.5与ID3的区别只是除了 ， 其计算方法就是把这一列X当作Y计算一下信息增益，最后返回信息增益最大的列，以及每列的经验条件熵，Y列的经验熵。
# 计算信息增益，选择最好的特征划分数据集，即返回最佳特征下标及传入数据集各列的信息增益
def chooseBestFeature(dataSet,types='ID3'):
numFeatures = len(dataSet[0]) - 1 # 最后一列为y，计算x特征列数
baseEntropy = calcShannonEnt(dataSet) # 计算整个数据集D的经验熵:H(D)
bestFeature = -1 # 初始化参数，记录最优特征列i，下标从0开始
columnEntropy={} # 初始化参数，记录每一列x的信息增益 g(D,A)
for i in range(numFeatures): # 遍历所有x特征列
prob = {} #按x列计算各个分类的概率
newEntropy = 0.0
featList = list(dataSet[:,i]) # 取这一列x中所有数据，转换为list类型
prob=dict(Counter(featList)) # 使用Counter函数计算这一列x各特征数量
if types=='C45': # types等于C45
HaD=calcShannonEnt(dataSet[:,i].reshape((-1,1)))
for value in prob.keys(): # 循环这一列的特征，计算H(D|A)
prob[value]=prob[value]/len(featList) # 这一列x中每一个分类的概率（其实就是频率）
subDataSet = splitDataSet(dataSet, i, value) # 获取切分后的数据
newEntropy += prob[value] * calcShannonEnt(subDataSet) # 累加经验熵
infoGain = baseEntropy - newEntropy # 计算这一列数据的信息增益，g(D,A)=H(D)-H(D|A)
if types=='C45': # types等于C45
infoGain=infoGain/HaD
columnEntropy[i]=infoGain # 记录每一列x的信息增益，g(D,A)
bestFeature=max(columnEntropy,key=columnEntropy.get) # 找到最大信息增益对应的数据列
return bestFeature,columnEntropy,baseEntropy
createTree()函数，根据ID3算法逻辑实现迭代计算，返回最终的树模型，存储结构是dict类型。
def createTree(dataSet,features,types='ID3'):
"""
输入：训练数据集D，特征集A，阈值ε
输出：决策树T
"""
y_lables = np.unique(dataSet[: , -1])
#1、如果数据集D中的所有实例都属于同一类label（Ck），则T为单节点树，并将类label（Ck）作为该结点的类标记，返回T
if len(set(y_lables)) == 1:
return y_lables[0]
#2、若特征集A=空，则T为单节点，并将数据集D中实例树最大的类label（Ck）作为该节点的类标记，返回T
if len(dataSet[0]) == 1:
labelCount = {}
labelCount=dict(Counter(y_lables))
return max(labelCount,key=labelCount.get)
#3、否则，按ID3算法就计算特征集A中各特征对数据集D的信息增益，选择信息增益最大的特征bestFeature（Ag）
#4、如果beatFeature（Ag）的信息增益小于阈值ε，则置T为单节点树，并将数据集D中实例数最大的类label（Ck）作为该节点的类标记，返回T
#这里没有实现4
bestFeature,columnEntropy,baseEntropy=chooseBestFeature(dataSet,types)
bestFeatureLable = features[bestFeature] #最佳特征
decisionTree = {bestFeatureLable:{}} #构建树，以信息增益最大的特征bestFeature为子节点
del(features[bestFeature]) #该特征已最为子节点使用，则删除，以便接下来继续构建子树
#5、否则对beatFeature（Ag）的每一种可能ai，依Ag=ai将数据集D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子节点，由节点及其子节点构成树T，返回T
bestFeatureColumn = np.unique(dataSet[:,bestFeature])
for bfc in bestFeatureColumn:
subFeatures = features[:]
#6、对第i各子节点，以Di为训练集，以A-『Ag』为特征集，递归地调用步1-5，得到子树Ti，返回Ti
decisionTree[bestFeatureLable][bfc] = createTree(splitDataSet(dataSet, bestFeature, bfc), subFeatures,types)
return decisionTree
5.C4.5
C4.5是ID3的一个改进算法，继承了ID3算法的优点。C4.5算法用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足在树构造过程中进行剪枝；能够完成对连续属性的离散化处理；能够对不完整数据进行处理。C4.5算法产生的分类规则易于理解、准确率较高；但效率低，因树构造过程中，需要对数据集进行多次的顺序扫描和排序。也是因为必须多次数据集扫描，C4.5只适合于能够驻留于内存的数据集。
《统计学习方法》李航，P65页：
算法代码同C4.5，C4.5与ID3的区别只是除了 ，其他计算逻辑一致。注意，以上实现的ID3与C4.5均没有进行减枝操作，C4.5没有实现对连续变量的处理。
ID3与C4.5，输出的树如下：
使用ID3树，绘制的树图像如下：
使用测试数据预测结果如下：
以上ID3与C4.5完整代码如下：
# -*- coding: utf-8 -*-
"""
@Time : 2018/11/13 10:02
@Author : hanzi5
@Email : hanzi5@yeah.net
@File : dt_id3_c45.py
@Software: PyCharm
"""
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
import matplotlib
from collections import Counter
matplotlib.rcParams['font.family']='SimHei'
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-")
# 计算传入数据的信息增益
def calcShannonEnt(dataSet):
# 获得y中分类标签的唯一值
y_lables = np.unique(dataSet[: , -1])
y_counts=len(dataSet) # y总数据条数
y_p={} # y中每一个分类的概率，字典初始化为空，y分类数是不定的，按字典存储更方便取值
for y_lable in y_lables:
y_p[y_lable]=len(dataSet[dataSet[:, -1]==y_lable])/y_counts # y中每一个分类的概率（其实就是频率）
shannonEnt=0.0
for key in y_p.keys():
shannonEnt-=y_p[key]*np.log2(y_p[key])
return shannonEnt
#划分数据集
def splitDataSet(dataSet, i, value):
subDataSet=dataSet[list(dataSet[:,i]==value)] # 按照数据x第i列==value即可判断，不需要像《机器学习实战》书里写的那么复杂
subDataSet = np.array(subDataSet) # 强制转换为array类型
return np.delete(subDataSet,[i],1) # 每次去掉已经划分过的列，删除与否无所谓，calcShannonEnt是按y这一列计算信息增益的
# 计算信息增益，选择最好的特征划分数据集，即返回最佳特征下标及传入数据集各列的信息增益
def chooseBestFeature(dataSet,types='ID3'):
numFeatures = len(dataSet[0]) - 1 # 最后一列为y，计算x特征列数
baseEntropy = calcShannonEnt(dataSet) # 计算整个数据集D的经验熵:H(D)
bestFeature = -1 # 初始化参数，记录最优特征列i，下标从0开始
columnEntropy={} # 初始化参数，记录每一列x的信息增益 g(D,A)
for i in range(numFeatures): # 遍历所有x特征列
prob = {} #按x列计算各个分类的概率
newEntropy = 0.0
featList = list(dataSet[:,i]) # 取这一列x中所有数据，转换为list类型
prob=dict(Counter(featList)) # 使用Counter函数计算这一列x各特征数量
if types=='C45': # types等于C45
HaD=calcShannonEnt(dataSet[:,i].reshape((-1,1)))
for value in prob.keys(): # 循环这一列的特征，计算H(D|A)
prob[value]=prob[value]/len(featList) # 这一列x中每一个分类的概率（其实就是频率）
subDataSet = splitDataSet(dataSet, i, value) # 获取切分后的数据
newEntropy += prob[value] * calcShannonEnt(subDataSet) # 累加经验熵
infoGain = baseEntropy - newEntropy # 计算这一列数据的信息增益，g(D,A)=H(D)-H(D|A)
if types=='C45': # types等于C45
infoGain=infoGain/HaD
columnEntropy[i]=infoGain # 记录每一列x的信息增益，g(D,A)
bestFeature=max(columnEntropy,key=columnEntropy.get) # 找到最大信息增益对应的数据列
return bestFeature,columnEntropy,baseEntropy
def createTree(dataSet,features,types='ID3'):
"""
输入：训练数据集D，特征集A，阈值ε
输出：决策树T
"""
y_lables = np.unique(dataSet[: , -1])
#1、如果数据集D中的所有实例都属于同一类label（Ck），则T为单节点树，并将类label（Ck）作为该结点的类标记，返回T
if len(set(y_lables)) == 1:
return y_lables[0]
#2、若特征集A=空，则T为单节点，并将数据集D中实例树最大的类label（Ck）作为该节点的类标记，返回T
if len(dataSet[0]) == 1:
labelCount = {}
labelCount=dict(Counter(y_lables))
return max(labelCount,key=labelCount.get)
#3、否则，按ID3算法就计算特征集A中各特征对数据集D的信息增益，选择信息增益最大的特征bestFeature（Ag）
#4、如果beatFeature（Ag）的信息增益小于阈值ε，则置T为单节点树，并将数据集D中实例数最大的类label（Ck）作为该节点的类标记，返回T
#这里没有实现4
bestFeature,columnEntropy,baseEntropy=chooseBestFeature(dataSet,types)
bestFeatureLable = features[bestFeature] #最佳特征
decisionTree = {bestFeatureLable:{}} #构建树，以信息增益最大的特征bestFeature为子节点
del(features[bestFeature]) #该特征已最为子节点使用，则删除，以便接下来继续构建子树
#5、否则对beatFeature（Ag）的每一种可能ai，依Ag=ai将数据集D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子节点，由节点及其子节点构成树T，返回T
bestFeatureColumn = np.unique(dataSet[:,bestFeature])
for bfc in bestFeatureColumn:
subFeatures = features[:]
#6、对第i各子节点，以Di为训练集，以A-『Ag』为特征集，递归地调用步1-5，得到子树Ti，返回Ti
decisionTree[bestFeatureLable][bfc] = createTree(splitDataSet(dataSet, bestFeature, bfc), subFeatures,types)
return decisionTree
#对测试数据进行分类
def classify(testData, features, decisionTree):
for key in decisionTree:
index = features.index(key)
testData_value = testData[index]
subTree = decisionTree[key][testData_value]
if type(subTree) == dict:
result = classify(testData,features,subTree)
return result
else:
return subTree
####以下是用来画图的完全复制的《机器学习实战》第三章的内容，不感兴趣的可以略过#############################################
def getNumLeafs(myTree):
numLeafs = 0
firstStr = list(myTree.keys())[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes
numLeafs += getNumLeafs(secondDict[key])
else: numLeafs +=1
return numLeafs
def getTreeDepth(myTree):
maxDepth = 0
firstStr = list(myTree.keys())[0]#myTree.keys()[0]
secondDict = myTree[firstStr]
for key in secondDict.keys():
if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes
thisDepth = 1 + getTreeDepth(secondDict[key])
else: thisDepth = 1
if thisDepth > maxDepth: maxDepth = thisDepth
return maxDepth
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
xytext=centerPt, textcoords='axes fraction',
va="center", ha="center", bbox=nodeType, arrowprops=arrow_args )
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)
def plotTree(myTree, parentPt, nodeTxt):#if the first key tells you what feat was split on
numLeafs = getNumLeafs(myTree) #this determines the x width of this tree
#depth = getTreeDepth(myTree)
firstStr = list(myTree.keys())[0]#myTree.keys()[0] #the text label for this node should be this
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
for key in secondDict.keys():
if type(secondDict[key]).__name__=='dict':#test to see if the nodes are dictonaires, if not they are leaf nodes
plotTree(secondDict[key],cntrPt,str(key)) #recursion
else: #it's a leaf node print the leaf node
plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD
#if you do get a dictonary you know it's a tree, and the first element will be another dict
def createPlot(myTree):
fig = plt.figure(1, facecolor='white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
createPlot.ax1 = plt.subplot(111, frameon=False, **axprops) #no ticks
#createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses
plotTree.totalW = float(getNumLeafs(myTree))
plotTree.totalD = float(getTreeDepth(myTree))
plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;
plotTree(myTree, (0.5,1.0), '')
plt.show()
if __name__ == "__main__":
#读入数据，《统计学习方法》李航，P59，表5.1
df_data=pd.read_csv('D:/python_data/loan_application.csv')
features = list(df_data.columns[1:-1]) # x的表头
dataSet=np.array(df_data.values[:,1:]) # 数据处理为numpy.array类型，其实pandas.Dataframe类型更方便计算
# 结果验证，计算结果与《统计学习方法》李航，P62页一致。
bestFeature,columnEntropy,baseEntropy=chooseBestFeature(dataSet,'ID3')
print('H(D):',baseEntropy,'\ng(D,A):',columnEntropy)
bestFeature,columnEntropy,baseEntropy=chooseBestFeature(dataSet,'C45')
print('\nH(D):',baseEntropy,'\ng(D,A)/Ha(D):',columnEntropy)
dt_ID3 = createTree(dataSet, features,'ID3') #建立决策树，ID3
print( '\n1、decisonTree：ID3\n',dt_ID3)
features = list(df_data.columns[1:-1]) # x的表头
#dataSet=np.array(df_data.values[:,1:]) # 数据处理为numpy.array类型，其实pandas.Dataframe类型更方便计算
dt_C45 = createTree(dataSet, features,'C45') #建立决策树，C4.5
print( '\n2、decisonTree：C4.5\n',dt_C45)
# 画出决策树
createPlot(dt_ID3)
# 预测数据
features = list(df_data.columns[1:-1]) # x的表头
testData = ['青年', '否', '否','一般']
result = classify(testData, features, dt_ID3) #对测试数据进行分类
print( '\n3、预测数据，是否给',testData,'贷款：',result)
数据来源，《统计学习方法》李航，P59页，表5.1贷款申请样本数据表，复制到txt中另存为loan_application.csv。
ID,年龄,有工作,有自己的房子,信贷情况,类别
1,青年,否,否,一般,否
2,青年,否,否,好,否
3,青年,是,否,好,是
4,青年,是,是,一般,是
5,青年,否,否,一般,否
6,中年,否,否,一般,否
7,中年,否,否,好,否
8,中年,是,是,好,是
9,中年,否,是,非常好,是
10,中年,否,是,非常好,是
11,老年,否,是,非常好,是
12,老年,否,是,好,是
13,老年,是,否,好,是
14,老年,是,否,非常好,是
15,老年,否,否,一般,否
参考资料：
1、Machine-Learning-With-Python
2、《机器学习实战》Peter Harrington著
3、《机器学习》西瓜书，周志华著
4、 斯坦福大学公开课 ：机器学习课程
5、机器学习视频，邹博
6、《统计学习方法》李航
7、《机器学习实战》基于信息论的三种决策树算法(ID3,C4.5,CART)
8、决策树ID3算法–python实现