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