Towards more efficient multiclass AUC computations

The area under the receiver operating characteristics curve (AUC) can be used to assess the discriminatory power of a dichotomous classifier model. Extending this measure to more than two classes is not obvious, and a number of variants have been proposed in the literature. We investigate a heuristic approximation to a method that generalizes the notion of probabilities being correctly ordered, which is equivalent to AUC, to an arbitrary number of classes. While the exact method is computationally complex, we propose a much simpler heuristic that is linear in the number of classes for every combination of data points. Using one artificial and one real-world data set, we demonstrate empirically that this simple heuristic can provide good approximations to the exact method, with Pearson correlation coefficients between 0.85 and 0.998 across all data sets.