Context Navigation

build.c @ 116

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

File size: 16.8 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 if(Lp-Fp > 1000) shared(Possible, AvGain) private(thread_id)
413	{
414
415	#pragma omp for private(Att) schedule(static) reduction(+:Possible, AvGain)
416
417	ForEach(Att, 0, MaxAtt) {
418	Gain[Att] = -Epsilon;
419
420	if (SpecialStatus[Att] == IGNORE)
421	continue;
422
423	if (MaxAttVal[Att]) {
424	/* discrete valued attribute */
425
426	if (SUBSET && MaxAttVal[Att] > 2) {
427	EvalSubset(Att, Fp, Lp, Cases);
428	} else if (!Tested[Att]) {
429	thread_id = omp_get_thread_num();
430	//printf("thread_id = %d\n", thread_id);
431	EvalDiscreteAtt_Discr(Att, Fp, Lp, Cases, Freq_discr[thread_id],
432	ValFreq_discr[thread_id], UnknownRate_discr[thread_id], &Gain[Att], &Info[Att]);
433	}
434	} else {
435	/* continuous attribute */
436	EvalContinuousAtt(Att, Fp, Lp);
437	}
438
439	/* Update average gain, excluding attributes with very many values */
440
441	if (Gain[Att] > -Epsilon && (MultiVal \|\| MaxAttVal[Att] < 0.3 * (MaxItem + 1))){
442	//#pragma omp atomic
443	Possible++;
444
445	//#pragma omp atomic
446	AvGain += Gain[Att];
447	}
448
449	}
450
451	}
452
453	/* Find the best attribute according to the given criterion */
454
455	BestVal = -Epsilon;
456	BestAtt = None;
457	AvGain = (Possible ? AvGain / Possible : 1E6);
458
459	Verbosity(2) {
460	if (AvGain < 1E6)
461	printf("\taverage gain %.3f\n", AvGain);
462	}
463
464	ForEach(Att, 0, MaxAtt) {
465	if (Gain[Att] > -Epsilon) {
466	Val = Worth(Info[Att], Gain[Att], AvGain);
467	if (Val > BestVal) {
468	BestAtt = Att;
469	BestVal = Val;
470	}
471	}
472	}
473
474	/* Decide whether to branch or not */
475
476	if (BestAtt != None) {
477	Verbosity(1) {
478	printf("\tbest attribute %s", AttName[BestAtt]);
479	if (!MaxAttVal[BestAtt]) {
480	printf(" cut %.3f", Bar[BestAtt]);
481	}
482	printf(" inf %.3f gain %.3f val %.3f\n", Info[BestAtt],
483	Gain[BestAtt], BestVal);
484	}
485
486	/* Build a node of the selected test */
487
488	if (MaxAttVal[BestAtt]) {
489	/* Discrete valued attribute */
490
491	if (SUBSET && MaxAttVal[BestAtt] > 2) {
492	SubsetTest(Node, BestAtt);
493	} else {
494	DiscreteTest(Node, BestAtt);
495	}
496	} else {
497	/* Continuous attribute */
498
499	ContinTest(Node, BestAtt);
500	}
501
502	/* Remove unknown attribute values */
503
504	PrevAllKnown = AllKnown;
505
506	Kp = Group(0, Fp, Lp, Node) + 1;
507	if (Kp != Fp)
508	AllKnown = false;
509	KnownCases = Cases - CountItems(Fp, Kp - 1);
510	UnknownRate[BestAtt] = (Cases - KnownCases) / (Cases + 0.001);
511
512	Verbosity(1) {
513	if (UnknownRate[BestAtt] > 0) {
514	printf("\tunknown rate for %s = %.3f\n", AttName[BestAtt],
515	UnknownRate[BestAtt]);
516	}
517	}
518
519	/* Recursive divide and conquer */
520
521	++Tested[BestAtt];
522
523	Ep = Kp - 1;
524	Node->Errors = 0;
525
526	ForEach(v, 1, Node->Forks) {
527	Ep = Group(v, Kp, Lp, Node);
528
529	if (Kp <= Ep) {
530	Factor = CountItems(Kp, Ep) / KnownCases;
531
532	ForEach(i, Fp, Kp-1) {
533	Weight[i] *= Factor;
534	}
535
536	Node->Branch[v] = FormTree_Discr(Fp, Ep);
537	Node->Errors += Node->Branch[v]->Errors;
538
539	Group(0, Fp, Ep, Node);
540	ForEach(i, Fp, Kp-1) {
541	Weight[i] /= Factor;
542	}
543	} else {
544	Node->Branch[v] = Leaf(Node->ClassDist, BestClass, 0.0, 0.0);
545	}
546	}
547
548	--Tested[BestAtt];
549	AllKnown = PrevAllKnown;
550
551	/* See whether we would have been no worse off with a leaf */
552
553	if (Node->Errors >= Cases - NoBestClass - Epsilon) {
554	Verbosity(1)
555	printf("Collapse tree for %d items to leaf %s\n", Lp - Fp + 1,
556	ClassName[BestClass]);
557
558	Node->NodeType = 0;
559	}
560	}
561	else {
562	Verbosity(1)
563	printf("\tno sensible splits %.1f/%.1f\n", Cases, Cases
564	- NoBestClass);
565	}
566
567	return Node;
568	}
569	/*************************************************************************/
570	/* */
571	/* Group together the items corresponding to branch V of a test */
572	/* and return the index of the last such */
573	/* */
574	/* Note: if V equals zero, group the unknown values */
575	/* */
576	/*************************************************************************/
577
578	ItemNo Group(V, Fp, Lp, TestNode)
579	/* ----- */
580	DiscrValue V;ItemNo Fp, Lp;Tree TestNode; {
581	ItemNo i;
582	Attribute Att;
583	float Thresh;
584	Set SS;
585	void Swap();
586
587	Att = TestNode->Tested;
588
589	if (V) {
590	/* Group items on the value of attribute Att, and depending
591	on the type of branch */
592
593	switch (TestNode->NodeType) {
594	case BrDiscr:
595
596	ForEach(i, Fp, Lp) {
597	if (DVal(Item[i], Att) == V)
598	Swap(Fp++, i);
599	}
600	break;
601
602	case ThreshContin:
603
604	Thresh = TestNode->Cut;
605	ForEach(i, Fp, Lp) {
606	if ((CVal(Item[i], Att) <= Thresh) == (V == 1))
607	Swap(Fp++, i);
608	}
609	break;
610
611	case BrSubset:
612
613	SS = TestNode->Subset[V];
614	ForEach(i, Fp, Lp) {
615	if (In(DVal(Item[i], Att), SS))
616	Swap(Fp++, i);
617	}
618	break;
619	}
620	} else {
621	/* Group together unknown values */
622
623	switch (TestNode->NodeType) {
624	case BrDiscr:
625	case BrSubset:
626
627	ForEach(i, Fp, Lp) {
628	if (!DVal(Item[i], Att))
629	Swap(Fp++, i);
630	}
631	break;
632
633	case ThreshContin:
634
635	ForEach(i, Fp, Lp) {
636	if (CVal(Item[i], Att) == Unknown)
637	Swap(Fp++, i);
638	}
639	break;
640	}
641	}
642
643	return Fp - 1;
644	}
645
646	/*************************************************************************/
647	/* */
648	/* Return the total weight of items from Fp to Lp */
649	/* */
650	/*************************************************************************/
651
652	ItemCount CountItems(Fp, Lp)
653	/* ---------- */
654	ItemNo Fp, Lp; {
655	register ItemCount Sum = 0.0, Wt, LWt;
656	ItemNo i;
657
658	if (AllKnown)
659	return Lp - Fp + 1;
660
661	//Lwt = Weight + Lp;
662
663	for (i = Fp; i <= Lp; i++) {
664	Sum += Weight[i];
665	}
666
667	return Sum;
668	}
669
670	/*************************************************************************/
671	/* */
672	/* Exchange items at a and b */
673	/* */
674	/*************************************************************************/
675
676	void Swap(a, b)
677	/* ---- */
678	ItemNo a, b; {
679	register Description Hold;
680	register ItemCount HoldW;
681
682	Hold = Item[a];
683	Item[a] = Item[b];
684	Item[b] = Hold;
685
686	HoldW = Weight[a];
687	Weight[a] = Weight[b];
688	Weight[b] = HoldW;
689	}

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

Context Navigation

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

Download in other formats: