c4.5.c

通过C4.5 的实现可以进行构建决策树 来进行有效的分类

/*************************************************************************/
/*									 */
/*	Main routine, c4.5						 */
/*	------------------						 */
/*									 */
/*************************************************************************/


#include "defns.i"
#include "types.i"

#include <stdlib.h>

    /*  External data, described in extern.i  */

short		MaxAtt, MaxClass, MaxDiscrVal = 2;

ItemNo		MaxItem;

Description	*Item;

DiscrValue	*MaxAttVal;

char		*SpecialStatus;

String		*ClassName,
		*AttName,
		**AttValName,
		FileName = "DF";

short		VERBOSITY = 0,
		TRIALS    = 10;

Boolean		GAINRATIO  = true,
		SUBSET     = false,
		BATCH      = true,
		UNSEENS    = false,
		PROBTHRESH = false;

ItemNo		MINOBJS   = 2,
		WINDOW    = 0,
		INCREMENT = 0;

float		CF = 0.25;

Tree		*Pruned;

Boolean		AllKnown = true;
extern Tree	DecisionTree = NULL;
 void   PrintHeader(char * Title);

int    getopt(int Argc, char **Argv,char * Str);
void    GetNames();
void    GetData(String Extension);
void    OneTree();
short BestTree();
void    SoftenThresh(Tree T);
void    PrintTree(Tree T);
void    SaveTree(    Tree T,String Extension);
void   Evaluate(Boolean CMInfo,short Saved);
void    InterpretTree();
int m_idum=0;
double ran1(int* pidum)
{
	int idum=* pidum;
	const int IA=16807,IM=2147483647,IQ=127773,IR=2836,NTAB=32;
	const int NDIV=(1+(IM-1)/NTAB);
	const double EPS=3.0e-16,AM=1.0/IM,RNMX=(1.0-EPS);
	static int iy=0;
	static int iv[32];
	int j,k;
	double temp;
	
	if ( idum <= 0 || !iy) {
		if (- idum < 1) idum=1;
		else idum = -idum;
		for (j=NTAB+7;j>=0;j--) {
			k=idum/IQ;
			idum=IA*(idum-k*IQ)-IR*k;
			if (idum < 0) idum += IM;
			if (j < NTAB) iv[j] = idum;
		}
		iy=iv[0];
	}
	k=idum/IQ;
	idum=IA*(idum-k*IQ)-IR*k;
	if (idum < 0) idum += IM;
	j=iy/NDIV;
	iy=iv[j];
	iv[j] = idum;
	* pidum=idum;
	if ((temp=AM*iy) > RNMX) return RNMX;
	else return temp;
}

double random()
{
	return ran1(&m_idum);
}
void init_random(int seed)
{
	m_idum=seed;
}

int    main(int Argc,char ** Argv)
{
	int j;
    int o;
    extern char *optarg;
    extern int optind;
    Boolean FirstTime=true;
    short Best;
		Tree *t;

    PrintHeader("decision tree generator");

    /*  Process options  */

    while ( (o = getopt(Argc, Argv, "f:bupv:t:w:i:gsm:c:")) != EOF )
    {
		if ( FirstTime )
		{
			printf("\n    Options:\n");
			FirstTime = false;
		}

		switch (o)
		{
		case 'f':   FileName = optarg;
				printf("\tFile stem <%s>\n", FileName);
				break;
		case 'b':   BATCH = true;
				printf("\tWindowing disabled (now the default)\n");
				break;
		case 'u':   UNSEENS = true;
				printf("\tTrees evaluated on unseen cases\n");
				break;
		case 'p':   PROBTHRESH = true;
				printf("\tProbability thresholds used\n");
				break;
		case 'v':   VERBOSITY = atoi(optarg);
				printf("\tVerbosity level %d\n", VERBOSITY);
				break;
		case 't':   TRIALS = atoi(optarg);
				printf("\tWindowing enabled with %d trials\n", TRIALS);
				Check(TRIALS, 1, 10000);
				BATCH = false;
				break;
		case 'w':   WINDOW = atoi(optarg);
				printf("\tInitial window size of %d items\n", WINDOW);
				Check(WINDOW, 1, 1000000);
				BATCH = false;
				break;
		case 'i':   INCREMENT = atoi(optarg);
				printf("\tMaximum window increment of %d items\n",
				   INCREMENT);
				Check(INCREMENT, 1, 1000000);
				BATCH = false;
				break;
		case 'g':   GAINRATIO = false;
				printf("\tGain criterion used\n");
				break;
		case 's':   SUBSET = true;
				printf("\tTests on discrete attribute groups\n");
				break;
		case 'm':   MINOBJS = atoi(optarg);
				printf("\tSensible test requires 2 branches with >=%d cases\n",
					MINOBJS);
				Check(MINOBJS, 1, 1000000);
				break;
		case 'c':   CF = (float)atof(optarg);
				printf("\tPruning confidence level %g%%\n", CF);
				Check(CF, Epsilon, 100);
				CF /= 100;
				break;
		case '?':   printf("unrecognised option\n");
				exit(1);
		}
    }

    /*  Initialise  */

    GetNames();
    GetData(".data");
    printf("\nRead %d cases (%d attributes) from %s.data\n",
	   MaxItem+1, MaxAtt+1, FileName);

    /*  Build decision trees  */

    if ( BATCH )
    {
	TRIALS = 1;
	OneTree();
	Best = 0;
    }
    else
    {
    	Best = BestTree();
    }

    /*  Soften thresholds in best tree  */

    if ( PROBTHRESH )
    {
		printf("Softening thresholds");
		if ( ! BATCH ) printf(" for best tree from trial %d", Best);
		printf("\n");
		SoftenThresh(Pruned[Best]);
		printf("\n");
		PrintTree(Pruned[Best]);
    }

    /*  Save best tree  */

    if ( BATCH || TRIALS == 1 )
    {
	printf("\nTree saved\n");
    }
    else
    {
	printf("\nBest tree from trial %d saved\n", Best);
    }
    SaveTree(Pruned[Best], ".tree");

    /*  Evaluation  */

    printf("\n\nEvaluation on training data (%d items):\n", MaxItem+1);
    Evaluate(false, Best);

	t = Pruned[Best]->Branch;
/*
	DecisionTree = Pruned[Best]; 
	
	while ( true )
    {
		InterpretTree();
    }
*/
    if ( UNSEENS )
    {   
        GetData(".test");
        printf("\nEvaluation on test data (%d items):\n", MaxItem+1);
        Evaluate(true, Best);
    }
	
	
    exit(0);
}