mybase.h

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

/*								         */
/*  Add rule r to the set of included rules and increase the number of	 */
/*  rules covering each of the items that fire the rule		         */
/*								         */
/*************************************************************************/
void AddRule(RuleNo r);

/*************************************************************************/
/*								         */
/*  Delete rule r from the included rules and decrease the number of	 */
/*  rules covering each of the items covered by the rule	         */
/*								         */
/*************************************************************************/
void DeleteRule(RuleNo r);


/*************************************************************************/
/*								         */
/*  Make an index of included rules in RuleIndex.  Select first those    */
/*  classes whose rules have the fewest false positives.  Within a	 */
/*  class, put rules with higher accuracy ahead.			 */
/*								         */
/*************************************************************************/
void MakeIndex();


/*************************************************************************/
/*								         */
/*  Find the default class as the one with most items not covered by	 */
/*  any rule.  Resolve ties in favour of more frequent classes.		 */
/*  (Note: Covered has been set by MakeIndex.)				 */
/*								         */
/*************************************************************************/
void   FindDefault();


/*************************************************************************/
/*								         */
/*  Given a rule and a case, determine the strength with which we can    */
/*  conclude that the case belongs to the class specified by the rule's  */
/*  right-hand side.						         */
/*								         */
/*  If the case doesn't satisfy all the conditions of the rule,		 */
/*  then this is 0.						         */
/*								         */
/*************************************************************************/
float Strength(PR ThisRule, Description Case);

/*************************************************************************/
/*									 */
/*  Determine the number of bits to encode exceptions.  Unlike the	 */
/*  version in the book, this uses an approximate encoding that 	 */
/*  penalizes unbalanced numbers of false positives and false negatives  */
/*  as described in my paper at 1995 International Machine Learning      */
/*  Conference (published by Morgan Kaufmann).				 */
/*									 */
/*************************************************************************/
float Biased(int N, int E, float ExpE);

float ExceptionBits(int Fires, int FP, int FN);

/*************************************************************************/
/*									 */
/*  Find encoding lengths for all rules					 */
/*									 */
/*************************************************************************/
void FindRuleCodes();


/*************************************************************************/
/*									 */
/*  Determine the number of bits required to encode a condition		 */
/*									 */
/*************************************************************************/
float CondBits(Condition C);


/*************************************************************************/
/*								   	 */
/*	Pruning single rules					   	 */
/*	--------------------				   	      	 */
/*								   	 */
/*************************************************************************/

/*************************************************************************/
/*									 */
/*  Prune the rule given by the conditions Cond, and the number of	 */
/*  conditions NCond, and add the resulting rule to the current		 */
/*  ruleset if it is sufficiently accurate				 */
/*									 */
/*************************************************************************/
void PruneRule(Condition Cond[], short NCond, ClassNo TargetClass);


/*************************************************************************/
/*									 */
/*  See whether condition R is redundant                           	 */
/*									 */
/*************************************************************************/
BOOL Redundant(short R, Condition Cond, short NCond);


/*************************************************************************/
/*									 */
/*  Decide whether subset S1 of values is contained in subset S2	 */
/*									 */
/*************************************************************************/
BOOL IsSubset(Set S1, Set S2, Attribute Att);

/*************************************************************************/
/*									 */
/*  Find the frequency distribution tables for the current conditions: 	 */
/*									 */
/*	Total[0] = items matching all conditions		   	 */
/*	Total[d] = items matching all except condition d	   	 */
/*									 */
/*	Errors[0] = wrong-class items matching all conditions	   	 */
/*	Errors[d] = wrong-class items matching all but cond d	   	 */
/*									 */
/*  This routine is critical to the efficiency of rule pruning. It	 */
/*  computes the information above in one pass through the data,	 */
/*  looking at cases that fail to satisfy at most one of the		 */
/*  non-deleted conditions						 */
/*									 */
/*************************************************************************/
void  FindTables(short NCond, ClassNo TargetClass);

/*************************************************************************/
/*									 */
/*  Increment the counts Total[d] and Errors[d]				 */
/*									 */
/*************************************************************************/
void UpdateCount(ItemNo Tp[], ItemNo E[], short d, Boolean OK);


/*************************************************************************/
/*									 */
/*  Determine whether the given case description satisfies the given	 */
/*  condition.								 */
/*									 */
/*************************************************************************/
BOOL Satisfies(Description CaseDesc, Condition OneCond);

/*************************************************************************/
/*									 */
/*  Hypergeometric distribution	(uses tabulated log factorials)		 */
/*									 */
/*************************************************************************/
double Hypergeom(int a,int  r, int A, int B);

/*************************************************************************/
/*									 */
/*  TableProb examines the 2x2 contingency table t and computes the      */
/*  probability that a random division could have produced a split at	 */
/*  least as extreme as this.  Also known as "Fisher's Exact Test",	 */
/*  after its inventor, R.A. Fisher.					 */
/*									 */
/*************************************************************************/
float TableProb(int t11, int t12, int t21, int t22);

/*************************************************************************/
/*									 */
/*	Evaluatation of rulesets					 */
/*	------------------------					 */
/*									 */
/*************************************************************************/

/*************************************************************************/
/*									 */
/*	Evaluate all rulesets						 */
/*									 */
/*************************************************************************/
void EvaluateRulesets(Boolean DeleteRules);


/*************************************************************************/
/*									 */
/*	Evaluate current ruleset					 */
/*									 */
/*************************************************************************/
ItemNo Interpret(ItemNo Fp, ItemNo Lp, BOOL DeleteRules, BOOL CMInfo, BOOL Arrow);

/*************************************************************************/
/*									 */
/*	Find the best rule for the given case, leaving probability       */
/*      in Confidence							 */
/*									 */
/*************************************************************************/
RuleNo BestRuleIndex(Description CaseDesc, RuleNo Start);


/*************************************************************************/
/*								   	 */
/*		From Consult.c   		   	 */
/*								   	 */
/*	Classify items interactively using a decision tree	   	 */
/*	--------------------------------------------------   		 */
/*								   	 */
/*************************************************************************/
/*  The interview module uses a more complex description of an
 case called a "Range Description".   The value of an
 attribute is given by 
 - lower and upper bounds (continuous attribute)
 - probability of each possible value (discrete attribute)  */
typedef	struct ValRange *RangeDescRec;

struct ValRange
{ 
	Boolean	Known,		/* is range known? */
		Asked;		/* has it been asked? */
	float	LowerBound,	/* lower bound given */
		UpperBound,	/* upper ditto */
		*Probability;	/* prior prob of each discr value */
};

#define Fuzz	0.01			/* minimum weight */
/*************************************************************************/
/*								   	 */
/*  Classify the extended case description in RangeDesc using the	 */
/*  given subtree, by adjusting the values ClassSum and LowClassSum	 */
/*  for each class, indicating the likelihood of the case being  	 */
/*  of that class.						   	 */
/*								   	 */
/*************************************************************************/
void ClassifyCase(Tree Subtree, float Weight);

/*************************************************************************/
/*								   	 */
/*  Interpolate a single value between Lower, Cut and Upper		 */
/*								   	 */
/*************************************************************************/
float Interpolate(Tree t,float v);

/*************************************************************************/
/*								   	 */
/*  Compute the area under a soft threshold curve to the right of a	 */
/*  given value.							 */
/*								   	 */
/*************************************************************************/
float Area(Tree t, float v);

/*************************************************************************/
/*								  	 */
/*		Process a single case				  	 */
/*								  	 */
/*************************************************************************/
void InterpretTree();

/*************************************************************************/
/*								  	 */
/*  Print the chosen class with certainty factor and range	  	 */
/*								  	 */
/*************************************************************************/
void Decision(ClassNo c, float p, float lb, float ub);

/*************************************************************************/
/*								 	 */
/*	User interface for consulting trees and rulesets	 	 */
/*	------------------------------------------------	 	 */
/*								 	 */
/*************************************************************************/
/*************************************************************************/
/*									 */
/*	Ask for the value of attribute Att if necessary			 */
/*									 */
/*************************************************************************/
void CheckValue(Attribute Att, Tree T);

/*************************************************************************/
/*									 */
/*	Print the range of values for attribute Att			 */
/*									 */
/*************************************************************************/
void PrintRange(Attribute Att);

#define	SkipSpace	while ( (c = getchar()) == ' ' || c == '\t' )

/*************************************************************************/
/*									 */
/*	Read a range of values for attribute Att or <cr>		 */
/*									 */
/*************************************************************************/
void ReadRange(Attribute Att, Tree T);

/*************************************************************************/
/*									 */
/*	Read a discrete attribute value or range			 */
/*									 */
/*************************************************************************/
void ReadDiscr(Attribute Att, Tree T);

/*************************************************************************/
/*									 */
/*	Read a continuous attribute value or range			 */
/*									 */
/*************************************************************************/
void ReadContin(Attribute Att, Tree T);

/*************************************************************************/
/*									 */
/*	Try again to obtain a value for attribute Att			 */
/*									 */
/*************************************************************************/
void Retry(Attribute Att, Tree T);

/*************************************************************************/
/*									 */
/*	Skip to the end of the line of input				 */
/*									 */
/*************************************************************************/
void SkipLine(char c);


/*************************************************************************/
/*									 */
/*		Clear the range description				 */
/*									 */
/*************************************************************************/
void Clear();



#endif  //!defined(AFX_MYDIAG_H__0C77D11B_84AE_450C_BBEWEWEWESDFRF4EBF44F075E__INCLUDED_MMMMM)