决策树（Decision Tree）

决策树（Decision Tree）是应用于分类的一种树结构。其中的每个内部节点（internal node）代表对某个属性的一次测试判别，一个分枝代表一个测试结果，叶子（leaf）代表某个类（class）或者类的分布（class distribution）。最顶层的节点是根结点。可以将决策树理解为一个if-then规则的集合，由决策树的根节点到叶节点的每一条路径构建一条规则。

最早的决策树算法是由Hunt等人于1966年提出的CLS。当前最有影响的决策树算法是Quinlan于1986年提出的ID3和1993年提出的C4.5。ID3只能处理离散型描述属性，它选择信息增益最大的属性划分训练样本，其目的是进行分枝时系统的熵最小，从而提高算法的运算速度和精确度。ID3算法的主要缺陷是，用信息增益作为选择分枝属性的标准时，偏向于取值较多的属性，而在某些情况下，这类属性可能不会提供太多有价值的信息。C4.5是ID3算法的改进算法，不仅可以处理离散型描述属性，还能处理连续性描述属性。C4.5采用了信息增益比作为选择分枝属性的标准，弥补了ID3算法的不足。

决策树经常在运筹学中使用，特别是在决策分析中，它帮助确定一个能最可能达到目标的策略。如果在实际中，决策不得不在没有完备知识的情况下被在线采用，一个决策树应该平行概率模型作为最佳的选择模型或在线选择模型算法。决策树的另一个使用是作为计算条件概率的描述性手段。

决策树（Decision Tree）这里的应用算法有：

  • 分类和回归树（CART）

  • ID3算法(Iterative Dichotomiser 3)

  • CHAID（Chi-squared Automatic Interaction Detection

  • 随机森林（Random Forest）

  • 多元自适应回归样条（MARS）

  • 梯度推进机（Gradient Boosting Machine， GBM）

决策树的优点

  • 便于理解和解释。树的结构可以可视化出来。

  • 训练需要的数据少。其他机器学习模型通常需要数据规范化，比如构建虚拟变量和移除缺失值,不过请注意，这种模型不支持缺失值。

  • 由于训练决策树的数据点的数量导致了决策树的使用开销呈指数分布(训练树模型的时间复杂度是参与训练数据点的对数值)。

  • 能够处理数值型数据和分类数据。其他的技术通常只能用来专门分析某一种变量类型的数据集。详情请参阅算法。

  • 能够处理多路输出的问题。

  • 使用白盒模型。如果某种给定的情况在该模型中是可以观察的，那么就可以轻易的通过布尔逻辑来解释这种情况。相比之下，在黑盒模型中的结果就是很难说明清 楚地。

  • 可以通过数值统计测试来验证该模型。这对事解释验证该模型的可靠性成为可能。

  • 即使该模型假设的结果与真实模型所提供的数据有些违反，其表现依旧良好。

决策树的缺点

  • 决策树模型容易产生一个过于复杂的模型,这样的模型对数据的泛化性能会很差。这就是所谓的过拟合.一些策略像剪枝、设置叶节点所需的最小样本数或设置数的最大深度是避免出现 该问题最为有效地方法。

  • 决策树可能是不稳定的，因为数据中的微小变化可能会导致完全不同的树生成。这个问题可以通过决策树的集成来得到缓解

  • 在多方面性能最优和简单化概念的要求下，学习一棵最优决策树通常是一个NP难问题。因此，实际的决策树学习算法是基于启发式算法，例如在每个节点进 行局部最优决策的贪心算法。这样的算法不能保证返回全局最优决策树。这个问题可以通过集成学习来训练多棵决策树来缓解,这多棵决策树一般通过对特征和样本有放回的随机采样来生成。

  • 有些概念很难被决策树学习到,因为决策树很难清楚的表述这些概念。例如XOR，奇偶或者复用器的问题。

  • 如果某些类在问题中占主导地位会使得创建的决策树有偏差。因此，建议在拟合前先对数据集进行平衡。

原文：https://github.com/KeKe-Li/tutorial