Efficient Implementation of ROC AUC Score

Introduction

This post is a continuation of the ROC and AUC Interpretation. Please make sure that you understand that post before reading this one.

In this post, we will implement an efficient ROC AUC Score in Python with \(O(n\log n)\) runtime complexity.

Subscribe to get a notification about future posts.

Explanation

Let’s say we have:

A dataset with positive and negative items
An ML model that predicts a probability score from 0 to 1, representing the probability that the input belongs to the positive class.

Similar to the previous post, we can visualize our dataset and their probability predictions in the same visualization as following:

Positive items in the dataset are shown in green, and negative items are shown in red. The sizes of circles represent the predicted probability scores, with smaller circles representing scores close to 0 and larger circles representing scores close to 1.

Then, choosing a threshold gives us different points on the ROC curve with x representing the false positive rate (FPR) and y representing the true positive rate (TPR). For example:

A threshold of value 0.5 gives us the point \((\frac{3}{8}, \frac{4}{7})\), whereas a threshold of value 0.4:

gives us the point \((\frac{3}{8}, \frac{5}{7})\). We just increased the numerator of the true positive rate when transitioning from 0.5 to 0.4, since a new green point was introduced as a true positive item; everything else remains the same. We would increase the numerator of the false positive rate if a new red point was introduced instead.

Next, we need to calculate the sum of the areas of all trapezoids formed by the mentioned adjacent points:

We would find the sum of all five trapezoids shown above, which will be the ROC AUC score.

Implementation

Let’s setup our environment:

import numpy as np

np.random.seed(0)
n = 100
target = np.random.randint(0, 2, n)
predicted = np.random.rand(n)

We randomly generated targets and predicted probability scores. Let’s check the result of sklearn.metrics.roc_auc_score:

import sklearn
sklearn.metrics.roc_auc_score(target, predicted)

np.float64(0.4277597402597403)

Our implementation should have the same score.

Trapezoid Area

First, let’s implement a helper function that finds the area of the trapezoid defined by two points \((x_0, y_0)\) and \((x_1, y_1)\).

To achieve this, we can add the area of the rectangle and the area of the right triangle, which is:

\[ \begin{align} \text{Area}&=(x_1-x_0) \times y0+\frac{1}{2}(x_1-x_0) \times (y_1-y_0)\\ &= \frac{1}{2}(x_1-x_0) \times (2y_0+y_1 - y_0)\\ &= \frac{1}{2}(x_1-x_0) \times (y_0 + y_1)\\ \end{align} \]

Let’s implement the formula in Python:

def trapezoid_area(p0, p1):
    return (p1[0] - p0[0]) * (p0[1] + p1[1]) / 2.0

ROC AUC Score

It is better explained in the code, but roughtly our algorithm is:

Sort items by their predicted scores, from largest to smallest
Process the sorted items one by one in a loop
1. Form the current point on the ROC curve by: \((\frac{\text{num\_false\_positive}}{\text{num\_negative}}, \frac{\text{num\_true\_positive}}{\text{num\_positive}})\)
2. Add the trapezoid area formed by the previous point and the current one
3. If the current item is positive, then increase num_true_positive by one
4. If the current item is negative, then increase num_false_positive by one

def roc_auc_score(target, predicted):
    n = target.shape[0]
    num_positive = np.sum(target == 1)
    num_negative = n - num_positive 
    
    order = np.argsort(predicted)[::-1]
    last = [0, 0]
    num_true_positive = 0
    num_false_positive = 0
    score = 0
    for index in range(n):
        # Make sure that the new threshold is unique
        if index == 0 or predicted[order[index]] != predicted[order[index - 1]]:
            # True positive rate
            tpr = num_true_positive / num_positive
            # False positive rate
            fpr = num_false_positive / num_negative
            # New point on the ROC curve
            cur = [fpr, tpr]
            
            score += trapezoid_area(last, cur)
            last = cur
        
        if target[order[index]] == 1:
            num_true_positive += 1
        else:
            num_false_positive += 1
    score += trapezoid_area(last, [1, 1])

    return score

roc_auc_score(target, predicted)

np.float64(0.4277597402597403)

Nice, we got exactly the same result as sklearn

The End

I hope you enjoyed this post.

Subscribe to get a notification about future posts.