How to determine the quality of a multiclass classifier

Question

Given

• a dataset with instances $x_i$ together with $N$ classes where every instance $x_i$ belongs exactly to one class $y_i$
• a multiclass classifier

After the training and testing I basically have a table with the true class $y_i$ and the predicted class $a_i$ for every instance $x_i$ in the test set. So for every instance I have either a match ($y_i= a_i$) or a miss ($y_i\neq a_i$).

How can I evaluate the quality of the match ? The issue is that some classes can have many members, i.e. many instances belong to it. Obviously if 50% of all data points belong to one class and my final classifier is 50% correct overall, I have gained nothing. I could have just as well made a trivial classifier which outputs that biggest class no matter what the input is.

Is there a standard method to estimate the quality of a classifier based on the known testing set results of matches and hits for each class? Maybe it's even important to distinguish matching rates for each particular class?

The simplest approach I can think of is to exclude the correct matches of the biggest class. What else?

Answer 1

Like binary classification, you can use the empirical error rate for estimating the quality of your classifier. Let $g$ be a classifier, and $x_i$ and $y_i$ be respectively an example in your data base and its class. $$err(g) = \frac{1}{n} \sum_{i \leq n} \mathbb{1}_{g(x_i) \neq y_i}$$ As you said, when the classes are unbalanced, the baseline is not 50% but the proportion of the bigger class. You could add a weight on each class to balance the error. Let $W_y$ be the weight of the class $y$. Set the weights such that $\frac{1}{W_y} \sim \frac{1}{n}\sum_{i \leq n} \mathbb{1}_{y_i = y}$ and define the weighted empirical error $$err_W(g) = \frac{1}{n} \sum_{i \leq n} W_{y_i} \mathbb{1}_{g(x_i) \neq y_i}$$

As Steffen said, the confusion matrix could be a good way to estimate the quality of a classifier. In the binary case, you can derive some measure from this matrix such as sensitivity and specificity, estimating the capability of a classifier to detect a particular class. The source of error of a classifier might be in a particular way. For example a classifier could be too much confident when predicting a 1, but never say wrong when predicting a 0. Many classifiers can be parametrized to control this rate (false positives vs false negatives), and you are then interested in the quality of the whole family of classifier, not just one. From this you can plot the ROC curve, and measuring the area under the ROC curve give you the quality of those classifiers.

ROC curves can be extended for your multiclass problem. I suggest you to read the answer of this thread.

Answer 2

To evaluate multi-way text classification systems, I use micro- and macro-averaged F1 (F-measure). The F-measure is essentially a weighted combination of precision and recall that. For binary classification, the micro and macro approaches are the same, but, for the multi-way case, I think they might help you out. You can think of Micro F1 as a weighted combination of precision and recall that gives equal weight to every document, while Macro F1 gives equal weight to every class. For each, the F-measure equation is the same, but you calculate precision and recall differently:

$$F = \frac{(\beta^{2} + 1)PR}{\beta^{2}P+R},$$

where $\beta$ is typically set to 1. Then,

$$P_{micro}=\frac{\sum^{|C|}_{i=1}TP_{i}}{\sum^{|C|}_{i=1}TP_{i}+FP_{i}}, R_{micro}=\frac{\sum^{|C|}_{i=1}TP_{i}}{\sum^{|C|}_{i=1}TP_{i}+FN_{i}}$$

$$P_{macro}=\frac{1}{|C|}\sum^{|C|}_{i=1}\frac{TP_{i}}{TP_{i}+FP_{i}}, R_{macro}=\frac{1}{|C|}\sum^{|C|}_{i=1}\frac{TP_{i}}{TP_{i}+FN_{i}}$$

where $TP$ is True Positive, $FP$ is False Positive, $FN$ is False Negative, and $C$ is class.

Answer 3

# Function in R, using precision, recall and F statistics

check.model.accuracy <- function(predicted.class, actual.class){

  result.tbl <- as.data.frame(table(predicted.class,actual.class ) ) 

  result.tbl$Var1 <- as.character(result.tbl$predicted.class)
  result.tbl$Var2 <- as.character(result.tbl$actual.class)

  colnames(result.tbl)[1:2] <- c("Pred","Act")

  cntr <- 0  
  for (pred.class in unique(result.tbl$Pred) ){
    cntr <- cntr+ 1
    tp <- sum(result.tbl[result.tbl$Pred==pred.class & result.tbl$Act==pred.class, "Freq"])
    tp.fp <- sum(result.tbl[result.tbl$Pred == pred.class , "Freq" ])
    tp.fn <- sum(result.tbl[result.tbl$Act == pred.class , "Freq" ])
    presi <- tp/tp.fp 
    rec <- tp/tp.fn
    F.score <- 2*presi*rec/(presi+rec)
    if (cntr == 1 ) F.score.row <- cbind(pred.class, presi,rec,F.score)
    if (cntr > 1 ) F.score.row <- rbind(F.score.row,cbind(pred.class,presi,rec,F.score))
  }

  F.score.row <- as.data.frame(F.score.row) 
  return(F.score.row)
}

check.model.accuracy(predicted.df,actual.df) 
# For multiclass, average across all classes