/*************************************************************************//*									 *//*	Process sets of rules						 *//*	---------------------					         *//*								         *//*************************************************************************/#include "defns.i"#include "types.i"#include "extern.i"#include "rulex.i"ItemNo	*ClassFreq,	/* ClassFreq[c]	= no. items of class c  */	*Covered,	/* Covered[i]	= no. included rules that cover item i */	*FalsePos,	/* FalsePos[c]	= no. false positives from rules					  selected for class c */	*NoRule,	/* NoRule[c]	= no. items covered by no selected rule */	*Right,		/* Right[r]	= no. correct rule firings */	*Wrong;		/* Wrong[r]	= no. incorrect rule firings */float	*Value,		/* Value[r]	= advantage attributable to rule r or					  realisable if rule r included */	SubsetValue,	/* value of best class subset so far */	CodeWeight;	/* multiplying factor for rule encodings */Boolean	*RuleIn,	/* RuleIn[r]	= true if rule r included */	*Subset,	/* best class subset so far */	**Match;	/* Match[r][i]	= true if rule r fires on item i */RuleNo	*ClassRules;	/* list of all rules for current target class */ClassNo	FocusClass;/*************************************************************************//*									 *//*  Construct an ordered subset (indexed by RuleIndex) of the current	 *//*  set of rules							 *//*									 *//*************************************************************************/    ConstructRuleset()/*  ----------------  */{    RuleNo r, OldNRules = NRules;    /*  Allocate tables  */    Right = (ItemNo *) calloc(NRules+1, sizeof(ItemNo));    Wrong = (ItemNo *) calloc(NRules+1, sizeof(ItemNo));    Value = (float *) calloc(NRules+1, sizeof(float));    RuleIn = (Boolean *) calloc(NRules+1, sizeof(Boolean));    Subset = (Boolean *) malloc((NRules+1) * sizeof(Boolean));    ClassRules = (RuleNo *) malloc((NRules+1) * sizeof(RuleNo));    ClassFreq = (ItemNo *) calloc(MaxClass+1, sizeof(ItemNo));    Covered = (ItemNo *) calloc(MaxItem+1, sizeof(ItemNo));    Match = (Boolean **) calloc(NRules+1, sizeof(Boolean *));    FalsePos = (ItemNo *) calloc(MaxClass+1, sizeof(ItemNo));    NoRule = (ItemNo *) calloc(MaxClass+1, sizeof(ItemNo));    ForEach(r, 1, NRules)    {	Match[r] = (Boolean *) calloc(MaxItem+1, sizeof(Boolean));    }    /*  Cover each class, then order the classes to give an index of rules  */    InitialiseTables();    FindRuleCodes();    CodeWeight = 0.5;    ForEach(FocusClass, 0, MaxClass)    {	CoverClass();    }    MakeIndex();    FindDefault();    /*  Clear  */    cfree(Value);    cfree(RuleIn);    cfree(ClassRules);    cfree(Subset);    cfree(Covered);    cfree(FalsePos);    cfree(NoRule);    ForEach(r, 1, OldNRules)    {	cfree(Match[r]);    }    cfree(Match);}/*************************************************************************//*									 *//*		Initialise all tables used in sifting			 *//*									 *//*************************************************************************/    InitialiseTables()/*  ----------------  */{    ItemNo i;    RuleNo r;    ClassNo c;    float Strength();    ForEach(r, 1, NRules)    {	RuleIn[r] = false;	Rule[r].Used = Rule[r].Incorrect = 0;    }    ForEach(c, 0, MaxClass)    {	ClassFreq[c] = 0;    }    ForEach(i, 0, MaxItem)    {	ClassFreq[Class(Item[i])]++;	ForEach(r, 1, NRules)	{	    Match[r][i] = Strength(Rule[r], Item[i]) > 0.1;	    if ( Match[r][i] )	    {		Rule[r].Used++;		if ( Class(Item[i]) != Rule[r].Rhs ) Rule[r].Incorrect++;	    }	}    }}/*************************************************************************//*								         *//*	Select a subset of the rules for class FocusClass	         *//*								         *//*************************************************************************/    CoverClass()/*  ----------  */{    RuleNo r, RuleCount=0;    ItemNo i;    Verbosity(1)	printf("\nClass %s\n-----\nAction  Change  Value",		ClassName[FocusClass]);    ForEach(i, 0, MaxItem)    {	Covered[i] = 0;    }    ForEach(r, 1, NRules)    {	if ( Rule[r].Rhs == FocusClass )	{	    RuleCount++;	    ClassRules[RuleCount] = r;	}    }    if ( ! RuleCount )    {	return;    }    SubsetValue = 1E10;    if ( RuleCount <= 10 )    {	AllCombinations(RuleCount);    }    else    if ( SIMANNEAL )    {	SimAnneal(RuleCount);    }    else    {	SpotSearch(RuleCount);    }    memcpy(RuleIn, Subset, NRules+1);    Verbosity(1) printf("\n\tBest value %.1f\n", SubsetValue);} /*************************************************************************//*									 *//*    Try all combinations of rules to find best value			 *//*									 *//*************************************************************************/    AllCombinations(NR)/*  ---------------  */    RuleNo NR;{    RuleNo r;    if ( ! NR )    {	CalculateValue();    }    else    {	r = ClassRules[NR];	AllCombinations(NR-1);	AddRule(r);	AllCombinations(NR-1);	DeleteRule(r);	Verbosity(1) printf("\n");    }}/*************************************************************************//*									 *//*  Find a good subset by simulated annealing				 *//*									 *//*************************************************************************/    SimAnneal(RuleCount)/*  ---------  */    RuleNo RuleCount;{    RuleNo r, OutCount;    short ri, Tries;    float Temp, Delta;    Boolean Changed;    /*  Keep dropping and adding rules until can't improve  */    for ( Temp = 1000 ; Temp > 0.001 ; Temp *= 0.95 )    {	CalculateValue();	Verbosity(2)	{	    OutCount = 0;	    ForEach(ri, 1, RuleCount)	    {		r = ClassRules[ri];		if ( ! RuleIn[r] )		{		    if ( ! (OutCount++ % 3) ) printf("\n\t\t");		    printf("%d<%d|%d=%.1f> ", r, Right[r], Wrong[r], Value[r]);		}	    }	    printf("\n\n");	}	Changed = false;	for ( Tries = 100 ; ! Changed && Tries > 0 ; Tries-- )	{	    /*  Choose a rule to add or delete  */	    ri = RuleCount * Random + 1;	    r = ClassRules[ri];	    Delta = ( RuleIn[r] ? -Value[r] : Value[r] );	    if ( Delta > 0 || Random < exp(Delta / Temp) )	    {		if ( RuleIn[r] )		{		    DeleteRule(r);		}		else		{		    AddRule(r);		}				Changed = true;	    }	}	if ( ! Changed ) break;    }    /*  Try to improve best subset so far by hill-climbing  */    Verbosity(1) printf("Polish: ");    memcpy(RuleIn, Subset, NRules+1);    HillClimb(RuleCount);}/*************************************************************************//*									 *//*  Find a good subset by repeated greedy search			 *//*									 *//*************************************************************************/    SpotSearch(RuleCount)/*  ----------  */    RuleNo RuleCount;{    RuleNo r;    short ri, Trial;    float ProbIn;    ForEach(Trial, 0, 10)    {	Verbosity(1) printf("\n    Trial %d:", Trial);	/*  Add rules randomly to the initial subset  */	ProbIn = Trial / 10.0;	ForEach(ri, 1, RuleCount)	{	    r = ClassRules[ri];	    RuleIn[r] = Random < ProbIn;	}	HillClimb(RuleCount);    }}/*************************************************************************//*									 *//*  Improve a subset of rules by adding and deleting rules		 *//*									 *//*************************************************************************/    HillClimb(RuleCount)/*  ---------  */    RuleNo RuleCount;{    RuleNo r, Bestr;    short ri, OutCount;    ItemNo i;    float Delta, BestDelta;    ForEach(i, 0, MaxItem)    {	Covered[i] = 0;    }    ForEach(ri, 1, RuleCount)    {	r = ClassRules[ri];	if ( RuleIn[r] )	{	    ForEach(i, 0, MaxItem)	    {		if ( Match[r][i] )		{		    Covered[i]++;		}	    }	}    }        /*  Add or drop rule with greatest reduction in coding cost  */    while ( true )    {	CalculateValue();	Verbosity(2)	{	    OutCount = 0;	    ForEach(ri, 1, RuleCount)	    {		r = ClassRules[ri];		if ( ! RuleIn[r] )		{		    if ( ! (OutCount++ % 3) ) printf("\n\t\t");		    printf("%d<%d|%d=%.1f> ", r, Right[r], Wrong[r], Value[r]);		}	    }	    printf("\n\n");	}	Bestr = BestDelta = 0;	ForEach(ri, 1, RuleCount)	{	    r = ClassRules[ri];	    Delta = ( RuleIn[r] ? -Value[r] : Value[r] );	    if ( Delta > BestDelta )	    {		Bestr = r;		BestDelta = Delta;	    }	}	if ( ! Bestr ) break;	if ( RuleIn[Bestr] )	{	    DeleteRule(Bestr);	}	else	{	    AddRule(Bestr);	}    }}/*************************************************************************//*								         *//*  Find the number of correct and incorrect rule firings for rules      *//*  for class FocusClass and hence determine the Value of the rules.     *//*  If best so far, remember.						 *//*								         *//*************************************************************************/    CalculateValue()/*  --------------  */{    RuleNo r, Selected=0, InCount;    ItemNo i, Times, FPos=0, FNeg=0, SumCover=0;    float BaseBits, RuleBits=0, NewBits, ExceptionBits();    ClassNo ThisClass;    Boolean *RuleMatch;    ForEach(i, 0, MaxItem)    {	ThisClass = Class(Item[i]);	if ( Covered[i] )