trees.cpp

计算机人工智能方面的决策树方法 c4.5

/*************************************************************************/
/*                                                                       */
/*      Routines for displaying, building, saving and restoring trees    */
/*      -------------------------------------------------------------    */
/*                                                                       */
/*************************************************************************/


#include "defns.h"
#include "c45types.h"
#include "extern.h"


#define Tab             "|   "
#define TabSize         4
#define Width           80      /* approx max width of printed trees */

	/*  If lines look like getting too long while a tree is being
	    printed, subtrees are broken off and printed separately after
	    the main tree is finished    */

int   Subtree;                /* highest subtree to be printed */
Tree    Subdef[500];            /* pointers to subtrees */

FILE    *Tf = 0, *fopen();      /* file pointer for tree i/o */
char    Fn[500];                /* file name */

int InCount;
int OutCount;

/*************************************************************************/
/*                                                                       */
/*      Display entire decision tree T                                   */
/*                                                                       */
/*************************************************************************/
extern FILE *fpScreen;

void    PrintTree(Tree T)
/*  ----------  */
{
    int s;

	
    Subtree=0;
    fprintf(fpScreen,"Decision Tree:\n");
	printf("Decision Tree:\n");
    Show(T, 0);
    fprintf(fpScreen,"\n");
	printf("\n");

    ForEach(s, 1, Subtree)
    {
	fprintf(fpScreen,"\n\nSubtree [S%d]\n", s);
	printf("\n\nSubtree [S%d]\n", s);
	Show(Subdef[s], 0);
	fprintf(fpScreen,"\n");
	printf("\n");
    }
    fprintf(fpScreen,"\n");
	printf("\n");
}



/*************************************************************************/
/*                                                                       */
/*      Display the tree T with offset Sh                                */
/*                                                                       */
/*************************************************************************/


void    Show(Tree T,int  Sh)
/*  ---- */
{
    DiscrValue v, MaxV;

    if ( T->NodeType )
    {
	/*  See whether separate subtree needed  */

	if ( T != Nil && Sh * TabSize + MaxLine(T) > Width )
	{
	    if ( Subtree < 99 )
	    {
		Subdef[++Subtree] = T;
		fprintf(fpScreen,"[S%d]", Subtree);
		printf("[S%d]", Subtree);
	    }
	    else
	    {
		fprintf(fpScreen,"[S??]");
		printf("[S??]");
	    }
	}
	else
	{
	    MaxV = T->Forks;

	    /*  Print simple cases first */

	    ForEach(v, 1, MaxV)
	    {
		if ( ! T->Branch[v]->NodeType )
		{
		    ShowBranch(Sh, T, v);
		}
	    }

	    /*  Print subtrees  */

	    ForEach(v, 1, MaxV)
	    {
		if ( T->Branch[v]->NodeType )
		{
		    ShowBranch(Sh, T, v);
		}
	    }
	}
    }
    else
    {
	fprintf(fpScreen," %s (%.1f", ClassName[T->Leaf], T->Items);
	printf(" %s (%.1f", ClassName[T->Leaf], T->Items);	
	if ( T->Errors > 0 ) 
	{
		fprintf(fpScreen,"/%.1f", T->Errors);
		printf("/%.1f", T->Errors);
	}
	fprintf(fpScreen,")");
	printf(")");
    }
}



/*************************************************************************/
/*                                                                       */
/*      Print a node T with offset Sh, branch value v, and continue      */
/*                                                                       */
/*************************************************************************/


void    ShowBranch(int Sh, Tree T, DiscrValue v)
/*  -----------  */
{
    DiscrValue Pv, Last;
    Attribute Att;
    Boolean FirstValue;
    int TextWidth, Skip, Values=0, i;
    
    Att = T->Tested;

    switch ( T->NodeType )
    {
	case BrDiscr:

	    Indent(Sh, Tab);

	    fprintf(fpScreen,"%s = %s:", AttName[Att], AttValName[Att][v]);
		printf("%s = %s:", AttName[Att], AttValName[Att][v]);
	    break;

	case ThreshContin:

	    Indent(Sh, Tab);

	    fprintf(fpScreen,"%s %s %g ",
		    AttName[Att], ( v == 1 ? "<=" : ">" ), T->Cut);

		printf("%s %s %g ",
		    AttName[Att], ( v == 1 ? "<=" : ">" ), T->Cut);

	    if ( T->Lower != T->Upper )
	    {
		fprintf(fpScreen,"[%g,%g]", T->Lower, T->Upper);
		printf("[%g,%g]", T->Lower, T->Upper);
	    }

	    fprintf(fpScreen,":");
		printf(":");
	    break;

	case BrSubset:

	    /*  Count values at this branch  */

	    ForEach(Pv, 1, MaxAttVal[Att])
	    {
		if ( In(Pv, T->Subset[v]) )
		{
		    Last = Pv;
		    Values++;
		}
	    }
	    if ( ! Values ) return;

	    Indent(Sh, Tab);

	    if ( Values == 1 )
	    {
		fprintf(fpScreen,"%s = %s:", AttName[Att], AttValName[Att][Last]);
		printf("%s = %s:", AttName[Att], AttValName[Att][Last]);
		break;
	    }

	    fprintf(fpScreen,"%s in {", AttName[Att]);
		printf("%s in {", AttName[Att]);
	    FirstValue = true;
	    Skip = TextWidth = strlen(AttName[Att]) + 5;

	    ForEach(Pv, 1, MaxAttVal[Att])
	    {
		if ( In(Pv, T->Subset[v]) )
		{
		    if ( ! FirstValue &&
			 TextWidth + strlen(AttValName[Att][Pv]) + 11 > Width )
		    {
			Indent(Sh, Tab);
			ForEach(i, 1, Skip) putchar(' ');

			TextWidth = Skip;
			FirstValue = true;
		    }

		    fprintf(fpScreen,"%s%c", AttValName[Att][Pv], Pv == Last ? '}' : ',');
			printf("%s%c", AttValName[Att][Pv], Pv == Last ? '}' : ',');
		    TextWidth += strlen(AttValName[Att][Pv]) + 1;
		    FirstValue = false;
		}
	    }
	    //putchar(':');
    }

    Show(T->Branch[v], Sh+1);
}



/*************************************************************************/
/*                                                                       */
/*      Find the maximum single line size for non-leaf subtree St.       */
/*      The line format is                                               */
/*                      <attribute> <> X.xx:[ <class (<Items>)], or      */
/*                      <attribute> = <DVal>:[ <class> (<Items>)]        */
/*                                                                       */
/*************************************************************************/


int MaxLine(Tree St)
/*    --------  */
{
    Attribute a;
    DiscrValue v, MaxV, Next;
    int Ll, MaxLl=0;

    a = St->Tested;

    MaxV = St->Forks;
    ForEach(v, 1, MaxV)
    {
	Ll = ( St->NodeType == 2 ? 4 : strlen(AttValName[a][v]) ) + 1;

	/*  Find the appropriate branch  */

	Next = v;

	if ( ! St->Branch[Next]->NodeType )
	{
	    Ll += strlen(ClassName[St->Branch[Next]->Leaf]) + 6;
	}
	MaxLl = Max(MaxLl, Ll);
    }

    return strlen(AttName[a]) + 4 + MaxLl;
}



/*************************************************************************/
/*                                                                       */
/*      Indent Sh columns                                                */
/*                                                                       */
/*************************************************************************/

void    Indent(int Sh, char *Mark)
/*  ------  */
{
    fprintf(fpScreen,"\n");
	printf("\n");
    while ( Sh-- )
	{
		fprintf(fpScreen,"%s", Mark);
		printf("%s", Mark);
	}
}



/*************************************************************************/
/*                                                                       */
/*      Save entire decision tree T in file with extension Extension     */
/*                                                                       */
/*************************************************************************/


void    SaveTree(Tree T, String Extension)
/*  ---------  */
{
    static char *LastExt="";

    if ( strcmp(LastExt, Extension) )
    {
	LastExt = Extension;

	if ( Tf ) fclose(Tf);

	strcpy(Fn, FileName);
	strcat(Fn, Extension);
	if ( ! ( Tf = fopen(Fn, "wb") ) )
	    Error(0, Fn, " for writing");
    }

	putc('\n', Tf);
	OutCount=0;
    OutTree(T);
}



/*************************************************************************/
/*                                                                       */
/*      Save tree T as characters                                        */
/*                                                                       */
/*************************************************************************/


void    OutTree(Tree T)
/*  --------  */
{
    DiscrValue v;