决策树基础知识点整理
1、基本算法流程
决策树的构造是一个递归的过程，有三种情形会导致递归返回：(1) 当前结点包含的样本全属于同一类别，这时直接将该节点标记为叶节点，并设为相应的类别；(2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分，这时将该节点标记为叶节点，并将其类别设为该节点所含样本最多的类别；(3) 当前结点包含的样本集合为空，不能划分，这时也将该节点标记为叶节点，并将其类别设为父节点中所含样本最多的类别。算法的基本流程如下图所示：
2.划分的特征选择的方法：
- 信息增益。这种方法对可取值数目较多的属性有偏好。ID3算法采用了这种方法
- 增益率。这种方法是为了减少信息增益对取值数目较多的属性的偏好带来的不利影响。C4.5算法采用了这种方法。需要注意的是，增益率对可取值数目较少的属性有所偏好。因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
- 基尼指数。CART决策树采用了基尼指数。
3.剪枝处理
在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得“太好了”，以至于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此可以通过去掉一些分支来降低过拟合的风险。
决策树剪枝策略主要包括：
- 预剪枝；在构造的过程中先评估，再考虑是否分支。
- 后剪枝；在构造好一颗完整的决策树后，自底向上，评估分支的必要性。
评估指的是性能度量，即决策树的泛化性能。之前提到：可以使用测试集作为学习器泛化性能的近似，因此可以将数据集划分为训练集和测试集。预剪枝表示在构造数的过程中，对一个节点考虑是否分支时，首先计算决策树不分支时在测试集上的性能，再计算分支之后的性能，若分支对性能没有提升，则选择不分支（即剪枝）。后剪枝则表示在构造好一颗完整的决策树后，从最下面的节点开始，考虑该节点分支对模型的性能是否有提升，若无则剪枝，即将该节点标记为叶子节点，类别标记为其包含样本最多的类别。
4.连续值处理
对于连续值的属性，若每个取值作为一个分支则显得不可行，因此需要进行离散化处理，常用的方法为二分法，基本思想为：给定样本集D与连续属性α，二分法试图找到一个划分点t将样本集D在属性α上分为≤t与＞t。
- 首先将α的所有取值按升序排列，所有相邻属性的均值作为候选划分点（n-1个，n为α所有的取值数目）。
- 计算每一个划分点划分集合D（即划分为两个分支）后的信息增益。
- 选择最大信息增益的划分点作为最优划分点。
5.缺失值处理
现实中常会遇到不完整的样本，即某些属性值缺失。有时若简单采取剔除，则会造成大量的信息浪费，因此在属性值缺失的情况下需要解决两个问题：（1）如何选择划分属性。（2）给定划分属性，若某样本在该属性上缺失值，如何划分到具体的分支上。
具体参考：周志华《机器学习》第四章–决策树
6.多变量决策树
若把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。
7.决策树的优点和缺点
优点：
决策树算法中学习简单的决策规则建立决策树模型的过程非常容易理解，
决策树模型可以可视化，非常直观
应用范围广，可用于分类和回归，而且非常容易做多类别的分类
能够处理数值型和连续的样本特征
缺点：
很容易在训练数据中生成复杂的树结构，造成过拟合（overfitting）。剪枝可以缓解过拟合的负作用，常用方法是限制树的高度、叶子节点中的最少样本数量。
学习一棵最优的决策树被认为是NP-Complete问题。实际中的决策树是基于启发式的贪心算法建立的，这种算法不能保证建立全局最优的决策树。Random Forest 引入随机能缓解这个问题
8.基本掌握ID3、C4.5和CART算法，以及它们的区别
- ID3决策树可以有多个分支，但是不能处理特征值为连续的情况
- C4.5还弥补了ID3中不能处理特征属性值连续的问题。但是，对连续属性值需要扫描排序，会使C4.5性能下降
- CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用基尼指数（Gini）来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似 -