机器学习实验报告(DOC)

《机器学习》课内实验报告（1）ID算法实现决策树2015-2016学年第2学期专业：智能科学与技术班级：智能1301班学号：06133029姓名：张争辉一、实验目的：理解ID3算法的基本原理，并且编程实现。二、实验要求：使用C/C++/MATLAB实现ID3算法。输入：若干行，每行5个字符串，表示OutlookTemperatureHumidityWindPlayball如上表。输出：决策树。实验结果如下：输入：SunnyHotHighWeakNoSunnyHotHighStrongNoOvercastHotHighWeakYesRainMildHighWeakYesRainCoolNormalWeakYesRainCoolNormalStrongNoOvercastCoolNormalStrongYesSunnyMildHighWeakNoSunnyCoolNormalWeakYesRainMildNormalWeakYesSunnyMildNormalStrongYesOvercastMildHighStrongYesOvercastHotNormalWeakYesRainMildHighStrongNo输出：OutlookRainWindStrongNoWeakYesOvercastYesSunnyHumidityNormalYesHighNo三、具体实现：实现算法如下：#includeiostream#includefstream#includemath.h#includestringusingnamespacestd;#defineROW14#defineCOL5#definelog20.69314718055typedefstructTNode{chardata[15];charweight[15];TNode*firstchild,*nextsibling;}*tree;typedefstructLNode{charOutLook[15];charTemperature[15];charHumidity[15];charWind[15];charPlayTennis[5];LNode*next;}*link;typedefstructAttrNode{charattributes[15];//属性intattr_Num;//属性的个数AttrNode*next;}*Attributes;char*Examples[ROW][COL]={//OverCast,Cool,High,Strong,No,//Rain,Hot,Normal,Strong,Yes,Sunny,Hot,High,Weak,No,Sunny,Hot,High,Strong,No,OverCast,Hot,High,Weak,Yes,Rain,Mild,High,Weak,Yes,Rain,Cool,Normal,Weak,Yes,Rain,Cool,Normal,Strong,No,OverCast,Cool,Normal,Strong,Yes,Sunny,Mild,High,Weak,No,Sunny,Cool,Normal,Weak,Yes,Rain,Mild,Normal,Weak,Yes,Sunny,Mild,Normal,Strong,Yes,OverCast,Mild,Normal,Strong,Yes,OverCast,Hot,Normal,Weak,Yes,Rain,Mild,High,Strong,No};char*Attributes_kind[4]={OutLook,Temperature,Humidity,Wind};intAttr_kind[4]={3,3,2,2};char*OutLook_kind[3]={Sunny,OverCast,Rain};char*Temperature_kind[3]={Hot,Mild,Cool};char*Humidity_kind[2]={High,Normal};char*Wind_kind[2]={Weak,Strong};/*inti_Exampple[14][5]={0,0,0,0,1,0,0,0,1,1,1,0,0,1,0,2,1,0,0,0,2,2,1,0,0,2,2,1,1,1,1,2,1,1,0,0,1,0,0,1,0,2,1,0,0,2,1,1,0,0,0,1,1,1,0,1,1,1,1,0,1,1,1,0,0,2,1,0,0,1};*/voidtreelists(treeT);voidInitAttr(Attributes&attr_link,char*Attributes_kind[],intAttr_kind[]);voidInitLink(link&L,char*Examples[][COL]);voidID3(tree&T,linkL,linkTarget_Attr,Attributesattr);voidPN_Num(linkL,int&positve,int&negative);doubleGain(intpositive,intnegative,char*atrribute,linkL,Attributesattr_L);voidmain(){linkLL,p;Attributesattr_L,q;treeT;T=newTNode;T-firstchild=T-nextsibling=NULL;strcpy(T-weight,);strcpy(T-data,);attr_L=newAttrNode;attr_L-next=NULL;LL=newLNode;LL-next=NULL;//成功建立两个链表InitLink(LL,Examples);InitAttr(attr_L,Attributes_kind,Attr_kind);ID3(T,LL,NULL,attr_L);cout决策树以广义表形式输出如下：endl;treelists(T);//以广义表的形式输出树//coutGain(9,5,OutLook,LL,attr_L)endl;coutendl;}//以广义表的形式输出树voidtreelists(treeT){treep;if(!T)return;cout{T-weight};coutT-data;p=T-firstchild;if(p){cout(;while(p){treelists(p);p=p-nextsibling;if(p)cout',';}cout);}}voidInitAttr(Attributes&attr_link,char*Attributes_kind[],intAttr_kind[]){Attributesp;for(inti=0;i4;i++){p=newAttrNode;p-next=NULL;strcpy(p-attributes,Attributes_kind[i]);p-attr_Num=Attr_kind[i];p-next=attr_link-next;attr_link-next=p;}}voidInitLink(link&LL,char*Examples[][COL]){linkp;for(inti=0;iROW;i++){p=newLNode;p-next=NULL;strcpy(p-OutLook,Examples[i][0]);strcpy(p-Temperature,Examples[i][1]);strcpy(p-Humidity,Examples[i][2]);strcpy(p-Wind,Examples[i][3]);strcpy(p-PlayTennis,Examples[i][4]);p-next=LL-next;LL-next=p;}}voidPN_Num(linkL,int&positve,int&negative){positve=0;negative=0;linkp;p=L-next;while(p){if(strcmp(p-PlayTennis,No)==0)negative++;elseif(strcmp(p-PlayTennis,Yes)==0)positve++;p=p-next;}}//计算信息增益//linkL:样本集合S//attr_L：属性集合doubleGain(intpositive,intnegative,char*atrribute,linkL,Attributesattr_L){intatrr_kinds;//每个属性中的值的个数Attributesp=attr_L-next;linkq=L-next;intattr_th=0;//第几个属性while(p){if(strcmp(p-attributes,atrribute)==0){atrr_kinds=p-attr_Num;break;}p=p-next;attr_th++;}doubleentropy,gain=0;doublep1=1.0*positive/(positive+negative);doublep2=1.0*negative/(positive+negative);entropy=-p1*log(p1)/log2-p2*log(p2)/log2;//集合熵gain=entropy;//获取每个属性值在训练样本中出现的个数//获取每个属性值所对应的正例和反例的个数//声明一个3*atrr_kinds的数组int**kinds=newint*[3];for(intj=0;j3;j++){kinds[j]=newint[atrr_kinds];//保存每个属性值在训练样本中出现的个数}//初始化for(intj=0;j3;j++){for(inti=0;iatrr_kinds;i++){kinds[j][i]=0;}}while(q){if(strcmp(OutLook,atrribute)==0){for(inti=0;iatrr_kinds;i++){if(strcmp(q-OutLook,OutLook_kind[i])==0){kinds[0][i]++;if(strcmp(q-PlayTennis,Yes)==0)kinds[1][i]++;elsekinds[2][i]++;}}}elseif(strcmp(Temperature,atrribute)==0){for(inti=0;iatrr_kinds;i++){if(strcmp(q-Temperature,Temperature_kind[i])==0){kinds[0][i]++;if(strcmp(q-PlayTennis,Yes)==0)kinds[1][i]++;elsekinds[2][i]++;}}}elseif(strcmp(Humidity,atrribute)==0){for(inti=0;iatrr_kinds;i++){if(strcmp(q-Humidity,Humidity_kind[i])==0){kinds[0][i]++;if(strcmp(q-PlayTennis,Yes)==0)kinds[1][i]++;//elsekinds[2][i]++;}}}elseif(strcmp(Wind,atrribute)==0){for(inti=0;iatrr_kinds;i++){if(strcmp(q-Wind,Wind_kind[i])==0){kinds[0][i]++;if(strcmp(q-PlayTennis,Yes)==0)kinds[1][i]++;elsekinds[2][i]++;}}}q=q-next;}//计算信息增益double*gain_kind=newdouble[a