4 决策树

mac2026-02-26 8

4.1 基本流程

一般的，一棵决策树包含一个根节点、若干个内部节点和若干个叶节点；叶节点对应于决策结果，其他每个节点则对应于一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子节点中；根节点包含样本全集。下面为决策树学习基本算法。

输入：训练集 D = ｛(x₁,y₁), …, (x_m,y_m)｝　　　属性集 A = ｛a₁, a₂, …, a_m｝过程：函数 TreeGenerate(D, A) 1：生成节点 node 2：if D 中样本全部属于同一类别 C then 3：　将 node 标记为 C 类叶节点；return 4：end if 5：if A = $∅\emptyset$ OR D 中样本在 A 上取值相同 then 6：　将 node 标记为叶节点，其类别标记为 D 中样本数最多的类；return 7：end if 8：从A中选择最优划分属性 a_* // 下节讨论如何最优划分属性 9：for a_* 的每一个值 a_*^vdo 10：　为 node 生成一个分支；令 D_v 表示 D 中在 a_* 上取值为 a_*^v 的样本子集； 11：　if D_v 为空 then 12：　　将分支节点标记为叶节点，其类别标记为 D 中样本最多的类；return 13：　else 14：　　以 TreeGenrate (D_v,A \ {a_*}) 为分支节点 15：　end if 16：end for 输出：以 node 为根节点的一棵决策树

4.2 划分选择

一般而言,随着划分属性过程不断进行,我们希望决策树节点的纯度(purity)越来越高,即决策树的分直接点所包含的样本尽可能属于同一类别.

4.2.1 信息增益

信息熵(information entropy)是度量样本集合纯度最常用的一种指标,信息熵定义为: $-\sum_{k=1}^{|y|}p_klog_2p_k \tag{4.1}$ 其中:

|y| 表示标签取值的个数,如二分类问题则|y|=2.p_k表示样本集合 D 中第 k 类样本所占的比例

信息增益(information gain)定义为: $Gain(D,a)=Ent(D)−∑v=1V∣Dv∣∣D∣Ent(Dv)(4.2)Gain(D,a)=Ent(D)-\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)\tag{4.2}$ 其中:

D_v 为样本 D 中第 v 个分支节点包含了 D 中所有在属性 a 上取值为 a^v 的样本

∣Dv∣D\frac{|D_v|}{D}

表示给分支节点赋予的权重

一般而言,信息增益越大,则意味着使用属性 a 来进行划分所获得的"纯度提升"越大.因此,我们使用信息增益来进行决策树的划分属性选择

以下面的西瓜数据集为例:

以属性"色泽"为例,它有三个可能的取值:{青绿、乌黑、浅白}，分别标记为: D¹(色泽=青绿), D²(色泽=乌黑), D³(色泽=浅白) 则: $Ent(D1)=−(36log236+36log236)=1.000Ent(D_1)=-(\frac36log_2\frac36+\frac36log_2\frac36)=1.000$ $Ent(D2)=−(46log246+26log226)=0.918Ent(D_2)=-(\frac46log_2\frac46+\frac26log_2\frac26)=0.918$ $Ent(D3)=−(15log215+45log245)=1.000Ent(D_3)=-(\frac15log_2\frac15+\frac45log_2\frac45)=1.000$ 于是,根据式(4.2)可计算出属性"色泽"的信息增益为: $\begin{aligned} Gain(D,色泽) &= Ent(D)-\sum_{v=1}^3\frac{|D^v|}{|D|}Ent(D^v) \\&=0.998-(\frac{6}{17}\times1.0000+\frac{6}{17}\times0.918+\frac{5}{17}\times0.722) \\&=0.109 \end{aligned}$ 类似的,我们计算出其他属性的信息增益,比较各自的值,将最大的选为属性划分.

注意：当父节点上使用如“色泽”作为属性划分时，其子节点不能再使用该属性。

4.2.2 增益率

实际上，信息增益准则对可取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响，著名的 C4.5 决策树算法使用增益率（gain ratio）来选择最优划分属性。采用与式(4.2)相同的符号表示，增益率定义为： $Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}\tag{4.3}$ 其中 $IV(a)=-\sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}\tag{4.4}$ 称为属性 a 的固有值(intrinsic value)，属性 a 的可能取值数目越多（即V越大），则IV(a)的值越大

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

4.3 剪枝处理

剪枝（pruning）是决策树学习算法对付过拟合的主要手段，它分为预剪枝和后剪枝。

预剪枝指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点。

后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上的对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。

判断决策树泛化性能是否提升可使用性能评估方法，如留出法。

根据信息增益决定如何选择决策树的属性进行最优属性划分根据性能指标决定是否进行剪枝（即需不需要这个属性划分）

通常，后剪枝决策树比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险小，泛化性能往往优于预剪枝决策树。但其训练时间开销比预剪枝决策树大。

4.4 连续与缺失值

4.4.1 连续值处理到目前我们只讨论了基于离散属性来生成决策树，现实学习任务中常常会遇到连续属性，下面讨论如何在决策树学习中使用连续属性。

我们常用连续属性离散化技术来对连续属性进行处理，最常用的策略是二分法(bi-partition)

给定样本集 D 和连续属性 a ，假设 a 在 D 上出现了 n 个不同的取值，将这些值从小到大进行排序，即为｛a¹,a², …, aⁿ｝。基于划分点 t 可以将 D 分为子集 D_t⁺ 和 D_t^-，其中 D_t^- 包含哪些属性 a 上取值不大于 t 的样本，而 D_t⁺ 则包含哪些在属性 a 上取值大于 t 的样本。显然，对相邻的属性取值 aⁱ 与 aⁱ⁺¹来说，t 在区间 [aⁱ,aⁱ⁺¹) 中取任意值所产生的划分结果相同。因此，对连续属性 a ，我们可考察包含 n-1 个元素的候选划分点集合 $T_a=\{\frac{a^i+a^{i+1}}{2}|1≤i≤n-1\}\tag{4.7}$ 即把区间[aⁱ,aⁱ⁺¹)的中卫店作为候选划分点。然后，我们就可以像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。例如，可以对式(4.2)稍加改造：其中Gain(D,a,t)是样本集基于划分点 t 二分后的信息增益。于是，我们就可以选择使 Gain(D,a,t)最大化的划分点。

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

4.2.2 缺失值处理

对于样本中含有缺失值的情况，我们需要解决两个问题

如何在属性值缺失的情况下进行划分属性选择？给定划分属性，若样本在该属性上的值缺失，如何进行样本划分？

此处参考书本

4.5 多变量决策树

此处参考书本，理解即可。

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

最新回复(0)