决策树 ID3算法.ppt

决策树_ID3算法决策树
报告人:彭蔚
指导老师:李玉鑑
决策树
决策树基本概念
关于分类问题
分类(Classification)任务就是通过学习获得一个目标函数
(Target Function)f, 将每个属性集x映射到一个预先定义好的类
标号y。
分类方法的实例包括:决策树分类法、基于规则的分类法、
神经网络、支持向量级、朴素贝叶斯分类方法等。
决策树
决策树基本概念
解决分类问题的一般方法
分类问题一般包括两个步骤:
1、模型构建(归纳)
通过对训练集合的归纳,建立分类模型。
2、预测应用(推论)
根据建立的分类模型,对测试集合进行测试。
决策树
决策树基本概念
决策树
决策树是一种典型的分类方法,首先对数据进行处理,利用
归纳算法生成可读的规则和决策树,然后使用决策对新数据进行
分析。本质上决策树是通过一系列规则对数据进行分类的过程。
决策树
决策树算法
与决策树相关的重要算法
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
决策树
决策树算法
决策树的表示
决策树的基本组成部分:决策结点、分支和叶子。
年龄?
学生?
信誉?
买
青
中
老
否
是
优
良
不买
买
买
不买
决策树中最上面的结点称为根结点。
是整个决策树的开始。每个分支是一
个新的决策结点,或者是树的叶子。
每个决策结点代表一个问题或者决策.
通常对应待分类对象的属性。
每个叶结点代表一种可能的分类结果
在沿着决策树从上到下的遍历过程中,在每个结点都有一个
测试。对每个结点上问题的不同测试输出导致不同的分枝,最后
会达到一个叶子结点。这一过程就是利用决策树进行分类的过程,
利用若干个变量来判断属性的类别
决策树
决策树的优点
1、推理过程容易理解,决策推理过程可以表示成If Then形式;
2、推理过程完全依赖于属性变量的取值特点;
3、可自动忽略目标变量没有贡献的属性变量,也为判断属性
变量的重要性,减少变量的数目提供参考。
决策树
决策树算法
CLS(Concept Learning System)算法
CLS算法是早期的决策树学习算法。它是许多决策树学习算法
的基础。
CLS基本思想
从一棵空决策树开始,选择某一属性(分类属性)作为测试
属性。该测试属性对应决策树中的决策结点。根据该属性的值的
不同,可将训练样本分成相应的子集,如果该子集为空,或该子
集中的样本属于同一个类,则该子集为叶结点,否则该子集对应
于决策树的内部结点,即测试结点,需要选择一个新的分类属性
对该子集进行划分,直到所有的子集都为空或者属于同一类。
决策树
决策树算法
CLS算法-决策树的构建
眼睛颜色
[1,6]
[2,4,8]
[3,5,7]
黑色
兰色
灰色
不属于同一类,非叶结点
决策树
眼睛颜色
头发颜色
头发颜色
头发颜色
黑色
兰色
灰色
决策树算法
CLS算法
黄种人[1]
混血[6]
白种人[2]
白种人[4]
混血[8]
白种人[3]
白种人[5]
混血[7]
黑色
金色
金色
红色
黑色
金色
红色
黑色