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

/*************************************************************************/
/*                                                                       */
/*      Evaluation of the subsetting of a discrete attribute             */
/*      ----------------------------------------------------             */
/*                                                                       */
/*************************************************************************/


#include "buildex.i"


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

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

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



/*************************************************************************/
/*                                                                       */
/*  Evaluate subsetting a discrete attribute and form the chosen         */
/*  subsets Subset[Att][], setting Subsets[Att] to the number of         */
/*  subsets, and the Info[] and Gain[] of a test on the attribute        */
/*                                                                       */
/*************************************************************************/


    EvalSubset(Att, Fp, Lp, Items)
/*  ----------  */ 
    Attribute Att;
    ItemNo Fp, Lp; 
    ItemCount Items;
{ 
    DiscrValue V1, V2, BestV1, BestV2, Barred;
    ItemCount KnownItems;
    ClassNo c;
    float BaseInfo, MinGain, ThisGain, ThisInfo,
        Val, BestVal, BestGain, BestInfo,
        PrevVal, PrevGain, PrevInfo,
        DiscrKnownBaseInfo(), Worth(), ComputeGain(), TotalInfo();
    short Blocks=0, MissingValues=0, ReasonableSubsets, Bytes, b;
    Boolean MergedSubsets = false;
    int SaveMINOBJS;

    SaveMINOBJS = MINOBJS;
    MINOBJS = 1;

    /*  First compute Freq[][], ValFreq[], base info, and the gain
        and total info of a split on discrete attribute Att  */

    ComputeFrequencies(Att, Fp, Lp);

    KnownItems = Items - ValFreq[0];
    if ( KnownItems < Epsilon )
    {
        Verbosity(2) printf("\tAtt %s: no known values\n", AttName[Att]);

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

    BaseInfo = DiscrKnownBaseInfo(KnownItems, MaxAttVal[Att]);

    PrevGain = ComputeGain(BaseInfo, UnknownRate[Att], MaxAttVal[Att],KnownItems);
    PrevInfo = TotalInfo(ValFreq, 0, MaxAttVal[Att]) / Items;
    PrevVal = Worth(PrevInfo, PrevGain, Epsilon);

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

        Verbosity(3) PrintDistribution(Att, MaxAttVal[Att], true);

        printf("\tinf %.3f, gain %.3f, val=%.3f\n",
                PrevInfo, PrevGain, PrevVal);
    }

    /*  Eliminate unrepresented attribute values from Freq[] and ValFreq[]
        and form a separate subset for each represented attribute value  */

    Bytes = (MaxAttVal[Att]>>3) + 1;
    ClearBits(Bytes, Subset[Att][0]);

    ForEach(V1, 1, MaxAttVal[Att])
    {
        if ( ValFreq[V1] > 0.5 )
        {
            if ( ++Blocks < V1 )
            {
                ValFreq[Blocks] = ValFreq[V1];
                ForEach(c, 0, MaxClass)
                {
                    Freq[Blocks][c] = Freq[V1][c];
                }
            }
            ClearBits(Bytes, Subset[Att][Blocks]);
            SetBit(V1, Subset[Att][Blocks]);
        }
        else
        {
            SetBit(V1, Subset[Att][0]);
            MissingValues++;
        }
    }

    /*  Merge any single-class subsets with others of the same class  */
    /*  Note: have ValFreq[V] > 0 for all V  */

    ForEach(V1, 1, Blocks-1)
    {
        for ( c = 0 ; Freq[V1][c] < 0.1 ; c++ )
            ;

        if ( Freq[V1][c] < ValFreq[V1] - 0.1 ) continue;

        /*  Now have a single class -- look for others  */

        for ( V2 = V1+1 ; V2 <= Blocks ; )
        {
            if ( Freq[V2][c] < ValFreq[V2] - 0.1 )
            {
                V2++;
            }
            else
            {
                /*  Merge these subsets  */

                Combine(V1, V2, Blocks);

                ForEach(b, 0, Bytes-1)
                {
                    Subset[Att][V1][b] |= Subset[Att][V2][b];
                    Subset[Att][V2][b] = Subset[Att][Blocks][b];
                }

                Blocks--;
                MergedSubsets = true;
            }
        }
    }

    if ( MergedSubsets )
    {
        PrevGain = ComputeGain(BaseInfo, UnknownRate[Att], Blocks, KnownItems);
        PrevInfo = TotalInfo(ValFreq, 0, Blocks) / Items;
        PrevVal = Worth(PrevInfo, PrevGain, Epsilon);

        Verbosity(2)
        {
            printf("\tAfter merging single-class subsets:");

            Verbosity(3) PrintDistribution(Att, Blocks, false);

            printf("\tinf %.3f, gain %.3f, val=%.3f\n",
                    PrevInfo, PrevGain, PrevVal);
        }
    }

    /*  Examine possible pair mergers and hill-climb  */

    MinGain = PrevGain / 2;

    while ( Blocks > 2 )
    {
        BestVal = BestV1 = 0;
        BestGain = -Epsilon;

        /*  Check reasonable subsets; if less than 3, bar mergers
            involving the largest block  */

        ReasonableSubsets = 0;
        Barred = 1;

        ForEach(V1, 1, Blocks)
        {
            if ( ValFreq[V1] >= SaveMINOBJS ) ReasonableSubsets++;

            if ( ValFreq[V1] > ValFreq[Barred] ) Barred = V1;
        }

        if ( ReasonableSubsets >= 3 ) Barred = 0;

        /*  For each possible pair of values, calculate the gain and
            total info of a split in which they are treated as one.
            Keep track of the pair with the best gain.  */

        ForEach(V1, 1, Blocks-1)
        {
            ForEach(V2, V1+1, Blocks)
            {
                if ( V1 == Barred || V2 == Barred ) continue;

                Combine(V1, V2, Blocks);

                ThisGain = ComputeGain(BaseInfo, UnknownRate[Att],
                                        Blocks-1, KnownItems);
                ThisInfo = TotalInfo(ValFreq, 0, Blocks-1) / Items;
                Val      = Worth(ThisInfo, ThisGain, Epsilon);

                Verbosity(4)
                {
                    printf("\tcombine %d %d info %.3f gain %.3f val %.3f",
                           V1, V2, ThisInfo, ThisGain, Val);
                    PrintDistribution(Att, Blocks-1, false);
                }

                /*  Force a split if
                        less than two reasonable subsets, or
                        using GAIN criterion
                    Prefer this split to the previous one if
                        gain >= MinGain (and previous < MinGain), or
                        val >= previous best val  */

                if ( ThisGain >= MinGain && BestGain < MinGain ||
                     Val >= BestVal ||
                     ! BestV1 && ( ! GAINRATIO || ReasonableSubsets < 2 ) )
                {
                    BestVal  = Val;
                    BestGain = ThisGain;
                    BestInfo = ThisInfo;
                    BestV1   = V1;
                    BestV2   = V2;
                }

                Uncombine(V1, V2);
            }
        }

        if ( GAINRATIO &&
             ReasonableSubsets >= 2 &&
             ( ! BestV1 ||
               BestVal < PrevVal + 1E-5 ||
               BestVal == PrevVal && BestGain < PrevGain ) ) break;

        PrevGain = BestGain;
        PrevInfo = BestInfo;
        PrevVal = BestVal;

        Combine(BestV1, BestV2, Blocks);

        ForEach(b, 0, Bytes-1)
        {
            Subset[Att][BestV1][b] |= Subset[Att][BestV2][b];
            Subset[Att][BestV2][b] = Subset[Att][Blocks][b];
        }

        Blocks--;

        Verbosity(2)
        {
            printf("\t\tform subset ");
            PrintSubset(Att, Subset[Att][BestV1]);
            printf(": %d subsets, inf %.3f, gain %.3f, val %.3f\n",
                   Blocks, BestInfo, BestGain, BestVal);
            Verbosity(3)
            {
                printf("\t\tcombine %d, %d", BestV1, BestV2);
                PrintDistribution(Att, Blocks, false);
            }
        }
    }

    MINOBJS = SaveMINOBJS;

    if ( PrevVal <= 0 )
    {
        Gain[Att] = -Epsilon;
        Info[Att] = 0;
    }
    else
    {
        Gain[Att] = ComputeGain(BaseInfo, UnknownRate[Att], Blocks, KnownItems);
        Info[Att] = PrevInfo;

        if ( MissingValues )
        {
            Blocks++;
            CopyBits(Bytes, Subset[Att][0], Subset[Att][Blocks]);
        }

        Subsets[Att] = Blocks;

        Verbosity(2) printf("\tFinal subsets:");
        Verbosity(3) PrintDistribution(Att, Blocks, false);
        Verbosity(2)
            printf("\tinf %.3f gain %.3f val %.3f\n", 
                   Info[Att], Gain[Att], Worth(Info[Att], Gain[Att], Epsilon));
    }
}



/*************************************************************************/
/*                                                                       */
/*  Combine the distribution figures of discrete attribute values        */
/*  x and y, putting the combined figures in Freq[x][] and               */
/*  ValFreq[x][], and saving old values in Slice1 and Slice2             */
/*                                                                       */
/*************************************************************************/


    Combine(x, y, Last)
/*  -------  */
    DiscrValue x, y, Last;
{
    ClassNo c;

    ForEach(c, 0, MaxClass)
    {
        Slice1[c] = Freq[x][c];
        Slice2[c] = Freq[y][c];

        Freq[x][c] += Freq[y][c];
        Freq[y][c]  = Freq[Last][c];
    }

    Slice1[MaxClass+1] = ValFreq[x];
    Slice2[MaxClass+1] = ValFreq[y];

    ValFreq[x] += ValFreq[y];
    ValFreq[y]  = ValFreq[Last];
}



/*************************************************************************/
/*                                                                       */
/*  Restore old class distribution figures of discrete attribute         */
/*  values x and y from Slice1 and Slice2                                */
/*                                                                       */
/*************************************************************************/


    Uncombine(x, y)
/*  ---------  */
    DiscrValue x, y;
{
    ClassNo c;

    ForEach(c, 0, MaxClass)
    {
        Freq[x][c] = Slice1[c];
        Freq[y][c] = Slice2[c];
    }

    ValFreq[x] = Slice1[MaxClass+1];
    ValFreq[y] = Slice2[MaxClass+1];
}



/*************************************************************************/
/*                                                                       */
/*  Print the values of attribute Att which are in the subset Ss         */
/*                                                                       */
/*************************************************************************/


    PrintSubset(Att, Ss)
/*  -----------  */
    Attribute Att;
    Set Ss;
{
    DiscrValue V1;
    Boolean First=true;

    ForEach(V1, 1, MaxAttVal[Att])
    {
        if ( In(V1, Ss) )
        {
            if ( First )
            {
                First = false;
            }
            else
            {
                printf(", ");
            }

            printf("%s", AttValName[Att][V1]);
        }
    }
}



/*************************************************************************/
/*                                                                       */
/*  Construct and return a node for a test on a subset of values         */
/*                                                                       */
/*************************************************************************/


    SubsetTest(Node, Att)
/*  -----------  */
    Tree Node;
    Attribute Att;
{ 
    ItemCount CountItems();
    short S, Bytes;

    Sprout(Node, Subsets[Att]);

    Node->NodeType      = BrSubset;
    Node->Tested        = Att;
    Node->Errors        = 0;
    
    Bytes = (MaxAttVal[Att]>>3) + 1;
    Node->Subset = (Set *) calloc(Subsets[Att] + 1, sizeof(Set));
    ForEach(S, 1, Node->Forks)
    {
        Node->Subset[S] = (Set) malloc(Bytes);
        CopyBits(Bytes, Subset[Att][S], Node->Subset[S]);
    }
}