Changeset 8770:992b1400226d in orange
 Timestamp:
 08/24/11 23:14:39 (3 years ago)
 Branch:
 default
 Convert:
 2d6a97cf427959713d141d66ed2869571fa1df3b
 Location:
 source/orange
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

source/orange/tdidt_simple.cpp
r8735 r8770 1 1 /* 2 2 This file is part of Orange. 3 3 4 4 Copyright 19962010 Faculty of Computer and Information Science, University of Ljubljana 5 5 Contact: janez.demsar@fri.unilj.si … … 34 34 35 35 #ifndef _MSC_VER 36 37 36 #include "err.h" 37 #define ASSERT(x) if (!(x)) err(1, "%s:%d", __FILE__, __LINE__) 38 38 #else 39 39 #define ASSERT(x) if(!(x)) exit(1) 40 40 #endif // _MSC_VER 41 41 42 42 #ifndef INFINITY 43 44 43 #include <limits> 44 #define INFINITY numeric_limits<float>::infinity() 45 45 #endif // INFINITY 46 47 #define LOG2(x) log((double) (x)) / log(2.0)48 49 enum { DiscreteNode, ContinuousNode, PredictorNode };50 46 51 47 struct Args { … … 53 49 float maxMajority, skipProb; 54 50 55 int *attr_split_so_far;51 int type, *attr_split_so_far; 56 52 PDomain domain; 57 53 }; 58 54 55 struct Example { 56 TExample *example; 57 float weight; 58 }; 59 60 enum { DiscreteNode, ContinuousNode, PredictorNode }; 61 enum { Classification, Regression }; 62 59 63 int compar_attr; 60 64 61 65 /* 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. 63 67 */ 64 68 int 65 69 compar_examples(const void *ptr1, const void *ptr2) 66 70 { 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()) 70 76 return 1; 71 if ( (*e2)>values[compar_attr].isSpecial())77 if (e2>example>values[compar_attr].isSpecial()) 72 78 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 75 82 76 83 float 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); 84 entropy(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); 85 91 sum += *ip; 86 92 } 87 93 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 97 int 98 test_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 } 91 107 92 108 float 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); 109 gain_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; 100 114 101 115 cls_vals = args>domain>classVar>noOfValues(); 102 116 117 /* minExamples should be at least 1, otherwise there is no point in splitting */ 118 minExamples = args>minExamples < 1 ? 1 : args>minExamples; 119 103 120 /* 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)); 107 124 108 125 /* sort */ 109 126 compar_attr = attr; 110 qsort(examples, size, sizeof( TExample *), compar_examples);127 qsort(examples, size, sizeof(struct Example), compar_examples); 111 128 112 129 /* 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; 120 143 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) 140 155 continue; 141 156 142 157 /* 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; 144 159 score = (cls_entropy  score) / entropy(attr_dist, 2); 160 145 161 146 162 if (score > best_score) { 147 163 best_score = score; 148 * rank = i;164 *best_split = (ex>example>values[attr].floatV + ex_next>example>values[attr].floatV) / 2.0; 149 165 } 150 166 } … … 160 176 } 161 177 178 162 179 float 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); 180 gain_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); 210 233 211 234 /* printf("D %s %f\n", args>domain>attributes>at(attr)>get_name().c_str(), score); */ 212 235 213 236 finish: 214 237 free(cont); 215 238 free(attr_dist); 216 239 free(attr_dist_cls_known); 217 return score; 218 } 240 return score; 241 } 242 243 244 float 245 mse_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 320 float 321 mse_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 369 finish: 370 free(attr_dist); 371 free(variances); 372 373 return score; 374 } 375 219 376 220 377 struct 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))); 378 make_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 397 struct SimpleTreeNode * 398 build_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 230 406 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); 251 461 252 462 /* 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; 279 478 } 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); 296 494 297 495 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 } 341 573 342 574 node>type = ContinuousNode; 343 575 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; 349 577 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; 357 588 } 358 589 … … 365 596 } 366 597 367 PClassifier 598 PClassifier 368 599 TSimpleTreeLearner::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; 373 603 struct Args args; 374 604 375 if (!ogen>domain>classVar) 376 raiseError("classless 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("classless 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))); 385 618 args.minExamples = minExamples; 386 619 args.maxMajority = maxMajority; … … 388 621 args.skipProb = skipProb; 389 622 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); 397 631 } 398 632 … … 403 637 } 404 638 405 TSimpleTreeClassifier::TSimpleTreeClassifier(const PVariable &classVar, struct SimpleTreeNode *t) 406 : TClassifier(classVar, true) 407 { 408 tree = t; 409 } 639 TSimpleTreeClassifier::TSimpleTreeClassifier(const PVariable &classVar, struct SimpleTreeNode *tree, int type) : 640 TClassifier(classVar, true), 641 tree(tree), 642 type(type) 643 { 644 } 645 410 646 411 647 void 412 destroy_tree(struct SimpleTreeNode *node )648 destroy_tree(struct SimpleTreeNode *node, int type) 413 649 { 414 650 int i; … … 416 652 if (node>type != PredictorNode) { 417 653 for (i = 0; i < node>children_size; i++) 418 destroy_tree(node>children[i] );654 destroy_tree(node>children[i], type); 419 655 free(node>children); 420 } else { 656 } 657 if (type == Classification) 421 658 free(node>dist); 422 }423 659 free(node); 424 660 } 425 661 662 426 663 TSimpleTreeClassifier::~TSimpleTreeClassifier() 427 664 { 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 669 float * 670 predict_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) 435 676 if (ex.values[node>split_attr].isSpecial()) { 436 int i, j, cls_vals, *dist, *child_dist;437 438 677 cls_vals = ex.domain>classVar>noOfValues(); 439 ASSERT(dist = ( int *)calloc(cls_vals, sizeof *dist));678 ASSERT(dist = (float *)calloc(cls_vals, sizeof *dist)); 440 679 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); 442 681 for (j = 0; j < cls_vals; j++) 443 682 dist[j] += child_dist[j]; … … 453 692 node = node>children[ex.values[node>split_attr].floatV >= node>split]; 454 693 } 455 } 694 456 695 *free_dist = 0; 457 return node>dist; 458 } 459 460 TValue 696 return node>dist; 697 } 698 699 700 void 701 predict_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 727 TValue 461 728 TSimpleTreeClassifier::operator()(const TExample &ex) 462 729 { 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 } 474 751 } 475 752 … … 477 754 TSimpleTreeClassifier::classDistribution(const TExample &ex) 478 755 { 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 } 491 773 } 492 774 … … 494 776 TSimpleTreeClassifier::predictionAndDistribution(const TExample &ex, TValue &value, PDistribution &dist) 495 777 { 496 497 498 } 778 value = operator()(ex); 779 dist = classDistribution(ex); 780 } 
source/orange/tdidt_simple.hpp
r8735 r8770 27 27 28 28 struct SimpleTreeNode { 29 int type, children_size, split_attr , *dist;29 int type, children_size, split_attr; 30 30 float split; 31 31 SimpleTreeNode **children; 32 };33 32 34 struct Split { 35 float score, split;33 float *dist; /* classification */ 34 float n, sum; /* regression */ 36 35 }; 37 36 … … 50 49 class ORANGE_API TSimpleTreeClassifier : public TClassifier { 51 50 private: 51 int type; 52 52 struct SimpleTreeNode *tree; 53 53 … … 56 56 57 57 TSimpleTreeClassifier(); 58 TSimpleTreeClassifier(const PVariable &, struct SimpleTreeNode *tree );58 TSimpleTreeClassifier(const PVariable &, struct SimpleTreeNode *tree, int type); 59 59 ~TSimpleTreeClassifier(); 60 60
Note: See TracChangeset
for help on using the changeset viewer.