决策树是用于分类和回归问题的树。在本文中，我们将首先讨论分类树。决策树可以被视为if-then 规则的集合或在特征和类空间中定义的条件概率分布。

优点：阅读方便，分类速度快。

决策树的定义

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

用决策树进行分类时：从根节点开始，根据实例的某些特征将实例分配到相应的子节点。每个子节点对应于特征的特定值。以这种方式递归分配实例，直到到达叶节点。最后将一个实例分配给叶节点所在的类。

学习决策树：

目标：根据给定的训练集构建决策树模型，以正确分类实例。

本质：从训练数据集中总结一组分类规则，以获得与训练数据集不一致程度较小的树，或者从训练数据集中选择最佳条件概率模型。这是一个特征空间划分的问题。

决策树训练主要由三个主要部分组成。

特征选择决策树生成和修剪

特征选择

选择能够对训练数据进行分类的特征。标准：信息增益或信息增益比。

分类能力：基于该特征的训练数据类别的每个子集的分类纯度越高，分类能力越强。

信息增益的经验熵=随机变量不确定性的度量。不确定性越大，熵就越大。

条件熵=给定已知随机变量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)从小到大对直到根节点的子树进行排序。该节点将被修剪。

3）算法

模型优缺点

1）优点：

易于理解和解释。 可视化。需要很少的数据预处理。 其他技术通常需要数据标准化，例如创建虚拟变量或删除空白值。 但请注意，该模块不支持缺失值。您需要处理缺失值。使用树（即预测数据）的成本是用于训练树的数据点数量的对数。处理数字和分类数据的能力。 但是，scikit-learn 实现当前不支持分类变量。 可以处理多个输出问题。使用白盒模型。 如果模型中可以观察到某个条件，则可以使用布尔逻辑轻松解释该条件的解释。 相比之下，黑盒模型（例如人工神经网络）可能会使结果更难以解释。您可以使用统计测试来验证您的模型。 这使得解释模型的可靠性成为可能。即使生成数据的实际模型在某种程度上违反了其假设，性能也很好。 2）缺点：

决策树学习者可能会创建过于复杂而无法充分总结数据的树。 这称为过度拟合。 为了避免这个问题，您应该使用剪枝、设置叶节点所需的最小样本数以及设置最大树深度等机制。决策树可能不稳定，因为数据的微小变化可能会产生完全不同的树。 通过在集成学习中使用决策树可以缓解这个问题。决策树的预测既不平滑也不连续，而是分段常数近似，如上图所示。 因此，他们不擅长推断学习最优决策树的问题，即使在简单的最优概念的某些方面，最优决策树也被认为是np 完全的。 因此，实际的决策树学习算法基于贪婪算法等启发式算法在每个节点做出局部最优决策。 该算法不能保证返回总体最优的决策树。 这可以通过在集成学习器中训练多个树来缓解，其中特征和样本通过替换进行随机采样。有些概念（例如异或、奇偶校验和复用问题）很难学习，因为它们无法轻松地在决策树中表示。如果特定类别占主导地位，决策树学习器将创建一棵偏置树。 因此，建议您在拟合决策树之前平衡数据集。