siftrules.c.5

来自「vc的源代码程序的基于最小特征向量的元素的集合方法的程序源代码」· 5 代码 · 共 793 行 · 第 1/2 页

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



/*************************************************************************/
/*									 */
/*  Construct an ordered subset (indexed by RuleIndex) of the current	 */
/*  set of rules							 */
/*									 */
/*************************************************************************/


    ConstructRuleset()
/*  ----------------  */
{
    RuleNo r, OldNRules = NRules;
    ItemNo i;
    ClassNo c;

    /*  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(c, 0, MaxClass)
    {
	CoverClass(c);
    }

    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])]++;

	ClearOutcomes();

	ForEach(r, 1, NRules)
	{
	    Match[r][i] = Strength(Rule[r], Item[i]) > 0.3;

	    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(FocusClass)
/*  ----------  */
    ClassNo FocusClass;
{
    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, FocusClass);
    }
    else
    {
	SimAnneal(RuleCount, FocusClass);
    }

    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, FocusClass)
/*  ---------------  */
    RuleNo NR;
    ClassNo FocusClass;
{
    float ThisValue, CalculateValue();
    RuleNo r;

    if ( ! NR )
    {
	ThisValue = CalculateValue(FocusClass);
	if ( ThisValue < SubsetValue )
	{
	    SubsetValue = ThisValue;
	    memcpy(Subset, RuleIn, NRules+1);
	}
    }
    else
    {
	r = ClassRules[NR];

	AllCombinations(NR-1, FocusClass);

	AddRule(r);
	AllCombinations(NR-1, FocusClass);

	DeleteRule(r);
	Verbosity(1) printf("\n");
    }
}



/*************************************************************************/
/*									 */
/*  Find a good subset by simulated annealing				 */
/*									 */
/*************************************************************************/


    SimAnneal(RuleCount, FocusClass)
/*  ---------  */
    RuleNo RuleCount;
    ClassNo FocusClass;
{
    RuleNo r, OutCount;
    ItemNo i;
    short ri, Tries;
    float Temp, Delta, ThisValue, CalculateValue();
    Boolean Changed;

    /*  Keep dropping and adding rules until can't improve  */

    for ( Temp = 1000 ; Temp > 0.001 ; Temp *= 0.95 )
    {
	ThisValue = CalculateValue(FocusClass);
	if ( ThisValue < SubsetValue )
	{
	    SubsetValue = ThisValue;
	    memcpy(Subset, RuleIn, NRules+1);
	}

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



/*************************************************************************/
/*								         */
/*  Find the number of correct and incorrect rule firings for rules      */
/*  for class FocusClass and hence determine the Value of the rules      */
/*								         */
/*************************************************************************/


float CalculateValue(FocusClass)
/*    --------------  */
    ClassNo FocusClass;
{
    RuleNo r, Selected=0, InCount;
    ItemNo i, Times, FPos=0, FNeg=0, SumUsed=0, SumCover=0;
    float SumErrors=0, BaseBits, RuleBits=0, NewBits, ExceptionBits();
    ClassNo ThisClass;

    /*  Initialise Right and Wrong  */

    ForEach(r, 1, NRules)
    {
	if ( Rule[r].Rhs == FocusClass )
	{
	    Right[r] = Wrong[r] = 0;

	    if ( RuleIn[r] )
	    {
		SumUsed += Rule[r].Used;
		SumErrors += Rule[r].Error * Rule[r].Used;
		RuleBits += Rule[r].Bits;
		Selected++;
	    }
	}
    }

    RuleBits -= LogFact[Selected];	/* allow for reordering of rules */

    /*  For each rule for the FocusClass, set Right to the number
	of items that correctly fire the rule and aren't covered by
	any other included rules, and Wrong to the number of items
	that incorrectly do so.  */

    ForEach(i, 0, MaxItem)
    {
	ThisClass = Class(Item[i]);

	if ( Times = Covered[i] )
	{
	    SumCover++;
	    if( ThisClass != FocusClass ) FPos++;
	}
	else
	if ( ThisClass == FocusClass )
	{
	    FNeg++;
	}

	ForEach(r, 1, NRules)
	{
	    if ( Rule[r].Rhs == FocusClass &&
		 Match[r][i] &&
		 ( ! Times || Times == 1 && RuleIn[r] ) )
	    {
		if ( ThisClass == FocusClass )
		{
		    Right[r]++;
		}