source: proiecte/Parallel-DT/R8/Src/contin.c @ 24

/*************************************************************************/
/*                                                                       */
/*      Evaluation of a test on a continuous valued attribute            */
/*      -----------------------------------------------------            */
/*                                                                       */
/*************************************************************************/


#include "buildex.i"


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



/*************************************************************************/
/*                                                                       */
/*  Continuous attributes are treated as if they have possible values    */
/*      0 (unknown), 1 (less than cut), 2(greater than cut)              */
/*  This routine finds the best cut for items Fp through Lp and sets     */
/*  Info[], Gain[] and Bar[]                                             */
/*                                                                       */
/*************************************************************************/


    EvalContinuousAtt(Att, Fp, Lp)
/*  -----------------  */ 
    Attribute Att;
    ItemNo Fp, Lp; 
{ 
    ItemNo i, BestI, Xp, Tries=0;
    ItemCount Items, KnownItems, LowItems, MinSplit, CountItems();
    ClassNo c;
    float AvGain=0, Val, BestVal, BaseInfo, ThreshCost,
        ComputeGain(), TotalInfo(), Worth();
    void Swap();

    Verbosity(2) printf("\tAtt %s", AttName[Att]);
    Verbosity(3) printf("\n");

    ResetFreq(2);

    /*  Omit and count unknown values */

    Items = CountItems(Fp, Lp);
    Xp = Fp;
    ForEach(i, Fp, Lp)
    {
        if ( CVal(Item[i],Att) == Unknown )
        {
            Freq[ 0 ][ Class(Item[i]) ] += Weight[i];
            Swap(Xp, i);
            Xp++;
        }
    }

    ValFreq[0] = 0;
    ForEach(c, 0, MaxClass)
    {
        ValFreq[0] += Freq[0][c];
    }

    KnownItems = Items - ValFreq[0];
    UnknownRate[Att] = 1.0 - KnownItems / Items;

    /*  Special case when very few known values  */

    if ( KnownItems < 2 * MINOBJS )
    {
        Verbosity(2) printf("\tinsufficient cases with known values\n");

        Gain[Att] = -Epsilon;
        Info[Att] = 0.0;
        return;
    }

    Quicksort(Xp, Lp, Att, Swap);

    /*  Count base values and determine base information  */

    ForEach(i, Xp, Lp)
    {
        Freq[ 2 ][ Class(Item[i]) ] += Weight[i];
        SplitGain[i] = -Epsilon;
        SplitInfo[i] = 0;
    }

    BaseInfo = TotalInfo(Freq[2], 0, MaxClass) / KnownItems;

    /*  Try possible cuts between items i and i+1, and determine the
        information and gain of the split in each case.  We have to be wary
        of splitting a small number of items off one end, as we can always
        split off a single item, but this has little predictive power.  */

    MinSplit = 0.10 * KnownItems / (MaxClass + 1);
    if ( MinSplit <= MINOBJS ) MinSplit = MINOBJS;
    else
    if ( MinSplit > 25 ) MinSplit = 25;

    LowItems = 0;
    ForEach(i, Xp, Lp - 1)
    {
        c = Class(Item[i]);
        LowItems   += Weight[i];
        Freq[1][c] += Weight[i];
        Freq[2][c] -= Weight[i];

        if ( LowItems < MinSplit ) continue;
        else
        if ( LowItems > KnownItems - MinSplit ) break;

        if ( CVal(Item[i],Att) < CVal(Item[i+1],Att) - 1E-5 )
        {
            ValFreq[1] = LowItems;
            ValFreq[2] = KnownItems - LowItems;
            SplitGain[i] = ComputeGain(BaseInfo, UnknownRate[Att], 2, KnownItems);
            SplitInfo[i] = TotalInfo(ValFreq, 0, 2) / Items;
            AvGain += SplitGain[i];
            Tries++;

            Verbosity(3)
            {   printf("\t\tCut at %.3f  (gain %.3f, val %.3f):",
                       ( CVal(Item[i],Att) + CVal(Item[i+1],Att) ) / 2,
                       SplitGain[i],
                       Worth(SplitInfo[i], SplitGain[i], Epsilon));
                       PrintDistribution(Att, 2, true);
            }
        }
    }

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

    ThreshCost = Log(Tries) / Items;

    BestVal = 0;
    BestI   = None;
    ForEach(i, Xp, Lp - 1)
    {
        if ( (Val = SplitGain[i] - ThreshCost) > BestVal )
        {
            BestI   = i;
            BestVal = Val;
        }
    }

    /*  If a test on the attribute is able to make a gain,
        set the best break point, gain and information  */ 

    if ( BestI == None )
    {
        Gain[Att] = -Epsilon;
        Info[Att] = 0.0;

        Verbosity(2) printf("\tno gain\n");
    }
    else
    {
        Bar[Att]  = (CVal(Item[BestI],Att) + CVal(Item[BestI+1],Att)) / 2;
        Gain[Att] = BestVal;
        Info[Att] = SplitInfo[BestI];

        Verbosity(2)
            printf("\tcut=%.3f, inf %.3f, gain %.3f\n",
                   Bar[Att], Info[Att], Gain[Att]);
    }
} 



/*************************************************************************/
/*                                                                       */
/*  Change a leaf into a test on a continuous attribute                  */
/*                                                                       */
/*************************************************************************/


    ContinTest(Node, Att)
/*  ----------  */
    Tree Node;
    Attribute Att;
{
    float Thresh, GreatestValueBelow();
    ItemCount CountItems();

    Sprout(Node, 2);

    Thresh = GreatestValueBelow(Att, Bar[Att]);

    Node->NodeType      = ThreshContin;
    Node->Tested        = Att;
    Node->Cut           =
    Node->Lower         =
    Node->Upper         = Thresh;
    Node->Errors        = 0;
}



/*************************************************************************/
/*                                                                       */
/*  Return the greatest value of attribute Att below threshold t         */
/*                                                                       */
/*************************************************************************/


float GreatestValueBelow(Att, t)
/*    ------------------  */
    Attribute Att;
    float t;
{
    ItemNo i;
    float v, Best;
    Boolean NotYet=true;

    ForEach(i, 0, MaxItem)
    {
        v = CVal(Item[i], Att);
        if ( v != Unknown && v <= t && ( NotYet || v > Best ) )
        {
            Best = v;
            NotYet = false;
        }
    }

    return Best;
}