source: proiecte/Parallel-DT/R8/Src/discr.c @ 68

Last change on this file since 68 was 68, checked in by (none), 14 years ago
File size: 5.9 KB
Line 
1/*************************************************************************/
2/*                                                                       */
3/*      Evaluation of a test on a discrete valued attribute              */
4/*      ---------------------------------------------------              */
5/*                                                                       */
6/*************************************************************************/
7
8#include "buildex.i"
9
10/*************************************************************************/
11/*                                                                       */
12/*  Set Info[] and Gain[] for discrete partition of items Fp to Lp       */
13/*                                                                       */
14/*************************************************************************/
15
16EvalDiscreteAtt(Att, Fp, Lp, Items)
17        /*  ---------------  */
18        Attribute Att;ItemNo Fp, Lp;ItemCount Items; {
19        ItemCount KnownItems;
20        float DiscrKnownBaseInfo(), ComputeGain(), TotalInfo();
21
22        ComputeFrequencies(Att, Fp, Lp);
23
24        KnownItems = Items - ValFreq[0];
25
26        /*  Special case when no known values of the attribute  */
27
28        if (Items <= ValFreq[0]) {
29                Verbosity(2)
30                        printf("\tAtt %s: no known values\n", AttName[Att]);
31
32                Gain[Att] = -Epsilon;
33                Info[Att] = 0.0;
34                return;
35        }
36
37        Gain[Att] = ComputeGain(DiscrKnownBaseInfo(KnownItems, MaxAttVal[Att]),
38                        UnknownRate[Att], MaxAttVal[Att], KnownItems);
39        Info[Att] = TotalInfo(ValFreq, 0, MaxAttVal[Att]) / Items;
40
41        Verbosity(2) {
42                printf("\tAtt %s", AttName[Att]);
43                Verbosity(3)
44                        PrintDistribution(Att, MaxAttVal[Att], true);
45                printf("\tinf %.3f, gain %.3f\n", Info[Att], Gain[Att]);
46        }
47
48}
49
50EvalDiscreteAtt_Discr(Att, Fp, Lp, Items, Freq, ValFreq, UnknownRate)
51        /*  ---------------  */
52        Attribute Att;ItemNo Fp, Lp;ItemCount Items; ItemCount** Freq; ItemCount* ValFreq; float* UnknownRate; {
53        ItemCount KnownItems;
54        float DiscrKnownBaseInfo_Discr(), ComputeGain_Discr(), TotalInfo();
55
56        ComputeFrequencies_Discr(Att, Fp, Lp, Freq, ValFreq, UnknownRate);
57
58        KnownItems = Items - ValFreq[0];
59
60        /*  Special case when no known values of the attribute  */
61
62        if (Items <= ValFreq[0]) {
63                Verbosity(2)
64                        printf("\tAtt %s: no known values\n", AttName[Att]);
65
66                Gain[Att] = -Epsilon;
67                Info[Att] = 0.0;
68                return;
69        }
70
71        Gain[Att] = ComputeGain_Discr(DiscrKnownBaseInfo_Discr(KnownItems, MaxAttVal[Att], Freq),
72                        UnknownRate[Att], MaxAttVal[Att], KnownItems, Freq, ValFreq);
73        Info[Att] = TotalInfo(ValFreq, 0, MaxAttVal[Att]) / Items;
74
75        Verbosity(2) {
76                printf("\tAtt %s", AttName[Att]);
77                Verbosity(3)
78                        PrintDistribution_Discr(Att, MaxAttVal[Att], true, Freq);
79                printf("\tinf %.3f, gain %.3f\n", Info[Att], Gain[Att]);
80        }
81
82}
83/*************************************************************************/
84/*                                                                       */
85/*  Compute frequency tables Freq[][] and ValFreq[] for attribute        */
86/*  Att from items Fp to Lp, and set the UnknownRate for Att             */
87/*                                                                       */
88/*************************************************************************/
89
90ComputeFrequencies(Att, Fp, Lp)
91        /*  ------------------  */
92        Attribute Att;ItemNo Fp, Lp; {
93        Description Case;
94        ClassNo c;
95        DiscrValue v;
96        ItemCount CountItems();
97        ItemNo p;
98
99        ResetFreq(MaxAttVal[Att], Freq, ValFreq);
100
101        /*  Determine the frequency of each class amongst cases
102         with each possible value for the given attribute  */
103
104        #pragma omp parallel for private(p, Case)
105        ForEach(p, Fp, Lp) {
106                Case = Item[p];
107                #pragma omp critical
108                Freq[DVal(Case,Att)][Class(Case)] += Weight[p];
109        }
110
111        /*  Determine the frequency of each possible value for the
112         given attribute  */
113
114        #pragma omp parallel for private(v)
115        ForEach(v, 0, MaxAttVal[Att]) {
116                ForEach(c, 0, MaxClass) {
117                        ValFreq[v] += Freq[v][c];
118                }
119        }
120
121        /*  Set the rate of unknown values of the attribute  */
122
123        UnknownRate[Att] = ValFreq[0] / CountItems(Fp, Lp);
124}
125
126ComputeFrequencies_Discr(Att, Fp, Lp, Freq, ValFreq, UnknownRate)
127        /*  ------------------  */
128        Attribute Att;ItemNo Fp, Lp; ItemCount** Freq; ItemCount* ValFreq; float* UnknownRate;{
129        Description Case;
130        ClassNo c;
131        DiscrValue v;
132        ItemCount CountItems();
133        ItemNo p;
134
135        ResetFreq(MaxAttVal[Att], Freq, ValFreq);
136
137        /*  Determine the frequency of each class amongst cases
138         with each possible value for the given attribute  */
139
140        ForEach(p, Fp, Lp) {
141                Case = Item[p];
142                Freq[DVal(Case,Att)][Class(Case)] += Weight[p];
143        }
144
145        /*  Determine the frequency of each possible value for the
146         given attribute  */
147
148        ForEach(v, 0, MaxAttVal[Att]) {
149                ForEach(c, 0, MaxClass) {
150                        ValFreq[v] += Freq[v][c];
151                }
152        }
153
154        /*  Set the rate of unknown values of the attribute  */
155
156        UnknownRate[Att] = ValFreq[0] / CountItems(Fp, Lp);
157}
158/*************************************************************************/
159/*                                                                       */
160/*  Return the base info for items with known values of a discrete       */
161/*  attribute, using the frequency table Freq[][]                        */
162/*                                                                       */
163/*************************************************************************/
164
165float DiscrKnownBaseInfo(KnownItems, MaxVal)
166        /*    ------------------  */
167        DiscrValue MaxVal;ItemCount KnownItems; {
168        ClassNo c;
169        ItemCount ClassCount;
170        double Sum = 0;
171        DiscrValue v;
172
173        //#pragma omp parallel for
174        ForEach(c, 0, MaxClass) {
175                ClassCount = 0;
176                ForEach(v, 1, MaxVal) {
177                        ClassCount += Freq[v][c];
178                }
179                Sum += ClassCount * Log(ClassCount);
180        }
181
182        return (KnownItems * Log(KnownItems) - Sum) / KnownItems;
183}
184
185float DiscrKnownBaseInfo_Discr(KnownItems, MaxVal, Freq)
186        /*    ------------------  */
187        DiscrValue MaxVal;ItemCount KnownItems; ItemCount** Freq;{
188        ClassNo c;
189        ItemCount ClassCount;
190        double Sum = 0;
191        DiscrValue v;
192
193        ForEach(c, 0, MaxClass) {
194                ClassCount = 0;
195                ForEach(v, 1, MaxVal) {
196                        ClassCount += Freq[v][c];
197                }
198                Sum += ClassCount * Log(ClassCount);
199        }
200
201        return (KnownItems * Log(KnownItems) - Sum) / KnownItems;
202}
203
204/*************************************************************************/
205/*                                                                       */
206/*  Construct and return a node for a test on a discrete attribute       */
207/*                                                                       */
208/*************************************************************************/
209
210DiscreteTest(Node, Att)
211        /*  ----------  */
212        Tree Node;Attribute Att; {
213        ItemCount CountItems();
214
215        Sprout(Node, MaxAttVal[Att]);
216
217        Node->NodeType = BrDiscr;
218        Node->Tested = Att;
219        Node->Errors = 0;
220}
Note: See TracBrowser for help on using the repository browser.