source: proiecte/Parallel-DT/R8/Src/subset.c @ 70

Last change on this file since 70 was 70, checked in by (none), 14 years ago
File size: 9.1 KB
Line 
1/*************************************************************************/
2/*                                                                       */
3/*      Evaluation of the subsetting of a discrete attribute             */
4/*      ----------------------------------------------------             */
5/*                                                                       */
6/*************************************************************************/
7
8#include "buildex.i"
9
10ItemCount *Slice1, /* Slice1[c]    = saved values of Freq[x][c] in subset.c */
11*Slice2; /* Slice2[c]    = saved values of Freq[y][c] */
12
13Set **Subset; /* Subset[a][s] = subset s for att a */
14
15short *Subsets; /* Subsets[a] = no. subsets for att a */
16
17/*************************************************************************/
18/*                                                                       */
19/*  Evaluate subsetting a discrete attribute and form the chosen         */
20/*  subsets Subset[Att][], setting Subsets[Att] to the number of         */
21/*  subsets, and the Info[] and Gain[] of a test on the attribute        */
22/*                                                                       */
23/*************************************************************************/
24
25EvalSubset(Att, Fp, Lp, Items)
26        /*  ----------  */
27        Attribute Att;ItemNo Fp, Lp;ItemCount Items; {
28        DiscrValue V1, V2, BestV1, BestV2, Barred;
29        ItemCount KnownItems;
30        ClassNo c;
31        float BaseInfo, MinGain, ThisGain, ThisInfo, Val, BestVal, BestGain,
32                        BestInfo, PrevVal, PrevGain, PrevInfo, DiscrKnownBaseInfo(),
33                        Worth(), ComputeGain(), TotalInfo();
34        short Blocks = 0, MissingValues = 0, ReasonableSubsets, Bytes, b;
35        Boolean MergedSubsets = false;
36        int SaveMINOBJS;
37
38        SaveMINOBJS = MINOBJS;
39        MINOBJS = 1;
40
41        /*  First compute Freq[][], ValFreq[], base info, and the gain
42         and total info of a split on discrete attribute Att  */
43
44        ComputeFrequencies(Att, Fp, Lp);
45
46        KnownItems = Items - ValFreq[0];
47        if (KnownItems < Epsilon) {
48                Verbosity(2)
49                        printf("\tAtt %s: no known values\n", AttName[Att]);
50
51                Gain[Att] = -Epsilon;
52                Info[Att] = 0;
53                return;
54        }
55
56        BaseInfo = DiscrKnownBaseInfo(KnownItems, MaxAttVal[Att]);
57
58        PrevGain = ComputeGain(BaseInfo, UnknownRate[Att], MaxAttVal[Att],
59                        KnownItems);
60        PrevInfo = TotalInfo(ValFreq, 0, MaxAttVal[Att]) / Items;
61        PrevVal = Worth(PrevInfo, PrevGain, Epsilon);
62
63        Verbosity(2) {
64                printf("\tAtt %s", AttName[Att]);
65
66                Verbosity(3)
67                        PrintDistribution(Att, MaxAttVal[Att], true);
68
69                printf("\tinf %.3f, gain %.3f, val=%.3f\n", PrevInfo, PrevGain, PrevVal);
70        }
71
72        /*  Eliminate unrepresented attribute values from Freq[] and ValFreq[]
73         and form a separate subset for each represented attribute value  */
74
75        Bytes = (MaxAttVal[Att] >> 3) + 1;
76        ClearBits(Bytes, Subset[Att][0]);
77
78        ForEach(V1, 1, MaxAttVal[Att]) {
79                if (ValFreq[V1] > 0.5) {
80                        if (++Blocks < V1) {
81                                ValFreq[Blocks] = ValFreq[V1];
82                                ForEach(c, 0, MaxClass) {
83                                        Freq[Blocks][c] = Freq[V1][c];
84                                }
85                        }
86                        ClearBits(Bytes, Subset[Att][Blocks]);
87                        SetBit(V1, Subset[Att][Blocks]);
88                } else {
89                        SetBit(V1, Subset[Att][0]);
90                        MissingValues++;
91                }
92        }
93
94        /*  Merge any single-class subsets with others of the same class  */
95        /*  Note: have ValFreq[V] > 0 for all V  */
96
97        ForEach(V1, 1, Blocks-1) {
98                for (c = 0; Freq[V1][c] < 0.1; c++)
99                        ;
100
101                if (Freq[V1][c] < ValFreq[V1] - 0.1)
102                        continue;
103
104                /*  Now have a single class -- look for others  */
105
106                for (V2 = V1 + 1; V2 <= Blocks;) {
107                        if (Freq[V2][c] < ValFreq[V2] - 0.1) {
108                                V2++;
109                        } else {
110                                /*  Merge these subsets  */
111
112                                Combine(V1, V2, Blocks);
113
114                                ForEach(b, 0, Bytes-1) {
115                                        Subset[Att][V1][b] |= Subset[Att][V2][b];
116                                        Subset[Att][V2][b] = Subset[Att][Blocks][b];
117                                }
118
119                                Blocks--;
120                                MergedSubsets = true;
121                        }
122                }
123        }
124
125        if (MergedSubsets) {
126                PrevGain = ComputeGain(BaseInfo, UnknownRate[Att], Blocks, KnownItems);
127                PrevInfo = TotalInfo(ValFreq, 0, Blocks) / Items;
128                PrevVal = Worth(PrevInfo, PrevGain, Epsilon);
129
130                Verbosity(2) {
131                        printf("\tAfter merging single-class subsets:");
132
133                        Verbosity(3)
134                                PrintDistribution(Att, Blocks, false);
135
136                        printf("\tinf %.3f, gain %.3f, val=%.3f\n", PrevInfo, PrevGain,
137                                        PrevVal);
138                }
139        }
140
141        /*  Examine possible pair mergers and hill-climb  */
142
143        MinGain = PrevGain / 2;
144
145        while (Blocks > 2) {
146                BestVal = BestV1 = 0;
147                BestGain = -Epsilon;
148
149                /*  Check reasonable subsets; if less than 3, bar mergers
150                 involving the largest block  */
151
152                ReasonableSubsets = 0;
153                Barred = 1;
154
155                ForEach(V1, 1, Blocks) {
156                        if (ValFreq[V1] >= SaveMINOBJS)
157                                ReasonableSubsets++;
158
159                        if (ValFreq[V1] > ValFreq[Barred])
160                                Barred = V1;
161                }
162
163                if (ReasonableSubsets >= 3)
164                        Barred = 0;
165
166                /*  For each possible pair of values, calculate the gain and
167                 total info of a split in which they are treated as one.
168                 Keep track of the pair with the best gain.  */
169
170                ForEach(V1, 1, Blocks-1) {
171                        ForEach(V2, V1+1, Blocks) {
172                                if (V1 == Barred || V2 == Barred)
173                                        continue;
174
175                                Combine(V1, V2, Blocks);
176
177                                ThisGain = ComputeGain(BaseInfo, UnknownRate[Att], Blocks - 1,
178                                                KnownItems);
179                                ThisInfo = TotalInfo(ValFreq, 0, Blocks - 1) / Items;
180                                Val = Worth(ThisInfo, ThisGain, Epsilon);
181
182                                Verbosity(4) {
183                                        printf("\tcombine %d %d info %.3f gain %.3f val %.3f", V1,
184                                                        V2, ThisInfo, ThisGain, Val);
185                                        PrintDistribution(Att, Blocks - 1, false);
186                                }
187
188                                /*  Force a split if
189                                 less than two reasonable subsets, or
190                                 using GAIN criterion
191                                 Prefer this split to the previous one if
192                                 gain >= MinGain (and previous < MinGain), or
193                                 val >= previous best val  */
194
195                                if (ThisGain >= MinGain && BestGain < MinGain || Val >= BestVal
196                                                || !BestV1 && (!GAINRATIO || ReasonableSubsets < 2)) {
197                                        BestVal = Val;
198                                        BestGain = ThisGain;
199                                        BestInfo = ThisInfo;
200                                        BestV1 = V1;
201                                        BestV2 = V2;
202                                }
203
204                                Uncombine(V1, V2);
205                        }
206                }
207
208                if (GAINRATIO && ReasonableSubsets >= 2 && (!BestV1 || BestVal
209                                < PrevVal + 1E-5 || BestVal == PrevVal && BestGain < PrevGain))
210                        break;
211
212                PrevGain = BestGain;
213                PrevInfo = BestInfo;
214                PrevVal = BestVal;
215
216                Combine(BestV1, BestV2, Blocks);
217
218                ForEach(b, 0, Bytes-1) {
219                        Subset[Att][BestV1][b] |= Subset[Att][BestV2][b];
220                        Subset[Att][BestV2][b] = Subset[Att][Blocks][b];
221                }
222
223                Blocks--;
224
225                Verbosity(2) {
226                        printf("\t\tform subset ");
227                        PrintSubset(Att, Subset[Att][BestV1]);
228                        printf(": %d subsets, inf %.3f, gain %.3f, val %.3f\n", Blocks,
229                                        BestInfo, BestGain, BestVal);
230                        Verbosity(3) {
231                                printf("\t\tcombine %d, %d", BestV1, BestV2);
232                                PrintDistribution(Att, Blocks, false);
233                        }
234                }
235        }
236
237        MINOBJS = SaveMINOBJS;
238
239        if (PrevVal <= 0) {
240                Gain[Att] = -Epsilon;
241                Info[Att] = 0;
242        } else {
243                Gain[Att] = ComputeGain(BaseInfo, UnknownRate[Att], Blocks, KnownItems);
244                Info[Att] = PrevInfo;
245
246                if (MissingValues) {
247                        Blocks++;
248                        CopyBits(Bytes, Subset[Att][0], Subset[Att][Blocks]);
249                }
250
251                Subsets[Att] = Blocks;
252
253                Verbosity(2)
254                        printf("\tFinal subsets:");
255                Verbosity(3)
256                        PrintDistribution(Att, Blocks, false);
257                Verbosity(2)
258                        printf("\tinf %.3f gain %.3f val %.3f\n", Info[Att], Gain[Att],
259                                        Worth(Info[Att], Gain[Att], Epsilon));
260        }
261}
262
263/*************************************************************************/
264/*                                                                       */
265/*  Combine the distribution figures of discrete attribute values        */
266/*  x and y, putting the combined figures in Freq[x][] and               */
267/*  ValFreq[x][], and saving old values in Slice1 and Slice2             */
268/*                                                                       */
269/*************************************************************************/
270
271Combine(x, y, Last)
272        /*  -------  */
273        DiscrValue x, y, Last; {
274        ClassNo c;
275
276        ForEach(c, 0, MaxClass) {
277                Slice1[c] = Freq[x][c];
278                Slice2[c] = Freq[y][c];
279
280                Freq[x][c] += Freq[y][c];
281                Freq[y][c] = Freq[Last][c];
282        }
283
284        Slice1[MaxClass + 1] = ValFreq[x];
285        Slice2[MaxClass + 1] = ValFreq[y];
286
287        ValFreq[x] += ValFreq[y];
288        ValFreq[y] = ValFreq[Last];
289}
290
291/*************************************************************************/
292/*                                                                       */
293/*  Restore old class distribution figures of discrete attribute         */
294/*  values x and y from Slice1 and Slice2                                */
295/*                                                                       */
296/*************************************************************************/
297
298Uncombine(x, y)
299        /*  ---------  */
300        DiscrValue x, y; {
301        ClassNo c;
302
303        ForEach(c, 0, MaxClass) {
304                Freq[x][c] = Slice1[c];
305                Freq[y][c] = Slice2[c];
306        }
307
308        ValFreq[x] = Slice1[MaxClass + 1];
309        ValFreq[y] = Slice2[MaxClass + 1];
310}
311
312/*************************************************************************/
313/*                                                                       */
314/*  Print the values of attribute Att which are in the subset Ss         */
315/*                                                                       */
316/*************************************************************************/
317
318PrintSubset(Att, Ss)
319        /*  -----------  */
320        Attribute Att;Set Ss; {
321        DiscrValue V1;
322        Boolean First = true;
323
324        ForEach(V1, 1, MaxAttVal[Att]) {
325                if (In(V1, Ss)) {
326                        if (First) {
327                                First = false;
328                        } else {
329                                printf(", ");
330                        }
331
332                        printf("%s", AttValName[Att][V1]);
333                }
334        }
335}
336
337/*************************************************************************/
338/*                                                                       */
339/*  Construct and return a node for a test on a subset of values         */
340/*                                                                       */
341/*************************************************************************/
342
343SubsetTest(Node, Att)
344        /*  -----------  */
345        Tree Node;Attribute Att; {
346        ItemCount CountItems();
347        short S, Bytes;
348
349        Sprout(Node, Subsets[Att]);
350
351        Node->NodeType = BrSubset;
352        Node->Tested = Att;
353        Node->Errors = 0;
354
355        Bytes = (MaxAttVal[Att] >> 3) + 1;
356        Node->Subset = (Set *) calloc(Subsets[Att] + 1, sizeof(Set));
357        ForEach(S, 1, Node->Forks) {
358                Node->Subset[S] = (Set) malloc(Bytes);
359                CopyBits(Bytes, Subset[Att][S], Node->Subset[S]);
360        }
361}
Note: See TracBrowser for help on using the repository browser.