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

Last change on this file since 22 was 22, checked in by (none), 14 years ago

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