AI_决策树学习_Chap6.ppt

人工智能 第6章学习智能体 决策树学习 巢文涵chaowenhan G1001 G931北航计算机学院智能信息研究所2019年12月27日星期五 2 大纲 简介决策树学习算法应用实例 3 决策树 DecisionTree 决策树学习是应用最广的归纳推理算法之一它是一种逼近离散函数的方法学习到的函数以决策树的形式表示主要用于分类对噪声数据有很好的鲁棒性能够学习析取表达 4 分类任务基本框架 5 分类应用实例 垃圾邮件过滤信贷分析新闻分类人脸识别 手写体识别等 6 决策树的结构 图结构内部节点 非树叶节点 包括根节点 在一个属性上的测试分枝一个测试输出树叶节点类标识 7 决策树示例 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 测试属性 训练数据 模型 决策树 Refund YES Refund NO MarSt Single Divorced TaxInc 80K Refund NO Married NO 8 另一棵决策树 MarSt Refund TaxInc YES NO NO Yes No Married Single Divorced 80K 80K 相同的数据可产生多棵决策树 9 决策树分类任务框架 决策树 10 决策树应用 测试数据 从根节点开始 11 决策树应用 测试数据 12 决策树应用 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 测试数据 13 决策树应用 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 测试数据 14 决策树应用 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 测试数据 15 决策树应用 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 测试数据 指定欺诈为 No 16 决策树分类任务框架 DecisionTree 17 大纲 简介决策树学习算法应用实例 18 决策树算法 Hunt sAlgorithmCARTID3 C4 5SLIQ SPRINT 19 基本的ID3算法 20 基本算法 Don tCheat 21 决策树归纳 贪婪策略根据特定的性能度量选择最好的划分属性要素哪个属性是最佳的分类属性 如何确定最佳划分点如何确定停止条件 22 度量标准 熵 熵 Entropy 信息论中广泛使用的一个度量标准刻画任意样例集的纯度 purity 一般计算公式为 对于二元分类 给定包含关于某个目标概念的正反样例的样例集S 那么S相对这个布尔型分类的熵为 Entropy S p log2p p log2p 其中p 是在S中正例的比例 p 是在S中负例的比例 在有关熵的所有计算中我们定义0log0为0 23 例子 Entropy 0 6 log 0 6 6 6 log 6 6 0 Entropy 1 1 6 log 1 6 5 6 log 5 6 0 650 Entropy 1 3 6 log 3 6 3 6 log 3 6 1 24 度量标准 熵 25 度量标准 熵 信息论中熵的一种解释熵确定了要编码集合S中任意成员 即以均匀的概率随机抽出的一个成员 的分类所需要的最少二进制位数 1接收者知道抽出的样例必为正 所以不必发任何消息 熵为0 0 5必须用一个二进制位来说明抽出的样例是正还是负 熵为1 0 8那么对所需的消息编码方法是赋给正例集合较短的编码 可能性较小的反例集合较长的编码 平均每条消息的编码少于1个二进制位 26 性能度量 信息增益 属性的信息增益使用这个属性分割样例而导致的期望熵降低的数量Values A 是属性A所有可能值的集合Sv是S中属性A的值为v的子集 即Sv s S A s v 当对S的一个任意成员的目标值编码时 Gain S A 的值是在知道属性A的值后可以节省的二进制位数 27 例子 假设S是有关天气的训练样例集 9 5 其中 wind weak的样例是 6 2 wind strong的样例 3 3 问题 计算属性wind的信息增益S的熵 E S 9 14 log 9 14 5 14 log 9 14 0 940 28 选择最好的分类属性 29 大纲 简介决策树学习算法应用实例 30 应用实例 问题及数据集根据其他属性 判断周六是否玩网球playTennis Y N 31 Step1 确定根节点 分别计算4个属性的信息增益Outlook 0 246 Sunny 2 3 Overcast 4 0 Rain 3 2 Wind 0 048 weak的样例是 6 2 strong的样例 3 3 Humidity 0 151Temperature 0 029因此 根节点为Outlook 32 Step2 分枝 选择哪个属性进行划分 33 Step3 循环 选择哪个属性进行划分 34 小结 实例是由 属性 值 对 pair 表示的目标函数具有离散的输出值可能需要析取的描述 disjunctivedescription 训练数据可以包含错误训练数据可以包含缺少属性值的实例 35 作业 6 1画出表示下面布尔函数的决策树 a A B b A B C c AXORB d A B C D 36 作业 6 2考虑下面的训练样例集合手动给出决策树的构造过程 37 作业 6 3ID3仅寻找一个一致的假设 而候选消除算法寻找所有一致的假设 考虑这两种学习算法间的对应关系 a 假定给定Enjo