AI_决策树学习_Chap6

1、人工智能第6章学习智能体-决策树学习 G1001/G9317/12/20221大纲简介决策树学习算法应用实例2决策树(Decision Tree)决策树学习是应用最广的归纳推理算法之一它是一种逼近离散函数的方法学习到的函数以决策树的形式表示主要用于分类对噪声数据有很好的鲁棒性能够学习析取表达 3分类任务根本框架4分类应用实例垃圾邮件过滤信贷分析新闻分类人脸识别、手写体识别等5决策树的结构图结构内部节点（非树叶节点，包括根节点）在一个属性上的测试分枝一个测试输出树叶节点类标识6决策树例如分类型分类型连续型类别RefundMarStTaxIncYESNONONOYesNoMarried Singl

2、e, Divorced 80K测试属性训练数据模型：决策树(Refund=YES) (Refund=NO MarSt=Single,Divorced TaxInc 80K) (Refund=NO Married=NO)7另一棵决策树MarStRefundTaxIncYESNONONOYesNoMarried Single, Divorced 80K相同的数据可产生多棵决策树分类型分类型连续型类别8决策树分类任务框架决策树9决策树应用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K测试数据从根节点开始10决策树应用Refund

3、MarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K测试数据11决策树应用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K测试数据12决策树应用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K测试数据13决策树应用RefundMarStTaxIncYESNONONOYesNoMarried Single, Divorced 80K测试数据14决策树应用RefundMarStTaxIncYESNONONO

4、YesNoMarried Single, Divorced 80K测试数据指定欺诈为： “No15决策树分类任务框架Decision Tree16大纲简介决策树学习算法应用实例17决策树算法Hunts AlgorithmCARTID3, C4.5SLIQ,SPRINT18根本的ID3算法19根本算法Dont CheatRefundDont CheatDont CheatYesNoRefundDont CheatYesNoMaritalStatusDont CheatCheatSingle,DivorcedMarriedTaxableIncomeDont Cheat= 80KRefundDont

5、 CheatYesNoMaritalStatusDont CheatCheatSingle,DivorcedMarried20决策树归纳贪婪策略根据特定的性能度量选择最好的划分属性要素哪个属性是最正确的分类属性？如何确定最正确划分点如何确定停止条件21度量标准熵熵(Entropy)信息论中广泛使用的一个度量标准刻画任意样例集的纯度（purity）一般计算公式为：对于二元分类：给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为： Entropy(S) -plog2p-plog2p其中p是在S中正例的比例，p是在S中负例的比例。在有关熵的所有计算中我们定义0log0为0。

6、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 那么对所需的消息编码方法是赋给正例集合较短的编码，可能性较

7、小的反例集合较长的编码，平均每条消息的编码少于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.

8、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,-3Humidity : 0.151Temperature : 0.029因此：根节点为Outlook31Step 2: 分枝选择哪个属性进行划分？32Step 3: 循环选择哪个属性进行划分？33小结实例是由“属性-值对（pair）表示的目标函数具有离散的输出值可能需要析取的描述（disjunctive description）训练数据可以包含错误训练数据可以包含缺少属性值的实例34作业6-1画出表示下面布尔函数的决策树 （a）AB（b）ABC（c）A XOR B（d）AB CD35作业6-2考虑下面的训练样例集合 手动给出决策树的构造过程36作业6-3 ID3仅寻找一个一致的假设，而候选消除算法寻找所有一致的假设。考虑这两种学习算法间的对应关系 （a