source: proiecte/Parallel-DT/R8/Src/besttree_v2.c @ 62

Last change on this file since 62 was 62, checked in by (none), 14 years ago
File size: 9.6 KB
Line 
1/*************************************************************************/
2/*                                                                       */
3/*      Routines to manage tree growth, pruning and evaluation           */
4/*      ------------------------------------------------------           */
5/*                                                                       */
6/*************************************************************************/
7
8#include "defns.i"
9#include "types.i"
10#include "extern.i"
11
12ItemNo *TargetClassFreq;
13Tree *Raw;
14extern Tree *Pruned;
15
16/*************************************************************************/
17/*                                                                       */
18/*      Grow and prune a single tree from all data                       */
19/*                                                                       */
20/*************************************************************************/
21
22OneTree()
23/*  ---------  */
24{
25        Tree FormTree(), CopyTree();
26        Boolean Prune();
27
28        InitialiseTreeData();
29        InitialiseWeights();
30
31        Raw = (Tree *) calloc(1, sizeof(Tree));
32        Pruned = (Tree *) calloc(1, sizeof(Tree));
33
34        AllKnown = true;
35
36        #pragma omp parallel default(shared)
37        {
38                #pragma omp single nowait
39                {
40                        Raw[0] = FormTree(0, MaxItem);
41                }
42        }
43        //printf("\n");
44        //PrintTree(Raw[0]);
45
46        SaveTree(Raw[0], ".unpruned");
47
48        Pruned[0] = CopyTree(Raw[0]);
49        if (Prune(Pruned[0])) {
50                //printf("\nSimplified ");
51                //PrintTree(Pruned[0]);
52        }
53}
54
55/*************************************************************************/
56/*                                                                       */
57/*      Grow and prune TRIALS trees and select the best of them          */
58/*                                                                       */
59/*************************************************************************/
60
61short BestTree()
62/*    --------  */
63{
64        Tree CopyTree(), Iterate();
65        Boolean Prune();
66        short t, Best = 0;
67
68        InitialiseTreeData();
69
70        TargetClassFreq = (ItemNo *) calloc(MaxClass + 1, sizeof(ItemNo));
71
72        Raw = (Tree *) calloc(TRIALS, sizeof(Tree));
73        Pruned = (Tree *) calloc(TRIALS, sizeof(Tree));
74
75        /*  If necessary, set initial size of window to 20% (or twice
76         the sqrt, if this is larger) of the number of data items,
77         and the maximum number of items that can be added to the
78         window at each iteration to 20% of the initial window size  */
79
80        if (!WINDOW) {
81                WINDOW = Max(2 * sqrt(MaxItem+1.0), (MaxItem+1) / 5);
82        }
83
84        if (!INCREMENT) {
85                INCREMENT = Max(WINDOW / 5, 1);
86        }
87
88        FormTarget(WINDOW);
89
90        /*  Form set of trees by iteration and prune  */
91
92        ForEach(t, 0, TRIALS-1 ) {
93                FormInitialWindow();
94
95                printf("\n--------\nTrial %d\n--------\n\n", t);
96
97                Raw[t] = Iterate(WINDOW, INCREMENT);
98                printf("\n");
99                PrintTree(Raw[t]);
100
101                SaveTree(Raw[t], ".unpruned");
102
103                Pruned[t] = CopyTree(Raw[t]);
104                if (Prune(Pruned[t])) {
105                        printf("\nSimplified ");
106                        PrintTree(Pruned[t]);
107                }
108
109                if (Pruned[t]->Errors < Pruned[Best]->Errors) {
110                        Best = t;
111                }
112        }
113        printf("\n--------\n");
114
115        return Best;
116}
117
118/*************************************************************************/
119/*                                                                       */
120/*  The windowing approach seems to work best when the class             */
121/*  distribution of the initial window is as close to uniform as         */
122/*  possible.  FormTarget generates this initial target distribution,    */
123/*  setting up a TargetClassFreq value for each class.                   */
124/*                                                                       */
125/*************************************************************************/
126
127FormTarget(Size)
128        /*  -----------  */
129        ItemNo Size; {
130        ItemNo i, *ClassFreq;
131        ClassNo c, Smallest, ClassesLeft = 0;
132
133        ClassFreq = (ItemNo *) calloc(MaxClass + 1, sizeof(ItemNo));
134
135        /*  Generate the class frequency distribution  */
136
137        ForEach(i, 0, MaxItem) {
138                ClassFreq[Class(Item[i])]++;
139        }
140
141        /*  Calculate the no. of classes of which there are items  */
142
143        ForEach(c, 0, MaxClass) {
144                if (ClassFreq[c]) {
145                        ClassesLeft++;
146                } else {
147                        TargetClassFreq[c] = 0;
148                }
149        }
150
151        while (ClassesLeft) {
152                /*  Find least common class of which there are some items  */
153
154                Smallest = -1;
155                ForEach(c, 0, MaxClass) {
156                        if (ClassFreq[c] && (Smallest < 0 || ClassFreq[c]
157                                        < ClassFreq[Smallest])) {
158                                Smallest = c;
159                        }
160                }
161
162                /*  Allocate the no. of items of this class to use in the window  */
163
164                TargetClassFreq[Smallest]
165                                = Min(ClassFreq[Smallest], Round(Size/ClassesLeft));
166
167                ClassFreq[Smallest] = 0;
168
169                Size -= TargetClassFreq[Smallest];
170                ClassesLeft--;
171        }
172
173        cfree(ClassFreq);
174}
175
176/*************************************************************************/
177/*                                                                       */
178/*  Form initial window, attempting to obtain the target class profile   */
179/*  in TargetClassFreq.  This is done by placing the targeted number     */
180/*  of items of each class at the beginning of the set of data items.    */
181/*                                                                       */
182/*************************************************************************/
183
184FormInitialWindow()
185/*  -------------------  */
186{
187        ItemNo i, Start = 0, More;
188        ClassNo c;
189        void Swap();
190
191        Shuffle();
192
193        ForEach(c, 0, MaxClass) {
194                More = TargetClassFreq[c];
195
196                for (i = Start; More; i++) {
197                        if (Class(Item[i]) == c) {
198                                Swap(Start, i);
199                                Start++;
200                                More--;
201                        }
202                }
203        }
204}
205
206/*************************************************************************/
207/*                                                                       */
208/*              Shuffle the data items randomly                          */
209/*                                                                       */
210/*************************************************************************/
211
212Shuffle()
213/*  -------  */
214{
215        ItemNo This, Alt, Left;
216        Description Hold;
217
218        This = 0;
219        for (Left = MaxItem + 1; Left;) {
220                Alt = This + (Left--) * Random;
221                Hold = Item[This];
222                Item[This++] = Item[Alt];
223                Item[Alt] = Hold;
224        }
225}
226
227/*************************************************************************/
228/*                                                                       */
229/*  Grow a tree iteratively with initial window size Window and          */
230/*  initial window increment IncExceptions.                              */
231/*                                                                       */
232/*  Construct a classifier tree using the data items in the              */
233/*  window, then test for the successful classification of other         */
234/*  data items by this tree.  If there are misclassified items,          */
235/*  put them immediately after the items in the window, increase         */
236/*  the size of the window and build another classifier tree, and        */
237/*  so on until we have a tree which successfully classifies all         */
238/*  of the test items or no improvement is apparent.                     */
239/*                                                                       */
240/*  On completion, return the tree which produced the least errors.      */
241/*                                                                       */
242/*************************************************************************/
243
244Tree Iterate(Window, IncExceptions)
245        /*   -------  */
246        ItemNo Window, IncExceptions; {
247        Tree Classifier, BestClassifier = Nil, FormTree();
248        ItemNo i, Errors, TotalErrors, BestTotalErrors = MaxItem + 1, Exceptions,
249                        Additions;
250        ClassNo Assigned, Category();
251        short Cycle = 0;
252        void Swap();
253
254        printf("Cycle   Tree    -----Cases----");
255        printf("    -----------------Errors-----------------\n");
256        printf("        size    window   other");
257        printf("    window  rate   other  rate   total  rate\n");
258        printf("-----   ----    ------  ------");
259        printf("    ------  ----  ------  ----  ------  ----\n");
260
261        do {
262                /*  Build a classifier tree with the first Window items  */
263
264                InitialiseWeights();
265                AllKnown = true;
266                Classifier = FormTree(0, Window - 1);
267
268                /*  Error analysis  */
269
270                Errors = Round(Classifier->Errors);
271
272                /*  Move all items that are incorrectly classified by the
273                 classifier tree to immediately after the items in the
274                 current window.  */
275
276                Exceptions = Window;
277                ForEach(i, Window, MaxItem) {
278                        Assigned = Category(Item[i], Classifier);
279                        if (Assigned != Class(Item[i])) {
280                                Swap(Exceptions, i);
281                                Exceptions++;
282                        }
283                }
284                Exceptions -= Window;
285                TotalErrors = Errors + Exceptions;
286
287                /*  Print error analysis  */
288
289                printf("%3d  %7d  %8d  %6d  %8d%5.1f%%  %6d%5.1f%%  %6d%5.1f%%\n",
290                                ++Cycle, TreeSize(Classifier), Window, MaxItem - Window + 1,
291                                Errors, 100 * (float) Errors / Window, Exceptions, 100
292                                                * Exceptions / (MaxItem - Window + 1.001), TotalErrors,
293                                100 * TotalErrors / (MaxItem + 1.0));
294
295                /*  Keep track of the most successful classifier tree so far  */
296
297                if (!BestClassifier || TotalErrors < BestTotalErrors) {
298                        if (BestClassifier)
299                                ReleaseTree(BestClassifier);
300                        BestClassifier = Classifier;
301                        BestTotalErrors = TotalErrors;
302                } else {
303                        ReleaseTree(Classifier);
304                }
305
306                /*  Increment window size  */
307
308                Additions = Min(Exceptions, IncExceptions);
309                Window = Min(Window + Max(Additions, Exceptions / 2), MaxItem + 1);
310        } while (Exceptions);
311
312        return BestClassifier;
313}
314
315/*************************************************************************/
316/*                                                                       */
317/*      Print report of errors for each of the trials                    */
318/*                                                                       */
319/*************************************************************************/
320
321Evaluate(CMInfo, Saved)
322        /*  --------  */
323        Boolean CMInfo;short Saved; {
324        ClassNo RealClass, PrunedClass, Category();
325        short t;
326        ItemNo *ConfusionMat, i, RawErrors, PrunedErrors;
327
328        if (CMInfo) {
329                ConfusionMat = (ItemNo *) calloc((MaxClass + 1) * (MaxClass + 1),
330                                sizeof(ItemNo));
331        }
332
333        printf("\n");
334
335        if (TRIALS > 1) {
336                printf("Trial\t Before Pruning           After Pruning\n");
337                printf("-----\t----------------   ---------------------------\n");
338        } else {
339                printf("\t Before Pruning           After Pruning\n");
340                printf("\t----------------   ---------------------------\n");
341        }
342        printf("\tSize      Errors   Size      Errors   Estimate\n\n");
343
344        ForEach(t, 0, TRIALS-1) {
345                RawErrors = PrunedErrors = 0;
346
347                ForEach(i, 0, MaxItem) {
348                        RealClass = Class(Item[i]);
349
350                        if (Category(Item[i], Raw[t]) != RealClass)
351                                RawErrors++;
352
353                        PrunedClass = Category(Item[i], Pruned[t]);
354
355                        if (PrunedClass != RealClass)
356                                PrunedErrors++;
357
358                        if (CMInfo && t == Saved) {
359                                ConfusionMat[RealClass * (MaxClass + 1) + PrunedClass]++;
360                        }
361                }
362
363                if (TRIALS > 1) {
364                        printf("%4d", t);
365                }
366
367                printf("\t%4d  %3d(%4.1f%%)   %4d  %3d(%4.1f%%)    (%4.1f%%)%s\n",
368                                TreeSize(Raw[t]), RawErrors, 100.0 * RawErrors
369                                                / (MaxItem + 1.0), TreeSize(Pruned[t]), PrunedErrors,
370                                100.0 * PrunedErrors / (MaxItem + 1.0), 100 * Pruned[t]->Errors
371                                                / Pruned[t]->Items, (t == Saved ? "   <<" : ""));
372        }
373
374        if (CMInfo) {
375                PrintConfusionMatrix(ConfusionMat);
376                free(ConfusionMat);
377        }
378}
Note: See TracBrowser for help on using the repository browser.