Context Navigation

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

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

File size: 7.1 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	#pragma omp parallel for private(v)
56	ForEach(v, 0, MaxVal) {
57	ForEach(c, 0, MaxClass) {
58	Freq[v][c] = 0;
59	}
60	ValFreq[v] = 0;
61	}
62	}
63
64	void ResetFreq_discr(MaxVal, Freq_discr, ValFreq_discr)
65	DiscrValue MaxVal; ItemCount** Freq_discr; ItemCount* ValFreq_discr;{
66	DiscrValue v;
67	ClassNo c;
68
69	ForEach(v, 0, MaxVal) {
70	ForEach(c, 0, MaxClass) {
71	Freq_discr[v][c] = 0;
72	}
73	ValFreq_discr[v] = 0;
74	}
75	}
76
77	/*************************************************************************/
78	/* */
79	/* Given tables Freq[][] and ValFreq[], compute the information gain. */
80	/* */
81	/* Parameters: */
82	/* BaseInfo: average information for all items with */
83	/* known values of the test attribute */
84	/* UnknownRate: fraction of items with unknown ditto */
85	/* MaxVal: number of forks */
86	/* TotalItems: number of items with known values of */
87	/* test att */
88	/* */
89	/* where Freq[x][y] contains the no. of cases with value x for a */
90	/* particular attribute that are members of class y, */
91	/* and ValFreq[x] contains the no. of cases with value x for a */
92	/* particular attribute */
93	/* */
94	/*************************************************************************/
95
96	float ComputeGain(BaseInfo, UnknFrac, MaxVal, TotalItems)
97	/* ----------- */
98	float BaseInfo, UnknFrac;DiscrValue MaxVal;ItemCount TotalItems; {
99	DiscrValue v;
100	float ThisInfo = 0.0, ThisGain, TotalInfo();
101	short ReasonableSubsets = 0;
102
103	/* Check whether all values are unknown or the same */
104
105	if (!TotalItems)
106	return -Epsilon;
107
108	/* There must be at least two subsets with MINOBJS items */
109
110	ForEach(v, 1, MaxVal) {
111	if (ValFreq[v] >= MINOBJS)
112	ReasonableSubsets++;
113	}
114	if (ReasonableSubsets < 2)
115	return -Epsilon;
116
117	/* Compute total info after split, by summing the
118	info of each of the subsets formed by the test */
119
120	//#pragma omp parallel for reduction(+:ThisInfo)
121	ForEach(v, 1, MaxVal) {
122	ThisInfo += TotalInfo(Freq[v], 0, MaxClass);
123	}
124
125	/* Set the gain in information for all items, adjusted for unknowns */
126
127	ThisGain = (1 - UnknFrac) * (BaseInfo - ThisInfo / TotalItems);
128
129	Verbosity(5)
130	printf(
131	"ComputeThisGain: items %.1f info %.3f base %.3f unkn %.3f result %.3f\n",
132	TotalItems + ValFreq[0], ThisInfo, BaseInfo, UnknFrac, ThisGain);
133
134	return ThisGain;
135	}
136
137	float ComputeGain_Discr(BaseInfo, UnknFrac, MaxVal, TotalItems, Freq_discr,ValFreq_discr)
138	/* --------- */
139	float BaseInfo, UnknFrac;DiscrValue MaxVal;ItemCount TotalItems; ItemCount** Freq_discr; ItemCount* ValFreq_discr;{
140	DiscrValue v;
141	float ThisInfo = 0.0, ThisGain, TotalInfo();
142	short ReasonableSubsets = 0;
143
144	/* Check whether all values are unknown or the same */
145
146	if (!TotalItems)
147	return -Epsilon;
148
149	/* There must be at least two subsets with MINOBJS items */
150
151	ForEach(v, 1, MaxVal) {
152	if (ValFreq_discr[v] >= MINOBJS)
153	ReasonableSubsets++;
154	}
155	if (ReasonableSubsets < 2)
156	return -Epsilon;
157
158	/* Compute total info after split, by summing the
159	info of each of the subsets formed by the test */
160
161	ForEach(v, 1, MaxVal) {
162	ThisInfo += TotalInfo(Freq_discr[v], 0, MaxClass);
163	}
164
165	/* Set the gain in information for all items, adjusted for unknowns */
166
167	ThisGain = (1 - UnknFrac) * (BaseInfo - ThisInfo / TotalItems);
168
169	Verbosity(5)
170	printf(
171	"ComputeThisGain: items %.1f info %.3f base %.3f unkn %.3f result %.3f\n",
172	TotalItems + ValFreq_discr[0], ThisInfo, BaseInfo, UnknFrac, ThisGain);
173
174	return ThisGain;
175	}
176
177	/*************************************************************************/
178	/* */
179	/* Compute the total information in V[ MinVal..MaxVal ] */
180	/* */
181	/*************************************************************************/
182
183	float TotalInfo(V, MinVal, MaxVal)
184	/* --------- */
185	ItemCount* V;DiscrValue MinVal, MaxVal; {
186	DiscrValue v;
187	float Sum = 0.0;
188	ItemCount N, TotalItems = 0;
189
190	ForEach(v, MinVal, MaxVal) {
191	N = V[v];
192
193	Sum += N * Log(N);
194	TotalItems += N;
195	}
196
197	return TotalItems * Log(TotalItems) - Sum;
198	}
199
200
201	/*************************************************************************/
202	/* */
203	/* Print distribution table for given attribute */
204	/* */
205	/*************************************************************************/
206
207	PrintDistribution(Att, MaxVal, ShowNames)
208	/* ----------------- */
209	Attribute Att;DiscrValue MaxVal;Boolean ShowNames; {
210	DiscrValue v;
211	ClassNo c;
212	String Val;
213
214	printf("\n\t\t\t ");
215	ForEach(c, 0, MaxClass) {
216	printf("%7.6s", ClassName[c]);
217	}
218	printf("\n");
219
220	ForEach(v, 0, MaxVal) {
221	if (ShowNames) {
222	Val = (!v ? "unknown" : MaxAttVal[Att] ? AttValName[Att][v] : v
223	== 1 ? "below" : "above");
224	printf("\t\t[%-7.7s:", Val);
225	} else {
226	printf("\t\t[%-7d:", v);
227	}
228
229	ForEach(c, 0, MaxClass) {
230	printf(" %6.1f", Freq[v][c]);
231	}
232
233	printf("]\n");
234	}
235	}
236
237	PrintDistribution_Discr(Att, MaxVal, ShowNames, Freq_discr)
238	/* ----------------- */
239	Attribute Att;DiscrValue MaxVal;Boolean ShowNames; ItemCount** Freq_discr;{
240	DiscrValue v;
241	ClassNo c;
242	String Val;
243
244	printf("\n\t\t\t ");
245	ForEach(c, 0, MaxClass) {
246	printf("%7.6s", ClassName[c]);
247	}
248	printf("\n");
249
250	ForEach(v, 0, MaxVal) {
251	if (ShowNames) {
252	Val = (!v ? "unknown" : MaxAttVal[Att] ? AttValName[Att][v] : v
253	== 1 ? "below" : "above");
254	printf("\t\t[%-7.7s:", Val);
255	} else {
256	printf("\t\t[%-7d:", v);
257	}
258
259	ForEach(c, 0, MaxClass) {
260	printf(" %6.1f", Freq_discr[v][c]);
261	}
262
263	printf("]\n");
264	}
265	}

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

Download in other formats: