Как эффективно вычисляется ROC-кривая?

ROC-кривая (от англ. receiver operating characteristic, рабочая характеристика приёмника) или «кривая ошибок» — популярный метод оценки качества бинарной классификации, также называемый ROC-анализом. Она базируется на балансе долей двух типов объектов — TPR (true positive rate) или «верно классифицированных» как несущие признак и FPR (false positive rate) «ошибочно классифицированных» как несущие признак — при определении точек порогов (thresholds) решающего правила. Этот метод широко применяется при диагностике опасных заболеваний на ранних стадиях или оценке качества предсказательных моделей в науке и маркетинге.

Для того чтобы вычислить пороговые точки на ROC-кривой (между осями значений TPR и FPR), можно просто многократно оценивать модель логистической регрессии с разными порогами классификации, но это было бы крайне неэффективно. К счастью, в ROC-анализе существует гораздо более эффективный алгоритм расчета на основе сортировки, базирующийся на показателе AUC (от англ. Area Under Curve, площадь под кривой).

>>> import numpy as np
>>> from sklearn import metrics
>>> y = np.array([1, 1, 2, 2])
>>> scores = np.array([0.1, 0.4, 0.35, 0.8])
>>> fpr, tpr, thresholds = metrics.roc_curve(y, scores, pos_label=2)
>>> fpr
array([0. , 0. , 0.5, 0.5, 1. ])
>>> tpr
array([0. , 0.5, 0.5, 1. , 1. ])
>>> thresholds
array([1.8 , 0.8 , 0.4 , 0.35, 0.1 ])

Шаг 1: Определяем, сколько пороговых точек (thresholds points) нам нужно.

Нам не нужно больше точек, чем количество выборок для вероятности/оценки. В примере выше у нас есть массив scores = [0,1, 0,4, 0,35, 0,8]. Если мы выберем точку между 0,35 и 0,4  (так же, как и собственно 0,4), она не добавит новую точку на кривой ROC. Мы можем дополнительно уменьшить количество порогов, выбрав только уникальные пороги (их набор). Мы также можем удалить любые коллинеарные точки.

Временная сложность: O(n)

Шаг 2: Рассчитываем TPR и FPR.

Конечно, можно рассчитать TPR и FPR, рассмотрев каждый порог, подсчитав, сколько баллов выше этой точки, и проверив их истинные метки классов (true labels).

Временная сложность: O (N ^ 2).

Но сортировка массива scores сделает наш подход намного более эффективным:

y_score = [0.8, 0.4, 0.35, 0.1]

y_true = [1, 0, 1, 0] # converted to binary

Если мы повторяем y_score для 0,8, зная, что y_true = 1, тогда истинное положительное количество (TPC) будет равно 1, потому что только у 1 истинная метка >= 0,8. Если рассматривать 0,4,то мы знаем, что 0,8 и 0,4 >= 0,4. Но для 0,4 метка неверна, так что, тем не менее, TPC равен 1 для 0,35. Получается, 0,35 и 0,4 и 0,8 >= 0,35, и есть 2 истинные метки, это означает, что TPC равно 2. Теперь мы можем легко вычислить это с помощью кумулятивной суммы.

TPC = [1, 1, 2, 2]

Мы можем нормализовать это значение по последнему элементу TPC[-1], чтобы получить TPR.

TPR = [0.5, 0.5, 1, 1]

Так же будет выглядеть вывод scikit-learn. Дополнительный порог: 1 + max(score) нужен для того, чтобы убедиться, что ROC начинается с (0, 0).

Точно так же мы можем рассчитать FPR с помощью формулы: 1 + index - TPC.

Общая временная сложность: O(N*logN) (для сортировки).