决策树

决策树

决策树的生成是一个递归过程，有三种情形会导致递归返回：
（1）当前结点包含的样本全属于同一类别，无需划分
（2）当前属性集为空，或是所有样本的所有属性上取值相同，无法划分
（3）当前结点包含的样本集合为空，不能划分

决策树划分目的：随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越来越高

ID3决策树算法：

以信息增益为准则选择划分属性：

信息熵（information entropy）：度量样本集合纯度的最常用指标，假定当前样本集合D中第k类样本所占比例为$p_{k}(k=1,2, \ldots,|\mathcal{Y}|)$，则D的信息熵定义为：

$$\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|} p_{k} \log _{2} p_{k}$$

计算信息熵时约定，若$p=0$，则$p \log {2} p=0$
$0 < \operatorname{Ent}(D) < \log {2}|\mathcal{Y}|$，$\operatorname{Ent}(D)$的值越小，则D的纯度越高。
假定离散属性a有V个可能的取值$\left{a^{1}, a^{2}, \ldots, a^{V}\right}$，若使用a来对样本集合D进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为$a^{v}$的样本，记为$D^{v}$。我们可以计算出$D^{v}$的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重$\left|D^{v}\right| /|D|$，即样本数越多的分支结点的影响越大，于是可计算出属性a对样本集D进行划分所获得的信息增益（information gain）

$$\operatorname{Gain}(D, a)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right)$$

信息增益越大，则意味着使用属性a来进行划分所获得的纯度提升越大。

C4.5决策树算法：

信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法使用增益率（gain ratio）来选择最优划分属性。增益率定义为：

$$\text { Gain_ratio }(D, a)=\frac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)}$$

其中

$$\operatorname{IV}(a)=-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \log _{2} \frac{\left|D^{v}\right|}{|D|}$$

称为属性a的固有值（intrinsic value）。属性a的可能取值数目越多（即V越大），则IV（a）的值通常越大。

CART决策树算法：

CART决策树对连续属性采用二分法(bi-partition)
数据集D的纯度可用基尼指数（Gini index）来度量：

$$\begin{aligned} \operatorname{Gini}(D) &=\sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{\prime} \neq k} p_{k} p_{k^{\prime}} \\ &=1-\sum_{k=1}^{|\mathcal{Y}|} p_{k}^{2} \end{aligned}$$

$\operatorname{Gini}(D)$反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此$\operatorname{Gini}(D)$越小，数据集D的纯度越高。属性a的基尼指数定义为：

$$\text { Gini_index }(D, a)=\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Gini}\left(D^{v}\right)$$

剪枝（pruning）

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。

预剪枝（prepruning）：基于“贪心”，带来欠拟合风险。降低过拟合风险，显著减少决策树训练时间和测试时间开销。
后剪枝（postpruning）：比预剪枝决策树保留了更多的分支。欠拟合风险小，泛化性能优于预剪枝决策树。但训练时间开销比未剪枝决策树和预剪枝决策树要大得多。