機(jī)器學(xué)習(xí)決策樹ID3算法的源代碼

1、機(jī)器學(xué)習(xí)決策樹ID3算法的源代碼上（VC6.0測試通過）發(fā)布：2009-4-1611:42|作者：天涯|來源：資訊i=s本帖最后由天涯于2009-4-1713:03編輯這個(gè)的重要，不用多說了吧，有什么意見和建議跟帖留言啊，哈，覺得好，請頂一個(gè)第一部分：#include<iostream.h>#include<fstream.h>#include<string.h>#include<stdlib.h>#include<math.h>#include<iomanip.h># defineN500/N定義為給定訓(xùn)練數(shù)據(jù)的估計(jì)個(gè)數(shù)

2、# defineM6/M定義為候選屬性的個(gè)數(shù)# definec2/定義c=2個(gè)不同類# defines_max5/定義s_max為每個(gè)候選屬性所劃分的含有最大的子集數(shù)intavM=3,3,2,3,4,2;intsNM+2,aNM+2;/數(shù)組sj用來記錄第i個(gè)訓(xùn)練樣本的第j個(gè)屬性值intpath_aNM+1,path_bNM+1;/用path_aNM+1,path_bNM+1記錄每一片葉子的路徑intcount_list=M;/count_list用于記錄候選屬性個(gè)數(shù)intcount=-1;/用count+1記錄訓(xùn)練樣本數(shù)intattribute_test_list1M;intleaves=1;

3、用數(shù)組sskj表示第k個(gè)候選屬性劃分的子集Sj中類Ci的樣本數(shù)，數(shù)組的具體大小可根據(jù)給定訓(xùn)練數(shù)據(jù)調(diào)整intssMcs_max;第k個(gè)候選屬性劃分的子集Sj中樣本屬于類Ci的概率doublepMcs_max;/count_sj用來記錄第i個(gè)候選屬性的第j個(gè)子集中樣本個(gè)數(shù)intcount_sMs_max;/分別定義EM,GainM表示嫡和嫡的期望壓縮doubleEM;doubleGainM;/變量max_Gain用來存儲最大的信息增益doublemax_Gain;intTrip=-1;/用Trip記錄每一個(gè)葉子遞歸次數(shù)intmost;voidmain(void)inti,j=-1,k,temp,l

4、,count_test,true_class=0,count_train;chartrainname256,testname256;inttestN8;cout<<"請輸入訓(xùn)練集文件名："；cin>>trainname;ifstreamtrainfile;trainfile.open(trainname,ios:in|ios:nocreate);if(!trainfile)cout<<"無法使用訓(xùn)練集，請重試！"<<'n'exit(1);/讀取訓(xùn)練集while(trainfile>&g

5、t;temp)j=j+1;k=j%(M+2);if(k=0|j=0)count+=1;/count為訓(xùn)練集的第幾個(gè)，k代表室第幾個(gè)屬性switch(k)case0:scount0=temp;case1:scount1=temp;break;case2:scount2=temp;break;case3:scount3=temp;break;case4:scount4=temp;break;case5:scount5=temp;break;case6:scount6=temp;break;case7:scount7=temp;break;trainfile.close();/輸出訓(xùn)練集for(i=

6、0;i<=count;i+)if(i%2=0)cout<<'n'for(j=0;j<M+2;j+)cout<<setw(4)<<sj;/most記錄訓(xùn)練集中哪類樣本數(shù)比較多，以用于確定遞歸終止時(shí)不確定的類別for(i=0,j=0,k=0;i<=count;i+)if(s0=0)j+=1;elsek+=1;if(j>k)most=0;elsemost=1;/count_train記錄訓(xùn)練集的樣本數(shù)count_train=count+1;/訓(xùn)練的屬性for(i=0;i<M;i+)attribute_test_list

7、1=i+1;/首次調(diào)用遞歸函數(shù)，即是生成根結(jié)點(diǎn)的分支Generate_decision_tree(s,count+1,attribute_test_list1,count_list,0,0);cout<<'n'<<"葉子結(jié)點(diǎn)的個(gè)數(shù)為："<<leaves<<'n'cout<<"請輸入測試集文件名："；cin>>testname;ifstreamtestfile;testfile.open(testname,ios:in|ios:nocreate);if(

8、!testfile)cout<<"無法使用訓(xùn)練集，請重試！"<<'n'exit(1);count_test=0;j=-1;/讀取測試集數(shù)據(jù)while(testfile>>temp)j=j+1;k=j%(M+2);if(k=0)count_test+=1;switch(k)case0:testcount_test7=temp;break;case1:testcount_test1=temp;break;case2:testcount_test2=temp;break;case3:testcount_test3=temp;br

9、eak;case4:testcount_test4=temp;break;case5:testcount_test5=temp;break;case6:testcount_test6=temp;break;testfile.close();for(i=1;i<=count_test;i+)test0=0;/以確保評估分類準(zhǔn)確率cout<<"count_test="<<count_test<<'n'cout<<"count_train="<<count_train<&l

10、t;'n'/用測試集來評估分類準(zhǔn)確率for(i=1;i<=count_test;i+)l=0;for(j=1;j<=leaves;j+)if(testpath_bj1=path_aj1&&testpath_bj2=path_aj2&&testpath_bj3=path_aj3&&testpath_bj4=path_aj4&&testpath_bj5=path_aj5&&testpath_bj6=path_aj6)l=1;if(test7=path_aj0)true_class+=1;br

11、eak;if(test7=most&&l=0)true_class+=1;cout<<"測試集與訓(xùn)練集的比例為："<<float(count_train)/count_test<<'n'cout<<"分類準(zhǔn)確率為:"<<float(true_class)/count_test<<'n'第二部分:voidGenerate_decision_tree(intbM+2,intbn,intattribute_test_list,intsn,in

12、tai,intaj)(/定義數(shù)組a記錄目前待分的訓(xùn)練樣本集，定義數(shù)組b記錄目前要分結(jié)點(diǎn)中所含的訓(xùn)練樣本集/same_class用來記數(shù)，判另Usamples是否都屬于同一個(gè)類Trip+=1;/用Trip記錄每一個(gè)葉子遞歸次數(shù)path_aleavesTrip=ai;/用path_aNM+1,path_bNM+1記錄每一片葉子的路徑path_bleavesTrip=aj;intsame_class,i,j,k,l,ll,lll;if(bn=0)/待分結(jié)點(diǎn)的樣本集為空時(shí)，加上一個(gè)樹葉，標(biāo)記為訓(xùn)練集中最普通的類/記錄路徑與前一路徑相同的部分for(i=1;i<Trip;i+)if(path_al

13、eavesi=0)path_aleavesi=path_aleaves-1i;path_bleavesi=path_bleaves-1i;cout<<'n'<<"IF"for(i=1;i<=Trip;i+)if(i=1)cout<<"a"<<path_bleavesi<<"="<<path_aleavesi;elsecout<<"Aa"<<path_bleavesi<<"=&q

14、uot;<<path_aleavesi;cout<<"THENclass="<<most;path_aleaves0=most;/修改樹的深度if(path_aleavesTrip=avpath_bleavesTrip-1)for(i=Trip;i>1;i-)if(path_aleavesi=avpath_bleavesi-1)Trip-=1;elsebreak;Trip-=1;leaves+=1;elsesame_class=1;for(i=0;i<bn-1;i+)if(bi0=bi+10)same_class+=1;if(

15、same_class=bn)/待分樣本集屬于同一類時(shí)以該類標(biāo)記/記錄路徑與前一路徑相同的部分for(i=1;i<Trip;i+)if(path_aleavesi=0)path_aleavesi=path_aleaves-1i;path_bleavesi=path_bleaves-1i;cout<<'n'<<"IF"for(i=1;i<=Trip;i+)if(i=1)cout<<"a"<<path_bleavesi<<"="<<path_

16、aleavesi;elsecout<<"Aa"<<path_bleavesi<<"="<<path_aleavesi;cout<<"THENclass="<<b00;path_aleaves0=b00;/修改樹的深度if(path_aleavesTrip=avpath_bleavesTrip-1)for(i=Trip;i>1;i-)if(path_aleavesi=avpath_bleavesi-1)Trip-=1;elsebreak;Trip-=1;lea

17、ves+=1;/未分類的樣本集減少for(i=0,l=-1;i<=count;i+)for(j=0,lll=0;j<bn;j+)if(siM+1=bjM+1)lll+;if(lll=0)l+=1;for(ll=0;ll<M+2;ll+)alll=sill;k+;for(ll=0;ll<M+2;ll+)skll=aill;)count=count-bn;)elseif(sn=0)/候選屬性集為空時(shí)，標(biāo)記為訓(xùn)練集中最普通的類/記錄路徑與前一路徑相同的部分for(i=1;i<Trip;i+)if(path_aleavesi=0)path_aleavesi=path_al

18、eaves-1i;path_bleavesi=path_bleaves-1i;)cout<<'n'<<"IF"for(i=1;i<=Trip;i+)if(i=1)cout<<"a"<<path_bleavesi<<"="<<path_aleavesi;elsecout<<"Aa"<<path_bleavesi<<"="<<path_aleavesi;/判斷

19、類別for(i=0,ll=0,lll=0;i<bn;i+)if(bi0=0)ll+=1;elselll+=1;)if(ll>lll)cout<<"THENclass=0"path_aleaves0=0;)elsecout<<"THENclass=1"path_aleaves0=1;)/修改樹的深度if(path_aleavesTrip=avpath_bleavesTrip-1)for(i=Trip;i>1;i-)if(path_aleavesi=avpath_bleavesi-1)Trip-=1;elsebrea

20、k;Trip-=1;leaves+=1;/未分類的樣本集減少for(i=0,l=-1;i<=count;i+)for(j=0,lll=0;j<bn;j+)if(siM+1=bjM+1)III+;if(lll=O)l+=1;for(ll=0;IKM+2;ll+)al"=siH；)for(i=0,k=-1;i<l;i+)k+;for(ll=0;IKM+2;ll+)skll=aill;)count=count-bn;)else/待分結(jié)點(diǎn)的樣本集不為空時(shí)(/定義count_Positive記錄屬于正例的樣本數(shù)intcount_Positive=0;/p1,p2分別定義為正負(fù)

21、例的比例doublep1,p2;doubleEntropy_Es;/Entropy_Es表示嫡for(i=0;i<=count;i+)if(siO=1)count_Positive+=1;p1=double(count_Positive)/(count+1);p2=1-p1;Entropy_Es=-p1*log10(p1)/log10(2)-p2*log10(p2)/log10(2);cout«p1«'t,<<p2«'t'«Entropy_Es«'n'天涯(2009-4-1611:43:

22、32)繼續(xù):/初始化for(i=0;i<sn;i+)/當(dāng)前的屬性包含的個(gè)數(shù)for(j=0;j<c;j+)/類別for(k=0;k<avi;k+)/以當(dāng)前屬性分成的小類(每個(gè)屬性包含的種類數(shù))ssattribute_test_listi-1jk=0;/用數(shù)組sskij表示第k個(gè)候選屬性劃分的子集Sj中類Ci的樣本數(shù)，數(shù)組的具體大小可根據(jù)給定訓(xùn)練數(shù)據(jù)調(diào)整for(i=0;i<sn;i+)for(j=0;j<avi;j+)count_sattribute_test_listi-1j=0;/初始化某個(gè)屬性的某個(gè)具體值的全部個(gè)數(shù)for(i=0;i<count+1;i+)

23、for(j=1;j<=sn;j+)if(si0=0)/找出每個(gè)屬性具體某個(gè)值屬于反例的個(gè)數(shù)ssattribute_test_listj-1-10sij-1+=1;count_sattribute_test_listj-1-1sij-1+=1;elsessattribute_test_listj-1-11sij-1+=1;count_sattribute_test_listj-1-1sij-1+=1;/計(jì)算分別以各個(gè)候選屬性劃分樣本后，各個(gè)子集Sj中的樣本屬于類Ci的概率for(i=0;i<sn;i+)for(j=0;j<c;j+)for(k=0;k<avi;k+)if(

24、count_sattribute_test_listi-1k!=0)pattribute_test_listi-1jk=double(ssattribute_test_listi-1jk)/count_sattribute_test_listi-1k;for(i=0;i<sn;i+)Eattribute_test_listi-1=0.0;/計(jì)算嫡for(j=0;j<avattribute_test_listi-1;j+)/if語句處理0*log10(0)=0if(pattribute_test_listi-10j=0|pattribute_test_listi-11j=0)pattribute_test_listi-10j=1;pattribute_test_listi-11j=1;Eattribute_test_listi-1+=(ssattribute_test_listi-10j+ssattribute_test_listi-11j)*(-(pattribute_test_listi-10j*10g10(pattribute_test_listi-10j)/10g10(2)+pattribute_test_listi-11j*10g10(pattribute_test_listi-11j)/10g10(2)/(count+1);