J2Medium★ Core Essential · Industrial BedrockPart J · RecSys & Search Metrics

AUC-ROC Calculation with Rank Ties Handling

⚡Flashcard Drill➔

Exact O(N log N) ROC-AUC computation via Wilcoxon-Mann-Whitney rank sums with tie averaging.

⏱️ Time: O(N log N) 排序开销
💾 Space: O(N)
🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
import numpy as np
def calculate_auc_roc_fast(y_true: np.ndarray, y_score: np.ndarray) -> float:
"""
基于秩排序与并列平均的高效 AUC 计算。
"""
y_true = np.asarray(y_true, dtype=bool)
y_score = np.asarray(y_score, dtype=np.float64)
n_pos =
n_neg = len(y_true) - n_pos
if n_pos == 0 or n_neg == 0:
return 0.5
# 升序排序
order = np.argsort(y_score)
sorted_scores = y_score[order]
sorted_labels = y_true[order]
# 计算并列分数的平均秩 (从 1-indexed)
ranks = np.empty(len(y_score), dtype=np.float64)
i = 0
n = len(y_score)
while i < n:
j = i
# 寻找打分相同的连续段
while j < n and sorted_scores[j] == sorted_scores[i]:
j += 1
# 计算平均秩: (i+1 + ... + j) / (j - i) = (i + 1 + j) / 2.0
avg_rank = (i + 1 + j) / 2.0
ranks[i:j] = avg_rank
i = j
# 求所有正样本的秩和
sum_pos_ranks = np.sum(ranks[sorted_labels])
# 核心公式: (Sum_R - M*(M+1)/2) / (M * N)
auc =
return float(auc)
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: Why is Group AUC (GAUC) often preferred over global AUC in recommender evaluation?
Next: NDCG@K (Normalized Discounted Cumulative Gain) →
💡

Core Mental Anchor / Mnemonic

Sort ascending, average tied ranks, sum positive ranks minus M(M+1)/2, divide by M*N.

📐 Mathematical Derivation & Core Formula

AUC=∑i∈PosRanki−M(M+1)2M⋅N\mathrm{AUC} = \frac{\sum_{i \in \mathrm{Pos}} \mathrm{Rank}_i - \frac{M(M+1)}{2}}{M \cdot N}
### Probabilistic Interpretation & Wilcoxon Rank Equivalence
AUC equals the probability that a randomly drawn positive outscores a randomly drawn negative (counting ties as 0.50.5):
AUC=P(y^pos>y^neg)+0.5⋅P(y^pos=y^neg)\mathrm{AUC} = P(\hat{y}_{\text{pos}} > \hat{y}_{\text{neg}}) + 0.5 \cdot P(\hat{y}_{\text{pos}} = \hat{y}_{\text{neg}})
Sorting all M+NM+N scores in O((M+N)log⁡(M+N))O((M+N)\log(M+N)), assigning average ranks to ties, and summing positive ranks gives AUC=∑i∈posranki−M(M+1)/2M⋅N\mathrm{AUC} = \frac{\sum_{i \in \text{pos}} \mathrm{rank}_i - M(M+1)/2}{M \cdot N}.

🔄 Tensor Dimensions & Shape Flow

scores, labels -> argsort ascending -> assign mean ranks to ties -> sum positive ranks -> AUC scalar

🛡️ Numerical Stability & Pitfalls Checklist

  • Assign average rank to identical scores (ties); arbitrary tie ordering skews binary or discrete-score AUC.
  • Return safe fallback (e.g., 0.5) if all labels belong to a single class.

💻 Reference Code Implementation

import numpy as np

def calculate_auc_roc_fast(y_true: np.ndarray, y_score: np.ndarray) -> float:
    """
    基于秩排序与并列平均的高效 AUC 计算。
    """
    y_true = np.asarray(y_true, dtype=bool)
    y_score = np.asarray(y_score, dtype=np.float64)
    
    n_pos = np.sum(y_true)
    n_neg = len(y_true) - n_pos
    if n_pos == 0 or n_neg == 0:
        return 0.5
        
    # 升序排序
    order = np.argsort(y_score)
    sorted_scores = y_score[order]
    sorted_labels = y_true[order]
    
    # 计算并列分数的平均秩 (从 1-indexed)
    ranks = np.empty(len(y_score), dtype=np.float64)
    i = 0
    n = len(y_score)
    while i < n:
        j = i
        # 寻找打分相同的连续段
        while j < n and sorted_scores[j] == sorted_scores[i]:
            j += 1
        # 计算平均秩: (i+1 + ... + j) / (j - i) = (i + 1 + j) / 2.0
        avg_rank = (i + 1 + j) / 2.0
        ranks[i:j] = avg_rank
        i = j
        
    # 求所有正样本的秩和
    sum_pos_ranks = np.sum(ranks[sorted_labels])
    
    # 核心公式: (Sum_R - M*(M+1)/2) / (M * N)
    auc = (sum_pos_ranks - n_pos * (n_pos + 1) / 2.0) / (n_pos * n_neg)
    return float(auc)

🧪 Runnable Assertions & Validation

Copy and run directly in Python / Jupyter:

import numpy as np
# 简单测试用例
y_true = np.array([0, 0, 1, 1])
y_score = np.array([0.1, 0.4, 0.35, 0.8])
# 顺序: 0.1(0, rank1), 0.35(1, rank2), 0.4(0, rank3), 0.8(1, rank4)
# 正样本秩: 2 + 4 = 6; 6 - 2*3/2 = 3; 3 / (2*2) = 0.75
assert calculate_auc_roc_fast(y_true, y_score) == 0.75

# 完美预测
assert calculate_auc_roc_fast(np.array([0, 1]), np.array([0.1, 0.9])) == 1.0
print("✓ AUC-ROC 排序法实现自测通过")

🎯 Core Follow-up Inquiries & Reference Answers

Q1:Why is Group AUC (GAUC) often preferred over global AUC in recommender evaluation?
Global AUC can be inflated by cross-user baseline CTR differences (Simpson's paradox). GAUC computes AUC per user over their own impressions and averages weighted by impressions/clicks, directly measuring personalized within-user ranking quality.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
← Prev: Factorization Machine (FM) O(kd) ImplementationBack to Part J & All 105Next: NDCG@K (Normalized Discounted Cumulative Gain) →