Changeset 2556

Timestamp:

Aug 20, 2011, 4:28:52 AM (12 years ago)

Author:

Peter

Message:

ROC: implement correction for ties in large sample approximation o p-value. refs #144.

Location:

trunk

Files:

• test/roc.cc (modified) (3 diffs)
• yat/statistics/ROC.cc (modified) (6 diffs)
• yat/statistics/ROC.h (modified) (3 diffs)

trunk/test/roc.cc

@@ -25 +25 @@
 #include "yat/classifier/DataLookupWeighted1D.h"
 #include "yat/classifier/Target.h"
+#include "yat/statistics/Fisher.h"
 #include "yat/statistics/ROC.h"
 #include "yat/statistics/utility.h"
 #include "yat/utility/Vector.h"
 
+#include <cassert>
 #include <cmath>
 #include <fstream>
@@ -37 +39 @@
 
 void test_ties(test::Suite& suite);
+void test_p_exact_with_ties(test::Suite& suite);
+void test_p_approx_with_ties(test::Suite& suite);
 
 int main(int argc, char* argv[])
@@ -96 +100 @@
   add(roc, dlw.begin(), dlw.end(), target);
   test_ties(suite);
-  
+  test_p_approx_with_ties(suite);
+  test_p_exact_with_ties(suite);
+
   return suite.return_value();
+}
+
+
+void test_p_exact_with_ties(test::Suite& suite)
+{
+  suite.out() << "test p exact with ties\n";
+  statistics::ROC roc;
+  /*
+    +++-- 6 
+    ++-+- 5 4.5 *** our case ***
+    +-++- 4 4.5
+    ++--+ 4 3.5
+    +-+-+ 3 3.5
+    +--++ 2 2
+    -+++- 3 3
+    -++-+ 2 2
+    -+-++ 1 0.5
+    --+++ 0 0.5
+   */
+  roc.add(2, true);
+  roc.add(1, true);
+  roc.add(1, false);
+  roc.add(0, true);
+  roc.add(-1, false);
+  roc.area();
+  if (!suite.equal(roc.p_value_one_sided(), 3.0/10.0)) {
+    suite.xadd(false);
+    suite.out() << "p_value_one_sided: expected 0.3\n";
+  }
+  else
+    suite.xadd(true);
+  if (!suite.equal(roc.p_value(), 5.0/10.0)) {
+    suite.xadd(false);
+    suite.out() << "p_value: expected 0.5\n";
+  }
+  else
+    suite.xadd(true);
+}
+
+
+void test_p_approx_with_ties(test::Suite& suite)
+{
+  suite.out() << "test p approx with ties\n";
+  statistics::ROC roc;
+  for (size_t i=0; i<100; ++i) {
+    roc.add(1, i<60);
+    roc.add(0, i<40);
+  }
+  suite.add(suite.equal(roc.area(), 0.6));
+  // Having only two data values, 0 and 1, data can be represented as
+  // a 2x2 contigency table, and ROC test is same as Fisher's exact
+  // test.
+  statistics::Fisher fisher;
+  fisher.oddsratio(60, 40, 40, 60);
+  suite.add(suite.equal_fix(roc.p_value(), fisher.p_value(), 0.0002));
 }
 

trunk/yat/statistics/ROC.cc

@@ -21 +21 @@
 */
 
+#include <iostream>
+
 #include "ROC.h"
 #include "AUC.h"
@@ -26 +28 @@
 #include <gsl/gsl_cdf.h>
 
+#include <cassert>
 #include <cmath>
 #include <utility>
@@ -40 +43 @@
   }
 
-  ROC::~ROC(void)
-  {
-  }
-
 
   void ROC::add(double x, bool target, double w)
@@ -49 +48 @@
     if (!w)
       return;
-    multimap_.insert(std::make_pair(x, std::make_pair(target, w)));
+    typedef std::multimap<double, std::pair<bool, double> > Map;
+    Map::value_type element(x, std::make_pair(target, w));
+    Map::iterator lower = multimap_.lower_bound(x);
+    if (lower!=multimap_.end() && lower->first == x)
+      has_ties_ = true;
+    multimap_.insert(lower, element);
+    //    multimap_.insert(std::make_pair(x, std::make_pair(target, w)));
     if (target)
       w_pos_+=w;
@@ -79 +84 @@
     else
       return 0.5;
-    double sigma = std::sqrt( ( n()+1.0 )/(12*n_pos()*n_neg()) );
-    return gsl_cdf_gaussian_Q(x, sigma);
+    double var = 1.0+n();
+    if (has_ties_) {
+      double correction = 0;
+      Map::const_iterator first = multimap_.begin();
+      Map::const_iterator last = multimap_.begin();
+      while (first!=multimap_.end()) {
+        size_t n = 0;
+        while (first->first == last->first) {
+          ++n;
+          ++last;
+        }
+        correction += n * (n-1) * (n+1);
+        first = last;
+      }
+      /*
+        mn(N+1)/12-[mn/(12N(N-1)) * sum(t(t-1)(t+1))] =
+        mn/12 [ N+1 - 1/(N(N-1)) * sum(t(t-1)(t+1)) ]
+      */
+      var -= correction/(n() * (n()-1));
+    }
+    var = var / (12*n_pos()*n_neg());
+    return gsl_cdf_gaussian_Q(x, std::sqrt(var));
   }
 
@@ -153 +178 @@
   {
     area_=-1;
+    has_ties_ = false;
     w_pos_=0;
     w_neg_=0;

trunk/yat/statistics/ROC.h

@@ -7 +7 @@
   Copyright (C) 2004 Peter Johansson
   Copyright (C) 2005, 2006, 2007, 2008 Jari Häkkinen, Peter Johansson
+  Copyright (C) 2011 Peter Johansson
 
   This file is part of the yat library, http://dev.thep.lu.se/yat
@@ -46 +47 @@
     ///
     ROC(void);
-         
-    ///
-    /// @brief The destructor
-    ///
-    virtual ~ROC(void);
          
     /**
@@ -136 +132 @@
 
     double area_;
+    bool has_ties_;
     unsigned int minimum_size_;
     double w_neg_;
     double w_pos_;
     // <data pair<class, weight> >
-    std::multimap<double, std::pair<bool, double> > multimap_;
+    typedef std::multimap<double, std::pair<bool, double> > Map;
+    Map multimap_;
   };