C45VC++实现.docx
- 文档编号:13386820
- 上传时间:2023-06-13
- 格式:DOCX
- 页数:54
- 大小:32.75KB
C45VC++实现.docx
《C45VC++实现.docx》由会员分享,可在线阅读,更多相关《C45VC++实现.docx(54页珍藏版)》请在冰点文库上搜索。
C45VC++实现
************************************************c45.h************************************************************************
#ifndefC45_H
#defineC45_H
#include"stdafx.h"
externAttributeSettestAttributes;
externAttributeSetattributes;
externContinuousSetisContinues;
externDecisionsSetdecisions;
externIndexCollectionattrIndex;
externintERRNO;
typedefstructresult
{
//样本总数
intcount;
//错误样本的在样本中的索引
vector
//失败率
floatrate;
}Result;
typedefstructtreenode
{
//属性在样本中的索引
intarrrindex;
//属性值
TCHARvalue[32];
//属性名
TCHARname[32];
//附加数据
TCHARtag[8];
//表示下一个条件或者结果
vector
}TreeNode;
typedefstructnode
{
//指示是否是叶子节点
boolisLeaf;
//指向分裂属性的索引
intattrIndex;
union
{
//若是叶子节点,则指向结果属性的索引
intclassIndex;
//指向下一个节点
node**rules;
};
//0索引记录结果在样本中出现的数量,1记录除结果以外的其他结果的数量总和
intcount[2];
//指向结果属性中普遍值的索引
intpopularClass;
}Node,*pNode;
classC45
{
public:
//************************************
//Method:
buildTree使用c4.5构造决策树
//Returns:
pNode返回决策树的根节点
//samples:
样本集
//attrIndex:
属性索引集合
//************************************
staticpNodebuildTree(DataTablesamples,IndexCollectionattrIndex);
//************************************
//Method:
postPrune进行悲观剪枝
//Returns:
booltrue表示可以剪枝,否则不需要
//iNode要进行剪枝的节点
//************************************
staticboolpostPrune(pNode&iNode);
//************************************
//Method:
removeTree移除树
//head:
要移除的根节点
//************************************
staticvoidremoveTree(pNode&head);
//************************************
//Method:
test进行测试
//Returns:
Result返回结果记录对象
//treeNode:
规则树
//testSet:
测试样本数据集
//************************************
staticResulttest(TreeNode*treeNode,DataTabletestSet);
private:
//************************************
//Method:
count统计各个属性的分量所对应的结果值的数量
//samples:
样本集
//sampleCount:
结果属性,存储结果
//attrIndex:
属性索引集合
//************************************
staticvoidcount(DataTablesamples,pCountCollection&sampleCount,IndexCollectionattrIndex);
//************************************
//Method:
discrete离散化连续属性
//Returns:
double离散化后的结果
//classNum:
结果属性的值分量数量
//colIndex:
要判断的属性在表中的索引
//classIndex:
结果属性在表中的索引
//samples:
样本集
//************************************
staticdoublediscrete(intclassNum,intcolIndex,intclassIndex,DataTablesamples,inttruecol);
//************************************
//Method:
entropy获取信息熵
//Returns:
double返回信息熵
//attrClassCount:
属性列的数量
//classNum:
结果属性的值分量数量
//allNum:
//************************************
staticdoubleentropy(int*attrClassCount,intclassNum,intallNum);
//************************************
//Method:
gainRatio计算增益比
//Returns:
double返回增益比
//classNum:
结果属性的值分量数量
//attriCount:
某个属性的值分量的统计结果集
//pEntropy:
该属性的信息熵
//************************************
staticdoublegainRatio(intclassNum,CountCollectionattriCount,doublepEntropy);
//************************************
//Method:
chooseAttribute选择一个要分裂的属性
//Returns:
int返回在样本集或属性中的索引
//attrIndex:
索性索引集合
//sampleCount:
属性组统计集合
//************************************
staticintchooseAttribute(IndexCollectionattrIndex,pCountCollectionsampleCount);
//返回与value匹配的结果属性值在结果属性列中的索引,没有匹配返回-1
staticintgetResultValueIndex(intclassIndex,intclassNum,stringvalue);
//true表示结果集的结果属性值都一样
staticboolisSameResultValue(DataTable&samples,intclassIndex);
//执行测试
staticbooltodotest(vector
};
#endif
*******************************************c45.cpp*********************************************************
#include"c45.h"
#include
#include
#include
intbestIndex;
voidC45:
:
count(DataTablesamples,pCountCollection&sampleCount,IndexCollectionattrIndex)
{
sampleCount=newCountCollection[attributes.size()];
inttheLastIndex=(int)attrIndex.size()-1;//结果属性在属性样本集中的索引
intcolCount=theLastIndex+1;
intresultIndex=attrIndex[theLastIndex];//结果属性在样本表中的索引
intclassNum=(int)(decisions[resultIndex]).size();//结果属性的值分量数目
intvalueNum;
//构造统计结构
//遍历样本集中的列
for(intcol=0;col { if(isContinues[attrIndex[col]])//离散属性只有两种可能结果 valueNum=2; else valueNum=(int)decisions[attrIndex[col]].size(); for(intvalueIndex=0;valueIndex { sampleCount[col].push_back(newint[classNum]); for(inti=0;i sampleCount[col][sampleCount[col].size()-1][i]=0; } } //统计 for(intcol=0;col { staticintindex; boolisContinue=isContinues[attrIndex[col]]; doubledivider; if(isContinue) { /* 此处曾隐藏一个错误,现已修正.但是不敢肯定已经完全修复此错 错误原因: 离散化处理时,之前discrete函数仅有个参数,col参数表示需要离散的属性列的索引, attrIndex及col的值会因函数的递归而相对改变,但是在discrete中却包含修改decisions值的语句, 问题就是decisions是个全局变量,它的值不因discrete的递归而改变,结果导致col参数指向的索引在 decisions中被错误地表示并被修改. */ divider=discrete(classNum,col,resultIndex,samples,attrIndex[col]); } for(introwIndex=0;rowIndex { //如果是连续属性,那么统计两种值 if(isContinue) { intrange=1; if(atof(samples[rowIndex][col].c_str()) range=0; intm=getResultValueIndex(resultIndex,classNum,samples[rowIndex][theLastIndex]); sampleCount[col][range][m]++; } else { for(intk=0;k<(int)decisions[attrIndex[col]].size();k++) { if(samples[rowIndex][col].compare(decisions[attrIndex[col]][k])==0) { intm=getResultValueIndex(resultIndex,classNum,samples[rowIndex][theLastIndex]); sampleCount[col][k][m]++; break; } } } } } } intC45: : getResultValueIndex(intcolIndex,intclassNum,stringvalue) { for(inti=0;i if(pare(decisions[colIndex][i])==0) returni; ERRNO=ERROR_NOTMATCHVALUE; return-1; } doubleC45: : entropy(int*attrClassCount,intclassNum,intallNum) { doubleiEntropy=0.0; for(inti=0;i { doubletemp=((double)attrClassCount[i])/allNum; if(temp! =0.0) iEntropy-=temp*(log(temp)/log(2.0)); } returniEntropy; } doubleC45: : gainRatio(intclassNum,CountCollectionattriCount,doublepEntropy) { int*attriNum=newint[attriCount.size()]; intallNum=0; for(inti=0;i<(int)attriCount.size();i++) { attriNum[i]=0; for(intj=0;j { attriNum[i]+=attriCount[i][j]; allNum+=attriCount[i][j]; } } doublegain=0.0; doublesplitInfo=0.0; for(inti=0;i<(int)attriCount.size();i++) { gain-=((double)attriNum[i])/allNum*entropy(attriCount[i],classNum,attriNum[i]); splitInfo-=((double)attriNum[i])/allNum*(log(((double)attriNum[i])/allNum)/log(2.0)); } gain+=pEntropy; delete[]attriNum; return(gain/splitInfo); } doubleC45: : discrete(intclassNum,intcolIndex,intclassIndex,DataTablesamples,inttruecol) { //用于存储本列每一行离散后的值 double*discreteAtt=newdouble[(int)samples.size()]; int*samplesClass=newint[(int)samples.size()]; for(introw=0;row<(int)samples.size();row++) { discreteAtt[row]=atof(samples[row][colIndex].c_str());//将字符串转成double intresultColIndex=samples[row].size()-1;//结果属性列的索引 //遍历结果属性值分量,将值分量的索引赋值给离散后的当前行 samplesClass[row]=getResultValueIndex(classIndex,classNum,samples[row][samples[row].size()-1]); } //排序 for(introw=0;row<(int)samples.size()-1;row++) { for(introw2=(int)samples.size()-1;row2>row;row2--){ if(discreteAtt[row2-1]>discreteAtt[row2]) { doubletemp=discreteAtt[row2]; discreteAtt[row2]=discreteAtt[row2-1]; discreteAtt[row2-1]=temp; intttemp=samplesClass[row2]; samplesClass[row2]=samplesClass[row2-1]; samplesClass[row2-1]=ttemp; } } } CountCollectionclassCount; int*minSetCount; int*maxSetCount; intbestDivider=0; doublemaxGain=-100; for(introw=2;row<(int)samples.size()-2;row++) { minSetCount=newint[classNum]; maxSetCount=newint[classNum]; //遍历值分量 for(intj=0;j { //初始化 minSetCount[j]=0; maxSetCount[j]=0; } for(intj=0;j minSetCount[samplesClass[j]]++; for(intj=row;j<(int)samples.size()-1;j++) maxSetCount[samplesClass[j]]++; classCount.push_back(minSetCount); classCount.push_back(maxSetCount); //获取最大的分裂分量 doublegain=gainRatio(classNum,classCount,0.0); if(gain>maxGain) { bestDivider=row; maxGain=gain; } delete[]minSetCount; delete[]maxSetCount; classCount.clear(); } doubledivider=discreteAtt[bestDivider]; decisions[truecol].clear(); ostringstreamboundStr; boundStr< decisions[truecol].push_back("0"); decisions[truecol].push_back(boundStr.str()); delete[]discreteAtt; delete[]samplesClass; returndivider; } intC45: : chooseAttribute(IndexCollectionattrIndex,pCountCollectionsampleCount) { intbestIndex=0; doublemaxGainRatio=0.0; intclassNum=(int)(decisions[attrIndex[(int)attrIndex.size()-1]]).size(); int*temp=newint[classNum]; intallNum=0; for(inti=0;i { temp[i]=sampleCount[(int)attrIndex.size()-1][i][i]; allNum+=temp[i]; } doublepEntropy=entropy(temp,classNum,allNum); delete[]temp; for(introwIndex=0;rowIndex<(int)attrIndex.size()-1;rowIndex++) { doublegainR=gainRatio(classNum,sampleCount[rowIndex],pEntropy); if(gainR>maxGainRatio) { bestIndex=rowIndex; maxGainRatio=gainR; } } returnbestIndex; } //判断表中的结果是否都一致 boolC45: : i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- C45VC 实现
![提示](https://static.bingdoc.com/images/bang_tan.gif)