main.c

决策树算法

/*
决策树算法

由于时间问题，本决策树算法并不太完善，按照资料中所给的数据及算法，本算法成功
建立了一树决策树，并加以测试，得出了与原题要求的结果。但程序设计上还存在不少
细节上的问题，例如对数据的存储方面，当初把每个分量分别设置了参数名，这导致了
后面某些地方程序编写方面的不便，若是改由一个数组存储，忽略掉各参数本身所带有
的现实意义，对于整个决策树算法的编写会有一定的好处。

算法分析：
首先，本算法在计算各子树的E值时，把子树根结点的条件一并计算在内，但这并不影响
算法的正常实现，因为我发现这个条件的E值必定等于此子树的信息总量，所以不会将其
作为下一级子树的首要结点来使用，所以不会影响算法的执行。

其次，本算法并未真正计算G值，因为我发现，G(A)=H(n,m)-E(A)，对于同一级子树而言，
H(n,m)是一定的，对于程序执行来说，只需比较E值即可。

最后，以上两点的应用，本人并未经过严格的数学验证，并不清楚其正确性与否，若在在
问题，请老师指正，谢谢。

程序在WINDOWS XP + VC6.0下正常编译运行通过，生成的的应用程序需与数据文件放于同
一目录（或修改FILENAME宏的值，以更改数据文件的路径）。

按PPT中数据生成决策树请看附带的图片文件result.jpg，数据文件格式请参看readme.txt
中的相关说明。

*/
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define FILENAME "BI_02_DATA.txt"

typedef struct _DATA{
	int id;
	int area; /*面积*/
	int price;/*单价*/
	int is_cantonal;/*是否在内环内*/
	int is_old;/*房龄是否大于5年*/
	int invest;/*是否投资*/
	struct _DATA * next;
} DATA;

typedef struct _NODE{
	struct _NODE * child[3];
	DATA con;
	int result;
} NODE;

DATA * head;
NODE * root;
int count_N[5][3],count_M[5][3];
float E[5];

void init();
void input();
float H(int _n,int _m);
void count(DATA * con);
void cal_E();
void create(NODE * cur);
NODE * new_node();
int predict(DATA * t);

int main(){
	DATA t;
	init();
	create(root);
	t.id = 0;
	while(1){
		printf("请输入测试序号（-1为结束测试）：");
		scanf("%d",&(t.id));
		if(t.id == -1) break;
		printf("请依次输入各项参数代码，\n顺序为面积、单价、是否在内环内、房龄是否大于5年，\n");
		printf("其中面积小于90为0，90-120为1，120以上为2；\n");
		printf("单价0.8以下为0，0.8-1.2为1，1.2以上为2；\n");
		printf("在内环内为1，不在内环内为0；\n");
		printf("房龄大于5年为1，小于5年为0。\n");
		scanf("%d%d%d%d",&(t.area),&(t.price),&(t.is_cantonal),&(t.is_old));
		if(predict(&t)) printf("投资此房产！\n"); else printf("不投资此房产！\n");
	}
	return 0;
}

NODE * new_node(){
	int i;
	NODE * tem;
	tem =(NODE *)malloc(sizeof(NODE));
	tem->con.id = -1;
	tem->con.area = -1;
	tem->con.price = -1;
	tem->con.is_cantonal = -1;
	tem->con.is_old = -1;
	tem->result = -1;
	for(i=0;i<3;i++) tem->child[i] = NULL;
	return tem;
}
void init(){
	input();
	root = new_node();
}

void input(){
	FILE * fi;
	DATA * cur;
	int t;
	fi = fopen(FILENAME,"r");
	fscanf(fi,"%d",&t);
	head = NULL;
	if(t == -1) return;
	head = (DATA *)malloc(sizeof(DATA));
	cur = head;
	while(cur){
		cur->id = t;
		fscanf(fi,"%d%d%d%d%d",&(cur->area),&(cur->price),&(cur->is_cantonal),&(cur->is_old),&(cur->invest));
		fscanf(fi,"%d",&t);
		if (t == -1)
			cur->next = NULL;
		else
			cur->next = (DATA *)malloc(sizeof(DATA));
		cur = cur->next;
	}
	fclose(fi);
}

float H(int _n,int _m){
	float n,m;
	n=(float)_n;
	m=(float)_m;
	if(m==0 || n == 0) return 0;
	else return (float)(-m / (m + n) * log(m / (m + n)) / log(2) -n / (m + n) * log(n / (m + n)) / log(2));
}

void count(DATA * con){
	int i,j;
	DATA * cur;
/*计算各参数的n和m值*/
	cur = head;
	for(i=0;i<5;i++)
		for(j=0;j<3;j++)
			count_N[i][j] = count_M[i][j] = 0;
	while(cur){
		if(con->id != -1){
			if(con->area != -1 && cur->area != con->area){
				cur = cur->next;
				continue;
			}
			if(con->price != -1 && cur->price != con->price){
				cur = cur->next;
				continue;
			}
			if(con->is_cantonal != -1 && cur->is_cantonal != con->is_cantonal){
				cur = cur->next;
				continue;
			}
			if(con->is_old != -1 && cur->is_old != con->is_old){
				cur = cur->next;
				continue;
			}
		}
		if(cur->invest == 0){
			count_M[0][0]++;
			count_M[1][cur->area]++;
			count_M[2][cur->price]++;
			count_M[3][cur->is_cantonal]++;
			count_M[4][cur->is_old]++;
		}
		else{
			count_N[0][0] ++;
			count_N[1][cur->area]++;
			count_N[2][cur->price]++;
			count_N[3][cur->is_cantonal]++;
			count_N[4][cur->is_old]++;
		}
		cur = cur->next;
	}
}


void cal_E(){
	int i,j;
	E[0] = -1;
	for(i=1;i<5;i++){
		E[i]=0;
		for(j=0;j<3;j++)
			E[i]+=(count_N[i][j]+ count_M[i][j])*H(count_M[i][j],count_N[i][j]);
		E[i] /= count_N[0][0]+count_M[0][0];
	}
}

void create(NODE * cur){
	int i,j;
	count(&(cur->con));
	cal_E();
	if(H(count_N[0][0],count_M[0][0]) == 0){
		if(count_N[0][0] == 0) cur->result = 0;
		else cur->result = 1;
		return;
	}
	j=1;
	E[0]=E[1];
	for(i=1;i<5;i++)
		if(E[i]<E[0]){
			j=i;
			E[0] = E[i];
		}
	cur->con.id = j;
	switch(j){
	case 1:/*面积作为结点*/
		for(i=0;i<3;i++){
			cur->child[i] = new_node();
			cur->child[i]->con.id = j;
			cur->child[i]->con.area = i;
			cur->child[i]->con.price = cur->con.price;
			cur->child[i]->con.is_cantonal = cur->con.is_cantonal;
			cur->child[i]->con.is_old = cur->con.is_old;
			create(cur->child[i]);
		}
		break;
	case 2:/*单价作为结点*/
		for(i=0;i<3;i++){
			cur->child[i] = new_node();
			cur->child[i]->con.id = j;
			cur->child[i]->con.area = cur->con.area;
			cur->child[i]->con.price = i;
			cur->child[i]->con.is_cantonal = cur->con.is_cantonal;
			cur->child[i]->con.is_old = cur->con.is_old;
			create(cur->child[i]);
		}
		break;
	case 3:/*内环内作为结点*/
		for(i=0;i<2;i++){
			cur->child[i] = new_node();
			cur->child[i]->con.id = j;
			cur->child[i]->con.area = cur->con.area;
			cur->child[i]->con.price = cur->con.price;
			cur->child[i]->con.is_cantonal = i;
			cur->child[i]->con.is_old = cur->con.is_old;
			create(cur->child[i]);
		}
		break;
	case 4:/*房龄作为结点*/
		for(i=0;i<2;i++){
			cur->child[i] = new_node();
			cur->child[i]->con.id = j;
			cur->child[i]->con.area = cur->con.area;
			cur->child[i]->con.price = cur->con.price;
			cur->child[i]->con.is_cantonal = cur->con.is_cantonal;
			cur->child[i]->con.is_old = i;
			create(cur->child[i]);
		}
		break;
	}/*end switch*/
}

int predict(DATA * t){
	NODE * cur = root;
	while(cur){
		switch(cur->con.id){
		case 1:/*当前结点检测面积参数*/
			if (cur->result != -1) return cur->result;
			cur = cur->child[t->area];
			break;
		case 2:/*当前结点检测单价*/
			if (cur->result != -1) return cur->result;
			cur = cur->child[t->price];
			break;
		case 3:/*当前结点检测内环内*/
			if (cur->result != -1) return cur->result;
			cur = cur->child[t->is_cantonal];
			break;
		case 4:/*当前结点检测房龄*/
			if (cur->result != -1) return cur->result;
			cur = cur->child[t->is_old];
			break;
		}
	}
	return -1;
}