机器学习决策树算法ID3

1、山东大学计算机学院实验报告实验题目：决策树算法id3学号：日期：2016.12.6 班级：2014级4班 姓名：email :实验目的：1 .熟悉matlab环境及相关函数的熟练使用。2学习如何构造一棵决策树，并且用matlab画岀树形状。3学习如何使用一棵决策树，即将测试数值代入时,如何判断属于d那一类。4.会写测试集代入的分类表达式和类别的逻辑表达式并化简。5分析该算法准确性。硬件环境:windowslo操作系统软件环境：matlab 环境,azure ml 平台实验步骤：、背景知识及原理决策树算法：树状结构每一个叶子节点对应着一个分类决策树方法在分类、预测、规则提取等领域有着广泛的应用。

2、在20世纪70 年代后期和80年代初期，机器学习研究者j.ross quinilan提出了 id3算法以 后，决策树在机器学习、数据挖掘领域得到极大的发展。quinilan后来又提岀 了 c4.5，成为新的监督学习算法。1984年几位统计学家提出了 cart分类算法。id3和art算法大约同时被提出，但都是采用类似的方法从训练样本中学习决策树的。决策树是一树状结构，它的每一个叶子节点对应着一个分类，非叶子节点对应着在某个属性上的划分，根据样本在该属性上的不同取值将其划分成若干个子 集。构造决策树的核心问题是在每一步如何选择适当的属性对样本进行拆分。对 个分类问题，从已知类标记的训练样本中学习并

3、构造出决策树是一个自上而下 分而治之的过程。常见的决策树算法"决策树算法。算法描述qid3算法。其核心是在决策树的各级节点上，使用信息增益方法作为属性的选择标准， 来帮助确定生成每个节点时所应采用的合适属性。c4.5算法qc4.5决策树算法相对于id3算法的重要改进是使用信息增益率来选择节点 属性。c4.5算法可以克服id3算法存在的不足：id3算法只适用于离散的描 述属性，而c4.5算法既能够处理离散的描述属性，乂可以处理连续的描述 属性cart算法qcart决策树是一种1分有效的非参数分类和回归方法，通过构建树、修剪 树、评估树来构建一个二叉树。当终节点是连续变量时，该树为回归树

4、；当 终节点是分类变量时，该树为分类树卜id3算法简介及基本原理id3算法基于信息嫡来选择最佳的测试属性，它选择当前样本集中具有最大信息增益值的属性作为测试属性；样本集的划分则依据测试属性的取值进行,测 试属性有多少个不同的取值就将样本集划分为多少个子样本集伺时决策树上相 应于该样本集的节点长出新的叶子节点。id3算法根据信息论的理论,采用划分 后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量不确定性:信 息增益值越大，不确定性越小。因此jd3算法在每个非叶节点选择信息增益最 大的属性作为测试属性，这样可以得到当前情况下最纯的划分，从而得到较小的 决策树。设s是s个数据样本的集合。假

5、定类别属性具有m个不同的值： qg二1, 2，m）,设目是类g中的样本数。对_个给定的样本，它总的信息爛，（s,s2，.，耳）=-乞目log?（目）口c为z，其中，鸟是任意样本属于q的概率，一般可以设一个属性a具有k个不同的值畑心，利用属性a将集合s划分为k个子集虑，,乞，其中号包含了集合s中属性a取勺值的样本。若选择属性a为测试属性，则这些子集就是从集合s的节点生长出来的新的叶节点。设衍 是子集码中类别为5的样本数，则根据属性a划分样本的信息爛为 四）=£宓+阴+%疋曲j，,>1 s其中z（sj,呵，%）=为号呂2（号）i-1沁 +*2j+%；是子集号中类别为g的样本的概率。

6、最后，用属性a划分样本集s后所得的信息增益（gain ）为显认（q = 2（勺,巧,，耳）一 e（q显然運（q越小,gain（a）的值就越大,说明选择测试属性a对于分类提供的信息越大，选择a之后对分类的不确定程度越小。属性a的k个不同的值对 应的样本集s的k个子集或分支，通过递归调用上述过程（不包括已经选择的 属性）,生成其他属性作为节点的子节点和分支来生成整个决策树。id3决策树 算法作为一个典型的决策树学习算法,其核心是在决策树的各级节点上都用信息 增益作为判断标准来进行属性的选择，使得在每个非叶子节点上进行测试时，都 能获得最大的类别分类增益，使分类后的数据集的爛最小。这样的处理方法使得

7、 树的平均深度较小，从而有效地提高了分类效率。id3算法的具体流程1) 对当前样本集合,计算所有属性的信息增益；2) 选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同 子样本集；3) 若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处；否则对子样本集递归调用本算法。二实验步骤1. 因为以前经常使用微软的azure平台,这次仍然想用这个平台实验一下。测试使用决策树算法求出的准确率和召回率等以及改变参数对结果的影响。a.两分类决策树(第一个图是数据,前12个数据;第二个图是平台上的流程图)再try7.txt -记事本文件(f)漏辂(

8、e)格式(0) m(v)网助(h)xabcdef111111212311132321231111132311222312223322212322333122333312433112n 212312isqeqpqn aaipsojooso000l0乙rods idi岸吗訓得6刑mn丄9ai1isoj 9s|e-j£££0£££00luoispajjxetwy9ai;e6a| 95|弓saiisoj mn丄°%t壷回昱£££区壷的我'd乙工第b '郢族d £讦碧识郦：番芳e

9、s|ejaids payijejis pees cuopuey|ds peziiuopuey .sz*o 9屮 ui saoj jo uoipejjs/aoy #|dsapouj 6uini|ds日eg l!|ds r4monpw»u»j -si/n<1rm "ipxinuui run» jo<jdsmsayussmil 1m71sxiwdoia iimwptdx rsv1avsw*mn i2n j1avsa3f01smnn»b oamj1tvo 1xamb olhsibfw 8dalsaik>o jmitaj 丽as1 6

10、umuo)厂l血 kias。】 xu。冈几“。叮nfj0； 1aau01aso 6 1*<auooiw讽叫jsswv 0】umu。aftnur縹 ntq »1町g啦a*$>inep 6uwru ptqfiutjnn om1x*h»>o p<* indui nrom)n©ag-th 样imnra p*$dt?入（apcrimmt> macro、 x0 x c http/$tudioazurrml net hu */vh k l “： s ao>2ci4614.：- i71 “小"/f* “；-山/f rit/（xm7；仆

11、？（ :461 i sn.i * u : -a77r f- q !通过可视化平台的结果对比可以发现决策树算法的准确率很低，我感觉这个的原因是数据太少,所以偶然性太强,数据若是多一些,可能会好一些。2. 开始自己着手写matlab程序，刚开始看到题感觉挺简单的，不就是算出爛，然后算信息增益得到每次要判断的属性，那树不就画出来了么。然而事实告 诉我，用笔算的简单但是写程序就不那么容易了。每次传进去的是一批数据，得 根据数据去画树。然后我就通过看清华大学那本机器学习的书，找到了一个伪代 码的算法，思路没有错，就是一个递归算法,输入的变量是数据和属性,输出的 变量是一棵树的结构。照着这个循环写完之后，

12、运行出来又出现了错误，然后和 同学讨论发现是结构体的问题结构体比较bt的地方是要求参数数目是相同的, 所以每次定义结构体的以及每个return的时候都需要写全所有的参数，即使为 空。（第一张图片是算法伪代码，第二张是结构体的写法）输入：f)(工1.“|),(丄釘力)(he."”"，风” a 01,07a.粋 wflmljctfih vfiltl ir<*<fcfi<tat<*(/jf >4) 1:生成饬成node;2: if d中样本个jh j同类别c then3： 梅node杯记为c类叶结za, return4： end if5： if 4

13、«= 0 or d中竹本布a卜取值相同then6： node杯记为叶结d. )1类别杯记为d中样本数的类;return 7： end if追归何茨得最优划分属m運归通aj.怡彷（3）.4 a中去丼a.8：从1中选择优划分件 9： for a.的毎个（ft a： do 10： 为node生肢一个分支; 11:if dy 为空 then12：将分支结点标记为叶13:else14:以 tycgcncrbtc（d.取備为町的样木f集;林"多的类；roturn16： end for15:end iftree = struct c alue?, nullz);%如果样本都屈于同一类别，

14、则将节点标记为该类别1 as sum= 1 eng th (f ind (dat a (m+1, : )=1); %lastcolunmsum = sum(data(6, '!/);if (last.sum = 1):tree, valu已='true?;tree.node= null'tree.nextsx=o;%树的每个节点的下一个要选择的属性 tree. child=，false宀节点是否有下一个孩子 returnend3把树构造好后,返回的是一棵树的结构,里1:1包含了好几层,可以用plot的专门画树的方法画出来。但是，如何使用这棵树呢？我是把每棵树的每个节点

15、也就是结构体构造了好几个属性（如上图所示），保存了节点的类别（1或者2 ）, 保存了节点下一个属性（最大信息增益的属性），保存了它是否是叶子节点。这 样每次使用树的时候,代入数值后,先比较第一个最大信息增益的属性,然后找 下一个，直到叶子节点就可以判断出类别了。第二个问题是第二个测试数据中的第二维是d ,并不在该有的属性集中，然后我按照老师上课讲的方法，把它设置为属性集(1,2;3)中出现次数最多的值3 z然后去计算。4.算法的过程：a是id3算法中最后的包括了递归的循环(注意每次递归进去的是去掉了已使用过的属性值的，数据data和属性attributes都要去掉);b是信息增益的求法；c是判

16、断样本在属性上取值是否相同：a从属性中选择最优划分属性求最优属性位于笫a行，后而递归传入data时记得去掉那一行a=gain(data,attributes);treenextsx=a;ma=length(unique(data(a,:);号首先对每一个属性循环，生成node的一个分支for i=l:manode=struct('value *,1 null1 );nodenode=1 null1;node . nextsx=0; %树的每个节点的卜个要选择的属性tree.node(i)=node;%得到data屮在该属性上不同取值的样本子集dd% dl, d2, d3, d4 =fk

17、 jz (data, a);dd=;for t=l:1if date(a,t)=idd=dd,data(:,t);endendif (isempty(dd)%fprintf ( 1 data中在属性上不同取值的样本子集为空n 1 );if (last_sum >= ( 1 / 2)*1);tree.node(i) .value= 'true *;elsetree.node (i) .value = 1 false 1;endtree, node (i)nextsx=0;%树的每个节点的下一个耍选择的属性elsedd(m, ：) = ;shux=attributes;shux (a

18、)=;treenode(i)=id3(ddz shux);% treenode(i)=a;endendbfor i=l:m2xlz x2z x3, x4 =fk jz (x, i) ; %每次都得到按照某一个属性分开的矩阵11 (i, :) = size(xlz2)/12z size(x2z2)/12z size(x3,2)/12z size(x4z2)/12;%5 行4列，5种特征，每种特征中每种节点占总结点，也就是sv/sif size (xl,2)/12=0pll(i,1),pl2(if1),entrol(i,1)=entropy(xl(m,:),1,2);endif size (x2z

19、 2)/12=0pll(i,2),pl2(i,2),entrol(i,2)=entropy(x2(m,:),1,2);endif size (x3,2)/12-=0pll(i,3),pl2(i,3),entrol(i,3)=entropy(x3(m,:),1,2);endif size (x4,2)/12=0pll(i,4),pl2(iz 4),entrol(i,4)=entropy(x4(mz :), 1,2);endgain2(i)=entro-(11(iz1)*entrol(iz1)+11(i,2)*entrol(i,2)+11(i,3)*entro 1 (i,3)+ll (iz 4)*entrol(i,4);end咎求最大的信息增益位于的行数gain_max=find(gain2=(max(gain2);gain_max = gain_max(1);c. m,1=size (x);a=0;for i=2:lfor w=l:m-1if x(w, 1)=x(w,i)returnendendenda=l；三、实验结果l树的结构:算上根节点分成了 4层，属性依次选的是1,2 , 5 （第一张图是画的这次分出的树的结构；第二张图是