决策树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
{
显示全部