source: orange/source/orange/tdidt_split.cpp @ 10992:cb84adf86ce5

Revision 10992:cb84adf86ce5, 39.1 KB checked in by Janez Demšar <janez.demsar@…>, 19 months ago (diff)

Fixed a bug in TTreeSplitConstructor_ExhaustiveBinary: invalid selection of the best split

Line 
1/*
2    This file is part of Orange.
3   
4    Copyright 1996-2010 Faculty of Computer and Information Science, University of Ljubljana
5    Contact: janez.demsar@fri.uni-lj.si
6
7    Orange is free software: you can redistribute it and/or modify
8    it under the terms of the GNU General Public License as published by
9    the Free Software Foundation, either version 3 of the License, or
10    (at your option) any later version.
11
12    Orange is distributed in the hope that it will be useful,
13    but WITHOUT ANY WARRANTY; without even the implied warranty of
14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15    GNU General Public License for more details.
16
17    You should have received a copy of the GNU General Public License
18    along with Orange.  If not, see <http://www.gnu.org/licenses/>.
19*/
20
21
22#include "measures.hpp"
23#include "random.hpp"
24#include "classfromvar.hpp"
25#include "discretize.hpp"
26#include "table.hpp"
27
28#include "boolcnt.hpp"
29#include "tdidt.hpp"
30#include "tdidt_stop.hpp"
31
32#include "tdidt_split.ppp"
33
34
35TTreeSplitConstructor::TTreeSplitConstructor(const float &aml)
36: minSubset(aml>0 ? aml : 1e-20)
37{}
38
39
40
41TTreeSplitConstructor_Measure::TTreeSplitConstructor_Measure(PMeasureAttribute meas, const float &aworst, const float &aml)
42: TTreeSplitConstructor(aml),
43  measure(meas),
44  worstAcceptable(aworst)
45{}
46
47
48
49TTreeSplitConstructor_Combined::TTreeSplitConstructor_Combined(PTreeSplitConstructor discreteSplit, PTreeSplitConstructor continuousSplit, const float &aminSubset)
50: TTreeSplitConstructor(aminSubset),
51  discreteSplitConstructor(discreteSplit),
52  continuousSplitConstructor(continuousSplit)
53{}
54
55
56
57PClassifier TTreeSplitConstructor_Combined::operator()(
58                             PStringList &descriptions, PDiscDistribution &subsetSizes, float &quality, int &spentAttribute,
59
60                             PExampleGenerator gen, const int &weightID ,
61                             PDomainContingency dcont, PDistribution apriorClass,
62                             const vector<bool> &candidates,
63                             PClassifier nodeClassifier
64                            )
65{ checkProperty(discreteSplitConstructor);
66  checkProperty(continuousSplitConstructor);
67
68  vector<bool> discrete, continuous;
69 
70  bool cse = candidates.size()==0;
71  vector<bool>::const_iterator ci(candidates.begin()), ce(candidates.end());
72  TVarList::const_iterator vi(gen->domain->attributes->begin()), ve(gen->domain->attributes->end());
73
74  for(; (cse || (ci!=ce)) && (vi!=ve); vi++) {
75    if (cse || *(ci++))
76      if ((*vi)->varType == TValue::INTVAR) {
77        discrete.push_back(true);
78        continuous.push_back(false);
79        continue;
80      }
81      else if ((*vi)->varType == TValue::FLOATVAR) {
82        discrete.push_back(false);
83        continuous.push_back(true);
84        continue;
85      }
86    discrete.push_back(false);
87    continuous.push_back(false);
88  }
89
90  float discQuality;
91  PStringList discDescriptions;
92  PDiscDistribution discSizes;
93  int discSpent;
94  PClassifier discSplit = discreteSplitConstructor->call(discDescriptions, discSizes, discQuality, discSpent,
95                                                               gen, weightID, dcont, apriorClass, discrete, nodeClassifier);
96
97  float contQuality;
98  PStringList contDescriptions;
99  PDiscDistribution contSizes;
100  int contSpent;
101  PClassifier contSplit = continuousSplitConstructor->call(contDescriptions, contSizes, contQuality, contSpent,
102                                                                 gen, weightID, dcont, apriorClass, continuous, nodeClassifier);
103
104  int N = gen ? gen->numberOfExamples() : -1;
105  if (N<0)
106    N = dcont->classes->cases;
107
108  if (   discSplit
109      && (   !contSplit
110          || (discQuality>contQuality)
111          || (discQuality==contQuality) && (N%2>0))) {
112    quality = discQuality;
113    descriptions = discDescriptions;
114    subsetSizes = discSizes;
115    spentAttribute = discSpent;
116    return discSplit;
117  }
118  else if (contSplit) {
119    quality = contQuality;
120    descriptions = contDescriptions;
121    subsetSizes = contSizes;
122    spentAttribute = contSpent;
123    return contSplit;
124  }
125  else 
126    return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
127}
128
129
130
131TTreeSplitConstructor_Attribute::TTreeSplitConstructor_Attribute(PMeasureAttribute meas, const float &worst, const float &ms)
132: TTreeSplitConstructor_Measure(meas, worst, ms)
133{}
134
135
136// rejects the split if there are less than two non-empty branches
137// or there is a non-empty branch with less then minSubset examples
138bool checkDistribution(const TDiscDistribution &dist, const float &minSubset)
139{
140  int nonzero = 0;
141  for(TDiscDistribution::const_iterator dvi(dist.begin()), dve(dist.end()); dvi!=dve; dvi++)
142    if (*dvi > 0) {
143      if  (*dvi < minSubset)
144        return false;
145      nonzero++;
146    }
147
148  return nonzero >= 2;
149}
150
151
152
153inline bool noCandidates(const vector<bool> &candidates)
154{
155  vector<bool>::const_iterator ci(candidates.begin()), ce(candidates.end());
156  while(ci!=ce && !*ci)
157    ci++;
158  return ci==ce;
159}
160
161PClassifier TTreeSplitConstructor_Attribute::operator()(
162                             PStringList &descriptions, PDiscDistribution &subsetSizes, float &quality, int &spentAttribute,
163
164                             PExampleGenerator gen, const int &weightID,
165                             PDomainContingency dcont, PDistribution apriorClass,
166                             const vector<bool> &candidates,
167                             PClassifier nodeClassifier
168                            )
169{ checkProperty(measure);
170
171  measure->checkClassTypeExc(gen->domain->classVar->varType);
172
173  bool cse = candidates.size()==0;
174  vector<bool>::const_iterator ci(candidates.begin()), ce(candidates.end());
175  if (!cse) {
176    if (noCandidates(candidates))
177      return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
178
179    ci = candidates.begin();
180  }
181
182  int N = gen ? gen->numberOfExamples() : -1;
183  if (N<0)
184    N = dcont->classes->cases;
185  TSimpleRandomGenerator rgen(N);
186
187  int thisAttr = 0, bestAttr = -1, wins = 0;
188  quality = 0.0;
189
190  if (measure->needs == TMeasureAttribute::Contingency_Class) {
191    vector<bool> myCandidates;
192    if (cse) {
193      myCandidates.reserve(gen->domain->attributes->size());
194      PITERATE(TVarList, vi, gen->domain->attributes)
195        myCandidates.push_back((*vi)->varType == TValue::INTVAR);
196    }
197    else {
198      myCandidates.reserve(candidates.size());
199      TVarList::const_iterator vi(gen->domain->attributes->begin());
200      for(; ci != ce; ci++, vi++)
201        myCandidates.push_back(*ci && ((*vi)->varType == TValue::INTVAR));
202    }
203
204    if (!dcont || dcont->classIsOuter)
205      dcont = PDomainContingency(mlnew TDomainContingency(gen, weightID, myCandidates));
206
207    ci = myCandidates.begin();
208    ce = myCandidates.end();
209    TDomainContingency::iterator dci(dcont->begin()), dce(dcont->end());
210    for(; (ci != ce) && (dci!=dce); dci++, ci++, thisAttr++)
211      if (*ci && checkDistribution((const TDiscDistribution &)((*dci)->outerDistribution.getReference()), minSubset)) {
212        float thisMeas = measure->call(thisAttr, dcont, apriorClass);
213
214        if (   ((!wins || (thisMeas>quality)) && ((wins=1)==1))
215            || ((thisMeas==quality) && rgen.randbool(++wins))) {
216          quality = thisMeas;
217          subsetSizes = (*dci)->outerDistribution;
218          bestAttr = thisAttr;
219        }
220      }
221  }
222
223  else if (measure->needs == TMeasureAttribute::DomainContingency) {
224    if (!dcont || dcont->classIsOuter)
225      dcont = PDomainContingency(mlnew TDomainContingency(gen, weightID));
226
227    TDomainContingency::iterator dci(dcont->begin()), dce(dcont->end());
228    for(; (cse || (ci!=ce)) && (dci!=dce); dci++, thisAttr++)
229      if (    (cse || *(ci++))
230           && ((*dci)->outerVariable->varType==TValue::INTVAR)
231           && checkDistribution((const TDiscDistribution &)((*dci)->outerDistribution.getReference()), minSubset)) {
232        float thisMeas = measure->call(thisAttr, dcont, apriorClass);
233
234        if (   ((!wins || (thisMeas>quality)) && ((wins=1)==1))
235            || ((thisMeas==quality) && rgen.randbool(++wins))) {
236          quality = thisMeas;
237          subsetSizes = (*dci)->outerDistribution;
238          bestAttr = thisAttr;
239        }
240      }
241  }
242
243  else {
244    TDomainDistributions ddist(gen, weightID);
245
246    TDomainDistributions::iterator ddi(ddist.begin()), dde(ddist.end()-1);
247    for(; (cse || (ci!=ce)) && (ddi!=dde); ddi++, thisAttr++)
248      if (cse || *(ci++)) {
249        TDiscDistribution *discdist = (*ddi).AS(TDiscDistribution);
250        if (discdist && checkDistribution(*discdist, minSubset)) {
251          float thisMeas = measure->call(thisAttr, gen, apriorClass, weightID);
252
253          if (   ((!wins || (thisMeas>quality)) && ((wins=1)==1))
254              || ((thisMeas==quality) && rgen.randbool(++wins))) {
255            quality = thisMeas;
256            subsetSizes = PDiscDistribution(*ddi); // not discdist - this would be double wrapping!
257            bestAttr = thisAttr;
258          }
259        }
260      }
261   
262  }
263
264  if (!wins)
265    return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
266
267  if (quality<worstAcceptable)
268    return returnNothing(descriptions, subsetSizes, spentAttribute);
269
270  PVariable attribute = gen->domain->attributes->at(bestAttr);
271  TEnumVariable *evar = attribute.AS(TEnumVariable);
272  if (evar)
273    descriptions = mlnew TStringList(evar->values.getReference());
274  else
275    descriptions = mlnew TStringList(subsetSizes->size(), "");
276
277  spentAttribute = bestAttr;
278
279  TClassifierFromVarFD *cfv = mlnew TClassifierFromVarFD(attribute, gen->domain, bestAttr, subsetSizes);
280  cfv->transformUnknowns = false;
281  return cfv;
282}
283
284
285
286
287TTreeSplitConstructor_ExhaustiveBinary::TTreeSplitConstructor_ExhaustiveBinary(PMeasureAttribute meas, const float &aworst, const float &aml)
288: TTreeSplitConstructor_Measure(meas, aworst, aml)
289{}
290
291
292
293PClassifier TTreeSplitConstructor_ExhaustiveBinary::operator()(
294                             PStringList &descriptions, PDiscDistribution &subsetSizes, float &quality, int &spentAttribute,
295
296                             PExampleGenerator gen, const int &weightID ,
297                             PDomainContingency dcont, PDistribution apriorClass,
298                             const vector<bool> &candidates,
299                             PClassifier
300                            )
301{ 
302  checkProperty(measure);
303  measure->checkClassTypeExc(gen->domain->classVar->varType);
304
305  PIntList bestMapping;
306  int wins, bestAttr;
307  PVariable bvar;
308
309  if (measure->needs==TMeasureAttribute::Generator) {
310    bool cse = candidates.size()==0;
311    bool haveCandidates = false;
312    vector<bool> myCandidates;
313    myCandidates.reserve(gen->domain->attributes->size());
314    vector<bool>::const_iterator ci(candidates.begin()), ce(candidates.end());
315    TVarList::const_iterator vi, ve(gen->domain->attributes->end());
316    for(vi = gen->domain->attributes->begin(); vi != ve; vi++) {
317      bool co = (*vi)->varType == TValue::INTVAR && (!cse || (ci!=ce) && *ci);
318      myCandidates.push_back(co);
319      haveCandidates = haveCandidates || co;
320    }
321    if (!haveCandidates)
322      return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
323
324    PDistribution thisSubsets;
325    float thisQuality;
326    wins = 0;
327    int thisAttr = 0;
328
329    int N = gen->numberOfExamples();
330    TSimpleRandomGenerator rgen(N);
331
332    ci = myCandidates.begin();
333    for(vi = gen->domain->attributes->begin(); vi != ve; ci++, vi++, thisAttr++) {
334      if (*ci) {
335        thisSubsets = NULL;
336        PIntList thisMapping =
337           /*throughCont ? measure->bestBinarization(thisSubsets, thisQuality, *dci, dcont->classes, apriorClass, minSubset)
338                       : */measure->bestBinarization(thisSubsets, thisQuality, *vi, gen, apriorClass, weightID, minSubset);
339          if (thisMapping
340                && (   (!wins || (thisQuality>quality)) && ((wins=1)==1)
341                    || (thisQuality==quality) && rgen.randbool(++wins))) {
342            bestAttr = thisAttr;
343            quality = thisQuality;
344            subsetSizes = thisSubsets;
345            bestMapping = thisMapping;
346          }
347      }
348      /*if (thoughCont)
349        dci++; */
350    }
351 
352    if (!wins)
353      return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
354
355    if (quality<worstAcceptable)
356      return returnNothing(descriptions, subsetSizes, spentAttribute);
357
358    if (subsetSizes && subsetSizes->variable)
359      bvar = subsetSizes->variable;
360    else {
361      TEnumVariable *evar = mlnew TEnumVariable("");
362      evar->addValue("0");
363      evar->addValue("1");
364      bvar = evar;
365    }
366  }
367 
368  else {
369    bool cse = candidates.size()==0;
370    if (!cse && noCandidates(candidates))
371      return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
372
373    if (!dcont || dcont->classIsOuter) {
374      dcont = PDomainContingency(mlnew TDomainContingency(gen, weightID));
375//      raiseWarningWho("TreeSplitConstructor_ExhaustiveBinary", "this class is not optimized for 'candidates' list and can be very slow");
376    }
377
378    int N = gen ? gen->numberOfExamples() : -1;
379    if (N<0)
380      N = dcont->classes->cases;
381    TSimpleRandomGenerator rgen(N);
382
383    PDistribution classDistribution = dcont->classes;
384
385    vector<bool>::const_iterator ci(candidates.begin()), ce(candidates.end());
386
387    TDiscDistribution *dis0, *dis1;
388    TContDistribution *con0, *con1;
389
390    int thisAttr = 0;
391    bestAttr = -1;
392    wins = 0;
393    quality = 0.0;
394    float leftExamples, rightExamples;
395
396    TDomainContingency::iterator dci(dcont->begin()), dce(dcont->end());
397    for(; (cse || (ci!=ce)) && (dci!=dce); dci++, thisAttr++) {
398
399      // We consider the attribute only if it is a candidate, discrete and has at least two values
400      if ((cse || *(ci++)) && ((*dci)->outerVariable->varType==TValue::INTVAR) && ((*dci)->discrete->size()>=2)) {
401
402        const TDistributionVector &distr = *(*dci)->discrete;
403
404        if (distr.size()>16)
405          raiseError("'%s' has more than 16 values, cannot exhaustively binarize", gen->domain->attributes->at(thisAttr)->get_name().c_str());
406
407        // If the attribute is binary, we check subsetSizes and assess the quality if they are OK
408        if (distr.size()==2) {
409          if ((distr.front()->abs<minSubset) || (distr.back()->abs<minSubset))
410            continue; // next attribute
411          else {
412            float thisMeas = measure->call(thisAttr, dcont, apriorClass);
413            if (   ((!wins || (thisMeas>quality)) && ((wins=1)==1))
414                || ((thisMeas==quality) && rgen.randbool(++wins))) {
415              bestAttr = thisAttr;
416              quality = thisMeas;
417              leftExamples = distr.front()->abs;
418              rightExamples = distr.back()->abs;
419              bestMapping = mlnew TIntList(2, 0);
420              bestMapping->at(1) = 1;
421            }
422            continue;
423          }
424        }
425
426        vector<int> valueIndices;
427        int ind = 0;
428        for(TDistributionVector::const_iterator dvi(distr.begin()), dve(distr.end()); (dvi!=dve); dvi++, ind++)
429          if ((*dvi)->abs>0)
430            valueIndices.push_back(ind);
431
432        if (valueIndices.size()<2)
433          continue;
434
435        PContingency cont = prepareBinaryCheat(classDistribution, *dci, bvar, dis0, dis1, con0, con1);
436
437        // A real job: go through all splits
438        int binWins = 0;
439        float binQuality = -1.0;
440        float binLeftExamples = -1.0, binRightExamples = -1.0;
441        // Selection: each element correspons to a value of the original attribute and is 1, if the value goes right
442        // The first value always goes left (and has no corresponding bit in selection.
443        TBoolCount selection(valueIndices.size()-1), bestSelection(0);
444
445        // First for discrete classes
446        if (dis0) {
447          do {
448            *dis0 = CAST_TO_DISCDISTRIBUTION(distr[valueIndices[0]]);
449            *dis1 *= 0;
450            vector<int>::const_iterator ii(valueIndices.begin());
451            ii++;
452            for(TBoolCount::const_iterator bi(selection.begin()), be(selection.end()); bi!=be; bi++, ii++)
453               *(*bi ? dis1 : dis0) += distr[*ii];
454            cont->outerDistribution->setint(0, dis0->abs);
455            cont->outerDistribution->setint(1, dis1->abs);
456
457            if ((dis0->abs < minSubset) || (dis1->abs < minSubset))
458              continue; // cannot split like that, to few examples in one of the branches
459
460            float thisMeas = measure->operator()(cont, classDistribution, apriorClass);
461            if (   ((!binWins) || (thisMeas>binQuality)) && ((binWins=1) ==1)
462                || (thisMeas==binQuality) && rgen.randbool(++binWins)) {
463              bestSelection = selection; 
464              binQuality = thisMeas;
465              binLeftExamples = dis0->abs;
466              binRightExamples = dis1->abs;
467            }
468          } while (selection.next());
469        }
470
471        // And then exactly the same for continuous classes
472        else {
473          do {
474            *con0 = CAST_TO_CONTDISTRIBUTION(distr[0]);
475            *con1 = TContDistribution();
476            vector<int>::const_iterator ii(valueIndices.begin());
477            for(TBoolCount::const_iterator bi(selection.begin()), be(selection.end()); bi!=be; bi++, ii++)
478               *(*bi ? con1 : con0) += distr[*ii];
479
480            if ((con0->abs<minSubset) || (con1->abs<minSubset))
481              continue; // cannot split like that, to few examples in one of the branches
482
483            float thisMeas = measure->operator()(cont, classDistribution, apriorClass);
484            if (   ((!binWins) || (thisMeas>binQuality)) && ((binWins=1) ==1)
485                || (thisMeas==binQuality) && rgen.randbool(++binWins)) {
486              bestSelection = selection; 
487              binQuality = thisMeas;
488              binLeftExamples = con0->abs;
489              binRightExamples = con1->abs;
490            }
491          } while (selection.next());
492        }
493
494        if (       binWins
495            && (   (!wins || (binQuality>quality)) && ((wins=1)==1)
496                || (binQuality==quality) && rgen.randbool(++wins))) {
497          bestAttr = thisAttr;
498          quality = binQuality;
499          leftExamples = binLeftExamples;
500          rightExamples = binRightExamples;
501          bestMapping = mlnew TIntList(distr.size(), -1);
502          vector<int>::const_iterator ii = valueIndices.begin();
503          bestMapping->at(*(ii++)) = 0;
504          ITERATE(TBoolCount, bi, bestSelection)
505            bestMapping->at(*(ii++)) = *bi ? 1 : 0;
506        }
507      }
508    }
509 
510
511    if (!wins)
512      return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
513
514    subsetSizes = mlnew TDiscDistribution();
515    subsetSizes->addint(0, leftExamples);
516    subsetSizes->addint(1, rightExamples);
517  }
518
519  PVariable attribute = gen->domain->attributes->at(bestAttr);
520
521  if (attribute->noOfValues() == 2) {
522    spentAttribute = bestAttr;
523    descriptions = mlnew TStringList(attribute.AS(TEnumVariable)->values.getReference());
524    TClassifierFromVarFD *cfv = mlnew TClassifierFromVarFD(attribute, gen->domain, bestAttr, subsetSizes);
525    cfv->transformUnknowns = false;
526    return cfv;
527  }
528
529  string s0, s1;
530  int ns0 = 0, ns1 = 0;
531  TValue ev;
532  attribute->firstValue(ev);
533  PITERATE(TIntList, mi, bestMapping) {
534    string str;
535    attribute->val2str(ev, str);
536    if (*mi==1) {
537      s1 += string(ns1 ? ", " : "") + str;
538      ns1++;
539    }
540    else if (*mi==0) {
541      s0 += string(ns0 ? ", " : "") + str;
542      ns0++;
543    }
544
545    attribute->nextValue(ev);
546  }
547
548  descriptions = mlnew TStringList();
549  descriptions->push_back(ns0>1 ? "in ["+s0+"]" : s0);
550  descriptions->push_back(ns1>1 ? "in ["+s1+"]" : s1);
551
552  bvar->set_name(gen->domain->attributes->at(bestAttr)->get_name());
553  spentAttribute = (ns0==1) && (ns1==1) ? bestAttr : -1;
554  TClassifierFromVarFD *cfv = mlnew TClassifierFromVarFD(bvar, gen->domain, bestAttr, subsetSizes, mlnew TMapIntValue(bestMapping));
555  cfv->transformUnknowns = false;
556  return cfv;
557}
558
559
560
561
562
563
564
565
566
567PClassifier TTreeSplitConstructor_OneAgainstOthers::operator()(
568                             PStringList &descriptions, PDiscDistribution &subsetSizes, float &quality, int &spentAttribute,
569
570                             PExampleGenerator gen, const int &weightID ,
571                             PDomainContingency dcont, PDistribution apriorClass,
572                             const vector<bool> &candidates,
573                             PClassifier
574                            )
575{ 
576  checkProperty(measure);
577  measure->checkClassTypeExc(gen->domain->classVar->varType);
578
579  int bestValue, wins, bestAttr;
580  PVariable bvar;
581
582  if (measure->needs==TMeasureAttribute::Generator) {
583    bool cse = candidates.size()==0;
584    bool haveCandidates = false;
585    vector<bool> myCandidates;
586    myCandidates.reserve(gen->domain->attributes->size());
587    vector<bool>::const_iterator ci(candidates.begin()), ce(candidates.end());
588    TVarList::const_iterator vi, ve(gen->domain->attributes->end());
589    for(vi = gen->domain->attributes->begin(); vi != ve; vi++) {
590      bool co = (*vi)->varType == TValue::INTVAR && (!cse || (ci!=ce) && *ci);
591      myCandidates.push_back(co);
592      haveCandidates = haveCandidates || co;
593    }
594    if (!haveCandidates)
595      return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
596
597    PDistribution thisSubsets;
598    float thisQuality;
599    wins = 0;
600    int thisAttr = 0;
601
602    int N = gen->numberOfExamples();
603    TSimpleRandomGenerator rgen(N);
604
605    ci = myCandidates.begin();
606    for(vi = gen->domain->attributes->begin(); vi != ve; ci++, vi++, thisAttr++) {
607      if (*ci) {
608        thisSubsets = NULL;
609        int thisValue = measure->bestValue(thisSubsets, thisQuality, *vi, gen, apriorClass, weightID, minSubset);
610        if ((thisValue >=0)
611                && (   (!wins || (thisQuality>quality)) && ((wins=1)==1)
612                    || (thisQuality==quality) && rgen.randbool(++wins))) {
613            bestAttr = thisAttr;
614            quality = thisQuality;
615            subsetSizes = thisSubsets;
616            bestValue = thisValue;
617          }
618      }
619    }
620 
621    if (!wins)
622      return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
623
624    if (quality<worstAcceptable)
625      return returnNothing(descriptions, subsetSizes, spentAttribute);
626
627    if (subsetSizes && subsetSizes->variable)
628      bvar = subsetSizes->variable;
629    else {
630      TEnumVariable *evar = mlnew TEnumVariable("");
631      const string &value = gen->domain->attributes->at(bestAttr).AS(TEnumVariable)->values->at(bestValue);
632      evar->addValue(string("not ")+value);
633      evar->addValue(value);
634      bvar = evar;
635    }
636  }
637 
638  else {
639    bool cse = candidates.size()==0;
640    if (!cse && noCandidates(candidates))
641      return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
642
643    if (!dcont || dcont->classIsOuter) {
644      dcont = PDomainContingency(mlnew TDomainContingency(gen, weightID));
645    }
646
647    int N = gen ? gen->numberOfExamples() : -1;
648    if (N<0)
649      N = dcont->classes->cases;
650    TSimpleRandomGenerator rgen(N);
651
652    PDistribution classDistribution = dcont->classes;
653
654    vector<bool>::const_iterator ci(candidates.begin()), ce(candidates.end());
655
656    TDiscDistribution *dis0, *dis1;
657    TContDistribution *con0, *con1;
658
659    int thisAttr = 0;
660    bestAttr = -1;
661    wins = 0;
662    quality = 0.0;
663    float leftExamples, rightExamples;
664
665    TDomainContingency::iterator dci(dcont->begin()), dce(dcont->end());
666    for(; (cse || (ci!=ce)) && (dci!=dce); dci++, thisAttr++) {
667
668      // We consider the attribute only if it is a candidate, discrete and has at least two values
669      if ((cse || *(ci++)) && ((*dci)->outerVariable->varType==TValue::INTVAR) && ((*dci)->discrete->size()>=2)) {
670
671        const TDistributionVector &distr = *(*dci)->discrete;
672
673        // If the attribute is binary, we check subsetSizes and assess the quality if they are OK
674        if (distr.size() == 2) {
675          if ((distr.front()->abs < minSubset) || (distr.back()->abs < minSubset))
676            continue; // next attribute
677          else {
678            float thisMeas = measure->call(thisAttr, dcont, apriorClass);
679            if (   ((!wins || (thisMeas>quality)) && ((wins=1)==1))
680                || ((thisMeas==quality) && rgen.randbool(++wins))) {
681              bestAttr = thisAttr;
682              quality = thisMeas;
683              leftExamples = distr.front()->abs;
684              rightExamples = distr.back()->abs;
685              bestValue = 1;
686            }
687            continue;
688          }
689        }
690
691        int binWins = 0, binBestValue = -1;
692        float binQuality = -1.0;
693        float binLeftExamples = -1.0, binRightExamples = -1.0;
694
695        PContingency cont = prepareBinaryCheat(classDistribution, *dci, bvar, dis0, dis1, con0, con1);
696        int thisValue = 0;
697        const float maxSubset = (*dci)->innerDistribution->abs - minSubset;
698        for(TDistributionVector::const_iterator dvi(distr.begin()), dve(distr.end()); (dvi!=dve); dvi++, thisValue++) {
699          if (((*dvi)->abs < minSubset) || ((*dvi)->abs > maxSubset))
700            continue;
701
702          float thisMeas;
703         
704          // First for discrete classes
705          if (dis0) {
706            *dis0 = CAST_TO_DISCDISTRIBUTION(*dvi);
707            *dis1 = CAST_TO_DISCDISTRIBUTION((*dci)->innerDistribution);
708            *dis1 -= *dis0;
709            thisMeas = measure->operator()(cont, classDistribution, apriorClass);
710          }
711          else {
712            *con0 = CAST_TO_CONTDISTRIBUTION(*dvi);
713            *con1 = CAST_TO_CONTDISTRIBUTION((*dci)->innerDistribution);
714            *con0 -= *con1;
715            thisMeas = measure->operator()(cont, classDistribution, apriorClass);
716          }
717         
718          if (   ((!binWins) || (thisMeas>binQuality)) && ((binWins=1) ==1)
719              || (thisMeas==binQuality) && rgen.randbool(++binWins)) {
720            binBestValue = thisValue; 
721            binQuality = thisMeas;
722            binLeftExamples = dis0->abs;
723            binRightExamples = dis1->abs;
724          }
725        }
726
727        if (       binWins
728            && (   (!wins || (binQuality>quality)) && ((wins=1)==1)
729                || (binQuality==quality) && rgen.randbool(++wins))) {
730          bestAttr = thisAttr;
731          quality = binQuality;
732          leftExamples = binLeftExamples;
733          rightExamples = binRightExamples;
734          bestValue = binBestValue;
735        }
736      }
737    }
738 
739
740    if (!wins)
741      return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
742
743    subsetSizes = mlnew TDiscDistribution();
744    subsetSizes->addint(0, leftExamples);
745    subsetSizes->addint(1, rightExamples);
746  }
747
748  PVariable attribute = gen->domain->attributes->at(bestAttr);
749
750  if (attribute->noOfValues() == 2) {
751    spentAttribute = bestAttr;
752    descriptions = mlnew TStringList(attribute.AS(TEnumVariable)->values.getReference());
753    TClassifierFromVarFD *cfv = mlnew TClassifierFromVarFD(attribute, gen->domain, bestAttr, subsetSizes);
754    cfv->transformUnknowns = false;
755    return cfv;
756  }
757
758  const string &bestValueS = attribute.AS(TEnumVariable)->values->at(bestValue);
759  descriptions = mlnew TStringList();
760  descriptions->push_back(string("not ") + bestValueS);
761  descriptions->push_back(bestValueS);
762 
763  bvar->set_name(gen->domain->attributes->at(bestAttr)->get_name());
764
765  TIntList *bestMapping = mlnew TIntList(attribute.AS(TEnumVariable)->values->size(), 0);
766  PIntList wb = bestMapping;
767  bestMapping->at(bestValue) = 1;
768  spentAttribute = -1;
769  TClassifierFromVarFD *cfv = mlnew TClassifierFromVarFD(bvar, gen->domain, bestAttr, subsetSizes, mlnew TMapIntValue(bestMapping));
770  cfv->transformUnknowns = false;
771  return cfv;
772}
773
774
775
776
777
778
779
780
781
782
783TTreeSplitConstructor_Threshold::TTreeSplitConstructor_Threshold(PMeasureAttribute meas, const float &worst, const float &aml)
784: TTreeSplitConstructor_Measure(meas, worst, aml)
785{}
786
787
788PClassifier TTreeSplitConstructor_Threshold::operator()(
789                             PStringList &descriptions, PDiscDistribution &subsetSizes, float &quality, int &spentAttribute,
790
791                             PExampleGenerator gen, const int &weightID ,
792                             PDomainContingency dcont, PDistribution apriorClass,
793                             const vector<bool> &candidates,
794                             PClassifier
795                            )
796{ 
797  checkProperty(measure);
798  measure->checkClassTypeExc(gen->domain->classVar->varType);
799
800  bool cse = candidates.size()==0;
801  bool haveCandidates = false;
802  vector<bool> myCandidates;
803  myCandidates.reserve(gen->domain->attributes->size());
804  vector<bool>::const_iterator ci(candidates.begin()), ce(candidates.end());
805  TVarList::const_iterator vi, ve(gen->domain->attributes->end());
806  for(vi = gen->domain->attributes->begin(); vi != ve; vi++) {
807    bool co = (*vi)->varType == TValue::FLOATVAR && (cse || (ci!=ce) && *ci);
808    if (ci != ce)
809      ci++;
810    myCandidates.push_back(co);
811    haveCandidates = haveCandidates || co;
812  }
813  if (!haveCandidates)
814    return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
815
816  int N = gen ? gen->numberOfExamples() : -1;
817  if (N < 0)
818    N = dcont->classes->cases;
819
820  TSimpleRandomGenerator rgen(N);
821
822
823  PDistribution thisSubsets;
824  float thisQuality, bestThreshold;
825  ci = myCandidates.begin();
826  int wins = 0, thisAttr = 0, bestAttr;
827
828  TDomainContingency::iterator dci, dce;
829  bool throughCont = (dcont && !dcont->classIsOuter && (measure->needs <= measure->DomainContingency));
830  if (throughCont) {
831    dci = dcont->begin();
832    dce = dcont->end();
833  }
834
835  for(vi = gen->domain->attributes->begin(); vi != ve; ci++, vi++, thisAttr++) {
836    if (*ci) {
837      thisSubsets = NULL;
838      const float thisThreshold =
839         throughCont ? measure->bestThreshold(thisSubsets, thisQuality, *dci, dcont->classes, apriorClass, minSubset)
840                     : measure->bestThreshold(thisSubsets, thisQuality, *vi, gen, apriorClass, weightID, minSubset);
841        if ((thisThreshold != ILLEGAL_FLOAT)
842              && (   (!wins || (thisQuality>quality)) && ((wins=1)==1)
843                  || (thisQuality==quality) && rgen.randbool(++wins))) {
844          bestAttr = thisAttr;
845          quality = thisQuality;
846          subsetSizes = thisSubsets;
847          bestThreshold = thisThreshold;
848        }
849    }
850    if (throughCont)
851      dci++;
852  }
853 
854  if (!wins)
855    return returnNothing(descriptions, subsetSizes, quality, spentAttribute);
856
857  if (quality<worstAcceptable)
858    return returnNothing(descriptions, subsetSizes, spentAttribute);
859
860  PVariable bvar;
861  if (subsetSizes && subsetSizes->variable)
862    bvar = subsetSizes->variable;
863  else {
864    TEnumVariable *evar = mlnew TEnumVariable("");
865    evar->addValue("0");
866    evar->addValue("1");
867    bvar = evar;
868  }
869
870  descriptions = mlnew TStringList();
871  char str[128];
872  sprintf(str, "<=%3.3f", bestThreshold);
873  descriptions->push_back(str);
874  sprintf(str, ">%3.3f", bestThreshold);
875  descriptions->push_back(str);
876
877  bvar->set_name(gen->domain->attributes->at(bestAttr)->get_name());
878  spentAttribute = -1;
879  TClassifierFromVarFD *cfv = mlnew TClassifierFromVarFD(bvar, gen->domain, bestAttr, subsetSizes, mlnew TThresholdDiscretizer(bestThreshold));
880  cfv->transformUnknowns = false;
881  return cfv;
882}
883
884
885
886PExampleGeneratorList TTreeExampleSplitter::prepareGeneratorList(int size, PExampleGenerator gen, vector<TExampleTable *> &unwrapped)
887{
888  PExampleTable lock = gen.AS(TExampleTable);
889  if (lock) {
890    if (lock->lock)
891      lock = lock->lock;
892  }
893  else {
894    lock = mlnew TExampleTable(gen);
895  }
896   
897  PExampleGeneratorList examplePtrs = mlnew TExampleGeneratorList();
898  while(size--) {
899    TExampleTable *ntable = mlnew TExampleTable(lock, 1);
900    examplePtrs->push_back(PExampleGenerator(ntable));
901    unwrapped.push_back(ntable);
902  }
903
904  return examplePtrs;
905}
906
907
908bool TTreeExampleSplitter::getBranchIndices(PTreeNode node, PExampleGenerator gen, vector<int> &indices)
909{
910  TClassifier &branchSelector = node->branchSelector.getReference();
911  const int maxIndex = node->branchDescriptions->size();
912 
913  PEITERATE(ei, gen) {
914    TValue index = branchSelector(*ei);
915    if (index.isSpecial() || (index.intV<0) || (index.intV>=maxIndex))
916      return false;
917    indices.push_back(index.intV);
918  }
919
920  return true;
921}
922
923PExampleGeneratorList TTreeExampleSplitter_IgnoreUnknowns::operator ()(PTreeNode node, PExampleGenerator gen, const int &, vector<int> &)
924{ TClassifier &branchSelector = node->branchSelector.getReference();
925  const int maxIndex = node->branchDescriptions->size();
926
927  vector<TExampleTable *> uexamplePtrs;
928  PExampleGeneratorList examplePtrs = prepareGeneratorList(maxIndex, gen, uexamplePtrs);
929  PEITERATE(ei, gen) {
930    TValue index = branchSelector(*ei);
931    if (!index.isSpecial() && (index.intV>=0) && (index.intV<maxIndex))
932      uexamplePtrs[index.intV]->addExample(*ei);
933  }
934
935  return examplePtrs;
936}
937
938
939PExampleGeneratorList TTreeExampleSplitter_UnknownsToCommon::operator ()(PTreeNode node, PExampleGenerator gen, const int &, vector<int> &)
940{ 
941  if (!node->branchSizes)
942    raiseError("TreeExampleSplitter_UnknownsToCommon: splitConstructor didn't set the branchSize; use different constructor or splitter");
943
944  TClassifier &branchSelector = node->branchSelector.getReference();
945  const int maxIndex = node->branchDescriptions->size();
946  const int mostCommon = node->branchSizes->highestProbIntIndex();
947
948  vector<TExampleTable *> uexamplePtrs;
949  PExampleGeneratorList examplePtrs = prepareGeneratorList(maxIndex, gen, uexamplePtrs);
950
951  PEITERATE(ei, gen) {
952    TValue index = branchSelector(*ei);
953    uexamplePtrs[!index.isSpecial() && (index.intV>=0) && (index.intV<maxIndex) ? index.intV : mostCommon]->addExample(*ei);
954  }
955
956  return examplePtrs;
957}
958
959
960PExampleGeneratorList TTreeExampleSplitter_UnknownsToAll::operator ()(PTreeNode node, PExampleGenerator gen, const int &, vector<int> &)
961{ TClassifier &branchSelector = node->branchSelector.getReference();
962  const int maxIndex = node->branchDescriptions->size();
963
964  vector<TExampleTable *> uexamplePtrs;
965  PExampleGeneratorList examplePtrs = prepareGeneratorList(maxIndex, gen, uexamplePtrs);
966
967  PEITERATE(ei, gen) {
968    TValue index = branchSelector(*ei);
969    if (!index.isSpecial() && (index.intV>=0) && (index.intV<maxIndex))
970      uexamplePtrs[index.intV]->addExample(*ei);
971    else
972      ITERATE(vector<TExampleTable *>, pei, uexamplePtrs)
973        (*pei)->addExample(*ei);
974  }
975
976  return examplePtrs;
977}
978
979
980PExampleGeneratorList TTreeExampleSplitter_UnknownsToRandom::operator ()(PTreeNode node, PExampleGenerator gen, const int &, vector<int> &)
981{ TClassifier &branchSelector = node->branchSelector.getReference();
982  const int maxIndex = node->branchDescriptions->size();
983
984  vector<TExampleTable *> uexamplePtrs;
985  PExampleGeneratorList examplePtrs = prepareGeneratorList(maxIndex, gen, uexamplePtrs);
986
987  PEITERATE(ei, gen) {
988    TValue index = branchSelector(*ei);
989    if (!index.isSpecial() && (index.intV>=0) && (index.intV<maxIndex))
990      uexamplePtrs[index.intV]->addExample(*ei);
991    else {
992      TDiscDistribution *distr = NULL;
993      if (index.svalV)
994        distr = index.svalV.AS(TDiscDistribution);
995      if (!distr)
996        distr = node->branchSizes.AS(TDiscDistribution);
997      if (distr)
998        uexamplePtrs[distr->randomInt()]->addExample(*ei);
999    }
1000  }
1001
1002  return examplePtrs;
1003}
1004
1005
1006PExampleGeneratorList TTreeExampleSplitter_UnknownsToBranch::operator ()(PTreeNode node, PExampleGenerator gen, const int &, vector<int> &)
1007{ TClassifier &branchSelector = node->branchSelector.getReference();
1008  int maxIndex = node->branchDescriptions->size();
1009  node->branchDescriptions->push_back("unknown");
1010
1011  vector<TExampleTable *> uexamplePtrs;
1012  PExampleGeneratorList examplePtrs = prepareGeneratorList(maxIndex+1, gen, uexamplePtrs);
1013
1014  PEITERATE(ei, gen) {
1015    TValue index = branchSelector(*ei);
1016    if (!index.isSpecial() && (index.intV>=0) && (index.intV<maxIndex))
1017      uexamplePtrs[index.intV]->addExample(*ei);
1018    else
1019      uexamplePtrs.back()->addExample(*ei);
1020  }
1021
1022  return examplePtrs;
1023}
1024
1025
1026PExampleGeneratorList TTreeExampleSplitter_UnknownsAsBranchSizes::operator()(PTreeNode node, PExampleGenerator gen, const int &weightID, vector<int> &newWeights)
1027{ 
1028  int maxIndex = node->branchDescriptions->size();
1029  TClassifier &branchSelector = node->branchSelector.getReference();
1030 
1031  vector<TExampleTable *> uexamplePtrs;
1032  PExampleGeneratorList examplePtrs = prepareGeneratorList(maxIndex, gen, uexamplePtrs);
1033
1034  vector<int> indices;
1035 
1036  if (getBranchIndices(node, gen, indices)) {
1037    TExampleIterator ei(gen->begin());
1038    ITERATE(vector<int>, ii, indices) {
1039      uexamplePtrs[*ii]->addExample(*ei);
1040      ++ei;
1041    }
1042  }
1043
1044  else {
1045    if (!node->branchSizes)
1046      raiseError("TreeExampleSplitter_UnknownsAsBranchSizes: splitConstructor didn't set the branchSize; use different constructor or splitter");
1047
1048    const TDiscDistribution &branchSizes = node->branchSizes.getReference();
1049    for(int i = maxIndex; i--; )
1050      newWeights.push_back(getMetaID());
1051
1052    TExampleIterator ei(gen->begin());
1053    ITERATE(vector<int>, ii, indices) {
1054      uexamplePtrs[*ii]->addExample(*ei);
1055      (*ei).setMeta(newWeights[*ii], TValue(WEIGHT(*ei)));
1056      ++ei;
1057    }
1058
1059    for (; ei; ++ei) {
1060      TValue index = branchSelector(*ei);
1061
1062      if (!index.isSpecial() && (index.intV>=0) && (index.intV<maxIndex)) {
1063        uexamplePtrs[index.intV]->addExample(*ei);
1064        (*ei).setMeta(newWeights[index.intV], TValue(WEIGHT(*ei)));
1065      }
1066   
1067      else {
1068        if (index.isDC()) {
1069          for(int branchNo = 0; branchNo<maxIndex; branchNo++) {
1070            uexamplePtrs[branchNo]->addExample(*ei);
1071            (*ei).setMeta(newWeights[branchNo], TValue(WEIGHT(*ei)));
1072          }
1073        }
1074        else {
1075          for(int branchNo = 0; branchNo<maxIndex; branchNo++) {
1076            float weight = branchSizes.p(branchNo) * WEIGHT(*ei);
1077            if (weight) {
1078              uexamplePtrs[branchNo]->addExample(*ei);
1079              (*ei).setMeta(newWeights[branchNo], TValue(weight));
1080            }
1081          }
1082        }
1083      }
1084    }
1085  }
1086
1087  return examplePtrs;
1088}
1089
1090
1091PExampleGeneratorList TTreeExampleSplitter_UnknownsAsSelector::operator()(PTreeNode node, PExampleGenerator gen, const int &weightID, vector<int> &newWeights)
1092{ TClassifier &branchSelector = node->branchSelector.getReference();
1093  int maxIndex = node->branchDescriptions->size();
1094
1095 
1096  vector<TExampleTable *> uexamplePtrs;
1097  PExampleGeneratorList examplePtrs = prepareGeneratorList(maxIndex, gen, uexamplePtrs);
1098
1099  vector<int> indices;
1100 
1101  if (getBranchIndices(node, gen, indices)) {
1102    TExampleIterator ei(gen->begin());
1103    ITERATE(vector<int>, ii, indices) {
1104      uexamplePtrs[*ii]->addExample(*ei);
1105      ++ei;
1106    }
1107  }
1108
1109  else {
1110    for(int i = maxIndex; i--; )
1111      newWeights.push_back(getMetaID());
1112
1113    TExampleIterator ei(gen->begin());
1114    ITERATE(vector<int>, ii, indices) {
1115      uexamplePtrs[*ii]->addExample(*ei);
1116      (*ei).setMeta(newWeights[*ii], TValue(WEIGHT(*ei)));
1117      ++ei;
1118    }
1119
1120    for (; ei; ++ei) {
1121      TValue index = branchSelector(*ei);
1122
1123      if (!index.isSpecial() && (index.intV>=0) && (index.intV<maxIndex)) {
1124        uexamplePtrs[index.intV]->addExample(*ei);
1125        (*ei).setMeta(newWeights[index.intV], TValue(WEIGHT(*ei)));
1126      }
1127   
1128      else {
1129        if (index.isDC()) {
1130          for(int branchNo = 0; branchNo<maxIndex; branchNo++) {
1131            uexamplePtrs[branchNo]->addExample(*ei);
1132            (*ei).setMeta(newWeights[branchNo], TValue(WEIGHT(*ei)));
1133          }
1134        }
1135        else {
1136          TDiscDistribution *distr = index.svalV ? index.svalV.AS(TDiscDistribution) : NULL;
1137          if (distr)
1138            for(int branchNo = 0; branchNo<maxIndex; branchNo++) {
1139              float weight = distr->p(branchNo) * WEIGHT(*ei);
1140              if (weight) {
1141                uexamplePtrs[branchNo]->addExample(*ei);
1142                (*ei).setMeta(newWeights[branchNo], TValue(weight));
1143            }
1144          }
1145        }
1146      }
1147    }
1148  }
1149
1150  return examplePtrs;
1151}
Note: See TracBrowser for help on using the repository browser.