J2Medium★ 工业基石 (核心高频)Part J · 推荐系统与搜索指标

AUC-ROC 排序法实现(并列 Ties 处理)

⚡闪卡盲测➔

推荐排序与风控评估核心,从 Wilcoxon-Mann-Whitney 统计检验角度,基于秩排序 O(N log N) 并列均值求解。

⏱️ 时间复杂度: O(N log N) 排序开销
💾 空间复杂度: O(N)
🎯 免登录实战自测闭环(先做再看答案)
按「机制回忆 → 关键行填空 → 边界反例 → 追问与错题记录」顺序自测,进度自动保存在本地。
Step 1 · 机制口述与数值稳定性自检
Step 2 · 核心代码关键行补全
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 · 反例与边界断言核对
Step 4 · 面试追问盲答与错题记录
Q1: GAUC(Group AUC)相比全局 AUC 为什么在推荐系统中更能反映算法对真实用户体验的提升?
下一题: NDCG@K 贴现累计增益与理想 IDCG 归一化 →
💡

实战一句话记忆口诀

打分升序排座位,并列各取平均位,正例排位相加扣,除以正负总对数

📐 核心数学公式与机理推导

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}
### 概率定义与 Wilcoxon 秩检验等价性
AUC(Area Under ROC Curve)在物理上严格等价于:随机抽取一个正样本和一个负样本,模型对正样本预测打分高于负样本的概率:
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}})
直接枚举所有正负样本对需要 O(M⋅N)O(M \cdot N)(MM 为正例数,NN 为负例数)。
高效排序法(Mann-Whitney U 检验):
1. 将所有 M+NM + N 个样本按模型预测概率从小到大升序排序;
2. 赋予每个样本排序序号 Rank(从 1 到 M+NM+N);
3. 并列处理(Ties Handling):若多个样本打分完全相同,其 Rank 必须取这组样本的平均序号;
4. 正样本的 Rank 之和减去正样本内部两两组合的位次和 M(M+1)2\frac{M(M+1)}{2},再除以总对数 M⋅NM \cdot N。
整体耗时直接由排序算法决定的 O((M+N)log⁡(M+N))O((M+N) \log(M+N))。

🔄 张量维度与形状流转说明

scores, labels -> argsort 升序 -> 处理 ties 求平均秩 -> 提取正样本 rank 求和 -> 代入闭式解 -> 标量 AUC

🛡️ 数值稳定性自检与边界要点

  • 打分相同时必须赋予平均秩(例如第 2、3 位并列,秩均为 2.5),否则在二值输出或离散打分下计算结果会严重失真
  • 全正或全负样本无法定义 AUC,需捕获异常返回 0.5

💻 完整参考代码实现

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)

🧪 本地测试与正确性断言

可直接复制到本地 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 排序法实现自测通过")

🎯 核心工程追问与标准应答

Q1:GAUC(Group AUC)相比全局 AUC 为什么在推荐系统中更能反映算法对真实用户体验的提升?
全局 AUC 容易被“高活跃但全点击”的重度用户或大盘曝光偏置拉偏(辛普森悖论);GAUC 按照每个独立 User 分别在各自的历史展现列表中计算 AUC 并以展示量加权平均:GAUC=∑uwuAUCu∑uwu\mathrm{GAUC} = \frac{\sum_u w_u \mathrm{AUC}_u}{\sum_u w_u},剔除了用户间固有点击意愿的基础偏差,衡量的是推荐模型在单个用户内部排序的相对保真度。
⚡
想检验本题的肌肉记忆?进入 3 阶闪卡主动回忆盲测
隐藏答案遮罩,自测:审题锚点 ➔ 数理公式机理 ➔ 工业标杆代码与连环追问。3 分钟攻破认知盲区!
🎯 立即在闪卡中盲测此题➔
← 上一题: FM 因子分解机(二阶特征交叉 O(kd) 手撕)返回 Part J 与全部 105 题下一题: NDCG@K 贴现累计增益与理想 IDCG 归一化 →