Context Navigation

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

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

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

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

Download in other formats: