决策树（Decision Tree）是一种非参数的有监督学习方法，它能够从一系列有特征和标签的数据中总结出决策规则，并用树状图的结构来呈现这些规则，以解决分类和回归问题。决策树算法容易理解，适用各种数据，在解决各种问题时都有良好表现，尤其是以树模型为核心的各种集成算法，比如随机森林，xgboost等，在各个行业和领域都有广泛的应用。
本文对决策树算法原理做一个总结，包括ID3， C4.5，CART的算法思想，以及scikit-learn中决策树算法的实现和调参小结。
1.决策树的ID3算法
决策树算法的核心是要解决两个问题：1）如何从数据表中找出最佳节点和最佳分枝？ 2）如何让决策树停止生长，防止过拟合？
ID3算法是一个贪心算法，在每一个节点种用信息增益大小来判断当前节点应该用什么特征来构建决策树，用计算出的信息增益最大的特征来建立决策树的当前节点。通过实现局部最优来达到接近全局最优结果。
（1）熵
决策树的ID3算法用信息论中的熵来度量决策树的决策选择过程。熵度量了事物的不确定性，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：
[HX) = -sumlimits_{i=1}^{n}p_i logp_i
]
其中n代表X的n种不同的离散取值。而pi代表了X取值为i的概率。
（2）条件熵
条件熵类似于条件概率,它度量了X在知道特征Y以后剩下的不确定性。表达式如下：
[HX|Y) = sumlimits_{i=1}^{n}p_iHX|Y=y_i)
]
其中n代表特征Y的n种不同的取值，而pi代表Y取值为i时的概率。
（3）信息增益
我们刚才提到HX)度量了X的不确定性，而条件熵HX|Y)度量了我们在知道Y以后X剩下的不确定性，那么HX)-HX|Y)呢？
从上面的描述大家可以看出，它度量了X在知道Y以后不确定性减少程度，信息论中称为互信息，在决策树ID3算法中叫做信息增益，记为IX,Y)。
[IX,Y) = HX)-HX|Y)
]
若某个特征的信息增益越大，则越适合用于分类。因此ID3算法就是用信息增益大小来判断当前节点应该用什么特征来构建决策树，用计算出的信息增益最大的特征来建立决策树的当前节点。
这里我们举一个信息增益计算的具体的例子。比如我们有15个样本D，输出为0或者1。其中有9个输出为1， 6个输出为0。 样本中有个特征A，取值为A1，A2和A3。在取值为A1的样本的输出中，有3个输出为1， 2个输出为0，取值为A2的样本输出中,2个输出为1,3个输出为0， 在取值为A3的样本中，4个输出为1，1个输出为0.
样本D的熵为：$$HD) = -frac{9}{15}log_2frac{9}{15} + frac{6}{15}log_2frac{6}{15}) = 0.971$$
样本D在特征下的条件熵为： $$egin{align} HD|A) &= frac{5}{15}HD1) + frac{5}{15}HD2) + frac{5}{15}HD3) \
&= -frac{5}{15}frac{3}{5}log_2frac{3}{5} + frac{2}{5}log_2frac{2}{5}) – frac{5}{15}frac{2}{5}log_2frac{2}{5} + frac{3}{5}log_2frac{3}{5}) -frac{5}{15}frac{4}{5}log_2frac{4}{5} + frac{1}{5}log_2frac{1}{5}) = 0.888 end{align}$$
对应的信息增益为: $$ID,A) = HD) – HD|A) = 0.083$$
4) ID3算法步骤
下面我们看看具体算法过程大概是怎么样的。
输入的是m个样本，样本输出集合为D，每个样本有n个离散特征，特征集合即为A，输出为决策树T。
算法的过程为：
1)初始化信息增益的阈值ϵ
2）判断样本是否为同一类输出Di，如果是则返回单节点树T。标记类别为Di
3) 判断特征是否为空，如果是则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
4）计算A中的各个特征（一共n个）对输出D的信息增益，选择信息增益最大的特征Ag
5) 如果Ag的信息增益小于阈值ϵ，则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
6）否则，按特征Ag的不同取值Agi将对应的样本输出D分成不同的类别Di。每个类别产生一个子节点。对应特征值为Agi。返回增加了节点的数T。
7）对于所有的子节点，令D=Di,A=A−{Ag}递归调用2-6步，得到子树Ti并返回。
5) ID3算法的不足
ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。
无法直接处理连续型的特征
用信息增益作为标准容易偏向于取值较多的特征。在相同条件下，取值比较多的特征比取值少的特征信息增益大。
对于缺失值的情况没有做考虑
没有考虑过拟合的问题
ID3 算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是C4.5算法。
2.决策树的C4.5算法
上一节讲到ID3算法有四个主要的不足，C4.5算法针对性的做了改进。
（1）第一个问题，不能处理连续特征
C4.5的思路是将连续的特征离散化。比如m个样本的连续特征A有m个，从小到大排列为a1,a2,…,am,则C4.5取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点Ti表示为：Ti=ai+ai+1)/2。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为at,则小于at的值为类别1，大于at的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。
（2) 第二个问题，信息增益作为标准容易偏向于取值较多的特征的问题
我们引入一个信息增益比的变量I_RX,Y))，它是信息增益和特征熵的比值。表达式如下：
[I_RD,A) = frac{IA,D)}{H_AD)}
]
其中D为样本特征输出的集合，A为样本特征，对于特征熵HAD), 表达式如下：
[H_AD) = -sumlimits_{i=1}^{n}frac{|D_i|}{|D|}log_2frac{|D_i|}{|D|}
]
其中n为特征A的类别数， Di为特征A的第i个取值对应的样本个数。|D|为样本个数。
特征数越多的特征对应的特征熵越大，它作为分母，可以当作一个惩罚项，可以校正信息增益容易偏向于取值较多的特征的问题。
（3) 第三个缺失值处理的问题
主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择特征，二是选定了特征，对于在该特征上缺失特征的样本的处理。
对于第一个子问题，之前的算法是选择信息增益最大的特征作为最优划分属性，那么对于有缺失值的特征，其信息增益就是无缺失值样本所占的比例乘以无缺失值样本子集的信息增益。
对于第二个子问题，将缺失值样本按不同的权重划分到了所有分支中，而权重则等于无缺失值样本在每个分支中所占的比例。
4)第四个过拟合问题
C4.5引入了正则化系数进行初步的剪枝。具体方法在讲CART的时候会讨论剪枝的思路。
除了上面的4点，C4.5和ID3的思路区别不大。
（5) C4.5算法的不足
C4.5虽然改进或者改善了ID3算法的几个主要的问题，仍然有优化的空间。
C4.5的由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。
C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。CART树的减枝思路，主要采用的是后剪枝加上交叉验证选择最合适的决策树。
这4个问题在CART树里面部分加以了改进。scikit-learn的决策树使用的也是CART算法。
3.决策树的CART算法
（1）CART分类树算法的特征选择方法的改进
我们知道，在ID3算法中我们使用了信息增益来选择特征，信息增益大的优先选择。在C4.5算法中，采用了信息增益比来选择特征，以减少信息增益容易选择特征值多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的，这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢？
CART分类树算法使用基尼系数来代替信息增益比，基尼系数代表了模型的不纯度，基尼系数越小，则不纯度越低，特征越好。这和信息增益比)是相反的。 具体的，在分类问题中，假设有K个类别，第k个类别的概率为pk, 则基尼系数的表达式为：
[Ginip) = sumlimits_{k=1}^{K}p_k1-p_k) = 1- sumlimits_{k=1}^{K}p_k^2
]
换个方式阐述，对于给定的样本集合D,假设有K个类别, 第k个类别的数量为Ck,则样本D的基尼系数表达式为：
[GiniD) = 1-sumlimits_{k=1}^{K}frac{|C_k|}{|D|})^2
]
特别的，对于样本集合D,如果根据特征A的某个值a,把D分成D1和D2两部分，则在特征A的条件下，D的基尼系数表达式为：
[GiniD,A) = frac{|D_1|}{|D|}GiniD_1) + frac{|D_2|}{|D|}GiniD_2)
]
大家可以比较下基尼系数表达式和熵模型的表达式，二次运算是不是比对数简单很多？尤其是二类分类的计算，更加简单。但是简单归简单，和熵模型的度量方式比，基尼系数对应的误差有多大呢？对于二类分类，基尼系数和熵之半的曲线如下：
从上图可以看出，基尼系数和熵之半的曲线非常接近，仅仅在45度角附近误差稍大。因此，基尼系数可以做为熵模型的一个近似替代。
而CART分类树算法就是使用的基尼系数来选择决策树的特征。同时，为了进一步简化，CART分类树算法每次仅仅对某个特征的值进行二分，而不是多分，这样CART分类树算法建立起来的是二叉树，而不是多叉树。这样一可以进一步简化基尼系数的计算，二可以建立一个更加优雅的二叉树模型。
2)CART分类树算法对于连续特征和离散特征处理的改进
对于CART分类树连续值的处理问题，其思想和C4.5是相同的，都是将连续的特征离散化。唯一的区别在于在选择划分点时的度量方式不同，C4.5使用的是信息增益比，则CART分类树使用的是基尼系数。
对于CART分类树离散值的处理问题，采用的思路是不停的二分离散特征。
回忆下ID3或者C4.5，如果某个特征A被选取建立决策树节点，如果它有A1,A2,A3三种类别，我们会在决策树上一下建立一个三叉的节点。这样导致决策树是多叉树。但是CART分类树使用的方法不同，他采用的是不停的二分，还是这个例子，CART分类树会考虑把A分成{A1}和{A2,A3}, {A2}和{A1,A3}, {A3}和{A1,A2}三种情况，找到基尼系数最小的组合，比如{A2}和{A1,A3},然后建立二叉树节点，一个节点是A2对应的样本，另一个节点是{A1,A3}对应的节点。同时，由于这次没有把特征A的取值完全分开，后面我们还有机会在子节点继续选择到特征A来划分A1和A3。这和ID3或者C4.5不同，在ID3或者C4.5的一棵子树中，离散特征只会参与一次节点的建立。
3) CART分类树建立算法的具体流程
算法输入是训练集D，基尼系数的阈值，样本个数阈值。
输出是决策树T。
我们的算法从根节点开始，用训练集递归的建立CART树。
1) 对于当前节点的数据集为D，如果样本个数小于阈值或者没有特征，则返回决策子树，当前节点停止递归。
2) 计算样本集D的基尼系数，如果基尼系数小于阈值，则返回决策树子树，当前节点停止递归。
3) 计算当前节点现有的各个特征的各个特征值对数据集D的基尼系数，对于离散值和连续值的处理方法和基尼系数的计算见上一节。缺失值的处理方法和上篇的C4.5算法里描述的相同。
4) 在计算出来的各个特征的各个特征值对数据集D的基尼系数中，选择基尼系数最小的特征A和对应的特征值a。根据这个最优特征和最优特征值，把数据集划分成两部分D1和D2，同时建立当前节点的左右节点，做节点的数据集D为D1，右节点的数据集D为D2.
5) 对左右的子节点递归的调用1-4步，生成决策树。
对于生成的决策树做预测的时候，假如测试集里的样本A落到了某个叶子节点，而节点里有多个训练样本。则对于A的类别预测采用的是这个叶子节点里概率最大的类别。
（4) CART算法的不足
CART算法做了很多的改进，但依然有一些缺点：
1）应该大家有注意到，无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1，这里不多介绍。
2）如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。
4.决策树算法小结
上面我们对CART算法做了一个详细的介绍，CART算法相比C4.5算法的分类方法，采用了简化的二叉树模型，同时特征选择采用了近似的基尼系数来简化计算。当然CART树最大的好处是还可以做回归模型，这个C4.5没有。下表给出了ID3，C4.5和CART的一个比较总结。
1) ID3，C4.5和CART三种算法的比较
（2）决策树算法的优缺点
终于到了最后的总结阶段了，这里我们不再纠结于ID3, C4.5和 CART，我们来看看决策树算法作为一个大类别的分类回归算法的优缺点。
（1）优点
模型易解释，可以把树可视化
数据预处理较简单，特征无需归一化，不需要对空值进行填充
预测时成本较低，速度较快
能用于分类也可以用于回归
可处理多输出问题
（2）缺点
决策树容易过拟合，需要剪枝
决策树的学习基于贪婪算法，靠局部最优（每个节点最优）来达到全局最优。可用集成算法改进。
如果标签中的某些类占主导地位，决策树学习者会创建偏向主导类的树。因此，建议在拟合决策树之前平衡 数据集。
5.代码实现与调参
5.1 sklearn 中的决策树
sklearn.tree 模块
sklearn中决策树的类都在”tree“这个模块之下。这个模块总共包含五个类：
5.2 DecisionTreeClassifier与红酒数据集
接下来主要介绍决策树的分类树。参数和接口如下：
class sklearn.tree.DecisionTreeClassifier criterion=’gini’, splitter=’best’, max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, min_impurity_split=None, class_weight=None, presort=False)
本节将会介绍分类树DecisionTreeClassifier和用决策树绘图（export_graphviz）的基础。主要包括分类树的八个参数，一个属性，四个接口，以及绘图所用的代码。
八个参数：一个分枝准则参数（Criterion），两个随机性相关的参数（random_state，splitter），五个剪枝参数（max_depth, min_samples_split，min_samples_leaf，max_feature，min_impurity_decrease）
一个属性：feature_importances_
四个接口：fit，score，apply，predict
重要参数
1) 寻找最佳节点和分枝的衡量指标 ——criterion
Criterion这个参数正是用来决定不纯度的计算方法的。sklearn提供了两种选择：
1）输入”entropy“，使用信息熵（Entropy）,sklearn实际计算的是基于信息熵的信息增益Information Gain)，即父节点的信息熵和子节点的信息熵之差。
2）输入”gini“，使用基尼系数（Gini Impurity)，默认值
在实际使用中，信息熵和基尼系数的效果基本相同。但是比起基尼系数，信息熵对不纯度更加敏感，对不纯度的惩罚更强，决策树的生长会更加“精细”。
因此：
通常就使用基尼系数 ，当维度低，数据比较清晰的时候，信息熵和基尼系数没区别
当数据维度很大，噪音很大时使用基尼系数 ，因为用信息熵容易过拟合
当决策树的拟合程度不够的时候，使用信息熵
（2） 分枝随机模式控制参数 —— random_state & splitter
sklearn在训练决策树寻找最优节点和最优分枝的时候，使用了集成算法。即在每次分枝时，不使用全部特征，而是随机选取一部分特征，从中选取不纯度相关指标最优的作为分枝用的节点。这样，从一组数据集中建不同的树，最后取最优的那颗树。
因此，因为特征选择的随机性，使得决策树可能每次训练的树都会稍有不同。为了增加模型训练的稳定性，sklearn设置了随机模式的参数。
random_state
用来设置分枝中的随机模式的参数，默认None。输入任意整数，会一直长出同一棵树，让模型稳定下来。
在高维度时随机性会表现更明显；低维度的数据 （比如鸢尾花数据集），随机性几乎不会显现。
splitter
用来控制决策树中的随机选项的，有两种输入值:
输入”best”，决策树在分枝时虽然随机，但是还是会 优先选择更重要的特征进行分枝（重要性可以通过属性feature_importances_查看)
输入“random”，决策树在 分枝时会更加随机，可以防止过拟合。 树会因为含有更多的不必要信息而更深更大，并因这些不必要信息而降低对训练集的拟合。当你预测到你的模型会过拟合，用这两个参数来帮助你降低树建成之后过拟合的可能性。当然，树一旦建成，我们依然是使用剪枝参数来防止过拟合。
3）剪枝参数 —— max_depth & min_samples_leaf & min_samples_split
在不加限制的情况下，一棵决策树会生长到衡量不纯度的指标最优，或者没有更多的特征可用为止。这样的决策树 往往会过拟合。为了让决策树有更好的泛化性，我们要对决策树进行剪枝。剪枝策略对决策树的影响巨大，正确的剪枝策略是优化 决策树算法的核心。
sklearn为我们提供了不同的剪枝策略：
max_depth
限制树的最大深度，超过设定深度的树枝全部剪掉，能有效防止过拟合
用得最广泛的剪枝参数，在高维度低样本量时非常有效。
实际使用时，建议从=3开始尝试，看看拟合的效 果再决定是否增加设定深度。
min_samples_leaf
min_samples_leaf 会限定一个节点在分枝后的每个子节点都必须包含至少min_samples_leaf个训练样本，否则分枝就不会发生。或者分枝会朝着满足每个子节点都包含min_samples_leaf个样本的方向去发生。
一般搭配max_depth使用，在回归树中有神奇的效果，可以让模型变得更加平滑。
一般来说，建议从=5开始使用。如果叶节点中含有的样本量变化很大，建议输入浮点数作为样本量的百分比来使用。对于类别不多的分类问题，=1通常就是最佳选择。
min_samples_split
min_samples_split 会限定一个节点必须要包含至少min_samples_split个训练样本，这个节点才允许被分枝，否则 分枝就不会发生。
max_features & min_impurity_decrease
max_features，一般搭配max_depth使用，用作树的”精修“。 max_features限制分枝时考虑的特征个数，超过限制个数的特征都会被舍弃。但由于该方法比较暴力，在不知道决策树中的各个特征的重要性的情况下，强行设定这个参数可能会导致模型学习不足。如果希望通过降维的方式防止过拟合，建议使用PCA，ICA或者特征选择模块中的降维算法。
min_impurity_decrease限制信息增益的大小，信息增益小于设定数值的分枝不会发生
重要属性和接口
sklearn中许多算法的接口都是相似的，比如说我们之前已经用到的fit和score，几乎对每个算法都可以使用。除了 这两个接口之外，决策树最常用的接口还有apply和predict。
apply中输入测试集返回每个测试样本所在的叶子节点的索引
predict输入测试集返回每个测试样本的标签。
代码示例
1.导入需要的算法库和模块
from sklearn import tree
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split
2.探索数据
wine = load_wine)
wine.data.shape
wine.target
#如果wine是一张表，应该长这样：
import pandas as pd
pd.concat[pd.DataFramewine.data),pd.DataFramewine.target)],axis=1)
wine.feature_names
wine.target_names
分训练集和测试集
Xtrain, Xtest, Ytrain, Ytest = train_test_splitwine.data,wine.target,test_size=0.3)
Xtrain.shape
Xtest.shape
建立模型
clf = tree.DecisionTreeClassifiercriterion="entropy"
,random_state=30
,splitter="random"
,max_depth=3
,min_samples_leaf=10
,min_samples_split=10)
clf = clf.fitXtrain, Ytrain)
score = clf.scoreXtest, Ytest) #返回预测的准确度
score
画出一棵树吧
feature_name = ['酒精','苹果酸','灰','灰的碱性','镁','总酚','类黄酮','非黄烷类酚类','花青素'
,'颜色强度','色调','od280/od315稀释葡萄酒','脯氨酸']
import graphviz
dot_data = tree.export_graphvizclf
,out_file = None
,feature_names= feature_name
,class_names=["琴酒","雪莉","贝尔摩德"]
,filled=True
,rounded=True
)
graph = graphviz.Sourcedot_data)
graph
探索决策树
#特征重要性
clf.feature_importances_
[*zipfeature_name,clf.feature_importances_)]
#apply返回每个测试样本所在的叶子节点的索引
clf.applyXtest)
#predict返回每个测试样本的分类/回归结果
clf.predictXtest)