trees.cpp

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

    int Bytes;

    StreamOut((char *) &T->NodeType, sizeof(int));
    StreamOut((char *) &T->Leaf, sizeof(ClassNo));
    StreamOut((char *) &T->Items, sizeof(ItemCount));
    StreamOut((char *) &T->Errors, sizeof(ItemCount));
    StreamOut((char *) T->ClassDist, (MaxClass + 1) * sizeof(ItemCount));

    if ( T->NodeType )
    {
	StreamOut((char *) &T->Tested, sizeof(Attribute));
	StreamOut((char *) &T->Forks, sizeof(int));

	switch ( T->NodeType )
	{
	    case BrDiscr:
		break;

	    case ThreshContin:
		StreamOut((char *) &T->Cut, sizeof(double));
		StreamOut((char *) &T->Lower, sizeof(double));
		StreamOut((char *) &T->Upper, sizeof(double));
		break;

	    case BrSubset:
		Bytes = (MaxAttVal[T->Tested]>>3) + 1;
		ForEach(v, 1, T->Forks)
		{
		    StreamOut((char *) T->Subset[v], Bytes);
		}
		break;
	}

	ForEach(v, 1, T->Forks)
	{
	    OutTree(T->Branch[v]);
	}
    }
}



/*************************************************************************/
/*                                                                       */
/*      Retrieve entire decision tree with extension Extension           */
/*                                                                       */
/*************************************************************************/


Tree GetTree(String Extension)
/*   --------  */
{
    Tree InTree();
    static char *LastExt="";

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

	if ( Tf ) fclose(Tf);

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

    if ( ! Tf  || getc(Tf) == EOF ) return Nil;

	InCount=0;
    return InTree();
}



/*************************************************************************/
/*                                                                       */
/*      Retrieve tree from saved characters                              */
/*                                                                       */
/*************************************************************************/


Tree InTree()
/*   -------  */
{
	Tree T;
    DiscrValue v;
    int Bytes;

    T = (Tree) malloc(sizeof(TreeRec));
	if (T==NULL) 
	{
		fprintf(fpScreen,"Low Memory!\n");
		printf("Low Memory!\n");
		exit(1);
	}

    StreamIn((char *) &T->NodeType, sizeof(int));
    StreamIn((char *) &T->Leaf, sizeof(ClassNo));
    StreamIn((char *) &T->Items, sizeof(ItemCount));
    StreamIn((char *) &T->Errors, sizeof(ItemCount));

    T->ClassDist = (ItemCount *) calloc(MaxClass+1, sizeof(ItemCount));
	
	if (T->ClassDist==NULL) 
	{
		fprintf(fpScreen,"Low Memory!\n");
		printf("Low Memory!\n");
		exit(1);
	}

    StreamIn((char *) T->ClassDist, (MaxClass + 1) * sizeof(ItemCount));

    if ( T->NodeType )
    {
	StreamIn((char *) &T->Tested, sizeof(Attribute));
	StreamIn((char *) &T->Forks, sizeof(int));

	switch ( T->NodeType )
	{
	    case BrDiscr:
		break;

	    case ThreshContin:
		StreamIn((char *) &T->Cut, sizeof(double));
		StreamIn((char *) &T->Lower, sizeof(double));
		StreamIn((char *) &T->Upper, sizeof(double));
		break;

	    case BrSubset:
		T->Subset = (Set *) calloc(T->Forks + 1, sizeof(Set));
		if (T->Subset==NULL) 
		{
			fprintf(fpScreen,"Low Memory!\n");
			printf("Low Memory!\n");
			exit(1);
		}


		Bytes = (MaxAttVal[T->Tested]>>3) + 1;
		ForEach(v, 1, T->Forks)
		{
		    T->Subset[v] = (Set) malloc(Bytes);
			if (T->Subset[v]==NULL) 
			{
				fprintf(fpScreen,"Low Memory!\n");
				printf("Low Memory!\n");
				exit(1);
			}

		    StreamIn((char *) T->Subset[v], Bytes);
		}
		break;
	}

	T->Branch = (Tree *) calloc(T->Forks + 1, sizeof(Tree));
	if (T->Branch==NULL) 
	{
		fprintf(fpScreen,"Low Memory!\n");
		printf("Low Memory!\n");
		exit(1);
	}

	ForEach(v, 1, T->Forks)
	{
	    T->Branch[v] = InTree();
	}
    }

    return T;
}



/*************************************************************************/
/*                                                                       */
/*      Stream characters to/from file Tf from/to an address             */
/*                                                                       */
/*************************************************************************/


void    StreamOut(String s, int n)
/*  ---------  */
{
    while ( n-- )
	{
		putc((int)*s++, Tf);
		OutCount++;
	}
}



void    StreamIn(String s,int n)
/*  ---------  */
{
    while ( n-- ) 
	{
		//*s++ = fgetc(Tf);
		fscanf(Tf,"%c",s);
		s++;
		InCount++;
	}
}



/*************************************************************************/
/*                                                                       */
/*      Free up space taken up by tree Node                              */
/*                                                                       */
/*************************************************************************/


void    ReleaseTree(Tree Node)
/*  -------  */
{
    DiscrValue v;

    if ( Node->NodeType )
    {
	ForEach(v, 1, Node->Forks)
	{
	    ReleaseTree(Node->Branch[v]);
	}

	cfree(Node->Branch);

	if ( Node->NodeType == BrSubset )
	{
	    cfree(Node->Subset);
	}

    }

    cfree(Node->ClassDist);
    cfree(Node);
}



/*************************************************************************/
/*                                                                       */
/*      Construct a leaf in a given node                                 */
/*                                                                       */
/*************************************************************************/


Tree Leaf(ItemCount *ClassFreq, ClassNo NodeClass, ItemCount Cases, ItemCount Errors)
{
    Tree Node;

    Node = (Tree) calloc(1, sizeof(TreeRec));

    Node->ClassDist = (ItemCount *) calloc(MaxClass+1, sizeof(ItemCount));
    memcpy(Node->ClassDist, ClassFreq, (MaxClass+1) * sizeof(ItemCount));
    
    Node->NodeType      = 0; 
    Node->Leaf          = NodeClass;
    Node->Items         = (double)Cases;
    Node->Errors        = (double)Errors;

    return Node; 
}



/*************************************************************************/
/*                                                                       */
/*      Insert branches in a node                                        */
/*                                                                       */
/*************************************************************************/


void    Sprout(Tree Node, DiscrValue Branches)
/*  ------  */
{
    Node->Forks = Branches;
    
    Node->Branch = (Tree *) calloc(Branches+1, sizeof(Tree));
}



/*************************************************************************/
/*                                                                       */
/*      Count the nodes in a tree                                        */
/*                                                                       */
/*************************************************************************/

	
int TreeSize(Tree Node)
/*  --------  */    
{
    int Sum=0;
    DiscrValue v;

    if ( Node->NodeType )
    {
	ForEach(v, 1, Node->Forks)
	{
	    Sum += TreeSize(Node->Branch[v]);
	}
    }

    return Sum + 1;
}



/*************************************************************************/
/*                                                                       */
/*      Return a copy of tree T                                          */
/*                                                                       */
/*************************************************************************/


Tree CopyTree(Tree T)
/*   ---------  */
{
    DiscrValue v;
    Tree New;

    New = (Tree) malloc(sizeof(TreeRec));
    memcpy(New, T, sizeof(TreeRec));

    New->ClassDist = (ItemCount *) calloc(MaxClass+1, sizeof(ItemCount));
    memcpy(New->ClassDist, T->ClassDist, (MaxClass + 1) * sizeof(ItemCount));

    if ( T->NodeType )
    {
	New->Branch = (Tree *) calloc(T->Forks + 1, sizeof(Tree));
	ForEach(v, 1, T->Forks)
	{
	    New->Branch[v] = CopyTree(T->Branch[v]);
	}
    }

    return New;
}