机器学习笔记-决策树
决策树学习
学堂在线机器学习笔记
什么是决策树
决策树基本上就是把我们以前的经验总结出来。我给你准备了一个享受运动的训练集。如果我们要出门进行体育活动,一般会根据“天气”、“温度”、“湿度”、“风”这几个条件来判断,最后得到结果:去运动?还是不去?
适用于决策树学习的经典目标问题
- 带有非数值特征的分类问题
- 离散特征
- 没有相似度概念 (比如天气,阴天跟雨天跟接近还是阴天跟有雾更接近,没有明确的可度量方式)
- 特征无序 (比如男性,女性 ,不能说男性群体>女性群体)
样本表示
- 属性的列表而非数值向量
例如享受运动的例子:
6值属性:天气、温度、湿度、风、水温、预测天气
某一天的天气实例:{晴、暖、一般、强、暖、不变}
决策树-概念
经典决策树算法
经典决策树算法-ID3 流程
- 自顶向下,贪心搜索
- 递归算法 • 核心循环:
- A :下一步 最佳 决策属性
- 将 A 作为当前节点决策属性
- 对属性A (vi )的每个值,创建与其对应的新的子节点
- 根据属性值将训练样本分配到各个节点
- 如果 训练样本被完美分类,则退出循环,否则继续 下探分裂新的叶节点
这里要解决2个问题:哪个属性是最佳属性?何时返回(停止分裂)?
第一个问题:
属性选择和节点混杂度(Impurity)
- 基本原则: 简洁 —— 我们偏向于使用简洁的具有较少节点的树
- 在每个节点 N上,我们选择一个属性 T,使得到达当 前派生节点的数据尽可能 “纯”
- 纯度(purity) – 混杂度(impurity)
用熵来衡量混杂度
- 定义: 0log0=0
- 在信息理论中,熵度量了信息 的纯度/混杂度,或者信息的 不确定性
- 正态分布 – 具有最大的熵值
简单的计算一下,A1的熵
其他的混杂度度量
- Gini 混杂度
- 错分类混杂度
度量混杂度的变化--信息增益(IG)
例如由于对A的排序整理带来的熵的期望减少量
A1的信息增益
A2的信息增益 。 所以选择信息增益大的A1节点
解决完怎么选择最佳属性后,再来看看第二个问题 何时返回(停止分裂节点)?
- 如果训练样本被完美分类
- 情形 1: 如果当前子集中所有数据 有完全相同的输出类别,那么终止
- 情形 2: 如果当前子集中所有数据 有完全相同的输入特征,那么终止(意味着数据有噪声或者有重要的特征被遗漏了)
可能情形3 是信息增益为0 但使用这个方法一般是不可行的
比如 y=a xor b (xor表示异或)
如果按IG=0终止,那么在第一步都无法选取属性。有多个相同的IG取值时,正确的做法是随机选一个属性
ID3算法搜索的假设空间
- 假设空间是完备的
目标函数一定在假设空间里
- 输出单个假设
不超过20个问题(根据经验)
- 没有回溯
局部最优
- 在每一步中使用子集的所有数据
数据驱动的搜索选择
对噪声数据有鲁棒性
ID3中的归纳偏置 (Inductive Bias )
- 假设空间H 是作用在样本集合 X 上的
没有对假设空间作限制
- 偏向于在靠近根节点处的属性具有更大信息增益的树
尝试找到最短的树
该算法的偏置在于对某些假设具有一些偏好(preference) (搜索偏置), 而不是 对假设空间 H 做限制(restrict)(描述偏置).
过拟合问题
模型在训练集上的表现很好,但在测试集上的表现不好
决策树过拟合的一个极端例子:
- 每个叶节点都对应单个训练样本 —— 每个训练样本都被完美地分类
- 整个树相当于仅仅是一个数据查表算法的简单实现
决策树的过拟合以及措施
- 对决策树来说有两种方法避免过拟合
I. 当数据的分裂在统计意义上并不显著时,就停止增长:预剪枝
II. 构建一棵完全树,然后做后剪枝
类型I .预剪枝:何时停止分裂(1):基于样本数
通常 一个节点不再继续分裂,当:
- 到达一个节点的训练样本数小于训练集合的一个特定比例 (例如 5%)
- 无论混杂度或错误率是多少
- 原因:基于过少数据样本的决定会带来较大误差和泛化错误
类型I .预剪枝:何时停止分裂(2):基于信息增益阈值
设定一个较小的阈值,如果满足下述条件则停止分裂
优点: 用到了所有训练数据 , 叶节点可能在树中的任何一层
缺点: 很难设定一个好的阈值
类型 II. 后剪枝 (1): 错误降低剪枝
- 把数据集分为训练集和验证集
验证集:
已知标签
测试效果
在该集合上不做模型更新!
- 剪枝直到再剪就会对损害性能:
在验证集上测试剪去每个 可能节点(和以其为根的子树)的影响
贪心地去掉某个可以提升验证集准确率的节点
- 剪枝后新的叶节点的标签赋值策略
赋值成最常见的类别
给这个节点多类别的标签
每个类别有一个支持度 (根据训练集中每种标签的数目)
测试时: 依据概率选择某个类别或选择多个标签
如果是一个回归树 (数值标签),可以做平均或加权平均
类型 II. 后剪枝 (2):规则后剪枝
- 把树转换成等价的由规则构成的集合 if (outlook=sunny)^ (humidity=high) then playTennis = no
- 对每条规则进行剪枝,去除哪些能够提升该规则准确率的规则前件 (outlook=sunny), (humidity=high)
- 将规则排序成一个序列 (根据规则的准确率从高往低排序)
- 用该序列中的最终规则对样本进行分类(依次查看是否满足规则序列)
- 这是一种被广泛使用的方法,例如C4.5
现实场景中的决策树学习
1.将连续属性离散化
可以采用等宽法(分成具有相同宽度的区间)等频法(相同数量的记录放进每个区间)
2. 具有过多取值的属性
- 偏差: 如果属性有很多值,根据信息增益IG,会优先被选择
- 一个可能的解决方法: 用 GainRatio (增益比)来替代