决策树模型

决策树模型概述

决策树方法的目标就是在一个树的结构上,根据节点的判断来搜索类别,对于一个二分判决问题,我们可以将其类比为二叉树,用内部节点代表一个特征或者属性,用叶子节点代表一个类别。

决策树模型呈树形结构,有着树结构的优点:不必测试所有特征和区域,但是也面临着两个问题:一是高维特征空间不可见,如何确定节点?,二是我们怎么知道应该从那些特征开始? 这也就引出了决策树模型的关键问题:

  • 问题数
  • 划分(问题)选择
  • 决策树生成
  • 决策树剪枝

问题数

离散值情况:以特征或者特征可能的离散值作为问题

连续值情况:以每个维度的样本特征作为问题

无论特征值是连续还是离散,确定每个属性所产生的候选问题后,最后的候选问题总数是:
$$N = \sum N_i$$

划分选择

我们定义非纯度 $IM(Impurity\;Measure)$ 作为衡量度量类别划分优劣的标准,$IM$ 定义应该满足以下两点:

  • $IM$ 最大时,当前的划分应使所有数据占各类别的比例相等:
    $$ p = \frac {1} {number\;of\;classes}$$
  • $IM$ 最小时为 $0$,当前的划分使所有数据都是相同类,这也是我们的期望目标

所以最后的划分目标是:选择能最大程度上减少类别非纯度的问题作为划分节点。非纯度的减少量为:
$$ \Delta I(t) = 1 - \frac {N_{tY}} {N_t}I(tY) - \frac {N_{tN}} {N_t}I(tN) $$

$IM$ 在不同的算法中有着不同的度量方式,较为典型的就是熵度量基尼度量

非纯度的熵度量

$$ I(D) = Entropy\,(D) = - \sum_{i=1}^kp_i\log p_i $$

信息增益

$$ Gain\,(D,a) = Entropy\,(D) - \sum_{v=1}^V \frac {|D^v|} {|D|} Entropy\,(D^v) $$

其中 $v$ 是特征 $a$ 的问题数

显然,$ Gain\,(D,a) $ 偏好划分问题数 $v$ 多的特征。直观上的理解是:划分区间越细,区域内的纯度也就越高,相对未划分时的信息增益也就越大,一个极端的情况是每个区间只有一个样本,此时信息熵为 $0$,划分的信息增益即为$ Gain\,(D,a) $。

$ID3$ 决策树使用了信息增益作为非纯度的度量标准,信息增益越大,划分效果越好。

信息增益比

$$ Gain_ratio\,(D,a) = \frac {Gain\,(D,a)} {IV(a)}
\\s.t.\; IV(a) = - \sum_{v=1}^V \frac {|D^v|} {|D|} \log \frac {|D^v|} {|D|} $$

其中 $v$ 是特征 $a$ 的问题数,$IV(a)$ 实际上就是数据集 $D$ 关于特征 $a$ 的信息熵

和信息增益不同,信息增益比可能对划分问题数 $v$ 少的特征有所偏好,因为 $v$ 越小 $IV(a)$ 也就越小,例如 $-\sum_{v=1}^3 \frac 1 3 \log \frac 1 3 \gt -\sum_{v=1}^2 \frac 1 2 \log \frac 1 2 $。

$C4.5$ 决策树使用了信息增益比作为非纯度的度量标准,信息增益比越大,划分效果越好。

非纯度的基尼度量

$$ I(D) = Gini\,(D) = \sum_{k=1}^Kp_k(1-p_k) = 1- \sum_{k=1}^K p_k^2$$

基尼指数

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

$CART$ 决策树使用了基尼指数作为非纯度的度量标准,基尼指数越小,划分效果越好。

停止划分
叶子节点纯度达到预设阈值后,停止划分,并对叶子节点进行类别设置。 按概率最大的类别设定:
$$ j = \arg\max_i p_i $$

决策树生成

决策树的生成过程和传统树结构的生成过程相同,都是一个自顶向下,不断增加节点的迭代过程。

ID3 算法

$ID3$ 算法的划分选择依据是最大化信息增益,以属性特征作为结点问题,划分选择的过程其实就是特征选择的过程。

$ID3$ 算法以信息增益作为非纯度的度量标准,所以在特征选择时,会倾向于选择特征取值较多的特征,也正是因为这个原因,$ID3$ 算法不能够处理连续的特征值,如果直接按照连续值的取值进行分类,分出的类别将会非常多,最后学得的决策树可能只有这一连续值特征,明显不具备泛化性能,若是简单地把连续值分成 $n$ 类,$n$ 的选择对特征选择有很大的影响,通常情况下人工很难找到优秀的一个 $n$。

C4.5 算法

$C4.5$ 算法和 $ID3$ 算法类似,把非纯度的度量标准由信息增益改成了信息增益比,于是有了以下改进:

  • 克服了用信息增益选择特征时偏向选择取值多的特征
  • 能够对连续值进行离散化
  • 能够处理缺失值

连续值处理

  1. 对特征的取值进行升序排序
  2. 两个特征取值的平均值作为候选划分点,将数据集分成两部分,计算每个候选划分点的信息增益
  3. 选择修正后信息增益最大的划分点作为该特征的最佳分裂点
  4. 计算最佳划分点的信息增益率作为特征的信息增益率

此处需对最佳划分点的信息增益进行修正:减去 $\log_2 \frac {N-1} {|D|}$,其中 $N$ 是连续特征的取值个数,$D$ 是训练数据数目,此修正使当离散属性和连续属性并存时,$C4.5$ 算法倾向于选择连续特征做最佳树分裂点。

算法实例



缺失值处理

对于缺失值,我们需要解决两个问题:

  1. (训练)如何在属性值缺失的情况下进行划分属性选择?
  2. (测试)给定划分属性,若样本在该属性上的值缺失,如何对样本进行分类?

对于属性 $a$,我们用 $\rho$ 来表示在该属性上无缺失值样本所占的比例,$\tilde{p_k}$ 表示在该属性上无缺失值样本中第 $k$ 类所占的比例,$\tilde{r_v}$ 表示无缺失值样本中在属性 $a$ 上取值 $a^v$ 的样本的比例。

对于问题 $1$:
基于以上定义,我们可以把信息增益的公式推广为:

$$ Gain\,(D,a) = \rho \times Gain\,(\tilde{D},a) = \rho \times \left( Entropy\,(\tilde{D}) - \sum_{v=1}^V \tilde{r_v} Entropy\,(\tilde{D}^v) \right) $$
其中
$$ Entropy\,(\tilde{D}) = - \sum_{k=1}^K \tilde{p_k} \log_2\tilde{p_k} $$

对于问题 $2$:

若样本 $x$ 在属性 $a$ 上的取值已知,则将 $x$ 划分到与其取值对应的子节点,样本权重 $w_x$ 不变;若样本 $x$ 在属性 $a$ 上的取值未知,则将 $x$ 划分到所有子节点,且样本权值在属性 $a^v$ 对应的子节点中调整为 $\tilde{r_v} $。直观地看,就是让同一个样本以不同的概率划分到不同的子节点中去。

算法实例



CART 算法

$Classification\;And\;Regression\;Tree,\;CART$ 是分类与回归树,与 $ID3$ 和 $C4.5$ 不同,$CART$ 不单单能够用户分类,同样也可以用于回归,其本质是一个二叉树,左分支是“是”,右分支是“否”。生成过程的第一步是生成尽可能大的决策树,第二步使用验证集对决策树进行剪枝。

回归树

回归树在构建过程中始终遵循平方误差最小化的准则

其中,$c_m$ 为元素在空间 $R_m$ 上的输出,显然当 $c_m$ 取 $R_m$ 中所有实例输出的均值时,平方误差最小。在式 $(5.21)$ 中,对每个不同的 $j$ 都有不同的 $c_1$ 和 $c_2$,此时 $c$ 可以看到当前区域的均值,而整个式子就是寻找一组使划分后两个区域的方差和最小的 $j,s$。

分类树

分类树使用基尼指数选择最优特征,同时决定该特征的最优二值切分点,在特征 $a$ 的条件下,集合 $D$ 的基尼指数为:

$$ Gini\,(D,a) = \frac {|D_1|}{|D|} Gini\,(D_1) + \frac {|D_2|}{|D|} Gini\,(D_2)$$

剪枝算法

ID3及C4.5算法的剪枝

构造整体损失函数:
$$ C_{\alpha}\left( T \right) = C\left( T \right) + \alpha\left| T \right|$$

其中 $C(T)$ 表示模型对训练数据的预测误差,$|T|$ 表示模型复杂度,通常可以用节点数量来表示,$\alpha \ge 0 $ 控制两者之间的影响,较大的 $\alpha$ 会促使选择较为简单的模型,反之则会选择较为复杂的模型,剪枝的过程也就是当 $\alpha$ 给定时,选择损失函数最小的模型。

算法描述


由算法可以看出,式 $(5.15)$ 值考虑两个数的损失函数的差,其计算可以在局部进行

CART算法的剪枝

按照损失函数的定义,对于一个子树 $|T_t|$,有:

$$C_{\alpha}(T_t)=C(T_t)+\alpha |T_t|$$

对于单节点 $t$,有:

$$C_{\alpha}(T_t)=C(T_t)+\alpha $$

当 $\alpha=0$ 或者充分小时,在某一个 $\alpha$ 有:

$$C_{\alpha}(T_t)=C_{\alpha}(t)
\\ \alpha = \frac{C(t)-C_(T_t)}{|T_t|-1}$$

此时表示 $T_t$ 和 $t$ 有相同的损失函数值。

为此,对 $T_0$ 中每一个内部节点 $t$,计算

$$ g(t)=\frac{C(t)-C_(T_t)}{|T_t|-1} $$

它表示剪枝后整体损失函数减少的程度(抛开正则项),在 $T_0$ 中减去 $g(t)$ 最小的 $T_t$,得到子树 $T_1$,同时将最小的 $g(t)$ 设为 $\alpha_1$, $T_1$ 即为区间 $[\alpha_1, \alpha_2)$ 之间的最优子树,不断迭代,增加 $\alpha$ 的值,直至根节点。

对于同一棵树的结点, $\alpha$ 都是一样的,当 $\alpha$ 从 $0$ 开始缓慢增大,总会有某棵子树该剪,其他子树不该剪的情况,即 $\alpha$ 超过了某个结点的 $g(t)$,但还没有超过其他结点的 $g(t)$。这样随着 $\alpha$ 不断增大,不断地剪枝,就得到了 $n+1$ 棵嵌套的子树。

算法描述

对于子树 $T_k$ 来说,节点 $t$ 是当前 $\alpha$ 下最优的切分点,其它节点的 $g(t)$ 都比该节点的 $g(t)$ 大。

总的来说,就是 $ID3$ 和 $C4.5$ 剪枝时 $\alpha$ 是人为给定的,而 $CART$ 剪枝时的 $\alpha$ 是根据特征值在 $[0, +\infty)$ 找到一系列的值,从而得到一系列剪枝后的树,从中选取最优的。从最宏观的角度去考虑的话,就是利用 $\alpha$ 生成 $T_{\alpha}$。抽象一下,即从无限的实数中找寻有限个数的 $T_{\alpha}$。

预剪枝与后剪枝

剪枝操作是防止决策树过拟合的有效方法,上图所示的是一个未经剪枝的决策树。

预剪枝

预剪枝就是在树的构建过程(只使用训练集),设置一个阈值(样本个数小于预定阈值或基尼指数小于预定阈值),若当前节点划分前和划分后的误差超过这个阈值则进行划分,否则不进行划分,预剪枝基于“贪心”本质禁止这些分支展开,防止了过拟合的同时也带来了欠拟合的风险。

后剪枝

后剪枝是先按照训练集生成一颗完整的决策树,随后按照验证集尝试不断回缩,设置一个阈值,若回缩后模型的精度和回缩前模型的精度差超过了这个阈值,则进行回缩(剪枝)。一般情况下,后剪枝决策树通常比预剪枝决策树保留了更多的分支,所以欠拟合的风险很小,泛化性能更好,但是后剪枝过程首先需要生成完整的决策树,并且自底向上地对所有非叶子节点逐一考察,因此时间开销远大于预剪枝和未剪枝决策树

参考文献:
[1] 周晓飞,《统计机器学习》,中国科学院大学2017年秋季研究生课程
[2] 李航,《统计学习方法》,清华大学出版社
[3] 周志华,《机器学习》,清华大学出版社