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