classify.cpp

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

/*************************************************************************/
/*                                                                       */
/*  Determine the class of a case description from a decision tree       */
/*  --------------------------------------------------------------       */
/*                                                                       */
/*************************************************************************/


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

double   *ClassSum=Nil;          /* ClassSum[c] = total weight of class c */

extern FILE *fpScreen;

/*************************************************************************/
/*                                                                       */
/*  Categorize a case description using the given decision tree          */
/*                                                                       */
/*************************************************************************/


ClassNo Category(Description CaseDesc, Tree DecisionTree) 
/*       --------  */
{ 
    ClassNo c, BestClass;

    if ( ! ClassSum )
    {
	ClassSum = (double *) malloc((MaxClass+1) * sizeof(double));
    }

    ForEach(c, 0, MaxClass)
    {
	ClassSum[c] = 0;
    }

    Classify(CaseDesc, DecisionTree, 1.0);

    BestClass = 0;
    ForEach(c, 0, MaxClass)
    {
		Verbosity(5) 
		{
			fprintf(fpScreen,"class %s weight %.2f\n", ClassName[c], ClassSum[c]);
			printf("class %s weight %.2f\n", ClassName[c], ClassSum[c]);
		}

		if ( ClassSum[c] > ClassSum[BestClass] ) BestClass = c;
    }

    return BestClass;
}



/*************************************************************************/
/*                                                                       */
/*  Classify a case description using the given subtree by adjusting     */
/*  the value ClassSum for each class                                    */
/*                                                                       */
/*************************************************************************/


void Classify(Description CaseDesc, Tree T, double Weight)
/*  --------  */
{
    DiscrValue v, dv;
    double Cv;
    Attribute a;
    ClassNo c;

    switch ( T->NodeType )
    {
	case 0:  /* leaf */

	    if ( T->Items > 0 )
	    {
		/*  Update from ALL classes  */

		ForEach(c, 0, MaxClass)
		{
		    if ( T->ClassDist[c] )
		    {
			ClassSum[c] += Weight * T->ClassDist[c] / T->Items;
		    }
		}
	    }
	    else
	    {
		ClassSum[T->Leaf] += Weight;
	    }

	    return;

	case BrDiscr:  /* test of discrete attribute */

	    a = T->Tested;
	    v = DVal(CaseDesc, a);

	    if ( v && v <= T->Forks )   /*  Make sure not new discrete value  */
	    {
		Classify(CaseDesc, T->Branch[v], Weight);
	    }
	    else
	    {
		ForEach(v, 1, T->Forks)
		{
		    Classify(CaseDesc, T->Branch[v], 
			     (Weight * T->Branch[v]->Items) / T->Items);
		}
	    }

	    return;

	case ThreshContin:  /* test of continuous attribute */

	    a = T->Tested;
	    Cv = CVal(CaseDesc, a);

	    if ( Cv == Unknown )
	    {
		ForEach(v, 1, 2)
		{
		    Classify(CaseDesc, T->Branch[v], 
			     (Weight * T->Branch[v]->Items) / T->Items);
		}
	    }
	    else
	    {
		v = ( Cv <= T->Cut ? 1 : 2 );
		Classify(CaseDesc, T->Branch[v], Weight);
	    }

	    return;

	case BrSubset:  /* subset test on discrete attribute  */

	    a = T->Tested;
	    dv = DVal(CaseDesc, a);

	    if ( dv )
	    {
		ForEach(v, 1, T->Forks)
		{
		    if ( In(dv, T->Subset[v]) )
		    {
			Classify(CaseDesc, T->Branch[v], Weight);

			return;
		    }
		}
	    }

	    /*  Value unknown or not found in any of the subsets  */

	    ForEach(v, 1, T->Forks)
	    {
		Classify(CaseDesc, T->Branch[v], 
			 (Weight * T->Branch[v]->Items) / T->Items);
	    }

	    return;
    } 
}