决策树

作者：Gauss

知乎：通俗易懂讲解决策树算法系列第一讲：决策树模型基本概念及如何构建
通俗易懂讲解决策树算法系列第二讲：ID3、C4.5和CART算法详解
通俗易懂讲解决策树算法系列第三讲：GBDT算法在回归任务中的应用

ShowMeAI:图解机器学习 | LightGBM模型详解

1 决策树构造

1.1 信息熵&信息增益

信息熵

?组数据中不确定性越?（纯度越低），熵值（entrophy）越?。数据集中第K类样本所占的?例为$p_k$, 则总样本的信息熵定义为：

\[Ent(D) = -\sum_{k=1}^K p_k \log_2 p_k \]

信息增益

?较各特征的信息增益，即原系统熵和引?特征分?后的系统熵的差值，信息增益越多，根节点的选择越有效。

\[Gain(D,a) = Ent(D) - \sum_{v=1}^V \frac{|D^v|}{|D|} Ent(D^v) \]

$a$是数据集$D$上的某一特征，共有$\{a^1,...,a^V\},V$种取值，每种取值$v$对应样本集$D^v$

这个公式可以理解为在属性$a$的取值已知后数据集$D$中类别$k$的不确定性减?的程度。

ID3：基于信息增益的属性划分，从根节点开始，对结点计算所有可能的特征的信息增益，选择信息增益最?的特征作为根节点的特征，由该特征的不同取值建??结点，再对?结点递归调?以上?法，构建决策树，直到所有特征的信息增益均很?或者没有特征可以选择为?。

信息增益率

信息增益对于可取值数?较多的特征有所偏好，因此引?信息增益率（gain ratio）。

?先定义特征$a$的固有值IV(Intrinsic Value)，取值越多，IV越大。

\[IV(a) = -\sum_{v=1}^V \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|} \\ GainRatio(D,a) = \frac{Gain(D,a)}{IV(a)} \]

C4.5:基于以上划分准则。且由于信息增益率对于可取值数?较少的特征有所偏好，C4.5是基于信息增益+信息增益率的属性划分：先从候选划分属性中找出信息增益?于平均?平的属性，再从中选择信息增益率最?的。

1.2 基尼指数

Gini Index。GI反应了数据集中随机抽取两个样本其标记值不?致的概率。Gini越?，数据集的纯度越?。

\[Gini(D) = \sum_{k=1}^K \sum_{k' \neq k} p_k p_{k'} = 1-\sum_{k=1}^K p_k^2 \]

属性$a$的基尼指数定义为:

\[Gini\_Index (D,a) = \sum_{v}^V \frac{|D^v|}{|D|} Gini(D^v) \]

相?于信息增益，GI没有使?对数运算和

CART：对于分类决策树，使?基尼指数最?化原则进?特征选择，?成?叉树。

1.3 决策树生成流程

输入：训练数据集$D$，特征集$A$，信息增益阈值$\epsilon$；

输出：决策树$T$

$D$中所有有实例属于同?类$C_k$，则$T$为单结点树，并将类$C_k$作为该结点的类标记，返回$T$；
若$A = \emptyset$，则$T$为单结点树，并将$D$中实例数最?的类$C_k$作为该结点的类标记，返回$T$；
否则，计算$A$中各特征对$D$的信息增益/信息增益率/基尼指数，选择信息增益最?/基尼指数最?的特征$A_g$；
如果$A_g$的信息增益?于阈值$\epsilon$，则置$T$为单结点树，并将$D$中实例数最?的类$C_k$作为该结点的类标记，返回$T$；
否则，对$A_g$的每?可能值$a_i$，将$D$分割为若??空?集$D_i$，将$D_i$中实例数最?的类作为标记，构建?节点，由节点及其?节点构成树$T$，返回$T$；
对第i个?结点，以$D_i$为训练集，以$A-A_g$为特征集，递归地调?步1~步5得到?树$T_i$，返回$T_i$。

2 剪枝

pruning

2.1 预剪枝

pre-pruning

在决策树?成的过程中，对每个Node在进?步划分之前进?估计，若当前结点的划分不能带来决策树泛化性的提升（结点划分后验证集精度变低），就停?划分，将此标记为叶结点。

优点：很好解决过拟合，还降减少了决策树的训练时间开销和测试时间开销。

缺点：失去了后续划分的性能提升可能，导致?拟合

2.2 后剪枝

post-pruning

在?成了完整的决策树后从叶?结点逐层向上计算验证集精度。如果剪枝后的验证集精度?于剪枝前的验证集精度，则执?剪枝操作。

优点&缺点：?拟合?险很?，但是训练的开销较?。

2.3 CART剪枝

CART采?后剪枝法，即先?成决策树，然后产?所有剪枝后的CART树，然后使?交叉验证检验剪枝的效

果，选择泛化能?最好的剪枝策略。

步骤：?先从?成算法产?的决策树$T_0$底端开始不断剪枝，直到$T_0$的根结点，形成?个?树序列$\{T_0,...,T_n\}$。然后通过交叉验证法在独?的验证数据集上对?树序列进?预测，从中选择最优的?树。

定义?树的损失函数：

\[C_\alpha(T) = C(T)+ \alpha |T| \]

$T$为任意树，$C(T)$为对训练数据的预测误差（如基尼指数）， $|T|$为?树的叶结点个数，$\alpha \geq 0 $为参数衡量训练数据的拟合程度与模型的复杂度， $C_\alpha(T) $是$T$的整体损失。

3. 决策树拓展

3.1 连续变量处理

C4.5连续属性离散化

给定样本集$D$和属性$a$，假定$a$在$D$上出现了$V$个不同的取值$a^1,...,a^V$，从小到大排序，基于划分点$t$分为两个子集$D^+$和$D^-$，对于连续属性$a$,我们可以考察包含$n-1$个元素的候选划分点集合：

\[T_a = \{\frac{a_1 + a_{i+1}}{2}| 1 \leq i \leq n-1\} \]

把区间的中位点作为候选划分点，对于每?个分割点计算信息增益。其中$Gain(D,a,t)$?是样本集基于$t$点进?划分后的信息增益。

\[Gain(D,a) = \max_{t \in T_a} Gain(D,a,t) = \max_{t \in T_a} Ent(D) - \sum_{\lambda \in \{-,+\}} \frac{|D_t^\lambda|}{|D|} Ent(D_t^\lambda) \]

3.2 缺失值处理

（1）如何在属性值缺失的情况下进?划分属性选择？

（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进?划分？

C4.5的缺失值处理

给定训练集$D$和属性$a$，令$\tilde{D}$表示$D$中在属性$a$上没有缺失值的样本?集。假定$a$在$D$上出现了$V$个不同的取值$a^1,...,a^V$。$\tilde{D}^v$为$\tilde{D}$在属性$a$上取值为$a^v$的样本?集，$\tilde{D}_k$表示$\tilde{D}$中属于第$k$类的样本?集。假定给每?个样本赋予?个权重$w_x$?（在决策树开始学习阶段，各样本的权重初始化为1），并定义：

$\rho = \frac{\sum_{x \in \tilde{D}}w_x}{\sum_{x \in D} w_x}$:属性$a$上?缺失值样本所占的?例
$\tilde{p}_k= \frac{\sum_{x \in \tilde{D}_k}w_x}{\sum_{x \in D} w_x}(1 \leq k \leq |\mathcal{Y}|)$:?缺失值样本中第$k$类所占的?例
$\tilde{r}_v= \frac{\sum_{x \in \tilde{D}^v}w_x}{\sum_{x \in D} w_x}(1 \leq v \leq V)$:?缺失值样本中属性$a$上取值为$a^v$占的?例
$Ent(\tilde{D}) = -\sum_{k=1}^{|\mathcal{Y}|} \tilde{p}_k \log_2 \tilde{p}_k$: 没有缺失值的样本?集的信息熵
$Gain(D,a) = \rho \times Gain(\tilde{D},a) = \rho \times (Ent(\tilde{D})-\sum_{v=1}^V \tilde{r}_v Ent(\tilde{D}^v))$:新信息增益

针对（2）：在划分时，

若样本的划分属性已知，则将划分与其取值对应的?结点，并且样本权值保持不变；

若样本的划分属性未知，则将同时划?所有的?结点，且样本权值在与属性值对应的?结点中调整为$\tilde{r}_v \times w_x$

3.3 回归树:CART

且输出变量是连续变量。如何使?决策树进?回归?

给定训练数据集$D = \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$。?个回归树对应着输?（特征）空间的?个划分以及在划分单元上的输出值。假设已经将输?空间划分为$M$个单元$R_1,...,R_M$, 并且在每个单元上有?个固定的输出值$c_m$，于是期望得到的回归树模型表示为

\[f(x) = \sum_{m=1}^M c_m I(x \in R_m) \]

?成过程如下：

选择第$j$个变量$x^{(j)}$和取值$s$作为切分变量（splitting variable）和切分点（splitting point）, 并定义两个区域

\[R_{1}(j,s) = \{x|x^{(j)} \leq s\} , R_2(j,s) = \{x| x^{(j)} >s\} \]

然后寻找最优切分变量和最优切分点。具体地，求解

\[\min_{j,s} \bigg[ \min_{c_1} \sum_{x_i \in R_1 (j,s)} (y_i-c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)}(y_i - c_2)^2 \bigg] \]

对固定输?变量$j$可以找到最优切分点$s$。

\[\hat{c}_1 = avg(y_i|x_i \in R_1(j,s)) ,\hat{c}_2 = ave(y_i|x_i \in R_2(j,s)) \]

遍历所有输?变量，找到最优的切分变量，构成?对$(j,s)$。依此将输?空间划分为两个区域，接着对每个区域执?同样的划分过程，直到满?停?条件。

当输?空间的划分确定时，可以?均?差（Mean Square Error）: $\sum_{x_i \in R_m}(y_i - f(x_i))^2$来表示回归树。对于训练数据的预测误差，?MSE最?的原则求解每个单元上的最优输出。单元$R_m$上的$c_m$的最优值$\hat{c}_m$是$R_m$上的所有输?实例$x_i$对应的输出$y_i$的均值，即

\[\hat{c}_m = ave(y_i | x_i \in R_m) \]

那么，就得到了我们期望找到的回归树$f(x) = \sum_{m=1}^M c_m I,(x \in R_m)$

2 总结

算法	适用	树结构	分裂准则	连续值处理	缺失值处理	剪枝
ID3	分类	多叉树	信息增益	不支持	不支持	不支持
C4.5	分类	多叉树	信息增益率	支持	支持	支持
CART	分类回归	二叉树	基尼指数、均方差	支持	支持	支持

集成学习

决策树