Context Navigation

info.c @ 104

Last change on this file since 104 was 104, checked in by (none), 14 years ago

File size: 7.0 KB

Rev	Line
[26]	1	/*************************************************************************/
	2	/* */
	3	/* Calculate information, information gain, and print dists */
	4	/* -------------------------------------------------------- */
	5	/* */
	6	/*************************************************************************/
	7
	8	#include "buildex.i"
	9
	10
	11	/*************************************************************************/
	12	/* */
	13	/* Determine the worth of a particular split according to the */
	14	/* operative criterion */
	15	/* */
	16	/* Parameters: */
	17	/* SplitInfo: potential info of the split */
	18	/* SplitGain: gain in info of the split */
	19	/* MinGain: gain above which the Gain Ratio */
	20	/* may be used */
	21	/* */
	22	/* If the Gain criterion is being used, the information gain of */
	23	/* the split is returned, but if the Gain Ratio criterion is */
	24	/* being used, the ratio of the information gain of the split to */
	25	/* its potential information is returned. */
	26	/* */
	27	/*************************************************************************/
	28
	29	float Worth(ThisInfo, ThisGain, MinGain)
[69]	30	/* ----- */
	31	float ThisInfo, ThisGain, MinGain; {
	32	if (GAINRATIO) {
	33	if (ThisGain >= MinGain - Epsilon && ThisInfo > Epsilon) {
	34	return ThisGain / ThisInfo;
	35	} else {
	36	return -Epsilon;
	37	}
	38	} else {
	39	return (ThisInfo > 0 && ThisGain > -Epsilon ? ThisGain : -Epsilon);
[26]	40	}
	41	}
	42
	43	/*************************************************************************/
	44	/* */
	45	/* Zero the frequency tables Freq[][] and ValFreq[] up to MaxVal */
	46	/* */
	47	/*************************************************************************/
	48
[69]	49	ResetFreq(MaxVal, Freq, ValFreq)
	50	/* --------- */
[85]	51	DiscrValue MaxVal; ItemCount** Freq; ItemCount* ValFreq; {
[69]	52	DiscrValue v;
	53	ClassNo c;
[26]	54
[69]	55	ForEach(v, 0, MaxVal) {
	56	ForEach(c, 0, MaxClass) {
	57	Freq[v][c] = 0;
	58	}
	59	ValFreq[v] = 0;
[26]	60	}
	61	}
	62
[85]	63	void ResetFreq_discr(MaxVal, Freq_discr, ValFreq_discr)
	64	DiscrValue MaxVal; ItemCount** Freq_discr; ItemCount* ValFreq_discr;{
	65	DiscrValue v;
	66	ClassNo c;
	67
	68	ForEach(v, 0, MaxVal) {
	69	ForEach(c, 0, MaxClass) {
	70	Freq_discr[v][c] = 0;
	71	}
	72	ValFreq_discr[v] = 0;
	73	}
	74	}
	75
[26]	76	/*************************************************************************/
	77	/* */
	78	/* Given tables Freq[][] and ValFreq[], compute the information gain. */
	79	/* */
	80	/* Parameters: */
	81	/* BaseInfo: average information for all items with */
	82	/* known values of the test attribute */
	83	/* UnknownRate: fraction of items with unknown ditto */
	84	/* MaxVal: number of forks */
	85	/* TotalItems: number of items with known values of */
	86	/* test att */
	87	/* */
	88	/* where Freq[x][y] contains the no. of cases with value x for a */
	89	/* particular attribute that are members of class y, */
	90	/* and ValFreq[x] contains the no. of cases with value x for a */
	91	/* particular attribute */
	92	/* */
	93	/*************************************************************************/
	94
	95	float ComputeGain(BaseInfo, UnknFrac, MaxVal, TotalItems)
[69]	96	/* ----------- */
	97	float BaseInfo, UnknFrac;DiscrValue MaxVal;ItemCount TotalItems; {
	98	DiscrValue v;
	99	float ThisInfo = 0.0, ThisGain, TotalInfo();
	100	short ReasonableSubsets = 0;
[26]	101
[69]	102	/* Check whether all values are unknown or the same */
[26]	103
[69]	104	if (!TotalItems)
	105	return -Epsilon;
[26]	106
[69]	107	/* There must be at least two subsets with MINOBJS items */
[26]	108
[69]	109	ForEach(v, 1, MaxVal) {
	110	if (ValFreq[v] >= MINOBJS)
	111	ReasonableSubsets++;
	112	}
	113	if (ReasonableSubsets < 2)
	114	return -Epsilon;
[26]	115
[69]	116	/* Compute total info after split, by summing the
	117	info of each of the subsets formed by the test */
[26]	118
[69]	119	ForEach(v, 1, MaxVal) {
	120	ThisInfo += TotalInfo(Freq[v], 0, MaxClass);
	121	}
[26]	122
[69]	123	/* Set the gain in information for all items, adjusted for unknowns */
[26]	124
[69]	125	ThisGain = (1 - UnknFrac) * (BaseInfo - ThisInfo / TotalItems);
[26]	126
[69]	127	Verbosity(5)
	128	printf(
	129	"ComputeThisGain: items %.1f info %.3f base %.3f unkn %.3f result %.3f\n",
	130	TotalItems + ValFreq[0], ThisInfo, BaseInfo, UnknFrac, ThisGain);
[26]	131
[69]	132	return ThisGain;
[26]	133	}
	134
[85]	135	float ComputeGain_Discr(BaseInfo, UnknFrac, MaxVal, TotalItems, Freq_discr,ValFreq_discr)
	136	/* --------- */
	137	float BaseInfo, UnknFrac;DiscrValue MaxVal;ItemCount TotalItems; ItemCount** Freq_discr; ItemCount* ValFreq_discr;{
[69]	138	DiscrValue v;
	139	float ThisInfo = 0.0, ThisGain, TotalInfo();
	140	short ReasonableSubsets = 0;
[26]	141
[69]	142	/* Check whether all values are unknown or the same */
[26]	143
[69]	144	if (!TotalItems)
	145	return -Epsilon;
	146
	147	/* There must be at least two subsets with MINOBJS items */
	148
	149	ForEach(v, 1, MaxVal) {
[85]	150	if (ValFreq_discr[v] >= MINOBJS)
[69]	151	ReasonableSubsets++;
	152	}
	153	if (ReasonableSubsets < 2)
	154	return -Epsilon;
	155
	156	/* Compute total info after split, by summing the
	157	info of each of the subsets formed by the test */
	158
	159	ForEach(v, 1, MaxVal) {
[85]	160	ThisInfo += TotalInfo(Freq_discr[v], 0, MaxClass);
[69]	161	}
	162
	163	/* Set the gain in information for all items, adjusted for unknowns */
	164
	165	ThisGain = (1 - UnknFrac) * (BaseInfo - ThisInfo / TotalItems);
	166
	167	Verbosity(5)
	168	printf(
	169	"ComputeThisGain: items %.1f info %.3f base %.3f unkn %.3f result %.3f\n",
[85]	170	TotalItems + ValFreq_discr[0], ThisInfo, BaseInfo, UnknFrac, ThisGain);
[69]	171
	172	return ThisGain;
	173	}
	174
[26]	175	/*************************************************************************/
	176	/* */
	177	/* Compute the total information in V[ MinVal..MaxVal ] */
	178	/* */
	179	/*************************************************************************/
	180
	181	float TotalInfo(V, MinVal, MaxVal)
[69]	182	/* --------- */
[85]	183	ItemCount* V;DiscrValue MinVal, MaxVal; {
[69]	184	DiscrValue v;
	185	float Sum = 0.0;
	186	ItemCount N, TotalItems = 0;
[26]	187
[69]	188	ForEach(v, MinVal, MaxVal) {
	189	N = V[v];
[26]	190
[69]	191	Sum += N * Log(N);
	192	TotalItems += N;
	193	}
[26]	194
[69]	195	return TotalItems * Log(TotalItems) - Sum;
[26]	196	}
	197
[85]	198
[26]	199	/*************************************************************************/
	200	/* */
	201	/* Print distribution table for given attribute */
	202	/* */
	203	/*************************************************************************/
	204
[69]	205	PrintDistribution(Att, MaxVal, ShowNames)
	206	/* ----------------- */
	207	Attribute Att;DiscrValue MaxVal;Boolean ShowNames; {
	208	DiscrValue v;
	209	ClassNo c;
	210	String Val;
[26]	211
[69]	212	printf("\n\t\t\t ");
	213	ForEach(c, 0, MaxClass) {
	214	printf("%7.6s", ClassName[c]);
	215	}
	216	printf("\n");
[26]	217
[69]	218	ForEach(v, 0, MaxVal) {
	219	if (ShowNames) {
	220	Val = (!v ? "unknown" : MaxAttVal[Att] ? AttValName[Att][v] : v
	221	== 1 ? "below" : "above");
	222	printf("\t\t[%-7.7s:", Val);
	223	} else {
	224	printf("\t\t[%-7d:", v);
	225	}
[26]	226
[69]	227	ForEach(c, 0, MaxClass) {
	228	printf(" %6.1f", Freq[v][c]);
	229	}
	230
	231	printf("]\n");
[26]	232	}
[69]	233	}
	234
[85]	235	PrintDistribution_Discr(Att, MaxVal, ShowNames, Freq_discr)
[69]	236	/* ----------------- */
[85]	237	Attribute Att;DiscrValue MaxVal;Boolean ShowNames; ItemCount** Freq_discr;{
[69]	238	DiscrValue v;
	239	ClassNo c;
	240	String Val;
	241
	242	printf("\n\t\t\t ");
	243	ForEach(c, 0, MaxClass) {
	244	printf("%7.6s", ClassName[c]);
[26]	245	}
[69]	246	printf("\n");
[26]	247
[69]	248	ForEach(v, 0, MaxVal) {
	249	if (ShowNames) {
	250	Val = (!v ? "unknown" : MaxAttVal[Att] ? AttValName[Att][v] : v
	251	== 1 ? "below" : "above");
	252	printf("\t\t[%-7.7s:", Val);
	253	} else {
	254	printf("\t\t[%-7d:", v);
	255	}
	256
	257	ForEach(c, 0, MaxClass) {
[85]	258	printf(" %6.1f", Freq_discr[v][c]);
[69]	259	}
	260
	261	printf("]\n");
[26]	262	}
	263	}

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: proiecte/Parallel-DT/R8/Src/info.c @ 104

Download in other formats: