PerformanceMeasures.cpp

Go to the documentation of this file.
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 Sebastian Henschel
00008  * Copyright (C) 2008 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 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     // num_labels+1 due to point 1,1
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     // calculate for 1,1
00249     r[i]=(DREAL)fp/(DREAL)(m_all_false);
00250     r[num_roc+i]=(DREAL)tp/DREAL(m_all_true);
00251 
00252     /* paper says:
00253      * auROC+=trapezoid_area(1, fp_prev, 1, tp_prev)
00254      * wrong? was meant for calculating with rates?
00255      */
00256     m_auROC+=trapezoid_area(fp, fp_prev, tp, tp_prev);
00257     m_auROC/=(DREAL)(m_all_true*m_all_false); // normalise
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 // FIXME: make as efficient as compute_ROC
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; // recall
00291         r[m_num_labels+i]=(DREAL)tp/(DREAL)(tp+fp); // precision
00292     }
00293 
00294     // sort by ascending recall
00295     CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00296 
00297     // calculate auPRC
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 // FIXME: make as efficient as compute_ROC
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     // sort by ascending false positive rate
00343     CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00344 
00345     // calculate auDET
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) // actually a logical error
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 }

SHOGUN Machine Learning Toolbox - Documentation