Context Navigation

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

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

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

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

Download in other formats: