Changeset 8770:992b1400226d in orange


Ignore:
Timestamp:
08/24/11 23:14:39 (3 years ago)
Author:
jzbontar <jure.zbontar@…>
Branch:
default
Convert:
2d6a97cf427959713d141d66ed2869571fa1df3b
Message:

SimpleTreeLearner now properly supports unknown values (example weights)

Location:
source/orange
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • source/orange/tdidt_simple.cpp

    r8735 r8770  
    11/* 
    22    This file is part of Orange. 
    3      
     3 
    44    Copyright 1996-2010 Faculty of Computer and Information Science, University of Ljubljana 
    55    Contact: janez.demsar@fri.uni-lj.si 
     
    3434 
    3535#ifndef _MSC_VER 
    36     #include "err.h" 
    37     #define ASSERT(x) if (!(x)) err(1, "%s:%d", __FILE__, __LINE__) 
     36    #include "err.h" 
     37    #define ASSERT(x) if (!(x)) err(1, "%s:%d", __FILE__, __LINE__) 
    3838#else 
    39     #define ASSERT(x) if(!(x)) exit(1) 
     39    #define ASSERT(x) if(!(x)) exit(1) 
    4040#endif // _MSC_VER 
    4141 
    4242#ifndef INFINITY 
    43     #include <limits> 
    44     #define INFINITY numeric_limits<float>::infinity() 
     43    #include <limits> 
     44    #define INFINITY numeric_limits<float>::infinity() 
    4545#endif // INFINITY 
    46  
    47 #define LOG2(x) log((double) (x)) / log(2.0) 
    48  
    49 enum { DiscreteNode, ContinuousNode, PredictorNode }; 
    5046 
    5147struct Args { 
     
    5349    float maxMajority, skipProb; 
    5450 
    55     int *attr_split_so_far; 
     51    int type, *attr_split_so_far; 
    5652    PDomain domain; 
    5753}; 
    5854 
     55struct Example { 
     56    TExample *example; 
     57    float weight; 
     58}; 
     59 
     60enum { DiscreteNode, ContinuousNode, PredictorNode }; 
     61enum { Classification, Regression }; 
     62 
    5963int compar_attr; 
    6064 
    6165/* This function uses the global variable compar_attr. 
    62  * Examples with unknowns are larger so that when sorted, appear at the bottom. 
     66 * Examples with unknowns are larger so that, when sorted, they appear at the bottom. 
    6367 */ 
    6468int 
    6569compar_examples(const void *ptr1, const void *ptr2) 
    6670{ 
    67     TExample **e1 = (TExample **) ptr1; 
    68     TExample **e2 = (TExample **) ptr2; 
    69     if ((*e1)->values[compar_attr].isSpecial()) 
     71    struct Example *e1, *e2; 
     72 
     73    e1 = (struct Example *)ptr1; 
     74    e2 = (struct Example *)ptr2; 
     75    if (e1->example->values[compar_attr].isSpecial()) 
    7076        return 1; 
    71     if ((*e2)->values[compar_attr].isSpecial()) 
     77    if (e2->example->values[compar_attr].isSpecial()) 
    7278        return -1; 
    73     return (*e1)->values[compar_attr].compare((*e2)->values[compar_attr]); 
    74 } 
     79    return e1->example->values[compar_attr].compare(e2->example->values[compar_attr]); 
     80} 
     81 
    7582 
    7683float 
    77 entropy(int *xs, int size) 
    78 { 
    79     int *ip, *end, sum; 
    80     float e, p; 
    81  
    82     for (ip = xs, end = xs + size, e = 0, sum = 0; ip != end; ip++) 
    83         if (*ip) { 
    84             e -= *ip * LOG2(*ip); 
     84entropy(float *xs, int size) 
     85{ 
     86    float *ip, *end, sum, e; 
     87 
     88    for (ip = xs, end = xs + size, e = 0.0, sum = 0.0; ip != end; ip++) 
     89        if (*ip > 0.0) { 
     90            e -= *ip * log2f(*ip); 
    8591            sum += *ip; 
    8692        } 
    8793 
    88     return sum == 0 ? 0.0 : e / sum + LOG2(sum); 
    89 } 
    90  
     94    return sum == 0.0 ? 0.0 : e / sum + log2f(sum); 
     95} 
     96 
     97int 
     98test_min_examples(float *attr_dist, int attr_vals, struct Args *args) 
     99{ 
     100    int i; 
     101 
     102    for (i = 0; i < attr_vals; i++) 
     103        if (attr_dist[i] > 0.0 && attr_dist[i] < args->minExamples) 
     104            return 0; 
     105    return 1; 
     106} 
    91107 
    92108float 
    93 score_attribute_c(TExample **examples, int size, int attr, float cls_entropy, int *rank, struct Args *args) 
    94 { 
    95     TExample **ex, **ex_end, **ex_next; 
    96     int i, cls_vals, *attr_dist, *dist_lt, *dist_ge, minExamples; 
    97     float best_score; 
    98  
    99     assert(size > 0); 
     109gain_ratio_c(struct Example *examples, int size, int attr, float cls_entropy, struct Args *args, float *best_split) 
     110{ 
     111    struct Example *ex, *ex_end, *ex_next; 
     112    int i, cls, cls_vals, minExamples, size_known; 
     113    float score, *dist_lt, *dist_ge, *attr_dist, best_score, size_weight; 
    100114 
    101115    cls_vals = args->domain->classVar->noOfValues(); 
    102116 
     117    /* minExamples should be at least 1, otherwise there is no point in splitting */ 
     118    minExamples = args->minExamples < 1 ? 1 : args->minExamples; 
     119 
    103120    /* allocate space */ 
    104     ASSERT(dist_lt = (int*) calloc(cls_vals, sizeof *dist_lt)); 
    105     ASSERT(dist_ge = (int*) calloc(cls_vals, sizeof *dist_ge)); 
    106     ASSERT(attr_dist = (int*) calloc(2, sizeof *attr_dist)); 
     121    ASSERT(dist_lt = (float *)calloc(cls_vals, sizeof *dist_lt)); 
     122    ASSERT(dist_ge = (float *)calloc(cls_vals, sizeof *dist_ge)); 
     123    ASSERT(attr_dist = (float *)calloc(2, sizeof *attr_dist)); 
    107124 
    108125    /* sort */ 
    109126    compar_attr = attr; 
    110     qsort(examples, size, sizeof(TExample *), compar_examples); 
     127    qsort(examples, size, sizeof(struct Example), compar_examples); 
    111128 
    112129    /* compute gain ratio for every split */ 
    113     for (ex = examples, ex_end = examples + size; ex != ex_end; ex++) { 
    114         if (!(*ex)->getClass().isSpecial()) 
    115             dist_ge[(*ex)->getClass().intV]++; 
    116         if ((*ex)->values[attr].isSpecial()) 
    117             size--; 
    118     } 
    119  
     130    size_known = size; 
     131    size_weight = 0.0; 
     132    for (ex = examples, ex_end = examples + size; ex < ex_end; ex++) { 
     133        if (ex->example->values[attr].isSpecial()) { 
     134            size_known = ex - examples; 
     135            break; 
     136        } 
     137        if (!ex->example->getClass().isSpecial()) 
     138            dist_ge[ex->example->getClass().intV] += ex->weight; 
     139        size_weight += ex->weight; 
     140    } 
     141 
     142    attr_dist[1] = size_weight; 
    120143    best_score = -INFINITY; 
    121     attr_dist[1] = size; 
    122  
    123     /* minExamples should be at least 1, otherwise there is no point in splitting */ 
    124     minExamples = minExamples < 1 ? 1 : minExamples; 
    125     ex = examples + minExamples - 1; 
    126     ex_end = examples + size - (minExamples - 1); 
    127     for (ex_next = ex + 1, i = 0; ex_next < ex_end; ex++, ex_next++, i++) { 
    128         int cls; 
    129         float score; 
    130  
    131         if (!(*ex)->getClass().isSpecial()) { 
    132             cls = (*ex)->getClass().intV; 
    133             dist_lt[cls]++; 
    134             dist_ge[cls]--; 
    135         } 
    136         attr_dist[0]++; 
    137         attr_dist[1]--; 
    138  
    139         if ((*ex)->values[attr] == (*ex_next)->values[attr]) 
     144 
     145    for (ex = examples, ex_end = ex + size_known - minExamples, ex_next = ex + 1, i = 0; ex < ex_end; ex++, ex_next++, i++) { 
     146        if (!ex->example->getClass().isSpecial()) { 
     147            cls = ex->example->getClass().intV; 
     148            dist_lt[cls] += ex->weight; 
     149            dist_ge[cls] -= ex->weight; 
     150        } 
     151        attr_dist[0] += ex->weight; 
     152        attr_dist[1] -= ex->weight; 
     153 
     154        if (ex->example->values[attr] == ex_next->example->values[attr] || i + 1 < minExamples) 
    140155            continue; 
    141156 
    142157        /* gain ratio */ 
    143         score = (attr_dist[0] * entropy(dist_lt, cls_vals) + attr_dist[1] * entropy(dist_ge, cls_vals)) / size; 
     158        score = (attr_dist[0] * entropy(dist_lt, cls_vals) + attr_dist[1] * entropy(dist_ge, cls_vals)) / size_weight; 
    144159        score = (cls_entropy - score) / entropy(attr_dist, 2); 
     160 
    145161 
    146162        if (score > best_score) { 
    147163            best_score = score; 
    148             *rank = i; 
     164            *best_split = (ex->example->values[attr].floatV + ex_next->example->values[attr].floatV) / 2.0; 
    149165        } 
    150166    } 
     
    160176} 
    161177 
     178 
    162179float 
    163 score_attribute_d(TExample **examples, int size, int attr, float cls_entropy, struct Args *args) 
    164 { 
    165     TExample **ex, **ex_end; 
    166     int i, j, cls_vals, attr_vals, *cont, *attr_dist, *attr_dist_cls_known, min, size_attr_known, size_attr_cls_known; 
    167     float score; 
    168  
    169     assert(size > 0); 
    170  
    171     cls_vals = args->domain->classVar->noOfValues(); 
    172     attr_vals = args->domain->attributes->at(attr)->noOfValues(); 
    173  
    174     /* allocate space */ 
    175     ASSERT(cont = (int *) calloc(cls_vals * attr_vals, sizeof *cont)); 
    176     ASSERT(attr_dist = (int *) calloc(attr_vals, sizeof *attr_dist)); 
    177     ASSERT(attr_dist_cls_known = (int *) calloc(attr_vals, sizeof *attr_dist)); 
    178  
    179     /* contingency matrix */ 
    180     size_attr_known = 0; 
    181     size_attr_cls_known = 0; 
    182     for (ex = examples, ex_end = examples + size; ex != ex_end; ex++) { 
    183         if (!(*ex)->values[attr].isSpecial()) { 
    184             int attr_val = (*ex)->values[attr].intV; 
    185  
    186             attr_dist[attr_val]++; 
    187             size_attr_known++; 
    188             if (!(*ex)->getClass().isSpecial()) { 
    189                 int cls_val = (*ex)->getClass().intV; 
    190  
    191                 size_attr_cls_known++; 
    192                 attr_dist_cls_known[attr_val]++; 
    193                 cont[attr_val * cls_vals + cls_val]++; 
    194             } 
    195         } 
    196     } 
    197  
    198     /* minimum examples in leaves */ 
    199     for (i = 0; i < attr_vals; i++) 
    200         if (attr_dist[i] < args->minExamples) { 
    201             score = -INFINITY; 
    202             goto finish; 
    203         } 
    204  
    205     /* gain ratio */ 
    206     score = 0; 
    207     for (i = 0; i < attr_vals; i++) 
    208         score += attr_dist_cls_known[i] * entropy(cont + i * cls_vals, cls_vals); 
    209     score = (cls_entropy - score / size_attr_cls_known) / entropy(attr_dist, attr_vals) * ((float)size_attr_known / size); 
     180gain_ratio_d(struct Example *examples, int size, int attr, float cls_entropy, struct Args *args) 
     181{ 
     182    struct Example *ex, *ex_end; 
     183    int i, cls_vals, attr_vals, attr_val, cls_val; 
     184    float score, size_weight, size_attr_known, size_attr_cls_known, attr_entropy, *cont, *attr_dist, *attr_dist_cls_known; 
     185 
     186    cls_vals = args->domain->classVar->noOfValues(); 
     187    attr_vals = args->domain->attributes->at(attr)->noOfValues(); 
     188 
     189    /* allocate space */ 
     190    ASSERT(cont = (float *)calloc(cls_vals * attr_vals, sizeof(float *))); 
     191    ASSERT(attr_dist = (float *)calloc(attr_vals, sizeof(float *))); 
     192    ASSERT(attr_dist_cls_known = (float *)calloc(attr_vals, sizeof(float *))); 
     193 
     194    /* contingency matrix */ 
     195    size_weight = 0.0; 
     196    for (ex = examples, ex_end = examples + size; ex < ex_end; ex++) { 
     197        if (!ex->example->values[attr].isSpecial()) { 
     198            attr_val = ex->example->values[attr].intV; 
     199            attr_dist[attr_val] += ex->weight; 
     200            if (!ex->example->getClass().isSpecial()) { 
     201                cls_val = ex->example->getClass().intV; 
     202                attr_dist_cls_known[attr_val] += ex->weight; 
     203                cont[attr_val * cls_vals + cls_val] += ex->weight; 
     204            } 
     205        } 
     206        size_weight += ex->weight; 
     207    } 
     208 
     209    /* min examples in leaves */ 
     210    if (!test_min_examples(attr_dist, attr_vals, args)) { 
     211        score = -INFINITY; 
     212        goto finish; 
     213    } 
     214 
     215    size_attr_known = size_attr_cls_known = 0.0; 
     216    for (i = 0; i < attr_vals; i++) { 
     217        size_attr_known += attr_dist[i]; 
     218        size_attr_cls_known += attr_dist_cls_known[i]; 
     219    } 
     220 
     221    /* gain ratio */ 
     222    score = 0.0; 
     223    for (i = 0; i < attr_vals; i++) 
     224        score += attr_dist_cls_known[i] * entropy(cont + i * cls_vals, cls_vals); 
     225    attr_entropy = entropy(attr_dist, attr_vals); 
     226 
     227    if (size_attr_cls_known == 0.0 || attr_entropy == 0.0 || size_weight == 0.0) { 
     228        score = -INFINITY; 
     229        goto finish; 
     230    } 
     231 
     232    score = (cls_entropy - score / size_attr_cls_known) / attr_entropy * ((float)size_attr_known / size_weight); 
    210233 
    211234    /* printf("D %s %f\n", args->domain->attributes->at(attr)->get_name().c_str(), score); */ 
    212235 
    213236finish: 
    214     free(cont); 
     237    free(cont); 
    215238    free(attr_dist); 
    216239    free(attr_dist_cls_known); 
    217     return score; 
    218 } 
     240    return score; 
     241} 
     242 
     243 
     244float 
     245mse_c(struct Example *examples, int size, int attr, float cls_mse, struct Args *args, float *best_split) 
     246{ 
     247    struct Example *ex, *ex_end, *ex_next; 
     248    int i, cls_vals, minExamples, size_known; 
     249    float size_attr_known, size_weight, cls_val, cls_score, best_score, size_attr_cls_known, score; 
     250 
     251    struct Variance { 
     252        float n, sum, sum2; 
     253    } var_lt = {0.0, 0.0, 0.0}, var_ge = {0.0, 0.0, 0.0}; 
     254 
     255    cls_vals = args->domain->classVar->noOfValues(); 
     256 
     257    /* minExamples should be at least 1, otherwise there is no point in splitting */ 
     258    minExamples = args->minExamples < 1 ? 1 : args->minExamples; 
     259 
     260    /* sort */ 
     261    compar_attr = attr; 
     262    qsort(examples, size, sizeof(struct Example), compar_examples); 
     263 
     264    /* compute mse for every split */ 
     265    size_known = size; 
     266    size_attr_known = 0.0; 
     267    for (ex = examples, ex_end = examples + size; ex < ex_end; ex++) { 
     268        if (ex->example->values[attr].isSpecial()) { 
     269            size_known = ex - examples; 
     270            break; 
     271        } 
     272        if (!ex->example->getClass().isSpecial()) { 
     273            cls_val = ex->example->getClass().floatV; 
     274            var_ge.n += ex->weight; 
     275            var_ge.sum += ex->weight * cls_val; 
     276            var_ge.sum2 += ex->weight * cls_val * cls_val; 
     277        } 
     278        size_attr_known += ex->weight; 
     279    } 
     280 
     281    /* count the remaining examples with unknown values */ 
     282    size_weight = size_attr_known; 
     283    for (ex_end = examples + size; ex < ex_end; ex++) 
     284        size_weight += ex->weight; 
     285 
     286    size_attr_cls_known = var_ge.n; 
     287    best_score = -INFINITY; 
     288 
     289    for (ex = examples, ex_end = ex + size_known - minExamples, ex_next = ex + 1, i = 0; ex < ex_end; ex++, ex_next++, i++) { 
     290        if (!ex->example->getClass().isSpecial()) { 
     291            cls_val = ex->example->getClass(); 
     292            var_lt.n += ex->weight; 
     293            var_lt.sum += ex->weight * cls_val; 
     294            var_lt.sum2 += ex->weight * cls_val * cls_val; 
     295 
     296            var_ge.n -= ex->weight; 
     297            var_ge.sum -= ex->weight * cls_val; 
     298            var_ge.sum2 -= ex->weight * cls_val * cls_val; 
     299        } 
     300 
     301        if (ex->example->values[attr] == ex_next->example->values[attr] || i + 1 < minExamples) 
     302            continue; 
     303 
     304        /* compute mse */ 
     305        score = var_lt.sum2 - var_lt.sum * var_lt.sum / var_lt.n; 
     306        score += var_ge.sum2 - var_ge.sum * var_ge.sum / var_ge.n; 
     307        score = (cls_mse - score / size_attr_cls_known) / cls_mse * (size_attr_known / size_weight); 
     308 
     309        if (score > best_score) { 
     310            best_score = score; 
     311            *best_split = (ex->example->values[attr].floatV + ex_next->example->values[attr].floatV) / 2.0; 
     312        } 
     313    } 
     314 
     315    /* printf("C %s %f\n", args->domain->attributes->at(attr)->get_name().c_str(), best_score); */ 
     316    return best_score; 
     317} 
     318 
     319 
     320float 
     321mse_d(struct Example *examples, int size, int attr, float cls_mse, struct Args *args) 
     322{ 
     323    int i, attr_vals, attr_val; 
     324    float *attr_dist, d, score, cls_val, size_attr_cls_known, size_attr_known, size_weight; 
     325    struct Example *ex, *ex_end; 
     326 
     327    struct Variance { 
     328        float n, sum, sum2; 
     329    } *variances, *v, *v_end; 
     330 
     331    attr_vals = args->domain->attributes->at(attr)->noOfValues(); 
     332 
     333    ASSERT(variances = (struct Variance *)calloc(attr_vals, sizeof *variances)); 
     334    ASSERT(attr_dist = (float *)calloc(attr_vals, sizeof *attr_dist)); 
     335 
     336    size_weight = size_attr_cls_known = size_attr_known = 0.0; 
     337    for (ex = examples, ex_end = examples + size; ex < ex_end; ex++) { 
     338        if (!ex->example->values[attr].isSpecial()) { 
     339            attr_dist[ex->example->values[attr].intV] += ex->weight; 
     340            size_attr_known += ex->weight; 
     341 
     342            if (!ex->example->getClass().isSpecial()) { 
     343                    cls_val = ex->example->getClass().floatV; 
     344                    v = variances + ex->example->values[attr].intV; 
     345                    v->n += ex->weight; 
     346                    v->sum += ex->weight * cls_val; 
     347                    v->sum2 += ex->weight * cls_val * cls_val; 
     348                    size_attr_cls_known += ex->weight; 
     349            } 
     350        } 
     351        size_weight += ex->weight; 
     352    } 
     353 
     354    /* minimum examples in leaves */ 
     355    if (!test_min_examples(attr_dist, attr_vals, args)) { 
     356        score = -INFINITY; 
     357        goto finish; 
     358    } 
     359 
     360    score = 0.0; 
     361    for (v = variances, v_end = variances + attr_vals; v < v_end; v++) 
     362        if (v->n > 0.0) 
     363            score += v->sum2 - v->sum * v->sum / v->n; 
     364    score = (cls_mse - score / size_attr_cls_known) / cls_mse * (size_attr_known / size_weight); 
     365 
     366    if (size_attr_cls_known <= 0.0 || cls_mse <= 0.0 || size_weight <= 0.0) 
     367        score = 0.0; 
     368 
     369finish: 
     370    free(attr_dist); 
     371    free(variances); 
     372 
     373    return score; 
     374} 
     375 
    219376 
    220377struct SimpleTreeNode * 
    221 build_tree(TExample **examples, int size, int depth, struct SimpleTreeNode *parent, struct Args *args) 
    222 { 
    223     TExample **ex, **ex_top, **ex_end; 
    224     TVarList::const_iterator it; 
    225     struct SimpleTreeNode *node; 
    226     float score, best_score, cls_entropy; 
    227     int i, best_attr, best_rank, sum, best_val, finish, cls_vals; 
    228  
    229     ASSERT(node = (SimpleTreeNode *) malloc(sizeof(*node))); 
     378make_predictor(struct SimpleTreeNode *node, struct Example *examples, int size, struct Args *args) 
     379{ 
     380    struct Example *ex, *ex_end; 
     381 
     382    node->type = PredictorNode; 
     383    if (args->type == Regression) { 
     384        node->n = node->sum = 0.0; 
     385        for (ex = examples, ex_end = examples + size; ex < ex_end; ex++) 
     386            if (!ex->example->getClass().isSpecial()) { 
     387                node->sum += ex->weight * ex->example->getClass().floatV; 
     388                node->n += ex->weight; 
     389            } 
     390 
     391    } 
     392 
     393    return node; 
     394} 
     395 
     396 
     397struct SimpleTreeNode * 
     398build_tree(struct Example *examples, int size, int depth, struct SimpleTreeNode *parent, struct Args *args) 
     399{ 
     400    int i, cls_vals, best_attr; 
     401    float cls_entropy, cls_mse, best_score, score, size_weight, best_split, split; 
     402    struct SimpleTreeNode *node; 
     403    struct Example *ex, *ex_end; 
     404    TVarList::const_iterator it; 
     405 
    230406    cls_vals = args->domain->classVar->noOfValues(); 
    231     ASSERT(node->dist = (int *) calloc(cls_vals, sizeof *node->dist)); 
    232  
    233     if (size == 0) { 
    234         assert(parent); 
    235         node->type = PredictorNode; 
    236         memcpy(node->dist, parent->dist, cls_vals * sizeof *node->dist); 
    237         return node; 
    238     } 
    239  
    240     /* class distribution */ 
    241     for (ex = examples, ex_end = examples + size; ex != ex_end; ex++) 
    242         if (!(*ex)->getClass().isSpecial()) 
    243             node->dist[(*ex)->getClass().intV]++; 
    244  
    245     /* stop splitting with majority class or depth exceeds limit */ 
    246     best_val = 0; 
    247     for (i = 0; i < cls_vals; i++) 
    248         if (node->dist[i] > node->dist[best_val]) 
    249             best_val = i; 
    250     finish = depth == args->maxDepth || node->dist[best_val] >= args->maxMajority * size; 
     407 
     408    ASSERT(node = (SimpleTreeNode *)malloc(sizeof *node)); 
     409 
     410    if (args->type == Classification) { 
     411        ASSERT(node->dist = (float *)calloc(cls_vals, sizeof(float *))); 
     412 
     413        if (size == 0) { 
     414            assert(parent); 
     415            node->type = PredictorNode; 
     416            memcpy(node->dist, parent->dist, cls_vals * sizeof *node->dist); 
     417            return node; 
     418        } 
     419 
     420        /* class distribution */ 
     421        size_weight = 0.0; 
     422        for (ex = examples, ex_end = examples + size; ex < ex_end; ex++) 
     423            if (!ex->example->getClass().isSpecial()) { 
     424                node->dist[ex->example->getClass().intV] += ex->weight; 
     425                size_weight += ex->weight; 
     426            } 
     427 
     428        /* stopping criterion: majority class */ 
     429        for (i = 0; i < cls_vals; i++) 
     430            if (node->dist[i] / size_weight >= args->maxMajority) 
     431                return make_predictor(node, examples, size, args); 
     432 
     433        cls_entropy = entropy(node->dist, cls_vals); 
     434    } else { 
     435        float n, sum, sum2, cls_val; 
     436 
     437        assert(args->type == Regression); 
     438        if (size == 0) { 
     439            assert(parent); 
     440            node->type = PredictorNode; 
     441            node->n = parent->n; 
     442            node->sum = parent->sum; 
     443            return node; 
     444        } 
     445 
     446        n = sum = sum2 = 0.0; 
     447        for (ex = examples, ex_end = examples + size; ex < ex_end; ex++) 
     448            if (!ex->example->getClass().isSpecial()) { 
     449                cls_val = ex->example->getClass().floatV; 
     450                n += ex->weight; 
     451                sum += ex->weight * cls_val; 
     452                sum2 += ex->weight * cls_val * cls_val; 
     453            } 
     454 
     455        cls_mse = (sum2 - sum * sum / n) / n; 
     456    } 
     457 
     458    /* stopping criterion: depth exceeds limit */ 
     459    if (depth == args->maxDepth) 
     460        return make_predictor(node, examples, size, args); 
    251461 
    252462    /* score attributes */ 
    253     if (!finish) { 
    254         cls_entropy = entropy(node->dist, cls_vals); 
    255         best_score = -INFINITY; 
    256         for (i = 0, it = args->domain->attributes->begin(); it != args->domain->attributes->end(); it++, i++) 
    257             if (!args->attr_split_so_far[i]) { 
    258  
    259                 /* select random subset of attributes - CHANGE ME */ 
    260                 if ((double)rand() / RAND_MAX < args->skipProb) 
    261                     continue; 
    262              
    263                 if ((*it)->varType == TValue::INTVAR) { 
    264                     score = score_attribute_d(examples, size, i, cls_entropy, args); 
    265                     if (score > best_score) { 
    266                         best_score = score; 
    267                         best_attr = i; 
    268                     } 
    269                 } else { 
    270                     int rank; 
    271                     assert((*it)->varType == TValue::FLOATVAR); 
    272  
    273                     score = score_attribute_c(examples, size, i, cls_entropy, &rank, args); 
    274                     if (score > best_score) { 
    275                         best_score = score; 
    276                         best_rank = rank; 
    277                         best_attr = i; 
    278                     } 
     463    best_score = -INFINITY; 
     464 
     465    for (i = 0, it = args->domain->attributes->begin(); it != args->domain->attributes->end(); it++, i++) { 
     466        if (!args->attr_split_so_far[i]) { 
     467            /* select random subset of attributes */ 
     468            if ((double)rand() / RAND_MAX < args->skipProb) 
     469                continue; 
     470 
     471            if ((*it)->varType == TValue::INTVAR) { 
     472                score = args->type == Classification ? 
     473                  gain_ratio_d(examples, size, i, cls_entropy, args) : 
     474                  mse_d(examples, size, i, cls_mse, args); 
     475                if (score > best_score) { 
     476                    best_score = score; 
     477                    best_attr = i; 
    279478                } 
    280             } 
    281         finish = best_score == -INFINITY; 
    282     } 
    283  
    284     /* stop splitting - produce predictor node */ 
    285     if (finish) { 
    286         node->type = PredictorNode; 
    287         return node; 
    288     } 
    289     free(node->dist); 
    290  
    291     /* remove examples with unknown values */ 
    292     for (ex = examples, ex_top = examples, ex_end = examples + size; ex != ex_end; ex++) 
    293         if (!(*ex)->values[best_attr].isSpecial()) 
    294             *ex_top++ = *ex; 
    295     size = ex_top - examples; 
     479            } else if ((*it)->varType == TValue::FLOATVAR) { 
     480                score = args->type == Classification ? 
     481                  gain_ratio_c(examples, size, i, cls_entropy, args, &split) : 
     482                  mse_c(examples, size, i, cls_mse, args, &split); 
     483                if (score > best_score) { 
     484                    best_score = score; 
     485                    best_split = split; 
     486                    best_attr = i; 
     487                } 
     488            } 
     489        } 
     490    } 
     491 
     492    if (best_score == -INFINITY) 
     493        return make_predictor(node, examples, size, args); 
    296494 
    297495    if (args->domain->attributes->at(best_attr)->varType == TValue::INTVAR) { 
    298         TExample **tmp; 
    299         int *cnt, no_of_values; 
    300  
    301         /* printf("* %2d %3s %3d %f\n", depth, args->domain->attributes->at(best_attr)->get_name().c_str(), size, best_score); */ 
    302  
    303         node->type = DiscreteNode; 
    304         node->split_attr = best_attr; 
    305          
    306         /* counting sort */ 
    307         no_of_values = args->domain->attributes->at(best_attr)->noOfValues(); 
    308  
    309         ASSERT(tmp = (TExample **) calloc(size, sizeof *tmp)); 
    310         ASSERT(cnt = (int *) calloc(no_of_values, sizeof *cnt)); 
    311          
    312         for (ex = examples, ex_end = examples + size; ex != ex_end; ex++) 
    313             cnt[(*ex)->values[best_attr].intV]++; 
    314  
    315         for (i = 1; i < no_of_values; i++) 
    316             cnt[i] += cnt[i - 1]; 
    317  
    318         for (ex = examples, ex_end = examples + size; ex != ex_end; ex++) 
    319             tmp[--cnt[(*ex)->values[best_attr].intV]] = *ex; 
    320  
    321         memcpy(examples, tmp, size * sizeof(TExample **)); 
    322  
    323         /* recursively build subtrees */ 
    324         node->children_size = no_of_values; 
    325         ASSERT(node->children = (SimpleTreeNode **) calloc(no_of_values, sizeof *node->children)); 
    326  
    327         args->attr_split_so_far[best_attr] = 1; 
    328         for (i = 0; i < no_of_values; i++) { 
    329             int new_size; 
    330  
    331             new_size = (i == no_of_values - 1) ? size - cnt[i] : cnt[i + 1] - cnt[i]; 
    332             node->children[i] = build_tree(examples + cnt[i], new_size, depth + 1, node, args); 
    333         } 
    334         args->attr_split_so_far[best_attr] = 0; 
    335  
    336         free(tmp); 
    337         free(cnt); 
    338     } else if (args->domain->attributes->at(best_attr)->varType == TValue::FLOATVAR) { 
    339         compar_attr = best_attr; 
    340         qsort(examples, size, sizeof(TExample *), compar_examples); 
     496        struct Example *child_examples, *child_ex; 
     497        int attr_vals; 
     498        float size_known, *attr_dist; 
     499 
     500        /* printf("* %2d %3s %3d %f\n", depth, args->domain->attributes->at(best_attr)->get_name().c_str(), size, best_score); */ 
     501 
     502        attr_vals = args->domain->attributes->at(best_attr)->noOfValues();  
     503 
     504        node->type = DiscreteNode; 
     505        node->split_attr = best_attr; 
     506        node->children_size = attr_vals; 
     507 
     508        ASSERT(child_examples = (struct Example *)calloc(size, sizeof *child_examples)); 
     509        ASSERT(node->children = (SimpleTreeNode **)calloc(attr_vals, sizeof *node->children)); 
     510        ASSERT(attr_dist = (float *)calloc(attr_vals, sizeof *attr_dist)); 
     511 
     512        /* attribute distribution */ 
     513        size_known = 0; 
     514        for (ex = examples, ex_end = examples + size; ex < ex_end; ex++) 
     515            if (!ex->example->values[best_attr].isSpecial()) { 
     516                attr_dist[ex->example->values[best_attr].intV] += ex->weight; 
     517                size_known += ex->weight; 
     518            } 
     519 
     520        args->attr_split_so_far[best_attr] = 1; 
     521 
     522        for (i = 0; i < attr_vals; i++) { 
     523            /* create a new example table */ 
     524            for (ex = examples, ex_end = examples + size, child_ex = child_examples; ex < ex_end; ex++) { 
     525                if (ex->example->values[best_attr].isSpecial()) { 
     526                    *child_ex = *ex; 
     527                    child_ex->weight *= attr_dist[i] / size_known; 
     528                    child_ex++; 
     529                } else if (ex->example->values[best_attr].intV == i) { 
     530                    *child_ex++ = *ex; 
     531                } 
     532            } 
     533 
     534            node->children[i] = build_tree(child_examples, child_ex - child_examples, depth + 1, node, args); 
     535        } 
     536                     
     537        args->attr_split_so_far[best_attr] = 0; 
     538 
     539        free(attr_dist); 
     540        free(child_examples); 
     541    } else { 
     542        struct Example *examples_lt, *examples_ge, *ex_lt, *ex_ge; 
     543        float size_lt, size_ge; 
     544 
     545        /* printf("* %2d %3s %3d %f %f\n", depth, args->domain->attributes->at(best_attr)->get_name().c_str(), size, best_split, best_score); */ 
     546 
     547        assert(args->domain->attributes->at(best_attr)->varType == TValue::FLOATVAR); 
     548 
     549        ASSERT(examples_lt = (struct Example *)calloc(size, sizeof *examples)); 
     550        ASSERT(examples_ge = (struct Example *)calloc(size, sizeof *examples)); 
     551 
     552        size_lt = size_ge = 0.0; 
     553        for (ex = examples, ex_end = examples + size; ex < ex_end; ex++) 
     554            if (!ex->example->values[best_attr].isSpecial()) 
     555                if (ex->example->values[best_attr].floatV < best_split) 
     556                    size_lt += ex->weight; 
     557                else 
     558                    size_ge += ex->weight; 
     559 
     560        for (ex = examples, ex_end = examples + size, ex_lt = examples_lt, ex_ge = examples_ge; ex < ex_end; ex++) 
     561            if (ex->example->values[best_attr].isSpecial()) { 
     562                *ex_lt = *ex; 
     563                *ex_ge = *ex; 
     564                ex_lt->weight *= size_lt / (size_lt + size_ge); 
     565                ex_ge->weight *= size_ge / (size_lt + size_ge); 
     566                ex_lt++; 
     567                ex_ge++; 
     568            } else if (ex->example->values[best_attr].floatV < best_split) { 
     569                *ex_lt++ = *ex; 
     570            } else { 
     571                *ex_ge++ = *ex; 
     572            } 
    341573 
    342574        node->type = ContinuousNode; 
    343575        node->split_attr = best_attr; 
    344         node->split = (examples[best_rank]->values[best_attr].floatV + examples[best_rank + 1]->values[best_attr].floatV) / 2.0; 
    345  
    346         /* printf("%2d %3s %.4f\n", depth, args->domain->attributes->at(best_attr)->get_name().c_str(), node->split); */ 
    347  
    348         /* recursively build subtrees */ 
     576        node->split = best_split; 
    349577        node->children_size = 2; 
    350         ASSERT(node->children = (SimpleTreeNode **) calloc(2, sizeof *node->children)); 
    351          
    352         node->children[0] = build_tree(examples, best_rank + 1, depth + 1, node, args); 
    353         node->children[1] = build_tree(examples + best_rank + 1, size - (best_rank + 1), depth + 1, node, args); 
    354     } 
    355  
    356     return node; 
     578        ASSERT(node->children = (SimpleTreeNode **)calloc(2, sizeof *node->children)); 
     579 
     580        node->children[0] = build_tree(examples_lt, ex_lt - examples_lt, depth + 1, node, args); 
     581        node->children[1] = build_tree(examples_ge, ex_ge - examples_ge, depth + 1, node, args); 
     582 
     583        free(examples_lt); 
     584        free(examples_ge); 
     585    } 
     586 
     587    return node; 
    357588} 
    358589 
     
    365596} 
    366597 
    367 PClassifier  
     598PClassifier 
    368599TSimpleTreeLearner::operator()(PExampleGenerator ogen, const int &weight) 
    369 {  
    370     int i, *attr_split_so_far; 
    371     TExample **examples, **ex; 
    372     struct SimpleTreeNode *tree; 
     600{ 
     601    struct Example *examples, *ex; 
     602    struct SimpleTreeNode *tree; 
    373603    struct Args args; 
    374604 
    375     if (!ogen->domain->classVar) 
    376         raiseError("class-less domain"); 
    377      
    378     /* create a tabel with pointers to examples */ 
    379     ASSERT(examples = (TExample **) calloc(ogen->numberOfExamples(), sizeof(TExample**))); 
    380     ex = examples; 
    381     PEITERATE(ei, ogen) 
    382         *(ex++) = &(*ei); 
    383  
    384     ASSERT(args.attr_split_so_far = (int *) calloc(ogen->domain->attributes->size(), sizeof(int))); 
     605    if (!ogen->domain->classVar) 
     606        raiseError("class-less domain"); 
     607 
     608    /* create a tabel with pointers to examples */ 
     609    ASSERT(examples = (struct Example *)calloc(ogen->numberOfExamples(), sizeof *examples)); 
     610    ex = examples; 
     611    PEITERATE(ei, ogen) { 
     612        ex->example = &(*ei); 
     613        ex->weight = 1.0; 
     614        ex++; 
     615    } 
     616 
     617    ASSERT(args.attr_split_so_far = (int *)calloc(ogen->domain->attributes->size(), sizeof(int))); 
    385618    args.minExamples = minExamples; 
    386619    args.maxMajority = maxMajority; 
     
    388621    args.skipProb = skipProb; 
    389622    args.domain = ogen->domain; 
    390  
    391     tree = build_tree(examples, ogen->numberOfExamples(), 0, NULL, &args); 
    392  
    393     free(examples); 
    394     free(args.attr_split_so_far); 
    395  
    396     return new TSimpleTreeClassifier(ogen->domain->classVar, tree); 
     623    args.type = ogen->domain->classVar->varType == TValue::INTVAR ? Classification : Regression; 
     624 
     625    tree = build_tree(examples, ogen->numberOfExamples(), 0, NULL, &args); 
     626 
     627    free(examples); 
     628    free(args.attr_split_so_far); 
     629 
     630    return new TSimpleTreeClassifier(ogen->domain->classVar, tree, args.type); 
    397631} 
    398632 
     
    403637} 
    404638 
    405 TSimpleTreeClassifier::TSimpleTreeClassifier(const PVariable &classVar, struct SimpleTreeNode *t)  
    406     : TClassifier(classVar, true) 
    407 { 
    408     tree = t; 
    409 } 
     639TSimpleTreeClassifier::TSimpleTreeClassifier(const PVariable &classVar, struct SimpleTreeNode *tree, int type) :  
     640    TClassifier(classVar, true), 
     641    tree(tree), 
     642    type(type) 
     643{ 
     644} 
     645 
    410646 
    411647void 
    412 destroy_tree(struct SimpleTreeNode *node) 
     648destroy_tree(struct SimpleTreeNode *node, int type) 
    413649{ 
    414650    int i; 
     
    416652    if (node->type != PredictorNode) { 
    417653        for (i = 0; i < node->children_size; i++) 
    418             destroy_tree(node->children[i]); 
     654            destroy_tree(node->children[i], type); 
    419655        free(node->children); 
    420     } else { 
     656    } 
     657    if (type == Classification) 
    421658        free(node->dist); 
    422     } 
    423659    free(node); 
    424660} 
    425661 
     662 
    426663TSimpleTreeClassifier::~TSimpleTreeClassifier() 
    427664{ 
    428     destroy_tree(tree); 
    429 } 
    430  
    431 int * 
    432 classify(const TExample &ex, struct SimpleTreeNode *node, int *free_dist) 
    433 { 
    434     while (node->type != PredictorNode) { 
     665    destroy_tree(tree, type); 
     666} 
     667 
     668 
     669float * 
     670predict_classification(const TExample &ex, struct SimpleTreeNode *node, int *free_dist) 
     671{ 
     672    int i, j, cls_vals; 
     673    float *dist, *child_dist; 
     674 
     675    while (node->type != PredictorNode) 
    435676        if (ex.values[node->split_attr].isSpecial()) { 
    436             int i, j, cls_vals, *dist, *child_dist; 
    437  
    438677            cls_vals = ex.domain->classVar->noOfValues(); 
    439             ASSERT(dist = (int *) calloc(cls_vals, sizeof *dist)); 
     678            ASSERT(dist = (float *)calloc(cls_vals, sizeof *dist)); 
    440679            for (i = 0; i < node->children_size; i++) { 
    441                 child_dist = classify(ex, node->children[i], free_dist); 
     680                child_dist = predict_classification(ex, node->children[i], free_dist); 
    442681                for (j = 0; j < cls_vals; j++) 
    443682                    dist[j] += child_dist[j]; 
     
    453692            node = node->children[ex.values[node->split_attr].floatV >= node->split]; 
    454693        } 
    455     } 
     694 
    456695    *free_dist = 0; 
    457     return node->dist; 
    458 } 
    459  
    460 TValue  
     696    return node->dist; 
     697} 
     698 
     699 
     700void 
     701predict_regression(const TExample &ex, struct SimpleTreeNode *node, float *sum, float *n) 
     702{ 
     703    int i; 
     704    float local_sum, local_n; 
     705 
     706    while (node->type != PredictorNode) 
     707        if (ex.values[node->split_attr].isSpecial()) { 
     708            *sum = *n = 0; 
     709            for (i = 0; i < node->children_size; i++) { 
     710                predict_regression(ex, node->children[i], &local_sum, &local_n); 
     711                *sum += local_sum; 
     712                *n += local_n; 
     713            } 
     714            return; 
     715        } else if (node->type == DiscreteNode) { 
     716            node = node->children[ex.values[node->split_attr].intV]; 
     717        } else { 
     718            assert(node->type == ContinuousNode); 
     719            node = node->children[ex.values[node->split_attr].floatV > node->split]; 
     720        } 
     721 
     722    *sum = node->sum; 
     723    *n = node->n; 
     724} 
     725 
     726 
     727TValue 
    461728TSimpleTreeClassifier::operator()(const TExample &ex) 
    462729{ 
    463     int i, *dist, free_dist, best_val; 
    464  
    465     dist = classify(ex, tree, &free_dist); 
    466     best_val = 0; 
    467     for (i = 1; i < ex.domain->classVar->noOfValues(); i++) 
    468         if (dist[i] > dist[best_val]) 
    469             best_val = i; 
    470  
    471     if (free_dist) 
    472         free(dist); 
    473     return TValue(best_val); 
     730    if (type == Classification) { 
     731        int i, free_dist, best_val; 
     732        float *dist; 
     733 
     734        dist = predict_classification(ex, tree, &free_dist); 
     735        best_val = 0; 
     736        for (i = 1; i < ex.domain->classVar->noOfValues(); i++) 
     737            if (dist[i] > dist[best_val]) 
     738                best_val = i; 
     739 
     740        if (free_dist) 
     741            free(dist); 
     742        return TValue(best_val); 
     743    } else { 
     744        float sum, n; 
     745 
     746        assert(type == Regression); 
     747 
     748        predict_regression(ex, tree, &sum, &n); 
     749        return TValue(sum / n); 
     750    } 
    474751} 
    475752 
     
    477754TSimpleTreeClassifier::classDistribution(const TExample &ex) 
    478755{ 
    479     int i, *dist, free_dist; 
    480  
    481     dist = classify(ex, tree, &free_dist); 
    482  
    483     PDistribution pdist = TDistribution::create(ex.domain->classVar); 
    484     for (i = 0; i < ex.domain->classVar->noOfValues(); i++) 
    485         pdist->setint(i, dist[i]); 
    486     pdist->normalize(); 
    487  
    488     if (free_dist) 
    489         free(dist); 
    490     return pdist; 
     756    if (type == Classification) { 
     757        int i, free_dist; 
     758        float *dist; 
     759 
     760        dist = predict_classification(ex, tree, &free_dist); 
     761 
     762        PDistribution pdist = TDistribution::create(ex.domain->classVar); 
     763        for (i = 0; i < ex.domain->classVar->noOfValues(); i++) 
     764            pdist->setint(i, dist[i]); 
     765        pdist->normalize(); 
     766 
     767        if (free_dist) 
     768            free(dist); 
     769        return pdist; 
     770    } else { 
     771        return NULL; 
     772    } 
    491773} 
    492774 
     
    494776TSimpleTreeClassifier::predictionAndDistribution(const TExample &ex, TValue &value, PDistribution &dist) 
    495777{ 
    496     value = operator()(ex); 
    497     dist = classDistribution(ex); 
    498 } 
     778    value = operator()(ex); 
     779    dist = classDistribution(ex); 
     780} 
  • source/orange/tdidt_simple.hpp

    r8735 r8770  
    2727 
    2828struct SimpleTreeNode { 
    29     int type, children_size, split_attr, *dist; 
     29    int type, children_size, split_attr; 
    3030    float split; 
    3131    SimpleTreeNode **children; 
    32 }; 
    3332 
    34 struct Split { 
    35     float score, split; 
     33    float *dist;  /* classification */ 
     34    float n, sum; /* regression */ 
    3635}; 
    3736 
     
    5049class ORANGE_API TSimpleTreeClassifier : public TClassifier { 
    5150private: 
     51    int type; 
    5252    struct SimpleTreeNode *tree; 
    5353 
     
    5656 
    5757    TSimpleTreeClassifier(); 
    58     TSimpleTreeClassifier(const PVariable &, struct SimpleTreeNode *tree); 
     58    TSimpleTreeClassifier(const PVariable &, struct SimpleTreeNode *tree, int type); 
    5959    ~TSimpleTreeClassifier(); 
    6060 
Note: See TracChangeset for help on using the changeset viewer.