AUC Code Implementation

The ROC curve uses FPR as the horizontal axis and TPR as the vertical axis. The larger the AUC value, the more likely the model is to classify a sample as positive.

• FPR: False Positive Rate

• TPR: True Positive Rate

AUC is suitable for evaluating datasets with imbalanced positive and negative samples, with a value range of $[0.5, 1]$.

AUC, while aiming to improve Recall, also hopes to reduce the probability of making mistakes and avoid false positives as much as possible — it is relatively conservative.

Calculation Method 1: $O(N^2)$

According to the statistical definition of AUC: randomly draw one positive and one negative sample from the dataset, and the probability that the predicted probability of the positive sample is greater than that of the negative sample is the AUC. It sounds a bit convoluted, but it is essentially the probability of a probability.

$$\begin{align} AUC = \frac{\sum (pred_{pos} > pred_{neg})}{m * n} \end{align}$$

To implement this in code: in a dataset with m positive samples and n negative samples, among the m * n pairs of positive and negative samples, count the number of pairs where the predicted probability of the positive sample is greater than that of the negative sample, then divide by the total number of pairs.

def calcAUC_byProb(labels, probs):

    N = 0           # Number of positive samples

    P = 0           # Number of negative samples

    neg_prob = []   # Predicted values of negative samples

    pos_prob = []   # Predicted values of positive samples

    for index, label in enumerate(labels):

        if label == 1: # Positive sample count++

            P += 1

            pos_prob.append(probs[index])

        else:

            N += 1  # Negative sample count++

            neg_prob.append(probs[index])

    number = 0

    

    for pos in pos_prob: # Iterate over all pairwise combinations of positive and negative samples

        for neg in neg_prob:

            if (pos > neg):  # If the positive sample's predicted value > the negative sample's predicted value, count one concordant pair

                number += 1

            elif (pos == neg):  # If the positive sample's predicted value == the negative sample's predicted value, count 0.5 concordant pair

                number += 0.5

    return number / (N * P)

Calculation Method 2: $O(N \log N)$

There is also a better method with a time complexity of $O(N \log N)$, which is more important than the method above.

$$\begin{align} AUC & = \frac{\sum (pred_{pos} > pred_{neg})}{m * n} \\ & = \frac{\sum_{pos} \sum_{neg} (pred_{pos} > pred_{neg})}{m * n} \\ & = \frac{(\sum_{pos} rank_{pos}) - \frac{m * (1 + m)}{2}}{m * n} \\ \end{align}$$

def get_auc(labels, preds):

    # This code essentially follows the formula:

    # 1. First compute the sum of ranks of positive samples

    # 2. Then subtract (m*(m+1)/2)

    # 3. Finally divide by the number of combinations

    

    # However, special attention must be paid to handling cases where predicted values are equal.

    # For samples with equal predicted values, their corresponding ranks need to be averaged.



    # First sort the data by pred

    sorted_data = sorted(list(zip(labels, preds)), key=lambda item: item[1])

    pos = 0.0       # Number of positive samples

    neg = 0.0       # Number of negative samples

    auc = 0.0

    # Note the boundary value here: initially we set last_pre to the first value, so when iterating to the first value, only count++ occurs

    # and nothing is accumulated into the result yet (because count==0 at that point, there is nothing to accumulate)

    last_pre = sorted_data[0][1]

    count = 0.0

    pre_sum = 0.0    # Sum of ranks of samples with equal predicted values before the current position; ranks start from 1, so in the code below it is i+1

    pos_count = 0.0  # Records the number of positive samples among samples with equal predicted values

    

    # To handle samples with equal predicted values, we adopt a lazy computation strategy here:

    # When predicted values are equal, we only accumulate count, and when we encounter a different value next time,

    # we incorporate them all into the result at once

    for i, (label, pred) in enumerate(sorted_data):

        # Note: the rank is i+1

        if label > 0:

            pos += 1

        else:

            neg += 1

        if last_pre != pred:                    # The current predicted probability differs from the previous value

            # The lazy accumulation strategy is triggered: compute the average and add it to the result, then reset all accumulated states

            auc += pos_count * pre_sum / count  # Note that only the positive sample portion is accumulated into the result

            count = 1

            pre_sum = i + 1                     # Clear the accumulated rank sum and update it to the current rank

            last_pre = pred

            if label > 0:

                pos_count = 1                   # If the current sample is positive, set it to 1

            else:

                pos_count = 0                   # Otherwise set it to 0

        # If the predicted value is the same as the previous one, enter the accumulation state

        else:

            pre_sum += i + 1                    # Ranks are gradually accumulated

            count += 1                          # The counter is also accumulated

            if label > 0:                       # We need to separately record the number of positive samples here, because negative samples are counted

                pos_count += 1                  # when computing the average rank, but they are not included in the rank sum result

    

    

    # Note that after exiting the loop, we need to add one more accumulation.

    # This is because our lazy accumulation strategy above causes the last group of data to not be accumulated

    auc += pos_count * pre_sum / count         

    auc -= pos * (pos + 1) / 2                  # Subtract the cases where positive samples come before other positive samples, i.e., (m+1)m/2 in the formula

    auc = auc / (pos * neg)                     # Divide by the total number of combinations, i.e., m*n in the formula

    return auc