转载：
https://cuijiahua.com/blog/2017/11/ml_2_decision_tree_1.html
https://cuijiahua.com/blog/2017/11/ml_3_decision_tree_2.html
https://blog.csdn.net/jiaoyangwm/article/details/

一、决策树简介

1.1、解释
决策树是什么？决策树(decision tree)是一种基本的分类与回归方法。
举个通俗易懂的例子：判断是否给贷款，如下图所示的流程图就是一个决策树，长方形代表判断模块(decision block)，椭圆形成代表终止模块(terminating block)，表示已经得出结论，可以终止运行。从判断模块引出的左右箭头称作为分支(branch)，它可以达到另一个判断模块或者终止模块。

讯享网

1.2、组成
决策树由结点(node)和有向边(directed edge)组成。
结点有两种类型：内部结点(internal node)和叶结点(leaf node)。
内部结点表示一个特征或属性，叶结点表示一个类。
长方形和椭圆形都是结点。长方形的结点属于内部结点，椭圆形的结点属于叶结点，从结点引出的左右箭头就是有向边。而最上面的结点就是决策树的根结点(root node)。

1.3、通俗解释
决策树就是做判断，做出每个判断都对应不同的结果，一直做判断直到得到最总结果。

1.4、决策树术语
（1）香农熵
集合信息的度量方式称为香农熵或者简称为熵(entropy)，这个名字来源于信息论之父克劳德·香农。

图片中的 p(x_i) 指的是概率。期中n是分类的数目。熵越大，随机变量的不确定性就越大。

（2） 条件熵
条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，随机变量X给定的条件下随机变量Y的条件熵(conditional entropy)H(Y|X)，定义为X给定条件下Y的条件概率分布的熵对X的数学期望


图片中的 p(x_i) 指的是概率。

（3） 信息增益
信息增益是相对于特征而言的，信息增益越大，特征对最终的分类结果影响也就越大，我们就应该选择对最终分类结果影响最大的那个特征作为我们的分类特征。

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

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

1.5、决策树步骤

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

二、示例

判断是否能够给贷款

2.1、创建具体步骤

1. 整理数据：将原始数据整理为数据集、分类属性
2. 计算经验熵：按照公式计算
3. 计算最大信息增益：在经验熵的基础上，计算得到条件熵，用经验熵减去条件熵
4. 创建决策树：最大增益对应最优特征索引，递归创建
5. 使用决策树：利用决策树判断测试例子

2.2、提取特征向量

1. 年龄：0代表青年，1代表中年，2代表老年；
2. 有工作：0代表否，1代表是；
3. 有自己的房子：0代表否，1代表是；
4. 信贷情况：0代表一般，1代表好，2代表非常好；
5. 类别(是否给贷款)：no代表否，yes代表是。

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'] ] 

2.3、完整代码

讯享网# !/usr/bin/python # -*- coding: utf-8 -*-  # @Time : 2020/1/1 18:01  # @Author : ljf # @File : DT_test4.py from matplotlib.font_manager import FontProperties import matplotlib.pyplot as plt from math import log import operator def createDataSet(): """ 函数说明:创建测试数据集 Returns: dataSet: 数据集 labels: 分类属性 """ 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 # 返回数据集和分类属性 def calcShannonEnt(dataSet): """ 函数说明:计算给定数据集的经验熵(香农熵) Args: dataSet: 数据集 Returns: shannonEnt: 经验熵(香农熵) """ numEntires = len(dataSet) # 返回数据集的行数 labelCounts = { 
   } # 保存每个标签(Label)出现次数的字典 for featVec in dataSet: # 对每组特征向量进行统计 currentLabel = featVec[-1] # 提取标签(Label)信息 if currentLabel not in labelCounts.keys(): # 如果标签(Label)没有放入统计次数的字典,添加进去 labelCounts[currentLabel] = 0 labelCounts[currentLabel] += 1 # Label计数 shannonEnt = 0.0 # 经验熵(香农熵) for key in labelCounts: # 计算香农熵 prob = float(labelCounts[key]) / numEntires # 选择该标签(Label)的概率 shannonEnt -= prob * log(prob, 2) # 利用公式计算 return shannonEnt # 返回经验熵(香农熵) def splitDataSet(dataSet, axis, value): """ 函数说明:按照给定特征划分数据集 Args: dataSet: 待划分的数据集 axis: 划分数据集的特征 value: 需要返回的特征的值 Returns: retDataSet：去掉后的数据集 """ retDataSet = [] # 创建返回的数据集列表 for featVec in dataSet: # 遍历数据集 if featVec[axis] == value: reducedFeatVec = featVec[:axis] # 去掉axis特征 reducedFeatVec.extend(featVec[axis + 1:]) # 将符合条件的添加到返回的数据集 retDataSet.append(reducedFeatVec) return retDataSet # 返回划分后的数据集 def chooseBestFeatureToSplit(dataSet): """ 函数说明:选择最优特征 Args: dataSet: 数据集 Returns: bestFeature:信息增益最大的(最优)特征的索引值 """ 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 # 返回信息增益最大的特征的索引值 def majorityCnt(classList): """ 函数说明:统计classList中出现此处最多的元素(类标签) Args: classList: 类标签列表 Returns: sortedClassCount[0][0]: 出现此处最多的元素(类标签) """ classCount = { 
   } for vote in classList: # 统计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] # 返回classList中出现次数最多的元素 def createTree(dataSet, labels, featLabels): """ 函数说明:创建决策树 Args: dataSet: 训练数据集 labels: 分类属性标签 featLabels: 存储选择的最优特征标签 Returns: myTree: 决策树 """ 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 or len(labels) == 0: # 遍历完所有特征时返回出现次数最多的类标签 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: # 遍历特征，创建决策树。 subLabels = labels[:] myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels, featLabels) return myTree def getNumLeafs(myTree): """ 函数说明:获取决策树叶子结点的数目 Args: myTree: 决策树 Returns: numLeafs: 决策树的叶子结点的数目 """ numLeafs = 0 # 初始化叶子 # python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0] firstStr = next(iter(myTree)) secondDict = myTree[firstStr] # 获取下一组字典 for key in secondDict.keys(): if type(secondDict[key]).__name__ == 'dict': # 测试该结点是否为字典，如果不是字典，代表此结点为叶子结点 numLeafs += getNumLeafs(secondDict[key]) else: numLeafs += 1 return numLeafs def getTreeDepth(myTree): """ 函数说明:获取决策树的层数 Args: myTree: 决策树 Returns: maxDepth: 决策树的层数 """ maxDepth = 0 # 初始化决策树深度 # python3中myTree.keys()返回的是dict_keys,不在是list,所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0] firstStr = next(iter(myTree)) secondDict = myTree[firstStr] # 获取下一个字典 for key in secondDict.keys(): if type(secondDict[key]).__name__ == 'dict': # 测试该结点是否为字典，如果不是字典，代表此结点为叶子结点 thisDepth = 1 + getTreeDepth(secondDict[key]) else: thisDepth = 1 if thisDepth > maxDepth: maxDepth = thisDepth # 更新层数 return maxDepth def plotNode(nodeTxt, centerPt, parentPt, nodeType): """ 函数说明:绘制结点 Args: nodeTxt: 结点名 centerPt: 文本位置 parentPt: 标注的箭头位置 nodeType: 结点格式 Returns: 无 """ 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 ) def plotMidText(cntrPt, parentPt, txtString): """ 函数说明:标注有向边属性值 Args: cntrPt: 注释的位置 parentPt: 被注释点的位置 txtString: 标注的内容 Returns: 无 """ 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): """ 函数说明:绘制决策树 Args: myTree: 决策树(字典) parentPt: 标注的内容 nodeTxt: 结点名 Returns: 无 """ 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.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 def createPlot(inTree): """ 函数说明:创建绘制面板 Args: inTree: 决策树(字典) Returns: 无 """ fig = plt.figure(1, facecolor='white') # 创建fig fig.clf() # 清空fig axprops = 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() # 显示绘制结果 def classify(inputTree, featLabels, testVec): """ 函数说明:使用决策树分类 Args: inputTree: 已经生成的决策树 featLabels: 存储选择的最优特征标签 testVec: 测试数据列表，顺序对应最优特征标签 Returns: classLabel: 分类结果 """ firstStr = next(iter(inputTree)) # 获取决策树结点 secondDict = inputTree[firstStr] # 下一个字典 featIndex = featLabels.index(firstStr) for key in secondDict.keys(): if testVec[featIndex] == key: if type(secondDict[key]).__name__ == 'dict': classLabel = classify(secondDict[key], featLabels, testVec) else: classLabel = secondDict[key] return classLabel if __name__ == '__main__': dataSet, labels = createDataSet() featLabels = [] myTree = createTree(dataSet, labels, featLabels) print(myTree) createPlot(myTree) testVec = [1, 0] # 测试数据 result = classify(myTree, featLabels, testVec) if result == 'yes': print('放贷') if result == 'no': print('不放贷') 

2.4、结果
可以看到年龄、贷款信誉在例子中没出现，即没有关系。

三、总结

3.1、决策树主要算法

3.2、优缺点
（1）优点：

• 易于理解和解释，决策树可以可视化。
• 几乎不需要数据预处理。其他方法经常需要数据标准化，创建虚拟变量和删除缺失值。决策树还不支持缺失值。
• 使用树的花费（例如预测数据）是训练数据点(data points)数量的对数。
• 可以同时处理数值变量和分类变量。其他方法大都适用于分析一种变量的集合。
• 可以处理多值输出变量问题。
• 使用白盒模型。如果一个情况被观察到，使用逻辑判断容易表示这种规则。相反，如果是黑盒模型（例如人工神经网络），结果会非常难解释。
• 即使对真实模型来说，假设无效的情况下，也可以较好的适用。

（2）缺点：

• 决策树学习可能创建一个过于复杂的树，并不能很好的预测数据。也就是过拟合。修剪机制（现在不支持），设置一个叶子节点需要的最小样本数量，或者数的最大深度，可以避免过拟合。
• 决策树可能是不稳定的，因为即使非常小的变异，可能会产生一颗完全不同的树。这个问题通过decision trees with an ensemble来缓解。
• 学习一颗最优的决策树是一个NP-完全问题under several aspects of optimality and even for simple concepts。因此，传统决策树算法基于启发式算法，例如贪婪算法，即每个节点创建最优决策。这些算法不能产生一个全家最优的决策树。对样本和特征随机抽样可以降低整体效果偏差。
• 概念难以学习，因为决策树没有很好的解释他们，例如，XOR, parity or multiplexer problems.
  如果某些分类占优势，决策树将会创建一棵有偏差的树。因此，建议在训练之前，先抽样使样本均衡。

（3）决策树算法主要包括三个部分：特征选择、树的生成、树的剪枝。常用算法有 ID3、C4.5、CART。

• 特征选择。特征选择的目的是选取能够对训练集分类的特征。特征选择的关键是准则：信息增益、信息增益比、Gini 指数；
• 决策树的生成。通常是利用信息增益最大、信息增益比最大、Gini 指数最小作为特征选择的准则。从根节点开始，递归的生成决策树。相当于是不断选取局部最优特征，或将训练集分割为基本能够正确分类的子集；
• 决策树的剪枝。决策树的剪枝是为了防止树的过拟合，增强其泛化能力。包括预剪枝和后剪枝。