source: proiecte/Parallel-DT/R8/Src/info.c @ 69

Last change on this file since 69 was 69, checked in by (none), 14 years ago
File size: 6.8 KB
Line 
1/*************************************************************************/
2/*                                                                       */
3/*      Calculate information, information gain, and print dists         */
4/*      --------------------------------------------------------         */
5/*                                                                       */
6/*************************************************************************/
7
8#include "buildex.i"
9
10
11/*************************************************************************/
12/*                                                                       */
13/*  Determine the worth of a particular split according to the           */
14/*  operative criterion                                                  */
15/*                                                                       */
16/*          Parameters:                                                  */
17/*              SplitInfo:      potential info of the split              */
18/*              SplitGain:      gain in info of the split                */
19/*              MinGain:        gain above which the Gain Ratio          */
20/*                              may be used                              */
21/*                                                                       */
22/*  If the Gain criterion is being used, the information gain of         */
23/*  the split is returned, but if the Gain Ratio criterion is            */
24/*  being used, the ratio of the information gain of the split to        */
25/*  its potential information is returned.                               */
26/*                                                                       */
27/*************************************************************************/
28
29float Worth(ThisInfo, ThisGain, MinGain)
30        /*    -----  */
31        float ThisInfo, ThisGain, MinGain; {
32        if (GAINRATIO) {
33                if (ThisGain >= MinGain - Epsilon && ThisInfo > Epsilon) {
34                        return ThisGain / ThisInfo;
35                } else {
36                        return -Epsilon;
37                }
38        } else {
39                return (ThisInfo > 0 && ThisGain > -Epsilon ? ThisGain : -Epsilon);
40        }
41}
42
43/*************************************************************************/
44/*                                                                       */
45/*  Zero the frequency tables Freq[][] and ValFreq[] up to MaxVal        */
46/*                                                                       */
47/*************************************************************************/
48
49ResetFreq(MaxVal, Freq, ValFreq)
50        /*  ---------  */
51        DiscrValue MaxVal; ItemCount** Freq; ItemCount* ValFreq; {
52        DiscrValue v;
53        ClassNo c;
54
55        #pragma omp parallel for private(v)
56        ForEach(v, 0, MaxVal) {
57                ForEach(c, 0, MaxClass) {
58                        Freq[v][c] = 0;
59                }
60                ValFreq[v] = 0;
61        }
62}
63
64/*************************************************************************/
65/*                                                                       */
66/*  Given tables Freq[][] and ValFreq[], compute the information gain.   */
67/*                                                                       */
68/*          Parameters:                                                  */
69/*              BaseInfo:       average information for all items with   */
70/*                              known values of the test attribute       */
71/*              UnknownRate:    fraction of items with unknown ditto     */
72/*              MaxVal:         number of forks                          */
73/*              TotalItems:     number of items with known values of     */
74/*                              test att                                 */
75/*                                                                       */
76/*  where Freq[x][y] contains the no. of cases with value x for a        */
77/*  particular attribute that are members of class y,                    */
78/*  and ValFreq[x] contains the no. of cases with value x for a          */
79/*  particular attribute                                                 */
80/*                                                                       */
81/*************************************************************************/
82
83float ComputeGain(BaseInfo, UnknFrac, MaxVal, TotalItems)
84        /*    -----------  */
85        float BaseInfo, UnknFrac;DiscrValue MaxVal;ItemCount TotalItems; {
86        DiscrValue v;
87        float ThisInfo = 0.0, ThisGain, TotalInfo();
88        short ReasonableSubsets = 0;
89
90        /*  Check whether all values are unknown or the same  */
91
92        if (!TotalItems)
93                return -Epsilon;
94
95        /*  There must be at least two subsets with MINOBJS items  */
96
97        ForEach(v, 1, MaxVal) {
98                if (ValFreq[v] >= MINOBJS)
99                        ReasonableSubsets++;
100        }
101        if (ReasonableSubsets < 2)
102                return -Epsilon;
103
104        /*  Compute total info after split, by summing the
105         info of each of the subsets formed by the test  */
106
107        //#pragma omp parallel for reduction(+:ThisInfo)
108        ForEach(v, 1, MaxVal) {
109                ThisInfo += TotalInfo(Freq[v], 0, MaxClass);
110        }
111
112        /*  Set the gain in information for all items, adjusted for unknowns  */
113
114        ThisGain = (1 - UnknFrac) * (BaseInfo - ThisInfo / TotalItems);
115
116        Verbosity(5)
117                printf(
118                                "ComputeThisGain: items %.1f info %.3f base %.3f unkn %.3f result %.3f\n",
119                                TotalItems + ValFreq[0], ThisInfo, BaseInfo, UnknFrac, ThisGain);
120
121        return ThisGain;
122}
123
124float ComputeGain_Discr(BaseInfo, UnknFrac, MaxVal, TotalItems, Freq, ValFreq)
125        /*    -----------  */
126        float BaseInfo, UnknFrac;DiscrValue MaxVal;ItemCount TotalItems; ItemCount** Freq; ItemCount* ValFreq; {
127        DiscrValue v;
128        float ThisInfo = 0.0, ThisGain, TotalInfo();
129        short ReasonableSubsets = 0;
130
131        /*  Check whether all values are unknown or the same  */
132
133        if (!TotalItems)
134                return -Epsilon;
135
136        /*  There must be at least two subsets with MINOBJS items  */
137
138        ForEach(v, 1, MaxVal) {
139                if (ValFreq[v] >= MINOBJS)
140                        ReasonableSubsets++;
141        }
142        if (ReasonableSubsets < 2)
143                return -Epsilon;
144
145        /*  Compute total info after split, by summing the
146         info of each of the subsets formed by the test  */
147
148        ForEach(v, 1, MaxVal) {
149                ThisInfo += TotalInfo(Freq[v], 0, MaxClass);
150        }
151
152        /*  Set the gain in information for all items, adjusted for unknowns  */
153
154        ThisGain = (1 - UnknFrac) * (BaseInfo - ThisInfo / TotalItems);
155
156        Verbosity(5)
157                printf(
158                                "ComputeThisGain: items %.1f info %.3f base %.3f unkn %.3f result %.3f\n",
159                                TotalItems + ValFreq[0], ThisInfo, BaseInfo, UnknFrac, ThisGain);
160
161        return ThisGain;
162}
163
164/*************************************************************************/
165/*                                                                       */
166/*  Compute the total information in V[ MinVal..MaxVal ]                 */
167/*                                                                       */
168/*************************************************************************/
169
170float TotalInfo(V, MinVal, MaxVal)
171        /*    ---------  */
172        ItemCount V[];DiscrValue MinVal, MaxVal; {
173        DiscrValue v;
174        float Sum = 0.0;
175        ItemCount N, TotalItems = 0;
176
177        ForEach(v, MinVal, MaxVal) {
178                N = V[v];
179
180                Sum += N * Log(N);
181                TotalItems += N;
182        }
183
184        return TotalItems * Log(TotalItems) - Sum;
185}
186
187/*************************************************************************/
188/*                                                                       */
189/*      Print distribution table for given attribute                     */
190/*                                                                       */
191/*************************************************************************/
192
193PrintDistribution(Att, MaxVal, ShowNames)
194        /*  -----------------  */
195        Attribute Att;DiscrValue MaxVal;Boolean ShowNames; {
196        DiscrValue v;
197        ClassNo c;
198        String Val;
199
200        printf("\n\t\t\t ");
201        ForEach(c, 0, MaxClass) {
202                printf("%7.6s", ClassName[c]);
203        }
204        printf("\n");
205
206        ForEach(v, 0, MaxVal) {
207                if (ShowNames) {
208                        Val = (!v ? "unknown" : MaxAttVal[Att] ? AttValName[Att][v] : v
209                                        == 1 ? "below" : "above");
210                        printf("\t\t[%-7.7s:", Val);
211                } else {
212                        printf("\t\t[%-7d:", v);
213                }
214
215                ForEach(c, 0, MaxClass) {
216                        printf(" %6.1f", Freq[v][c]);
217                }
218
219                printf("]\n");
220        }
221}
222
223PrintDistribution_Discr(Att, MaxVal, ShowNames, Freq)
224        /*  -----------------  */
225        Attribute Att;DiscrValue MaxVal;Boolean ShowNames; ItemCount** Freq;{
226        DiscrValue v;
227        ClassNo c;
228        String Val;
229
230        printf("\n\t\t\t ");
231        ForEach(c, 0, MaxClass) {
232                printf("%7.6s", ClassName[c]);
233        }
234        printf("\n");
235
236        ForEach(v, 0, MaxVal) {
237                if (ShowNames) {
238                        Val = (!v ? "unknown" : MaxAttVal[Att] ? AttValName[Att][v] : v
239                                        == 1 ? "below" : "above");
240                        printf("\t\t[%-7.7s:", Val);
241                } else {
242                        printf("\t\t[%-7d:", v);
243                }
244
245                ForEach(c, 0, MaxClass) {
246                        printf(" %6.1f", Freq[v][c]);
247                }
248
249                printf("]\n");
250        }
251}
Note: See TracBrowser for help on using the repository browser.