本文源自微信公众号【Python编程和深度学习】原文链接：[机器学习系列（二）决策树（Decision Tree）](https://mp.weixin.qq.com/s?__biz=MzUxNTY1MjMxNQ==&mid=2247484376&idx=1&sn=fe3b6099b03a176b934fb903fb38eda7&chksm=f9b22c6ccec5a57a036af50c60c67318f53b92ab5d3fcbf85afbed435f07f89af5fad946cef6&token=1404604522&lang=zh_CN#rd)，欢迎扫码关注鸭！  # 目录 [一、算法概述](#1)<br> [二、决策树的构建过程](#2)<br> [三、常用指标](#3)<br> [四、决策树停止分裂的条件](#4)<br> [五、决策树算法](#5)<br> [六、决策树的剪枝](#6)<br> [七、梯度提升决策树（GBDT）](#7)<br> [八、实现方法](#8)<br> <div id="1"></div> ##一、算法概述 决策树是一种树形结构的机器学习方法，是一种监督学习方法（Supervised Learning），在决策树的树形结构里，每个内部节点表示由一种特征属性引发的判断，每个节点下面的分支代表某个判断结果的输出，最后的叶子结点表示一种分类结果。 决策树有三种结点： 根节点：就是树的最顶端，最开始的那个节点； 内部节点：就是树中间的那些节点； 叶节点：就是树最底部的节点，也就是决策结果。 节点之间存在父子关系。比如根节点会有子节点，子节点会有子子节点，但是到了叶节点就停止了，叶节点不存在子节点。  <div id="2"></div> ##二、决策树的构建过程 步骤1：将所有的数据看成是一个节点，进入步骤2； 步骤2：从所有的数据特征中挑选一个最优数据特征对节点进行分割，使得分割后的子集有一个在当前条件下最好的分类，进入步骤3； 步骤3：生成若干孩子节点，对每一个孩子节点进行判断，如果满足停止分裂的条件，进入步骤4；否则，进入步骤2； 步骤4：设置该节点是子节点，其输出的结果为该节点数量占比最大的类别。 决策树的特点： 优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。 缺点：可能会产生过度匹配的问题（需要剪枝）。 适用数据类型：数值型和标称型 决策树在对中间结点进行分裂的时候，是选择最优分裂结果的属性进行分裂，决策树使用信息增益或者信息增益率作为选择属性的依据。信息增益表示划分数据前后信息发生的变化，获得信息增益最高的特征就是最好的选择。 <div id="3"></div> ##三、常用指标 **熵**：定义为信息的期望值，如果待分类的事物可能划分在多个类之中，则符号*x_i*的信息定义为： $$ l\left(x_{i}\right)=-\log _{2} p\left(x_{i}\right) $$ 其中，*p(x_i)*是选择该分类的概率。为了计算熵，需要计算所有类别所有可能值所包含的信息期望值，即为熵： $$ H=-\Sigma_{i=1}^{n} p\left(x_{i}\right) \log _{2} p\left(x_{i}\right) $$ 其中，*n*为分类数目，熵越大，随机变量的不确定性就越大。 **基尼不纯度**：GIINI指数在CART算法中使用，公式为： $$ \operatorname{Gini}=1-\sum_{i=1}^{n} p_{i}^{2} $$ 其中*p_i*表示类*i*的数量占比，当两类数量相等时，基尼值等于0.5 ； 当节点数据属于同一类时，基尼值等于0 。 基尼值越大，数据越不纯，基尼值越小，数据越纯。基尼指数的计算不需要对数运算，效率更高，更偏向连续属性，而熵更偏向离散属性。 **经验熵**：当熵中的概率*p*是由数据估计（如最大似然估计）得到的，则该熵为经验熵： $$ H(D)=-\Sigma \frac{\left|c_{k}\right|}{|D|} \log _{2} \frac{\left|c_{k}\right|}{|D|} $$ 训练数据集为D，|D|表示其样本容量。设有K个类*c_k*，k = 1,2,3,···,K，|CK|为属于类*c_k*的样本个数。 Python代码： ```python from math import log 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 #返回经验熵 ``` **条件熵(conditional entropy)*H(Y∣X)***表示在已知随机变量X的条件下随机变量*Y*的不确定性，定义*X*给定条件下*Y*的条件概率分布的熵对X的数学期望 $$ H(Y \mid X)=\sum_{i=1}^{n} p_{i} H\left(Y \mid X=x_{i}\right) $$ 这里 $$ p_{i}=P\left(X=x_{i}\right) $$ 当概率由数据估计（特别是极大似然估计）得到时，所对应的为经验条件熵。 **信息增益**是相对于特征而言的。所以，特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即： $$ g(D, A)=H(D)-H(D \mid A) $$ Python代码： ```python 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 ``` 一般地，熵H(D)与条件熵H(D|A)之差成为互信息(mutual information)。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。 **信息增益的缺点**： 在分类问题困难时，也就是说在训练数据集经验熵大的时候，信息增益值会偏大，反之信息增益值会偏小，且信息增益会倾向选择分支比较多的属性，单纯用信息增益来做决策难免会不准确，使用信息增益比可以对这个问题进行校正，这是特征选择的另一个标准。 **信息增益比**： 特征A对训练数据集D的信息增益比g_R(D,A)定义为其信息增益g(D,A)与训练数据集D的经验熵之比： $$ g_{R}(D, A)=\frac{g(D, A)}{H_A(D)} $$ 注意：其中的$H_A(D)$，对于样本集合D，将当前特征A作为随机变量（取值是特征A的各个特征值），求得的经验熵。 <div id="4"></div> ##四、决策树停止分裂的条件 如果要等到最后一个数据样本再结束分裂，这样的决策树会过于复杂，对于测试样本的预测准确率也不会高，因此需要提前停止分裂。 1） 最小结点数 当某个节点的数据量小于指定的最小节点数值时，停止分裂，这样避免对噪声数据的过度分裂，降低过拟合。 2） 熵的最小值 当熵过小时，数据复杂程度不大，没必要继续分裂，如果熵小于给定阈值，则停止分裂。 3） 决策树的深度 决策树的深度是所有叶子结点的最大深度，子结点比父结点的深度大1，当决策树的深度达到指定深度阈值，则停止分裂。 4） 特征使用情况 当所有的特征属性都用完时，没有可继续分裂的属性，直接将当前节点设置为叶子结点。 <div id="5"></div> ##五、决策树算法 **决策树**可以分为**分类树**（分裂结果为类别）和**回归树**（分裂结果为数值）。 **ID3算法**是采用**信息增益**来做特征选择的，在每个结点处，计算所有可能特征的信息增益，选择信息增益最大的特征蕞为节点分裂特征，递归处理之后的子结点直到分裂结束。 Python代码： ```python 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 ``` **C4.5算法**对ID3算法进行改进，信息增益比作为选择特征的标准，如果分裂太多信息增益率会降低。 **CART**也叫**分类回归树**，是**二叉树**，每个节点只能分为2个子结点，既可以分类也可以回归，CRART采用**GINI指数**作为选择特征的标准，和ID3一样也会存在过度分裂造成过拟合的问题。 前面介绍说决策树容易造成过拟合，也是过度匹配，而剪枝就是给决策树瘦身，不需要太多判断分支也能得到比较好的结果。下图从左到右分别表示分类问题的欠拟合，拟合和过拟合。  重点解释一下**过拟合**问题，如果决策树在构建时中间结点过多，决策树很复杂，所有训练数据都可以完美的做分类，决策模型过分依赖现有训练数据的特征，但当遇到测试样本时，错误率反而很高。 <div id="6"></div> ##六、决策树的剪枝 **剪枝**一般分两种方法： 第一种方法是**预剪枝**，就是在决策树的构建过程中进行剪枝，在构造的过程中对节点进行评估，如果对某个节点进行划分时不能带来准确性的提升（损失函数的降低），那么对这个节点进行划分就没有意义，这时就会把当前节点作为叶节点，不对其进行划分。 第二种方法是**后剪枝**，在生成决策树之后再进行剪枝。通常会从决策树的叶节点开始，逐层向上对每个节点进行评估。如果剪掉这个节点子树，与保留该节点子树在分类准确性上差别不大，或者剪掉该节点子树，能在验证集中带来准确性的提升，那么就可以把该节点子树进行剪枝。 <div id="7"></div> ##七、梯度提升决策树（GBDT） **梯度提升决策树**（Gradient Boosting Decision Tree或Gradient Boosting Regression Tree）作为机器学习领域的“屠龙刀”是一种基于**集成思想**的决策树。GBDT的核心在于每一棵树学的是之前所有树结论和的**残差**，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学，如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。这就是Gradient Boosting在GBDT中的意义。 GBDT主要的优点： 1）可以灵活处理各种类型的数据，包括连续值和离散值； 2）在相对少的调参时间情况下，预测的准确率也可以比较高； 3）使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。 <div id="8"></div> ##八、实现方法 在构建决策树模型时，除了自己写代码外还可以采用**sklearn**的决策树包和**weka**数据挖掘平台。 部分转自：https://blog.csdn.net/jiaoyangwm/article/details/79525237 https://www.cnblogs.com/molieren/articles/10664954.html