Какая алгоритмическая сложность вычисления ROC-AUC?

Алгоритмическая сложность ROC-AUC

Вычисление ROC-AUC имеет временную сложность O(n log n), где n — количество примеров в датасете. Основная операция — сортировка предсказаний.

Как вычисляется ROC-AUC

ROC-AUC (Area Under the Receiver Operating Characteristic Curve) — это метрика качества классификатора, вычисляемая следующим образом:

1. Сортируем все примеры по предсказанной вероятности: O(n log n)
2. Вычисляем TPR и FPR для каждого порога: O(n)
3. Вычисляем площадь под кривой ROC: O(n)

Итоговая сложность: O(n log n)

Детальный алгоритм

import numpy as np

def compute_roc_auc_manual(y_true, y_pred_proba):
    """Ручное вычисление ROC-AUC: O(n log n)"""
    n = len(y_true)
    
    # Шаг 1: Сортировка по предсказаниям - O(n log n)
    sorted_indices = np.argsort(y_pred_proba)[::-1]  # по убыванию
    y_sorted = y_true[sorted_indices]
    
    # Шаг 2: Вычисляем кумулятивные TPR и FPR - O(n)
    # Идём по порогам от высокого к низкому
    total_positives = np.sum(y_true)
    total_negatives = n - total_positives
    
    tp = 0
    fp = 0
    auc = 0.0
    prev_recall = 0.0
    
    for i in range(n):
        if y_sorted[i] == 1:
            tp += 1
        else:
            fp += 1
        
        # TPR = TP / (TP + FN), FPR = FP / (FP + TN)
        recall = tp / total_positives if total_positives > 0 else 0
        fpr = fp / total_negatives if total_negatives > 0 else 0
        
        # Трапецеидальное интегрирование
        if i > 0:
            auc += (recall + prev_recall) / 2 * (fpr - prev_fpr)
        
        prev_fpr = fpr
        prev_recall = recall
    
    return auc

# Пример использования
y_true = np.array([1, 0, 1, 1, 0, 1, 0, 0, 1])
y_pred_proba = np.array([0.9, 0.2, 0.8, 0.7, 0.3, 0.6, 0.4, 0.1, 0.85])

auc = compute_roc_auc_manual(y_true, y_pred_proba)
print(f"ROC-AUC: {auc:.3f}")

Более эффективный метод: интерпретация как ранг

Есть более интуитивный способ вычисления ROC-AUC через ранги:

def compute_roc_auc_rank(y_true, y_pred_proba):
    """ROC-AUC через ранги: O(n log n)"""
    n_positives = np.sum(y_true)
    n_negatives = len(y_true) - n_positives
    
    # Сортировка - O(n log n)
    ranks = np.argsort(y_pred_proba)[::-1]
    
    # Вычисляем sum of ranks для позитивов - O(n)
    rank_sum = np.sum(np.where(y_true[ranks] == 1)[0] + 1)
    
    # ROC-AUC = (rank_sum - n_pos*(n_pos+1)/2) / (n_pos * n_neg)
    auc = (rank_sum - n_positives * (n_positives + 1) / 2) / (
        n_positives * n_negatives
    )
    
    return auc

Использование scikit-learn

from sklearn.metrics import roc_auc_score
import time
import numpy as np

# Генерируем данные
n = 1000000
y_true = np.random.binomial(1, 0.5, n)
y_pred_proba = np.random.random(n)

# Измеряем время - должно быть O(n log n)
start = time.time()
auc = roc_auc_score(y_true, y_pred_proba)
end = time.time()

print(f"ROC-AUC: {auc:.3f}")
print(f"Время: {end - start:.4f} сек")

Сложность в контексте других метрик

Почему именно O(n log n)?

Разберёмся на примере:

import numpy as np
import matplotlib.pyplot as plt
import time

sizes = [1000, 10000, 100000, 1000000]
times = []

for size in sizes:
    y_true = np.random.binomial(1, 0.5, size)
    y_pred = np.random.random(size)
    
    start = time.time()
    # Главная операция - сортировка
    np.argsort(y_pred)
    end = time.time()
    
    times.append(end - start)
    print(f"Size {size}: {end - start:.4f} сек")

# Если выполняется O(n log n), соотношение должно быть
for i in range(1, len(sizes)):
    ratio = times[i] / times[i-1]
    size_ratio = sizes[i] / sizes[i-1]
    expected_ratio = (size_ratio * np.log(sizes[i])) / np.log(sizes[i-1])
    print(f"Фактическое соотношение: {ratio:.2f}, O(n log n): {expected_ratio:.2f}")

Оптимизации и специальные случаи

from sklearn.metrics import roc_auc_score

# Для очень больших датасетов можно использовать sample_weight
y_true = np.random.binomial(1, 0.5, 1000000)
y_pred = np.random.random(1000000)
sample_weight = np.random.random(1000000)

# Всё равно O(n log n), но с дополнительной обработкой
auc = roc_auc_score(y_true, y_pred, sample_weight=sample_weight)

# Для многоклассовой классификации
# one-vs-rest: O(k * n log n), где k - число классов

Практический совет

ROC-AUC очень быстра на практике:

• На датасете из 1 млн примеров обычно вычисляется < 1 секунды
• Не является узким местом в пайплайне ML
• Вычислительная сложность часто не критична по сравнению с обучением модели

Итог:

• Временная сложность: O(n log n)
• Пространственная сложность: O(n) (для хранения рангов)
• На практике: очень быстро, не нужно оптимизировать