决策树学习培训讲义

《人工智能》第6章

学习智能体-决策树学习巢文涵

chaowenhan@G1001/G931北航计算机学院智能信息研究所1/25/20231大纲简介决策树学习算法应用实例2决策树(DecisionTree)决策树学习是应用最广的归纳推理算法之一它是一种逼近离散函数的方法学习到的函数以决策树的形式表示主要用于分类对噪声数据有很好的鲁棒性能够学习析取表达3分类任务基本框架4分类应用实例垃圾邮件过滤信贷分析新闻分类

人脸识别、手写体识别等5决策树的结构图结构内部节点（非树叶节点，包括根节点）在一个属性上的测试分枝一个测试输出树叶节点类标识6决策树示例分类型分类型连续型类别RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K测试属性训练数据模型：决策树(Refund=YES)٧

(Refund=NO

٨

MarSt=Single,Divorced

٨

TaxInc<80K)٧

(Refund=NO

٨

Married=NO)7另一棵决策树MarStRefundTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K相同的数据可产生多棵决策树分类型分类型连续型类别8决策树分类任务框架决策树9决策树应用用RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K测试数据从根节点开开始10决策树应用用RefundMarStTaxIncYESNONONOYesNoMarried

Single,Divorced<80K>80K测试数据11决策树应用用RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80K测试数据12决策树应用RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80K测试数据13决策树应用RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80K测试数据14决策树应用RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced<80K>80K测试数据指定欺诈为：：“No””15决策树分类任任务框架DecisionTree16大纲简介决策树学习算算法应用实例17决策树算法Hunt’sAlgorithmCARTID3,C4.5SLIQ,SPRINT18基本的ID3算法19基本算法Don’tCheatRefundDon’tCheatDon’tCheatYesNoRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTaxableIncomeDon’tCheat<80K>=80KRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarried20决策树归纳贪婪策略根据特定的性性能度量选择择最好的划分分属性要素哪个属性是最最佳的分类属属性？如何确定最佳佳划分点如何确定停止止条件21度量标准———熵熵(Entropy)信息论中广泛泛使用的一个个度量标准刻画任意样例例集的纯度（（purity）一般计算公式式为：对于二元分类类：给定包含含关于某个目目标概念的正正反样例的样样例集S，那么S相对这个布尔尔型分类的熵熵为：Entropy(S)-plog2p-pΘlog2pΘ其中p是在S中正例的比例例，pΘ是在S中负例的比例例。在有关熵熵的所有计算算中我们定义义0log0为0。22例子Entropy=-(0/6)log(0/6)-(6/6)log(6/6)=0Entropy=1-(1/6)log(1/6)-(5/6)log(5/6)=0.650Entropy=1-(3/6)log(3/6)-(3/6)log(3/6)=123度量标准———熵24度量标准———熵信息论中熵的的一种解释熵确定了要要编码集合合S中任意成员员（即以均均匀的概率率随机抽出出的一个成成员）的分分类所需要要的最少二二进制位数数=1接收者知道道抽出的样样例必为正正，所以不不必发任何何消息，熵熵为0=0.5必须用一个个二进制位位来说明抽抽出的样例例是正还是是负，熵为为1=0.8那么对所需需的消息编编码方法是是赋给正例例集合较短短的编码，，可能性较较小的反例例集合较长长的编码，，平均每条条消息的编编码少于1个二进制制位25性能度量———信息增增益属性的信息息增益使用这个属属性分割样样例而导致致的期望熵熵降低的数数量Values(A)是属性A所有可能值值的集合Sv是S中属性A的值为v的子集，，即Sv={sS|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.94027选择最好的的分类属性性28大纲简介决策树学习习算法应用实例29应用实例问题及数据据集根据其他属属性，判断断周六是否否玩网球playTennis=Y/N?30Step1:确确定根节点点分别计算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因此：根节节点为Outlook31Step2:分分枝选择哪个属属性进行划划分？32Step3:循循环选择哪个属属性进行划划分？33小结实例是由““属性-值值”对（pair））表示的目标函数具具有离散的的输出值可能需要析析取的描述述（disjunctivedescription）训练数据可可以包含错错误训练数据可可以包含缺缺少属性值值的实例34作业6-1画出出表示下面面布尔函数数的决策树树（a）A¬B（b）A[BC]（c）AXORB（d）[AB][CD]35作业6-2考虑虑下面的训训练样例集集合手动给出决决策树的构构造过程36作业6-3ID3仅仅寻找一个个一致的假假设，而候候选消除算算法寻找所所有一致的的假设。考考虑这两种种学习算法法间的对应应关系（a）假定定给定EnjoySport的四个训