决策树算法常用于解决分类问题，该方法的优势在于其数据形式非常容易理解。

概述

决策树（decision tree）是一类常见的机器学习方法．以二分类任务为例，我们希望从给定训练数据集学得一个模型用以对新示例进行分类，这个把样本 分类的任务，可看作对“当前样本属于正类吗？”这个问题的“决策”或“判定”过程。决策树是基于树结构来进行决策的，这是人类在面临决策问题时的一种很自然的处理机制。

例如：我们要对“这是好瓜吗？”这样的问题进行决策时，通常会进行一系列的判断或“子决策”：我们先看“它是什么颜色？”，如果是青绿色，我们再看它的根蒂是什么形态，如果是蜷缩，我们再看它敲起来是什么声音，最后得出最终决策：这是个好瓜，这个决策的过程如下图：

决策过程的最终结论与我们所希望的判定结果是对应的，决策过程中提出的每个判定问题都是对某个属性的测试，每个测试的结果导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内。

一棵决策树包含一个根结点、若干个内部结点和若干个叶结点，叶结点对应于决策结果，其他每个结点则对应于一个属性测试，每个结点包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列，决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树

决策树算法的基本流程

决策树算法从数据中提取出一系列规则，在创建规则的过程，就是决策树学习的过程。

选择最优划分属性（ID3）

从上面的流程中可以看出：当前数据集上选择哪个特征作为划分属性是该算法的关键。一般来说，我们希望随着划分过程的不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”越来越来。1970年，Quinlan J.R找到了用信息论中的熵来度量决策树的决策选择过程，这种方法的简洁和高效在当时就引起了轰动，并命名为ID3算法。

选择最优划分属性C4.5

当其中某个属性的取值在所有的样本上均不相同，此时计算它的信息增益其实为所有样本的信息熵，因为根据该属性划分分支，每个分支只有一个结点样本，这些分支的信息熵已经为0，样本纯度已经达到最高，此时就会选择该属性作为划分属性。所以信息增益准则对取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响，C4.5决策树算法不直接使用信息增益，而是利用增益率来选择最优划分属性.
增益率的定义如下：

需要注意，增益率准则对取值数目较少的属性有所偏好，因此c4.5不直接选择增益率最大的候选划分属性，而是使用一个启发式，先从候选划分属性中找出信息增益高于平均水平的属性，然后再从中选择增益率最高的。

CART决策树选择最优划分属性

CART决策树(Classification and Regression Tree)使用基尼指数来选择划分属性，数据集的纯度用基尼值来度量：

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

在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。

剪枝处理

剪枝为了避免过拟合，主要由于基于训练集划分的分支太多，在测试集上泛化性能不好，所以需要将一些分支剪掉。主要有两个基本策略“预剪枝”和“后剪枝”，前者是在生成决策树的过程中进行判断是否当前结点划分分支能否提高泛化性能，不能则停止划分，然后将该结点标记为叶节点。后者是在决策树生成后自底向上对非叶节点进行剪枝，判断是否将该结点对应子树替换为叶结点。

利用留出法，预留一部分用作验证集进行评估。
这部分不再赘述，可以参考西瓜书上的例子。

连续值处理

上面仅讨论了基于离散属性来生成决策树，对于连续属性由于其可能取值数目不定。此时需要将连续属性离散化，最简单的策略就是采用二分法对连续属性进行处理，这也是C4.5决策树算法中采用的机制。大致思路：对于某个连续属性，将其从小到大进行排序，然后选择每两个数的中位数作为候选划分点，大于该划分点的为一类，小于该划分点的为另一类，然后通过对这些候选划分点计算信息增益的情况，选择信息增益最大的候选划分点作为最终的划分点。该划分点对应的信息增益，为该连续属性作为划分属性的信息增益。需要注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可以作为其后代结点的划分属性。

缺失值处理

主要有两个问题：属性值缺失时如何进行划分属性的选择；划分属性确定后，样本在该属性上缺失值时，如何划分样本。

大致的解决思路：给每个样本赋予一个权重w，在原来计算某个属性的信息增益的基础上乘一个比例，该比例表示对于该属性无缺失值样本权重与所有样本权重的比值，计算信息增益针对无缺失值样本权重计算。对于第二个问题，在当前划分属性上，若样本在该属性上缺失值，让该缺失样本同时划分所有子节点，让样本的权值在与当前属性对应的子节点中调整为无缺失值样本在属性a上取值为v的样本所占的比例乘以该权值，其实该操作就是让同一个缺失样本以不同的概率划分到不同的子节点中。

详细的内容参考西瓜书。

决策树算法的优缺点

优点：计算复杂度不高，输出结果容易理解，可解释性，对中间值的缺失不敏感，可以处理不相关特征数据，在中等规模数据上以低难度取得较好的模型。
缺点：可能会产生过度匹配问题
使用数据类型：数值型和标称型

决策树分类示例

在信贷问题上的应用示例

下面通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类，即当新的客户提出贷款申请时，根据申请人的特征利用决策树决定是否批准贷款申请，样本数据如下表所示

对于上述样本数据，经过对属性值进行离散化处理，对于年龄离散化表示为[0, 1, 2]，其中0，1，2分别对应青年，中年与老年；对于有工作一栏离散化表示为[0, 1]，其中0，1分别对应无工作和有工作，同样对有房子这一属性进行相似的离散化；对于信贷情况按照上述方式离散化为[0, 1, 2] ，其中0，1，2分别对应一般，好，非常好；对于类别用yes和no表示。

对该问题利用复现的ID3算法构建决策树，得到的决策树最终为：

对结果进行验证，年龄这一列的数据，也就是特征A1，一共有三个类别，分别是：青年、中年和老年。其中年龄是青年的数据一共有5个，所以年龄是青年的数据在训练数据集出现的概率是三分之一。同理，年龄是中年和老年的数据在训练数据集出现的概率也都是三分之一。而年龄是青年的数据的最终得到贷款的概率为五分之二，因为在五个数据中，只有两个数据显示拿到了最终的贷款，同理，年龄是中年和老年的数据最终得到贷款的概率分别为五分之三、五分之四。所以计算年龄的信息增益，过程如下：

同理可以得到
因此利用属性A3是否有房子进行划分得到的信息增益最大，所以首先选择有房子作为划分属性。它将训练集D划分为两个子集D1(A3取值为“是”)和D2(A3取值为“否”)。由于D1只有同一类的样本点，所以它成为一个叶结点，结点的类标记为“是”。

对D2则需要从特征A1(年龄)，A2(有工作)和A4(信贷情况)中选择新的特征，计算各个特征的信息增益

根据计算，选择信息增益最大的特征A2(有工作)作为结点的特征。由于A2有两个可能取值，从这一结点引出两个子结点：一个对应“是”(有工作)的子结点，包含3个样本，它们属于同一类，所以这是一个叶结点，类标记为“是”；另一个是对应“否”(无工作)的子结点，包含6个样本，它们也属于同一类，所以这也是一个叶结点，类标记为“否”。这样就生成了一个决策树，该决策树只用了两个属性就构建好了。

在鱼类问题上的应用示例（含代码）

下面通过所给的训练数据学习一个海洋生物分类的决策树，根据海洋生物的特征利用决策树决定是否为鱼类，样本数据如下表所示

对于上述样本数据，经过对属性值进行离散化处理，用1表示“是”，0表示“否”。对于类别用“yes”与“no”表示是否为鱼类。

def createDataSet():dataSet = [[1, 1, 'yes'],[1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no']]labels = ['no surfacing', 'flippers']  # 特征的名称return dataSet, labels

生成决策树的主函数：
使用字典存储决策树mytree的结构;使用一个二维的list变量dataSet来保存数据集;使用一维的list变量labels来保存特征名称

def createTree(dataSet, labels):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]  # 得到对应的标签值myTree = {bestFeatLabel: {}}del (labels[bestFeat])  # 删掉labels[bestFeat],保证划分的数据集的属性索引和labels对应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)return myTree

其中majorityCnt 用来统计出现次数最大的类标签，chooseBestFeatureToSplit函数选择最大的信息增益来选择当前最优划分属性。

def majorityCnt(classList):classCount = {}for vote in classList:classCount[vote] = classCount.get(vote, 0) + 1# if vote not in classCount.keys():#     classCount[vote] = 0# classCount[vote] += 1sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)  # 从大到小排序return sortedClassCount[0][0]  # 返回出现次数最多的类别名称

def chooseBestFeatureToSplit(dataSet):# 特征数量numFeatures = len(dataSet[0]) - 1# 计算数据集的香农熵baseEntropy = calcShannonEnt(dataSet)# 信息增益bestInfoGain = 0.0# 最优特征的索引值bestFeature = -1# 遍历所有特征for i in range(numFeatures):# 获取dataSet的第i个所有特征存在featList这个列表中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# 比较得到最大信息增益if(infoGain > bestInfoGain):# 更新信息增益，找到最大的信息增益bestInfoGain = infoGain# 记录信息增益最大的特征的索引值bestFeature = i# 返回信息增益最大的特征的索引值return bestFeature

其中在chooseBestFeatureToSplit选择最优划分属性的函数中，利用calcShannonEnt计算信息熵，利用splitDataSet根据选择的属性划分数据集

# 计算给定数据集的香农熵
def calcShannonEnt(dataSet):numEntries = len(dataSet)labelCounts = {}for featVec in dataSet:currentLabel = featVec[-1]  # 获得标签# 构造存放标签的字典labelCounts[currentLabel] = labelCounts.get(currentLabel, 0) + 1# 计算香农熵shannonEnt = 0.0for key in labelCounts:prob = float(labelCounts[key]) / numEntriesshannonEnt -= prob * log(prob, 2)return 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  # 返回一个列表

最终构建的决策树如下：

构建好了决策树之后，则可以使用决策树进行分类

# 分类的函数，输入训练好的决策树，特征的label,以及待验证的数据，最后输出类别
def classify(inputTree, featLabels, testVec):firstStr = list(inputTree.keys())[0]# 获取下一组字典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]if 'classLabel' not in dir():return "maybe"return classLabel

完整代码

# coding=utf-8
'''
'''
from math import log
import operator
from matplotlib.font_manager import FontProperties
import matplotlib.pyplot as plt
from math import log
from collections import Counter
import pickledef createDataSet():dataSet = [[1, 1, 'yes'],[1, 1, 'yes'],[1, 0, 'no'],[0, 1, 'no'],[0, 1, 'no']]labels = ['no surfacing', 'flippers']  # 分类的属性return dataSet, labels# 计算给定数据的香农熵
def calcShannonEnt(dataSet):numEntries = len(dataSet)labelCounts = {}for featVec in dataSet:currentLabel = featVec[-1]  # 获得标签# 构造存放标签的字典labelCounts[currentLabel] = labelCounts.get(currentLabel, 0) + 1# 计算香农熵shannonEnt = 0.0for key in labelCounts:prob = float(labelCounts[key]) / numEntriesshannonEnt -= prob * log(prob, 2)return 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  # 返回一个列表# 选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):numFeature = len(dataSet[0]) - 1baseEntropy = calcShannonEnt(dataSet)bestInfoGain = 0.0beatFeature = -1for i in range(numFeature):featureList = [example[i] for example in dataSet]  # 获取样本中所有的第i个特征的值uniqueVals = set(featureList)  # 从列表中创建集合，得到不重复的所有可能取值，也就是第i个特征所有的可能取值集合newEntropy = 0.0for value in uniqueVals:subDataSet = splitDataSet(dataSet, i, value)  # 以i索引位置的特征为划分属性，value为特征的值来划分数据集prob = len(subDataSet) / float(len(dataSet))  # 特征值为value所占的样本比例newEntropy += prob * calcShannonEnt(subDataSet)  # 计算特征值为value子集的信息熵，并累加计算最终划分后的信息熵infoGain = baseEntropy - newEntropy  # 计算信息增益# 选择信息增益最大的划分属性if (infoGain > bestInfoGain):bestInfoGain = infoGainbestFeature = ireturn bestFeature# 递归构建决策树
def majorityCnt(classList):classCount = {}for vote in classList:classCount[vote] = classCount.get(vote, 0) + 1# if vote not in classCount.keys():#     classCount[vote] = 0# classCount[vote] += 1sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)  # 从大到小排序return sortedClassCount[0][0]  # 返回出现次数最多的类别名称# 创建树的函数代码
def createTree(dataSet, labels):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]  # 得到对应的标签值myTree = {bestFeatLabel: {}}del (labels[bestFeat])  # 删掉labels[bestFeat],保证划分的数据集的属性索引和labels对应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)return myTree# ==================下面是绘制决策树的函数==============def getNumLeafs(myTree):# 初始化叶子numLeafs = 0firstStr = list(myTree.keys())[0]# 获取下一组字典secondDict = myTree[firstStr]for key in secondDict.keys():# 测试该结点是否为字典，如果不是字典，代表此节点为叶子结点if type(secondDict[key]).__name__ == 'dict':numLeafs += getNumLeafs(secondDict[key])else:numLeafs += 1return numLeafsdef getTreeDepth(myTree):# 初始化决策树深度maxDepth = 0# python3中myTree.keys()返回的是dict_keys,不是list,所以不能用# myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0]# next() 返回迭代器的下一个项目 next(iterator[, default])firstStr = 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 = 1# 更新最深层数if thisDepth > maxDepth:maxDepth = thisDepth# 返回决策树的层数return maxDepthdef plotNode(nodeTxt, centerPt, parentPt, nodeType):# 定义箭头格式arrow_args = dict(arrowstyle="<-")# 设置中文字体font = FontProperties(fname=r"C:\Windows\Fonts\simsun.ttc", size=14)# 绘制结点createPlot.ax1创建绘图区# annotate是关于一个数据点的文本# nodeTxt为要显示的文本，centerPt为文本的中心点，箭头所在的点，parentPt为指向文本的点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):# 计算标注位置（箭头起始位置的中点处）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):# 设置结点格式boxstyle为文本框的类型，sawtooth是锯齿形，fc是边框线粗细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]# y偏移plotTree.yoff = plotTree.yoff - 1.0 / plotTree.totalDfor 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.totalDdef createPlot(inTree):# 创建figfig = plt.figure(1, facecolor="white")# 清空figfig.clf()axprops = dict(xticks=[], yticks=[])# 去掉x、y轴createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)# 获取决策树叶结点数目plotTree.totalW = float(getNumLeafs(inTree))# 获取决策树层数plotTree.totalD = float(getTreeDepth(inTree))# x偏移plotTree.xoff = -0.5 / plotTree.totalWplotTree.yoff = 1.0# 绘制决策树plotTree(inTree, (0.5, 1.0), '')# 显示绘制结果plt.show()# 分类的函数，输入训练好的决策树，特征的label,以及待验证的数据，最后输出类别
def classify(inputTree, featLabels, testVec):firstStr = list(inputTree.keys())[0]# 获取下一组字典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]if 'classLabel' not in dir():return "maybe"return classLabelif __name__ == "__main__":dataSet, labels = createDataSet()clabels = labels[:]myTree = createTree(dataSet, clabels)print(classify(myTree, labels, [1, 0]))  # 若测试集中出现了训练集中未出现的属性值，则异常，这个点需要改createPlot(myTree)