《第4机器学习-决策树课件》由会员分享，可在线阅读，更多相关《第4机器学习-决策树课件（102页珍藏版）》请在金锄头文库上搜索。
1、上节课程内容回顾上节课程内容回顾n什么是机器学习？什么是机器学习？n机器学习的产生与发展机器学习的产生与发展n贝叶斯定理贝叶斯定理n贝叶斯分类算法贝叶斯分类算法上节课程内容回顾上节课程内容回顾明天太阳明天太阳会升起吗会升起吗? ?他在一个袋子放他在一个袋子放了黑白各一个颗弹子。了黑白各一个颗弹子。（太阳升起的概率？）（太阳升起的概率？）第一天第一天第二天第二天太阳升起了，太阳升起了，他加了一个白弹子在袋子里。他加了一个白弹子在袋子里。（太阳升起的概率？）（太阳升起的概率？）第三天第三天太阳升起了，太阳升起了，他又加了一个白弹子在袋子里。他又加了一个白弹子在袋子里。（太阳升起的概率？）（太阳升起
2、的概率？）。结论结论几乎可以肯定，几乎可以肯定，太阳总会升起。太阳总会升起。主要内容主要内容4.6.5 4.6.5 决策树的假设空间搜索决策树的假设空间搜索4.6.4 4.6.4 最佳分类属性判定最佳分类属性判定4.6.3 4.6.3 决策树的基本算法决策树的基本算法4.6.2 4.6.2 决策树学习的适用问题决策树学习的适用问题4.6.1 4.6.1 决策树的概念决策树的概念4.6.8 4.6.8 决策树算法的决策树算法的PROLOGPROLOG实现实现4.6.7 4.6.7 决策树的优缺点决策树的优缺点4.6.6 4.6.6 决策树的常见问题决策树的常见问题什么是决策树什么是决策树?n从管
3、理学的角度定义决策树是指使用系统分析决策树是指使用系统分析方法，把各种决策方案及方法，把各种决策方案及出现结果的可能性进行分出现结果的可能性进行分组排列，然后确定最佳方组排列，然后确定最佳方案的决策过程。案的决策过程。 4.6.1 什么是决策树？举例举例:渔民投资渔民投资决策点决策点新船新船旧船旧船好鱼情好鱼情(0.7)坏鱼情坏鱼情(0.3)好鱼情好鱼情(0.7)坏鱼情坏鱼情(0.3)$90000-$10000$80000$200004.6.1 什么是决策树？什么是决策树什么是决策树?n从机器学习的角度定义决策树是运用于分类决策树是运用于分类的一种树结构。的一种树结构。 4.6.1 什么是决策
4、树？决策树的表示方法决策树的表示方法n每个内部节点（每个内部节点（internalnode）代表对某）代表对某个属性的一次测试。个属性的一次测试。n一条边代表一个测试结果。一条边代表一个测试结果。n叶子（叶子（leaf）代表某个类（）代表某个类（class）或者类）或者类的分布（的分布（classdistribution）。）。n最上面的节点是根结点。最上面的节点是根结点。4.6.1 什么是决策树？举例举例n假设用一个决策树表示一个关心电子产品的假设用一个决策树表示一个关心电子产品的用户是否会购买用户是否会购买PC的知识，然后用它来预的知识，然后用它来预测某条记录（某个人）的购买意向。测某条记
5、录（某个人）的购买意向。4.6.1 什么是决策树？举例举例年龄年龄? ?学生学生? ?信用状况信用状况? ?否否是是是是是是否否40否否是是很好很好一般一般4.6.1 什么是决策树？举例举例n类别：类别：buys_computers=yesbuys_computers=yes和和buys_computers=nobuys_computers=no）。）。n样本向量为（样本向量为（age, student, credit_rating; age, student, credit_rating; buys_computersbuys_computers）n被决策数据的格式为（被决策数据的格式为（a
6、ge, student, age, student, credit_ratingcredit_rating）n输入新的被决策的记录，可以预测该记录隶属于输入新的被决策的记录，可以预测该记录隶属于哪个类。哪个类。4.6.1 什么是决策树？决策树分类过程决策树分类过程n决策树通过把实例从根结点排列（决策树通过把实例从根结点排列（sort）到）到某个叶子结点来分类实例，叶子结点即为某个叶子结点来分类实例，叶子结点即为实例所属的分类。实例所属的分类。n树上的每一个结点指定了对实例的某个属性树上的每一个结点指定了对实例的某个属性（attribute）的测试，并且该结点的每一）的测试，并且该结点的每一个后
7、继分支对应于该属性的一个可能值。个后继分支对应于该属性的一个可能值。4.6.1 什么是决策树？决策树分类过程（续）决策树分类过程（续）n分类实例的方法是从这棵树的根结点开始，分类实例的方法是从这棵树的根结点开始，测试这个结点指定的属性，然后按照给定测试这个结点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动。这实例的该属性值对应的树枝向下移动。这个过程再在以新结点为根的子树上重复。个过程再在以新结点为根的子树上重复。4.6.1 什么是决策树？问题：实例怎么表达？问题：实例怎么表达？决策树与规则表达的转换决策树与规则表达的转换通常决策树代表实例属性值约束的合取通常决策树代表实例属性值约束
8、的合取（conjunction）的析取式（）的析取式（disjunction）。）。从树根到树叶的每一条路径对应一组属性测从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。试的合取，树本身对应这些合取的析取。(Buys_computer=age=30 Student) (Buys_computer=age40 Credit_rating=excellent)(Buys_computer=age40 Credit_rating=excellent)4.6.1 什么是决策树？决策树学习的适用问题决策树学习的适用问题n实例由“属性-值”对（pair）表示-实例是用一系列固定的
9、属性和它们的值来实例是用一系列固定的属性和它们的值来描述的。描述的。-最简单的决策树学习中，每一个属性取少最简单的决策树学习中，每一个属性取少数的分离的值。数的分离的值。-扩展的算法允许处理扩展的算法允许处理值域为实数值域为实数的属性的属性（例如，数字表示的温度）。（例如，数字表示的温度）。4.6.2 决策树学习的适用问题决策树学习的适用问题决策树学习的适用问题n目标函数具有离散的输出值-上面举例的决策树给每个实例赋予一个布上面举例的决策树给每个实例赋予一个布尔型的分类（例如，尔型的分类（例如，yes或或no）。）。-决策树方法很容易扩展到学习有两个以上决策树方法很容易扩展到学习有两个以上输出
10、值的函数。输出值的函数。-一种更强有力的扩展算法允许学习具有实一种更强有力的扩展算法允许学习具有实数值输出的函数，尽管决策树在这种情况下数值输出的函数，尽管决策树在这种情况下的应用不太常见。的应用不太常见。4.6.2 决策树学习的适用问题决策树学习的适用问题决策树学习的适用问题n可能需要析取的描述-决策树很自然地代表了析取表达式。决策树很自然地代表了析取表达式。4.6.2 决策树学习的适用问题决策树学习的适用问题决策树学习的适用问题n训练数据可以包含缺少属性值的实例-决策树学习对错误有很好的决策树学习对错误有很好的鲁棒性鲁棒性，无论，无论是训练样例所属的分类错误还是描述这些样是训练样例所属的分
11、类错误还是描述这些样例的属性值错误。例的属性值错误。4.6.2 决策树学习的适用问题已经发现有很多实际的问题符合这些特征，所以决策树学习已经被应用到很多问题中。例如：根据拖欠支付的可能性分类贷款申请；根据起因分类设备故障。它们的核心任务就是它们的核心任务就是要把样例分类到各可能的离散值对应的类别中。要把样例分类到各可能的离散值对应的类别中。已有的决策树学习算法已有的决策树学习算法4.6.3 基本的决策树学习算法大多数已开发的大多数已开发的决策树学习算法都是决策树学习算法都是一种核心算法的变体。一种核心算法的变体。ID3(QUINLAN 1986)ID3(QUINLAN 1986)及其后继的及其
12、后继的C4.5C4.5ID34.6.3 基本的决策树学习算法基本的基本的ID3ID3算法通过自顶向下构造决策树算法通过自顶向下构造决策树来进行学习。来进行学习。ID3算法的构造过程算法的构造过程（问题：哪一个属性将在树的根结点被测试？问题：哪一个属性将在树的根结点被测试？）4.6.3 基本的决策树学习算法使用统计测试来确定每一个实例属性单独分类训练样例的能力，使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性被选作树的根结点的测试。分类能力最好的属性被选作树的根结点的测试。 为根结点属性的每个可能值产生一个分支，并把训练样例排列到为根结点属性的每个可能值产生一个分支，并
13、把训练样例排列到适当的分支（也就是，样例的该属性值对应的分支）之下。适当的分支（也就是，样例的该属性值对应的分支）之下。 重复整个过程，用每个分支结点关联的训练样例来选取在该点被重复整个过程，用每个分支结点关联的训练样例来选取在该点被测试的最佳属性。测试的最佳属性。 专用于学习布尔函数的专用于学习布尔函数的ID3算法算法4.6.3 基本的决策树学习算法ID3ID3是一种是一种自顶向下增长树自顶向下增长树的贪婪的贪婪(greedy)(greedy)算法，算法，在每个结点选取能最好地分类样例的属性。在每个结点选取能最好地分类样例的属性。继续这个过程直到这棵树继续这个过程直到这棵树能完美分类训练样例
14、，能完美分类训练样例，或者所有的属性都使用过了。或者所有的属性都使用过了。 见复印资料。专用于学习布尔函数的专用于学习布尔函数的ID3算法算法4.6.3 基本的决策树学习算法什么是衡量属性价值的定量标准什么是衡量属性价值的定量标准？信息熵信息熵4.6.4 哪个属性是最佳的分类属性？n信息论中广泛使用的一个度量标准信息论中广泛使用的一个度量标准（ClaudeElwoodShannon），称为熵），称为熵（entropy），它刻画了任意样例集的纯度），它刻画了任意样例集的纯度（purity）。）。信息熵信息熵4.6.4 哪个属性是最佳的分类属性？n给定包含关于某个目标概念的正反样例的样给定包含关于
15、某个目标概念的正反样例的样例集例集S，那么，那么S相对这个布尔型分类的熵为：相对这个布尔型分类的熵为： Entropy(S) -p log2p -plog2p其中，其中，p 是在是在S中正例的比例，中正例的比例，p是在是在S中负例的比例。在有关熵的所有计算中我们中负例的比例。在有关熵的所有计算中我们定义定义0log0为为0。举例举例4.6.4 哪个属性是最佳的分类属性？n假设假设S是一个关于某布尔概念的有是一个关于某布尔概念的有14个样例个样例的集合，它包括的集合，它包括9个正例和个正例和5个反例（用记号个反例（用记号9+，5-来表示）。那么来表示）。那么S相对于这个布尔分相对于这个布尔分类的
16、熵（类的熵（Entropy）为：）为：注意注意4.6.4 哪个属性是最佳的分类属性？n如果如果S的所有成员属于同一类，那么的所有成员属于同一类，那么S的熵的熵为为0。例如，如果所有的成员是正的。例如，如果所有的成员是正的（p =1），那么），那么p就是就是0，那么，那么 Entropy(S)=0。注意注意4.6.4 哪个属性是最佳的分类属性？n当集合中正反样例的数量相等时熵为当集合中正反样例的数量相等时熵为1。如。如果集合中正反例的数量不等时，熵介于果集合中正反例的数量不等时，熵介于0和和1之间。之间。1.00,00.50.51.0某布尔分类的熵函数P随着从0到1变化的曲线信息论中熵的解释信息论中熵的解释4.6.4 哪个属性是最佳的分类属性？n熵确定了集合熵确定了集合S中任意成员（即以均匀的概中任意成员（即以均匀的概率随机抽出的一个成员）的分类所需要的最率随机抽出的一个成员）的分类所需要的最少二进制位数。少二进制位数。信息论中熵的解释信息论中熵的解释4.6.4 哪个属性是最佳的分类属性？n如果如果P 是是1，接收者知道抽出的样例必为，接收者知道抽出的样例必为正，所以不必发任何消息，此时
