實驗三決策樹算法實驗實驗報告

1、實驗三 決策樹算法實驗一、實驗?zāi)康模?熟悉和掌握決策樹的分類原理、實質(zhì)和過程；掌握典型的學(xué)習(xí)算法 和實現(xiàn)技術(shù)。二、實驗原理: 決策樹學(xué)習(xí)和分類. 三、實驗條件：四、實驗內(nèi)容：1 根據(jù)現(xiàn)實生活中的原型自己創(chuàng)建一個簡單的決策樹。2 要求用這個決策樹能解決實際分類決策問題。五、實驗步驟：1、驗證性實驗：（1）算法偽代碼 算法Decision_Tree(data,AttributeName) 輸入由離散值屬性描述的訓(xùn)練樣本集data; 候選屬性集合AttributeName。 輸出一棵決策樹。 （1） 創(chuàng)建節(jié)點N； （2） If samples 都在同一類C中then （3） 返回N作為葉節(jié)點，以類C

2、標記； （4） If attribute_list為空then （5） 返回N作為葉節(jié)點，以samples 中最普遍的類標記；/多數(shù)表決 （6） 選擇attribute_list 中具有最高信息增益的屬性test_attribute; （7） 以test_attribute 標記節(jié)點N； （8） For each test_attribute 的已知值v /劃分 samples ；（9） 由節(jié)點N分出一個對應(yīng)test_attribute=v的分支； （10令Sv為 samples中 test_attribute=v 的樣本集合；/一個劃分塊 （11）If Sv為空 then （12）加上一個葉

3、節(jié)點，以samples中最普遍的類標記； （13）Else 加入一個由Decision_Tree(Sv,attribute_list-test_attribute)返回節(jié)點值。（2）實驗數(shù)據(jù)預(yù)處理Age:30歲以下標記為“1”；30歲以上50歲以下標記為“2”；50歲以上標記為“3”。Sex：FEMAL-“1”；MALE-“2”Region：INNERCITY-“1”；TOWN-“2”；RURAL-“3”；SUBURBAN-“4”Income：50002萬-“1”；2萬4萬-“2”；4萬以上-“3”MarriedChildrenCarMortgagePep：以上五個條件，若為“是”標記為“1”

4、，若為“否”標記為“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

5、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語句：Tree RulesMatrix= DecisionTree(DataSe

6、t, AttributName)；六、實驗結(jié)果：實驗程序：function Tree RulesMatrix=DecisionTree(DataSet,AttributName)%輸入為訓(xùn)練集，為離散后的數(shù)字，如記錄1：1 1 3 2 1；%前面為屬性列，最后一列為類標if nargin1 error(請輸入數(shù)據(jù)集);else if isstr(DataSet) DataSet AttributValue=readdata2(DataSet); else AttributValue=; endendif narginmostlabelnum) mostlabelnum=length(ValRe

7、cords(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:ma

8、xindex-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:

9、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=ComputEntrop

10、y(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(Dat

11、aSet,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ù)下標越界 clnu

12、m(DataSet(i,attribut)=0; valnum=DataSet(i,attribut); Valueexamnum(DataSet(i,attribut)=0; RecordVal(DataSet(i,attribut).matrix=; %將編號保留下來，以方便后面按值分割數(shù)據(jù)集 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,attr

13、ibut)=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).

14、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,A

15、ttributName) 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é)點 if isempty(AttributName) d

16、isp(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.C

17、hild),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.Chil

18、d),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(Tre

19、e.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 e

20、nd附錄資料:不需要的可以自行刪除c語言典型問題處理方法小結(jié)循環(huán)問題（1）、數(shù)論問題1、求素數(shù) for(i=2;i1，如果它僅有平凡約數(shù)1和a，則我們稱a為素數(shù)(或質(zhì)數(shù))。整數(shù) 1 被稱為基數(shù)，它既不是質(zhì)數(shù)也不是合數(shù)。整數(shù) 0 和所有負整數(shù)既不是素數(shù)，也不是合數(shù)。 2、求最大公約數(shù)和最小公倍數(shù)a、 if(ab) t=a; a=b; b=t; for(i=a;i=1;i-) if(a%i=0&b%i=0) break; printf(largest common divisor:%dn,i); printf(least common multiple:%dn,(a*b)/is);b、輾轉(zhuǎn)相除法求

21、解 a1=a; b1=b; while(a%b!=0) t=a%b; a=b; b=t; printf(largest common divisor:%dnleast common multiple:%d,b,a1*b1/b);3、求完數(shù) 一個數(shù)如果恰好等于它的因子之和，這個數(shù)就稱為“完數(shù)”。 例如：6的因子為1、2、3，而6123，因此6是“完數(shù)”。for(a=1;a=1000;a+) s=0; for(i=1;i=a) break; if(s=a) printf(%dt,a);注意S=0所放的位置 4、分解質(zhì)因數(shù) 將一個整數(shù)寫成幾個質(zhì)因數(shù)的連乘積，如： 輸入36，則程序輸出36=2*2*3

22、*3 。解一、看似簡單，但要自己完整地寫出來還真不容易！竟然還動用了goto語句，正好可以熟悉一下goto語句的用法！main() int a,z,i; clrscr(); scanf(%d,&a);判斷下一個數(shù)開始有要重新從2開始了。所以用loop語句回到for語句，這是for語句仍從2初始化。從2開始的原則不變，變的是a的值。 loop: for(z=2;z=a;z+)判斷是否為質(zhì)數(shù)for(i=2;i=z;i+) if(z%i=0) break;判斷是否為a的質(zhì)因數(shù) if(z=i) if(a%z=0) k+; if(k=1) printf(%d=%d,a1,z);用計數(shù)器來解決每行輸入不同

23、的問題。 else printf(*%d,z); a/=z; goto loop; 解二：main() int n, k=2, isfirst=1; printf(Input n=); scanf(%d,&n); while(k=n) if(n%k=0) if(isfirst) printf(%d=%d, n, k); isfirst=0; else printf(*%d,k); n/=k; else k+; printf(n);5、從鍵盤輸入兩個整數(shù)，輸出這兩個整數(shù)的商的小數(shù)點后所有1000位整數(shù) for(i=1;i=2;i-) if(fm%i=0&fz%i=0) fz/=i; fm/=i;

24、 z=fz/fm; fzx=fz%fm; if(fzx=0) printf(%d%d/%d-%d%d/%d=%dn,z1,fz1,fm1,z2,fz2,fm2,z); else if(z=0) printf(%d%d/%d-%d%d/%d=%d/%dn,z1,fz1,fm1,z2,fz2,fm2,fzx,fm); else printf(%d%d/%d-%d%d/%d=%d%d/%dn,z1,fz1,fm1,z2,fz2,fm2,z,fzx,fm);（2）近似問題1、書P122習(xí)題4-6注意千萬不要忘記添加#include “math.h”#include math.hmain() float

25、 x,j=1,k,s,so; int n; scanf(%f,&x); s=x; so=x+1; for(n=1;fabs(s-so)1e-6;n+) for(k=1;k1e-6) x=(x1+x2)/2; f=x*x*x+4*x*x-10;可以用/*if(f*f10) x2=x; else x1=x; printf(%fn,x);（3）枚舉法（4）數(shù)列問題二、數(shù)組問題（1）排序問題1、從小到大排序main() int a10,i,j,t; for(i=0;i10;i+) scanf(%d,&ai); for(i=1;i10;i+) for(j=0;jaj+1) t=aj+1;aj+1=aj;

26、aj=t; for(i=0;i10;i+) printf(%d ,ai); printf(n);注意排序問題：1、須迅速，熟練，無差錯經(jīng)常插入在程序中間2、現(xiàn)使用最大數(shù)下沉冒泡法還可以使用最小數(shù)上浮冒泡法3、j控制前面一個數(shù)和后面一個數(shù)一一比較。由于是最大數(shù)下沉，i+1后j仍要從0開始。4、i控制這樣的操作一共要做多少次5、注意i j的控制次數(shù)2、從大到小排序main()現(xiàn)使用最大數(shù)上浮冒泡法還可使用最小數(shù)下沉冒泡法 int a10,i,j,t; for(i=0;i10;i+) scanf(%d,&ai); for(i=1;i=i;j-) if(ajaj-1) t=aj-1; aj-1=aj;

27、 aj=t; for(i=0;i10;i+) printf(%d ,ai);（2）二維數(shù)組三、字符或字符串輸入輸出問題（1）字符打印1、打印*此類題的溯源為書P122 4.11（1），其他題都是它的拓展 for (i=1;i=n;i+) 一共要輸出的行數(shù) for(j=1;j=i;j+) 每行要打印的*數(shù) printf(*); printf(n); a、*解題要點：此類題關(guān)鍵在于找到每行要打印的個數(shù)和行數(shù)的關(guān)系。此題j=i j=n-i+1b、* for(i=1;i=n;i+) 一共要輸出的行數(shù) for(j=1;j=n-i;j+) 控制空格數(shù) printf( ); for(k=1;k=i;k+)

28、每行要打印的*數(shù) printf(*); printf(n); c、 * * *解題要點：在出現(xiàn)空格的時候，在找到每行要打印的*個數(shù)和行數(shù)的關(guān)系后，還應(yīng)找到空格和行數(shù)的關(guān)系，分不同的參數(shù)進行循環(huán)。此題k=i j=n-i j=i-1k=n-i+1d、* * for(i=1;i=n;i+) for(j=1;j=n-i;j+) printf( ); for(k=1;k=2*i-1;k+) printf(*); printf(n); * *e、 * * * for(i=1;i=n-1;i+) for(j=1;j=i;j+) printf( ); for(k=1;k=2*(n-1-i)+1;k+) pri

29、ntf(*); printf(n); for(i=1;i=n;i+) for(j=1;j=n-i;j+) printf( ); for(k=1;k=2*i-1;k+) printf(*); printf(n); * * * * * *2、打印9*9乘法表解題要點：注意尋找行與列的規(guī)律。i*ji代表列j代表行for(i=1;i=9;i+) for(j=1;j=9;j+) printf(%-3d ,i*j); 注意輸出格式的控制 printf(n); 3、九九乘法表1 2 3 4 5 6 7 8 92 4 6 8 10 12 14 16 183 6 9 12 15 18 21 24 27 9 18

30、 27 36 45 54 63 72 814、楊暉三角形11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1（2）字符串打印問題for(i=1;i=7;i+) ai1=1; aii=1; for(i=3;i=7;i+) for(j=2;j=i-1;j+) aij=ai-1j-1+ai-1j; gets(a); puts(a); for(i=1;i0;j-) aj=aj-1; a0=t; for(k=0;k=a&ai=z) ai-=32; puts (a);3、逆序輸出gets (a); c=strlen(a); for(i=0;i=0;i

31、-) 藍色部分可以簡寫為綠色部分coutai-1;4、如輸入：ab1 3,;z 輸出：ab1注意點：1、= =2、while語句的使用處體會3、全面考慮問題 3,;zgets(a); while(a0= ) for(i=0;ai!=0;i+) ai=ai+1; for(i=0;ai!=0;i+)if(ai= &ai+1!= ) printf(n); else if(ai= &ai+1= ) for(k=i;ak!=0;k+) ak+1=ak+2; i-; elseprintf(%c,ai);5、輸入3個字符串，按從小到大排序輸出這3個字符串。 使用一個兩維數(shù)組貯存多個字符串char a8181

32、;注意：如何使用一個兩維數(shù)組貯存多個字符串 int i,j; for(i=0;i3;i+) gets(ai); for(i=0;i3;i+) puts(ai);注意：1、scanf(%d%s,&n,str) 其中%s為字符串格式2、逐個給字符串賦值的方法見書140頁。 不可for（i=0；ai!=0;i+）3、stri=stri-A+10;4、pow函數(shù)5、任何進制轉(zhuǎn)為十進制的方法6、輸入一個整數(shù)n和一個字符串str，計算并輸出n進制數(shù)str的值。 如輸入：7 16則輸出：13(16)7=(13)10如輸入：16 3A則輸出：58(3A)16=(58)10#include stdio.h#in

33、clude math.hmain() char str81; int n,i,s=0,t; clrscr(); scanf(%d%s,&n,str); for(i=0;stri!=0;i+) if(stri=A) stri=stri-A+10; else stri=stri-0; t=strlen(str); for(i=0;stri!=0;i+) s+=strt-i-1*pow(n,i); printf(%d,s);編寫程序，將一個十進制正整數(shù)轉(zhuǎn)換成十六進制數(shù)。 注意類比#include main()char a20;int x,i=0,j;clrscr();scanf(%d,&x);whi

34、le(x) if(x%16=10&x%16=0;j-)printf(%c,aj);printf(n);7、輸入一個字符串，將其中的縮寫形式展開，并輸出展開后的該字符串。所謂展開縮寫形式就是將其中由大小寫字母或數(shù)字構(gòu)成的形如a-f、U-Z、3-8 的形式展開成為 abcdef 、UVWXYZ 、345678，若出現(xiàn)f-a、A-7、9-5等形式則不予理睬。例如： 輸入：qwe246e-hA-d$-%4-7A-Dz-xp-R4-0輸出：qwr246efghA-d$-%4567ABCDz-xp-R4-0main() char a81; int i,c,s,k,t; gets(a); for(i=0;a

35、i!=0;i+) if(ai=-) if(ai-1=A&ai+1=a&ai+1=0&ai+1i;k-)ak+c-2=ak;as-1+c-2+1=0; for(;i=t;i+) ai=ai-1+1; puts(a);補充：循環(huán)：求：a+aa+aaa+.的值#includevoid main()int a,n,i=1,sn=0,tn=0;coutinput a and nan;while(i=n)tn=tn+a;sn+=tn;a*=10;i+;coutthe answer is snendl;兩個乒乓球隊進行比賽，各出3人。甲隊為A,B,C;已對是X,Y,Z；已經(jīng)抽簽決定比賽名單。有人向隊員大廳比

36、賽的名單。A說他不和X比，C說他不和X,Z比。請編程序找出3對賽手的名單。#includevoid main()char i,j,k;for(i=X;i=Z;i+)for(j=X;j=Z;j+)if(i!=j)for (k=X;k=Z;k+)if(i!=k&j!=k)if(i!=X&k!=X&k!=Z)coutA-i B-j C-kendl;枚舉口袋中有紅，黃，藍，白，黑5種顏色的球若干。每次從口袋中任意取出3歌，問得到3種不同顏色球的可能取法，輸出每種排列的情況。#include#include /在C語言中不用加這句void main()enum colorred ,yellow ,blu

37、e,white, black;color pri;int i,j,k,n=0,loop;for(i=red;i=black;i+)for(j=red;j=black;j+)if(i!=j)for (k=red;k=black;k+)if(k!=i)&(k!=j)n+;coutsetw(3)n; /setw是輸出格式的限定for(loop=1;loop=3;loop+)switch(loop)case 1:pri=color(i);break;case 2:pri=color(j);break;case 3:pri=color(k);break;default:break;switch(pri)

38、case red:coutsetw(8)red;break;case yellow:coutsetw(8)yellow;break;case blue:coutsetw(8)blue;break;case white:coutsetw(8)white;break;case black:coutsetw(8)black;break;default:break;coutendl;couttotal:nendl;數(shù)組：不用strcat函數(shù),編寫程序，將兩個字符串串接起來。#includeusing namespace std;void main()int i=0;char a20,b10;gets(a);gets(b);for(i=0;i1