搜索
算法分析与设计决策树算法一、程序代码：1.tree_plot.mfunctiontree_plot(p,nodevalues)%%参考treeplot函数[x,y,h]=treelayout(p);f=find(p~=0);pp=p(f);X=[x(f);x(pp);NaN(size(f))];Y=[y(f);y(pp);NaN(size(f))];X=X(:);Y=Y(:);n=length(p);ifn500,holdon;plot(x,y,'ro',X,Y,'r-');nodesize=length(x);fori=1:nodesize%text(x(i)+0.01,y(i),['node'num2str(i)]);text(x(i)+0.01,y(i),nodevalues{1,i});endholdoff;elseplot(X,Y,'r-');end;xlabel(['height='int2str(h)]);axis([0101]);end2.queue_push.mfunction[newqueue]=queue_push(queue,item)%%进队%cols=size(queue);%newqueue=structs(1,cols+1);newqueue=[queue,item];end3.queue_pop.mfunction[item,newqueue]=queue_pop(queue)%%访问队列ifisempty(queue)disp('队列为空，不能访问！');return;enditem=queue(1);%第一个元素弹出newqueue=queue(2:end);%往后移动一个元素位置end4.queue_curr_size.mfunction[length_]=queue_curr_size(queue)%%当前队列长度length_=length(queue);end5.print_tree.mfunction[nodeids_,nodevalue_]=print_tree(tree)%%打印树，返回树的关系向量globalnodeidnodeidsnodevalue;nodeids(1)=0;%根节点的值为0nodeid=0;nodevalue={};ifisempty(tree)disp('空树！');return;endqueue=queue_push([],tree);while~isempty(queue)%队列不为空[node,queue]=queue_pop(queue);%出队列visit(node,queue_curr_size(queue));if~strcmp(node.left,'null')%左子树不为空queue=queue_push(queue,node.left);%进队endif~strcmp(node.right,'null')%左子树不为空queue=queue_push(queue,node.right);%进队endend%%返回节点关系，用于treeplot画图nodeids_=nodeids;nodevalue_=nodevalue;endfunctionvisit(node,length_)%%访问node节点，并把其设置值为nodeid的节点globalnodeidnodeidsnodevalue;ifisleaf(node)nodeid=nodeid+1;fprintf('叶子节点，node:%d\t，属性值:%s\n',...nodeid,node.value);nodevalue{1,nodeid}=node.value;else%要么是叶子节点，要么不是%ifisleaf(node.left)&&~isleaf(node.right)%左边为叶子节点,右边不是nodeid=nodeid+1;nodeids(nodeid+length_+1)=nodeid;nodeids(nodeid+length_+2)=nodeid;fprintf('node:%d\t属性值:%s\t，左子树为节点：node%d，右子树为节点：node%d\n',...nodeid,node.value,nodeid+length_+1,nodeid+length_+2);nodevalue{1,nodeid}=node.value;endendfunctionflag=isleaf(node)%%是否是叶子节点ifstrcmp(node.left,'null')&&strcmp(node.right,'null')%左右都为空flag=1;elseflag=0;endend6.id3_preprocess.mfunction[matrix,attributes,activeAttributes]=id3_preprocess()%%ID3算法数据预处理，把字符串转换为0,1编码%输出参数：%matrix：转换后的0,1矩阵；%attributes:属性和Label；%activeAttributes:属性向量，全1；%%读取数据txt={'序号''天气''是否周末''是否有促销''销量''''坏''是''是''高''''坏''是''是''高''''坏''是''是''高''''坏''否''是''高''''坏''是''是''高''''坏''否''是''高''''坏''是''否''高''''好''是''是''高''''好''是''否''高''''好''是''是''高''''好''是''是''高''''好''是''是''高''''好''是''是''高''''坏''是''是''低''''好''否''是''高''''好''否''是''高''''好''否''是''高''''好''否''是''高''''好''否''否''高''''坏''否''否''低''''坏''否''是''低''''坏''否''是''低''''坏''否''是''低''''坏''否''否''低''''坏''是''否''低''''好''否''是''低''''好''否''是''低''''坏''否''否''低''''坏''否''否''低''''好''否''否''低''''坏''是''否''低''''好''否''是''低''''好''否''否''低''''好''否''否''低'}attributes=txt(1,2:end);activeAttributes=ones(1,length(attributes)-1);data=txt(2:end,2:end);%%针对每列数据进行转换[rows,cols]=size(data);matrix=zeros(rows,cols);forj=1:colsmatrix(:,j)=cellfun(@trans2onezero,data(:,j));endendfunctionflag=trans2onezero(data)ifstrcmp(data,'坏')||strcmp(data,'否')...||strcmp(data,'低')flag=0;return;endflag=1;end7.ID3_decision_tree.m%%使用ID3决策树算法预测销量高低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算法构建决策树完成！');8.id3.mfunction[tree]=id3(examples,attributes,activeAttributes)%%ID3算法，构建ID3决策树...参考：输入参数：%example:输入0、1矩阵；%attributes:属性值，含有Label；%activeAttributes:活跃的属性值；-1,1向量，1表示活跃；%输出参数：%tree：构建的决策树；%%提供的数据为空，则报异常if(isempty(examples));error('必须提供数据！');end%常量numberAttributes=length(activeAttributes);numberExamples=length(examples(:,1));%创建树节点tree=struct('value','null','left','null','right','null');%如果最后一列全部为1，则返回“true”lastColumnSum=sum(examples(:,numberAttributes+1));if(lastColumnSum==numberExamples);tree.value='true';returnend%如果最后一列全部为0，则返回“false”if(lastColumnSum==0);tree.value='false';returnend%如果活跃的属性为空，则返回label最多的属性值if(sum(activeAttributes)==0);if(lastColumnSum=numberExamples/2);tree.value='true';elsetree.value='false';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;endendend%熵S(v=1)if(~s1);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;%熵S(v=0)if(~s0);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=