4.决策树 - 一、原理 - 《AI算法工程师手册》

一、原理

决策树模型可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。
决策树将特征空间划分为互不相交的单元，在每个单元定义一个类的概率分布，这就构成了一个条件概率分布。
- 决策树的每一条路径对应于划分中的一个基本单元。
- 设某个单元内部有个样本点，则它定义了一个条件概率分布。
  - 单元上的条件概率偏向哪个类，则该单元划归到该类的概率较大。即单元的类别为：
  - 决策树所代表的条件概率分布由各个单元给定条件下类的条件概率分布组成。
决策树的学习目标是：根据给定的训练数据集构造一个决策树模型，使得它能够对样本进行正确的分类。
决策树最优化的策略是：损失函数最小化。决策树的损失函数通常是正则化的极大似然函数。
选择最优决策树的问题是个 NP 完全问题。一般采用启发式方法近似求解这个最优化问题，这时的解为次最优的。
决策树学习的算法通常递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类。

这一过程对应着特征空间的划分，也对应着决策树的构建。

决策树生成算法：
- 构建根结点：将所有训练数据放在根结点。
- 选择一个最优特征，根据这个特征将训练数据分割成子集，使得各个子集有一个在当前条件下最好的分类。
  - 若这些子集已能够被基本正确分类，则将该子集构成叶结点。
  - 若某个子集不能够被基本正确分类，则对该子集选择新的最优的特征，继续对该子集进行分割，构建相应的结点。
- 如此递归下去，直至所有训练数据子集都被基本正确分类，或者没有合适的特征为止。
上述生成的决策树可能对训练数据有很好的分类能力，但是对于未知的测试数据却未必有很好要的分类能力，即可能发生过拟合的现象。
- 解决的方法是：对生成的决策树进行剪枝，从而使得决策树具有更好的泛化能力。
- 剪枝是去掉过于细分的叶结点，使得该叶结点中的子集回退到父结点或更高层次的结点并让其成为叶结点。
决策树的生成对应着模型的局部最优，决策树的剪枝则考虑全局最优。
如果学习任意大小的决策树，则可以将决策树算法视作非参数算法。但是实践中经常有大小限制（如限制树的高度、限制树的叶结点数量），从而使得决策树成为有参数模型。