source: proiecte/Parallel-DT/R8/Src/build_v2.c @ 64

Last change on this file since 64 was 64, checked in by (none), 14 years ago
File size: 11.4 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
12
13   #include <omp.h>
14
15
16ItemCount *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
21float *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
26Boolean *Tested, /* Tested[a] set if att a has already been tested */
27MultiVal; /* true when all atts have many values */
28
29/*  External variables initialised here  */
30
31extern float *SplitGain, /* SplitGain[i] = gain with att value of item i as threshold */
32*SplitInfo; /* SplitInfo[i] = potential info ditto */
33
34extern ItemCount *Slice1, /* Slice1[c]    = saved values of Freq[x][c] in subset.c */
35*Slice2; /* Slice2[c]    = saved values of Freq[y][c] */
36
37extern Set **Subset; /* Subset[a][s] = subset s for att a */
38
39extern short *Subsets; /* Subsets[a] = no. subsets for att a */
40
41/*************************************************************************/
42/*                                                                       */
43/*              Allocate space for tree tables                           */
44/*                                                                       */
45/*************************************************************************/
46
47InitialiseTreeData()
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/*              Initialise the weight of each item                       */
103/*                                                                       */
104/*************************************************************************/
105
106InitialiseWeights()
107/*  -----------------  */
108{
109        ItemNo i;
110
111        ForEach(i, 0, MaxItem) {
112                Weight[i] = 1.0;
113        }
114}
115
116/*************************************************************************/
117/*                                                                       */
118/*  Build a decision tree for the cases Fp through Lp:                   */
119/*                                                                       */
120/*  - if all cases are of the same class, the tree is a leaf and so      */
121/*      the leaf is returned labelled with this class                    */
122/*                                                                       */
123/*  - for each attribute, calculate the potential information provided   */
124/*      by a test on the attribute (based on the probabilities of each   */
125/*      case having a particular value for the attribute), and the gain  */
126/*      in information that would result from a test on the attribute    */
127/*      (based on the probabilities of each case with a particular       */
128/*      value for the attribute being of a particular class)             */
129/*                                                                       */
130/*  - on the basis of these figures, and depending on the current        */
131/*      selection criterion, find the best attribute to branch on.       */
132/*      Note:  this version will not allow a split on an attribute       */
133/*      unless two or more subsets have at least MINOBJS items.          */
134/*                                                                       */
135/*  - try branching and test whether better than forming a leaf          */
136/*                                                                       */
137/*************************************************************************/
138
139Tree FormTree(Fp, Lp)
140        /*   ---------  */
141        ItemNo Fp, Lp; {
142        ItemNo i, Kp, Ep, Group();
143        ItemCount Cases, NoBestClass, KnownCases, CountItems();
144        float Factor, BestVal, Val, AvGain = 0, Worth();
145        Attribute Att, BestAtt, Possible = 0;
146        ClassNo c, BestClass;
147        Tree Node, Leaf();
148        DiscrValue v;
149        Boolean PrevAllKnown;
150
151        Cases = CountItems(Fp, Lp);
152
153        /*  Generate the class frequency distribution  */
154
155        //printf("The parallel region is executed by thread %d\n", omp_get_thread_num());
156
157        /* THIS CAN BE PARALELIZED */
158        ForEach(c, 0, MaxClass) {
159                ClassFreq[c] = 0;
160        }
161
162        /* THIS CAN BE PARALELIZED */
163        ForEach(i, Fp, Lp) {
164                ClassFreq[Class(Item[i])] += Weight[i];
165        }
166
167        /*  Find the most frequent class  */
168        /* THIS CAN BE PARALELIZED */
169        BestClass = 0;
170
171        ForEach(c, 0, MaxClass) {
172                if (ClassFreq[c] > ClassFreq[BestClass]) {
173                        BestClass = c;
174                }
175        }
176
177        NoBestClass = ClassFreq[BestClass];
178
179        Node = Leaf(ClassFreq, BestClass, Cases, Cases - NoBestClass);
180
181        /*  If all cases are of the same class or there are not enough
182         cases to divide, the tree is a leaf  */
183
184        if (NoBestClass == Cases || Cases < 2 * MINOBJS) {
185                return Node;
186        }
187
188        Verbosity(1)
189                printf("\n%d items, total weight %.1f\n", Lp - Fp + 1, Cases);
190
191        /*  For each available attribute, find the information and gain  */
192        /* THIS MUST BE PARALELIZED */
193
194        ForEach(Att, 0, MaxAtt) {
195                Gain[Att] = -Epsilon;
196
197                if (SpecialStatus[Att] == IGNORE)
198                        continue;
199
200                if (MaxAttVal[Att]) {
201                        /*  discrete valued attribute  */
202
203                        if (SUBSET && MaxAttVal[Att] > 2) {
204                                EvalSubset(Att, Fp, Lp, Cases);
205                        } else if (!Tested[Att]) {
206                                EvalDiscreteAtt(Att, Fp, Lp, Cases);
207                        }
208                } else {
209                        /*  continuous attribute  */
210
211                        EvalContinuousAtt(Att, Fp, Lp);
212                }
213
214                /*  Update average gain, excluding attributes with very many values  */
215
216                if (Gain[Att] > -Epsilon && (MultiVal || MaxAttVal[Att] < 0.3
217                                * (MaxItem + 1))) {
218                        Possible++;
219                        AvGain += Gain[Att];
220                }
221        }
222
223        /*  Find the best attribute according to the given criterion  */
224
225        BestVal = -Epsilon;
226        BestAtt = None;
227        AvGain = (Possible ? AvGain / Possible : 1E6);
228
229        Verbosity(2) {
230                if (AvGain < 1E6)
231                        printf("\taverage gain %.3f\n", AvGain);
232        }
233
234        ForEach(Att, 0, MaxAtt) {
235                if (Gain[Att] > -Epsilon) {
236                        Val = Worth(Info[Att], Gain[Att], AvGain);
237                        if (Val > BestVal) {
238                                BestAtt = Att;
239                                BestVal = Val;
240                        }
241                }
242        }
243
244        /*  Decide whether to branch or not  */
245
246        if (BestAtt != None) {
247                Verbosity(1) {
248                        printf("\tbest attribute %s", AttName[BestAtt]);
249                        if (!MaxAttVal[BestAtt]) {
250                                printf(" cut %.3f", Bar[BestAtt]);
251                        }
252                        printf(" inf %.3f gain %.3f val %.3f\n", Info[BestAtt],
253                                        Gain[BestAtt], BestVal);
254                }
255
256                /*  Build a node of the selected test  */
257
258                if (MaxAttVal[BestAtt]) {
259                        /*  Discrete valued attribute  */
260
261                        if (SUBSET && MaxAttVal[BestAtt] > 2) {
262                                SubsetTest(Node, BestAtt);
263                        } else {
264                                DiscreteTest(Node, BestAtt);
265                        }
266                } else {
267                        /*  Continuous attribute  */
268
269                        ContinTest(Node, BestAtt);
270                }
271
272                /*  Remove unknown attribute values  */
273
274                PrevAllKnown = AllKnown;
275
276                Kp = Group(0, Fp, Lp, Node) + 1;
277                if (Kp != Fp)
278                        AllKnown = false;
279                KnownCases = Cases - CountItems(Fp, Kp - 1);
280                UnknownRate[BestAtt] = (Cases - KnownCases) / (Cases + 0.001);
281
282                Verbosity(1) {
283                        if (UnknownRate[BestAtt] > 0) {
284                                printf("\tunknown rate for %s = %.3f\n", AttName[BestAtt],
285                                                UnknownRate[BestAtt]);
286                        }
287                }
288
289                /*  Recursive divide and conquer  */
290
291                ++Tested[BestAtt];
292
293                Ep = Kp - 1;
294                Node->Errors = 0;
295
296                ForEach(v, 1, Node->Forks) {
297                        Ep = Group(v, Kp, Lp, Node);
298
299                        if (Kp <= Ep) {
300                                Factor = CountItems(Kp, Ep) / KnownCases;
301
302                                ForEach(i, Fp, Kp-1) {
303                                        Weight[i] *= Factor;
304                                }
305
306                                #pragma omp task untied default(shared)
307                                {
308                                        Node->Branch[v] = FormTree(Fp, Ep);
309                                }
310
311                                #pragma omp taskwait
312                                Node->Errors += Node->Branch[v]->Errors;
313
314                                Group(0, Fp, Ep, Node);
315                                ForEach(i, Fp, Kp-1) {
316                                        Weight[i] /= Factor;
317                                }
318                        } else {
319                                Node->Branch[v] = Leaf(Node->ClassDist, BestClass, 0.0, 0.0);
320                        }
321                }
322
323                --Tested[BestAtt];
324                AllKnown = PrevAllKnown;
325
326                /*  See whether we would have been no worse off with a leaf  */
327
328                if (Node->Errors >= Cases - NoBestClass - Epsilon) {
329                        Verbosity(1)
330                                printf("Collapse tree for %d items to leaf %s\n", Lp - Fp + 1,
331                                                ClassName[BestClass]);
332
333                        Node->NodeType = 0;
334                }
335        } else {
336                Verbosity(1)
337                        printf("\tno sensible splits  %.1f/%.1f\n", Cases, Cases
338                                        - NoBestClass);
339        }
340
341        return Node;
342}
343
344/*************************************************************************/
345/*                                                                       */
346/*  Group together the items corresponding to branch V of a test         */
347/*  and return the index of the last such                                */
348/*                                                                       */
349/*  Note: if V equals zero, group the unknown values                     */
350/*                                                                       */
351/*************************************************************************/
352
353ItemNo Group(V, Fp, Lp, TestNode)
354        /*     -----  */
355        DiscrValue V;ItemNo Fp, Lp;Tree TestNode; {
356        ItemNo i;
357        Attribute Att;
358        float Thresh;
359        Set SS;
360        void Swap();
361
362        Att = TestNode->Tested;
363
364        if (V) {
365                /*  Group items on the value of attribute Att, and depending
366                 on the type of branch  */
367
368                switch (TestNode->NodeType) {
369                case BrDiscr:
370
371                        ForEach(i, Fp, Lp) {
372                                if (DVal(Item[i], Att) == V)
373                                        Swap(Fp++, i);
374                        }
375                        break;
376
377                case ThreshContin:
378
379                        Thresh = TestNode->Cut;
380                        ForEach(i, Fp, Lp) {
381                                if ((CVal(Item[i], Att) <= Thresh) == (V == 1))
382                                        Swap(Fp++, i);
383                        }
384                        break;
385
386                case BrSubset:
387
388                        SS = TestNode->Subset[V];
389                        ForEach(i, Fp, Lp) {
390                                if (In(DVal(Item[i], Att), SS))
391                                        Swap(Fp++, i);
392                        }
393                        break;
394                }
395        } else {
396                /*  Group together unknown values  */
397
398                switch (TestNode->NodeType) {
399                case BrDiscr:
400                case BrSubset:
401
402                        ForEach(i, Fp, Lp) {
403                                if (!DVal(Item[i], Att))
404                                        Swap(Fp++, i);
405                        }
406                        break;
407
408                case ThreshContin:
409
410                        ForEach(i, Fp, Lp) {
411                                if (CVal(Item[i], Att) == Unknown)
412                                        Swap(Fp++, i);
413                        }
414                        break;
415                }
416        }
417
418        return Fp - 1;
419}
420
421/*************************************************************************/
422/*                                                                       */
423/*      Return the total weight of items from Fp to Lp                   */
424/*                                                                       */
425/*************************************************************************/
426
427ItemCount CountItems(Fp, Lp)
428        /*        ----------  */
429        ItemNo Fp, Lp; {
430        register ItemCount Sum = 0.0, *Wt, *LWt;
431
432        if (AllKnown)
433                return Lp - Fp + 1;
434
435        for (Wt = Weight + Fp, LWt = Weight + Lp; Wt <= LWt;) {
436                Sum += *Wt++;
437        }
438
439        return Sum;
440}
441
442/*************************************************************************/
443/*                                                                       */
444/*              Exchange items at a and b                                */
445/*                                                                       */
446/*************************************************************************/
447
448void Swap(a, b)
449        /*   ----  */
450        ItemNo a, b; {
451        register Description Hold;
452        register ItemCount HoldW;
453
454        Hold = Item[a];
455        Item[a] = Item[b];
456        Item[b] = Hold;
457
458        HoldW = Weight[a];
459        Weight[a] = Weight[b];
460        Weight[b] = HoldW;
461}
Note: See TracBrowser for help on using the repository browser.