SHOGUN v0.9.0
|
00001 /* 00002 * This program is free software; you can redistribute it and/or modify 00003 * it under the terms of the GNU General Public License as published by 00004 * the Free Software Foundation; either version 3 of the License, or 00005 * (at your option) any later version. 00006 * 00007 * Written (W) 2008-2009 Sebastian Henschel 00008 * Copyright (C) 2008-2009 Friedrich Miescher Laboratory of Max-Planck-Society 00009 */ 00010 00011 #include "evaluation/PerformanceMeasures.h" 00012 00013 #include "lib/ShogunException.h" 00014 #include "lib/Mathematics.h" 00015 00016 using namespace shogun; 00017 00018 CPerformanceMeasures::CPerformanceMeasures() 00019 : CSGObject(), m_true_labels(NULL), m_output(NULL), m_sortedROC(NULL) 00020 { 00021 init_nolabels(); 00022 m_num_labels=0; 00023 m_all_true=0; 00024 m_all_false=0; 00025 } 00026 00027 CPerformanceMeasures::CPerformanceMeasures( 00028 CLabels* true_labels, CLabels* output) 00029 : CSGObject(), m_true_labels(NULL), m_output(NULL), m_sortedROC(NULL) 00030 { 00031 m_num_labels=0; 00032 m_all_true=0; 00033 m_all_false=0; 00034 00035 set_true_labels(true_labels); 00036 set_output(output); 00037 } 00038 00039 CPerformanceMeasures::~CPerformanceMeasures() 00040 { 00041 if (m_true_labels) 00042 SG_UNREF(m_true_labels); 00043 00044 if (m_output) 00045 SG_UNREF(m_output); 00046 00047 if (m_sortedROC) 00048 delete[] m_sortedROC; 00049 } 00050 00052 00053 void CPerformanceMeasures::init_nolabels() 00054 { 00055 delete[] m_sortedROC; 00056 m_sortedROC=NULL; 00057 00058 m_auROC=CMath::ALMOST_NEG_INFTY; 00059 m_auPRC=CMath::ALMOST_NEG_INFTY; 00060 m_auDET=CMath::ALMOST_NEG_INFTY; 00061 } 00062 00063 bool CPerformanceMeasures::set_true_labels(CLabels* true_labels) 00064 { 00065 init_nolabels(); 00066 00067 if (!true_labels) 00068 SG_ERROR("No true labels given!\n"); 00069 00070 float64_t* labels=true_labels->get_labels(m_num_labels); 00071 if (m_num_labels<1) 00072 { 00073 delete[] labels; 00074 SG_ERROR("Need at least one example!\n"); 00075 } 00076 00077 if (m_output && m_num_labels!=m_output->get_num_labels()) 00078 { 00079 delete[] labels; 00080 SG_ERROR("Number of true labels and output labels differ!\n"); 00081 } 00082 00083 for (int32_t i=0; i<m_num_labels; i++) 00084 { 00085 if (labels[i]==1) 00086 m_all_true++; 00087 else if (labels[i]==-1) 00088 m_all_false++; 00089 else 00090 { 00091 delete[] labels; 00092 SG_ERROR("Illegal true labels, not purely {-1, 1}!\n"); 00093 } 00094 } 00095 delete[] labels; 00096 00097 SG_UNREF(m_true_labels); 00098 m_true_labels=true_labels; 00099 SG_REF(m_true_labels); 00100 return true; 00101 } 00102 00103 bool CPerformanceMeasures::set_output(CLabels* output) 00104 { 00105 init_nolabels(); 00106 00107 if (!output) 00108 SG_ERROR("No output given!\n"); 00109 00110 if (m_true_labels && m_true_labels->get_num_labels() != output->get_num_labels()) 00111 SG_ERROR("Number of true labels and output labels differ!\n"); 00112 00113 SG_UNREF(m_output); 00114 m_output=output; 00115 SG_REF(m_output); 00116 return true; 00117 } 00118 00119 void CPerformanceMeasures::create_sortedROC() 00120 { 00121 if (m_num_labels<1) 00122 SG_ERROR("Need at least one example!\n"); 00123 00124 delete[] m_sortedROC; 00125 m_sortedROC=new int32_t[m_num_labels]; 00126 00127 for (int32_t i=0; i<m_num_labels; i++) 00128 m_sortedROC[i]=i; 00129 float64_t* out=m_output->get_labels(m_num_labels); 00130 CMath::qsort_backward_index(out, m_sortedROC, m_num_labels); 00131 delete[] out; 00132 } 00133 00135 00136 float64_t CPerformanceMeasures::trapezoid_area( 00137 float64_t x1, float64_t x2, float64_t y1, float64_t y2) 00138 { 00139 float64_t base=CMath::abs(x1-x2); 00140 float64_t height_avg=0.5*(y1+y2); 00141 float64_t result=base*height_avg; 00142 00143 if (result<0) 00144 SG_ERROR("Negative area - x1=%f x2=%f y1=%f y2=%f\n", x1,x2, y1,y2); 00145 return result; 00146 } 00147 00148 void CPerformanceMeasures::compute_confusion_matrix( 00149 float64_t threshold, int32_t *tp, int32_t* fp, int32_t* fn, int32_t* tn) 00150 { 00151 if (!m_true_labels) 00152 SG_ERROR("No true labels given!\n"); 00153 if (!m_output) 00154 SG_ERROR("No output data given!\n"); 00155 if (m_num_labels<1) 00156 SG_ERROR("Need at least one example!\n"); 00157 00158 if (tp) 00159 *tp=0; 00160 if (fp) 00161 *fp=0; 00162 if (fn) 00163 *fn=0; 00164 if (tn) 00165 *tn=0; 00166 00167 for (int32_t i=0; i<m_num_labels; i++) 00168 { 00169 if (m_output->get_label(i)>=threshold) 00170 { 00171 if (m_true_labels->get_label(i)>0) 00172 { 00173 if (tp) 00174 (*tp)++; 00175 } 00176 else 00177 { 00178 if (fp) 00179 (*fp)++; 00180 } 00181 } 00182 else 00183 { 00184 if (m_true_labels->get_label(i)>0) 00185 { 00186 if (fn) 00187 (*fn)++; 00188 } 00189 else 00190 { 00191 if (tn) 00192 (*tn)++; 00193 } 00194 } 00195 } 00196 } 00197 00199 00200 void CPerformanceMeasures::get_ROC( 00201 float64_t** result, int32_t *num, int32_t *dim) 00202 { 00203 *num=m_num_labels+1; 00204 *dim=2; 00205 compute_ROC(result); 00206 } 00207 00208 void CPerformanceMeasures::compute_ROC(float64_t** result) 00209 { 00210 if (!m_true_labels) 00211 SG_ERROR("No true labels given!\n"); 00212 if (!m_output) 00213 SG_ERROR("No output data given!\n"); 00214 if (m_all_true<1) 00215 SG_ERROR("Need at least one positive example in true labels!\n"); 00216 if (m_all_false<1) 00217 SG_ERROR("Need at least one negative example in true labels!\n"); 00218 00219 if (!m_sortedROC) 00220 create_sortedROC(); 00221 00222 // num_labels+1 due to point 1,1 00223 int32_t num_roc=m_num_labels+1; 00224 size_t sz=sizeof(float64_t)*num_roc*2; 00225 00226 float64_t* r=(float64_t*) malloc(sz); 00227 if (!r) 00228 SG_ERROR("Couldn't allocate memory for ROC result!\n"); 00229 00230 int32_t fp=0; 00231 int32_t tp=0; 00232 int32_t fp_prev=0; 00233 int32_t tp_prev=0; 00234 float64_t out_prev=CMath::ALMOST_NEG_INFTY; 00235 m_auROC=0.; 00236 int32_t i; 00237 00238 for (i=0; i<m_num_labels; i++) 00239 { 00240 float64_t out=m_output->get_label(m_sortedROC[i]); 00241 if (out!=out_prev) 00242 { 00243 r[i]=float64_t(fp)/m_all_false; 00244 r[num_roc+i]=float64_t(tp)/m_all_true; 00245 m_auROC+=trapezoid_area(fp, fp_prev, tp, tp_prev); 00246 00247 fp_prev=fp; 00248 tp_prev=tp; 00249 out_prev=out; 00250 } 00251 00252 if (m_true_labels->get_label(m_sortedROC[i])==1) 00253 tp++; 00254 else 00255 fp++; 00256 } 00257 00258 // calculate for 1,1 00259 r[i]=float64_t(fp)/m_all_false; 00260 r[num_roc+i]=float64_t(tp)/m_all_true; 00261 00262 /* paper says: 00263 * auROC+=trapezoid_area(1, fp_prev, 1, tp_prev) 00264 * wrong? was meant for calculating with rates? 00265 */ 00266 m_auROC+=trapezoid_area(fp, fp_prev, tp, tp_prev); 00267 m_auROC/=float64_t(m_all_true)*m_all_false; // normalise 00268 *result=r; 00269 } 00270 00272 00273 void CPerformanceMeasures::get_PRC( 00274 float64_t** result, int32_t *num, int32_t *dim) 00275 { 00276 *num=m_num_labels; 00277 *dim=2; 00278 compute_PRC(result); 00279 } 00280 00281 // FIXME: make as efficient as compute_ROC 00282 void CPerformanceMeasures::compute_PRC(float64_t** result) 00283 { 00284 if (!m_output) 00285 SG_ERROR("No output data given!\n"); 00286 if (m_num_labels<1) 00287 SG_ERROR("Need at least one example!\n"); 00288 00289 size_t sz=sizeof(float64_t)*m_num_labels*2; 00290 float64_t* r=(float64_t*) malloc(sz); 00291 if (!r) 00292 SG_ERROR("Couldn't allocate memory for PRC result!\n"); 00293 00294 int32_t tp, fp; 00295 float64_t threshold; 00296 00297 for (int32_t i=0; i<m_num_labels; i++) 00298 { 00299 threshold=m_output->get_label(i); 00300 compute_confusion_matrix(threshold, &tp, &fp, NULL, NULL); 00301 r[i]=float64_t(tp)/m_all_true; // recall 00302 r[m_num_labels+i]=float64_t(tp)/(float64_t(tp)+fp); // precision 00303 } 00304 00305 // sort by ascending recall 00306 CMath::qsort_index(r, r+m_num_labels, m_num_labels); 00307 00308 // calculate auPRC 00309 m_auPRC=0.; 00310 for (int32_t i=0; i<m_num_labels-1; i++) 00311 { 00312 if (r[1+i]==r[i]) 00313 continue; 00314 m_auPRC+=trapezoid_area( 00315 r[1+i], r[i], r[1+m_num_labels+i], r[m_num_labels+i]); 00316 } 00317 00318 *result=r; 00319 } 00320 00322 00323 void CPerformanceMeasures::get_DET( 00324 float64_t** result, int32_t *num, int32_t *dim) 00325 { 00326 *num=m_num_labels; 00327 *dim=2; 00328 compute_DET(result); 00329 } 00330 00331 // FIXME: make as efficient as compute_ROC 00332 void CPerformanceMeasures::compute_DET(float64_t** result) 00333 { 00334 if (!m_output) 00335 SG_ERROR("No output data given!\n"); 00336 if (m_num_labels<1) 00337 SG_ERROR("Need at least one example!\n"); 00338 00339 size_t sz=sizeof(float64_t)*m_num_labels*2; 00340 float64_t* r=(float64_t*) malloc(sz); 00341 if (!r) 00342 SG_ERROR("Couldn't allocate memory for DET result!\n"); 00343 00344 int32_t fp, fn; 00345 float64_t threshold; 00346 00347 for (int32_t i=0; i<m_num_labels; i++) 00348 { 00349 threshold=m_output->get_label(i); 00350 compute_confusion_matrix(threshold, NULL, &fp, &fn, NULL); 00351 r[i]=float64_t(fp)/m_all_false; 00352 r[m_num_labels+i]=float64_t(fn)/m_all_false; 00353 } 00354 00355 // sort by ascending false positive rate 00356 CMath::qsort_index(r, r+m_num_labels, m_num_labels); 00357 00358 // calculate auDET 00359 m_auDET=0; 00360 for (int32_t i=0; i<m_num_labels-1; i++) 00361 { 00362 if (r[1+i]==r[i]) 00363 continue; 00364 m_auDET+=trapezoid_area( 00365 r[1+i], r[i], r[1+m_num_labels+i], r[m_num_labels+i]); 00366 } 00367 00368 *result=r; 00369 } 00370 00372 00373 float64_t CPerformanceMeasures::get_accuracy(float64_t threshold) 00374 { 00375 if (m_num_labels<1) 00376 SG_ERROR("Need at least one example!\n"); 00377 00378 int32_t tp, tn; 00379 00380 compute_confusion_matrix(threshold, &tp, NULL, NULL, &tn); 00381 00382 return (float64_t(tp)+tn)/m_num_labels; 00383 } 00384 00385 void CPerformanceMeasures::compute_accuracy( 00386 float64_t** result, int32_t* num, int32_t* dim, bool do_error) 00387 { 00388 if (!m_output) 00389 SG_ERROR("No output data given!\n"); 00390 if (m_num_labels<1) 00391 SG_ERROR("Need at least one example!\n"); 00392 00393 *num=m_num_labels; 00394 *dim=2; 00395 size_t sz=sizeof(float64_t)*m_num_labels*(*dim); 00396 float64_t* r=(float64_t*) malloc(sz); 00397 if (!r) 00398 SG_ERROR("Couldn't allocate memory for all accuracy points!\n"); 00399 00400 for (int32_t i=0; i<m_num_labels; i++) 00401 { 00402 r[i]=m_output->get_label(i); 00403 if (do_error) 00404 r[i+m_num_labels]=1.0-get_accuracy(r[i]); 00405 else 00406 r[i+m_num_labels]=get_accuracy(r[i]); 00407 } 00408 00409 CMath::qsort_index(r, r+m_num_labels, m_num_labels); 00410 *result=r; 00411 } 00412 00413 void CPerformanceMeasures::get_all_accuracy( 00414 float64_t** result, int32_t* num, int32_t* dim) 00415 { 00416 compute_accuracy(result, num, dim, false); 00417 } 00418 00419 void CPerformanceMeasures::get_all_error( 00420 float64_t** result, int32_t *num, int32_t* dim) 00421 { 00422 compute_accuracy(result, num, dim, true); 00423 } 00424 00426 00427 float64_t CPerformanceMeasures::get_fmeasure(float64_t threshold) 00428 { 00429 float64_t recall, precision; 00430 float64_t denominator; 00431 int32_t tp, fp; 00432 00433 compute_confusion_matrix(threshold, &tp, &fp, NULL, NULL); 00434 00435 if (m_all_true==0) 00436 return 0; 00437 else 00438 recall=float64_t(tp)/m_all_true; 00439 00440 denominator=float64_t(tp)+fp; 00441 if (denominator==0) 00442 return 0; 00443 else 00444 precision=float64_t(tp)/denominator; 00445 00446 if (recall==0 && precision==0) 00447 return 0; 00448 else if (recall==0) 00449 return 2.0/(1.0/precision); 00450 else if (precision==0) 00451 return 2.0/(1.0/recall); 00452 else 00453 return 2.0/(1.0/precision+1.0/recall); 00454 } 00455 00456 void CPerformanceMeasures::get_all_fmeasure( 00457 float64_t** result, int32_t* num, int32_t* dim) 00458 { 00459 if (m_num_labels<1) 00460 SG_ERROR("Need at least one example!\n"); 00461 00462 *num=m_num_labels; 00463 *dim=2; 00464 size_t sz=sizeof(float64_t)*m_num_labels*(*dim); 00465 float64_t* r=(float64_t*) malloc(sz); 00466 if (!r) 00467 SG_ERROR("Couldn't allocate memory for all F-measure points!\n"); 00468 00469 for (int32_t i=0; i<m_num_labels; i++) { 00470 r[i]=m_output->get_label(i); 00471 r[i+m_num_labels]=get_fmeasure(r[i]); 00472 } 00473 00474 CMath::qsort_index(r, r+m_num_labels, m_num_labels); 00475 *result=r; 00476 } 00477 00479 00480 float64_t CPerformanceMeasures::get_CC(float64_t threshold) 00481 { 00482 int32_t tp, fp, fn, tn; 00483 float64_t radix; 00484 00485 compute_confusion_matrix(threshold, &tp, &fp, &fn, &tn); 00486 00487 radix=(float64_t(tp)+fp)*(float64_t(tp)+fn)*(float64_t(tn)+fp)*(float64_t(tn)+fn); 00488 if (radix<=0) 00489 return 0; 00490 else 00491 return (float64_t(tp)*tn-float64_t(fp)*fn)/CMath::sqrt(radix); 00492 } 00493 00494 void CPerformanceMeasures::get_all_CC( 00495 float64_t** result, int32_t* num, int32_t* dim) 00496 { 00497 if (!m_output) 00498 SG_ERROR("No output data given!\n"); 00499 if (m_num_labels<1) 00500 SG_ERROR("Need at least one example!\n"); 00501 00502 *num=m_num_labels; 00503 *dim=2; 00504 size_t sz=sizeof(float64_t)*m_num_labels*(*dim); 00505 00506 float64_t* r=(float64_t*) malloc(sz); 00507 if (!r) 00508 SG_ERROR("Couldn't allocate memory for all CC points!\n"); 00509 00510 for (int32_t i=0; i<m_num_labels; i++) 00511 { 00512 r[i]=m_output->get_label(i); 00513 r[i+m_num_labels]=get_CC(r[i]); 00514 } 00515 00516 CMath::qsort_index(r, r+m_num_labels, m_num_labels); 00517 *result=r; 00518 } 00519 00521 00522 float64_t CPerformanceMeasures::get_WRAcc(float64_t threshold) 00523 { 00524 int32_t tp, fp, fn, tn; 00525 float64_t denominator0, denominator1; 00526 00527 compute_confusion_matrix(threshold, &tp, &fp, &fn, &tn); 00528 00529 denominator0=float64_t(tp)+fn; 00530 denominator1=float64_t(fp)+tn; 00531 if (denominator0<=0 && denominator1<=0) 00532 return 0; 00533 else if (denominator0==0) 00534 return -fp/denominator1; 00535 else if (denominator1==0) 00536 return tp/denominator0; 00537 else 00538 return tp/denominator0-fp/denominator1; 00539 } 00540 00541 void CPerformanceMeasures::get_all_WRAcc( 00542 float64_t** result, int32_t* num, int32_t* dim) 00543 { 00544 if (!m_output) 00545 SG_ERROR("No output data given!\n"); 00546 if (m_num_labels<1) 00547 SG_ERROR("Need at least one example!\n"); 00548 00549 *num=m_num_labels; 00550 *dim=2; 00551 size_t sz=sizeof(float64_t)*m_num_labels*(*dim); 00552 00553 float64_t* r=(float64_t*) malloc(sz); 00554 if (!r) 00555 SG_ERROR("Couldn't allocate memory for all WRAcc points!\n"); 00556 00557 for (int32_t i=0; i<m_num_labels; i++) 00558 { 00559 r[i]=m_output->get_label(i); 00560 r[i+m_num_labels]=get_WRAcc(r[i]); 00561 } 00562 00563 CMath::qsort_index(r, r+m_num_labels, m_num_labels); 00564 *result=r; 00565 } 00566 00568 00569 float64_t CPerformanceMeasures::get_BAL(float64_t threshold) 00570 { 00571 int32_t fp, fn; 00572 00573 compute_confusion_matrix(threshold, NULL, &fp, &fn, NULL); 00574 00575 if (m_all_true==0 && m_all_false==0) // actually a logical error 00576 return 0; 00577 else if (m_all_true==0) 00578 return 0.5*fp/m_all_false; 00579 else if (m_all_false==0) 00580 return 0.5*fn/m_all_true; 00581 else 00582 return 0.5*(float64_t(fp)/m_all_false+float64_t(fn)/m_all_true); 00583 } 00584 00585 void CPerformanceMeasures::get_all_BAL(float64_t** result, int32_t* num, int32_t* dim) 00586 { 00587 if (!m_output) 00588 SG_ERROR("No output data given!\n"); 00589 if (m_num_labels<1) 00590 SG_ERROR("Need at least one example!\n"); 00591 00592 *num=m_num_labels; 00593 *dim=2; 00594 size_t sz=sizeof(float64_t)*m_num_labels*(*dim); 00595 00596 float64_t* r=(float64_t*) malloc(sz); 00597 if (!r) 00598 SG_ERROR("Couldn't allocate memory for all BAL points!\n"); 00599 00600 for (int32_t i=0; i<m_num_labels; i++) 00601 { 00602 r[i]=m_output->get_label(i); 00603 r[i+m_num_labels]=get_BAL(r[i]); 00604 } 00605 00606 CMath::qsort_index(r, r+m_num_labels, m_num_labels); 00607 *result=r; 00608 }