文档介绍：
机器学****决策树学****译者:曾华军等作者:Mitchell 讲者:陶晓鹏
1
机器学****br/>第3章决策树学****br/>1
机器学****决策树学****译者:曾华军等作者:Mitchell 讲者:陶晓鹏
2
概论
决策树学****是应用最广的归纳推理算法之一
是一种逼近离散值函数的方法
很好的健壮性
能够学****析取表达式
ID3, Assistant,
搜索一个完整表示的假设空间
归纳偏置是优先选择较小的树
决策树表示了多个if-then规则
2
机器学****决策树学****译者:曾华军等作者:Mitchell 讲者:陶晓鹏
3
提纲
决策树定义
适用问题特征
基本ID3算法
决策树学****的归纳偏置
训练数据的过度拟合
更深入的话题
3
机器学****决策树学****译者:曾华军等作者:Mitchell 讲者:陶晓鹏
4
决策树表示法
决策树
通过把实例从根节点排列到某个叶子节点来分类实例。
叶子节点即为实例所属的分类
树上每个节点说明了对实例的某个属性的测试
节点的每个后继分支对应于该属性的一个可能值
图3-1
决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取,树本身对应这些合取的析取。
4
机器学****决策树学****译者:曾华军等作者:Mitchell 讲者:陶晓鹏
5
决策树学****的适用问题
适用问题的特征
实例由“属性-值”对表示
目标函数具有离散的输出值
可能需要析取的描述
训练数据可以包含错误
训练数据可以包含缺少属性值的实例
问题举例
根据疾病分类患者
根据起因分类设备故障
根据拖欠支付的可能性分类贷款申请
分类问题
核心任务是把样例分类到各可能的离散值对应的类别
5
机器学****决策树学****译者:曾华军等作者:Mitchell 讲者:陶晓鹏
6
基本的决策树学****算法
大多数决策树学****算法是一种核心算法的变体
采用自顶向下的贪婪搜索遍历可能的决策树空间
ID3是这种算法的代表
6
机器学****决策树学****译者:曾华军等作者:Mitchell 讲者:陶晓鹏
7
基本的决策树学****算法(2)
ID3的思想
自顶向下构造决策树
从“哪一个属性将在树的根节点被测试”开始
使用统计测试来确定每一个实例属性单独分类训练样例的能力
ID3的过程
分类能力最好的属性被选作树的根节点
根节点的每个可能值产生一个分支
训练样例排列到适当的分支
重复上面的过程
7
机器学****决策树学****译者:曾华军等作者:Mitchell 讲者:陶晓鹏
8
表3-1 用于学****布尔函数的ID3算法概要
ID3(Examples, Target_attribute, Attributes)
创建树的root节点
如果Examples都为正,返回label=+的单节点树root
如果Examples都为反,返回label=-的单节点树root
如果Attributes为空,那么返回单节点root,label=Examples中最普遍的Target_attribute值
否则开始
AAttributes中分类examples能力最好的属性
root的决策属性A
对于A的每个可能值vi
在root下加一个新的分支对应测试A=vi
令Examplesvi为Examples中满足A属性值为vi的子集
如果Examplesvi为空
在这个新分支下加一个叶子节点,节点的label=Examples中最普遍的Target_attribute值
否则在新分支下加一个子树ID3( Examplesvi,Target_attribute,Attributes-{A})
结束
返回root
8
机器学****决策树学****译者:曾华军等作者:Mitchell 讲者:陶晓鹏
9
最佳分类属性
信息增益
用来衡量给定的属性区分训练样例的能力
ID3算法在增长树的每一步使用信息增益从候选属性中选择属性
用熵度量样例的均一性
熵刻画了任意样例集的纯度
给定包含关于某个目标概念的正反样例的样例集S,那么S相对这个布尔型分类的熵为
Entropy(S)=-p+log2p+ - p-log2p-
信息论中对熵的一种解释,熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数
更一般地,如果目标属性具有c个不同的值,那么S相对于c个状态的分类的熵定义为
Entropy(S)=
9
机器学****决策树学****译者:曾华军等作者:Mitchell 讲者:陶晓鹏
10
最佳分类属性(2)
用信息