概要

分类决策树模型是表示基于特征对实例进行分类的树形结构。决策树可以转换成一个if-then规则的集合，也可以看作是定义在特征空间划分上的类的条件概率分布。

决策树旨在构建一个与训练数据拟合很好，并且复杂度小的决策树。因为从可能的决策树中直接选取最优决策树是NP完全问题。实际应用中采用启发式的方法学习次优的决策树。

决策树学习算法包括三部分：特征选择、树的生成和树的剪枝。常用的算法有ID3、C4.5和CART。

模型介绍

特征选择的目的在于选取对训练数据能够分类的特征，特征选择的关键是其准则，根据准则的不同，将算法分为ID3、C4.5和CART。

1.信息增益

信息熵是度量样本集合纯度最常用的指标。假定当前样本集合D中第类样本所占的比例为,则D的信息熵为

                                                                                                   (1)

的值越小，则D的纯度越高。

假定离散属性a有V个可能的取值,若使用a来对样本集D进行划分，则会产生V个分支节点，其中第个分支节点包含了D中所有在属性a上取值为的样本，记为.根据（1）式考虑到不同的分支节点包含的样本数不同，可得用属性a对样本集D进行划分所获得的信息增益为：

                                                                        (2)

一般而言，信息增益越大，说明使用属性a来进行划分所获得的纯度提升越大，因此所找的属性为

ID3算法就是采用信息增益作为特征选择的标准

2.信息增益比

在上边所介绍的信息增益准则，它对可取值较多的属性有所偏好，为减少这种偏好所带来的不利影响，C4.5决策树算法不直接使用信息增益，而是使用增益率来选择最优划分属性。信息增益率定义为：
                                                            

其中

                                                                 

称为属性a的固有值，属性a的可能取值数目越多，则的值通常会越大。

需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式的方法：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

3.基尼指数

CART决策树使用基尼指数来选择划分属性。数据集D的纯度可用基尼值来度量：
                                                                

基尼指数反映了从数据集D中随机抽取两个样本，类别标记不一样的概率。也就是说，越小，数据集D的纯度越高。

属性a的基尼指数为

                                                               

于是我们在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优化分属性，即

决策树的剪枝

决策树生成算法递归的产生决策树，直到不能继续下去为止。这样产生的树往往对训练数据的分类很准确，但对于未知的数据分类效果往往会差一点，可能会出现过拟合现象。过拟合的原因在于学习时过多的考虑如何提高对训练数据的正确分类，从而构建出复杂的决策树。解决该问题的方法是考虑决策树的复杂度，从而对已生成的决策树进行简化。对决策树进行简化的过程称为剪枝。在周志华的《机器学习》一书中采用的是剪枝前后验证集上分类精度是否有提升做出选择，李航的《统计学习方法》一书中采用的以损失函数来衡量，在此我们采用《机器学习》中的方法。

决策树剪枝的基本策略有“预剪枝”和“后剪枝”，预剪枝是在决策树的生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则不进行划分；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上的对非叶节点进行分析，若将该节点对应的子树替换为叶节点能带来泛化性能的提升，则将该子树替换为叶节点。

优缺点：

预剪枝：降低了过拟合的风险，显著减少了决策树的训练时间开销和测试时间开销。但是有些分支虽然当前不能带来泛化性能的提升，但是继续划分可能导致性能显著提升。也就是说预剪枝基于贪心原则不允许这些分支展开，给预剪枝决策树带来了欠拟合的风险。

后剪枝：欠拟合风险较小，泛化性能往往优于预剪枝决策树，但是它是在生成完整的决策树之后进行的，并且需要自底向上的对树中的所有非叶节点进行逐一考察，因此其训练时间较长。

连续值和缺失值的处理

1.连续值的处理

因为连续属性的可取值数目不再有限，因此不能像前面处理离散属性枚举离散属性取值来对结点进行划分。因此需要连续属性离散化，常用的离散化策略是二分法，这个技术也是C4.5中采用的策略。下面来具体介绍下，如何采用二分法对连续属性离散化：

                    

需要注意的是：与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。

2.缺失值的处理

 在属性a下假如存在缺失值的话，在计算属性a下的信息增益或者信息增率时，把具有缺失值的元组去掉，把具有完整值的属性a代入计算，用去掉缺失值计算结果进行比较。具体可查看《机器学习》一书。

决策树的优缺点

优点：

1.直观，易于理解和实现

2.数据的准备简单或者不必要

3.能够同时处理数据型和常规型属性。其他的算法往往要求数据属性单一。

4.对缺失值不太敏感

5.可以处理不相关特征数据

6.效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度

7.可能使用统计检验来验证模型，这是为了验证模型的可靠性

8.从数据结果来看，它执行的效果很好，虽然它的假设有点违反真实模型


决策树算法的缺点

1.对连续属性的字段比较难预测

2.对有时间顺序的数据需要很多预处理的工作

3.当类别较多时，分类效果较差

4.在处理特征关联性比较强的数据时表现的不是很好

参考：周志华《机器学习》

         李航《统计学习方法》