决策树算法

决策树算法

决策树

• 一.原理
• • 1.学习算法定义
  • 2.树停止的条件
  • 3.采用启发式方法的原因
• 二.特征选择
• • 1.定义
  • 2.准则
  • 3.信息增益（互信息）
  • 4.信息增益算法
  • 5.信息增益存在的问题
  • 6.信息增益比
• 三.决策树的剪枝
• • 1.防止过拟合：
  • 2.预剪枝：
  • 3.后剪枝：
  • 4.两者比较：
  • *缺失值处理
• 四.决策树优缺点
• • 优点
  • 缺点

一.原理 1.学习算法定义

启发式方法，递归地选择最优特征，并根据该特征对训练数据进行分割，使得各个子数据集有一个最好的分类的过程

2.树停止的条件

（1）当前节点包含的样本全属于同一类别，无需划分
（2）当前属性集为空，或所有样本在所有属性上取值相同，无法划分
（3）当前节点包含的样本集合为空，不能划分

3.采用启发式方法的原因

决策树学习的损失函数通常是正则化的极大似然函数，当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法。

二.特征选择 1.定义

选取对训练数据具有分类能力的特征，即决定用哪个特征来划分特征空间。

2.准则

信息增益或信息增益比
一般而言我们希望选择一个属性a之后，其分支节点所包含的样本尽可能属于同一类别，即结点的纯度 (Purity) 越来越高。

3.信息增益（互信息）

表示得知特征X的信息而使类Y的信息的不确定性减少的程度。

理解：经验熵H(D)表示对数据集D进行分类的不确定性，经验条件熵H(D|A)表示在给定特征A的条件下对数据集D进行分类的不确定性，它们的差即信息增益，表示由于特征A而使得对数据集D的分类的不确定性减少的程度。
（互信息表示了两事件发生所代表的信息之间的重复部分，当两事件信息重复的部分越大，那么采用一种事件为标准来划分另一种事件所能确定的部分也就越大，也就是说采用属性 a来进行划分所获得的“纯度提升”越大。考虑极端情况，当属性 a与类别完全没有关系时，其互信息为 0，这时候采用 a属性作为划分标准对于数据集的类别确认完全没有帮助；当属性 a的各属性分别与数据集的类别一一对应时，也就是其概率分布完全相同，那么根据互信息的计算公式，其互信息等于各自的熵，也就是说，如果我们采用 a进行数据的划分，那么数据可以完全干净的划分出来，也就不再含有额外的不可知信息了。）

4.信息增益算法

5.信息增益存在的问题

采用信息增益来进行划分属性的决策有一个潜在的问题，当某一个属性的取值种类非常多时，对应每一个属性取值的样本子集，其分类的信息熵可能会变得很小。最后计算出来的信息增益很大。但是显然，用“编号”属性来作为结点的划分是没有意义的。思考其中的问题在于，对数函数并不是线性的，信息量的减少速度大于类别数量的增加速度。信息增益准则对取值数目较多的属性有所偏好。

6.信息增益比

增益率准则虽然减少了对取值数目较多的属性依赖，但是增加了对取值数目较少的属性偏好。因此，C4.5并没有直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

三.决策树的剪枝 1.防止过拟合：

过拟合的原因在于学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树。决策树的生成只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合，而决策树剪枝通过优化损失函数还考虑了减小模型复杂度。决策树生成学习局部的模型，而决策树剪枝学习整体的模型。

2.预剪枝：

在每一次实际对结点进行进一步划分之前，先采用验证集的数据来验证如果划分是否能提高划分的准确性。如果不能，就把结点标记为叶结点并退出进一步划分；如果可以就继续递归生成节点。

3.后剪枝：

后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来泛化性能提升，则将该子树替换为叶结点。

4.两者比较：

（1）后剪枝决策树通常比预剪枝决策树保留了更多的分支；
（2）后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树；
（3）后剪枝决策树训练时间开销比未剪枝决策树和预剪枝决策树都要大的多。

*缺失值处理 四.决策树优缺点 优点

1.决策树易于理解和解释.人们在通过解释后都有能力去理解决策树所表达的意义。
2.对于决策树，数据的准备往往是简单或者是不必要的，比如不需要归一化.其他的技术往往要求先把数据一般化，比如去掉多余的或者空白的属性。
3.能够同时处理数据型和常规型属性。其他的技术往往要求数据属性的单一。
4.决策树是一个白盒模型。如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
5.易于通过静态测试来对模型进行评测。表示有可能测量该模型的可信度。
6.在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
7.可以对有许多属性的数据集构造决策树。
8.决策树可很好地扩展到大型数据库中，同时它的大小独立于数据库的大小。

缺点

1.对于那些各类别样本数量不一致的数据，在决策树当中,信息增益的结果偏向于那些具有更多数值的特征。
2.决策树处理缺失数据时的困难。
3.过度拟合问题的出现。
4.忽略数据集中属性之间的相关性。