AI_决策树学习_Chap6

《人工智能》第6章学习智能体-决策树学习巢文涵[e-mail]1001/G931北航计算机学院智能信息研究所2019年8月29日星期四2大纲简介决策树学习算法应用实例3决策树(DecisionTree)决策树学习是应用最广的归纳推理算法之一它是一种逼近离散函数的方法学习到的函数以决策树的形式表示主要用于分类对噪声数据有很好的鲁棒性能够学习析取表达4分类任务基本框架ApplyModel归纳演绎LearnModel模型TidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10测试集学习算法训练集5分类应用实例垃圾邮件过滤信贷分析新闻分类人脸识别、手写体识别等6决策树的结构图结构内部节点（非树叶节点，包括根节点）在一个属性上的测试分枝一个测试输出树叶节点类标识7决策树示例TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes10RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80K测试属性训练数据模型：决策树(Refund=YES)٧(Refund=NO٨MarSt=Single,Divorced٨TaxInc80K)٧(Refund=NO٨Married=NO)8另一棵决策树MarStRefundTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80K相同的数据可产生多棵决策树TidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes109决策树分类任务框架ApplyModel归纳演绎LearnModel模型TidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10测试集决策树算法训练集决策树10决策树应用RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据从根节点开始11决策树应用RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据12决策树应用RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据13决策树应用RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据14决策树应用RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据15决策树应用RefundMarStTaxIncYESNONONOYesNoMarriedSingle,Divorced80K80KRefundMaritalStatusTaxableIncomeCheatNoMarried80K?10测试数据指定欺诈为：“No”16决策树分类任务框架ApplyModelInductionDeductionLearnModelModelTidAttrib1Attrib2Attrib3Class1YesLarge125KNo2NoMedium100KNo3NoSmall70KNo4YesMedium120KNo5NoLarge95KYes6NoMedium60KNo7YesLarge220KNo8NoSmall85KYes9NoMedium75KNo10NoSmall90KYes10TidAttrib1Attrib2Attrib3Class11NoSmall55K?12YesMedium80K?13YesLarge110K?14NoSmall95K?15NoLarge67K?10TestSetTreeInductionalgorithmTrainingSetDecisionTree17大纲简介决策树学习算法应用实例18决策树算法Hunt’sAlgorithmCARTID3,C4.5SLIQ,SPRINT19基本的ID3算法20基本算法Don’tCheatRefundDon’tCheatDon’tCheatYesNoRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTaxableIncomeDon’tCheat80K=80KRefundDon’tCheatYesNoMaritalStatusDon’tCheatCheatSingle,DivorcedMarriedTidRefundMaritalStatusTaxableIncomeCheat1YesSingle125KNo2NoMarried100KNo3NoSingle70KNo4YesMarried120KNo5NoDivorced95KYes6NoMarried60KNo7YesDivorced220KNo8NoSingle85KYes9NoMarried75KNo10NoSingle90KYes1021决策树归纳贪婪策略根据特定的性能度量选择最好的划分属性要素哪个属性是最佳的分类属性？如何确定最佳划分点如何确定停止条件22度量标准——熵熵(Entropy)信息论中广泛使用的一个度量标准刻画任意样例集的纯度（purity）一般计算公式为：对于二元分类：给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为：Entropy(S)-plog2p-pΘlog2pΘ其中p是在S中正例的比例，pΘ是在S中负例的比例。在有关熵的所有计算中我们定义0log0为0。ciiippSEntropy12log)(23例子C10C26C13C23C11C25Entropy=-(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)=124度量标准——熵25度量标准——熵信息论中熵的一种解释熵确定了要编码集合S中任意成员（即以均匀的概率随机抽出的一个成员）的分类所需要的最少二进制位数=1接收者知道抽出的样例必为正，所以不必发任何消息，熵为0=0.5必须用一个二进制位来说明抽出的样例是正还是负，熵为1=0.8那么对所需的消息编码方法是赋给正例集合较短的编码，可能性较小的反例集合较长的编码，平均每条消息的编码少于1个二进制位ppp26性能度量——信息增益属性的信息增益使用这个属性分割样例而导致的期望熵降低的数量Values(A)是属性A所有可能值的集合Sv是S中属性A的值为v的子集，即Sv={sS|A(s)=v}当对S的一个任意成员的目标值编码时，Gain(S,A)的值是在知道属性A的值后可以节省的二进制位数)(||||)(),()(AValuesvvvSEntropySSSEntropyASGain27例子假设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.940048.000.1)14/6(811.0)14/8(940.0)()14/6()()14/8()()(||||)(),(},{StrongWeakStrongWeakvvvSEntropySEntropySEntropySEntropySSSEntropyWindSGain28选择最好的分类属性29大纲简介决策树学习算法应用实例30应用实例问题及数据集根据其他属性，判断周六是否玩网球playTennis=Y/N?31Step1:确定根节点分别计算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因此：根节点为Outlook32Step2:分枝选择哪个属性进行划分？33Step3:循环选择哪个属性进行划分？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）假定给定EnjoySport的四个训练样例，画出ID3学习的决策树（b）学习到的决策树和从同样的样例使用变型空间算法得到的变型空间间有什么关系？树等价于变型空间的一个成员吗？38作业6-4实现ID3算法