NegativeAUC.h
Go to the documentation of this file.
1//===========================================================================
2/*!
3 *
4 *
5 * \brief Functions for measuring the area under the (ROC) curve
6 *
7 *
8 *
9 * \author Christian Igel
10 * \date 2011
11 *
12 *
13 * \par Copyright 1995-2017 Shark Development Team
14 *
15 * <BR><HR>
16 * This file is part of Shark.
17 * <https://shark-ml.github.io/Shark/>
18 *
19 * Shark is free software: you can redistribute it and/or modify
20 * it under the terms of the GNU Lesser General Public License as published
21 * by the Free Software Foundation, either version 3 of the License, or
22 * (at your option) any later version.
23 *
24 * Shark is distributed in the hope that it will be useful,
25 * but WITHOUT ANY WARRANTY; without even the implied warranty of
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27 * GNU Lesser General Public License for more details.
28 *
29 * You should have received a copy of the GNU Lesser General Public License
30 * along with Shark. If not, see <http://www.gnu.org/licenses/>.
31 *
32 */
33
34#ifndef SHARK_OBJECTIVEFUNCTIONS_NEGATIVE_AUC_H
35#define SHARK_OBJECTIVEFUNCTIONS_NEGATIVE_AUC_H
36
37
38#include <shark/ObjectiveFunctions/AbstractCost.h>
39#include <shark/Core/utility/KeyValuePair.h>
40
41namespace shark {
42///
43/// \brief Negative area under the curve
44///
45/// This class computes the area under the ROC (receiver operating characteristic) curve.
46/// It implements the algorithm described in:
47/// Tom Fawcett. ROC Graphs: Notes and Practical Considerations for Researchers. 2004
48///
49/// The area is negated so that optimizing the AUC corresponds to a minimization task.
50/// \ingroup costfunctions
51template<class LabelType = unsigned int, class OutputType = RealVector>
52class NegativeAUC : public AbstractCost<LabelType, OutputType>
53{
54public:
55 typedef KeyValuePair< double, LabelType > AUCPair;
56
57 /// Constructor.
58 /// \param invert: if set to true, the role of positive and negative class are switched
59 NegativeAUC(bool invert = false) {
60 m_invert = invert;
61 }
62
63 /// \brief From INameable: return the class name.
64 std::string name() const
65 { return "NegativeAUC"; }
66
67 /// \brief Computes area under the curve.
68 /// \param target: class label, 0 or 1
69 /// \param prediction: prediction by classifier, OutputType-valued vector
70 /// \param column: indicates the column of the prediction vector interpreted as probability of positive class
71 double eval(Data<LabelType> const& target, Data<OutputType> const& prediction, unsigned int column) const {
72 SHARK_RUNTIME_CHECK(dataDimension(prediction) > column,"Column number too large");
73
74 std::size_t elements = target.numberOfElements();
75
76 unsigned P = 0; // positive examples
77 unsigned N = 0; // negative examples
78 std::vector<AUCPair> L(elements); // list of predictions and labels
79
80 for(std::size_t i=0; i!= elements; i++) { // build list
81 LabelType t = target.element(i);
82 // negate predictions if m_invert is set
83 if(!m_invert)
84 L[i] = AUCPair(prediction.element(i)(column), t);
85 else
86 L[i] = AUCPair(-prediction.element(i)(column), t);
87 // count positive and negative examples
88 if(t > 0)
89 P++;
90 else
91 N++;
92 }
93
94 std::sort (L.begin(), L.end(),std::greater<AUCPair>() ); // sort in decreasing order
95
96 double A = 0; // area
97 unsigned TP = 0; // true positives
98 unsigned FP = 0; // false positives
99 unsigned TPPrev = 0; // previous true positives
100 unsigned FPPrev = 0; // previous false positives
101 double predictionPrev = -std::numeric_limits<double>::max(); // previous prediction
102 for(std::size_t i=0; i != elements; i++) {
103 if(L[i].key != predictionPrev){
104 A += trapArea(FP/double(N),FPPrev/double(N),TP/double(P),TPPrev/double(P));
105 predictionPrev = L[i].key;
106 FPPrev = FP;
107 TPPrev = TP;
108 }
109 if(L[i].value > 0)
110 TP++; // positive example
111 else
112 FP++; // negative example
113 }
114 // deviation from the original algorithm description: A += trapArea(1, FPPrev, 1, TPPrev);
115 A += trapArea(FP/double(N), FPPrev/double(N), TP/double(P), TPPrev/double(P));
116
117 //~ A /= double(N*P);
118 return -A;
119 }
120
121 /// \brief Computes area under the curve. If the prediction vector is
122 /// 1-dimensional, the "positive" class is mapped to larger values. If
123 /// the prediction vector is 2-dimensional, the second dimension is
124 /// viewed as the "positive" class. For higher dimensional vectors, an
125 /// exception is thrown. In such a case, the column has to be
126 /// explicitly specified as an additional parameter.
127 ///
128 /// \param target: class label, 0 or 1
129 /// \param prediction: prediction by classifier, OutputType-valued vector
130 double eval(Data<LabelType> const& target, Data<OutputType> const& prediction) const {
131 SHARK_RUNTIME_CHECK(prediction.numberOfElements() >= 1,"Empty prediction set");
132 SHARK_RUNTIME_CHECK(dataDimension(prediction) < 3, "Can not compute with more than two columns");
133 std::size_t dim = dataDimension(prediction);
134 if(dim == 1)
135 return eval(target, prediction, 0);
136 else if(dim == 2)
137 return eval(target, prediction, 1);
138 return 0.;
139 }
140
141
142protected:
143 double trapArea(double x1, double x2, double y1, double y2) const {
144 double base = std::abs(x1-x2);
145 double heightAvg = (y1+y2)/2;
146 return base * heightAvg;
147 }
148
149 bool m_invert;
150};
151
152///
153/// \brief Negative Wilcoxon-Mann-Whitney statistic
154///
155/// This class computes the Wilcoxon-Mann-Whitney statistic, which is
156/// an unbiased estimate of the area under the ROC curve.
157///
158/// See, for example:
159/// Corinna Cortes, Mehryar Mohri. Confidence Intervals for the Area under the ROC Curve. NIPS, 2004
160///
161/// The area is negated so that optimizing the AUC corresponds to a minimization task.
162/// \ingroup costfunctions
163template<class LabelType = unsigned int, class OutputType = LabelType>
164class NegativeWilcoxonMannWhitneyStatistic : public AbstractCost<LabelType, OutputType>
165{
166public:
167 /// Constructor.
168 /// \param invert: if set to true, the role of positive and negative class are switched
169 NegativeWilcoxonMannWhitneyStatistic(bool invert = false) {
170 m_invert = invert;
171 }
172
173 /// \brief From INameable: return the class name.
174 std::string name() const
175 { return "NegativeWilcoxonMannWhitneyStatistic"; }
176
177 /// \brief Computes Wilcoxon-Mann-Whitney statistic.
178 /// \param target: interpreted as binary class label
179 /// \param prediction: interpreted as binary class label
180 /// \param column: indicates the column of the prediction vector interpreted as probability of positive class
181 double eval(Data<LabelType> const& target, Data<OutputType> const& prediction, unsigned int column) const {
182 SHARK_RUNTIME_CHECK(prediction(0).size() > column,"column number too large");
183 std::vector<double> pos, neg;
184 for(std::size_t i=0; i<prediction.size(); i++) {
185 if(!m_invert){
186 if(target(i) > 0)
187 pos.push_back(prediction.element(i)(column));
188 else
189 neg.push_back(prediction.element(i)(column));
190 }else{
191 if(target(i) > 0)
192 pos.push_back(-prediction.element(i)(column));
193 else
194 neg.push_back(-prediction.element(i)(column));
195 }
196 }
197 std::size_t m = pos.size();
198 std::size_t n = neg.size();
199
200 std::sort (pos.begin(), pos.end());
201 std::sort (neg.begin(), neg.end());
202
203 double A = 0;
204 for(std::size_t i = 0, j = 0; i != m; i++) {
205 A += j;
206 for(std::size_t j = 0; j != n; j++) {
207 if(pos[i] > neg[j])
208 A++;
209 else
210 break;
211 }
212 }
213
214#ifdef DEBUG
215 // most naive implementation
216 double verifyA = 0.;
217 for(std::size_t i=0; i<m; i++) {
218 for(std::size_t j=0; j<n; j++) {
219 if(pos[i] > neg[j]) verifyA++;
220 }
221 }
222 if (A!=verifyA) {
223 throw( shark::Exception( "shark::WilcoxonMannWhitneyStatistic::eval: error in algorithm, efficient and naive implementation do no coincide", __FILE__, __LINE__ ) );
224 }
225#endif
226
227 return -A / (n*m);
228 }
229
230 double eval(Data<LabelType> const& target, Data<OutputType> const& prediction) const {
231 SHARK_RUNTIME_CHECK(prediction.numberOfElements() >= 1,"Empty prediction set");
232 SHARK_RUNTIME_CHECK(dataDimension(prediction) < 3, "Can not compute with more than two columns");
233
234 std::size_t dim = dataDimension(prediction);
235 if(dim == 1)
236 return eval(target, prediction, 0);
237 else if(dim == 2)
238 return eval(target, prediction, 1);
239 return 0.;
240 }
241
242private:
243 bool m_invert;
244};
245
246
247}
248#endif