一、决策树概念
在经典算法中，决策树是常用的算法之一。前面提到的线性回归可以解决回归问题，逻辑回归可以解决分类问题，而今天要学习的决策树不但可以回归问题，还可以解决分类问题。顾名思义，决策树分为两种树，回归树和分类树。在分类算法中，决策树是根基。现在常用的随机森林也是基于多个决策树集成的算法。从名称可以看出，决策树是含有分叉的树状算法。决策树思想是寻找最纯净的划分方法，每一步都寻找一个最优的特征进行划分。决策树简单图示：
根结点：它没有入边，但有零条或多条出边。
内部结点：恰有一条入边和两条或者多条出边。
叶结点：恰有一条入边，但没有出边。
父结点和子结点：一条有向边连接的两个结点，出边的结点是入边结点的父结点，而后者称为子结点。
二、特征选择
简单了解决策树的框架后，需要知道常见的几个概念。
1.误差率、熵、Gini指数
计算样本集合纯度的有三种方式，分别是误差率、熵和Gini指数。
误差率
其中i表示该类别中个数多的特征的个数，t表示该类别观测值数
熵
Gini指数
以上三种方式的计算例子如下：
三种方式的取值范围
Entropy=[0,1]，误差率和Gini=[0,0.5]
2.信息熵、信息增益
（1）信息熵：是度量样本集合纯度的，信息熵越小，样本集合纯度越高。
（2）信息增益
信息增益：在决策树划分中的属性选择中起作用。
信息增益=父结点的信息熵-子结点信息熵
子结点总信息熵
N是父节点上的记录总数，k是属性值的个数，N(vj)是与子节点vj相关联的记录个数。
具体实例可参考周志华--机器学习。
三、决策树的生成
决策树是在众多的特征中选择特征进行展开，主要是根据信息变化程度（即信息增益）来决定，这里涉及到决策树的算法，主要有三种，分别是ID3、C4.5和CART算法。
1.ID3算法
ID3算法是根据前面提到的信息增益来进行特征选择，流程如下。
ID3算法的流程：
1.计算父结点、子结点的信息熵和信息增益
2.选择信息增益最大的特征进行展开，再计算父结点、子结点的信息熵和信息增益
3.不断执行，直到熵等于0
ID3算法的局限：
所以接着引进了C4.5算法。
2.C4.5算法
在信息增益计算方法的子节点总信息熵的计算方法中添加了对分类变量数量的惩罚项。
其中，Gain(D,a)是信息增益，IV中的V是该特征下类别数，Gain_ratio(D,a)是信息增益率。
信息增益率对类别数较少的特征有所偏好。C4.5不是直接选择信息增益最大特征进行划分，而是从特征中找出信息增益高于平均水平的特征，再从中选择增益率最高的进行划分。
3.CART
CART决策树使用“基尼指数”来选择划分特征，它反应了从样本中随机抽取两个样本，其类别标记不一致的概率。Gini越小，纯度越高。
属性a的基尼指数定义为：
其中D是样本的数量，是a特征下各个类别样本量。
四、决策树的剪枝
剪枝是决策树解决过拟合问题的方法。在决策树学习过程中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，于是可能将训练样本学得太好，以至于把训练集自身的一些特点当作所有数据共有的一般特点而导致测试集预测效果不好，出现了过拟合现象。因此，可以通过剪枝来去掉一些分支来降低过拟合的风险。
决策树剪枝的基本策略有“预剪枝”和“后剪枝”。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
那如何判断决策树泛化性能是否提升呢？我们采用留出法，留出一部分作为验证集对模型进行评估。根据以下完整的一颗决策树为例。
1.预剪枝
预剪枝的实例参考周志华的机器学习。
预剪枝使得决策树的很多分支都没有"展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降?但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于"贪心"本质禁止这些分支展开，给预剪枝决策树带来了欠拟含的风险。
2.后剪枝
后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树 。但后剪枝过程是在生成完全决策树之后进行的 并且要白底向上对树中的所有非叶结点进行逐 考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。
五、连续与缺失值
1.连续特征
前面提到的特征类别都是可取值，但实际上，特征的值往往都是连续型数值。对于连续型数值，可取值往往很多，不能像离散型那样直接根据特征可取值进行划分，这时要对连续型特征的值采用二分法进行处理，这种方法在C4.5中使用较多。
该二分法步骤如下：
首先将连续型数值进行从小到大排序；
接着将数值划分成两部分，具体从哪里截断，具体要看信息增益。
注意：连续特征和离散特征不同的是，若当前结点划分特征是连续特征，该特征还可作为其后代结点的划分特征。
2.缺失值处理
实际中样本集总会存在缺失情况，如果将缺失值都丢弃，对于数据集很难收集的行业来说，这是难以做到的。所以必须要将缺失值处理后用于模型。
缺失值处理步骤：
1.将非缺失的样本用于特征划分，计算信息增益选择特征；
2.得到信息增益后再乘以非缺失值样本的占比，即Gain_new=Gain*(不含缺失样本/总样本)；
3.将缺失样本加入该特征下的每个类别，同时总样本=不含缺失样本+含缺失样本，即总权重改变。
参考资料：
周志华----机器学习（如果需要该书籍pdf的博友可以留言，定会分享！）