source: proiecte/Parallel-DT/R8/Src/build.c @ 26

/*************************************************************************/
/*                                                                       */
/*    Central tree-forming algorithm incorporating all criteria          */
/*    ---------------------------------------------------------          */
/*                                                                       */
/*************************************************************************/


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


ItemCount
        *Weight,        /* Weight[i]  = current fraction of item i */
        **Freq,         /* Freq[x][c] = no. items of class c with outcome x */
        *ValFreq,       /* ValFreq[x]   = no. items with outcome x */
        *ClassFreq;     /* ClassFreq[c] = no. items of class c */

float
        *Gain,          /* Gain[a] = info gain by split on att a */
        *Info,          /* Info[a] = potential info of split on att a */
        *Bar,           /* Bar[a]  = best threshold for contin att a */
        *UnknownRate;   /* UnknownRate[a] = current unknown rate for att a */

Boolean
        *Tested,        /* Tested[a] set if att a has already been tested */
        MultiVal;       /* true when all atts have many values */


        /*  External variables initialised here  */

extern float
        *SplitGain,     /* SplitGain[i] = gain with att value of item i as threshold */
        *SplitInfo;     /* SplitInfo[i] = potential info ditto */

extern ItemCount
        *Slice1,        /* Slice1[c]    = saved values of Freq[x][c] in subset.c */
        *Slice2;        /* Slice2[c]    = saved values of Freq[y][c] */

extern Set
        **Subset;       /* Subset[a][s] = subset s for att a */

extern short
        *Subsets;       /* Subsets[a] = no. subsets for att a */



/*************************************************************************/
/*                                                                       */
/*              Allocate space for tree tables                           */
/*                                                                       */
/*************************************************************************/


    InitialiseTreeData()
/*  ------------------  */
{ 
    DiscrValue v;
    Attribute a;

    Tested      = (char *) calloc(MaxAtt+1, sizeof(char));

    Gain        = (float *) calloc(MaxAtt+1, sizeof(float));
    Info        = (float *) calloc(MaxAtt+1, sizeof(float));
    Bar         = (float *) calloc(MaxAtt+1, sizeof(float));

    Subset = (Set **) calloc(MaxAtt+1, sizeof(Set *));
    ForEach(a, 0, MaxAtt)
    {
        if ( MaxAttVal[a] )
        {
            Subset[a]  = (Set *) calloc(MaxDiscrVal+1, sizeof(Set));
            ForEach(v, 0, MaxAttVal[a])
            {
                Subset[a][v] = (Set) malloc((MaxAttVal[a]>>3) + 1);
            }
        }
    }
    Subsets = (short *) calloc(MaxAtt+1, sizeof(short));

    SplitGain = (float *) calloc(MaxItem+1, sizeof(float));
    SplitInfo = (float *) calloc(MaxItem+1, sizeof(float));

    Weight = (ItemCount *) calloc(MaxItem+1, sizeof(ItemCount));

    Freq  = (ItemCount **) calloc(MaxDiscrVal+1, sizeof(ItemCount *));
    ForEach(v, 0, MaxDiscrVal)
    {
        Freq[v]  = (ItemCount *) calloc(MaxClass+1, sizeof(ItemCount));
    }

    ValFreq = (ItemCount *) calloc(MaxDiscrVal+1, sizeof(ItemCount));
    ClassFreq = (ItemCount *) calloc(MaxClass+1, sizeof(ItemCount));

    Slice1 = (ItemCount *) calloc(MaxClass+2, sizeof(ItemCount));
    Slice2 = (ItemCount *) calloc(MaxClass+2, sizeof(ItemCount));

    UnknownRate = (float *) calloc(MaxAtt+1, sizeof(float));

    /*  Check whether all attributes have many discrete values  */

    MultiVal = true;
    if ( ! SUBSET )
    {
        for ( a = 0 ; MultiVal && a <= MaxAtt ; a++ )
        {
            if ( SpecialStatus[a] != IGNORE )
            {
                MultiVal = MaxAttVal[a] >= 0.3 * (MaxItem + 1);
            }
        }
    }
}



/*************************************************************************/
/*                                                                       */
/*              Initialise the weight of each item                       */
/*                                                                       */
/*************************************************************************/


    InitialiseWeights()
/*  -----------------  */
{
    ItemNo i;

    ForEach(i, 0, MaxItem)
    {
        Weight[i] = 1.0;
    }
}



/*************************************************************************/
/*                                                                       */
/*  Build a decision tree for the cases Fp through Lp:                   */
/*                                                                       */
/*  - if all cases are of the same class, the tree is a leaf and so      */
/*      the leaf is returned labelled with this class                    */
/*                                                                       */
/*  - for each attribute, calculate the potential information provided   */
/*      by a test on the attribute (based on the probabilities of each   */
/*      case having a particular value for the attribute), and the gain  */
/*      in information that would result from a test on the attribute    */
/*      (based on the probabilities of each case with a particular       */
/*      value for the attribute being of a particular class)             */
/*                                                                       */
/*  - on the basis of these figures, and depending on the current        */
/*      selection criterion, find the best attribute to branch on.       */
/*      Note:  this version will not allow a split on an attribute       */
/*      unless two or more subsets have at least MINOBJS items.          */
/*                                                                       */
/*  - try branching and test whether better than forming a leaf          */
/*                                                                       */
/*************************************************************************/


Tree FormTree(Fp, Lp)
/*   ---------  */
    ItemNo Fp, Lp; 
{ 
    ItemNo i, Kp, Ep, Group();
    ItemCount Cases, NoBestClass, KnownCases, CountItems();
    float Factor, BestVal, Val, AvGain=0, Worth();
    Attribute Att, BestAtt, Possible=0;
    ClassNo c, BestClass;
    Tree Node, Leaf();
    DiscrValue v;
    Boolean PrevAllKnown;

    Cases = CountItems(Fp, Lp);

    /*  Generate the class frequency distribution  */

    ForEach(c, 0, MaxClass)
    {
        ClassFreq[c] = 0;
    }
    ForEach(i, Fp, Lp)
    { 
        ClassFreq[ Class(Item[i]) ] += Weight[i];
    } 

    /*  Find the most frequent class  */

    BestClass = 0;
    ForEach(c, 0, MaxClass)
    {
        if ( ClassFreq[c] > ClassFreq[BestClass] )
        {
            BestClass = c;
        }
    }
    NoBestClass = ClassFreq[BestClass];

    Node = Leaf(ClassFreq, BestClass, Cases, Cases - NoBestClass);

    /*  If all cases are of the same class or there are not enough
        cases to divide, the tree is a leaf  */

    if ( NoBestClass == Cases  || Cases < 2 * MINOBJS )
    { 
        return Node;
    } 

    Verbosity(1)
        printf("\n%d items, total weight %.1f\n", Lp - Fp + 1, Cases);

    /*  For each available attribute, find the information and gain  */

    ForEach(Att, 0, MaxAtt) 
    { 
        Gain[Att] = -Epsilon;

        if ( SpecialStatus[Att] == IGNORE ) continue;

        if ( MaxAttVal[Att] )
        {
            /*  discrete valued attribute  */

            if ( SUBSET && MaxAttVal[Att] > 2 )
            {
                EvalSubset(Att, Fp, Lp, Cases);
            }
            else
            if ( ! Tested[Att] )
            {
                EvalDiscreteAtt(Att, Fp, Lp, Cases);
            }
        }
        else
        { 
            /*  continuous attribute  */

            EvalContinuousAtt(Att, Fp, Lp);
        } 

        /*  Update average gain, excluding attributes with very many values  */

        if ( Gain[Att] > -Epsilon &&
             ( MultiVal || MaxAttVal[Att] < 0.3 * (MaxItem + 1) ) )
        {
            Possible++;
            AvGain += Gain[Att];
        }
    } 

    /*  Find the best attribute according to the given criterion  */

    BestVal = -Epsilon;
    BestAtt = None;
    AvGain  = ( Possible ? AvGain / Possible : 1E6 );

    Verbosity(2)
    {
        if ( AvGain < 1E6 ) printf("\taverage gain %.3f\n", AvGain);
    }

    ForEach(Att, 0, MaxAtt) 
    { 
        if ( Gain[Att] > -Epsilon )
        { 
            Val = Worth(Info[Att], Gain[Att], AvGain);
            if ( Val > BestVal ) 
            { 
                BestAtt  = Att; 
                BestVal = Val;
            } 
        } 
    } 

    /*  Decide whether to branch or not  */ 

    if ( BestAtt != None )
    { 
        Verbosity(1)
        {
            printf("\tbest attribute %s", AttName[BestAtt]);
            if ( ! MaxAttVal[BestAtt] )
            {
                printf(" cut %.3f", Bar[BestAtt]);
            }
            printf(" inf %.3f gain %.3f val %.3f\n",
                   Info[BestAtt], Gain[BestAtt], BestVal);
        }       

        /*  Build a node of the selected test  */

        if ( MaxAttVal[BestAtt] )
        {
            /*  Discrete valued attribute  */

            if ( SUBSET && MaxAttVal[BestAtt] > 2 )
            {
                SubsetTest(Node, BestAtt);
            }
            else
            {
                DiscreteTest(Node, BestAtt);
            }
        }
        else
        { 
            /*  Continuous attribute  */

            ContinTest(Node, BestAtt);
        } 

        /*  Remove unknown attribute values  */

        PrevAllKnown = AllKnown;

        Kp = Group(0, Fp, Lp, Node) + 1;
        if ( Kp != Fp ) AllKnown = false;
        KnownCases = Cases - CountItems(Fp, Kp-1);
        UnknownRate[BestAtt] = (Cases - KnownCases) / (Cases + 0.001);

        Verbosity(1)
        {
            if ( UnknownRate[BestAtt] > 0 )
            {
                printf("\tunknown rate for %s = %.3f\n",
                       AttName[BestAtt], UnknownRate[BestAtt]);
            }
        }

        /*  Recursive divide and conquer  */

        ++Tested[BestAtt];

        Ep = Kp - 1;
        Node->Errors = 0;

        ForEach(v, 1, Node->Forks)
        {
            Ep = Group(v, Kp, Lp, Node);

            if ( Kp <= Ep )
            {
                Factor = CountItems(Kp, Ep) / KnownCases;

                ForEach(i, Fp, Kp-1)
                {
                    Weight[i] *= Factor;
                }

                Node->Branch[v] = FormTree(Fp, Ep);
                Node->Errors += Node->Branch[v]->Errors;

                Group(0, Fp, Ep, Node);
                ForEach(i, Fp, Kp-1)
                {
                    Weight[i] /= Factor;
                }
            }
            else
            {
                Node->Branch[v] = Leaf(Node->ClassDist, BestClass, 0.0, 0.0);
            }
        }

        --Tested[BestAtt];
        AllKnown = PrevAllKnown;

        /*  See whether we would have been no worse off with a leaf  */

        if ( Node->Errors >= Cases - NoBestClass - Epsilon )
        { 
            Verbosity(1)
                printf("Collapse tree for %d items to leaf %s\n",
                        Lp - Fp + 1, ClassName[BestClass]);

            Node->NodeType = 0;
        } 
    }
    else
    { 
        Verbosity(1)
            printf("\tno sensible splits  %.1f/%.1f\n",
                   Cases, Cases - NoBestClass);
    } 

    return Node; 
} 



/*************************************************************************/
/*                                                                       */
/*  Group together the items corresponding to branch V of a test         */
/*  and return the index of the last such                                */
/*                                                                       */
/*  Note: if V equals zero, group the unknown values                     */
/*                                                                       */
/*************************************************************************/


ItemNo Group(V, Fp, Lp, TestNode)
/*     -----  */
    DiscrValue V;
    ItemNo Fp, Lp;
    Tree TestNode;
{
    ItemNo i;
    Attribute Att;
    float Thresh;
    Set SS;
    void Swap();

    Att = TestNode->Tested;

    if ( V )
    {
        /*  Group items on the value of attribute Att, and depending
            on the type of branch  */

        switch ( TestNode->NodeType )
        {
            case BrDiscr:

                ForEach(i, Fp, Lp)
                {
                    if ( DVal(Item[i], Att) == V ) Swap(Fp++, i);
                }
                break;

            case ThreshContin:

                Thresh = TestNode->Cut;
                ForEach(i, Fp, Lp)
                {
                    if ( (CVal(Item[i], Att) <= Thresh) == (V == 1) ) Swap(Fp++, i);
                }
                break;

            case BrSubset:

                SS = TestNode->Subset[V];
                ForEach(i, Fp, Lp)
                {
                    if ( In(DVal(Item[i], Att), SS) ) Swap(Fp++, i);
                }
                break;
        }
    }
    else
    {
        /*  Group together unknown values  */

        switch ( TestNode->NodeType )
        {
            case BrDiscr:
            case BrSubset:

                ForEach(i, Fp, Lp)
                {
                    if ( ! DVal(Item[i], Att) ) Swap(Fp++, i);
                }
                break;

            case ThreshContin:

                ForEach(i, Fp, Lp)
                {
                    if ( CVal(Item[i], Att) == Unknown ) Swap(Fp++, i);
                }
                break;
        }
    }

    return Fp - 1;
}



/*************************************************************************/
/*                                                                       */
/*      Return the total weight of items from Fp to Lp                   */
/*                                                                       */
/*************************************************************************/


ItemCount CountItems(Fp, Lp)
/*        ----------  */
    ItemNo Fp, Lp;
{
    register ItemCount Sum=0.0, *Wt, *LWt;

    if ( AllKnown ) return Lp - Fp + 1;

    for ( Wt = Weight + Fp, LWt = Weight + Lp ; Wt <= LWt ; )
    {
        Sum += *Wt++;
    }

    return Sum;
}



/*************************************************************************/
/*                                                                       */
/*              Exchange items at a and b                                */
/*                                                                       */
/*************************************************************************/


void Swap(a,b)
/*   ----  */
    ItemNo a, b;
{
    register Description Hold;
    register ItemCount HoldW;

    Hold = Item[a];
    Item[a] = Item[b];
    Item[b] = Hold;

    HoldW = Weight[a];
    Weight[a] = Weight[b];
    Weight[b] = HoldW;
}