Area Under ROC Curve for Multiple Classes

Question

I am working with a highly class-skewed three class classification problem. The class percentages are A = 1.8%, B = 17.5% and C = 80.7%. According to this paper, the following definition of multi-class AUC is insensitive to class distributions and therefore, I am using it:

Now I am testing 10 different classfiers on the dataset and only one of them has $AUC_{total} > 0.5$. Am I right in assuming that $AUC_{total} = 0.5$ for a random classifier? If yes, are 9 of the classifiers worse than a random classifier (on this data) just because they have a lower $AUC_{total}$? If yes again, can you suggest possible reasons for such poor performance and what can be done.

P.S.: Even the best performing classifier has $AUC_{total}$ of about 0.6.

Answer 1

I assume that to compute $AUC(c_i,c_j)$, you use the classifier obtained by comparing the probabilities of pertaining to these two classes.

Then, for the random classifier which draws uniformly a point $(p_1, \dots, p_n)$ in the $n$-simplex (I denote $n = |C|$), you have $AUC(c_i, c_j) = 0.5$.

As there are $n( n - 1)$ pairs $(c_i, c_j)$, if each $AUC(c_i, c_j) = 0.5$ then $AUC_{total} = 0.5$, yes.

Answer 2

Most classifiers are notoriously bad at unbalanced problems because they optimize error, accuracy or f-measure which is basically saying all INSTANCES are equal. On the other hand measures like ROC AUC, Gini, Informedness, Correlation and Kappa are designed on the assumption that all CLASSES are equal. Another possibility is that you COST classes or instances explicitly and use that as a basis for optimization.

In your case, saying everything is C will net you an accuracy of 80.7 and most neural network and tree classifiers have a bias to this for such an unbalanced set. However, the chance-correct evaluation of this is 0 (Gini=Youden=Informedness=Correlation=Kappa=0 means chance level performance is obtained). Any model which allocates A% to A, B% to B, C% to C randomly should average out (over multiple runs) to 0 for these measures. The "say everything is C" model arbitrarily allocates 0% to A, 0% to B, 100% to C (randomly with the indicated probability).

You need to look for algorithms that optimize the measure you are interested in, viz. ROC AUC or Gini or Informedness (chance-correct learning), or explicitly balance (balanced learning), or allow you to specify class or instance costs explicitly(cost-sensitive learning). On the other hand, some algorithms explicitly debalance (nodes in a decision tree or stages of boosting for example).

I've written several papers about these issues, including deriving chance-correct versions of both NN and Boosting algorithms. There are a lot of people using Kappa and AUC - but you need to look particularly at those addressing the multiclass case. And there is a growing literature on balanced/unbalanced/rebalanced learning.