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-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 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 float64_t CPerformanceMeasures::trapezoid_area(
00134     float64_t x1, float64_t x2, float64_t y1, float64_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     // num_labels+1 due to point 1,1
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     // calculate for 1,1
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     /* paper says:
00256      * auROC+=trapezoid_area(1, fp_prev, 1, tp_prev)
00257      * wrong? was meant for calculating with rates?
00258      */
00259     m_auROC+=trapezoid_area(fp, fp_prev, tp, tp_prev);
00260     m_auROC/=(float64_t)(m_all_true*m_all_false); // normalise
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 // FIXME: make as efficient as compute_ROC
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; // recall
00295         r[m_num_labels+i]=(float64_t)tp/(float64_t)(tp+fp); // precision
00296     }
00297 
00298     // sort by ascending recall
00299     CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00300 
00301     // calculate auPRC
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 // FIXME: make as efficient as compute_ROC
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     // sort by ascending false positive rate
00349     CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00350 
00351     // calculate auDET
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) // actually a logical error
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 }

SHOGUN Machine Learning Toolbox - Documentation