单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人工智能第6章,学习智能体-决策树学习,巢文涵,G1001/G931,北航计算机学院智能信息研究所,11/18/2024,1,大纲,简介,决策树学习算法,应用实例,2,决策树(Decision Tree),决策树学习是应用最广的归纳推理算法之一,它是一种逼近,离散,函数的方法,学习到的函数以决策树的形式表示,主要用于分类,对噪声数据有很好的鲁棒性,能够学习析取表达,3,分类任务基本框架,4,分类应用实例,垃圾邮件过滤,信贷分析,新闻分类,人脸识别、手写体识别等,5,决策树的结构,图结构,内部节点（非树叶节点，包括根节点）,在一个属性上的测试,分枝,一个测试输出,树叶节点,类标识,6,决策树示例,分类型,分类型,连续型,类别,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试属性,训练数据,模型：决策树,(Refund=YES),(Refund=NO,MarSt=Single,Divorced,TaxInc 80K,),(Refund=NO,Married=NO),7,另一棵决策树,MarSt,Refund,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,相同的数据可产生多棵决策树,分类型,分类型,连续型,类别,8,决策树分类任务框架,决策树,9,决策树应用,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,从根节点开始,10,决策树应用,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,11,决策树应用,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,12,决策树应用,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,13,决策树应用,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,14,决策树应用,Refund,MarSt,TaxInc,YES,NO,NO,NO,Yes,No,Married,Single,Divorced,80K,测试数据,指定欺诈为：“No”,15,决策树分类任务框架,Decision Tree,16,大纲,简介,决策树学习算法,应用实例,17,决策树算法,Hunts Algorithm,CART,ID3,C4.5,SLIQ,SPRINT,18,基本的ID3算法,19,基本算法,Dont,Cheat,Refund,Dont,Cheat,Dont,Cheat,Yes,No,Refund,Dont,Cheat,Yes,No,Marital,Status,Dont,Cheat,Cheat,Single,Divorced,Married,Taxable,Income,Dont,Cheat,=80K,Refund,Dont,Cheat,Yes,No,Marital,Status,Dont,Cheat,Cheat,Single,Divorced,Married,20,决策树归纳,贪婪策略,根据特定的性能度量选择最好的划分属性,要素,哪个属性是最佳的分类属性？,如何确定最佳划分点,如何确定停止条件,21,度量标准熵,熵(Entropy),信息论中广泛使用的一个度量标准,刻画任意样例集的纯度（purity）,一般计算公式为：,对于二元分类：给定包含关于某个目标概念的正反样例的样例集,S,，那么,S,相对这个布尔型分类的熵为：,Entropy,(,S,),-,p,log,2,p,-,p,log2,p,其中,p,是在,S,中正例的比例，,p,是在,S,中负例的比例。在有关熵的所有计算中我们定义0log0为0。,22,例子,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,23,度量标准熵,24,度量标准熵,信息论中熵的一种解释,熵确定了要编码集合,S,中任意成员（即以均匀的概率随机抽出的一个成员）的分类所需要的最少二进制位数,=1,接收者知道抽出的样例必为正，所以不必发任何消息，熵为0,=0.5,必须用一个二进制位来说明抽出的样例是正还是负，熵为1,=0.8,那么对所需的消息编码方法是赋给正例集合较短的编码，可能性较小的反例集合较长的编码，平均每条消息的编码少于1个二进制位,25,性能度量信息增益,属性的信息增益,使用这个属性分割样例而导致的期望熵降低的数量,Values,(,A,)是属性,A,所有可能值的集合,S,v,是,S,中属性,A,的值为,v,的子集，即S,v,=,s,S|A(s)=v,当对,S,的一个任意成员的目标值编码时，,Gain,(,S,A,)的值是在知道属性,A,的值后可以节省的二进制位数,26,例子,假设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,27,选择最好的分类属性,28,大纲,简介,决策树学习算法,应用实例,29,应用实例,问题及数据集,根据其他属性，判断周六是否玩网球playTennis=Y/N?,30,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.151,Temperature :0.029,因此：根节点为Outlook,31,Step 2:分枝,选择哪个属性进行划分？,32,Step 3:循环,选择哪个属性进行划分？,33,小结,实例是由“属性-值”对（pair）表示的,目标函数具有离散的输出值,可能需要析取的描述（disjunctive description）,训练数据可以包含错误,训练数据可以包含缺少属性值的实例,34,作业,6-1画出表示下面布尔函数的决策树,（a）,A,B,（b）,A,B,C,（c）,A,XOR,B,（d）,A,B,C,D,35,作业,6-2考虑下面的训练样例集合,手动给出决策树的构造过程,36,作业,6-3 ID3仅寻找一个一致的假设，而候选消除算法寻找所有一致的假设。考虑这两种学习算法间的对应关系,（a）假定给定,EnjoySport,的四个训练样例，画出ID3学习的决策树,（b）学习到的决策树和从同样的样例使用变型空间算法得到的变型空间间有什么关系？树等价于变型空间的一个成员吗？,37,作业,6-4 实现ID3算法，并以PlayTennis实例中的训练集进行训练，给出最终的决策树,38,