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

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