c4.5rules.c

用c++实现的决策树算法

/*************************************************************************/
/*									 */
/*  Main routine for constructing sets of production rules from trees	 */
/*  -----------------------------------------------------------------	 */
/*									 */
/*************************************************************************/


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


#include <stdlib.h>
#include <math.h>
/*  External data.  Note: uncommented variables have the same meaning
	    as for decision trees  */

short		MaxAtt, MaxClass, MaxDiscrVal;

ItemNo		MaxItem;

Description	*Item;

DiscrValue	*MaxAttVal;

char		*SpecialStatus;

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

short		VERBOSITY = 0,
		TRIALS;

Boolean		UNSEENS	  = false,
		SIGTEST	  = false,	/* use significance test in rule pruning */
		SIMANNEAL = false;	/* use simulated annealing */

float		SIGTHRESH   = 0.05f,
		CF	    = 0.25,
		REDUNDANCY  = 1.0;	/* factor that guesstimates the
					   amount of redundancy and
					   irrelevance in the attributes */

PR		*Rule;			/* current rules */

RuleNo		NRules = 0,		/* number of current rules */
		*RuleIndex;		/* rule index */

short		RuleSpace = 0;		/* space allocated for rules */

ClassNo		DefaultClass;		/* current default class */

RuleSet		*PRSet;			/* sets of rulesets */

float		AttTestBits,		/* bits to encode tested att */
		*BranchBits;		/* ditto attribute value */


 void   PrintHeader(char * Title);
 int    getopt(int Argc, char **Argv,char * Str);
 void    GetNames();
 void    GetData(String Extension);
 void   GenerateLogs();
 void    GenerateRules();
 void    EvaluateRulesets(Boolean DeleteRules);
 void   SaveRules();
 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;
 }	 
	 
void    main(int Argc, char *Argv[])
/*  ----  */
{
    int o;
    extern char *optarg;
    extern int optind;
    Boolean FirstTime=true;

    PrintHeader("rule generator");

    /*  Process options  */

    while ( (o = getopt(Argc, Argv, "f:uv:c:r:F:a")) != EOF )
    {
	if ( FirstTime )
	{
	    printf("\n    Options:\n");
	    FirstTime = false;
	}

	switch (o)
	{
	    case 'f':	FileName = optarg;
			printf("\tFile stem <%s>\n", FileName);
			break;
	    case 'u':	UNSEENS = true;
			printf("\tRulesets evaluated on unseen cases\n");
			break;
	    case 'v':	VERBOSITY = atoi(optarg);
			printf("\tVerbosity level %d\n", VERBOSITY);
			break;
	    case 'c':	CF = (float)atof(optarg);
			printf("\tPruning confidence level %g%%\n", CF);
			Check(CF, 0, 100);
			CF /= 100;
			break;
	    case 'r':	REDUNDANCY = (float)atof(optarg);
			printf("\tRedundancy factor %g\n", REDUNDANCY);
			Check(REDUNDANCY, 0, 10000);
			break;
	    case 'F':	SIGTHRESH = (float)atof(optarg);
			printf("\tSignificance test in rule pruning, ");
			printf("threshold %g%%\n", SIGTHRESH);
			Check(SIGTHRESH, 0, 100);
		 	SIGTHRESH /= 100;
			SIGTEST = true;
			break;
	    case 'a':	SIMANNEAL = true;
			printf("\tSimulated annealing for selecting rules\n");
			break;
	    case '?':	printf("unrecognised option\n");
			exit(1);
	}
    }

    /*  Initialise  */

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

    GenerateLogs();

    /*  Construct rules  */

    GenerateRules();

    /*  Evaluations  */

    printf("\n\nEvaluation on training data (%d items):\n", MaxItem+1);
    EvaluateRulesets(true);

    /*  Save current ruleset  */

    SaveRules();

    if ( UNSEENS )
    {
	GetData(".test");
	printf("\nEvaluation on test data (%d items):\n", MaxItem+1);
	EvaluateRulesets(false);
    }

    exit(0);
}