决策树 (Decision tree,DT) 是一种基本的分类与回归方法。它是一个树形结构，对于指定特征空间上的数据点来说，总能顺着决策树的根节点一步步分配到子节点最终到达叶节点，而叶节点表示了该数据点所属的分类。在每一次分配到子节点的过程中可以看作是对数据点中特有的特征属性值进行的 if-then 判断。
决策树可以认为是 if-then 规则的集合，也可以认为时定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。如何得到该决策树叫做决策树学习，决策树学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测试，对新的数据，利用决策树模型进行分类。
特征可以连续和离散
因变量分类时是离散，回归时是连续
1）简单直观，生成的决策树很直观。
2）基本不需要预处理，不需要提前归一化，处理缺失值。
3）使用决策树预测的代价是O(log2m)。 m为样本数。
4）既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
5）可以处理多维度输出的分类问题。
6）相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
7）可以交叉验证的剪枝来选择模型，从而提高泛化能力。
8） 对于异常点的容错能力好，健壮性高。
1）决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
2）决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
3）寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
4）有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
5）如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。
例子：
（表1）
根据以上决策树，现在给你一个实例：{色泽：青绿，根蒂：稍蜷，敲声：清脆，纹理：清晰，脐部：稍凹，触感：光滑}，来判断该瓜是否是好瓜。其过程是：脐部（稍凹）-->根蒂（稍蜷）-->色泽（青绿）-->好瓜。
以上是由决策树来进行分类的过程。而决策树的学习（构建）通常是一个递归地选择最优特征的过程。那么构建决策树时如何选择特征作为划分点（即选择哪个特征作为根节点或者选择哪个特征作为非叶子节点）？当训练数据量大、特征数量较多时构建的决策树可能很庞大，这样的决策树用来分类是否好？
由这些问题我们可以知道，构建决策树的三个要点：
（1）特征选择
（2）决策树的生成
（3）决策树修剪
基于ID3算法的决策树构建，其选择特征的准则是信息增益。信息增益（information gain）表示得知特征 XX的信息而使得类 YY 的信息的不确定性减少的程度。也就是说，信息增益越大，通过特征 XX ，就越能够准确地将样本进行分类；信息增益越小，越无法准确进行分类。
在介绍信息增益之前，我们需要先对熵进行一下讲解。
熵是度量样本集合纯度最常用的一种指标，它是信息的期望值。我们首先了解一下什么是信息。由《机器学习实战》中定义：
而熵计算的是所有类别所有可能值包含的信息期望值，其公式为：
其中 N 为类别个数。
现在使用例子，来理解熵的计算：
（1）对于最终分类（是否为好瓜），计算其信息熵：
由上表(1)可看出，一共有17个样本，属于好瓜的有8个样本，坏瓜的有9个样本，因此其熵为：
（2）对于特征“色泽”，计算其信息熵： 
由于特征“色泽”取值有：{青绿，乌黑，浅白}。若使用该属性对 DD进行划分，可得到3个子集，分别记为： D1（色泽=青绿）， D2 （色泽=乌黑）， D3 （色泽=浅白）。
信息增益，由《统计学习方法》中定义：
ID3算法递归地构建决策树，从根节点开始，对所有特征计算信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递归地调用以上方法构建决策树；知道所有特征的信息增益均很小或者没有特征可以选择为止。最后得到一个决策树。
在算法中（C4.5也是），有三种情形导致递归返回：
（1）当前节点包含的样本全属于同一类别，无需划分。
（2）当前属性集为空，或是所有样本在所有属性上取值相同，无法划分。（此时将所含样本最多的类别设置为该叶子节点类别）
（3）当前节点包含的样本集合为空，不能划分。（将其父节点中样本最多的类别设置为该叶子节点的类别）
实际上，信息增益准则对可取值书目较多的属性有所偏好，例如如果将前面表格中的第一列ID也作为特征的话，它的信息增益将达到最大值，而这样做显然不对，会造成过拟合。为了减少这种偏好可能带来的不利影响，C4.5算法中将采用信息增益比来进行特征的选择。信息增益比准则对可取值数目较少的属性有所偏好。接下来，我们首先对信息增益比进行介绍。
C4.5算法同ID3算法过程相似，仅在选择特征时，使用信息增益比作为特征选择准则。
通过验证集进行剪枝；
针对于在第1部分提到的最后一个问题：当训练数据量大、特征数量较多时构建的决策树可能很庞大，这样的决策树用来分类是否好？答案是否定的。决策树是依据训练集进行构建的，当决策树过于庞大时，可能对训练集依赖过多，也就是对训练数据过度拟合。从训练数据集上看，拟合效果很好，但对于测试数据集或者新的实例来说，并不一定能够准确预测出其结果。因此，对于决策树的构建还需要最后一步----即决策树的修剪。
决策树的修剪，也就是剪枝操作，主要分为两种：
（1）预剪枝（Pre-Pruning）
（2）后剪枝（Post-Pruning）
接下来我们将详细地介绍这两种剪枝方法。
预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶节点。
我们使用例子进一步理解预剪枝的过程：
将本文开始的西瓜数据集表划分成两部分，一部分作为训练集用来构建决策树，一部分作为验证集用来进行决策树的剪枝。具体划分见下图：
使用ID3算法进行决策树的构建，即使用信息增益进行特征的选择。首先选择特征“脐部”作为决策树根节点，如何判断该节点是否需要剪枝，需要对剪枝前后验证集精度进行比较。由“脐部”这个特征将产生三个分支“凹陷”、“稍凹”、“平坦”，并认定其分支结果（可采用多数表决法，当分类数量相当时，任选一类即可），如下图：
可有由图中看出，该决策树有点过于简单，虽然降低的过拟合的风险，但是由于其基于“贪心”的本质禁止了其它分支的展开，给预剪枝决策树带来了欠拟合的风险。
后剪枝是指先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策能力的提升，则将该子树替换成叶节点。
我们使用例子进一步理解后剪枝的过程：
同样适用1中的划分数据集。针对已建立好的决策树，我们首先对“纹理”特征节点进行处理，判断其是否需要剪枝，见下图。
后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情况下，后剪枝决策树欠拟合的风险很小，其泛化能力往往优于预剪枝预测数。但由于其是基于创建完决策树之后，再对决策树进行自底向上地剪枝判断，因此训练时间开销会比预剪枝或者不剪枝决策树要大。
接下来将以一个实际的例子对CART进行介绍：
从以下的思路理解CART：
分类树的作用是通过一个对象的特征来预测该对象所属的类别，而回归树的目的是根据一个对象的信息预测该对象的属性，并以数值表示。
CART既能是分类树，又能是决策树，如上表所示，如果我们想预测一个人是否已婚，那么构建的CART将是分类树；如果想预测一个人的年龄，那么构建的将是回归树。
分类树和回归树是怎么做决策的？
假设我们构建了两棵决策树分别预测用户是否已婚和实际的年龄，如图1和图2所示：
图1表示一棵分类树，其叶子节点的输出结果为一个实际的类别，在这个例子里是婚姻的情况（已婚或者未婚），选择叶子节点中数量占比最大的类别作为输出的类别；
图2是一棵回归树，预测用户的实际年龄，是一个具体的输出值。怎样得到这个输出值？一般情况下选择使用中值、平均值或者众数进行表示，图2使用节点年龄数据的平均值作为输出值。
CART如何选择分裂的属性？
分裂的目的是为了能够让数据变纯，使决策树输出的结果更接近真实值。那么CART是如何评价节点的纯度呢？如果是分类树，CART采用GINI值衡量节点纯度；如果是回归树，采用样本方差衡量节点纯度。节点越不纯，节点分类或者预测的效果就越差。
节点的分裂分为两种情况，连续型的数据和离散型的数据。
CART对连续型属性的处理与C4.5差不多，通过最小化分裂后的GINI值或者样本方差寻找最优分割点，将节点一分为二，在这里不再叙述，详细请看C4.5。
对于离散型属性，理论上有多少个离散值就应该分裂成多少个节点。但CART是一棵二叉树，每一次分裂只会产生两个节点，怎么办呢？很简单，只要将其中一个离散值独立作为一个节点，其他的离散值生成另外一个节点即可。这种分裂方案有多少个离散值就有多少种划分的方法，举一个简单的例子：如果某离散属性一个有三个离散值X，Y，Z，则该属性的分裂方法有{X}、{Y，Z}，{Y}、{X，Z}，{Z}、{X，Y}，分别计算每种划分方法的基尼值或者样本方差确定最优的方法。
以属性“职业”为例，一共有三个离散值，“学生”、“老师”、“上班族”。该属性有三种划分的方案，分别为{“学生”}、{“老师”、“上班族”}，{“老师”}、{“学生”、“上班族”}，{“上班族”}、{“学生”、“老师”}，分别计算三种划分方案的子节点GINI值或者样本方差，选择最优的划分方法，如下图所示：
综上，如果想预测是否已婚，则选择{“上班族”}、{“学生”、“老师”}的划分方法，如果想预测年龄，则选择{“老师”}、{“学生”、“上班族”}的划分方法。
CART如何剪枝？
CART采用基于代价复杂度（cost-complexity pruning,CCP）的剪枝方法。代价复杂度选择节点表面误差率增益值最小的非叶子节点，删除该非叶子节点的左右子节点，若有多个非叶子节点的表面误差率增益值相同小，则选择非叶子节点中子节点数最多的非叶子节点进行剪枝。
CCP剪枝主要分为两部分：
循环剪掉具有最小误差率增益值的子树，直到剩下根节点
利用独立的剪枝集进行评价，获取最佳剪枝树
第一部分-修剪： 
原文：https://www.cnblogs.com/wangleBlogs/p/11131505.html