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;
//错误样本的在样本中的索引
vectorerrindex;
//失败率
floatrate;
}Result;
typedefstructtreenode
{
//属性在样本中的索引
intarrrindex;
//属性值
TCHARvalue[32];
//属性名
TCHARname[32];
//附加数据
TCHARtag[8];
//表示下一个条件或者结果
vectornextNode;
}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&row,TreeNode*treeNode）;
};
#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;isampleCount[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;iif（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;jminSetCount[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
升级会员 