机器学习5（决策树<1>）

1.决策树

决策树为树结构，节点时决策结果，每隔叶节点存放一个类别，在每个节点的数个输出中，每个输出都代表特征属性在某个值域上的输出。

2.构成

构造决策树最关键时在节点进行分支的时候，所分出的各个分支要尽可能的纯。典型的有三种算法：ID3算法使用信息增益作为不纯度，C4.5算法使用信息增益律作为不纯度，CART算法使用基尼系数作为不纯度。

3. 信息增益，信息增益率，基尼系数

信息增益越大，属性纯度越高，信息增益率是信息增益处以数目的平均值，基尼指数反应的是随机抽取两个样本，其类别不一致的概率，因此Gini(D)越小，数据集D的纯度越高。

4. 剪枝（防止过拟合）

优点：计算复杂度不高，输出结果容易理解，对中间值的缺失不敏感，可以处理不相关特征数据
缺点：可能产生过拟合问题
适用数据类型：数值型和标称型

3.1 预剪枝

预剪枝对划分前后的泛化性能进行估计，若对某一节点划分后验证集的精度下降，则禁止划分该节点。预剪枝使得决策树的很多分支没有展开，不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于“贪心”的本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。
停止分类的条件：

(1) 如果节点中所有观测属于一类；
(2) 如果节点中所有观测的属性取值一致；
(3) 如果树的深度达到设定的阈值；
(4) 如果该节点所含观测值小于设定的父节点应含观测数的阈值；
(5) 如果该节点的子节点所含观测数将小于设定的阈值；
(6) 如果没有属性能满足设定的分裂准则的阈值。

3.2 后剪枝

后剪枝先从训练集生成一棵完整决策树，对每个节点，若将该节点对应的子树替换为叶节点后，验证集精度提升，则进行剪枝。后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树，但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶节点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。
后剪枝的方法：

(1) Reduced-Error Pruning (REP)：删除以此节点为根的子树使其成为叶节点，赋予该节点关联的训练数据的最常见分类，当修剪后的树对于验证集合的性能不会比原来的树差时，才真正删除该节点。
(2) Pessimistic Error Pruning (PEP)：计算某节点的误差，计算该节点的叶节点误差之和，当其误差小于等于叶节点误差之和加一个标准差时，则修建该节点。
(3) CCP：给基尼指数加上惩罚项，此时树的层次越深，基尼指数的惩罚项越大。