决策树方法应用实例

•例：构造决策树。下表给出了取自AllElectronics顾客数据库元组训练集。编号年龄收入学生信用等级类别：购买电脑1=30高否一般不会购买2=30高否良好不会购买331…40高否一般会购买440中等否一般会购买540低是一般会购买640低是良好不会购买731…40低是良好会购买8=30中等否一般不会购买9=30低是一般会购买1040中等是一般会购买11=30中等是良好会购买1231…40中等否良好会购买1331…40高是一般会购买1440中等否良好不会购买•解：由题意可知：•s＝14，类标号属性“购买电脑”有两个不同值（即｛会购买，不会购买｝），因此有两个不同的类（即m＝2）。设类C1对应于“会购买”，类C2对应于“不会购买”。则s1＝9，s2＝5，p1＝9/14，p2=5/14。•①计算对给定样本分类所需的期望信息：•②计算每个属性的熵。•先计算属性“年龄”的熵。•对于年龄＝“=30”：s11＝2，s21＝3，p11=2/5，p21=3/5，••对于年龄＝“31…40”：s12=4，s22=0，p12=4/4=1，p22=0，•21222219955,9,5logloglog0.94014141414iiiIssIpp1121222233,2,3loglog0.9715555IssI122224,4,0log1004IssI•对于年龄＝“40”：s13=3，s23=2，p13=3/5，p23=2/5，•如果样本按“年龄”划分，对一个给定的样本分类所需的期望信息为：•因此，这种划分的信息增益是•Gain(年龄)=I(s1,s2)-E(年龄)=0.246。•计算“收入”的熵。•对于收入＝“高”：s11=2，s21=2，p11=0.5，p21=0.5，•对于收入＝“中等”：s12=4，s22=2，p12=4/6，p22=2/4，1323223322,3,2loglog0.9715555IssI112112221323545,,,0.694141414EIssIssIss年龄1121222222,2,2loglog14444IssI1222224422,4,2loglog0.9186666IssI•对于收入＝“低”：s13=3，s23=1，p13=3/4，p23=1/4，•如果样本按“收入”划分，对一个给定的样本分类所需的期望信息为：•因此，这种划分的信息增益是•Gain(收入)=I(s1,s2)-E(收入)=0.940-0.911＝0.029。•计算“学生”的熵。•对于学生＝“是”：s11=6，s21=1，p11=6/7，p21=1/7，1323223311,3,1loglog0.8114444IssI112112221323464,,,0.911141414EIssIssIss收入1121226611,6,1loglog0.5927777IssI•对于学生＝“否”：s12=3，s22=4，p12=3/7，p22=4/7，•如果样本按“学生”划分，对一个给定的样本分类所需的期望信息为：•因此，这种划分的信息增益是•Gain(学生)=I(s1,s2)-E(学生)=0.940-0.789＝0.151。•计算“信用等级”的熵。•对于信用等级＝“一般”：s11=6，s21=2，p11=6/8，p21=2/8，•对于信用等级＝“良好”：s12=3，s22=3，p12=3/6，p22=3/6，1222223344,3,4loglog0.9857777IssI1121122277,,0.7891414EIssIss学生1121226622,6,2loglog0.8118888IssI1222223333,3,3loglog16666IssI•如果样本按“信用等级”划分，对一个给定的样本分类所需的期望信息为：•因此，这种划分的信息增益是•Gain(信用等级)=I(s1,s2)-E(信用等级)=0.940-0.892＝0.048。•由于“年龄”属性具有最高信息增益，它被选作测试属性。创建一个节点，用“年龄”标记，并对每个属性值引出一个分支。样本据此划分，如图所示。1121122286,,0.8921414EIssIss信用等级收入学生信用等级类高否一般会购买低是良好会购买中等否良好会购买高是一般会购买收入学生信用等级类高否一般不会购买高否良好不会购买中等否一般不会购买低是一般会购买中等是良好会购买收入学生信用等级类中等否一般会购买低是一般会购买低是良好不会购买中等是一般会购买中等否良好不会购买=3031…4040年龄收入学生信用等级类高否一般不会购买高否良好不会购买中等否一般不会购买低是一般会购买中等是良好会购买表1年龄=30•当年龄=30时，对应于表1。S＝5，设类C1对应于“会购买”，类C2对应于“不会购买”。则s1＝2，s2＝3，p1＝2/5，p2=3/5。•①计算对给定样本分类所需的期望信息：•②计算每个属性的熵。•先计算属性“收入”的熵。•对于收入＝“高”：s11＝0，s21＝2，p11=0，p21=1，21222212233,2,3logloglog0.9715555iiiIssIpp•对于收入＝“中等”：s12=1，s22=1，p12=1/2，p22=1/2，•对于收入＝“低”：s13=1，s23=0，p13=1，p23=0，•如果样本按“收入”划分，对一个给定的样本分类所需的期望信息为：•因此，这种划分的信息增益是•Gain(收入)=I(s1,s2)-E(收入)=0.971-0.0.4＝0.571。1121222,0,2log022IssI1222221111,1,1loglog12222IssI1323,1,00IssI112112221323221,,,0.4555EIssIssIss收入•计算“学生”的熵。•对于学生＝“是”：s11＝2，s21＝0，p11=1，p21=0，•对于学生＝“否”：s12＝0，s22＝3，p12=0，p22=1，•如果样本按“学生”划分，对一个给定的样本分类所需的期望信息为：•因此，这种划分的信息增益是•Gain(学生)=I(s1,s2)-E(学生)=0.971-0＝0.971。1121222,2,0log022IssI1222,0,30IssI1121122223,,055EIssIss学生•计算“信用等级”的熵。•对于信用等级＝“一般”：s11＝1，s21＝2，p11=1/3，p21=2/3，•对于信用等级＝“良好”：s12＝1，s22＝1，p12=1/2，p22=1/2，•如果样本按“信用等级”划分，对一个给定的样本分类所需的期望信息为：•因此，这种划分的信息增益是•Gain(信用等级)=I(s1,s2)-E(信用等级)=0.971-0.951＝0.02。112122112,1,2loglog0.918333IssI1222221111,1,1loglog12222IssI1121122232,,0.95155EIssIss信用等级•由于“学生”属性具有最高信息增益，它被选作测试属性。创建一个节点，用“学生”标记，并对每个属性值引出一个分支。•同理，对表2进行计算。得出属性“信用等级”具有最高信息增益，它被选作测试属性。创建一个节点，用“信用等级”标记，并对每个属性值引出一个分支。•最终构造的决策树如下图所示。收入学生信用等级类中等否一般会购买低是一般会购买低是良好不会购买中等是一般会购买中等否良好不会购买表2年龄40年龄?学生?信用等级?会购买不会购买会购买会购买不会购买=3031…4040一般良好是否“购买电脑”的决策树由决策树产生分类规则对上图进行分析，提取的关联规则是：•IF年龄＝“=30”AND学生＝“否”THEN购买电脑＝“不会购买”•IF年龄＝“=30”AND学生＝“是”THEN购买电脑＝“会购买”•IF年龄＝“31...40”THEN购买电脑＝“会购买”•IF年龄＝“40”AND信用等级＝“良好”THEN购买电脑＝“不会购买”•IF年龄＝“40”AND信用等级＝“一般”THEN购买电脑＝“会购买”论文中的应用•题目：决策树算法的研究与应用作者：杨静1，张楠男2，李建1，刘延明1，梁美红1(1．西南石油大学，四川成都610500；2．西南油气田分公司信息中心，四川成都610500)发表期刊：计算机技术与发展第20卷．第2期2010年2月摘要：主要研究了数据挖掘中决策树算法的基本思想和算法。针对目前钻井过程故障诊断的需求，结合决策树算法的特点，提出了一种基于决策树的钻井过程故障诊断专家系统模型。分析了钻井系统事故状态下的相关特征参数，并对基于决策树的钻井过程状态和知识获取进行了详细的论述。通过实例运用ID3算法实现了决策树的建立，为钻井过程故障诊断奠定了坚实的基础。最后提出了对算法的改进，综合对实际数据的处理结果表明，基于数据挖掘的决策树算法可以很好地识别钻井过程中的不同状态，能够实现故障诊断。论文中的应用•结语：文中在论述了决策树算法的基础上，结合钻井工程与工艺，将决策树应用于这一领域。利用决策树知识表示与获取集于一身的优点，对基于决策树的钻井过程故障诊断专家系统提出了初步的应用模型。但该算法对大量数据的实现还有待下一步的工作去改进。•可以继续研究：可以学习ID3算法的改进C4.5算法，并结合应用。