决策树ID3分类算法.doc

决策树ID3分类算法 一、 决策树学习是一种逼近离散值目标函数的方法，在这种方法中学习到的函数被表示为一颗决策树。ID3算法的思想就是自顶向下构造决策树，它使用统计测试来确定每一个实例属性单独分类训练样例的能力，继而判断哪个属性是最佳的分类属性，直到建立一棵完整的决策树。利用这棵决策树，我们可以对新的测试数据进行分类。 算法实现了对于给定的数据信息, 基于信息增益构造决策树，最后给出决策树和对训练数据集的分类准确率。 实例序号 颜色 体形 毛型 类别 1 黑 大 卷毛 危险 2 棕 大 光滑 危险 3 棕 中 卷毛 不危险 4 黑 小 卷毛 不危险 5 棕 中 光滑 危险 6 黑 大 光滑 危险 7 棕 小 卷毛 危险 8 棕 小 光滑 不危险 9 棕 大 卷毛 危险 10 黑 中 卷毛 不危险 11 黑 中 光滑 不危险 12 黑 小 光滑 不危险 程序代码及其部分注释 其中最核心的部分： void Generate_decision_tree(Tree_Node * root,vectorint Samples, vectorint attribute_list,int class_id) 该函数由给定的训练数据产生一棵判定树。 完整代码： #include stdio.h #include iostream #include vector #include math.h #include string.h using namespace std; typedef struct tnode { char tdata[100]; }tnode; typedef struct Tree_Node { char name[100]; bool isLeaf; //标记是否叶子节点 vectortnode att_list;//属性名称列表 vectorTree_Node * child_list; }Tree_Node,* pTreeNpde; typedef struct dnode { vectortnoderow; }dnode; typedef struct D_Node { vectordnodeDB; vectortnode attr_name; tnode class_name; }D_Node; D_Node G_DB; pTreeNpde Root = NULL; typedef struct FreeQNode { char name[100]; int count; vectorint Set_ID; }FreeQNode; typedef struct FreeQNodeDouble { char name[100]; int count; vectorint row_id; vectorFreeQNode classes;//存放分类属性列表及相应的出现次数 }FreeQNodeDouble; typedef struct attr_node { int attr_id; vectortnode attr_name; vectorint count_list; }attr_node; vectorattr_node G_Attr_List; typedef struct binNode { char name[100]; int count; vectorint Set_ID; struct binNode * lchild; struct binNode * rchild; }binNode; typedef struct binNodeDouble { char name[100]; int count; vectorint row_id; struct binNodeDouble * lchild; struct binNodeDouble * rchild; vectorFreeQNode classes; }binNodeDouble; void insert_tree(binNode * r, char str[100]) { if (NULL == r) { binNode * node = new binNode; strcpy(node-name,str); node-count = 1; //printf([%s,%d]\n,node-name,node-count); node-lchild = node-rchild = NULL; r = node; } else {