实验三 决策树算法实验
一、实验目的: 熟悉和掌握决策树的分类原理、实质和过程;掌握典型的学习算法 和实现技术。 二、实验原理: 决策树学习和分类. 三、实验条件: 四、实验内容:
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 Car Mortgage
Pep:以上五个条件,若为“是”标记为“1”,若为“否”标记为“2”。 Age sex region income married children car mortgage pep 1 2 1 1 2 1 1 2 2 1 2 1 1 2 2 2 2 1 2 1 4 2 1 1 1 2 1 1 2 1 2 1 2 2 1 1 2 1 3 2 1 2 2 2 1 2 1 2 2 2 1 1 1 1 3 2 1 1 1 1 1 1 3 3 1 2 3 2 3 3 2 2 3 1 3 3 2 1 3 2 1 3 1 1 1 2 1 1 1 2 1 1 2 1 2 1 1 1 2 1 2 1 1 2 2 2 2 1 2 2 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 2 2 1 2 3 1 1 3 1 2 3 1 1 3 1 2 3 1 1 3 1 2 2 2 1 2 2 2 2 2 2 2 1 1 1 1 2 1 2 1 1 2 1 2 2 2 2 1 1 2 1 1 2 1 2 2 2 1 1 2 2 1 2 1 1 2 1 2 2 1 1 2 1 1 1 2 2 2 1 1 2 2 1 1 1 1 1 2
3 1 3 3 1 2 2 2 2 3 2 4 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<1
error('请输入数据集'); else
if isstr(DataSet)
[DataSet AttributValue]=readdata2(DataSet); else
AttributValue=[]; end end
if nargin<2
AttributName=[]; end
Attributs=[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)/2
RulesMatrix(i,rule((j-1)*2+1))=rule(j*2); end
RulesMatrix(i,size(DataSet,2))=rule(length(rule)); end end
function 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; end end
Tree.Attribut=i; Tree.Child=[]; return; end
if(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; end
end
Tree.Attribut=mostlabel; Tree.Child=[]; return; end
for 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; end end
Tree.Child(j).root.Attribut=mostlabel;
Tree.Child(j).root.Child=[]; else
Tree.Child(j).root=CreatTree(DataSet2,Attributs2); end end end
function [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=[]; end
classnum(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]; end
Entropy=0;
for j=1:length(classnum)
P=classnum(j)/size(DataSet,1); if(P~=0)
Entropy=Entropy+(-P)*log2(P); end end
else
valnum=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=[]; %将编号保留下来,以方便后面按值分割数据集 end
if(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)); end
Value(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]; end
Entropy=0; for j=1:valnum Entropys=0;
for k=1:length(Value(j).classnum)
P=Value(j).classnum(k)/Valueexamnum(j); if(P~=0)
Entropys=Entropys+(-P)*log2(P); end end
Entropy=Entropy+(Valueexamnum(j)/size(DataSet,1))*Entropys; end end end
function showTree(Tree,level,value,branch,AttributValue,AttributName) blank=[];
for i=1:level-1
if(branch(i)==1)
blank=[blank ' |']; else
blank=[blank ' ']; end end
blank=[blank ' ']; if(level==0)
blank=[' (The Root):']; else
if isempty(AttributValue)
blank=[blank '|_____' int2str(value) '______']; else
blank=[blank '|_____' value '______']; end end
if(length(Tree.Child)~=0) %非叶子节点 if isempty(AttributName)
disp([blank 'Attribut ' int2str(Tree.Attribut)]);
else
disp([blank 'Attribut ' AttributName{Tree.Attribut}]); end
if isempty(AttributValue)
for j=1:length(Tree.Child)-1
showTree(Tree.Child(j).root,level+1,j,[branch 1],AttributValue,AttributName); end
showTree(Tree.Child(length(Tree.Child)).root,level+1,length(Tree.Child),[branch(1:length(branch)-1) 0 1],AttributValue,AttributName); else
for j=1:length(Tree.Child)-1
showTree(Tree.Child(j).root,level+1,AttributValue{Tree.Attribut}{j},[branch 1],AttributValue,AttributName); end
showTree(Tree.Child(length(Tree.Child)).root,level+1,AttributValue{Tree.Attribut}{length(Tree.Child)},[branch(1:length(branch)-1) 1],AttributValue,AttributName); end else
if isempty(AttributValue)
disp([blank 'leaf ' int2str(Tree.Attribut)]); else
disp([blank 'leaf ' AttributValue{length(AttributValue)}{Tree.Attribut}]); end end end
function Rules=getRule(Tree)
if(length(Tree.Child)~=0) Rules={};
0
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]}; end
Rules=[Rules;content]; end else
Rules={['C' num2str(Tree.Attribut)]}; end end
因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- sceh.cn 版权所有 湘ICP备2023017654号-4
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务