生物数据挖掘-决策树实验报告

实验四决策树一、实验目的1.了解典型决策树算法2.熟悉决策树算法的思路与步骤3.掌握运用Matlab对数据集做决策树分析的方法二、实验内容1.运用Matlab对数据集做决策树分析三、实验步骤1.写出对决策树算法的理解决策树方法是数据挖掘的重要方法之一，它是利用树形结构的特性来对数据进行分类的一种方法。决策树学习从一组无规则、无次序的事例中推理出有用的分类规则，是一种实例为基础的归纳学习算法。决策树首先利用训练数据集合生成一个测试函数，根据不同的权值建立树的分支，即叶子结点，在每个叶子节点下又建立层次结点和分支，如此重利生成决策树，然后对决策树进行剪树处理，最后把决策树转换成规则。决策树的最大优点是直观，以树状图的形式表现预测结果，而且这个结果可以进行解释。决策树主要用于聚类和分类方面的应用。决策树是一树状结构，它的每一个叶子节点对应着一个分类，非叶子节点对应着在某个属性上的划分，根据样本在该属性上的不同取值将其划分成若干个子集。构造决策树的核心问题是在每一步如何选择适当的属性对样本进行拆分。对一个分类问题，从已知类标记的训练样本中学习并构造出决策树是一个自上而下分而治之的过程。2.启动Matlab，运用Matlab对数据集进行决策树分析，写出算法名称、数据集名称、关键代码，记录实验过程，实验结果，并分析实验结果(1)算法名称:ID3算法ID3算法是最经典的决策树分类算法。ID3算法基于信息熵来选择最佳的测试属性，它选择当前样本集中具有最大信息增益值的属性作为测试属性；样本集的划分则依据测试属性的取值进行，测试属性有多少个不同的取值就将样本集划分为多少个子样本集，同时决策树上相应于该样本集的节点长出新的叶子节点。ID3算法根据信息论的理论，采用划分后样本集的不确定性作为衡量划分好坏的标准，用信息增益值度量不确定性：信息增益值越大，不确定性越小。因此，ID3算法在每个非叶节点选择信息增益最大的属性作为测试属性，这样可以得到当前情况下最纯的划分，从而得到较小的决策树。ID3算法的具体流程如下：1）对当前样本集合，计算所有属性的信息增益；2）选择信息增益最大的属性作为测试属性，把测试属性取值相同的样本划为同一个子样本集；3）若子样本集的类别属性只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处；否则对子样本集递归调用本算法。(2)数据集名称：鸢尾花卉Iris数据集选择了部分数据集来区分IrisSetosa（山鸢尾）及IrisVersicolour（杂色鸢尾）两个种类。（3）实验代码：%%使用ID3决策树算法预测鸢尾花卉Iris种类clear;%%数据预处理disp('正在进行数据预处理...');[matrix,attributes_label,attributes]=id3_preprocess();%%构造ID3决策树，其中id3()为自定义函数disp('数据预处理完成，正在进行构造树...');tree=id3(matrix,attributes_label,attributes);%%打印并画决策树[nodeids,nodevalues]=print_tree(tree);tree_plot(nodeids,nodevalues);disp('ID3算法构建决策树完成！');%%构造函数id3_preprocessfunction[matrix,attributes,activeAttributes]=id3_preprocess()%%ID3算法数据预处理，把字符串转换为0,1编码%%读取数据txt={'序号''花萼大小''花瓣长度''花瓣宽度''类型''''小''长''长''versicolor''''小''长''长''versicolor''''小''长''长''versicolor''''小''短''长''versicolor''''小''长''长''versicolor''''小''短''长''versicolor''''小''长''短''versicolor''''大''长''长''versicolor''''大''长''短''versicolor''''大''长''长''versicolor''''大''长''长''versicolor''''大''长''长''versicolor''''大''长''长''versicolor''''小''长''长''setosa''''大''短''长''versicolor''''大''短''长''versicolor''''大''短''长''versicolor''''大''短''长''versicolor''''大''短''短''versicolor''''小''短''短''setosa''''小''短''长''setosa''''小''短''长''setosa''''小''短''长''setosa''''小''短''短''setosa''''小''长''短''setosa''''大''短''长''setosa''''大''短''长''setosa''''小''短''短''setosa''''小''短''短''setosa''''大''短''短''setosa''''小''长''短''setosa''''大''短''长''setosa''''大''短''短''setosa''''大''短''短''setosa'}attributes=txt(1,2:end);%attributes:属性和Label；activeAttributes=ones(1,length(attributes)-1);%activeAttributes:属性向量，全1；data=txt(2:end,2:end);%%针对每列数据进行转换[rows,cols]=size(data);matrix=zeros(rows,cols);%matrix：转换后的0,1矩阵；forj=1:colsmatrix(:,j)=cellfun(@trans2onezero,data(:,j));endend%%构造函数trans2onezerofunctionflag=trans2onezero(data)ifstrcmp(data,'小')||strcmp(data,'短')...||strcmp(data,'setosa')flag=0;return;endflag=1;end%%构造函数id3function[tree]=id3(examples,attributes,activeAttributes)%%ID3算法，构建ID3决策树%%提供的数据为空，则报异常if(isempty(examples));error('必须提供数据！');endnumberAttributes=length(activeAttributes);%activeAttributes:活跃的属性值；-1,1向量，1表示活跃；numberExamples=length(examples(:,1));%example:输入0、1矩阵；%创建树节点tree=struct('value','null','left','null','right','null');%如果最后一列全部为1，则返回“versicolor”lastColumnSum=sum(examples(:,numberAttributes+1));if(lastColumnSum==numberExamples);tree.value='versicolor';returnend%如果最后一列全部为0，则返回“setosa”if(lastColumnSum==0);tree.value='setosa';returnend%如果活跃的属性为空，则返回label最多的属性值if(sum(activeAttributes)==0);if(lastColumnSum=numberExamples/2);tree.value='versicolor';elsetree.value='setosa';endreturnend%%计算当前属性的熵p1=lastColumnSum/numberExamples;if(p1==0);p1_eq=0;elsep1_eq=-1*p1*log2(p1);endp0=(numberExamples-lastColumnSum)/numberExamples;if(p0==0);p0_eq=0;elsep0_eq=-1*p0*log2(p0);endcurrentEntropy=p1_eq+p0_eq;%%寻找最大增益gains=-1*ones(1,numberAttributes);%初始化增益fori=1:numberAttributes;if(activeAttributes(i))%该属性仍处于活跃状态，对其更新s0=0;s0_and_true=0;s1=0;s1_and_true=0;forj=1:numberExamples;if(examples(j,i));s1=s1+1;if(examples(j,numberAttributes+1));s1_and_true=s1_and_true+1;endelses0=s0+1;if(examples(j,numberAttributes+1));s0_and_true=s0_and_true+1;endendendif(~s1);%熵S(v=1)p1=0;elsep1=(s1_and_true/s1);endif(p1==0);p1_eq=0;elsep1_eq=-1*(p1)*log2(p1);endif(~s1);p0=0;elsep0=((s1-s1_and_true)/s1);endif(p0==0);p0_eq=0;elsep0_eq=-1*(p0)*log2(p0);endentropy_s1=p1_eq+p0_eq;if(~s0);%熵S(v=0)p1=0;elsep1=(s0_and_true/s0);endif(p1==0);p1_eq=0;elsep1_eq=-1*(p1)*log2(p1);endif(~s0);p0=0;elsep0=((s0-s0_and_true)/s0);endif(p0==0);p0_eq=0;elsep0_eq=-1*(p0)*log2(p0);endentropy_s0=p1_eq+p0_eq;gains(i)=currentEntropy-((s1/numberExamples)*entropy_s1)-((s0/numberExamples)*entropy_s0);endend%选出最大增益[~,bestAttribute]=max(gains);%设置相应值tree.value=attributes{bestAttribute};%去活跃状态activeAttributes(bestAttribute)=0;%根据bestAttribute把数据进行分组examples_0=examples(examples(:,bestAttribute)==0,:);examples_1=examples(examples(:,bestAttribute)==1,:);%当value=falseor0,左分支if(isempty(examples_0));leaf=struct('value','null','left','null','right','null');if(lastColumnSum=numberExamples/2);%formatrixexamplesleaf.value='true';elseleaf.value='false';endtree.left=leaf;else%递归tree.left=id3(examples_0,attributes,activeAttributes);end%当value=trueor1,右分支if(isempty(examples_1));l