机器学习第4讲——决策树
决策树的表示
基本组成：决策节点，分支，叶子
- 根节点：决策树中最上面的节点
- 每个分支是一个新的决策结点，或者是树的叶子节点
分裂策略
基于离散特征的分裂方法
基于连续特征的分裂方法
决策树CLS算法
早期的决策树学习算法，是许多决策树学习算法的基础。
基本思想
- 从一棵空决策树开始，选择某一属性(分类属性)作为测试属性；
- 该测试属性对应决策树中的决策结点；
- 根据该属性的值的不同，可将训练样本分成相应的子集：
- 子集为空，或子集中的样本属于同一个类：该子集为叶子结点；
- 否则，对应于决策树的内部节点，需要选择一个新的分类属性对该子集进行划分。
CLS存在问题
在步骤3中，根据“某种策略”选取属性A，没有规定采用何种测试属性；
实践表明，测试属性集的组成以及测试属性的先后对决策树的学习具有举足轻重的影响
决策树常见问题——属性最佳划分
一般而言，随着长树过程的不断进行，希望决策树的分支结点所包含的样本越来越归属于同一类别，即结点的“不纯度”(impurity)越来越低；
因此为了确定按某个属性划分的效果，需要比较划分前(父结点)和划分后(所有子结点)不纯度的降低程度，降低越多，划分效果越好。
不纯度如何数学定义？
令p(i)表示：结点中第i类样本所占有的比例
最佳划分的度量标准
信息增益：ID3算法
例题PPT24
结果：0.381
增益率(gain ratio): C4.5算法
信息增益准则对可取值数目较多的属性有所偏好
例题(同上数据集)：
注意：增益率准则对可取值数目较少的属性有所偏好
因此：C4.5算法并不是直接选择增益率最大的候选划分属性
- 先从候选划分属性中找出信息增益高于平均水平的属性；
- 再从中选择增益率最高的
基尼指数：CART
基尼指数定义为(详细见下面目录)：从当前结点样本的标签集合D中随机抽取两个样本，其类别标签不一致的概率
pj：数据集中样本从属于第j类的概率
Gini(D)越小，则数据集D的纯度越高
属性a的基尼指数定义为：
决策树常见问题——叶子结点的判定
不考虑树的规模过大而导致的过拟合问题：
- 当前结点中的样本集合为空，即空叶子；
- 前结点中的所有样本全部归属于同一类别，即纯叶子；
- 当前结点的所有样本在所有属性上取值相同，即属性被测试完的叶子。
决策树常见问题——过拟合问题
剪枝(pruning)是解决过拟合问题的主要手段，基本策略有“预剪枝”(prepruning)和“后剪枝”(post pruning)
- 预剪枝：在算法完美划分训练数据之前就停止树生长；
- 后剪枝：允许树过度拟合训练数据，然后对树进行后修剪
解决过拟合问题的方法(没看懂)：
- 使用与训练样例截然不同的一套分离的样例，来评估通过后剪枝从树上修剪结点的效果；
- 使用所有可用数据进行训练，但进行统计测试来估计生长或修剪一个特定的结点是否有可能改善在训练集以外的样例上的性能；
- 使用一个明确的标准来衡量训练样例和决策树的复杂度，当这个编码的长度最小时停止树增长。
留出法(即第一种方法)
将可用数据分成两个样例集合：
- 训练集用于形成学习到的假设；
- 验证集用于评估这个假设在后续数据上的精度。
通常的做法：2/3作训练集，1/3作验证集。
决策树常见问题——剪枝问题
剪枝是决策树学习算法对付“过拟合”的主要手段；
是否剪枝，取决于剪枝能否带来决策树泛化性能提升。
预剪枝
后剪枝
对比
连续值与缺失值
连续值处理
例题PPT42
缺失值处理
仅使用无缺失的样本进行学习？
对数据信息极大的浪费。
使用有缺失的样本，需要解决哪些问题？
- 如何在属性缺失的情况下进行划分属性选择？
- 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
Q1
Q2
例题PPT46
多变量决策树
单变量决策树分类边界：轴平行
多变量决策树：非叶节点不再是仅对某个属性，而是对属性的线性组合
其中wi是属性ai的权值，可在该节点所含的样本集和属性集上学得
CART算法(Classification and Regression Tree)
既可以用于分类任务，也可以用于回归任务
CART算法由两部分组成：
- 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
- 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树。
CART回归树生成
Youtube: https://www.youtube.com/watch?v=g9c66TUylZ4
回归树：叶子结点不再表示一个类，而是数值
上面这种情况的数据，难以用线描述，更适合回归树的形式。
f(x)就是：点落在哪个区域，预测值就跟哪个区域相同
Cm最优值: 就是取同一个区域的平均值作为该区域的Cm
回归树生成算法
CART分类树生成
基尼指数
Youtube: https://www.youtube.com/watch?v=_L39rN6gz7Y&t=348s
二分类问题：Gini(D) = 1 - p2 - (1 - p)2
wj: 第j个类
分类树生成算法
例题PPT13
CART剪枝：代价复杂度剪枝(Cost Complexity Pruning,CCP)
Cα(T): 代价复杂度，表示在保证训练误差尽可能小的前提下，控制树的复杂度以防止过拟合
α：正则化参数，控制误差与复杂度之间的权衡；
- 当α=0，完全追求最小训练误差，容易过拟合
- 当α>0, 在减少训练误差的同时，会惩罚叶子节点
CART VS C4.5
剪枝：
其他方面：
例题
CART剪枝(PPT19)
决策树生成、剪枝与测试(PPT21)
首先，该数据集中存在2个离散特征和2个连续特征
- 计算每个特征，每种划分情况下的基尼指数，取所有结果中最小的(减少的最多的)，作为根的划分特征和划分阈值
- 离散特征：判断是或不是计算即可；
- 连续特征：将取到的值从小到大进行排序，一一取中点作为划分值，计算基尼指数。
对于划分后的两个子集，判断是否满足终止条件，不满足则继续计算基尼指数，同上；
- 进行剪枝，同上道例题。