决策树id3分类算法

《决策树id3分类算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、决策树ID3分类算法一、ID3算法介绍决策树学习是一种逼近离散值目标函数的方法，在这种方法屮学习到的函数被表示为一颗决策树。ID3算法的思想就是自顶向下构造决策树，它使用统计测试来确定每一个实例属性单独分类训练样例的能力，继而判断哪个属性是最佳的分类属性，直到建立一棵完整的决策树。利用这棵决策树，我们可以对新的测试数据进行分类。二、算法的实现算法实现了对于给定的数据信息，基于信息增益构造决策树，最后给出决策树和对训练数据集的分类准确率。程序给定的测试样本如下：实例序号颜色体形毛型类别1黑大卷毛危险2棕大光滑危险3棕中卷毛不危险4黑小卷毛不危险5棕中光滑危险6黑大光滑危险7棕小卷毛危险8棕小

2、光滑不危险9棕大卷毛危险10黑中卷毛不危险11黑中光滑不危险12黑小光滑不危险先对上述数据进行预处理：保存为“datal.txt”datal.txt-记事本文件(F)锔辑(E)格式(0)查看(V)帮助(H)性险险险险险险险险险危危险险险危险危危危危危危不不危危危不危不不不型毛滑毛毛滑滑毛滑毛毛滑滑毛卷光卷卷光光卷光卷卷光光1大大中小中大小小大中中小色颜黒棕棕黒棕黒棕棕棕黒黑黒再运行程序，读入数据，输出分析过程和决策规则:"C:UserslenovoDesktopID3DebugID3.exe"危险危险不®^不危险危险危险危险不危险不觸uUBQIuJJuJJE冃EXRUJJfn冃

3、uuuuEa冃HHlr卷光卷卷光光卷光卷卷光光e■tr滑大大中小中大小小大中中小at黑小光e哇th色型型睑1毛4颜体毛危12黑隱黑粽黑棕蜂粽黒黑里talQ^1中2卷IF体型=IF棟型=IF•｛本型=IF饨型=iH本型=IF棟型=IFj本型=Pressany濤>0冶濤濤力肩中中中小小小大ey*k色色色色色色颜颜颜颜颜颜性Je险nu危ItiNonECzhANDr棕棕黑棕棕黑龙次妒妒介妒=♦卷毛’THEN=#光淆〃THEN性=〃不危险#=*卷毛’THEN=♦光滑"THEN性=〃不危险#危险危蔭，危险危险•"不危险'危险，'危险*"不危险卜"C:UserslenovoDesktopID3

4、DebugID3.exe"alltheattributeare：0黑小光滑begintocallGenerate_decision_txee.thesamplesare：01234511011endgain(l)=2.355389-0.540852=1.814536thebestattnb_idis1,attribute—nameis［体型］最普通的类名.中弃晶处理r将按照1，体醐行划分~分共有3个子集幵始获职第［0］个划分［0］,属性名=中begintocallGenerate_decision_tree.thesamplesare：24910endgain(O)=1.500000—

5、0.500000=1.000000中间还有一些过程，为了节约资源，不复制过来了，下面是决策规则:三、程序代码及其部分注释其中最核心的部分:voidGenerate_decision」ree(Tree_Node*&root，vectorSamples,vectorattribute_list，intclass一id)该函数由给定的训练数据产生一棵判定树。完整代码:#include#include#include〈vector〉^include#includeusingnamespacestd;typ

6、edefstructtnode{chartdataflOOl;}tnode;typedefstructTree一Node{charname[100];boolisLeaf;//标记是否叶子节点vectoratt_list;//属性名称列表vectorchild_list;}Tree_Node，*pTreeNpde;typedefstructdnode{vectorrow;}dnode;typedefstructD_Node{vectorattr_name;tnodeclass_name;)D_

7、Node;D_NodeG_DB;pTreeNpdeRoot=NULL;typedefstructFreeQNode{charname[100J;intcount;vectorSet_ID;}FreeQNode;typedefstructFreeQNodeDouble{charname[l()01;intcount;vectorrow_id;vectorclasses;//存放分矣