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 float64_t* 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 (int32_t 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(int32_t)*m_num_labels;
00119 if (m_sortedROC) delete[] m_sortedROC;
00120 m_sortedROC=new int32_t[sz];
00121 if (!m_sortedROC)
00122 SG_ERROR("Couldn't allocate memory for sorted ROC index!\n");
00123
00124 for (int32_t i=0; i<m_num_labels; i++)
00125 m_sortedROC[i]=i;
00126 float64_t* 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> float64_t CPerformanceMeasures::trapezoid_area(
00134 T x1, T x2, T y1, T y2)
00135 {
00136 float64_t base=CMath::abs(x1-x2);
00137 float64_t height_avg=0.5*(float64_t)(y1+y2);
00138 return base*height_avg;
00139 }
00140
00141 void CPerformanceMeasures::compute_confusion_matrix(
00142 float64_t threshold, int32_t *tp, int32_t* fp, int32_t* fn, int32_t* tn)
00143 {
00144 if (!m_true_labels)
00145 SG_ERROR("No true labels given!\n");
00146 if (!m_output)
00147 SG_ERROR("No output data given!\n");
00148 if (m_num_labels<1)
00149 SG_ERROR("Need at least one example!\n");
00150
00151 if (tp)
00152 *tp=0;
00153 if (fp)
00154 *fp=0;
00155 if (fn)
00156 *fn=0;
00157 if (tn)
00158 *tn=0;
00159
00160 for (int32_t i=0; i<m_num_labels; i++)
00161 {
00162 if (m_output->get_label(i)>=threshold)
00163 {
00164 if (m_true_labels->get_label(i)>0)
00165 {
00166 if (tp)
00167 (*tp)++;
00168 }
00169 else
00170 {
00171 if (fp)
00172 (*fp)++;
00173 }
00174 }
00175 else
00176 {
00177 if (m_true_labels->get_label(i)>0)
00178 {
00179 if (fn)
00180 (*fn)++;
00181 }
00182 else
00183 {
00184 if (tn)
00185 (*tn)++;
00186 }
00187 }
00188 }
00189 }
00190
00192
00193 void CPerformanceMeasures::get_ROC(
00194 float64_t** result, int32_t *num, int32_t *dim)
00195 {
00196 *num=m_num_labels+1;
00197 *dim=2;
00198 compute_ROC(result);
00199 }
00200
00201 void CPerformanceMeasures::compute_ROC(float64_t** result)
00202 {
00203 if (!m_true_labels)
00204 SG_ERROR("No true labels given!\n");
00205 if (!m_output)
00206 SG_ERROR("No output data given!\n");
00207 if (m_all_true<1)
00208 SG_ERROR("Need at least one positive example in true labels!\n");
00209 if (m_all_false<1)
00210 SG_ERROR("Need at least one negative example in true labels!\n");
00211
00212 if (!m_sortedROC)
00213 create_sortedROC();
00214
00215
00216 int32_t num_roc=m_num_labels+1;
00217 size_t sz=sizeof(float64_t)*num_roc*2;
00218
00219 float64_t* r=(float64_t*) malloc(sz);
00220 if (!r)
00221 SG_ERROR("Couldn't allocate memory for ROC result!\n");
00222
00223 int32_t fp=0;
00224 int32_t tp=0;
00225 int32_t fp_prev=0;
00226 int32_t tp_prev=0;
00227 float64_t out_prev=CMath::ALMOST_NEG_INFTY;
00228 m_auROC=0.;
00229 int32_t i;
00230
00231 for (i=0; i<m_num_labels; i++)
00232 {
00233 float64_t out=m_output->get_label(m_sortedROC[i]);
00234 if (out!=out_prev)
00235 {
00236 r[i]=(float64_t)fp/(float64_t)m_all_false;
00237 r[num_roc+i]=(float64_t)tp/(float64_t)m_all_true;
00238 m_auROC+=trapezoid_area(fp, fp_prev, tp, tp_prev);
00239
00240 fp_prev=fp;
00241 tp_prev=tp;
00242 out_prev=out;
00243 }
00244
00245 if (m_true_labels->get_label(m_sortedROC[i])==1)
00246 tp++;
00247 else
00248 fp++;
00249 }
00250
00251
00252 r[i]=(float64_t)fp/(float64_t)(m_all_false);
00253 r[num_roc+i]=(float64_t)tp/float64_t(m_all_true);
00254
00255
00256
00257
00258
00259 m_auROC+=trapezoid_area(fp, fp_prev, tp, tp_prev);
00260 m_auROC/=(float64_t)(m_all_true*m_all_false);
00261 *result=r;
00262 }
00263
00265
00266 void CPerformanceMeasures::get_PRC(
00267 float64_t** result, int32_t *num, int32_t *dim)
00268 {
00269 *num=m_num_labels;
00270 *dim=2;
00271 compute_PRC(result);
00272 }
00273
00274
00275 void CPerformanceMeasures::compute_PRC(float64_t** result)
00276 {
00277 if (!m_output)
00278 SG_ERROR("No output data given!\n");
00279 if (m_num_labels<1)
00280 SG_ERROR("Need at least one example!\n");
00281
00282 size_t sz=sizeof(float64_t)*m_num_labels*2;
00283 float64_t* r=(float64_t*) malloc(sz);
00284 if (!r)
00285 SG_ERROR("Couldn't allocate memory for PRC result!\n");
00286
00287 int32_t tp, fp;
00288 float64_t threshold;
00289
00290 for (int32_t i=0; i<m_num_labels; i++)
00291 {
00292 threshold=m_output->get_label(i);
00293 compute_confusion_matrix(threshold, &tp, &fp, NULL, NULL);
00294 r[i]=(float64_t)tp/(float64_t)m_all_true;
00295 r[m_num_labels+i]=(float64_t)tp/(float64_t)(tp+fp);
00296 }
00297
00298
00299 CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00300
00301
00302 m_auPRC=0.;
00303 for (int32_t i=0; i<m_num_labels-1; i++)
00304 {
00305 if (r[1+i]==r[i])
00306 continue;
00307 m_auPRC+=trapezoid_area(
00308 r[1+i], r[i], r[1+m_num_labels+i], r[m_num_labels+i]);
00309 }
00310
00311 *result=r;
00312 }
00313
00315
00316 void CPerformanceMeasures::get_DET(
00317 float64_t** result, int32_t *num, int32_t *dim)
00318 {
00319 *num=m_num_labels;
00320 *dim=2;
00321 compute_DET(result);
00322 }
00323
00324
00325 void CPerformanceMeasures::compute_DET(float64_t** result)
00326 {
00327 if (!m_output)
00328 SG_ERROR("No output data given!\n");
00329 if (m_num_labels<1)
00330 SG_ERROR("Need at least one example!\n");
00331
00332 size_t sz=sizeof(float64_t)*m_num_labels*2;
00333 float64_t* r=(float64_t*) malloc(sz);
00334 if (!r)
00335 SG_ERROR("Couldn't allocate memory for DET result!\n");
00336
00337 int32_t fp, fn;
00338 float64_t threshold;
00339
00340 for (int32_t i=0; i<m_num_labels; i++)
00341 {
00342 threshold=m_output->get_label(i);
00343 compute_confusion_matrix(threshold, NULL, &fp, &fn, NULL);
00344 r[i]=(float64_t)fp/(float64_t)m_all_false;
00345 r[m_num_labels+i]=(float64_t)fn/(float64_t)m_all_false;
00346 }
00347
00348
00349 CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00350
00351
00352 m_auDET=0;
00353 for (int32_t i=0; i<m_num_labels-1; i++)
00354 {
00355 if (r[1+i]==r[i])
00356 continue;
00357 m_auDET+=trapezoid_area(
00358 r[1+i], r[i], r[1+m_num_labels+i], r[m_num_labels+i]);
00359 }
00360
00361 *result=r;
00362 }
00363
00365
00366 float64_t CPerformanceMeasures::get_accuracy(float64_t threshold)
00367 {
00368 if (m_num_labels<1)
00369 SG_ERROR("Need at least one example!\n");
00370
00371 int32_t tp, tn;
00372
00373 compute_confusion_matrix(threshold, &tp, NULL, NULL, &tn);
00374
00375 return (float64_t)(tp+tn)/(float64_t)m_num_labels;
00376 }
00377
00378 void CPerformanceMeasures::compute_accuracy(
00379 float64_t** result, int32_t* num, int32_t* dim, bool do_error)
00380 {
00381 if (!m_output)
00382 SG_ERROR("No output data given!\n");
00383 if (m_num_labels<1)
00384 SG_ERROR("Need at least one example!\n");
00385
00386 *num=m_num_labels;
00387 *dim=2;
00388 size_t sz=sizeof(float64_t)*m_num_labels*(*dim);
00389 float64_t* r=(float64_t*) malloc(sz);
00390 if (!r)
00391 SG_ERROR("Couldn't allocate memory for all accuracy points!\n");
00392
00393 for (int32_t i=0; i<m_num_labels; i++)
00394 {
00395 r[i]=m_output->get_label(i);
00396 if (do_error)
00397 r[i+m_num_labels]=1.0-get_accuracy(r[i]);
00398 else
00399 r[i+m_num_labels]=get_accuracy(r[i]);
00400 }
00401
00402 CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00403 *result=r;
00404 }
00405
00406 void CPerformanceMeasures::get_all_accuracy(
00407 float64_t** result, int32_t* num, int32_t* dim)
00408 {
00409 compute_accuracy(result, num, dim, false);
00410 }
00411
00412 void CPerformanceMeasures::get_all_error(
00413 float64_t** result, int32_t *num, int32_t* dim)
00414 {
00415 compute_accuracy(result, num, dim, true);
00416 }
00417
00419
00420 float64_t CPerformanceMeasures::get_fmeasure(float64_t threshold)
00421 {
00422 float64_t recall, precision;
00423 float64_t denominator;
00424 int32_t tp, fp;
00425
00426 compute_confusion_matrix(threshold, &tp, &fp, NULL, NULL);
00427
00428 if (m_all_true==0)
00429 return 0;
00430 else
00431 recall=(float64_t)tp/(float64_t)m_all_true;
00432
00433 denominator=(float64_t)(tp+fp);
00434 if (denominator==0)
00435 return 0;
00436 else
00437 precision=(float64_t)tp/denominator;
00438
00439 if (recall==0 && precision==0)
00440 return 0;
00441 else if (recall==0)
00442 return 2.0/(1/precision);
00443 else if (precision==0)
00444 return 2.0/(1/recall);
00445 else
00446 return 2.0/(1/precision+1/recall);
00447 }
00448
00449 void CPerformanceMeasures::get_all_fmeasure(
00450 float64_t** result, int32_t* num, int32_t* dim)
00451 {
00452 if (m_num_labels<1)
00453 SG_ERROR("Need at least one example!\n");
00454
00455 *num=m_num_labels;
00456 *dim=2;
00457 size_t sz=sizeof(float64_t)*m_num_labels*(*dim);
00458 float64_t* r=(float64_t*) malloc(sz);
00459 if (!r)
00460 SG_ERROR("Couldn't allocate memory for all F-measure points!\n");
00461
00462 for (int32_t i=0; i<m_num_labels; i++) {
00463 r[i]=m_output->get_label(i);
00464 r[i+m_num_labels]=get_fmeasure(r[i]);
00465 }
00466
00467 CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00468 *result=r;
00469 }
00470
00472
00473 float64_t CPerformanceMeasures::get_CC(float64_t threshold)
00474 {
00475 int32_t tp, fp, fn, tn;
00476 float64_t radix;
00477
00478 compute_confusion_matrix(threshold, &tp, &fp, &fn, &tn);
00479
00480 radix=(float64_t)(tp+fp)*(tp+fn)*(tn+fp)*(tn+fn);
00481 if (radix<=0)
00482 return 0;
00483 else
00484 return (float64_t)(tp*tn-fp*fn)/CMath::sqrt(radix);
00485 }
00486
00487 void CPerformanceMeasures::get_all_CC(
00488 float64_t** result, int32_t* num, int32_t* dim)
00489 {
00490 if (!m_output)
00491 SG_ERROR("No output data given!\n");
00492 if (m_num_labels<1)
00493 SG_ERROR("Need at least one example!\n");
00494
00495 *num=m_num_labels;
00496 *dim=2;
00497 size_t sz=sizeof(float64_t)*m_num_labels*(*dim);
00498
00499 float64_t* r=(float64_t*) malloc(sz);
00500 if (!r)
00501 SG_ERROR("Couldn't allocate memory for all CC points!\n");
00502
00503 for (int32_t i=0; i<m_num_labels; i++)
00504 {
00505 r[i]=m_output->get_label(i);
00506 r[i+m_num_labels]=get_CC(r[i]);
00507 }
00508
00509 CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00510 *result=r;
00511 }
00512
00514
00515 float64_t CPerformanceMeasures::get_WRAcc(float64_t threshold)
00516 {
00517 int32_t tp, fp, fn, tn;
00518 float64_t denominator0, denominator1;
00519
00520 compute_confusion_matrix(threshold, &tp, &fp, &fn, &tn);
00521
00522 denominator0=(float64_t)(tp+fn);
00523 denominator1=(float64_t)(fp+tn);
00524 if (denominator0<=0 && denominator1<=0)
00525 return 0;
00526 else if (denominator0==0)
00527 return -(float64_t)fp/denominator1;
00528 else if (denominator1==0)
00529 return (float64_t)tp/denominator0;
00530 else
00531 return (float64_t)tp/denominator0-(float64_t)fp/denominator1;
00532 }
00533
00534 void CPerformanceMeasures::get_all_WRAcc(
00535 float64_t** result, int32_t* num, int32_t* dim)
00536 {
00537 if (!m_output)
00538 SG_ERROR("No output data given!\n");
00539 if (m_num_labels<1)
00540 SG_ERROR("Need at least one example!\n");
00541
00542 *num=m_num_labels;
00543 *dim=2;
00544 size_t sz=sizeof(float64_t)*m_num_labels*(*dim);
00545
00546 float64_t* r=(float64_t*) malloc(sz);
00547 if (!r)
00548 SG_ERROR("Couldn't allocate memory for all WRAcc points!\n");
00549
00550 for (int32_t i=0; i<m_num_labels; i++)
00551 {
00552 r[i]=m_output->get_label(i);
00553 r[i+m_num_labels]=get_WRAcc(r[i]);
00554 }
00555
00556 CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00557 *result=r;
00558 }
00559
00561
00562 float64_t CPerformanceMeasures::get_BAL(float64_t threshold)
00563 {
00564 int32_t fp, fn;
00565
00566 compute_confusion_matrix(threshold, NULL, &fp, &fn, NULL);
00567
00568 if (m_all_true==0 && m_all_false==0)
00569 return 0;
00570 else if (m_all_true==0)
00571 return 0.5*((float64_t)fp/(float64_t)m_all_false);
00572 else if (m_all_false==0)
00573 return 0.5*((float64_t)fn/(float64_t)m_all_true);
00574 else
00575 return 0.5*((float64_t)fp/(float64_t)m_all_false+(float64_t)fn/(float64_t)m_all_true);
00576 }
00577
00578 void CPerformanceMeasures::get_all_BAL(float64_t** result, int32_t* num, int32_t* dim)
00579 {
00580 if (!m_output)
00581 SG_ERROR("No output data given!\n");
00582 if (m_num_labels<1)
00583 SG_ERROR("Need at least one example!\n");
00584
00585 *num=m_num_labels;
00586 *dim=2;
00587 size_t sz=sizeof(float64_t)*m_num_labels*(*dim);
00588
00589 float64_t* r=(float64_t*) malloc(sz);
00590 if (!r)
00591 SG_ERROR("Couldn't allocate memory for all BAL points!\n");
00592
00593 for (int32_t i=0; i<m_num_labels; i++)
00594 {
00595 r[i]=m_output->get_label(i);
00596 r[i+m_num_labels]=get_BAL(r[i]);
00597 }
00598
00599 CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00600 *result=r;
00601 }