决策树代码及实验数据文件

决策树是一个通过训练的数据来搭建起的树结构模型，根节点中存储着所有数据集和特征集，当前节点的每个分支是该节点在相应的特征值上的表现，而叶子节点存放的结果则是决策结果。通过这个模型，我们可以高效的对于未知的数据进行归纳分类。每次使用决策树时，是将测试样本从根节点开始，选择特征分支一直向下直至到达叶子节点，然后得到叶子节点的决策结果。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int Length;//训练集文本特征数 
int textcnt=0;//训练集文本数 
int train[800][10];//训练集二维数组 
int label[800];//训练集标签数组 
int valicnt=0;//验证集文本数 
int vali[500][10];//验证集二维数组 
int valilabel[500];//验证集标签数组 
int vali_label_result[800];//使用验证集猜测的标签数组 
double accuracy=0;//准确率 
int cnt_of_leave=0;//用训练集构建的决策树的叶子节点数目 
int cnt_of_arriving_leaf=0;//使用决策树时到达叶子节点的文本数 
int cnt_of_not_arriving_leaf=0;//使用决策树时没有到达叶子节点的文本数 
int cnt_of_pruned_leaves=0;
int test[500][10];//测试集二维数组 
int testcnt=0;//测试集样本数 
int test_label_result[500];//测试集使用决策树后的预测结果 
int test_cnt_of_arriving_leaf=0;//测试集使用决策树时到达叶子结点 
int test_cnt_of_not_arriving_leaf=0;//测试集使用决策树时没有到达叶子结点 
struct Node{
	int Data[1000][10];//数据集 
	int Label[1000];//当前数据集的标签数组，行数跟Data数据集一样多 
	int Attr[10];//共有9个特征 
	int datasize;//共多少行数据集 
	int attrsize;//共多少个特征 
	int attr_chosen;//选取哪个特征向下分裂 
	int final_label;//叶节点最后取的label（多数投票） 
	int attr_num;//父节点分裂时这个节点的具体的特征值 
	vector children;//子节点vector数组 
	bool prune_or_not;//判断是否剪枝 
};
Node *root=new Node; 
void Readtext（）;
void Readtest（）;
double Empirical_entropy（Node *p）//求当前数据集的经验熵 HD
{
	double HD;
	double pos=0neg=0;
	for（int i=0;idatasize;i++）//统计数据集中正标签和负标签的数目 
	{
		if（p->Label[i]==1） pos++;
		else neg++;
	}
	HD=-1*（pos/p->datasize）*log（pos/p->datasize）-（（neg/p->datasize）*log（neg/p->datasize））;
	return HD;
}
double Conditional_entropy（int attr_indexNode *p）//求索引位置为attr_index的特征的条件熵HDA 
{
	int maxnum=0minnum=1000;
	for（int i=0;idatasize;i++）{//先遍历找出当前特征的特征值的最小值和最大值 	
		if（p->Data[i][attr_index]Data[i][attr_index];
		if（p->Data[i][attr_index]>maxnum） maxnum=p->Data[i][attr_index];
	}	
	double HDA=0;
	for（int i=minnum;i<=maxnum;i++）{//遍历所有可能的取值 			
		double pos=0neg=0cnt=0;
		for（int j=0;jdatasize;j++）{//遍历所有样本 		
			if（p->Data[j][attr_index]==i）{//找出取值为i的所有样本 			
				cnt++;//记录取值为i的样本的数量 
				if（p->Label[j]==1） pos++;
				else neg++;
			}
		}
		double A=0B=0C=0;
		if（cnt!=0）{//cnt==0即没有这个特征值时不计算，cnt!=0即存在这个特征值时计算 		
			A=（cnt/p->datasize）*-1;
			if（pos!=0） B=pos/cnt*log（pos/cnt）;
			if（neg!=0） C=neg/cnt*log（neg/cnt）;
			HDA+=A*（ B + C ）;	//累加 
		}				 	
	}
	return HDA;
}
int ID3（Node *p）//用ID3从当前节点的特征集当中选择一个特征来分裂 
{
	double HD=Empirical_entropy（p）;//求当前数据集的经验熵 
	double HDA[10];
	for（int i=0;iattrsize;i++）	
		HDA[i]=Conditional_entropy（ip）;//求第i个特征，在当前数据集的经验熵 
	double G[10]maxG=-100;
	int max_index=0;//信息增益最大的特征的索引位置 
	for（int i=0;iattrsize;i++）//遍历所有特征，得到他们的信息增益 
	{
		G[i]=HD-HDA[i];
		if（G[i]>maxG）{	maxG=G[i];	max_index=i;}		
	}
	return p->Attr[max_index];//最终返回的是这个特征而不是其索引位置 
}
double SplitInfo（int attr_indexNode* p）//计算索引位置为attr_index的特征的熵 
{
	int maxnum=0minnum=1000;
	for（int i=0;idatasize;i++）//先遍历找出当前特征

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-04-02 16:00  决策树代码及数据文件\
     文件       15310  2018-04-02 16:00  决策树代码及数据文件\DecisionTree.cpp
     文件        6306  2017-10-26 11:06  决策树代码及数据文件\test.csv
     文件       17009  2017-10-26 11:06  决策树代码及数据文件\train.csv