实验三-决策树算法实验实验报告实验三决策树算法实验一、实验目的：熟悉和掌握决策树的分类原理、实质和过程；掌握典型的学习算法和实现技术。

二、实验原理: 决策树学习和分类.三、实验条件：四、实验内容：1 根据现实生活中的原型自己创建一个简单的决策树。

2 要求用这个决策树能解决实际分类决策问题。

五、实验步骤：1、验证性实验：（1）算法伪代码算法Decision_Tree(data,AttributeName) 输入由离散值属性描述的训练样本集data; 候选属性集合AttributeName。

输出一棵决策树。

（1）创建节点N；（2）If samples 都在同一类C中then （3）返回N作为叶节点，以类C标记；（4）If attribute_list为空then（5）返回N作为叶节点，以samples 中最普遍的类标记；//多数表决（6）选择attribute_list 中具有最高信息增益的属性test_attribute; （7）以test_attribute 标记节点N；（8）For each test_attribute 的已知值v //划分samples ；（9）由节点N分出一个对应test_attribute=v的分支；（10令Sv为samples中test_attribute=v 的样本集合；//一个划分块（11）If Sv 为空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：INNER CITY----“1”；TOWN----“2”；RURAL----“3”；SUBURBAN----“4”Income：5000~2万----“1”；2万~4万----“2”；4万以上----“3”Married Children CarMortgagePep：以上五个条件，若为“是”标记为“1”，若为“否”标记为“2”。

Age sex region income married children car mortgage pep1 2 1 1 2 1 1 2 21 2 1 1 2 2 2 2 12 1 4 1 2 1 2 2 12 1 1 1 1 2 2 2 2 1 2 1 1 1 2 2 2 21 2 1 1 2 1 2 1 12 1 2 1 1 2 1 1 2 2 1 1 1 2 1 1 2 1 2 13 1 2 2 1 2 1 2 1 2 2 2 1 2 2 2 2 2 1 2 2 2 2 1 1 2 1 2 2 1 1 2 1 1 2 2 1 2 1 2 2 1 2 1 1 1 2 1 2 2 2 1 3 2 1 2 1 1 1 2 2 1 1 1 2 1 1 1 2 11 1 32 2 2 1 2 13 1 2 2 1 2 2 2 1 3 2 3 3 1 1 1 2 1 3 2 2 3 1 2 1 1 2 3 1 3 3 1 1 2 2 1 3 2 1 3 1 2 1 2 2 3 2 1 3 1 1 1 1 1 3 1 1 3 1 2 1 1 2 3 1 3 3 1 2 2 2 2 3 24 3 1 2 2 1 1 3 1 3 3 2 2 1 1 2（3）Matlab语句：[Tree RulesMatrix]= DecisionTree(DataSet, AttributName)；六、实验结果：实验程序：function [Tree RulesMatrix]=DecisionTree(DataSet,AttributName) %输入为训练集，为离散后的数字，如记录1：1 1 3 2 1；%前面为属性列，最后一列为类标if nargin<1error('请输入数据集');elseif isstr(DataSet)[DataSet AttributValue]=readdata2(DataSet);elseAttributValue=[];endendif nargin<2AttributName=[];endAttributs=[1:size(DataSet,2)-1];Tree=CreatTree(DataSet,Attributs);disp([char(13) 'The Decision Tree:']);showTree(Tree,0,0,1,AttributValue,AttributName);Rules=getRule(Tree);RulesMatrix=zeros(size(Rules,1),size(DataSet,2));for i=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))]);for j=1:(length(rule)-1)/2RulesMatrix(i,rule((j-1)*2+1))=rule(j*2);endRulesMatrix(i,size(DataSet,2))=rule(length(rule));endendfunction Tree=CreatTree(DataSet,Attributs) %决策树程序输入为：数据集，属性名列表%disp(Attributs);[S ValRecords]=ComputEntropy(DataSet,0);if(S==0) %当样例全为一类时退出，返回叶子节点类标for i=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;for i=1:length(ValRecords)if(length(ValRecords(i).matrix)>mostlabelnum)mostlabelnum=length(ValRecords(i).matrix);mostlabel=i;endendTree.Attribut=mostlabel;Tree.Child=[];return;endfor i=1:length(Attributs)[Sa(i) ValRecord]=ComputEntropy(DataSet,i);Gains(i)=S-Sa(i);AtrributMatric(i).val=ValRecord;end[maxval maxindex]=max(Gains);Tree.Attribut=Attributs(maxindex);Attributs2=[Attributs(1:maxindex-1)Attributs(maxindex+1:length(Attributs))];for j=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;for i=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 [Entropy RecordVal]=ComputEntropy(DataSet,attribut) %计算信息熵if(attribut==0)clnum=0;for i=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))).matrix i];endEntropy=0;for j=1:length(classnum)P=classnum(j)/size(DataSet,1);if(P~=0)Entropy=Entropy+(-P)*log2(P);endendelsevalnum=0;for i=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)).matrix i];endEntropy=0;for j=1:valnumEntropys=0;for k=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;endendendfunction showTree(Tree,level,value,branch,AttributValue,AttributName) blank=[];for i=1:level-1if(branch(i)==1)blank=[blank ' |'];elseblank=[blank ' '];endendblank=[blank ' '];if(level==0)blank=[' (The Root):'];elseif isempty(AttributValue)blank=[blank '|_____' int2str(value) '______'];elseblank=[blank '|_____' value '______'];endendif(length(Tree.Child)~=0) %非叶子节点if isempty(AttributName)disp([blank 'Attribut ' int2str(Tree.Attribut)]);elsedisp([blank 'Attribut ' AttributName{Tree.Attribut}]);endif isempty(AttributValue)for j=1:length(Tree.Child)-1showTree(Tree.Child(j).root,level+1,j,[branch1],AttributValue,AttributName);endshowTree(Tree.Child(length(Tree.Child)).root,level+1,length(Tree.Child),[branch( 1:length(branch)-1) 0 1],AttributValue,AttributName);elsefor j=1:length(Tree.Child)-1showTree(Tree.Child(j).root,level+1,AttributValue{Tree.Attribut}{j},[branch 1],AttributValue,AttributName);endshowTree(Tree.Child(length(Tree.Child)).root,level+1,AttributValue{Tree.Attribu t}{length(Tree.Child)},[branch(1:length(branch)-1) 0 1],AttributValue,AttributName);endelseif isempty(AttributValue)disp([blank 'leaf ' int2str(Tree.Attribut)]);elsedisp([blank 'leaf ' AttributValue{length(AttributValue)}{Tree.Attribut}]);endendendfunction Rules=getRule(Tree)if(length(Tree.Child)~=0)Rules={};for i=1:length(Tree.Child)content=getRule(Tree.Child(i).root);%disp(content);%disp([num2str(Tree.Attribut) ',' num2str(i) ',']);for j=1:size(content,1)rule=cell2struct(content(j,1),{'str'});content(j,1)={[num2str(Tree.Attribut) ',' num2str(i) ',' rule.str]};endRules=[Rules;content];endelseRules={['C' num2str(Tree.Attribut)]};endend。