决策树课程设计报告

课程设计报告设计题目：决策树构造算法的实现学生姓名：班级：学号：完成日期：（一）需求和规格说明(1)决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。它是一个从上到下、分而治之的归纳过程，是决策树的一个经典的构造算法。应用于很多预测的领域，如通过对信用卡客户数据构建分类模型，可预测下一个客户他是否属于优质客户。(2)分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。数据分类是一个两步过程。第一步，使用已知类别标记的训练数据集建立一个分类模型。例如：图1是一个决策树模型。第二步，对未知标记的数据使用模型进行分类。例如，根据图1的决策树模型，运用自顶而下的属性测试过程，将表2中的样例1-6分别分类为“Y”、“Y”、“Y”、“Y”、“N”、“N”。图1.一个决策树模型的例子(3)举例：对下表运用算法构建决策树表1.一个训练数据集编号天况温度湿度风况分类1晴热大无N2晴热大有N3多云热大无Y4雨中大无Y5雨冷正常无Y6雨冷正常有N7多云冷正常有Y8晴中大无N9晴冷正常无Y10雨中正常无Y11晴中正常有Y12多云中大有Y13多云热正常无Y14雨中大有N对下列样例输入使用构建的决策树模型预测其分类属性：表2.一个待分类的数据集编号天况温度湿度风况分类1晴热正常无？2晴热正常有？天况湿度风况晴多云雨大有无YYNNY正常3雨热正常无？4晴中正常无？5晴冷大有？6晴冷大无？（二）设计基本算法描述：输入：训练样例集S，未标记的节点T，属性集A输出：以T为根的决策树①如果S中所有样例都是正例，则标记节点T为“Y”，并结束；②如果S中所有样例都是反例，则标记节点T为“N”，并结束；③否则，从A中选择一个属性X，(可随机选)标记节点T为X;④设X的所有取值为V1,V2,…,Vn，依据这些取值将S划分为n个子集S1,S2,…,Sn，建T的n个孩子节点Ti，并分别以Vi作为从T到Ti的分支标号;⑤对每对（Si，Ti，A-{X}），递归调用ID3算法建立一棵以Ti为根的子树；决策树算法是非常常用的分类算法，是逼近离散目标函数的方法，学习得到的函数以决策树的形式表示。其基本思路是不断选取产生信息增益最大的属性来划分样例集和，构造决策树。信息增益定义为结点与其子结点的信息熵之差。信息熵是香农提出的，用于描述信息不纯度(不稳定性)，其计算公式是Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例。这样信息收益可以定义为样本按照某属性划分时造成熵减少的期望，可以区分训练样本中正负样本的能力，其计算公式是根据此基本算法，设计一个链表结构体LNode，并用link作为指针，定义LL为训练样式集；设计另一个链表AttrNode，用Attributes作为指针，定义attr_L为属性集；设计一个树结构Tnode，存储形式为孩子-兄弟结点。另外，定义Attributes_kind存储属性名称，定义Attr_kind存储属性值的个数，OutLook_kind；Temperature_kind；Humidity_kind；Wind_kind存储各属性对应的值。训练样式集最初存储在”data\\examples.xls”中，决策树以广义表的形式输出到文件data\\result.dat，未知类别属性数据样例存放在”data/undec.xls”。系统结构图Tnodestringdata当前属性的值stringweight下一个属性名Tnode*firstchild指向第一个孩子结点Tnode*nextsibling指向下一个兄弟结点LnodestringOutLook各个属性的值stringTemperaturestringHumiditystringWindstringPlayTennisLnode*next指向下一个训练数据AttrNodestringattributes属性名intattr_Num属性的值Attrnode*next指向下一个属性（三）用户手册给定训练数据集，本程序将构建决策树模型，并实现对未知类别属性数据样例的分类。程序运行前，请先将训练数据集存放在data/examples.xls，请确保数据与天况、温度、湿度、风况、分类一一对应。例如：SunnyHotHighWeakNoSunnyHotHighStrongNoOverCastHotHighWeakYesRainMildHighWeakYesRainCoolNormalWeakYesRainCoolNormalStrongNoOverCastCoolNormalStrongYesSunnyMildHighWeakNoSunnyCoolNormalWeakYesRainMildNormalWeakYesSunnyMildNormalStrongYesOverCastMildHighStrongYesOverCastHotNormalWeakYesRainMildHighStrongNo如需使用未知类别属性数据样例来分类，请将数据存放在data/undec.xls。例如：SunnyHotNormalWeakSunnyHotNormalStrongRainHotNormalWeakSunnyMildNormalWeakSunnyColdHighStrongSunnyColdHighWeak分类结果将显示在屏幕中。决策树模型将以广义表的形式显示在data/result.dat中。（四）调试及测试运行实例：输入文件同（三）用户手册，输出文件data\\result.dat为：{}OutLook({Sunny}Humidity({High}No,{Normal}Yes),{OverCast}Yes,{Rain}Wind({Weak}Yes,{Strong}No))分类结果显示在屏幕中为SunnyHotNormalWeakYesSunnyHotNormalStrongYesRainHotNormalWeakYesSunnyMildNormalWeakYesSunnyColdHighStrongNoSunnyColdHighWeakNo界面设计：因可能不使用未知类别属性数据样例文件，故需提供一个界面供用户自由选择。不足与改进：因需对属性名、属性值进行匹配，对于每一个不同的属性，需使用不同的代码，故本程序比较繁琐，在后期增加了一些函数精简了代码。（五）附录——源程序#includeiostream#includefstream#includemath.h#includecstring#includestdlib.h#includeiomanipusingnamespacestd;#defineROW20#defineCOL5#definelog20.69314718055typedefstructTNode//决策树{stringdata;stringweight;TNode*firstchild,*nextsibling;}*tree;typedefstructLNode{stringOutLook;stringTemperature;stringHumidity;stringWind;stringPlayTennis;LNode*next;}*link;typedefstructAttrNode{stringattributes;//各个属性名称intattr_Num;//属性对应的值的个数AttrNode*next;}*Attributes;stringAttributes_kind[4]={OutLook,Temperature,Humidity,Wind};//属性名称intAttr_kind[4]={3,3,2,2};//属性对应的值的个数stringOutLook_kind[3]={Sunny,OverCast,Rain};//各个属性的值stringTemperature_kind[3]={Hot,Mild,Cool};stringHumidity_kind[2]={High,Normal};stringWind_kind[2]={Weak,Strong};stringundec[4];ifstreamfin(data\\examples.xls);ofstreamfout(data\\result.dat);ifstreamfin2(data\\undec.xls);linkLL;Attributesattr_L;treeT;voidtreelists(treeT);voidInitAttr();voidInitLink();voidID3(tree&T,linkL,linkTarget_Attr,Attributesattr);voidPN_Num(linkL,int&positve,int&negative);doubleGain(intpositive,intnegative,stringatrribute,linkL,Attributesattr_L);voidcopy1(linkq,linklink_child);voidinput();voiddecision(treeT);intmain1();intmain2();intmain(){intchoice;boolget_1=false;while(1){cout======决策树构造算法的实现======endl;cout│1、训练并构建决策树模型setw(9)│endl;cout│2、对未知类别属性数据样例分类setw(3)│endl;cout│3、帮助setw(25)│endl;cout│4、退出setw(25)│endl;cinchoice;switch(choice){case1:get_1=true;system(cls);main1();system(C:\\windows\\notepad.exedata\\result.dat);system(pause);system(cls);break;case2:system(cls);if(!get_1)coutPleasechoose1first.endl;elsemain2();system(pause);system(cls);break;case3:system(cls);coutendl\a给定训练数据集，本程序将构建决策树模型，并实现对未知类别属性数据样例的分类。endl;cout训练数据集请存放在data/examples.xls，未知类别属性数据样例请存放在data/undec.xls，决策树模型显示在data/result.dat。endlendl;cout***合肥工业大学计算机与信息学院魏慷***endlendl;system(pause);system(cls);break;case4:system(cls);return0;break;default:system(cls);coutErrorNumber!;system(pause);system(cls);break;}}}intmain1(){/**以文件读入训练数据集**/if(!fin){coutError!Cannotopenthefile.;return0;}input();fin.close();/**以文件读入训练数据集**//******初始化*******/T=newTNode;T-firstchild=NULL;T-nextsibling=NULL;T-weight=;T-data=;/******初始化*******/ID3(T,LL,NULL,attr_L);/**以广义表的形式输出到文件**/if(!fout){coutError!Cannotopenthefile.;return0;}treelists(T);fo