實(shí)驗(yàn)三-決策樹(shù)算法實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告.doc

實(shí)驗(yàn)三 決策樹(shù)算法實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康模?熟悉和掌握決策樹(shù)的分類原理、實(shí)質(zhì)和過(guò)程；掌握典型的學(xué)習(xí)算法 和實(shí)現(xiàn)技術(shù)。二、實(shí)驗(yàn)原理: 決策樹(shù)學(xué)習(xí)和分類. 三、實(shí)驗(yàn)條件：四、實(shí)驗(yàn)內(nèi)容：1 根據(jù)現(xiàn)實(shí)生活中的原型自己創(chuàng)建一個(gè)簡(jiǎn)單的決策樹(shù)。2 要求用這個(gè)決策樹(shù)能解決實(shí)際分類決策問(wèn)題。五、實(shí)驗(yàn)步驟：1、驗(yàn)證性實(shí)驗(yàn)：（1）算法偽代碼 算法Decision_Tree(data,AttributeName) 輸入由離散值屬性描述的訓(xùn)練樣本集data; 候選屬性集合AttributeName。 輸出一棵決策樹(shù)。 （1） 創(chuàng)建節(jié)點(diǎn)N； （2） If samples 都在同一類C中then （3） 返回N作為葉節(jié)點(diǎn)，以類C標(biāo)記； （4） If attribute_list為空then （5） 返回N作為葉節(jié)點(diǎn)，以samples 中最普遍的類標(biāo)記；/多數(shù)表決 （6） 選擇attribute_list 中具有最高信息增益的屬性test_attribute; （7） 以test_attribute 標(biāo)記節(jié)點(diǎn)N； （8） For each test_attribute 的已知值v /劃分 samples ；（9） 由節(jié)點(diǎn)N分出一個(gè)對(duì)應(yīng)test_attribute=v的分支； （10令Sv為 samples中 test_attribute=v 的樣本集合；/一個(gè)劃分塊 （11）If Sv為空 then （12）加上一個(gè)葉節(jié)點(diǎn)，以samples中最普遍的類標(biāo)記； （13）Else 加入一個(gè)由Decision_Tree(Sv,attribute_list-test_attribute)返回節(jié)點(diǎn)值。（2）實(shí)驗(yàn)數(shù)據(jù)預(yù)處理Age:30歲以下標(biāo)記為“1”；30歲以上50歲以下標(biāo)記為“2”；50歲以上標(biāo)記為“3”。Sex：FEMAL-“1”；MALE-“2”Region：INNERCITY-“1”；TOWN-“2”；RURAL-“3”；SUBURBAN-“4”Income：50002萬(wàn)-“1”；2萬(wàn)4萬(wàn)-“2”；4萬(wàn)以上-“3”MarriedChildrenCarMortgagePep：以上五個(gè)條件，若為“是”標(biāo)記為“1”，若為“否”標(biāo)記為“2”。Age sex region income married children car mortgage pep 1 2 1 1 2 1 1 2 21 2 1 1 2 2 2 2 12 1 4 1 2 1 2 2 1 2 1 1 1 1 2 2 2 21 2 1 1 1 2 2 2 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 1 2 2 1 1 1 2 1 1 2 1 2 1 3 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 1 1 1 3 2 2 2 1 2 1 3 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 2 4 3 1 2 2 1 1 3 1 3 3 2 2 1 1 2（3）Matlab語(yǔ)句：Tree RulesMatrix= DecisionTree(DataSet, AttributName)；六、實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)程序：function Tree RulesMatrix=DecisionTree(DataSet,AttributName)%輸入為訓(xùn)練集，為離散后的數(shù)字，如記錄1：1 1 3 2 1；%前面為屬性列，最后一列為類標(biāo)if nargin1 error(請(qǐng)輸入數(shù)據(jù)集);else if isstr(DataSet) DataSet AttributValue=readdata2(DataSet); else AttributValue=; endendif narginmostlabelnum) 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 endfunction Entropy RecordVal=ComputEntropy(DataSet,attribut) %計(jì)算信息熵 if(attribut=0) clnum=0; for i=1:size(DataSet,1) if(DataSet(i,size(DataSet,2)clnum) %防止下標(biāo)越界 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) %防止參數(shù)下標(biāo)越界 clnum(DataSet(i,attribut)=0; valnum=DataSet(i,attribut); Valueexamnum(DataSet(i,attribut)=0; RecordVal(DataSet(i,attribut).matrix=; %將編號(hào)保留下來(lái)，以方便后面按值分割數(shù)據(jù)集 end if(DataSet(i,size(DataSet,2)clnum(DataSet(i,attribut) %防止下標(biāo)越界 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 endendfunction 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) %非葉子節(jié)點(diǎn) if isempty(AttributName) disp(blank Attribut int2str(Tree.Attribut); else disp(blank Attribut AttributNameTree.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,AttributValueTree.Attributj,branch 1,AttributValue,AttributName); end showTree(Tree.Child(length(Tree.Child).root,level+1,AttributValueTree.Attributlength(Tree.Child),branch(1:length(branch)-1) 0 1,AttributValue,AttributName); end else if isempty(AttributValue) disp(blank leaf int2str(Tree.Attribut); else disp(blank leaf AttributValuelength(AttributValue)Tree.Attribut); end end endfunction Rules=getRule(Tree) if(length(Tree.Child)=0) Rules=; for i=1:length(Tree.Child) content=