Context Navigation

source: proiecte/Parallel-DT/R8/Src/build.c @ 65

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

File size: 16.5 KB

Line
1	/*************************************************************************/
2	/* */
3	/* Central tree-forming algorithm incorporating all criteria */
4	/* --------------------------------------------------------- */
5	/* */
6	/*************************************************************************/
7
8	#include "defns.i"
9	#include "types.i"
10	#include "extern.i"
11	//#include "buildex.i"
12
13	#include <omp.h>
14
15
16	ItemCount Weight, / Weight[i] = current fraction of item i */
17	*Freq, / Freq[x][c] = no. items of class c with outcome x */
18	ValFreq, / ValFreq[x] = no. items with outcome x */
19	ClassFreq; / ClassFreq[c] = no. items of class c */
20
21	float Gain, / Gain[a] = info gain by split on att a */
22	Info, / Info[a] = potential info of split on att a */
23	Bar, / Bar[a] = best threshold for contin att a */
24	UnknownRate; / UnknownRate[a] = current unknown rate for att a */
25
26	Boolean Tested, / Tested[a] set if att a has already been tested */
27	MultiVal; /* true when all atts have many values */
28
29	/* External variables initialised here */
30
31	extern float SplitGain, / SplitGain[i] = gain with att value of item i as threshold */
32	SplitInfo; / SplitInfo[i] = potential info ditto */
33
34	extern ItemCount Slice1, / Slice1[c] = saved values of Freq[x][c] in subset.c */
35	Slice2; / Slice2[c] = saved values of Freq[y][c] */
36
37	extern Set *Subset; / Subset[a][s] = subset s for att a */
38
39	extern short Subsets; / Subsets[a] = no. subsets for att a */
40
41	/*************************************************************************/
42	/* */
43	/* Allocate space for tree tables */
44	/* */
45	/*************************************************************************/
46
47	InitialiseTreeData()
48	/* ------------------ */
49	{
50	DiscrValue v;
51	Attribute a;
52
53	Tested = (char *) calloc(MaxAtt + 1, sizeof(char));
54
55	Gain = (float *) calloc(MaxAtt + 1, sizeof(float));
56	Info = (float *) calloc(MaxAtt + 1, sizeof(float));
57	Bar = (float *) calloc(MaxAtt + 1, sizeof(float));
58
59	Subset = (Set *) calloc(MaxAtt + 1, sizeof(Set ));
60	ForEach(a, 0, MaxAtt) {
61	if (MaxAttVal[a]) {
62	Subset[a] = (Set *) calloc(MaxDiscrVal + 1, sizeof(Set));
63	ForEach(v, 0, MaxAttVal[a]) {
64	Subset[a][v] = (Set) malloc((MaxAttVal[a] >> 3) + 1);
65	}
66	}
67	}
68	Subsets = (short *) calloc(MaxAtt + 1, sizeof(short));
69
70	SplitGain = (float *) calloc(MaxItem + 1, sizeof(float));
71	SplitInfo = (float *) calloc(MaxItem + 1, sizeof(float));
72
73	Weight = (ItemCount *) calloc(MaxItem + 1, sizeof(ItemCount));
74
75	Freq = (ItemCount *) calloc(MaxDiscrVal + 1, sizeof(ItemCount ));
76	ForEach(v, 0, MaxDiscrVal) {
77	Freq[v] = (ItemCount *) calloc(MaxClass + 1, sizeof(ItemCount));
78	}
79
80	ValFreq = (ItemCount *) calloc(MaxDiscrVal + 1, sizeof(ItemCount));
81	ClassFreq = (ItemCount *) calloc(MaxClass + 1, sizeof(ItemCount));
82
83	Slice1 = (ItemCount *) calloc(MaxClass + 2, sizeof(ItemCount));
84	Slice2 = (ItemCount *) calloc(MaxClass + 2, sizeof(ItemCount));
85
86	UnknownRate = (float *) calloc(MaxAtt + 1, sizeof(float));
87
88	/* Check whether all attributes have many discrete values */
89
90	MultiVal = true;
91	if (!SUBSET) {
92	for (a = 0; MultiVal && a <= MaxAtt; a++) {
93	if (SpecialStatus[a] != IGNORE) {
94	MultiVal = MaxAttVal[a] >= 0.3 * (MaxItem + 1);
95	}
96	}
97	}
98
99
100	}
101
102	/*************************************************************************/
103	/* */
104	/* Initialise the weight of each item */
105	/* */
106	/*************************************************************************/
107
108	InitialiseWeights()
109	/* ----------------- */
110	{
111	ItemNo i;
112
113	ForEach(i, 0, MaxItem) {
114	Weight[i] = 1.0;
115	}
116	}
117
118	/*************************************************************************/
119	/* */
120	/* Build a decision tree for the cases Fp through Lp: */
121	/* */
122	/* - if all cases are of the same class, the tree is a leaf and so */
123	/* the leaf is returned labelled with this class */
124	/* */
125	/* - for each attribute, calculate the potential information provided */
126	/* by a test on the attribute (based on the probabilities of each */
127	/* case having a particular value for the attribute), and the gain */
128	/* in information that would result from a test on the attribute */
129	/* (based on the probabilities of each case with a particular */
130	/* value for the attribute being of a particular class) */
131	/* */
132	/* - on the basis of these figures, and depending on the current */
133	/* selection criterion, find the best attribute to branch on. */
134	/* Note: this version will not allow a split on an attribute */
135	/* unless two or more subsets have at least MINOBJS items. */
136	/* */
137	/* - try branching and test whether better than forming a leaf */
138	/* */
139	/*************************************************************************/
140
141	Tree FormTree(Fp, Lp)
142	/* --------- */
143	ItemNo Fp, Lp; {
144	ItemNo i, Kp, Ep, Group();
145	ItemCount Cases, NoBestClass, KnownCases, CountItems();
146	float Factor, BestVal, Val, AvGain = 0, Worth();
147	Attribute Att, BestAtt, Possible = 0;
148	ClassNo c, BestClass;
149	Tree Node, Leaf();
150	DiscrValue v;
151	Boolean PrevAllKnown;
152
153	Cases = CountItems(Fp, Lp);
154
155	/* Generate the class frequency distribution */
156
157	// ########### begin parallel region ############## //
158	#pragma omp parallel default(shared)
159	{
160
161	//printf("The parallel region is executed by thread %d\n", omp_get_thread_num());
162	/* THIS CAN BE PARALELIZED */
163	#pragma omp for private(c)
164	ForEach(c, 0, MaxClass) {
165	ClassFreq[c] = 0;
166	}
167
168	/* THIS CAN BE PARALELIZED */
169	#pragma omp for private(i)
170	ForEach(i, Fp, Lp) {
171	#pragma omp atomic
172	ClassFreq[Class(Item[i])] += Weight[i];
173	}
174	}
175
176	/* Find the most frequent class */
177	/* THIS CAN BE PARALELIZED */
178	BestClass = 0;
179
180	ForEach(c, 0, MaxClass) {
181	if (ClassFreq[c] > ClassFreq[BestClass]) {
182	BestClass = c;
183	}
184	}
185
186	NoBestClass = ClassFreq[BestClass];
187
188	Node = Leaf(ClassFreq, BestClass, Cases, Cases - NoBestClass);
189
190	/* If all cases are of the same class or there are not enough
191	cases to divide, the tree is a leaf */
192
193	if (NoBestClass == Cases \|\| Cases < 2 * MINOBJS) {
194	return Node;
195	}
196
197	Verbosity(1)
198	printf("\n%d items, total weight %.1f\n", Lp - Fp + 1, Cases);
199
200	/* For each available attribute, find the information and gain */
201
202	ForEach(Att, 0, MaxAtt) {
203	Gain[Att] = -Epsilon;
204
205	if (SpecialStatus[Att] == IGNORE)
206	continue;
207
208	if (MaxAttVal[Att]) {
209	/* discrete valued attribute */
210
211	if (SUBSET && MaxAttVal[Att] > 2) {
212	EvalSubset(Att, Fp, Lp, Cases);
213	} else if (!Tested[Att]) {
214	EvalDiscreteAtt(Att, Fp, Lp, Cases);
215	}
216	} else {
217	/* continuous attribute */
218
219	EvalContinuousAtt(Att, Fp, Lp);
220	}
221
222	/* Update average gain, excluding attributes with very many values */
223
224	if (Gain[Att] > -Epsilon && (MultiVal \|\| MaxAttVal[Att] < 0.3 * (MaxItem + 1))) {
225	Possible++;
226	AvGain += Gain[Att];
227	}
228
229	}
230
231	/* Find the best attribute according to the given criterion */
232	BestVal = -Epsilon;
233	BestAtt = None;
234	AvGain = (Possible ? AvGain / Possible : 1E6);
235
236	Verbosity(2) {
237	if (AvGain < 1E6)
238	printf("\taverage gain %.3f\n", AvGain);
239	}
240
241	ForEach(Att, 0, MaxAtt) {
242	if (Gain[Att] > -Epsilon) {
243	Val = Worth(Info[Att], Gain[Att], AvGain);
244	if (Val > BestVal) {
245	BestAtt = Att;
246	BestVal = Val;
247	}
248	}
249	}
250
251
252	/* Decide whether to branch or not */
253
254	if (BestAtt != None) {
255	Verbosity(1) {
256	printf("\tbest attribute %s", AttName[BestAtt]);
257	if (!MaxAttVal[BestAtt]) {
258	printf(" cut %.3f", Bar[BestAtt]);
259	}
260	printf(" inf %.3f gain %.3f val %.3f\n", Info[BestAtt],
261	Gain[BestAtt], BestVal);
262	}
263
264	/* Build a node of the selected test */
265
266	if (MaxAttVal[BestAtt]) {
267	/* Discrete valued attribute */
268
269	if (SUBSET && MaxAttVal[BestAtt] > 2) {
270	SubsetTest(Node, BestAtt);
271	} else {
272	DiscreteTest(Node, BestAtt);
273	}
274	} else {
275	/* Continuous attribute */
276
277	ContinTest(Node, BestAtt);
278	}
279
280	/* Remove unknown attribute values */
281
282	PrevAllKnown = AllKnown;
283
284	Kp = Group(0, Fp, Lp, Node) + 1;
285	if (Kp != Fp)
286	AllKnown = false;
287	KnownCases = Cases - CountItems(Fp, Kp - 1);
288	UnknownRate[BestAtt] = (Cases - KnownCases) / (Cases + 0.001);
289
290	Verbosity(1) {
291	if (UnknownRate[BestAtt] > 0) {
292	printf("\tunknown rate for %s = %.3f\n", AttName[BestAtt],
293	UnknownRate[BestAtt]);
294	}
295	}
296
297	/* Recursive divide and conquer */
298
299	++Tested[BestAtt];
300
301	Ep = Kp - 1;
302	Node->Errors = 0;
303
304	ForEach(v, 1, Node->Forks) {
305	Ep = Group(v, Kp, Lp, Node);
306
307	if (Kp <= Ep) {
308	Factor = CountItems(Kp, Ep) / KnownCases;
309
310	ForEach(i, Fp, Kp-1) {
311	Weight[i] *= Factor;
312	}
313
314	Node->Branch[v] = FormTree(Fp, Ep);
315	Node->Errors += Node->Branch[v]->Errors;
316
317	Group(0, Fp, Ep, Node);
318	ForEach(i, Fp, Kp-1) {
319	Weight[i] /= Factor;
320	}
321	} else {
322	Node->Branch[v] = Leaf(Node->ClassDist, BestClass, 0.0, 0.0);
323	}
324	}
325
326	--Tested[BestAtt];
327	AllKnown = PrevAllKnown;
328
329	/* See whether we would have been no worse off with a leaf */
330
331	if (Node->Errors >= Cases - NoBestClass - Epsilon) {
332	Verbosity(1)
333	printf("Collapse tree for %d items to leaf %s\n", Lp - Fp + 1,
334	ClassName[BestClass]);
335
336	Node->NodeType = 0;
337	}
338	}
339	else {
340	Verbosity(1)
341	printf("\tno sensible splits %.1f/%.1f\n", Cases, Cases
342	- NoBestClass);
343	}
344
345	return Node;
346	}
347
348	Tree FormTree_Discr(Fp, Lp)
349	/* --------- */
350	ItemNo Fp, Lp; {
351	ItemNo i, Kp, Ep, Group();
352	ItemCount Cases, NoBestClass, KnownCases, CountItems();
353	float Factor, BestVal, Val, AvGain = 0, Worth();
354	Attribute Att, BestAtt, Possible = 0;
355	ClassNo c, BestClass;
356	Tree Node, Leaf();
357	DiscrValue v;
358	Boolean PrevAllKnown;
359	ItemCount Freq_discr[MAX_DISCR_VAL + 1][MAX_CLASS + 1], ValFreq_discr[MAX_DISCR_VAL + 1];
360	float UnknownRate_discr[MAX_ATT + 1];
361
362	Cases = CountItems(Fp, Lp);
363
364	/* Generate the class frequency distribution */
365
366	// ########### begin parallel region ############## //
367	#pragma omp parallel default(shared)
368	{
369
370	//printf("The parallel region is executed by thread %d\n", omp_get_thread_num());
371	/* THIS CAN BE PARALELIZED */
372	#pragma omp for private(c)
373	ForEach(c, 0, MaxClass) {
374	ClassFreq[c] = 0;
375	}
376
377	/* THIS CAN BE PARALELIZED */
378	#pragma omp for private(i)
379	ForEach(i, Fp, Lp) {
380	#pragma omp atomic
381	ClassFreq[Class(Item[i])] += Weight[i];
382	}
383	}
384
385	/* Find the most frequent class */
386	/* THIS CAN BE PARALELIZED */
387	BestClass = 0;
388
389	ForEach(c, 0, MaxClass) {
390	if (ClassFreq[c] > ClassFreq[BestClass]) {
391	BestClass = c;
392	}
393	}
394
395	NoBestClass = ClassFreq[BestClass];
396
397	Node = Leaf(ClassFreq, BestClass, Cases, Cases - NoBestClass);
398
399	/* If all cases are of the same class or there are not enough
400	cases to divide, the tree is a leaf */
401
402	if (NoBestClass == Cases \|\| Cases < 2 * MINOBJS) {
403	return Node;
404	}
405
406	Verbosity(1)
407	printf("\n%d items, total weight %.1f\n", Lp - Fp + 1, Cases);
408
409
410	/* For each available attribute, find the information and gain */
411	/* THIS MUST BE PARALELIZED */
412	#pragma omp parallel default(shared) private(Freq_discr, ValFreq_discr, UnknownRate_discr)
413	{
414
415	#pragma omp for
416	ForEach(Att, 0, MaxAtt) {
417	Gain[Att] = -Epsilon;
418
419	if (SpecialStatus[Att] == IGNORE)
420	continue;
421
422	if (MaxAttVal[Att]) {
423	/* discrete valued attribute */
424
425	if (SUBSET && MaxAttVal[Att] > 2) {
426	EvalSubset(Att, Fp, Lp, Cases);
427	} else if (!Tested[Att]) {
428	EvalDiscreteAtt_Discr(Att, Fp, Lp, Cases, (ItemCount*)Freq_discr, (ItemCount)ValFreq_discr, (float*)UnknownRate_discr);
429	}
430	} else {
431	/* continuous attribute */
432
433	EvalContinuousAtt(Att, Fp, Lp);
434	}
435
436	/* Update average gain, excluding attributes with very many values */
437	#pragma omp critical
438	{
439	if (Gain[Att] > -Epsilon && (MultiVal \|\| MaxAttVal[Att] < 0.3
440	* (MaxItem + 1))) {
441	Possible++;
442	AvGain += Gain[Att];
443	}
444	}
445	}
446
447	}
448
449	/* Find the best attribute according to the given criterion */
450	//#pragma omp single
451	//{
452	BestVal = -Epsilon;
453	BestAtt = None;
454	AvGain = (Possible ? AvGain / Possible : 1E6);
455
456	Verbosity(2) {
457	if (AvGain < 1E6)
458	printf("\taverage gain %.3f\n", AvGain);
459	}
460
461	ForEach(Att, 0, MaxAtt) {
462	if (Gain[Att] > -Epsilon) {
463	Val = Worth(Info[Att], Gain[Att], AvGain);
464	if (Val > BestVal) {
465	BestAtt = Att;
466	BestVal = Val;
467	}
468	}
469	}
470	//}
471	//}
472	/* Decide whether to branch or not */
473
474	if (BestAtt != None) {
475	Verbosity(1) {
476	printf("\tbest attribute %s", AttName[BestAtt]);
477	if (!MaxAttVal[BestAtt]) {
478	printf(" cut %.3f", Bar[BestAtt]);
479	}
480	printf(" inf %.3f gain %.3f val %.3f\n", Info[BestAtt],
481	Gain[BestAtt], BestVal);
482	}
483
484	/* Build a node of the selected test */
485
486	if (MaxAttVal[BestAtt]) {
487	/* Discrete valued attribute */
488
489	if (SUBSET && MaxAttVal[BestAtt] > 2) {
490	SubsetTest(Node, BestAtt);
491	} else {
492	DiscreteTest(Node, BestAtt);
493	}
494	} else {
495	/* Continuous attribute */
496
497	ContinTest(Node, BestAtt);
498	}
499
500	/* Remove unknown attribute values */
501
502	PrevAllKnown = AllKnown;
503
504	Kp = Group(0, Fp, Lp, Node) + 1;
505	if (Kp != Fp)
506	AllKnown = false;
507	KnownCases = Cases - CountItems(Fp, Kp - 1);
508	UnknownRate[BestAtt] = (Cases - KnownCases) / (Cases + 0.001);
509
510	Verbosity(1) {
511	if (UnknownRate[BestAtt] > 0) {
512	printf("\tunknown rate for %s = %.3f\n", AttName[BestAtt],
513	UnknownRate[BestAtt]);
514	}
515	}
516
517	/* Recursive divide and conquer */
518
519	++Tested[BestAtt];
520
521	Ep = Kp - 1;
522	Node->Errors = 0;
523
524	ForEach(v, 1, Node->Forks) {
525	Ep = Group(v, Kp, Lp, Node);
526
527	if (Kp <= Ep) {
528	Factor = CountItems(Kp, Ep) / KnownCases;
529
530	ForEach(i, Fp, Kp-1) {
531	Weight[i] *= Factor;
532	}
533
534	Node->Branch[v] = FormTree(Fp, Ep);
535	Node->Errors += Node->Branch[v]->Errors;
536
537	Group(0, Fp, Ep, Node);
538	ForEach(i, Fp, Kp-1) {
539	Weight[i] /= Factor;
540	}
541	} else {
542	Node->Branch[v] = Leaf(Node->ClassDist, BestClass, 0.0, 0.0);
543	}
544	}
545
546	--Tested[BestAtt];
547	AllKnown = PrevAllKnown;
548
549	/* See whether we would have been no worse off with a leaf */
550
551	if (Node->Errors >= Cases - NoBestClass - Epsilon) {
552	Verbosity(1)
553	printf("Collapse tree for %d items to leaf %s\n", Lp - Fp + 1,
554	ClassName[BestClass]);
555
556	Node->NodeType = 0;
557	}
558	}
559	else {
560	Verbosity(1)
561	printf("\tno sensible splits %.1f/%.1f\n", Cases, Cases
562	- NoBestClass);
563	}
564
565	return Node;
566	}
567	/*************************************************************************/
568	/* */
569	/* Group together the items corresponding to branch V of a test */
570	/* and return the index of the last such */
571	/* */
572	/* Note: if V equals zero, group the unknown values */
573	/* */
574	/*************************************************************************/
575
576	ItemNo Group(V, Fp, Lp, TestNode)
577	/* ----- */
578	DiscrValue V;ItemNo Fp, Lp;Tree TestNode; {
579	ItemNo i;
580	Attribute Att;
581	float Thresh;
582	Set SS;
583	void Swap();
584
585	Att = TestNode->Tested;
586
587	if (V) {
588	/* Group items on the value of attribute Att, and depending
589	on the type of branch */
590
591	switch (TestNode->NodeType) {
592	case BrDiscr:
593
594	ForEach(i, Fp, Lp) {
595	if (DVal(Item[i], Att) == V)
596	Swap(Fp++, i);
597	}
598	break;
599
600	case ThreshContin:
601
602	Thresh = TestNode->Cut;
603	ForEach(i, Fp, Lp) {
604	if ((CVal(Item[i], Att) <= Thresh) == (V == 1))
605	Swap(Fp++, i);
606	}
607	break;
608
609	case BrSubset:
610
611	SS = TestNode->Subset[V];
612	ForEach(i, Fp, Lp) {
613	if (In(DVal(Item[i], Att), SS))
614	Swap(Fp++, i);
615	}
616	break;
617	}
618	} else {
619	/* Group together unknown values */
620
621	switch (TestNode->NodeType) {
622	case BrDiscr:
623	case BrSubset:
624
625	ForEach(i, Fp, Lp) {
626	if (!DVal(Item[i], Att))
627	Swap(Fp++, i);
628	}
629	break;
630
631	case ThreshContin:
632
633	ForEach(i, Fp, Lp) {
634	if (CVal(Item[i], Att) == Unknown)
635	Swap(Fp++, i);
636	}
637	break;
638	}
639	}
640
641	return Fp - 1;
642	}
643
644	/*************************************************************************/
645	/* */
646	/* Return the total weight of items from Fp to Lp */
647	/* */
648	/*************************************************************************/
649
650	ItemCount CountItems(Fp, Lp)
651	/* ---------- */
652	ItemNo Fp, Lp; {
653	register ItemCount Sum = 0.0, Wt, LWt;
654	ItemNo i;
655
656	if (AllKnown)
657	return Lp - Fp + 1;
658
659	//Lwt = Weight + Lp;
660
661	#pragma omp parallel for reduction(+:Sum)
662	for (i = Fp; i <= Lp; i++) {
663	Sum += Weight[i];
664	}
665
666	return Sum;
667	}
668
669	/*************************************************************************/
670	/* */
671	/* Exchange items at a and b */
672	/* */
673	/*************************************************************************/
674
675	void Swap(a, b)
676	/* ---- */
677	ItemNo a, b; {
678	register Description Hold;
679	register ItemCount HoldW;
680
681	Hold = Item[a];
682	Item[a] = Item[b];
683	Item[b] = Hold;
684
685	HoldW = Weight[a];
686	Weight[a] = Weight[b];
687	Weight[b] = HoldW;
688	}

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

Download in other formats: