#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <set>
#include <vector>
#include <ctime>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <fstream>
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<Node*> children;//子节点vector数组
bool prune_or_not;//判断是否剪枝
};
Node *root=new Node;
void Readtext();
void Readtest();
double Empirical_entropy(Node *p)//求当前数据集的经验熵 HD
{
double HD;
double pos=0,neg=0;
for(int i=0;i<p->datasize;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_index,Node *p)//求索引位置为attr_index的特征的条件熵HDA
{
int maxnum=0,minnum=1000;
for(int i=0;i<p->datasize;i++){//先遍历找出当前特征的特征值的最小值和最大值
if(p->Data[i][attr_index]<minnum) minnum=p->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=0,neg=0,cnt=0;
for(int j=0;j<p->datasize;j++){//遍历所有样本
if(p->Data[j][attr_index]==i){//找出取值为i的所有样本
cnt++;//记录取值为i的样本的数量
if(p->Label[j]==1) pos++;
else neg++;
}
}
double A=0,B=0,C=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;i<p->attrsize;i++)
HDA[i]=Conditional_entropy(i,p);//求第i个特征，在当前数据集的经验熵
double G[10],maxG=-100;
int max_index=0;//信息增益最大的特征的索引位置
for(int i=0;i<p->attrsize;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_index,Node* p)//计算索引位置为attr_index的特征的熵
{
int maxnum=0,minnum=1000;
for(int i=0;i<p->datasize;i++)//先遍历找出当前特征的特征值的最小值和最大值
{
if(p->Data[i][attr_index]<minnum) minnum=p->Data[i][attr_index];
if(p->Data[i][attr_index]>maxnum) maxnum=p->Data[i][attr_index];
}
double sp_info=0;//当前特征的熵
for(int i=minnum;i<=maxnum;i++)//遍历所有可能的取值
{
double cnt=0;//取值为i的样本的数量
for(int j=0;j<p->datasize;j++)//遍历所有样本
{
if(p->Data[j][attr_index]==i)//找出取值为i的所有样本
cnt++;//记录取值为i的样本的数量
}
if(cnt!=0) sp_info+=-1*(cnt/p->datasize)*log(cnt/p->datasize);
}
return sp_info;
}
int C4_5(Node* p)//用C4.5方法从当前节点的特征集当中选择一个特征来分裂
{
double gainRatio[10];//信息增益率
double HD=Empirical_entropy(p);//计算当前数据集的经验熵
for(int i=0;i<p->attrsize;i++)//对当前所有特征求信息增益率
{
double HDA=Conditional_entropy(i,p);//条件熵
double sp_info=SplitInfo(i,p);//特征的熵
gainRatio[i]=(HD-HDA)/sp_info;//信息增益率
}
double maxgR=0;
int max_index=0;//信息增益率最大的特征的索引位置
for(int i=0;i<p->attrsize;i++)//求信息增益率最大的特征的索引位置
{
if(gainRatio[i]>maxgR)
{
maxgR=gainRatio[i]; max_index=i;
}
}
return p->Attr[max_index];//最终返回的是这个特征而不是其索引位置
}
double gini(int attr_index,Node* p) //计算索引位置为attr_index的特征的gini系数
{
int maxnum=0,minnum=1000;
for(int i=0;i<p->datasize;i++){//先遍历找出当前特征的特征值的最小值和最大值
if(p->Data[i][attr_index]<minnum) minnum=p->Data[i][attr_index];
if(p->Data[i][attr_index]>maxnum) maxnum=p->Data[i][attr_index];
}
double gini=0;
for(int i=minnum;i<=maxnum;i++){//遍历所有可能的取值
double pos=0,neg=0,cnt=0;
for(int j=0;j<p->datasize;j++){//遍历所有样本
if(p->Data[j][attr_index]==i)//找出取值为i的所有样本
{
cnt++;//记录取值为i的样本的数量
if(p->Label[j]==1) pos++;
else neg++;
}
}
double A=0,B=0,C=0;
if(cnt!=0){//如果这个特征取值i存在，累加进基尼系数中
A=(cnt/p->datasize);
B=(pos/cnt)*(pos/cnt);
C=(neg/cnt)*(neg/cnt);
gini+=A*(1- B - C );
}
}
return gini;//返回这个特征的基尼系数
}
int CART(Node* p)//用CART方法选取特征
{
double Gini[10];
for(int i=0;i<p->attrsize;i++)//计算得到每个特征的基尼系数
Gini[i]=gini(i,p);
double minnum=1000; int min_index=0;//基尼系数最小的特征的索引位置
for(int i=0;i<p->attrsize;i++)//得到基尼系数最小的特征的索引位置
{
if(Gini[i]<minnum)
{
minnum=Gini[i];min_index=i;
}
}
return p->Attr[min_index];//最终返回的是这个特征而不是其索引位置
}
int choose_attr(Node *p)//从当前节点的特征集当中选择一个特征来分裂
{
int attr;//被选中的特征，下面有三种选择方法
//attr=ID3(p);
//attr=C4_5(p);
attr=CART(p);
return attr;
}
void decide_final_label(Node* p)//叶子结点决定其标签类别（正或负）时调用，采用多数投票方法
{
int pos=0,neg=0;
for(int i=0;i<p->datasize;i++)//统计该叶子节点数据集中正样例和负样例的数目
{
if(p->Label[i]==1) pos++;
else neg++;
}
if(pos>=neg) p->final_label=1;
else p->final_label=-1;
}
bool meet_with_bound(Node* p)//每次递归时调用，用以判断是否满足边界条件
{
//边界条件一：所有数据集样本的标签都相同
bool flag1=1;
int firstone=p->Label[0];//以第一个标签为准，看后面的是否都跟他相同
for(int i=0;i<p->datasize;i++){
if(p->Label[i]!=firstone){
flag1=0; break;
}
}
if(flag1==1) return 1;
//边界条件二：所有数据集的每个特征的取值都相同，这样会导致
//每次取任意一个特征都只能生成同一个节点一直到最后特征取完。
//但在这次实验中，训练集中并没有这种情况出现
bool flag2=1;
for(int j=0;j<p->attrsize;j++){
int maxnum=0,minnum=1000;
for(int i=0;i<p->datasize;i++){
if(p->Data[i][j]<minnum) minnum=p->Data[i][j];
if(p->Data[i][j]>maxnum) maxnum=p->Data[i][j];
}
if(maxnum!=minnum){ //每个特征，都判断其取值的最大值和最小值是否相等，相等即取值相等。
flag2=0; break;
}
}
if(flag2==1) return 1;
//如果都不符合以上边界条件，则说明没有到达边界，继续分裂
return 0;
}
void recursive(Node *p)//递归生成全部节点
{
if(meet_with_bound(p))//如果判断到达边界，则当做叶子节点处理，然后返回
{
cnt_of_leave++;//叶子节点数+1
decide_final_label(p);//决定这个叶子结点的标签
return;
}
//不是叶子节点，则继续分裂/分支
int attr_chosen=choose_attr(p);//选择一个当前特征集中最优代表性的特征
p->attr_chosen=attr_chosen;//记录下当前节点选择了哪个特征进行分裂
int index_chosen;//寻找出这个被选中的特征在当前节点的特征集中的索引位置
for(int i=0;
