实验三-决策树算法实验实验报告

实验三决策树算法实验一、实验目的：熟悉和掌握决策树的分类原理、实质和过程；掌握典型的学习算法和实现技术。二、实验原理:决策树学习和分类.三、实验条件：四、实验内容：1根据现实生活中的原型自己创建一个简单的决策树。2要求用这个决策树能解决实际分类决策问题。五、实验步骤：1、验证性实验：（1）算法伪代码算法Decision_Tree(data,AttributeName)输入由离散值属性描述的训练样本集data;候选属性集合AttributeName。输出一棵决策树。（1）创建节点N；（2）Ifsamples都在同一类C中then（3）返回N作为叶节点，以类C标记；（4）Ifattribute_list为空then（5）返回N作为叶节点，以samples中最普遍的类标记；//多数表决（6）选择attribute_list中具有最高信息增益的属性test_attribute;（7）以test_attribute标记节点N；（8）Foreachtest_attribute的已知值v//划分samples；（9）由节点N分出一个对应test_attribute=v的分支；（10令Sv为samples中test_attribute=v的样本集合；//一个划分块（11）IfSv为空then（12）加上一个叶节点，以samples中最普遍的类标记；（13）Else加入一个由Decision_Tree(Sv,attribute_list-test_attribute)返回节点值。（2）实验数据预处理Age:30岁以下标记为“1”；30岁以上50岁以下标记为“2”；50岁以上标记为“3”。Sex：FEMAL----“1”；MALE----“2”Region：INNERCITY----“1”；TOWN----“2”；RURAL----“3”；SUBURBAN----“4”Income：5000~2万----“1”；2万~4万----“2”；4万以上----“3”MarriedChildrenCarMortgagePep：以上五个条件，若为“是”标记为“1”，若为“否”标记为“2”。Agesexregionincomemarriedchildrencarmortgagepep121121122121122221214121221211112222121112222121121211212112112211121121213122121212221222221222211212211211221212212111212221321211122111211121113222121312212221323311121322312112313311221321312122321311111311312112313312222324312211313322112（3）Matlab语句：[TreeRulesMatrix]=DecisionTree(DataSet,AttributName)；六、实验结果：实验程序：function[TreeRulesMatrix]=DecisionTree(DataSet,AttributName)%输入为训练集，为离散后的数字，如记录1：11321；%前面为属性列，最后一列为类标ifnargin1error('请输入数据集');elseifisstr(DataSet)[DataSetAttributValue]=readdata2(DataSet);elseAttributValue=[];endendifnargin2AttributName=[];endAttributs=[1:size(DataSet,2)-1];Tree=CreatTree(DataSet,Attributs);disp([char(13)'TheDecisionTree:']);showTree(Tree,0,0,1,AttributValue,AttributName);Rules=getRule(Tree);RulesMatrix=zeros(size(Rules,1),size(DataSet,2));fori=1:size(Rules,1)rule=cell2struct(Rules(i,1),{'str'});rule=str2num([rule.str([1:(find(rule.str=='C')-1)])rule.str((find(rule.str=='C')+1):length(rule.str))]);forj=1:(length(rule)-1)/2RulesMatrix(i,rule((j-1)*2+1))=rule(j*2);endRulesMatrix(i,size(DataSet,2))=rule(length(rule));endendfunctionTree=CreatTree(DataSet,Attributs)%决策树程序输入为：数据集，属性名列表%disp(Attributs);[SValRecords]=ComputEntropy(DataSet,0);if(S==0)%当样例全为一类时退出，返回叶子节点类标fori=1:length(ValRecords)if(length(ValRecords(i).matrix)==size(DataSet,1))break;endendTree.Attribut=i;Tree.Child=[];return;endif(length(Attributs)==0)%当条件属性个数为0时返回占多数的类标mostlabelnum=0;mostlabel=0;fori=1:length(ValRecords)if(length(ValRecords(i).matrix)mostlabelnum)mostlabelnum=length(ValRecords(i).matrix);mostlabel=i;endendTree.Attribut=mostlabel;Tree.Child=[];return;endfori=1:length(Attributs)[Sa(i)ValRecord]=ComputEntropy(DataSet,i);Gains(i)=S-Sa(i);AtrributMatric(i).val=ValRecord;end[maxvalmaxindex]=max(Gains);Tree.Attribut=Attributs(maxindex);Attributs2=[Attributs(1:maxindex-1)Attributs(maxindex+1:length(Attributs))];forj=1:length(AtrributMatric(maxindex).val)DataSet2=[DataSet(AtrributMatric(maxindex).val(j).matrix',1:maxindex-1)DataSet(AtrributMatric(maxindex).val(j).matrix',maxindex+1:size(DataSet,2))];if(size(DataSet2,1)==0)mostlabelnum=0;mostlabel=0;fori=1:length(ValRecords)if(length(ValRecords(i).matrix)mostlabelnum)mostlabelnum=length(ValRecords(i).matrix);mostlabel=i;endendTree.Child(j).root.Attribut=mostlabel;Tree.Child(j).root.Child=[];elseTree.Child(j).root=CreatTree(DataSet2,Attributs2);endendendfunction[EntropyRecordVal]=ComputEntropy(DataSet,attribut)%计算信息熵if(attribut==0)clnum=0;fori=1:size(DataSet,1)if(DataSet(i,size(DataSet,2))clnum)%防止下标越界classnum(DataSet(i,size(DataSet,2)))=0;clnum=DataSet(i,size(DataSet,2));RecordVal(DataSet(i,size(DataSet,2))).matrix=[];endclassnum(DataSet(i,size(DataSet,2)))=classnum(DataSet(i,size(DataSet,2)))+1;RecordVal(DataSet(i,size(DataSet,2))).matrix=[RecordVal(DataSet(i,size(DataSet,2))).matrixi];endEntropy=0;forj=1:length(classnum)P=classnum(j)/size(DataSet,1);if(P~=0)Entropy=Entropy+(-P)*log2(P);endendelsevalnum=0;fori=1:size(DataSet,1)if(DataSet(i,attribut)valnum)%防止参数下标越界clnum(DataSet(i,attribut))=0;valnum=DataSet(i,attribut);Valueexamnum(DataSet(i,attribut))=0;RecordVal(DataSet(i,attribut)).matrix=[];%将编号保留下来，以方便后面按值分割数据集endif(DataSet(i,size(DataSet,2))clnum(DataSet(i,attribut)))%防止下标越界Value(DataSet(i,attribut)).classnum(DataSet(i,size(DataSet,2)))=0;clnum(DataSet(i,attribut))=DataSet(i,size(DataSet,2));endValue(DataSet(i,attribut)).classnum(DataSet(i,size(DataSet,2)))=Value(DataSet(i,attribut)).classnum(DataSet(i,size(DataSet,2)))+1;Valueexamnum(DataSet(i,attribut))=Valueexamnum(DataSet(i,attribut))+1;RecordVal(DataSet(i,attribut)).matrix=[RecordVal(DataSet(i,attribut)).matrixi];endEntropy=0;forj=1:valnumEntropys=0;fork=1:length(Value(j).classnum)P=Value(j).classnum(k)/Valueexamnum(j);if(P~=0)Entropys=Entropys+(-P)*log2(P);endendEntropy=Entropy+(Valueexamnum(j)/size(DataSet,1))*Entropys;endendendfunctionshowTree(Tree,level,value,branch,AttributValue,AttributName)blank=[];fori=1:level-1if(branch(i)==1)blank=[blank'|'];elseblank=[blank''];endendblank=[blank''];if(level==0)blank=['(TheRoot):'];elseifisempty(AttributValue)blank=[blank'|__