机器学习决策树算法ID3

山东大学计算机学院实验报告实验题目：决策树算法ID3学号：日期：2016.12.6班级：2014级4班姓名：Email :实验目的：1 .熟悉matlab环境及相关函数的熟练使用。2 .学习如何构造一棵决策树，并且用matlab画出树形状。3. 学习如何使用一棵决策树，即将测试数值代入时，如何判断属于哪一类。4. 会写测试集代入的分类表达式和类别的逻辑表达式并化简。5 .分析该算法准确性。硬件环境：windows10操作系统软件环境：matlab 环境，Azure ML平台实验步骤：一、背景知识及原理决策树算法：树状结构，每一个叶子节点对应着一个分类决策树方法在分类、预测、规则提取等领域有着广泛的应用。在20世纪70 年代后期和80年代初期，机器学习研究者J.Ross Quinilan提出了 ID3算法以 后，决策树在机器学习、数据挖掘领域得到极大的发展。Quinilan后来又提出 了 C4.5，成为新的监督学习算法。1984年几位统计学家提出了 CART分类算法。ID3和ART算法大约同时被提出，但都是采用类似的方法从训练样本中学习决 策树的。决策树是一树状结构，它的每一个叶子节点对应着一个分类，非叶子节点对 应着在某个属性上的划分，根据样本在该属性上的不同取值将其划分成若干个子 集。构造决策树的核心问题是在每一步如何选择适当的属性对样本进行拆分。对 个分类问题，从已知类标记的训练样本中学习并构造出决策树是一个自上而下 分而治之的过程。常见的决策树算法决策树算法算法描述ID3算法其核心是在决策树的各级节点上，使用信息增益方法作为属性的选择标准， 来帮助确定主成每个节点时所应采用的合适属性 -C4.5算法C4.5决策树算法相对于ID3算法的重要改进杲使用信息增益率来选择节点 属性。C4.5算法可以克服ID3算法存在的不足：ID3算法只适用于离散的描 述属性，而C4.5算法既能够处理离散的描述属性，又可以处理连续的描述 属性CART算法CART决策树杲一种分有效的非参数分类和回归方法，通过构建树、修剪 树、评估树来构建一个二叉树。当终节点是连续变量时，该树为回归树；当 终节点是分类变量时，该树为分类树卜ID3算法简介及基本原理ID3算法基于信息熵来选择最佳的测试属性，它选择当前样本集中具有最大 信息增益值的属性作为测试属性；样本集的划分则依据测试属性的取值进行，测 试属性有多少个不同的取值就将样本集划分为多少个子样本集，同时决策树上相 应于该样本集的节点长出新的叶子节点。ID3算法根据信息论的理论，采用划分 后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量不确定性：信 息增益值越大，不确定性越小。因此D3算法在每个非叶节点选择信息增益最 大的属性作为测试属性，这样可以得到当前情况下最纯的划分，从而得到较小的 决策树。设S是s个数据样本的集合。假定类别属性具有m个不同的值:W），设馬是类q中的样本数。对个给定的样本，它总的信息熵为冷心血）=宅目囲，其中，目是任意样本属于G的概率，般可以 用&估计。设一个属性A具有 k个不同的值宀，卫，利用属性A将集合S划分为 k个子集（沈务，號，其中巧包含了集合S中属性A取幻值的样本。若选择属性A为测试属性，则这些子集就是从集合S的节点生长出来的新的叶节点。设知 是子集号中类别为5的样本数,则根据属性A划分样本的信息熵为 歐卫）=迟切+旬+知知隔i口 _ % + 呵+%其中，2-1厂 ； 是子集号中类别为5的样本的概率。最后,用属性A划分样本集S后所得的信息增益（Gain ）为GaM.A） = !（s1,s2,.,sk）-E（A）显然遲（卫）越小，Gain（A）的值就越大，说明选择测试属性A对于分类提供 的信息越大，选择A之后对分类的不确定程度越小。属性A的k个不同的值对 应的样本集S的k个子集或分支，通过递归调用上述过程（不包括已经选择的 属性），生成其他属性作为节点的子节点和分支来生成整个决策树。ID3决策树 算法作为一个典型的决策树学习算法,其核心是在决策树的各级节点上都用信息 增益作为判断标准来进行属性的选择，使得在每个非叶子节点上进行测试时，都 能获得最大的类别分类增益，使分类后的数据集的熵最小。这样的处理方法使得 树的平均深度较小，从而有效地提高了分类效率。ID3算法的具体流程1 ）对当前样本集合，计算所有属性的信息增益；2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同 个子样本集；3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值 并标上相应的符号，然后返回调用处；否则对子样本集递归调用本算法。二、实验步骤1因为以前经常使用微软的Azure平台，这次仍然想用这个平台实验一下。 测试使用决策树算法求出的准确率和召回率等以及改变参数对结果的影响。a.两分类决策树（第一个图是数据，前12个数据；第二个图是平台上的流程图）J try/.txi记事本帮助旧- X文件旧編辑（E格式（O）查看（V）A3匚DE=A1111112123111323212311111323112223122233222123223331223333124331122123120.75022网TWO NNCTJiJTT IKn/a-El-Il TIMEivai/t-Trairt M-sir ia5T.H1JSCDEFi5hedSTitTUiPFrL?frtarRiinhmms RHlidtofl |irjfiad r直.J Sufrnurv5曲 IQ CSVCc-nhvrl Id 2*ifiiiittonqrl Iq SvMLiflhl：Ccwen id T5Vj Elati lfci|ut jnd DulpulDvsTDaiB WariuilF参数配置：（随机种子0, 0.25的测试集）丿 Split DataSplitting modeSplit RowsFraction of rows in the.Randomized splitRandom seedTrue PositiveFalse NegativeFalse PositiveTrue NegativePositive LabeNsgative L日 beMkrosoft Azure Madhe Learning Studtod闊 haHEMEM jjt Dita bcjmffll CCPW*?iCfl5昴I &zcd Diasic| iflj E-urti McdriIjP Tat-CiafiE N執個 陶IrfOK#结果：测试集共3个数据，分错了 2个，准确率为33.3%，召回率1%。%钏m0Stratified splitFalseAccuracyPrecision0.3330.333RecallFl Score1.0000.500tipflnTTHTD - Metoi- J4C | iTtiiiiZftliJiflaMuramLnEVHQni即HcrfItfafapatBCftJiH如立三 Microsoft Azune Machine Learning Studio1 J:-1- : - -H會戛 女口哙旧心灯 5crr-fd r.Y.rp-d SlazisticsiWi AS ViELialisalianD.MXjBu5H Tl?HJUIFR1通过可视化平台的结果对比可以发现决策树算法的准确率很低，我感觉这个 的原因是数据太少，所以偶然性太强，数据若是多一些，可能会好一些。2开始自己着手写matlab程序，刚开始看到题感觉挺简单的，不就是算出熵，然后算信息增益得到每次要判断的属性，那树不就画出来了么。然而事实告 诉我，用笔算的简单但是写程序就不那么容易了。每次传进去的是一批数据，得 根据数据去画树。然后我就通过看清华大学那本机器学习的书，找到了一个伪代 码的算法，思路没有错，就是一个递归算法，输入的变量是数据和属性，输出的 变量是一棵树的结构。照着这个循环写完之后，运行出来又出现了错误，然后和 同学讨论发现是结构体的问题结构体比较BT的地方是要求参数数目是相同的， 所以每次定义结构体的以及每个return的时候都需要写全所有的参数，即使为 空。（第一张图片是算法伪代码，第二张是结构体的写法）第二个问题是第二个测试数据中的第二维是D ,并不在该有的属性集中，然 后我按照老师上课讲的方法，把它设置为属性集(1，2，3 )中出现次数最多的 值3，然后去计算。4算法的过程：a是ID3算法中最后的包括了递归的循环(注意每次递归进 去的是去掉了已使用过的属性值的，数据data和属性attributes都要去掉)； b是信息增益的求法；c是判断样本在属性上取值是否相同：a-%从属性中选择最优划分属性a,求最优属性位于第a行，后面递归传入data时记得去掉那 一行a=gain(data,attributes);tree.nextsx=a;ma=length(unique(data(a,:);%首先对每一个属性循环，生成node的一个分支for i=1:manode=struet value, null);node.node null;node.nextsx=0 %树的每个节点的下一个要选择的属性tree.node(i)=node;%得到data中在该属性上不同取值的样本子集dd% d1,d2,d3,d4=fkjz(data,a);dd=;for t=1:lif data(a,t)=idd=dd,data(:,t);endendif (isemp ty(dd)%fprintf(data中在属性上不同取值的样本子集为空n);if (last_sum =( l / 2)*l);tree.node(i).valuetrue;elsetree.node(i).value false;endt ree.node(i).nex tsx=0%树的每个节点的下一个要选择的属性elsedd(a,:) = ;shux=attributes;shux(a) = ;tree.node(i)=ID3(dd,shux);% tree.node(i)=a;endendb.for i=1:m2x1,x2,x3,x4=fkjz(x,i) %每次都得到按照某一个属性分开的矩阵I1(i,:)=size(x1,2)/12,size(x2,2)/12,size(x3,2)/12,size(x4,2)/12; %5 行4列，5种特征，每种特征中每种节点占总结点，也就是Sv/Sif size(x1,2)/12=0p11(i,1),p12(i,1),entro1(i,1)=entropy(x1(m,:),1,2);endif size(x2,2)/12=0p11(i,2),p12(i,2),entro1(i,2)=entropy(x2(m,:),1,2);endif size(x3,2)/12=0p11(i,3),p12(i,3),entro1(i,3)=entropy(x3(m,:),1,2);endif size(x4,2)/12=0p11(i,4),p12(i,4),entro1(i,4)=entropy(x4(m,:),1,2);endgain2(i)=entro-(l1(i,1)*entro1(i,1)+l1(i,2)*entro1(i,2)+l1(i,3)*entro 1(i,3)+l1(i,4)*entro1(i,4);end%求最大的信息增益位于的行数gain_max=find(gain2=(max(gain2);gain_max = gain_max(1);cm,l=size(x);a=0;for i=2:lfor w=1:m-1if x(w,1)=x(w,i)returnendendenda=1;三、实验结果1树的结构：算上根节点分成了 4层，属性依次选的是1,2,5（第一张图 是画的这次分出的树的结构；第二张图是调用算法后返回了的树；后面几张图是 打开树的结构体的内部参数和结构：其中，true是指w1类，false是指w2类。 每个结构体都是包含了 3个属性，value是类别，nextsx是下一个要选择的信 息增益最大的属性位于的行数（因为每次我代入递归的时候是去掉已用过的属 性，所以显示的第一次nextsx=1即第一行属性，第二次nextsx=1，也就是第 二行，第三次nextsx=3，也就是第五行）tree是根节点，按照第一个属性往下 分出了 4个子集，其中第二个子集又按照第二个属性分出了 3个子集，这3个 子集的第一个子集按照第五个属性分出3个节点，自此分好）treeri 1x1 也座包含3个字段valuen&xt5x nodenull结论分析与体会：刚开始感觉这个题还挺简单的，因为思路是非常清晰的，根据信息增益找属 性，然后递归ID3算法就能得到树的结构了，但是用笔算简单，用程序写的健 全是不容易的。特别是争取更加抽象一些，不能只根据这12个数据来算，最好 是以后不管传入什么数据进去都是可以算出来的。所以每个算法都包装一下，思 路一定要清晰。回过头看这个题目，感觉机器学习真的不能只靠听课了，平时要多看博客之 类的，才能深刻理解。除此之外感觉matlab越来越熟练了。