决策树decision tree是一颗树，用于分类和回归问题，本文先介绍分类树。决策树可以认为是if-then规则的集合，或者定义在特征空间与类空间上的条件概率分布。

优点：可读性、分类速度快。

决策树的定义

分类决策树是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶结点。内部结点表示一个特征或属性，叶结点表示一个类。

用决策树分类时：从根结点开始，根据实例的某一特征将实例分配到对应子结点；每一个子结点对应着特征的某个取值。如此递归的对实例进行分配，直至达到叶结点。最后将实例分配到叶结点所在的类中。

决策树的学习：

目标：根据给定训练集构建一个决策树模型，使它能够对实例进行正确的分类。

本质：从训练数据集归纳出一组分类规则，得到一颗与训练数据集矛盾较少的一棵树；或者由训练数据集选择一个最优的条件概率模型。是一个特征空间划分的问题。

决策树的学习主要由3大块组成：

特征选择决策树生成剪枝特征选择

选择对训练数据有分类能力的特征，准则：信息增益或信息增益比。

分类能力：训练数据的类别在该特征下各子集的分类纯度越高代表分类能力越强。

信息增益

经验熵=随机变量不确定性的度量，不确定性越大，熵越大

条件熵=已知随机变量X的条件下随机变量Y的不确定性

信息增益=经验熵-条件熵，表示得知特征X的信息，使得Y的不确定性减少的程度

信息增益取决于特征，信息增益大的特征具有更强的分类能力。

经验熵

条件熵

信息增益

信息增益比

信息增益有个缺点是某个特征的取值越多其条件熵越小，信息增益越大。例如对于特征 ID每个ID都是唯一的，ID中只有一个样本，其条件熵为0。信息增益比可以解决这一问题。

根据信息增益/信息增益比最大的方法找到根结点对应的特征。

决策树的生成ID3算法：在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。

停止条件：当信息增益小于阈值；没有更多特征；所有结点都是同一类

算法步骤：

ID3算法只有树的生成，所以该算法产生的树容易过拟合。

C4.5算法

C4.5与ID3唯一的区别就是用信息增益比代替信息增益

决策树的剪枝

上述算法都是基于局部最优解得到决策树，并未考虑全局损失函数。这样生成的树对训练数据拟合很好，但是生成的树过于复杂往往产生过拟合。因此，全局损失函数需考虑树的复杂度，简化生成的决策树。

决策树的剪枝就是将子树剪掉，用父节点替代原先的子结点，从而简化决策树。

操作手段有了，还需要确定决定是否剪枝的标准，如果剪掉的子树不会增加很多熵值，同时会大大减少结点个数，则选择剪枝。也就是说我们需要在熵值增加和结点数减少之间进行权衡，转化为公式：

剪枝算法：

输入：决策树T、参数alpha

输出：修剪后的子树t

1)计算每个结点的经验熵

2）递归地从树的叶结点向上回缩，如果子树的损失函数更小则得到子树。

3）重复2）直到不能继续为止。

CART算法

CART是一种分类回归树，是二叉树，内部结点的特征由是和否构成。CART回归树用平方误差最小化准则，对分类数用基尼系数最小化准则进行特征选择。

回归树的生成

1）回归树划分后显然用该特征空间划分上的y的平均值作为结点的预测值

2）划分后的预测误差用平方误差来抽象

3）对特征和取值遍历选择预测误差最小的特征作为切分变量、某个取值作为切分变量

4）依次用上述方法将输入空间划分为两个区域，生成一棵回归树。

分类数的生成

1）损失函数用基尼系数代替熵，样本集合的不确定性越大、基尼系数越大、熵越大。因此本优化问题为找到基尼系数最小的特征和取值。

2）二叉树：特征一次分为是否为某个取值

3）停止条件：结点中样本个数小于阈值；基尼系数小于阈值==基本属于一类；没有更多特征

CART剪枝

整体思路：将子树从下往上依次剪枝得到子树序列，然后通过交叉验证法在验证数据集上得到损失函数（平方误差或基尼系数）最小的子树。子数确定后最优的alpha也确定了。

alpha越小子树结点数的权重越小，树越大；alpha越大决策树越简单。

1）子树序列对应着alpha序列，从下往上剪形成子树序列，对应着alpha从小到大。

对于某个内部结点，剪枝与否的损失函数对比如下：

2）对一颗决策树内部每一结点计算g(t)，按g(t)从小到大排序子树直至根节点，alpha达到某一个g(t)值意味着对该内部结点剪枝。

3）算法

模型优缺点

1）优点：

简单易懂，易于解释。 可视化。几乎不需要数据预处理。 其他技术通常需要数据归一化，需要创建虚拟变量和删除空白值。 但是请注意，此模块不支持缺失值。缺失值要处理。使用树(即预测数据)的成本是用于训练树的数据点数量的对数。能够处理数值和分类数据。 然而，scikit-learn实现目前还不支持分类变量。 能够处理多输出问题。使用白盒模型。 如果给定的情况在一个模型中是可观察到的，那么对这个条件的解释很容易用布尔逻辑来解释。 相比之下，在黑盒模型中(例如，在人工神经网络中)，结果可能更难解释。可以使用统计测试来验证模型。 这使得解释模型的可靠性成为可能。即使生成数据的真实模型在某种程度上违反了它的假设，它也能很好地执行。

2）缺点：

决策树学习者可以创建过于复杂的树，不能很好地概括数据。 这叫做过拟合。 为了避免这个问题，需要使用修剪、设置叶子节点所需的最小样本数量或设置树的最大深度等机制。决策树可能是不稳定的，因为数据中的小变化可能导致生成完全不同的树。 通过在集成学习中使用决策树，可以缓解这个问题。决策树的预测既不是平滑的，也不是连续的，而是如上图所示的分段常数近似。 因此，他们不擅长外推学习最优决策树的问题是已知的np -完全在几个方面的最优性，甚至简单的概念。 因此，实际的决策树学习算法是基于启发式算法，如贪婪算法，在每个节点上做出局部最优决策。 这种算法不能保证返回全局最优决策树。 这可以通过在集成学习器中训练多棵树来缓解，其中特征和样本是随机采样的替换。有些概念很难学习，因为决策树不容易表达它们，比如异或、奇偶校验或多路复用问题。如果某些类占主导地位，决策树学习者会创建有偏差的树。 因此，建议在拟合决策树之前平衡数据集。