第四章 决策树

决策树（decision tree） 是一种常见的机器学习方法。一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶节点对应于决策结果，其他每个结点则对应于一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强的决策树，算法如下：

input: 
	训练集 D={(x_1,y_1),(x_2,y_2),...,(x_m,y_m)};
	属性集 A={a_1,a_2,...,a_d}.

process: 
	def TreeGenerate(D, A)
		生成结点 node；
		if D 中样本全属于同一类别 C
			将 node 标记为 C 类叶结点
			return
		if A 为空 or D 中样本在 A 上取值相同
			将 node 标记为叶结点，其类别标记为 D 中样本数量最多的类
		从 A 中选择最优划分属性 a_star
		for a_v in a_star:
			为 node 生成一个分支
			令 D_v 表示 D 中在 a_star 上取值为 a_v 的样本子集
			if D_v 为空:
				将分支结点标记为叶结点，其类别标记为 D 中样本最多的类
			else:
				以 TreeGenerate(D_v, A{a_star}) 为分支节点

output:
	以 node 为根结点的一颗决策树

由此可见，决策树的生成是一个递归过程。

从算法中可以看出，决策树学习的关键是划分最优属性。一般来说，随着划分过程不断进行，要使决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度（purity） 越来越高。

信息熵（information entropy） 是度量样本集合纯度最常用的一种指标。假定当前样本集合 D D D 中第 k k k 类样本所占比例为 p k ( k = 1 , 2 , . . . , ∣ y ∣ ) p_k(k=1,2,...,|y|) pk​(k=1,2,...,∣y∣) ，则 D D D 的信息熵定义为：

E n t ( D ) = − ∑ k = 1 ∣ y ∣ p k log ⁡ 2 p k Ent(D)=-sum_{k=1}^{|y|}p_klog_2 p_k Ent(D)=−k=1∑∣y∣​pk​log2​pk​

E n t ( D ) Ent(D) Ent(D) 的值越小，则 D D D 的纯度越高。

假定离散属性 a a a 有 V V V 个可能的取值 a 1 , a 2 , . . . , a V {a^1,a^2,...,a^V} a1,a2,...,aV ，若使用 a a a 来对样本集 D D D 进行划分，则会产生 V V V 个分支结点，其中第 v v v 个分支结点包含了 D D D 中所有在属性 a a a 上取值为 a v a^v av 的样本，记为 D v D^v Dv 。利用上式可以计算出 D v D^v Dv 的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 ∣ D v ∣ / ∣ D ∣ |D^v|/|D| ∣Dv∣/∣D∣ ，即样本数越多的分支结点的影响越大，于是可计算出用属性 a a a 对样本集 D D D 进行划分所获得的信息增益（information gain）：

G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(D,a)=Ent(D)-sum_{v=1}^Vfrac{|D^v|}{|D|}Ent(D^v) Gain(D,a)=Ent(D)−v=1∑V​∣D∣∣Dv∣​Ent(Dv)

信息增益越大，则意味着使用属性 a a a 来进行划分所获得的纯度提升越大。因此，可用信息增益来进行决策树的划分属性选择。

信息增益准则对可取值树木较多的属性有所偏好，为减少这种偏好可能带来的不利影响，可以使用增益率（gain ratio）：

G a i n _ r a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) (4.2) Gain_ratio(D,a)=frac{Gain(D,a)}{IV(a)}tag{4.2} Gain_ratio(D,a)=IV(a)Gain(D,a)​(4.2)

I V ( a ) = − ∑ v = 1 V = ∣ D v ∣ ∣ D ∣ log ⁡ 2 ∣ D v ∣ ∣ D ∣ IV(a)=-sum_{v=1}^V=frac{|D^v|}{|D|}log_2frac{|D^v|}{|D|} IV(a)=−v=1∑V​=∣D∣∣Dv∣​log2​∣D∣∣Dv∣​

其中 I V ( a ) IV(a) IV(a) 称为 a a a 的固有值（intrinsic value）。属性 a a a 的可能取值数目越多，则 I V ( a ) IV(a) IV(a) 的值通常会越大。需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此 C 4.5 C4.5 C4.5 算法使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

基尼值可以度量数据集纯度：

G i n i ( D ) = ∑ k = 1 ∣ y ∣ ∑ k ′ ≠ k p k p k ′ = 1 − ∑ k = 1 ∣ y ∣ p k 2 Gini(D)=sum_{k=1}^{|y|}sum_{k'ne k}p_kp_{k'}=1-sum_{k=1}^{|y|}p_k^2 Gini(D)=k=1∑∣y∣​k′=k∑​pk​pk′​=1−k=1∑∣y∣​pk2​

G i n i ( D ) Gini(D) Gini(D) 反映了从数据集 D D D 中随机抽取两个样本，其类别标记不一致的概率，因此基尼值越小则数据集纯度越高。基尼指数（Gini index） 定义：

g i n i _ i n d e x ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ G i n i ( D v ) gini_index(D,a)=sum_{v=1}^Vfrac{|D^v|}{|D|}Gini(D^v) gini_index(D,a)=v=1∑V​∣D∣∣Dv∣​Gini(Dv)

因此在侯选属性集合 A A A 中，选择使基尼指数最小的属性作为最优划分属性。

剪枝（pruning） 是决策树学习算法中解决过拟合的主要手段。

决策树剪枝的基本策略有预剪枝（prepruning） 和后剪枝（post-pruning）。预剪枝指在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

要想使用连续属性来生成决策树，就需要对连续值进行处理。最简单的策略是采用二分法（bi-partition）。

假定有一个连续属性 a a a ，它具有多个不同的取值，将这些值从小到大排序，使得其在某个划分点 t t t 可以对样本集 D D D 进行划分，此时 t t t 就等于相邻两被划分元素取值的均值：

T a = { a i + a i + 1 2 ∣ 1 ≤ i ≤ n − 1 } T_a=left{frac{a^i+a^{i+1}}{2}|1le ile n-1right} Ta​={2ai+ai+1​∣1≤i≤n−1}

为选取最优的划分点，可对式 4.2 进行改造：

G a i n ( D , a ) = max ⁡ t ∈ T a G a i n ( D , a , t ) = max ⁡ t ∈ T a E n t ( D ) − ∑ λ ∈ { − , + } ∣ D t λ ∣ ∣ D ∣ E n t ( D t λ ) Gain(D,a)=max_{tin T_a}Gain(D,a,t)=max_{tin T_a}Ent(D)-sum_{lambdainleft{-,+right}}frac{|D_t^lambda|}{|D|}Ent(D_t^lambda) Gain(D,a)=t∈Ta​max​Gain(D,a,t)=t∈Ta​max​Ent(D)−λ∈{−,+}∑​∣D∣∣Dtλ​∣​Ent(Dtλ​)

其中 G a i n ( D , a , t ) Gain(D,a,t) Gain(D,a,t) 是样本集 D D D 基于划分点 t t t 二分后的信息增益，因此可选择使其最大化的划分点。

如何在属性值缺失的情况下进行划分属性选择？

给定训练集 D D D 和属性 a a a ，令 D ~ tilde D D~ 表示 D D D 中在属性 a a a 上没有缺失值的样本子集。假定属性 a a a 有 V V V 个可取值 { a 1 , a 2 , . . . , a V } left{a^1,a^2,...,a^Vright} {a1,a2,...,aV} ，令 D ~ v tilde D^v D~v 表示 D ~ tilde D D~ 中在属性 a a a 上取值为 a v a^v av 的样本子集， D ~ k tilde D_k D~k​ 表示 D ~ tilde D D~ 中属于第 k ( k = 1 , 2 , . . . , ∣ Y ∣ ) k(k=1,2,...,|mathcal{Y} |) k(k=1,2,...,∣Y∣) 类的样本子集，则显然有 D ~ = ⋃ k = 1 ∣ y ∣ D ~ k tilde D=bigcup_{k=1}^{|y|}tilde D_k D~=⋃k=1∣y∣​D~k​ ， D ~ = ⋃ v = 1 V D ~ v tilde D=bigcup_{v=1}^Vtilde D^v D~=⋃v=1V​D~v 。假定为每个样本 x x x 赋予一个权重 w x w_x wx​ ，并定义：

ρ = ∑ x ∈ D ~ w x ∑ x ∈ D w x rho=frac{sum_{xintilde D}w_x}{sum_{xin D}w_x} ρ=∑x∈D​wx​∑x∈D~​wx​​

ρ ~ k = ∑ x ∈ D ~ k w x ∑ x ∈ D w x ( 1 ≤ k ≤ ∣ Y ∣ ) tilderho_k=frac{sum_{xintilde D_k}w_x}{sum_{xin D}w_x}(1le kle|mathcal{Y} |) ρ~​k​=∑x∈D​wx​∑x∈D~k​​wx​​(1≤k≤∣Y∣)

r ~ v = ∑ x ∈ D ~ v w x ∑ x ∈ D w x ( 1 ≤ v ≤ V ) tilde r_v=frac{sum_{xintilde D^v}w_x}{sum_{xin D}w_x}(1le vle V) r~v​=∑x∈D​wx​∑x∈D~v​wx​​(1≤v≤V)

直观来看，堆属性 a a a ， ρ rho ρ 表示无缺失值样本所占的比例， p ~ k tilde p_k p~​k​ 表示无缺失值样本中第 k k k 类所占的比例， r ~ v tilde r_v r~v​ 表示无缺失值样本中在属性 a a a 上取值 a v a^v av 的样本所占的比例。显然 ∑ k = 1 ∣ Y ∣ p ~ k = 1 sum_{k=1}^{|mathcal Y|}tilde p_k=1 ∑k=1∣Y∣​p~​k​=1 ， ∑ v = 1 V r ~ v = 1 sum_{v=1}^Vtilde r_v=1 ∑v=1V​r~v​=1 。基于上述定义，可对式 4.2 进行改造：

G a i n ( D , a ) = ρ × G a i n ( D ~ , a ) = ρ × ( E n t ( D ~ ) − ∑ v = 1 V r ~ v E n t ( D ~ v ) ) Gain(D,a)=rhotimes Gain(tilde D,a)=rhotimesleft(Ent(tilde D)-sum_{v=1}^Vtilde r_v Ent(tilde D^v)right) Gain(D,a)=ρ×Gain(D~,a)=ρ×(Ent(D~)−v=1∑V​r~v​Ent(D~v))

其中，由式 4.1 ，有：

E n t ( D ~ ) = − ∑ k = 1 ∣ Y ∣ p ~ k log ⁡ 2 p ~ k Ent(tilde D)=-sum_{k=1}^{|mathcal Y|}tilde p_klog_2tilde p_k Ent(D~)=−k=1∑∣Y∣​p~​k​log2​p~​k​

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

若样本 x x x 在划分属性 a a a 上的取值已知，则将 x x x 划入与其取值对应的子结点，且样本权值在子结点中保持为 w x w_x wx​ 。若样本 x x x 在划分属性 a a a 上的取值未知，则将 x x x 同时划入所有子结点，且样本权值在与属性值 a v a^v av 对应的子结点中调整为 r ~ v ⋅ w x tilde r_vcdot w_x r~v​⋅wx​ 。直观的看，这就是让同一个样本以不同的概率划入到不同的子结点中去。

若把每个属性视为坐标空间中的一个坐标轴，则 d d d 个属性描述的样本就对应了 d d d 维空间中的一个数据点，对样本分类则意味着在这个空间中寻找不同类样本之间的分类边界。决策树所形成分类边界的特点是轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成。

因此，这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值。但是当学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似。

此时决策树非常复杂，由于要进行大量的属性测试，因此预测时间开销很大。若能使用斜的划分边界，如上图红色线断所示，决策树模型将被简化。多变量决策树（multivariate decision tree） 可以实现这个目标。在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试，即每个叶结点是一个形如 ∑ i = 1 d w i a i = t sum_{i=1}^dw_ia_i=t ∑i=1d​wi​ai​=t 的线性分类器，其中 w i w_i wi​ 是属性 a i a_i ai​ 的权重， w i w_i wi​ 和 t t t 可在该结点所含的样本集和属性集上学得。于是，与传统的单决策树（univariate decision tree） 不同，在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是建立一个合适的线性分类器。