决策树 ID3算法.ppt

决策树_ID3算法
主要内容
决策树基本概念
决策树算法
决策树研究问题
主要参考文献
第6章 决策树
决策树基本概念
关于分类问题
分类（Classification）任务就是通过学习获得一个目标函数
（的类
准确率=正确的预测数/预测总数=（f11+f00）/(f11+f01+f10+f00)
差错率=错误的预测数/预测总数=（f10+f01）/(f11+f01+f10+f00)
归纳学习假设
机器学习的任务是在整个实例集合X上确定与目标概念c相同
的假设 。一般H表示所有可能假设。H中每个假设h表
示X上定义的布尔函数。由于对c仅有的信息只是它在训练样例上
的值，因此归纳学习最多只能保证输出的假设能与训练样例相拟
合。若没有更多的信息，只能假定对于未见实例最好的假设就是
训练数据最佳拟合的假设。
定义 归纳学习假设：任一假设如果在足够大的训练样例中很
好地逼近目标函数，则它也能在未见实例中很好地逼近目标函数。
（Function Approximation）。
第6章 决策树
决策树基本概念
从机器学习看分类及归纳推理等问题（4）
主要内容
决策树基本概念
决策树算法
决策树研究问题
主要参考文献
第6章 决策树
决策树算法
与决策树相关的重要算法
1、Hunt,Marin和Stone 于1966年研制的CLS学习系统，用于学习单个概 念。
2、1979年, . Quinlan 给出ID3算法，并在1983年和1986年对ID3 进行了总结和简化，使其成为决策树学习算法的典型。
3、Schlimmer 和Fisher 于1986年对ID3进行改造，在每个可能的决策树节点创建缓冲区，使决策树可以递增式生成，得到ID4算法。
4、1988年，Utgoff 在ID4基础上提出了ID5学习算法，进一步提高了效率。
1993年，Quinlan 进一步发展了ID3算法，。
5、另一类决策树算法为CART，，CART的决策树由二元逻辑问题生成，每个树节点只有两个分枝，分别包括学习实例的正例与反例。
CLS, ID3，，CART
第6章 决策树
决策树算法
计数
年龄
收入
学生
信誉
归类：买计算机？
64
青
高
否
良
不买
64
青
高
否
优
不买
128
中
高
否
良
买
60
老
中
否
良
买
64
老
低
是
良
买
64
老
低
是
优
不买
64
中
低
是
优
买
128
青
中
否
良
不买
64
青
低
是
良
买
132
老
中
是
良
买
64
青
中
是
优
买
32
中
中
否
优
买
32
中
高
是
良
买
63
老
中
否
优
不买
1
老
中
否
优
买
假定公司收集了左表数据，那么对于任意给定的客人（测试样例），你能帮助公司将这位客人归类吗？
即：你能预测这位客人是属于“买”计算机的那一类，还是属于“不买”计算机的那一类？
又：你需要多少有关这位客人的信息才能回答这个问题？
决策树的用途
第6章 决策树
计数
年龄
收入
学生
信誉
归类：买计算机？
64
青
高
否
良
不买
64
青
高
否
优
不买
128
中
高
否
良
买
60
老
中
否
良
买
64
老
低
是
良
买
64
老
低
是
优
不买
64
中
低
是
优
买
128
青
中
否
良
不买
64
青
低
是
良
买
132
老
中
是
良
买
64
青
中
是
优
买
32
中
中
否
优
买
32
中
高
是
良
买
63
老
中
否
优
不买
1
老
中
否
优
买
谁在买计算机？
年龄？
学生？
信誉？
买
青
中
老
否
是
优
良
不买
买
买
不买
决策树的用途
决策树算法
第6章 决策树
计数
年龄
收入
学生
信誉
归类：买计算机？
64
青
高
否
良
不买
64
青
高
否
优
不买
128
中
高
否
良
买
60
老
中
否
良
买
64
老
低
是
良