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