C4.5算法分类器

c4.5算法是ID3算法的改进，它使用了信息增益率来选择属性，克服使用信息增益来选择属性时偏向选择值多的属性的不足。信息增益率定义为其中Gain（S,A)与ID3算法中的信息增益相同，而分类信息SplitInfo（S，A）代表了按照属性A分裂样本集S的广度和均匀性。其中，Si到Sc是c个属性不同的值的属性A分割S而成的c个样本子集。

C4.5既可以处理离散型描述属性，也可以处理连续性描述属性。在选择某个节点上的分支属性时，对于离散描述属性.c4.5 的处理方法与ID3相同，按照该属性本身的取值个数进行计算，对于某个连续性描述属性使用从小到大排序各个值得中点作为分割点，然后选出按照该分割点分割前后信息增益率最大的分割点进行分支。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define EPS 0.000001
typedef struct Tuple
{
	int i;
    int g;
    double h;
    int c;
}tuple;
typedef struct TNode{
    double  gap;
    int attri;
    int reachValue;
    struct TNode *child[50];
    int kind;
}node;
tuple trainData[100];
double cal_entropy(tuple *data,int len);
double choose_best_gap(tuple *data,int len);
double cal_grainRatio(tuple *data,int len);
double cal_grainRatio2(tuple *data,int len,double gap);
double cal_splitInfo(tuple *data,int len);
int check_attribute(tuple *data,int len);
int choose_attribute(tuple *data,int len);
node *build_tree(tuple *data,int len,double reachValue,double gap);
void print_blank(int depth);
void traverse(node *no,int depth);
void test_data(node *root,tuple *data);
int cmp(const void *a, const void *b)
{
    tuple *a1=(tuple *)a;
    tuple *b1=(tuple *)b;
    return a1->h-b1->h>0?1:-1;
}
void copy_tuple(tuple *source,tuple *destination)
{
    destination->c=source->c;
    destination->g=source->g;
    destination->h=source->h;
	destination->i=source->i;
}
int main()
{
    FILE *fp;
    fp=fopen("./data.txt", "r");
    if(fp==NULL)
    {
        printf("can not open the file: data.txt\n");
        return 0;
    }
    char name[50];
    double height;
    char gender[10];
    char kind[10];
    int i=0;
    while(fscanf(fp, "%s",name)!=EOF)
    {
		trainData[i].i=i;
        fscanf(fp,"%s",gender);
        if(!strcmp(gender, "M"))
        {
            trainData[i].g=0;
        }
        else trainData[i].g=1;
        fscanf(fp,"%lf",&height);
        trainData[i].h=height;
        fscanf(fp,"%s",kind);
        if(!strcmp(kind, "Short"))
        {
            trainData[i].c=0;
        }
        else if(!strcmp(kind,"Medium"))
        {
            trainData[i].c=1;
        }
        else{
            trainData[i].c=2;
        }
        i++;
    }
    int rows=i;
	node *root=build_tree(trainData,rows,-1,-1);
	 traverse(root,0);printf("\n");
	 fp=fopen("./testData.txt", "r");
	     if(fp==NULL)
	     {
	         printf("can not open the file!\n");
	         return 0;
	     }
	     tuple testData;
	     fscanf(fp, "%s",name);
	     fscanf(fp,"%s",gender);
	     if(!strcmp(gender, "M"))
	     {
	         testData.g=0;
	     }
	     else  testData.g=1;
	     fscanf(fp,"%lf",&height);
	      testData.h=height;
	   //  printf("testData: gender: %d\theight: %lf\n",testData.g,testData.h);
		 fclose(fp);
		 fp=NULL;
		 test_data(root,&testData);
}
void test_data(node *root,tuple *data)
{
	/*
     1.检查节点得属性值
     2.如果是身高则检查gap得值如果<=就往左，否则就往右
     3.如果是性别就判断reachValue的值
     */
    if(root->attri==-1)
    {
        printf("the test data belongs to:");
        switch (root->kind) {
            case 0: printf("Short\n");break;
            case 1: printf("Medium\n");break;
            case 2: printf("Tall\n");break;
            default:break;
        }
		return;
    }
	if(root->attri==0)
    {
        if(data->g==0)
        {
            test_data(root->child[0],data);
        }
        else
        {
            test_data(root->child[1], data);
        }
    }
    else
    {
		//printf("gap: %lf\n",root->gap);
        if(data->h<=root->gap)
        {
            test_data(root->child[0], data);
        }
        else{
            test_data(root->child[1], data);
        }
    }
}
 
void print_blank(int depth)
{
    int i;
    for(i=0;i<depth;i++)
    {
        printf("\t");
    }
}
void traverse(node *no,int depth)
{
    if(no==NULL)return;
    int i;
	printf("-------------------\n");
	print_blank(depth);
    printf("attri: %d\n",no->attri);print_blank(depth);
    printf("gap: %lf\n",no->gap);print_blank(depth);
    printf("kind: %d\n",no->kind);print_blank(depth);
    printf("reachValue: %d\n",no->reachValue);print_blank(depth);
	printf("-------------------\n");print_blank(depth);
    for(i=0;no->child[i]!=NULL;i++)
    {
        traverse(no->child[i], depth+1);
    }
}
int choose_attribute(tuple *data,int len)//选择属性函数，返回代表属性的代号
{
    int i;
    /*
     1.如果是性别，就直接计算增益
     2.如果是身高就计算最高得增益值得gap
     3.性别和身高得增益进行比较的到最佳得分类属性
     */
    double gGrainRatio=cal_grainRatio(data, len);
	//printf("gGrainRatio: %lf\n",gGrainRatio);
    /*计算连续属性值的增益
     1.排序确定gap
     2.计算各个gap的信息增益率
     3.选定最大得信息增益率确定该属性的最大信息增益率
     */
    qsort(data,len,sizeof(tuple),cmp);
    double maxGap=-1;
    double maxRaito=-1;
	//printf("len: %d\n",len);
    for(i=1;i<len;i++)
    {
        double gap=(data[i-1].h+data[i].h)/2;
		//printf("gap: %lf\n",gap);
        double ratio=cal_grainRatio2(data,len,gap);//使用获得得gap对数据进行分组计算ratio
		//printf("ratio: %lf\n",ratio);
        if(maxRaito<ratio)///获得最大得增益率
        {
            maxRaito=ratio;maxGap=gap;//记录对打增益对应的gap
        }
    }
	//printf("maxRaito: %lf\n",maxRaito);
    if(gGrainRatio>maxRaito)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
 
node *build_tree(tuple *data,int len,double reachValue,double gap)
{
	//getchar();getchar();
    int i,j;
	/*for(i=0;i<len;i++)
	{
		printf("data i: %d g:%d h:%lf c:%d\n",data[i].i,data[i].g,data[i].h,data[i].c);
	}*/
    int kind=check_attribute(data, len);//检查所有得元组是否属于同一个类
	//printf("kind: %d\n",kind);
    if(kind!=0)//如果所有得元组都属于同一类则作为叶子节点返回
    {
	//	printf("leaves constructed completed!\n");
        node *newNode=(node *)malloc(sizeof(node));
        newNode->gap=gap;//如果是按照身高分类就用得到gap；
        newNode->attri=-1;
        newNode->reachValue=reachValue;
        newNode->kind=kind-1;
        for(i=0;i<50;i++)newNode->child[i]=NULL;//初始化所有的孩子节点
        return newNode;
    }
    //从元组中选择最优属性值进行分类
    int attribute=choose_attribute(data, len);
	//printf("choose: %d\n",attribute);
    //执行分类 深度优先构建树结构
    node *newNode=(node *)malloc(sizeof(node));
    newNode->reachValue=reachValue;
    newNode->attri=attribute;
    newNode->kind=-1;
	newNode->gap=gap;
    for(i=0;i<50;i++)newNode->child[i]=NULL;
    if(attribute==0)//选择性别进行构建
    {
        for(i=0;i<2;i++)
        {
            tuple subData[100];
            int sublen=0;
            for(j=0;j<len;j++)
            {
                if(data[j].g==i/*是男的或者女的*/)
                {
                    copy_tuple(&data[j],&subData[sublen++]);
                }
            }
			if(sublen==0)continue;
            newNode->child[i]=build_tree(subData,sublen,i,-1);//因为是用性别构建得，所以不用gap分区间取值
        }
    }
    else
    {
        //选择高度构建
        /*
         1.选择最优得分割值
         2.将元组分割成left和right两个部分
         */
        double gap=choose_best_gap(data,len);//选择分割连续变量得值
		newNode->gap=gap;
		//printf("best gap: %lf\n",gap);
        tuple leftData[100],rightData[100];//分割完成后，放入左右两个数组里面
        int leftlen=0;//左右数组的长度
        int rightlen=0;
        for(i=0;i<len;i++)
        {
            if(data[i].h<=gap)
            {
                copy_tuple(&data[i],&leftData[leftlen++]);
            }
            else{
                copy_tuple(&data[i],&rightData[rightlen++]);
            }
        }
		if(leftlen!=0)
        newNode->child[0]=build_tree(leftData,leftlen,-1,gap);//使用身高构建子树，因此必须分区间进行
		if(rightlen!=0)
        newNode->child[1]=build_tree(rightData,rightlen,-1,gap);
    }
    return newNode;
}
int check_attribute(tuple *data,int len)//检查所有得元组是否都是一类
{
    /*
     1.扫描所有得元组，如果出现不适同一类得元组，则返回
     */
    int i;
    for(i=1;i<len;i++)
    {
        if(data[i].c!=data[i-1].c)return 0;
    }
    return data[0].c+1;
}
double cal_grainRatio(tuple *data, int len)//计算性别属性得最大增益率
{
    /*
     1.计算总得熵是多少
     2.按照性别将元组分割再计算各个分组得熵
     3.按照权重计算该属性得总得熵
     4.相减计算信息增益
     5.计算分裂
     6.计算信息增益率
     */
    double preEntropy=cal_entropy(data, len);
	//printf("in function:preEntropy: %lf\n",preEntropy);
    int i,j;//计数器
	/*for(i=0;i<len;i++)
	{
		//printf("data: %d\n",data[i].i);
	}*/
    double entropy=0.0;
    for(i=0;i<2;i++)
    {
        tuple subData[100];
        int sublen=0;
        int cnt=0;
        for(j=0;j<len;j++)///分别收集男女得元组，计算出熵，加以权重计算属性熵值
        {
            if(data[j].g==i)
            {
                cnt++;
				//printf("data: %d\n",data[j].i);
                copy_tuple(&data[j],&subData[sublen++]);//这里把j写成了i，悲剧
            }
        }
		/*printf("data:");
		for(j=0;j<sublen;j++)
		{
			printf("%d ",subData[j].i);
		}printf("\n");*/
		//printf("entropy: %lf\n",cal_entropy(subData, sublen));
        entropy=entropy+cnt*1.0/len*cal_entropy(subData, sublen);
    }
    double splitInfo=cal_splitInfo(data,len);
	//printf("in function:entropy: %lf\n",entropy);
	//printf("in function:splitInfo: %lf\n",splitInfo);
    return (preEntropy-entropy)/splitInfo;
}
double choose_best_gap(tuple *data,int len)
{
    int i;
    qsort(data,len,sizeof(tuple),cmp);
    double maxGap=-1;
    double maxRaito=-1;
    for(i=1;i<len;i++)
    {
        double gap=(data[i-1].h+data[i].h)/2;//把int换成double
        double ratio=cal_grainRatio2(data,len,gap);//使用获得得gap对数据进行分组计算ratio
		//printf("ratio: %lf\n",ratio);
		//printf("gap: %lf\n",gap);
        if(maxRaito<ratio)///获得最大得增益率
        {
            maxRaito=ratio;
			maxGap=gap;//记录对打增益对应的gap
        }
    }
    return maxGap;
}
double cal_grainRatio2(tuple *data,int len,double gap)//计算身高得信息增益率
{
    /*
     1.计算总得熵是多少
     2.按照性别将元组分割再计算各个分组得熵
     3.按照权重计算该属性得总得熵
     4.相减计算信息增益
     5.计算分裂
     6.计算信息增益率
     */
    int i;//计数器
    double preEntropy=cal_entropy(data, len);
    tuple smaller[100],larger[100];
    int leftlen=0,rightlen=0;
    for(i=0;i<len;i++)
    {
        if(data[i].h<=gap)
        {
            copy_tuple(&data[i], &smaller[leftlen++]);
        }
        else
        {
            copy_tuple(&data[i], &larger[rightlen++]);
        }
    }
    double leftEntropy=cal_entropy(smaller, leftlen);
    double rightEntropy=cal_entropy(larger, rightlen);
    double tol=0;
    tol=tol+leftlen*1.0/len*leftEntropy+rightlen*1.0/len*rightEntropy;
    tol=preEntropy-tol;
    double splitInfo=cal_splitInfo(data, len);
    return tol/splitInfo;
}
 
double cal_entropy(tuple *data,int len)
{
    /*
     1.统计性别属性得熵值
     */
    int i,j;
    double result=0.0;
    for(i=0;i<3;i++)
    {
        int cnt=0;
        for(j=0;j<len;j++)
        {
            if(data[j].c==i)
            {
                cnt++;
            }
        }
		if(cnt==0)continue;//如果出现没有的情况就跳过
		//printf("cnt: %d\n",cnt);
        double temp=log(cnt*1.0/len)/log(2);
		//printf("temp: %lf\n",temp);
        result=result-cnt*1.0/len*temp;
		//printf("result: %lf\n",result);
    }
    return result;
}
double cal_splitInfo(tuple *data,int len)//计算性别的分裂值
{
    double result=0.0;
    int i,j;//计数器
    for(i=0;i<2;i++)
    {
        int cnt=0;
        for(j=0;j<len;j++)
        {
            if(data[j].g==i)
            {
                cnt++;
            }
        }
        double temp=log(cnt*1.0/len)/log(2);
        result=result-cnt*1.0/len*temp;
    }
    return result;
}