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

Line
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)
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);
40	}
41	}
42
43	/*************************************************************************/
44	/* */
45	/* Zero the frequency tables Freq[][] and ValFreq[] up to MaxVal */
46	/* */
47	/*************************************************************************/
48
49	ResetFreq(MaxVal, Freq, ValFreq)
50	/* --------- */
51	DiscrValue MaxVal; ItemCount** Freq; ItemCount* ValFreq; {
52	DiscrValue v;
53	ClassNo c;
54
55	ForEach(v, 0, MaxVal) {
56	ForEach(c, 0, MaxClass) {
57	Freq[v][c] = 0;
58	}
59	ValFreq[v] = 0;
60	}
61	}
62
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
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)
96	/* ----------- */
97	float BaseInfo, UnknFrac;DiscrValue MaxVal;ItemCount TotalItems; {
98	DiscrValue v;
99	float ThisInfo = 0.0, ThisGain, TotalInfo();
100	short ReasonableSubsets = 0;
101
102	/* Check whether all values are unknown or the same */
103
104	if (!TotalItems)
105	return -Epsilon;
106
107	/* There must be at least two subsets with MINOBJS items */
108
109	ForEach(v, 1, MaxVal) {
110	if (ValFreq[v] >= MINOBJS)
111	ReasonableSubsets++;
112	}
113	if (ReasonableSubsets < 2)
114	return -Epsilon;
115
116	/* Compute total info after split, by summing the
117	info of each of the subsets formed by the test */
118
119	ForEach(v, 1, MaxVal) {
120	ThisInfo += TotalInfo(Freq[v], 0, MaxClass);
121	}
122
123	/* Set the gain in information for all items, adjusted for unknowns */
124
125	ThisGain = (1 - UnknFrac) * (BaseInfo - ThisInfo / TotalItems);
126
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);
131
132	return ThisGain;
133	}
134
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;{
138	DiscrValue v;
139	float ThisInfo = 0.0, ThisGain, TotalInfo();
140	short ReasonableSubsets = 0;
141
142	/* Check whether all values are unknown or the same */
143
144	if (!TotalItems)
145	return -Epsilon;
146
147	/* There must be at least two subsets with MINOBJS items */
148
149	ForEach(v, 1, MaxVal) {
150	if (ValFreq_discr[v] >= MINOBJS)
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) {
160	ThisInfo += TotalInfo(Freq_discr[v], 0, MaxClass);
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",
170	TotalItems + ValFreq_discr[0], ThisInfo, BaseInfo, UnknFrac, ThisGain);
171
172	return ThisGain;
173	}
174
175	/*************************************************************************/
176	/* */
177	/* Compute the total information in V[ MinVal..MaxVal ] */
178	/* */
179	/*************************************************************************/
180
181	float TotalInfo(V, MinVal, MaxVal)
182	/* --------- */
183	ItemCount* V;DiscrValue MinVal, MaxVal; {
184	DiscrValue v;
185	float Sum = 0.0;
186	ItemCount N, TotalItems = 0;
187
188	ForEach(v, MinVal, MaxVal) {
189	N = V[v];
190
191	Sum += N * Log(N);
192	TotalItems += N;
193	}
194
195	return TotalItems * Log(TotalItems) - Sum;
196	}
197
198
199	/*************************************************************************/
200	/* */
201	/* Print distribution table for given attribute */
202	/* */
203	/*************************************************************************/
204
205	PrintDistribution(Att, MaxVal, ShowNames)
206	/* ----------------- */
207	Attribute Att;DiscrValue MaxVal;Boolean ShowNames; {
208	DiscrValue v;
209	ClassNo c;
210	String Val;
211
212	printf("\n\t\t\t ");
213	ForEach(c, 0, MaxClass) {
214	printf("%7.6s", ClassName[c]);
215	}
216	printf("\n");
217
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	}
226
227	ForEach(c, 0, MaxClass) {
228	printf(" %6.1f", Freq[v][c]);
229	}
230
231	printf("]\n");
232	}
233	}
234
235	PrintDistribution_Discr(Att, MaxVal, ShowNames, Freq_discr)
236	/* ----------------- */
237	Attribute Att;DiscrValue MaxVal;Boolean ShowNames; ItemCount** Freq_discr;{
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]);
245	}
246	printf("\n");
247
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) {
258	printf(" %6.1f", Freq_discr[v][c]);
259	}
260
261	printf("]\n");
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: