testrules.cpp

实现决策树分类训练试验。 源自c4.5

/*************************************************************************/
/*									 */
/*	Evaluatation of rulesets					 */
/*	------------------------					 */
/*									 */
/*************************************************************************/
#include "stdafx.h"
#include "MyBase.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

extern FILE *fLog;
/*********************************************/
/* This is from Ruleinex.i    **/

extern PR	*Rule;		/* production rules */

extern RuleNo	NRules,		/* number of production rules */
		*RuleIndex;	/* index to production rules */

extern short	RuleSpace;	/* space currently allocated for rules */

extern RuleSet	*PRSet;		/* set of rulesets */

extern ClassNo	DefaultClass;	/* default class associated with ruleset */

extern BOOL	SIGTEST,	/* use Fisher's test in rule pruning */
		SIMANNEAL;	/* use simulated annealing */

extern float	SIGTHRESH,	/* sig level used in rule pruning */
		REDUNDANCY,	/* factor governing encoding tradeoff
				   between rules and exceptions */
		AttTestBits,	/* average bits to encode tested attribute */
		*BranchBits;	/* ditto attribute value */

extern float	*LogItemNo;	/* LogItemNo[i] = log2(i) */
extern double	*LogFact;	/* LogFact[i] = log2(i!) */
/*************************************************/


float	Confidence;		/* certainty factor of fired rule */
				/* (set by BestRuleIndex) */


/*************************************************************************/
/*									 */
/*	Evaluate all rulesets						 */
/*									 */
/*************************************************************************/
void EvaluateRulesets(Boolean DeleteRules)
{
    short t;
    ItemNo *Errors;
    float AvSize=0, AvErrs=0;
    Boolean Final;

    if ( TRIALS == 1 )
    {
		/*  Evaluate current ruleset as there is no composite ruleset  */

		Interpret(0, MaxItem, DeleteRules, true, true);
		return;
    }

    Errors = (ItemNo *) malloc((TRIALS+1) * sizeof(ItemNo));

    ForEach(t, 0, TRIALS)
    {
		NRules    = PRSet[t].SNRules;
		Rule      = PRSet[t].SRule;
		RuleIndex = PRSet[t].SRuleIndex;
		DefaultClass = PRSet[t].SDefaultClass;

		if ( t < TRIALS )
		{
			fprintf(fLog,"\nRuleset %d:\n", t);
		}
		else
		{
			fprintf(fLog,"\nComposite ruleset:\n");
		}

		Final = (t == TRIALS);
		Errors[t] = Interpret(0, MaxItem, DeleteRules, Final, Final);

		AvSize += NRules;
		AvErrs += Errors[t];

		if ( DeleteRules )
		{
			PRSet[t].SNRules = NRules;
		}
	}

	/*  Print report  */

	fprintf(fLog,"\n");
	fprintf(fLog,"Trial   Size      Errors\n");
	fprintf(fLog,"-----   ----      ------\n");

	ForEach(t, 0, TRIALS)
	{
		if ( t < TRIALS )
		{
			fprintf(fLog,"%4d", t);
		}
		else
		{
			fprintf(fLog,"  **");
		}
		fprintf(fLog,"    %4d  %3d(%4.1f%%)\n",
			  PRSet[t].SNRules, Errors[t], 100 * Errors[t] / (MaxItem+1.0));
    }

    AvSize /= TRIALS + 1;
    AvErrs /= TRIALS + 1;
    fprintf(fLog,"\t\t\t\tAv size = %.1f,  av errors = %.1f (%.1f%%)\n",
	   AvSize, AvErrs, 100 * AvErrs / (MaxItem+1.0));
}



/*************************************************************************/
/*									 */
/*	Evaluate current ruleset					 */
/*									 */
/*************************************************************************/
ItemNo Interpret(ItemNo Fp, ItemNo Lp, BOOL DeleteRules, BOOL CMInfo, BOOL Arrow)
{
    ItemNo i, Tested=0, Errors=0, *Better, *Worse, *ConfusionMat;
    Boolean FoundRule;
    ClassNo AssignedClass, AltClass;
    Attribute Att;
    RuleNo p, Bestr, ri, ri2, riDrop=0;
    float ErrorRate, BestRuleConfidence;

    if ( CMInfo )
    {
		ConfusionMat = (ItemNo *) calloc((MaxClass+1)*(MaxClass+1), sizeof(ItemNo));
    }

    ForEach(ri, 1, NRules)
    {
		p = RuleIndex[ri];
		Rule[p].Used = Rule[p].Incorrect = 0;
    }

    Better = (ItemNo *) calloc(NRules+1, sizeof(ItemNo));
    Worse  = (ItemNo *) calloc(NRules+1, sizeof(ItemNo));

    ForEach(i, Fp, Lp)
	{
		/*  Find first choice for rule for this item  */

		ri = BestRuleIndex(Item[i], 1);
		Bestr = ( ri ? RuleIndex[ri] : 0 );
		FoundRule = Bestr > 0;

		if ( FoundRule )
		{
			Rule[Bestr].Used++;
			AssignedClass =  Rule[Bestr].Rhs;
			BestRuleConfidence = Confidence;

			/*  Now find second choice  */

			ri2 = BestRuleIndex(Item[i], ri+1);
			AltClass = ( ri2 ? Rule[RuleIndex[ri2]].Rhs : DefaultClass );
			if ( AltClass != AssignedClass )
			{
				if ( AssignedClass == Class(Item[i]) )
				{
					Better[ri]++;
				}
				else if ( AltClass == Class(Item[i]) )
				{
					Worse[ri]++;
				}
			}
		}
		else
		{
			AssignedClass = DefaultClass;
		}
		
		if ( CMInfo )
		{
			ConfusionMat[Class(Item[i])*(MaxClass+1)+AssignedClass]++;
		}
		Tested++;

		if ( AssignedClass != Class(Item[i]) )
		{
			Errors++;
			if ( FoundRule ) Rule[Bestr].Incorrect++;

			Verbosity(3)
			{
	    		fprintf(fLog,"\n");
	    		ForEach(Att, 0, MaxAtt)
	    		{
	    			fprintf(fLog,"\t%s: ", AttName[Att]);
	    			if ( MaxAttVal[Att] )
					{
						if ( DVal(Item[i],Att) )
						{
							fprintf(fLog,"%s\n", AttValName[Att][DVal(Item[i],Att)]);
						}
	    				else
						{
							fprintf(fLog,"?\n");
						}
					}
					else
	    			{
						if ( CVal(Item[i],Att) != Unknown )
						{
							fprintf(fLog,"%g\n", CVal(Item[i],Att));
						}
						else
						{
							fprintf(fLog,"?\n");
						}
	    			}
	    		}
	    		fprintf(fLog,"\t%4d:\tGiven class %s,", i, ClassName[Class(Item[i])]);
	    		if ( FoundRule )
	    		{
	    			fprintf(fLog," rule %d [%.1f%%] gives class ",
	    				Bestr, 100 * BestRuleConfidence);
	    		}
	    		else
				{
	    			fprintf(fLog," default class ");
				}
	    		fprintf(fLog,"%s\n", ClassName[AssignedClass]);
			}
		}
	}

    fprintf(fLog,"\nRule  Size  Error  Used  Wrong\t          Advantage\n");
    fprintf(fLog,  "----  ----  -----  ----  -----\t          ---------\n");
    ForEach(ri, 1, NRules)
	{
		p = RuleIndex[ri];
		if ( Rule[p].Used > 0 )
		{
			ErrorRate = Rule[p].Incorrect / (float) Rule[p].Used;

			fprintf(fLog,"%4d%6d%6.1f%%%6d%7d (%.1f%%)\t%6d (%d|%d) \t%s\n",
				p, Rule[p].Size,
				100 * Rule[p].Error, Rule[p].Used, Rule[p].Incorrect,
				100 * ErrorRate,
				Better[ri]-Worse[ri], Better[ri], Worse[ri],
				ClassName[Rule[p].Rhs]);

			/*  See whether this rule should be dropped.  Note: can only drop
			one rule at a time, because Better and Worse are affected  */

			if ( DeleteRules && ! riDrop && Worse[ri] > Better[ri] )
			{
				riDrop = ri;
			}
		}
	}

    delete Better;
    delete Worse;

    if ( riDrop )
	{
		fprintf(fLog,"\nDrop rule %d\n", RuleIndex[riDrop]);

		ForEach(ri, riDrop+1, NRules)
		{
			RuleIndex[ri-1] = RuleIndex[ri];
		}
		NRules--;
    
		if ( CMInfo ) delete ConfusionMat;
		return Interpret(Fp, Lp, DeleteRules, true, Arrow);
	}
    else
    {
		fprintf(fLog,"\nTested %d, errors %d (%.1f%%)%s\n",
			Tested, Errors, 100 * Errors / (float) Tested,
			( Arrow ? "   <<" : "" ));
    }

    if ( CMInfo )
    {
		PrintConfusionMatrix(ConfusionMat);
		delete ConfusionMat;
	}

    return Errors;
}



/*************************************************************************/
/*									 */
/*	Find the best rule for the given case, leaving probability       */
/*      in Confidence							 */
/*									 */
/*************************************************************************/


RuleNo BestRuleIndex(Description CaseDesc, RuleNo Start)
{
    RuleNo r, ri;

    ForEach(ri, Start, NRules)
    {
		r = RuleIndex[ri];
		Confidence = Strength(Rule[r], CaseDesc);

		if ( Confidence > 0.1 )
		{
			return ri;
		}
    }

    Confidence = 0.0;
    return 0;
}