机器学习笔记-第四章决策树

基本流程

• 决策过程的最终结论对应了我们所希望的判定结果，决策过程中提出的每个判定问题都是对某个属性的“测试”，每个测试的结果或是导出最终结论，或是导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内。
• 一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；
  叶结点 ==> 决策结果， 其他结点 ==> 属性测试
• 从根结点到每个叶结点的路径对应了一个判定测试序列。

输入：训练集D，属性集A
过程：函数TreeGenerate(D, A)
 1. 生成结点node
 2. if D中样本属于同一类别C:
 3. 	将node标记为C类叶结点
 4. if A为空集 or D中样本在A上取值相同:
 5. 	将node标记为叶结点，其类别标记为D中样本数最多的类
 6. 从A中选择最优划分属性a*
 7. for a*_v in a*:
 8. 	为node生成一个分支；令D_v表示D中在a*上取值为a*_v的样本子集
 9. 	if D_v为空:
 10.		将分支结点标记为叶结点，其类别标记为D中样本最多的类
 11.	else:
 12.		以TreeGenerate(D_v, A{a*})为分支结点
输出：以node为根结点的一棵决策树 

划分选择

1. 信息增益

• 信息熵：是度量样本集合纯度最常用的一种指标。
• 定义：假定当前样本集合$D$中第$k$类样本所占的比例为 p k ( k = 1 , 2 , . . . , ∣ y ∣ ) p_k(k=1,2,...,|y|) pk​(k=1,2,...,∣y∣)，$D$的信息熵定义为 E n t ( D ) = − ∑ k = 1 ∣ y ∣ p k log ⁡ 2 p k Ent(D)=-sum_{k=1}^{|y|}p_klog_2p_k Ent(D)=−k=1∑∣y∣​pk​log2​pk​$Ent(D)$的值越小，则$D$的纯度越高。
• 属性$a$对样本集$D$进行划分获得的信息增益： 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}^{V}frac{|D^v|}{|D|}Ent(D^v) Gain(D,a)=Ent(D)−v=1∑V​∣D∣∣Dv∣​Ent(Dv)其中$V$为属性$a$的取值个数， D v D^v Dv表示第$v$个分支结点，即$D$中所有在属性$a$上取值为 a v a^v av的样本。
  • 一般而言，信息增益越大，意味着使用属性$a$来进行划分获得的纯度提升越大。
• 应用：ID3决策树学习算法[Quinlan, 1986]

2. 增益率

• 信息增益对可取值数目较多的属性有所偏好。
• 增益率对取值数目较少的属性有所偏好
• 增益率： G a i n . r a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) , Gain.ratio(D,a)=frac{Gain(D,a)}{IV(a)}, Gain.ratio(D,a)=IV(a)Gain(D,a)​,其中 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∣​称为属性$a$的“固有值”，属性数目取值越多，固有值越大。
• 应用：C4.5决策树算法[Quinlan, 1993]：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

3. 基尼指数

• 数据集$D$的纯度可用基尼值来度量： G i n i ( D ) = 1 − ∑ k = 1 ∣ y ∣ p k 2 Gini(D)=1-sum_{k=1}^{|y|}p_k^2 Gini(D)=1−k=1∑∣y∣​pk2​$Gini(D)$越小，数据集$D$的纯度越高。
• 属性$a$的基尼指数定义为 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}^{V}frac{|D^v|}{|D|}Gini(D^v) Gini.index(D,a)=v=1∑V​∣D∣∣Dv∣​Gini(Dv)选取基尼指数最小的属性作为最优划分属性。
• 应用：CART决策树[Breiman er al., 1984]

剪枝处理

• 对付过拟合的主要手段
• 预剪枝：在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点记为叶结点；
• 后剪枝：先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
• 性能评估方法：留出法，即预留一部分数据用作验证集以进行性能评估。
• 区别：一般情形下，后剪枝决策树的欠拟合风险很小，泛化能力往往由于预剪枝决策树，但训练时间开销大得多。

连续与缺失值

1. 连续值处理

• 二分法：选取信息增益最大的划分点进行二分。
• 注意：与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。

2. 缺失值处理

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

• 在计算信息增益时，使用该属性中没有缺失值的样本子集，并乘上无缺失值样本所占的比例$\rho$，公式为： ρ × G a i n ( D ~ , a ) rhotimes Gain(tilde{D},a) ρ×Gain(D~,a)

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

• 将属性值缺失的样本以不同的概率划入到不同的子节点中去。

多变量决策树

• 若我们把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。
• 多变量决策树：实现“斜划分”甚至更复杂划分的决策树。
  • 以实现斜划分的多变量决策树为例：非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试，是一个形如 ∑ 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$可在该结点所含的样本集和属性集上学得。