This is a fun challenge. Here’s my suggestion. Construct an overall weighted accuracy score such that it incorporates not just whether a classifier succeeded or not in predicting the correct class (like in your calculation) but also by how much it succeeded or failed. In other words, the calculation should include the estimated probability as well, in addition to a binary (success/failure) measure.
To demonstrate, I will use an example of 10 users, five original classes, and we will make three predictions -- for top, second best, and third best classes. Below is an example of the original classes (C1 through C5) and estimated probabilities (p1 through p5) for a given classifier.
The next step is to find out the top three estimated probabilities (max_p1 through max_p3), and the true class membership associated with each prediction (C_pred1 through C_pred3):
For instance, the highest estimated probability for User #1 is 0.26 which corresponds to C1. And User #1 does not belong to that class (because C1 = 0), you get a ‘failed’ flag of 0 (instead of 1 for success) in column C_pred1. Similarly, the second best estimated probability (0.25) belongs to C4, and since User #1 does belong to C4, we get C_pred2 = 1.
Now, you can multiply ‘max_p1’ with ‘C_pred1’, and get a set of three scores for each user:
Note that these scores incorporate two things: (1) whether or not the first/second/third best prediction was correct, and (2) the respective estimated probability for the correct prediction. This way, a classifier that assigns high probabilities to correct classes will tend to get a higher score.
The sum of those three scores will give the overall score for each user, which can then be summed up across all users to get the overall weighted accuracy score for a given classifier.
Note that instead of taking a straight sum of the three scores for each user, you can assign weights such that the first prediction gets the highest weight and the third prediction gets the lowest. This can be based on a rule of thumb – depending on how much more important your top/second prediction is versus the others.
You can add some more nuances to this as well: before taking the sum of the triplet scores for each user, divide each of the three scores by the size of the corresponding segment. This will add an adjustment for the unbalanced classes. In other words, a classifier will have to perform better than the baseline probability (i.e., the original size of the class) in order to get a better score.
To summarize, the general idea is this: Make three predictions (class memberships) based on the top three estimated probabilities for each user. Then take the sum of those three probabilities -- but consider only those probabilities where the class predictions were correct. Finally, the overall weighted accuracy score is the sum of those user-level scores across the entire sample. This sum can be divided by the sample size to restrict its value between zero and one. Choose the classifier that has the highest overall weighted accuracy score (preferably on a separate validation set).