classify.cpp

One kind of decision-making tree algorithm, can be seen as one kind data mining algorithm ,find the

/*************************************************************************/
/*                                                                       */
/*  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;
    } 
}