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 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     // num_labels+1 due to point 1,1
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     // calculate for 1,1
00255     r[i]=float64_t(fp)/m_all_false;
00256     r[num_roc+i]=float64_t(tp)/m_all_true;
00257 
00258     /* paper says:
00259      * auROC+=trapezoid_area(1, fp_prev, 1, tp_prev)
00260      * wrong? was meant for calculating with rates?
00261      */
00262     m_auROC+=trapezoid_area(fp, fp_prev, tp, tp_prev);
00263     m_auROC/=float64_t(m_all_true)*m_all_false; // normalise
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 // FIXME: make as efficient as compute_ROC
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; // recall
00298         r[m_num_labels+i]=float64_t(tp)/(float64_t(tp)+fp); // precision
00299     }
00300 
00301     // sort by ascending recall
00302     CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00303 
00304     // calculate auPRC
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 // FIXME: make as efficient as compute_ROC
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     // sort by ascending false positive rate
00352     CMath::qsort_index(r, r+m_num_labels, m_num_labels);
00353 
00354     // calculate auDET
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) // actually a logical error
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 }

SHOGUN Machine Learning Toolbox - Documentation