C++决策树代码

#includeiostream#includelist#includecstring#includestring#includevector#includemap#includesstream#includeiomanip#includecmath#includefstream#includealgorithm#includeset#includequeueusingnamespacestd;classID3{classNode{public:stringvalue;boolisLeaf;mapstring,Node*map;public:Node():value(),isLeaf(false){}};private:vectorstringattribute;//vectorvectorstringattributevalue;vectorvectorstringdata;intdecatt;Node*root;public:ID3(){//从文件中加载数据ifstreamin(playData.txt);if(in==NULL){coutfailtoopenfile!endl;return;}stringline,str;getline(in,line);istringstreamistring(line);while(!istring.eof()){istringstr;attribute.push_back(str);}while(!in.eof()){getline(in,line);vectorstringvecStr;istringstreamistring(line);while(!istring.eof()){istringstr;vecStr.push_back(str);}data.push_back(vecStr);}in.close();}voidrun(){setDec(4);vectorintsubSet;for(inti=0;idata.size();i++){subSet.push_back(i);}vectorintcandidateAtt;for(inti=0;iattribute.size();i++){if(i!=decatt){candidateAtt.push_back(i);}}Node*tree=buildDT(subSet,candidateAtt);//输出树结构root=tree;vectorstrings;printTreeDepth(root,s);}voidsetDec(intn){if(n0||n=attribute.size()){cout指定决策树变量错误!endl;exit(0);}decatt=n;}doublegetEntropy(vectorintsubSet)//获得子集信息熵{doubleentropy=0;doublep,n;p=n=0;vectorstringvec;for(inti=0;isubSet.size();i++){if(data[subSet[i]][decatt]==yes)p++;elsen++;}//判断属于同一类，熵为零的情况if(0==p||0==n)return0;doublepR=p/(p+n),nR=n/(p+n);entropy=-pR*(log(pR)/log(2.0))-nR*(log(nR)/log(2.0));returnentropy;}boolisPure(vectorintsubset){stringvalue=data[subset[0]][decatt];for(inti=1;isubset.size();i++){if(data[subset[i]][decatt]!=value){returnfalse;}}returntrue;}doublegain(vectorintsubset,intindex)//返回以index为节点的信息增益{//统计正例个数和范例个数doubleentropy=getEntropy(subset);doublesum=0;//求可能的所有属性值mapstring,vectorintmapSub;for(inti=0;isubset.size();i++){mapSub[data[subset[i]][index]].push_back(subset[i]);}for(mapstring,vectorint::iteratoriter=mapSub.begin();iter!=mapSub.end();++iter){doublett=(iter-second.size()/(double)subset.size())*getEntropy(iter-second);//coutiter-first:ttendl;sum+=tt;}returnentropy-sum;}//suSet指子集，value:属性值attribute:候选属性tree:根节点指针的指针Node*buildDT(vectorintsubSet,vectorintattr){Node*p=newNode();if(isPure(subSet)){p-isLeaf=true;p-value=data[subSet[0]][decatt];/*if(*tree!=NULL){(*tree)-map[value]=p;}else{(*tree)=p;}*/returnp;}if(attr.size()==0){inty,n;y=n=0;for(inti=0;isubSet.size();i++){if(data[subSet[i]][decatt]==yes){y++;}elsen++;}if(y=n){p-isLeaf=true;p-value=yes;}else{p-isLeaf=true;p-value=no;}returnp;}//选择一个最优的属性intbest=0;doubledmax=0;intbestIndex=0;for(inti=0;iattr.size();i++){doubledd=gain(subSet,attr[i]);if(dddmax){dmax=dd;best=attr[i];bestIndex=i;}}//获得这个属性的所有属性值和其所对应的子集mapstring,vectorintmapAttValue;for(inti=0;isubSet.size();i++){mapAttValue[data[subSet[i]][best]].push_back(subSet[i]);}attr.erase(attr.begin()+bestIndex);//p-value=this-attribute[best];for(mapstring,vectorint::iteratoriter=mapAttValue.begin();iter!=mapAttValue.end();++iter){p-map[iter-first]=buildDT(iter-second,attr);}//遍历每个属性值被选择后的子集，递归的创建树returnp;}private:voidspace(intn){for(inti=0;in;i++)cout;}public://输出从根节点到叶子节点的所有路径voidprintTree(){Node*t=root;queueNode*que;que.push(t);Node*q=t,*p;while(!que.empty()){p=que.front();que.pop();coutsetw(10)p-value;boolflag=false;if(p==q){coutendl;flag=true;}for(mapstring,Node*::iteratoriter=p-map.begin();iter!=p-map.end();++iter){que.push(iter-second);if(flag){mapstring,Node*::iteratoriter1=iter;iter1++;if(iter1==p-map.end()){q=iter-second;flag=false;}}}}}voidprintTreeDepth(Node*t,vectorstringvec){if(t-isLeaf){for(inti=0;ivec.size();i+=2){if(i!=0)cout-;coutvec[i]:vec[i+1];}cout-t-value;coutendl;coutendl;}else{vec.push_back(t-value);for(mapstring,Node*::iteratoriter=t-map.begin();iter!=t-map.end();++iter){vec.push_back(iter-first);printTreeDepth(iter-second,vec);vec.pop_back();}}}};intmain(){ID3id3;id3.run();return0;}---------------------------------已下是放入playData.txt文件中的数据内容-----------------outlooktemperaturehumiditywindyplaysunnyhothighFALSEnosunnyhothighTRUEnoovercasthothighFALSEyesrainymildhighFALSEyesrainycoolnormalFALSEyesrainycoolnormalTRUEnoovercastcoolnormalTRUEyessunnymildhighFALSEnosunnycoolnormalFALSEyesrainymildnormalFALSEyessunnymildnormalTRUEyesovercastmildhighTRUEyesovercasthotnormalFALSEyesrainymildhighTRUEno