决策树基础
本文为周志华老师《机器学习》的读书笔记
定义
决策树是一类常见的机器学习算法，可基于离散型与连续型属性来生成决策树。决策树学习的目的是生成一棵泛化能力强，即处理未见示能力强的决策树。形状如下：
决策树通过递归过程来生成，在决策树基本算法中，有三种情况会导致递归返回：
- 当前节点包含的样本全属于同一类别，无需划分；
- 当前属性集为空集，或是所有样本在所有属性上取值相同，无法划分；
- 当前节点包含的样本集合为空，不能划分。
划分选择
从根节点开始，在每一个节点处我们都需要不断地选择一个最优的划分属性，来进行下一步的分支。而所谓最优的划分属性，即令该节点分支后下一层的各节点尽可能地属于同一类别，即要使划分进行的过程中节点的“纯度”不断提高。
例如，一批西瓜的属性集合为A，A中包含各个不同的属性a1、a2、a3…，分别代表色泽、根蒂形状、敲声…；而西瓜的目标变量为Y集合，Y中包含两个不同的目标值y1、y2，分别代表好瓜和坏瓜。
那么划分的过程就是在决策树的某一节点处，选择属性集合A中未选的一个属性a进行分支，使得分支节点的纯度得到提升，即尽可能地全为y1(好瓜)，或尽可能全为y2(坏瓜)。
纯度指标
既然要通过衡量纯度的提升与否，那么就得有一个指标来判断：选择此属性来进行下一步的分支是否比其余属性更优，是否具有最佳的纯度提升效果。
因此这里提出三个常用的，度量样本集合纯度的指标：信息熵增益、增益率、基尼系数。
(1)信息熵增益
假定当前样本集合D中第k类样本所占的比例为pk(k = 1,2,…,|γ|)，则D的信息熵定义为：
Ent(D)的值越小，则D的纯度越高，每一个节点都有自己的Ent(D)值。
定义了信息熵之后，我们便可以在其基础上给出信息增益的定义，先假定离散属性a有V个可能的取值{a1,a2,…,aV}，若选择属性a来划分样本集D，则所有取值为av的样本记为Dv，我们便可算出Dv的信息熵，此外，给分支节点Dv赋予权重|Dv| / |D|。我们便可算出用属性a给样本集D进行划分所获得的“信息增益”：
针对每一个节点，在选取属性来进行下一步分支前，都需要针对该节点选取余下的所有属性来计算信息增益的值，使得信息增益最大的属性为最优属性，即可使得“纯度提升”达到最大。
(2)增益率
多数情况下，信息增益准则对可取值数目较多的属性有所偏好，这种偏好会带来一些不利影响。因此，著名的C4.5决策树算法不直接使用信息增益准则，而是使用“增益率”来选择最优的划分属性，增益率定义为：
，其中IV(a)称为属性a的“固有值”，IV(a)定义为：
，属性a的取值越多(V越大)，则IV(a)的值通常会越大。
注： 增益率准则对可取值数目较少的属性有所偏好，因此，C4.5将信息增益和增益率结合使用：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
(3)基尼系数
CART决策树使用“基尼系数”来选择划分属性。数据集D(可看作某一节点处)的纯度可用基尼值来度量：
，Gini(D)表示样本集D中类别不同的概率大小，即Gini(D)越小，则样本集D的纯度越高。
将属性a的基尼指数定义为：
于是，我们选择能使得划分后基尼指数Gini_index(D,a)最小的属性a作为最优划分属性。
剪枝处理
剪枝是决策树学习算法对付“过拟合”的主要手段，通过主动剪掉一些分支来降低过拟合的风险。
(1)预剪枝
预剪枝是指在决策树生成过程中，对每一个节点在划分前先进性评估，如果当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶节点。
优点： 显著减少了决策树训练时间和测试时间的开销。
缺点： 有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高。因此预剪枝有可能给决策树带来欠拟合的风险。
(2)后剪枝
后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换成叶节点能带来决策树泛化能力的提升，则将该子树替换为叶节点。
优点： 后剪枝决策树通常比预剪枝决策树保留了更多的分支，因此其欠拟合的风险很小，泛化性能往往由于预剪枝决策树。
缺点： 但后剪枝是在决策树生成之后进行的，且自下而上逐一考察，因此开销时间比未剪枝和预剪枝决策树都大得多。
连续值处理
用特定的方法将连续型属性值转化为离散性属性，接着与其他离散性属性类似处理。
缺失值处理
对含缺失值的样本，以改进后的信息增益指标将它们以不同的概率划入到不同的子节点中去。