C45VC++实现.docx

1、C45VC+实现* c45.h*#ifndef C45_H#define C45_H#include stdafx.hextern AttributeSet testAttributes;extern AttributeSet attributes;extern ContinuousSet isContinues;extern DecisionsSet decisions;extern IndexCollection attrIndex;extern int ERRNO;typedef struct result /样本总数 int count; /错误样本的在样本中的索引 vector er

2、rindex; /失败率 float rate;Result;typedef struct treenode /属性在样本中的索引 int arrrindex; /属性值 TCHAR value32; /属性名 TCHAR name32; /附加数据 TCHAR tag8; /表示下一个条件或者结果 vector nextNode;TreeNode;typedef struct node /指示是否是叶子节点 bool isLeaf; /指向分裂属性的索引 int attrIndex; union /若是叶子节点,则指向结果属性的索引 int classIndex; /指向下一个节点 node

3、* rules; ; /0索引记录结果在样本中出现的数量,1记录除结果以外的其他结果的数量总和 int count2; /指向结果属性中普遍值的索引 int popularClass;Node, *pNode;class C45public: /* / Method: buildTree 使用c4.5构造决策树 / Returns: pNode 返回决策树的根节点 / samples: 样本集 / attrIndex: 属性索引集合 /* static pNode buildTree(DataTable samples, IndexCollection attrIndex); /* / Met

4、hod: postPrune 进行悲观剪枝 / Returns: bool true表示可以剪枝,否则不需要 / iNode 要进行剪枝的节点 /* static bool postPrune(pNode &iNode); /* / Method: removeTree 移除树 / head: 要移除的根节点 /* static void removeTree(pNode &head); /* / Method: test 进行测试 / Returns: Result 返回结果记录对象 / treeNode: 规则树 / testSet: 测试样本数据集 /* static Result te

5、st(TreeNode *treeNode, DataTable testSet);private: /* / Method: count 统计各个属性的分量所对应的结果值的数量 / samples: 样本集 / sampleCount: 结果属性,存储结果 / attrIndex: 属性索引集合 /* static void count(DataTable samples, pCountCollection &sampleCount, IndexCollection attrIndex); /* / Method: discrete 离散化连续属性 / Returns: double 离散化

6、后的结果 / classNum: 结果属性的值分量数量 / colIndex: 要判断的属性在表中的索引 / classIndex:结果属性在表中的索引 / samples: 样本集 /* static double discrete(int classNum, int colIndex,int classIndex, DataTable samples, int truecol); /* / Method: entropy 获取信息熵 / Returns: double 返回信息熵 / attrClassCount: 属性列的数量 / classNum: 结果属性的值分量数量 / allNu

7、m: /* static double entropy(int *attrClassCount, int classNum, int allNum); /* / Method: gainRatio 计算增益比 / Returns: double 返回增益比 / classNum: 结果属性的值分量数量 / attriCount:某个属性的值分量的统计结果集 / pEntropy: 该属性的信息熵 /* static double gainRatio(int classNum, CountCollection attriCount, double pEntropy); /* / Method:

8、chooseAttribute 选择一个要分裂的属性 / Returns: int 返回在样本集或属性中的索引 / attrIndex: 索性索引集合 / sampleCount:属性组统计集合 /* static int chooseAttribute(IndexCollection attrIndex, pCountCollection sampleCount); /返回与value匹配的结果属性值在结果属性列中的索引,没有匹配返回-1 static int getResultValueIndex(int classIndex, int classNum, string value); /

9、true 表示结果集的结果属性值都一样 static bool isSameResultValue(DataTable &samples, int classIndex); /执行测试 static bool todotest(vector &row, TreeNode *treeNode);#endif* c45.cpp*#include c45.h#include #include #include int bestIndex;void C45:count(DataTable samples, pCountCollection &sampleCount, IndexCollection a

10、ttrIndex) sampleCount = new CountCollectionattributes.size(); int theLastIndex = (int)attrIndex.size() - 1; /结果属性在属性样本集中的索引 int colCount = theLastIndex + 1; int resultIndex = attrIndextheLastIndex; /结果属性在样本表中的索引 int classNum = (int)(decisionsresultIndex).size(); /结果属性的值分量数目 int valueNum; /构造统计结构 /遍历

11、样本集中的列 for(int col = 0; col colCount; +col) if(isContinuesattrIndexcol) /离散属性只有两种可能结果 valueNum = 2; else valueNum = (int)decisionsattrIndexcol.size(); for(int valueIndex = 0; valueIndex valueNum; +valueIndex) sampleCountcol.push_back(new intclassNum); for(int i = 0; i classNum; i+) sampleCountcolsam

12、pleCountcol.size()-1i = 0; /统计 for(int col = 0; col colCount ; col+) static int index; bool isContinue = isContinuesattrIndexcol; double divider; if(isContinue) /* 此处曾隐藏一个错误,现已修正.但是不敢肯定已经完全修复此错 错误原因: 离散化处理时,之前discrete函数仅有个参数,col参数表示需要离散的属性列的索引, attrIndex及col的值会因函数的递归而相对改变,但是在discrete中却包含修改decisions值

13、的语句, 问题就是decisions是个全局变量,它的值不因discrete的递归而改变,结果导致col参数指向的索引在 decisions中被错误地表示并被修改. */ divider = discrete(classNum, col, resultIndex, samples, attrIndexcol); for (int rowIndex = 0; rowIndex samples.size(); rowIndex+) /如果是连续属性,那么统计两种值 if(isContinue) int range = 1; if(atof(samplesrowIndexcol.c_str() di

14、vider) range = 0; int m = getResultValueIndex(resultIndex, classNum, samplesrowIndextheLastIndex); sampleCountcolrangem+; else for(int k = 0; k (int)decisionsattrIndexcol.size(); k+) if(samplesrowIpare(decisionsattrIndexcolk) = 0) int m = getResultValueIndex(resultIndex, classNum, samplesrowIndexthe

15、LastIndex); sampleCountcolkm+; break; int C45:getResultValueIndex(int colIndex, int classNum, string value) for(int i = 0; i classNum; i+) if(pare(decisionscolIndexi) = 0) return i; ERRNO = ERROR_NOTMATCHVALUE; return -1;double C45:entropy(int *attrClassCount, int classNum, int allNum) double iEntro

16、py = 0.0; for(int i = 0; i classNum; i+) double temp = (double)attrClassCounti) / allNum; if(temp != 0.0) iEntropy -= temp * (log(temp) / log(2.0); return iEntropy;double C45:gainRatio(int classNum, CountCollection attriCount, double pEntropy) int* attriNum = new intattriCount.size(); int allNum = 0

17、; for(int i = 0; i (int)attriCount.size(); i+) attriNumi = 0; for(int j = 0; j classNum; j+) attriNumi += attriCountij; allNum += attriCountij; double gain = 0.0; double splitInfo = 0.0; for(int i = 0; i (int)attriCount.size(); i+) gain -= (double)attriNumi) / allNum * entropy(attriCounti, classNum,

18、 attriNumi); splitInfo -= (double)attriNumi) / allNum * (log(double)attriNumi)/allNum) / log(2.0); gain += pEntropy; delete attriNum; return (gain / splitInfo);double C45:discrete(int classNum, int colIndex,int classIndex, DataTable samples, int truecol) /用于存储本列每一行离散后的值 double *discreteAtt = new dou

19、ble(int)samples.size(); int *samplesClass = new int(int)samples.size(); for(int row = 0; row (int)samples.size(); row+) discreteAttrow = atof(samplesrowcolIndex.c_str();/将字符串转成double int resultColIndex = samplesrow.size()-1;/结果属性列的索引 /遍历结果属性值分量,将值分量的索引赋值给离散后的当前行 samplesClassrow = getResultValueIndex

20、(classIndex, classNum, samplesrowsamplesrow.size()-1); /排序 for(int row = 0; row row; row2-) if(discreteAttrow2-1 discreteAttrow2) double temp = discreteAttrow2; discreteAttrow2 = discreteAttrow2-1; discreteAttrow2-1 = temp; int ttemp = samplesClassrow2; samplesClassrow2 = samplesClassrow2-1; samples

21、Classrow2-1 = ttemp; CountCollection classCount; int* minSetCount; int* maxSetCount; int bestDivider = 0; double maxGain = -100; for(int row = 2; row (int)samples.size()-2; row+) minSetCount = new intclassNum; maxSetCount = new intclassNum; /遍历值分量 for(int j = 0; j classNum; j+) /初始化 minSetCountj = 0

22、; maxSetCountj = 0; for(int j = 0; j row; j+) minSetCountsamplesClassj+; for(int j = row; j maxGain) bestDivider = row; maxGain = gain; delete minSetCount; delete maxSetCount; classCount.clear(); double divider = discreteAttbestDivider; decisionstruecol.clear(); ostringstream boundStr; boundStr divi

23、der; decisionstruecol.push_back(0); decisionstruecol.push_back(boundStr.str(); delete discreteAtt; delete samplesClass; return divider;int C45:chooseAttribute(IndexCollection attrIndex, pCountCollection sampleCount) int bestIndex = 0; double maxGainRatio = 0.0; int classNum = (int)(decisionsattrInde

24、x(int)attrIndex.size()-1).size(); int* temp = new intclassNum; int allNum = 0; for(int i = 0; i classNum; i+) tempi = sampleCount(int)attrIndex.size()-1ii; allNum += tempi; double pEntropy = entropy(temp, classNum, allNum); delete temp; for(int rowIndex = 0; rowIndex maxGainRatio) bestIndex = rowIndex; maxGainRatio = gainR; return bestIndex;/判断表中的结果是否都一致bool C45:i