决策树课程设计报告

1、课程设计报告设计题目：决策树构造算法的实现学生姓名： 班级： 学号： 完成日期： （一） 需求和规格说明(1) 决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。它是一个从上到下、分而治之的归纳过程，是决策树的一个经典的构造算法。应用于很多预测的领域，如通过对信用卡客户数据构建分类模型，可预测下一个客户他是否属于优质客户。(2) 分类是数据挖掘、机器学习和模式识别中一个重要的研究领域。数据分类是一个两步过程。第一步，使用已知类别标记的训练数据集建立一个分类模型。例如：图1是一个决策树模型。第二步，对未知标记的数据使用模型进行分类。例如，根据图1的决

2、策树模型，运用自顶而下的属性测试过程，将表2中的样例1-6分别分类为“Y”、“Y”、“Y”、“Y”、“N”、“N”。天况湿度风况晴多云雨大有无YYNNY正常图1. 一个决策树模型的例子(3) 举例：对下表运用算法构建决策树表1. 一个训练数据集编号天况温度湿度风况分类1晴热大无N2晴热大有N3多云热大无Y4雨中大无Y5雨冷正常无Y6雨冷正常有N7多云冷正常有Y8晴中大无N9晴冷正常无Y10雨中正常无Y11晴中正常有Y12多云中大有Y13多云热正常无Y14雨中大有N对下列样例输入使用构建的决策树模型预测其分类属性：表2. 一个待分类的数据集编号天况温度湿度风况分类1晴热正常无？2晴热正常有？3雨

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为根的子树；决策树算法是非常常用的分类算法，是逼近离散目标函数的方

4、法，学习得到的函数以决策树的形式表示。其基本思路是不断选取产生信息增益最大的属性来划分样例集和，构造决策树。信息增益定义为结点与其子结点的信息熵之差。信息熵是香农提出的，用于描述信息不纯度(不稳定性)，其计算公式是Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例。这样信息收益可以定义为样本按照某属性划分时造成熵减少的期望，可以区分训练样本中正负样本的能力，其计算公式是根据此基本算法，设计一个链表结构体LNode，并用link作为指针，定义LL为训练样式集；设计另一个链表AttrNode，用Attributes作为指针，定义attr_L为属性集；设计一个树结构 Tnode，存储形式

5、为孩子-兄弟结点。另外，定义Attributes_kind存储属性名称，定义Attr_kind存储属性值的个数，OutLook_kind；Temperature_kind；Humidity_kind；Wind_kind存储各属性对应的值。训练样式集最初存储在” dataexamples.xls”中，决策树以广义表的形式输出到文件dataresult.dat，未知类别属性数据样例存放在”data/undec.xls”。系统结构图Tnodestringdata当前属性的值stringweight下一个属性名Tnode*firstchild指向第一个孩子结点Tnode*nextsibling指向下一

6、个兄弟结点LnodestringOutLook各个属性的值stringTemperaturestringHumiditystringWindstringPlayTennisLnode*next指向下一个训练数据AttrNodestringattributes属性名intattr_Num属性的值Attrnode*next指向下一个属性（三） 用户手册给定训练数据集，本程序将构建决策树模型，并实现对未知类别属性数据样例的分类。程序运行前，请先将训练数据集存放在，请确保数据与天况、温度、湿度、风况、分类一一对应。例如：SunnyHotHighWeakNoSunnyHotHighStrongNoOve

7、rCastHotHighWeakYesRainMildHighWeakYesRainCoolNormalWeakYesRainCoolNormalStrongNoOverCastCoolNormalStrongYesSunnyMildHighWeakNoSunnyCoolNormalWeakYesRainMildNormalWeakYesSunnyMildNormalStrongYesOverCastMildHighStrongYesOverCastHotNormalWeakYesRainMildHighStrongNo如需使用未知类别属性数据样例来分类，请将数据存放在。例如：SunnyHot

8、NormalWeakSunnyHotNormalStrongRainHotNormalWeakSunnyMildNormalWeakSunnyColdHighStrongSunnyColdHighWeak分类结果将显示在屏幕中。决策树模型将以广义表的形式显示在中。（四） 调试及测试运行实例：输入文件同（三）用户手册，输出文件dataresult.dat为：OutLook(SunnyHumidity(HighNo,NormalYes),OverCastYes,RainWind(WeakYes,StrongNo)分类结果显示在屏幕中为Sunny Hot Normal Weak YesSunny H

9、ot Normal Strong YesRain Hot Normal Weak YesSunny Mild Normal Weak YesSunny Cold High Strong NoSunny Cold High Weak No界面设计：因可能不使用未知类别属性数据样例文件，故需提供一个界面供用户自由选择。不足与改进：因需对属性名、属性值进行匹配，对于每一个不同的属性，需使用不同的代码，故本程序比较繁琐，在后期增加了一些函数精简了代码。（五）附录源程序#include #include #include #include #include #includeusing namespace

10、 std;#define ROW 20#define COL 5#define log2 0.typedef struct TNode /决策树 string data; string weight; TNode *firstchild,*nextsibling;*tree;typedef struct LNode string OutLook; string Temperature; string Humidity; string Wind; string PlayTennis; LNode *next;*link;typedef struct AttrNode string attribu

11、tes;/各个属性名称 int attr_Num;/属性对应的值的个数 AttrNode *next;*Attributes;string Attributes_kind4 = OutLook,Temperature,Humidity,Wind;/属性名称intAttr_kind4 = 3,3,2,2; /属性对应的值的个数string OutLook_kind3 = Sunny,OverCast,Rain; /各个属性的值string Temperature_kind3 = Hot,Mild,Cool;string Humidity_kind2 = High,Normal;string Wi

12、nd_kind2 = Weak,Strong;string undec4;ifstream fin(dataexamples.xls);ofstream fout(dataresult.dat);ifstream fin2(dataundec.xls);link LL;Attributes attr_L;tree T;void treelists(tree T);void InitAttr();void InitLink();void ID3(tree &T,link L,link Target_Attr,Attributes attr);void PN_Num(link L,int &pos

13、itve,int &negative);double Gain(int positive,int negative,string atrribute,link L,Attributes attr_L);void copy1(link q, link link_child);void input();void decision(tree T);int main1();int main2();int main() int choice; bool get_1=false; while(1) cout =决策树构造算法的实现=endl; cout1、训练并构建决策树模型setw(9)endl; co

14、ut2、对未知类别属性数据样例分类setw(3)endl; cout3、帮助setw(25)endl; cout4、退出setw(25)choice; switch (choice) case 1: get_1=true; system(cls); main1(); system(C:windowsnotepad.exe dataresult.dat); system(pause); system(cls); break; case 2: system(cls); if(!get_1)coutPlease choose 1 first.endl; else main2(); system(pa

15、use); system(cls); break; case 3: system(cls); coutendla 给定训练数据集，本程序将构建决策树模型，并实现对未知类别属性数据样例的分类。endl; cout 训练数据集请存放在，未知类别属性数据样例请存放在，决策树模型显示在。endlendl; cout *合肥工业大学 计算机与信息学院 魏慷*endlendl; system(pause); system(cls); break; case 4: system(cls); return 0; break; default: system(cls); coutError Number!; s

16、ystem(pause); system(cls); break; int main1() /*以文件读入训练数据集*/ if(!fin) coutfirstchild=NULL; T-nextsibling=NULL; T-weight=; T-data=; /*初始化*/ ID3(T,LL,NULL,attr_L); /*以广义表的形式输出到文件*/ if(!fout) coutError! Can not open the file.; return 0; treelists(T); foutendl; fout.close(); /*以广义表的形式输出到文件*/ return 0;in

17、t main2() /*完成对未知类别属性数据样例的分类*/ if(!fin2) coutError! Can not open the file.; return 0; for(int i=0; iundeci; while(fin2) for(int i=0; iCOL-1; i+) coutundecit; decision(T); for(int i=0; iundeci; fin2.close(); /*完成对未知类别属性数据样例的分类*/ return 0;/做出决策void decision(tree T) if(T-data=OutLook) for (tree p=T-fir

18、stchild; p!=NULL; p=p-nextsibling) if(undec0=p-weight) decision(p); else if(T-data=Temperature) for (tree p=T-firstchild; p!=NULL; p=p-nextsibling) if(undec1=p-weight) decision(p); else if(T-data=Humidity) for (tree p=T-firstchild; p!=NULL; p=p-nextsibling) if(undec2=p-weight) decision(p); else if(T

19、-data=Wind) for (tree p=T-firstchild; p!=NULL; p=p-nextsibling) if(undec3=p-weight) decision(p); else coutdatanext=NULL; LL=new LNode; LL-next=NULL; InitLink(); /从训练数据集读取数据到LL InitAttr();/将属性读取到attr_L中/以广义表的形式输出树void treelists(tree T) tree p; foutweight; foutdata; p=T-firstchild; if (p!=NULL) foutne

20、xtsibling; if (p!=NULL) fout,; foutp-OutLook; finp-Temperature; finp-Humidity; finp-Wind; finp-PlayTennis; p-next = LL-next; LL-next = p; void InitAttr() Attributes p;/逆序头指针插入法（顺序不变） for (int i=3; i=0; i-) p = new AttrNode; p-next = NULL; p-attributes=Attributes_kindi; p-attr_Num = Attr_kindi; p-nex

21、t = attr_L-next; attr_L-next = p; void PN_Num(link L,int &positve,int &negative) positve = 0; negative = 0; for (link p=L-next; p!=NULL ; p=p-next ) if (p-PlayTennis=No) negative+; else positve+;/计算信息增益/link L: 样本集合S/attr_L：属性集合double Gain(int positive,int negative,string atrribute,link L,Attributes

22、 attr_L) int atrr_kinds;/每个属性中的值的个数 int attr_th=0;/第几个属性 for (Attributes p=attr_L-next; p!=NULL; p=p-next, attr_th+) if (p-attributes=atrribute) atrr_kinds = p-attr_Num; break; double entropy,gain=0; double p1=1.0*positive/(positive + negative); double p2=1.0*negative/(positive + negative); entropy

23、= -p1*log(p1)/log2 - p2*log(p2)/log2;/集合熵 gain = entropy; /获取每个属性值在训练样本中出现的个数 /获取每个属性值所对应的正例和反例的个数 /声明一个3*atrr_kinds的数组 int * kinds= new int * 3; for (int j=0; j 3; j+) kindsj=new intatrr_kinds;/保存每个属性值在训练样本中出现的个数 /初始化 for (int j=0; j3; j+) for (int i=0; i next; q!=NULL; q=q-next) if (OutLook=atrrib

24、ute) for (int i = 0; i OutLook=OutLook_kindi) kinds0i+; if(q-PlayTennis=Yes) kinds1i+; else kinds2i+; else if (Temperature=atrribute) for (int i = 0; i Temperature=Temperature_kindi) kinds0i+; if(q-PlayTennis=Yes) kinds1i+; else kinds2i+; else if (Humidity=atrribute) for (int i = 0; i Humidity=Humid

25、ity_kindi) kinds0i+; if(q-PlayTennis=Yes) kinds1i+;/ else kinds2i+; else if (Wind=atrribute) for (int i = 0; i Wind=Wind_kindi) kinds0i+; if(q-PlayTennis=Yes) kinds1i+; else kinds2i+; /计算信息增益 double * gain_kind = new doubleatrr_kinds; for (int j = 0; j next; while (p!=NULL) q = p; p = p-next; delete

26、(q); Link-next=NULL;void copy1(link q, link link_child) link q1=new LNode; q1-OutLook=q-OutLook; q1-Humidity=q-Humidity; q1-Temperature=q-Temperature; q1-Wind=q-Wind; q1-PlayTennis=q-PlayTennis; q1-next=link_child-next; link_child-next = q1;void ID3(tree &T,link L,link Target_Attr,Attributes attr) /

27、主函数调用为ID3(T,LL,NULL,attr_L); Attributes p,max,attr_child,p1; link q,link_child; tree r,tree_p; int positive ,negative; PN_Num(L,positive,negative); /计算positive与negative 的值 attr_child=new AttrNode; /初始化两个子集合 attr_child-next=NULL; link_child=new LNode; link_child-next = NULL; if (positive=0)/如果S中所有样例都

28、是反例，则标记节点T为“Y”，并结束 T-data=No; return; if( negative=0)/如果S中所有样例都是正例，则标记节点T为“N”，并结束 T-data=Yes; return; /* 建立属性子集合与训练样本子集合有两个方案： 一：在原来链表的基础上进行删除； 二：另外申请空间进行存储子集合； 采用第二种方法虽然浪费了空间，但也省了很多事情，避免了变量之间的应用混乱 */ p=attr-next; /调整到第一个属性 double gain,g=0; if(p!=NULL) for (p=attr-next; p!=NULL; p=p-next) gain = Gai

29、n(positive,negative,p-attributes,L,attr); coutattributes gaing) g=gain; max=p;/寻找信息增益最大的属性 T-data=max-attributes;/增加决策树的节点 coutattributes = attributesendlnext; p!=NULL; p=p-next) if (p-attributes!=max-attributes) p1=new AttrNode; p1-attributes=p-attributes; p1-attr_Num=p-attr_Num; attr_child_s-next=

30、p1; p1-next=NULL; attr_child_s=p1; /*建立每一层的第一个节点*/ r=new TNode; r-firstchild=r-nextsibling = NULL; T-firstchild = r; if (OutLook=max-attributes) r-weight=OutLook_kind0; /获取与属性值相关的训练样例Example(vi),建立一个新的训练样本链表link_child for(q=L-next; q!=NULL; q=q-next) if (q-OutLook=OutLook_kind0) copy1(q,link_child);

31、 else if (Temperature=max-attributes) r-weight=Temperature_kind0; for(q=L-next; q!=NULL; q=q-next) if (q-Temperature=Temperature_kind0) copy1(q,link_child); else if (Humidity=max-attributes) r-weight=Humidity_kind0; for(q=L-next; q!=NULL; q=q-next) if (q-Humidity=Humidity_kind0) copy1(q,link_child);

32、 else r-weight=Wind_kind0; for(q=L-next; q!=NULL; q=q-next) if (q-Wind=Wind_kind0) copy1(q,link_child); int p=0,n=0; PN_Num(link_child,p,n); if (p!=0 & n!=0) ID3(T-firstchild,link_child,Target_Attr,attr_child); FreeLink(link_child); else if(p=0) T-firstchild-data=No; FreeLink(link_child); else if(n=0) T-firstchild-data=Yes; FreeLink(link_child); /*建立每一层上的其他节点。与建立第一个结点的方法区别不大*/