文档介绍：该【第3章 决策树学习 】是由【qqqqqq】上传分享，文档一共【57】页，该文档可以免费在线阅读，需要了解更多关于【第3章 决策树学习 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第3章 决策树学习(xuéxí)
(Decision-Tree Algorithm)
第一页，共五十七页。
排名
主题
算法
得票数
发表时间
作者
陈述人
1
分类
61
1993
Quinlan,
Hiroshi Motoda
2
聚类
k-Means
60
1967
MacQueen,
Joydeep Ghosh
3
统计学习
SVM
58
1995
Vapnik,
QiangYang
4
关联分析
Apriori
52
1994
Rakesh Agrawal
Christos Faloutsos
5
统计学习
EM
48
2000
McLachlan, G
Joydeep Ghosh
6
链接挖掘
PageRank
46
1998
Brin, S.
Christos Faloutsos
7
集装与推进
AdaBoost
45
1997
Freund, Y.
Zhi-Hua Zhou
8
分类
kNN
45
1996
Hastie, T
Vipin Kumar
9
分类
Naïve Bayes
45
2001
Hand,
Qiang Yang
10
分类
CART
34
1984
Dan Steinberg
共有145人参加了ICDM 2006 Panel (会议的专题讨论),并对18种候选算法进行(jìnxíng)投票，选出了机器学习10大算法
ICDM 2006会议(huìyì)的算法投票结果
第二页，共五十七页。
概 论
决策树学习是应用最广的归纳推理算法之一
是一种逼近离散值函数的方法
很好的健壮性
能够学习析取表达式
搜索一个完整(wánzhěng)表示的假设空间
归纳偏置是优先选择较小的树
决策树表示了多个if-then规则
第三页，共五十七页。
提 纲
决策树定义
适用问题特征
根本ID3算法(suàn fǎ)
决策树学习的归纳偏置
训练数据的过度拟合
…
第四页，共五十七页。
决策树根本概念
关于分类(fēn lèi)问题
分类〔Classification〕任务就是通过学习获得一个(yī ɡè)目标函数〔Target Function〕f, 将每个属性集x映射到一个预先定义好的类标号y。
分类任务(rèn wu)的输入数据是记录的集合，每条记录也称为实例或者样例。用元组(X,y)表示，其中，X 是属性集合，y是一个特殊的属性，指出样例的类标号〔也称为分类属性或者目标属性〕
第五页，共五十七页。
决策树根本概念
关于分类(fēn lèi)问题
名称
体温
表皮覆盖
胎生
水生动物
飞行动物
有腿
冬眠
类标号
人类
恒温
毛发
是
否
否
是
否
哺乳动物
海龟
冷血
鳞片
否
半
否
是
否
爬行类
鸽子
恒温
羽毛
否
否
是
是
否
鸟类
鲸
恒温
毛发
是
是
否
否
否
哺乳类
X
y
分类(fēn lèi)与回归
分类目标(mùbiāo)属性y是离散的，回归目标属性y是连续的
第六页，共五十七页。
决策树根本概念
解决分类问题的一般(yībān)方法
通过以上对分类问题一般方法的描述，可以看出(kàn chū)分类问题
一般包括两个步骤：
1、模型构建〔归纳〕
通过对训练集合的归纳，建立分类模型。
2、预测应用〔推论〕
根据建立的分类模型，对测试集合进行测试。
第七页，共五十七页。
决策树根本概念
解决分类问题的一般(yībān)方法
TID
A1
A2
A3
类
1
Y
100
L
N
2
N
125
S
N
3
Y
400
L
Y
4
N
415
M
N
学习(xuéxí)算法
学习(xuéxí)模型
模型
应用模型
TID
A1
A2
A3
类
1
Y
100
L
？
2
N
125
S
？
3
Y
400
L
？
4
N
415
M
？
训练集〔类标号〕
检验集〔类标号未知〕
归纳
推论
第八页，共五十七页。
决策树表示法
内部(nèibù)节点(包括根节点)指定了对实例的某个属性的测试
节点的每个后继分支对应于该属性的一个可能值
叶子节点即为实例所属的分类
决策树代表实例属性值约束的合取的析取式
图3-1 概念Play Tennis的决策树
Outlook
Humidity
Wind
No
Yes
No
Yes
Yes
Sunny
Rainy
Overcast
High
Normal
Strong
Weak
第九页，共五十七页。
决策树学习(xuéxí)的适用问题
适用问题(wèntí)的特征
实例由“属性-值〞对表示
目标函数具有离散的输出值
可能需要析取的描述
训练数据可以包含错误
训练数据可以包含缺少属性值的实例
问题举例
医学中的应用〔如根据疾病分类患者、疾病分析与预测〕
根据起因分类设备故障〔故障诊断〕
根据拖欠支付的可能性分类贷款申请
分类问题
核心任务是把样例分类到各可能的离散值对应的类别
第十页，共五十七页。