source: proiecte/Parallel-DT/R8/Src/besttree.c @ 101

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